Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Outlier formation and removal in 3D laser scanned point clouds Wang, Yutao 2014

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2015_february_wang_yutao.pdf [ 8.48MB ]
Metadata
JSON: 24-1.0167059.json
JSON-LD: 24-1.0167059-ld.json
RDF/XML (Pretty): 24-1.0167059-rdf.xml
RDF/JSON: 24-1.0167059-rdf.json
Turtle: 24-1.0167059-turtle.txt
N-Triples: 24-1.0167059-rdf-ntriples.txt
Original Record: 24-1.0167059-source.json
Full Text
24-1.0167059-fulltext.txt
Citation
24-1.0167059.ris

Full Text

 OUTLIER FORMATION AND REMOVAL IN 3D LASER SCANNED POINT CLOUDS by Yutao Wang  B.E., University of Science and Technology of China, 2007 M.E., University of Science and Technology of China, 2010  A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF  DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES (Mechanical Engineering)  THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver)  November 2014  © Yutao Wang, 2014 ii  Abstract  3D scanners have become widely used in many industrial applications in reverse engineering, quality inspection, entertainment industry, etc. Despite the popularity of 3D scanners, the raw scanned data, referred to as point cloud, is often contaminated by outliers not belonging to the scanned surface. Moreover, when the scanned surface is highly reflective, outliers become much more extensive due to specular reflections. Such outliers cause considerable issues to point cloud applications and thus need to be removed through an outlier detection process. Considering the commonness of reflective surfaces in mechanical parts, it is critical to investigate the outlier formation mechanism and develop methods to effectively remove outliers. However, research on how outliers are formed in scanning reflective surfaces is very limited. Meanwhile, existing outlier removal methods show limited effectiveness in detecting extensive outliers.  This thesis investigates the outlier formation mechanism in scanning reflective surfaces using laser scanners, and develops outlier removal algorithms to effectively and efficiently detect outliers in the scanned point clouds. The overall objective is to remove outliers in a raw data to obtain a clean point cloud in order to ensure the performance of point cloud applications. In particular, two outlier formation models, mixed reflections and multi-path reflections, are proposed and verified through experiments. The effects of scanning orientation on outlier formation are also experimentally investigated. A guidance of proper scan path planning is provided in order to reduce the occurrence of outliers. Regarding outlier removal, a rotating scan approach is proposed to efficiently remove view-dependent outliers. A flexible and effective algorithm is also presented to detect the challenging non-isolated outliers as well as other outliers.  iii  Preface  Parts of this thesis have been published in peer reviewed journals and conference proceedings. Chapters are written based on published and submitted journal articles. I was responsible for literature review, method development, experimental tests, data analysis and writing articles for publications. The publications reported work carried out during my Ph.D. research under the supervision of Dr. H.Y. Feng.   List of publications: 1. Wang Y, Feng H-Y, Delorme F-É, Engin S. An adaptive normal estimation method for scanned point clouds with sharp features. Computer-Aided Design 2013;45(11):1333-48. 2. Wang Y, Feng H-Y. Modeling outlier formation in scanning reflective surfaces using a laser stripe scanner. Measurement 2014;57:108-21. 3. Wang Y, Feng H-Y. Outlier detection for scanned point clouds using majority voting. Computer-Aided Design 2014. Accepted. DOI:10.1016/j.cad.2014.11.004 4. Wang Y, Feng H-Y. Outlier formation and removal in laser scanning of reflective surfaces, part I: effects of scanning orientation. Submitted.  5. Wang Y, Feng H-Y. Outlier formation and removal in laser scanning of reflective surfaces, part II: rotating scans. Submitted.   Chapter 3 is based on article #2, in which I proposed the outlier formation models, performed experiments for verification and wrote most of the manuscript with significant input from my supervisor.  iv   Chapter 4 is based on article #4. I defined the three orientation angles to be investigated, conducted experiments, analyzed data and wrote most of the manuscript.   Chapter 5 is based on article #5, which is a continuation of the work presented in Chapter 4. I developed a rotating scan scheme to efficiently remove outliers in the scanned point clouds, conducted all the experiments, and wrote the manuscript.   Chapter 6 is based on article #1 for Section 6.2 and article #3 for other sections. In Section 6.2, I developed and implemented a robust normal vector estimation algorithm to handle sharp features. In Section 6.3, I proposed a comprehensive outlier removal method to detect the challenging non-isolated outliers, as well as other types of outliers. I conducted all the experiments and wrote most of the manuscripts with significant input from my supervisor.    Besides the above journal articles, I have published and presented the following conference articles as part of my thesis:  1. Wang Y, Feng H-Y, Delorme F-É, Engin S. Evaluation of normal vector estimation methods for scanned point clouds. In: The CIRP 1st international conference on virtual machining process technology. 2012. 2. Wang Y, Feng H-Y, Delorme F-É, Engin S. Effects of scanning plane orientation on outlier occurrence in 3D laser scanning of mechanical parts. In: The CIRP 2nd international conference on virtual machining process technology. 2013. v  3. Wang Y, Feng H-Y. Outlier Removal for 3D Scanned Point Clouds from Laser Stripe Scanners. In: The CIRP 3rd international conference on virtual machining process technology. 2014.  vi  Table of Contents  Abstract .......................................................................................................................................... ii Preface ........................................................................................................................................... iii Table of Contents ......................................................................................................................... vi List of Tables ..................................................................................................................................x List of Figures ............................................................................................................................... xi List of Symbols .......................................................................................................................... xvii List of Abbreviations ............................................................................................................... xviii Acknowledgements .................................................................................................................... xix Dedication .....................................................................................................................................xx Chapter 1: Introduction ................................................................................................................1 1.1 Background and Motivation ........................................................................................... 1 1.2 Thesis Overview ............................................................................................................. 4 1.2.1 Objective ..................................................................................................................... 4 1.2.2 Scope ........................................................................................................................... 4 1.2.3 Outline......................................................................................................................... 5 1.3 Outlier Formation............................................................................................................ 7 1.4 Outlier Removal .............................................................................................................. 8 1.5 Contributions................................................................................................................... 9 Chapter 2: Related Work ............................................................................................................11 2.1 Outlier Formation.......................................................................................................... 11 2.2 Outlier Removal ............................................................................................................ 12 vii  Chapter 3: Outlier Formation Model ........................................................................................16 3.1 Introduction ................................................................................................................... 16 3.2 Laser Stripe Scanner ..................................................................................................... 18 3.2.1 Scanning Principle and Parameters ........................................................................... 18 3.2.2 Exposure Time .......................................................................................................... 20 3.3 Two Outlier Formation Models .................................................................................... 24 3.3.1 Reflective Surfaces ................................................................................................... 24 3.3.2 Mixed Reflection Model ........................................................................................... 25 3.3.3 Multi-path Reflection Model .................................................................................... 29 3.4 Experimental Results .................................................................................................... 32 3.4.1 Mixed Reflections ..................................................................................................... 34 3.4.2 Multi-path Reflections .............................................................................................. 41 3.4.3 Case Study ................................................................................................................ 44 3.5 Summary ....................................................................................................................... 47 Chapter 4: Effects of Scanning Orientation on Outlier Formation ........................................48 4.1 Introduction ................................................................................................................... 48 4.2 Scanning Orientation .................................................................................................... 49 4.3 Effects of Scanning Orientation on Mixed Reflections ................................................ 52 4.4 Effects of Scanning Orientation on Multi-path Reflections ......................................... 58 4.5 Discussion of Applications ........................................................................................... 64 4.6 Summary ....................................................................................................................... 67 Chapter 5: View-Dependent Outlier Removal by Rotating Scans ..........................................68 5.1 Introduction ................................................................................................................... 68 viii  5.2 Outlier Removal by Rotating Scans .............................................................................. 69 5.2.1 Outlier View Dependency......................................................................................... 69 5.2.1.1 Overlap Ratio .................................................................................................... 71 5.2.1.2 Point Spacing .................................................................................................... 73 5.2.1.3 Surface Variation .............................................................................................. 73 5.2.2 Rotating Scans .......................................................................................................... 74 5.3 Case Study and Discussion ........................................................................................... 79 5.3.1 Case Study ................................................................................................................ 79 5.3.2 Number of Scans ....................................................................................................... 82 5.4 Comparison with Existing Methods.............................................................................. 83 5.5 Summary ....................................................................................................................... 88 Chapter 6: Generic Outlier Removal using Majority Voting ..................................................90 6.1 Introduction ................................................................................................................... 90 6.2 Robust Normal Vector Estimation ................................................................................ 91 6.2.1 Iterative Reweighted Plane Fitting............................................................................ 95 6.2.2 Adaptive Bandwidth Selection ............................................................................... 100 6.2.3 Case Studies and Discussion ................................................................................... 104 6.2.3.1 Case Studies .................................................................................................... 107 6.2.3.2 Computational Time ....................................................................................... 111 6.2.4 Summary ................................................................................................................. 112 6.3 Non-isolated Outlier Detection ................................................................................... 113 6.3.1 Regular Point Separation ........................................................................................ 114 6.3.2 Majority Voting ...................................................................................................... 119 ix  6.4 Isolated Outlier Removal ............................................................................................ 127 6.4.1 Segmentation........................................................................................................... 127 6.4.2 Outlier Cluster Removal ......................................................................................... 128 6.5 Implementation Results and Discussion ..................................................................... 133 6.5.1 Comparison with Existing Methods........................................................................ 134 6.5.2 Computational Time ............................................................................................... 140 6.5.3 Discussions ............................................................................................................. 140 6.6 Summary ..................................................................................................................... 143 Chapter 7: Conclusions and Future Research Directions ......................................................145 7.1 Conclusions ................................................................................................................. 145 7.2 Future Research Directions ......................................................................................... 147 References ...................................................................................................................................149 Appendices ..................................................................................................................................155 Appendix A Feature Coefficient Estimation........................................................................... 155  x  List of Tables  Table 3.1 Specifications of LDI SLP-250 laser probe .................................................................. 33 Table 4.1 Effects of scanning orientation angles on outlier formation ......................................... 64 Table 5.1 Computational time of the rotating scan method for various test data. ........................ 88 Table 6.1 Computational time of the normal estimation method for various test data. .............. 112 Table 6.2 Computational time of the majority voting method for various test data. .................. 140  xi  List of Figures  Figure 1.1 Outliers in a point cloud scanned from a gear model. ................................................... 3 Figure 1.2 General overview of outlier formation and removal. .................................................... 7 Figure 3.1 Scanning principle and parameters of the laser stripe scanner. ................................... 19 Figure 3.2 Triangulation angle of the laser stripe scanner. ........................................................... 20 Figure 3.3 Scanning a planar surface: (a) underexposure: 0.2 ms; (b) good exposure: 2 ms; and (c) overexposure: 20 ms. .................................................................................................................... 23 Figure 3.4 Light reflection components in scanning a reflective surface. .................................... 25 Figure 3.5 Scanning an edge feature: (a) mixed reflections; and (b) outlier plane. ...................... 26 Figure 3.6 Crossing outlier planes in scanning a concave cylindrical surface. ............................ 29 Figure 3.7 Multi-path reflections in scanning concave geometry: (a) planar intersecting surfaces; (b) cylindrical surface; and (c) outlier starting and ending lines. ................................................. 30 Figure 3.8 Experimental setup for mixed reflections.................................................................... 35 Figure 3.9 Typical scanned results: (a) scanned point cloud with outliers; (b) raw image in the left sensor; (c) raw image in the right sensor; and (d) processed image in FOV. ............................... 36 Figure 3.10 Mixed reflection model validation: (a) scanned point cloud; (b) estimated outlier starting line; and (c) predicted outlier planes. ............................................................................... 38 Figure 3.11 Quantitative comparison of actual and predicted outlier distributions due to mixed reflections. ..................................................................................................................................... 39 Figure 3.12 Scanned point clouds from gauge blocks with varying  : (a) 9 mm; and (b) 20 mm........................................................................................................................................................ 40 Figure 3.13  Scanned point clouds from a 10-mm gauge block with different exposure time. .... 41 xii  Figure 3.14 Experimental setup for multi-path reflections. .......................................................... 42 Figure 3.15  Multi-path reflection model validation: (a) estimated outlier starting line; and (b) predicted outlier planes. ................................................................................................................ 43 Figure 3.16 Quantitative comparison of actual and predicted outlier distributions due to multi-path reflections. ..................................................................................................................................... 43 Figure 3.17 Scanning an aluminum part: two scan paths (top); results from the red path (middle two); and results from the green path (bottom). ........................................................................... 45 Figure 4.1 Laser scanning system. ................................................................................................ 50 Figure 4.2 In-plane Incident Angle, Out-plane Incident angle and Edge Orientation Angle. ...... 51 Figure 4.3 (a) Mixed reflection model, and (b) Specular reflections with different IIAs. ............ 53 Figure 4.4 Scanned point clouds with various OIAs in mixed reflection model. ......................... 55 Figure 4.5 Scanned point clouds with various IIAs in mixed reflection model. .......................... 56 Figure 4.6 Scanned point clouds with various EOAs in mixed reflection model. ........................ 56 Figure 4.7 Outlier percentage with respect to OIA, IIA and EOA in mixed reflection model. .... 58 Figure 4.8 Multi-path reflection model. ........................................................................................ 59 Figure 4.9 Outliers caused by mirrored light footprints around concave edge. ............................ 60 Figure 4.10 Scanned point clouds with various OIAs in multi-path reflection model. ................ 61 Figure 4.11 Scanned point clouds with various IIAs in multi-path reflection model. .................. 61 Figure 4.12 Scanned point clouds with various EOAs in multi-path reflection model. ............... 62 Figure 4.13 Outlier percentage with respect to OIA, IIA and EOA in multi-path reflection model........................................................................................................................................................ 63 Figure 4.14 Scanned point clouds from an aluminum part (a) with a poorly planned path (b) and a proper scan path (c). ...................................................................................................................... 66 xiii  Figure 5.1 (a) Scanning the top face of a cylinder; (b) Outliers in the scanned point cloud. ....... 70 Figure 5.2 (a) Scanned point clouds from various orientations; (b) Merged data after alignment; (c) Points with high overlaps. ....................................................................................................... 72 Figure 5.3 (a) A path (45° IIA and 0° EOA) to scan the bounding box of a general object; (b) One of the rotated paths (45° IIA and 30° EOA). ................................................................................ 76 Figure 5.4 (a) 12 scanned point clouds; (b) Merged point cloud; (c) Point cloud after outlier removal; and (d) Distributions of overlap ratio, point spacing and surface variation. ................. 80 Figure 5.5 (a) An aluminum part; (b) Scanned point cloud using poorly planned scan paths; (c) Scanned point cloud using rotating scans; and (d) Point cloud after outlier removal .................. 82 Figure 5.6 Merged data (top), overlap ratio distribution (middle) and outlier removal results using different numbers of scans. ........................................................................................................... 83 Figure 5.7 Outlier removal results using various methods. .......................................................... 84 Figure 5.8 Outlier removal results using various methods on a part with concave cylindrical surfaces. ........................................................................................................................................ 85 Figure 5.9 (a) A part with concave cylindrical surfaces; (b) Scanned point cloud using a poorly planned scan path; (c) Scanned point cloud using rotating scans; and (d) Point cloud after outlier removal. ........................................................................................................................................ 86 Figure 5.10 (a) A metal ball bearing; (b) Scanned point cloud using rotating scans; and (c) The point cloud after outlier removal. .................................................................................................. 86 Figure 5.11 (a) An aluminum round plate with holes; (b) Scanned point cloud using rotating scans; and (c) Point cloud after outlier removal. ..................................................................................... 87 xiv  Figure 6.1 (a) A sample scanned point cloud (top) from a gear (bottom); (b) Existing neighborhood weights around a sharp-feature point (top), reconstructed surface (middle), and point-based rendering (bottom); and (c) The proposed anisotropic neighborhood weights and results. ......... 93 Figure 6.2 Iterative reweighted plane fitting for a point around a sharp feature incorporating distance, residual and normal difference weights. ........................................................................ 97 Figure 6.3 Combined weights for neighbors of three typical points on the Fandisk model surface: (a) distance and residual weights; and (b) distance, residual and normal difference weights. ..... 98 Figure 6.4 Normal estimation errors for a noisy cylinder point cloud: (a) infinite large bandwidths; (b) small bandwidths; and (c) adaptive bandwidths. .................................................................. 102 Figure 6.5 (a) A randomly sub-sampled scanned point cloud; (b) Feature coefficient estimation results; (c) d rw w  with global bandwidths; (d) d nw w  with adaptive bandwidths; (e) d r nw w w   with global bandwidths; and (f) d r nw w w   with adaptive bandwidths............. 106 Figure 6.6 Comparison of point-based rendering results of the Carter data. .............................. 108 Figure 6.7 Comparison of the constructed surfaces of the Gear data based on normals estimated by the various methods. ................................................................................................................... 108 Figure 6.8 Estimated normals and constructed surfaces for sub-sampled Gear and Cater data. 110 Figure 6.9 (a) Carter and Ring data with 0.3% noise and 3% outliers; and (b) Point-based rendering results using the estimated normals of this work (outliers not shown for better view). ............. 111 Figure 6.10 Surface variations in a point’s neighborhood among various scenarios: first row: low noise on surface with low curvature (a), high curvature (b) and sharp feature (c); Second row: smooth surface with high noise (d), sparse outliers (e) and non-isolated outliers (f). ................ 115 xv  Figure 6.11 A slice of scanned point cloud from a gear tooth: (a) surface variation plot; (b) regular points (blue) and irregular points (red); and (c) removal of non-isolated outliers in the connection region. ......................................................................................................................................... 117 Figure 6.12 Regular point detection results: first row: surface variation for gear model with sharp feature (a), sheep model with high curvature (b) and 0.5% noise (c); Second row: regular points (blue) and irregular points (red) for each model. ........................................................................ 118 Figure 6.13 Majority voting: (a) regular point iq  as a voter for p ; and (b) majority in  Q  voting p  as an outlier. ............................................................................................................................ 122 Figure 6.14 Non-isolated outlier removal: (a) Shen et al.; and (b) the proposed method. ......... 127 Figure 6.15 A scanned point cloud from a digital camera after majority voting: (a) segmentation; (b) small cluster removal; (c) largest cluster only; and (d) isolated outlier removal. ................. 129 Figure 6.16 Boundary point estimation: (a) initial largest open angle  ; and (b) largest open angle   after expanding the neighborhood. ........................................................................................ 131 Figure 6.17 Scanned point cloud of a camera: (a) segmented point clusters; (b) identified boundary points; and (c) outlier clusters removed. ..................................................................................... 133 Figure 6.18 Outlier removal for the Gear scanned point cloud: (a) raw data; (b) PMR; (c) SP; (d) RG; (e) combined; and (f) proposed. .......................................................................................... 135 Figure 6.19 Outlier removal for the Digital Camera scanned point cloud: (a) raw data; (b) combined; and (c) proposed. ......................................................................................................................... 137 Figure 6.20 Outlier removal for the Ball-End Cutter scanned point cloud: (a) photo; (b) raw data; (c) combined; and (d) proposed. ................................................................................................. 138 xvi  Figure 6.21 Outlier removal for the Room point cloud: (a) original data; and (b) outliers near the room wall removed. .................................................................................................................... 138 Figure 6.22 Reconstructed surfaces from the outlier-removed Gear point clouds from; (a) the combined method; and (b) the proposed method. ....................................................................... 139 Figure 6.23 Outlier removal results for a point cloud (a) using rotating scan method (b) and majority voting method (c). ........................................................................................................ 141 Figure 6.24 Outlier removal for the Elbow Pipe Joint scanned point cloud: (a) photo; (b) raw data; (c) combined; and (d) proposed. ................................................................................................. 142 Figure A.1 Typical Gauss map clustering of normals on the Fandisk model surface. ............... 157 Figure A.2 Sharp feature point percentages (top) and their second derivatives (bottom) with respect to the angle threshold for: (a) Fandisk; (b) Rolling-Stage; and (c) Bunny. ................................ 159 Figure A.3 Normal clustering result for a corner point neighborhood (Icosahedron model with 0.5% imposed noise) ................................................................................................................... 161 Figure A.4 Feature coefficient estimation results for models with 0.5% noise and 0.3% outliers...................................................................................................................................................... 161  xvii  List of Symbols  Symbol Definition p  A measured point x  A point coordinate vector n  Normal vector C  Covariance matrix 0 , 1 , 2  Three eigenvalues of C  l  Local point spacing ( )d iw x  Distance weight ( )r iw r  Residual weight ( )n iw n  Normal difference weight d  Distance weight bandwidth r  Residual weight bandwidth n  Normal difference weight bandwidth Fcoe  Feature coefficient ( )n p  Surface variation of a point p  β   Quadric surface coefficient vector  xviii  List of Abbreviations  Abbreviation Definition CAD Computer-Aided Design CMM Coordinate Measurement Machine EOA Edge Orientation Angle FOV Field of View ICP Iterative Closest Point IIA In-plane Incident Angle IRLSs Iteratively Reweighted Least Squares MLSs Moving Least-Squares OIA Out-plane Incident Angle PCA Principal Component Analysis PH10M PH10 Motorized Indexing Head   xix  Acknowledgements  First I would like to express my sincerest gratitude to my supervisor Dr. Hsi-Yung Feng who has been continuously encouraging and supporting me all through my PhD years. His ideas and vision have helped inspire and guide my research career. I appreciate all his efforts, encouragement and friendship.   I wish to acknowledge the financial support of Natural Sciences and Engineering Research Council of Canada (NSERC) under the CANRIMT Strategic Network Grant. I also would like to thank MeshLab project, Point Cloud Library project and AIM@SHAPE Shape Repository for making their program and data set public.   I would like to thank my supervisory committee members for the time and effort they put to help me improve the quality of this thesis. I also would like to show my gratitude to the external examiner for reviewing this thesis.   Many thanks goes to my exceptional colleagues at CAD/CAM/CAI Lab: Ji, Jack, Farbod and friends at The University of British Columbia – whom I have been fortunate to befriend and learn from.   At the end, I would like to show my deepest gratitude and love to the people that words cannot express how grateful I am to them: my beloved parents, my brother and last but not least, my wonderful wife, Hongyu, for all her love and sacrifice. Thank you all.  xx  Dedication  Commit your work to the Lord, and then your plans will succeed.1  Chapter 1: Introduction 1.1 Background and Motivation With more than three decades of growth and development, 3D optical scanning techniques have successfully evolved from laboratory research to industrial applications [1].  Various types of 3D scanners are now commercially available and have been widely used in industrial applications such as reverse engineering and quality inspection, civil engineering and the entertainment industry.  With the emergence of fast, accurate and affordable 3D scanners, capturing 3D geometry of a physical object becomes a much more cost-effective task than ever.   Although they are generally less accurate than traditional contact-type scanners, such as Coordinate Measurement Machine (CMM) with touch trigger probe, 3D scanners excel in their high scanning speed (minutes VS. hours), tremendous number of coordinate data points (millions VS. thousands) and wide application scope from short range to long range scanning [1]. An optical scanner can generally capture thousands of coordinate data points per second, which reduces the data acquisition time significantly.  Despite the evident advantage in efficient data collection, 3D scanners encounter challenging issues when scanning objects with reflective surfaces such as polished metal or plastic.   Ideally, 3D active scanners typically emit laser lights or structured lights with a certain pattern onto an object with an opaque surface and their image sensors capture the diffuse reflection from the object surface. Based on the principle of triangulation  [2, 3], the scanners can record dense coordinate data points as a point cloud representing the surface geometry of the scanned object. However, when the scanned surface is highly reflective, the image sensors will receive undesirable 2  specular reflections, which can eventually produce coordinate points with large measurement errors as outliers.   Outliers occur when the ideal scanning condition is not met and are inevitable artifacts of optical scanners. In statistics, an outlying observation, or outlier, is one that appears to deviate markedly from other members (inliers) of the sample in which it occurs [4]. However, there is no rigid mathematical definition of what constitutes an outlier. While much research in statistics has been presented to detect outliers in a general data set, they have limited potential to geometrically detect outliers in large 3D point cloud set [5]. From geometrical perspective, outliers in a point cloud are false measurement points that do not belong to the scanned surface. Figure 1.1 shows a typical point cloud scanned from a gear model using a laser scanner. Due to the reflective surface, sharp features and concave geometries, a scanned point cloud usually contains extensive outliers. Some outliers are sparsely distributed, while others are densely clustered. Some clustered outliers are very close to the scanned surfaces and become non-isolated outlier clusters [6]. Detecting such outliers is a challenging task since the object surface to be scanned is usually unknown and any estimation of such surface is subject to be inaccurate in the presence of extensive outliers.  Failing to detect outliers in scanned point clouds will negatively affect many applications. In reverse engineering, outliers can cause ghost surface patches in the constructed surface, which do not exist in the scanned object [6]. Outliers may lead to false rejection by causing abrupt large deviations in quality inspection. Outliers also deteriorate the performance of many point cloud applications such as surface reconstruction [7], normal estimation [8], feature detection [9] and shape modeling [10]. In general, outliers are points not belonging to the scanned surface. Thus, 3  the resultant surface model has low fidelity to represent the actual object due to the interference of outliers. Therefore, it is critical to investigate the outlier formation mechanism in the scanning process and develop effective methods to remove outliers in a scanned point cloud.    Sparse OutliersIsolated Outlier ClusterNon-isolated Outlier Cluster Figure 1.1 Outliers in a point cloud scanned from a gear model.   Many studies have been conducted to investigate the sources of outliers in the 3D scanning process and to develop various approaches to detect outliers in the data processing step. However, most existing work treats the outlier formation and outlier removal separately without taking advantage of each other. On the one hand, many researchers experimentally investigated the factors of measurement errors in a general scanning process. However, research on outlier formation [11, 12] is limited and does not consider how to improve the scanning operation in order to facilitate outlier detection in the following data processing step. On the other hand, various outlier detection methods [5, 6, 13] purely analyze the scanned point cloud only without knowing how outliers are formed in the data acquisition step or utilizing the scanning process information to help remove 4  outliers. These methods generally rely on some ideal assumptions on the regularity of the good surface points and randomness of outliers. However, when scanning reflective surfaces with complex geometries, the scanned point cloud may contain sparse outliers, isolated clustered outliers and non-isolated clustered ones [6] as shown in Figure 1.1. Such outliers are systematic, extensive and complex. Existing outlier detection methods relying on relatively ideal assumptions fail to achieve satisfactory results in detecting such complex outliers. Despite the importance of outlier removal, effectively detecting outliers in a scanned point cloud remains an open problem.   1.2 Thesis Overview 1.2.1 Objective In mechanical engineering, scanning mechanical parts with reflective surfaces is a common yet challenging task using 3D scanners due to the unwanted outliers. Thus, it is highly desirable to understand how outliers are formed during the scanning process and develop effective methods to remove these outliers in scanned point clouds. Different from most existing methods, which treat outlier formation and removal separately, the objective of thesis is to investigate the outlier formation characteristics and integrate such knowledge into the development of outlier detection methods to effectively remove outliers in scanned point clouds. The overall objective is to improve the scanning process and eliminate outliers to produce more accurate point cloud data.   1.2.2 Scope Among various kinds of 3D scanners, the scanner to be studied in this thesis is a type of short-range 3D laser stripe scanner typically used for reverse engineering and quality inspection in mechanical engineering industry. 3D laser scanners capture 3D point data based on the principle 5  of triangulation, which is the same as other types of active scanners. Such laser scanners can offer high-accuracy ( ~10 m ), high-speed (~75,000 points per second), non-contact scanning. The objects to be scanned are mainly mechanical parts with reflective surfaces and complex geometries such as sharp features and curved surfaces. The focus of this thesis is to understand the outlier formation mechanism in scanning reflective surfaces using laser scanners and develop effective methods to remove outliers in the scanned point clouds.   1.2.3 Outline This thesis consists of two major stages: outlier formation in the data acquisition stage, outlier removal in the data processing stage. Figure 1.2 demonstrates the overview of outlier formation and removal in this thesis. In the data acquisition stage, two outlier formation models (Chapter 3) will be proposed and experimentally verified to investigate how outliers are formed in the scanning process using laser scanners. It turns out that the extent of outliers and the regions where outliers occur are directly affected by the relative scanning orientation between the scanner probe and the scanned surface geometry. In other words, proper scanning orientations can help reduce outliers in the scanned point cloud. To investigate the effects of scanning orientation on outlier formation, In Chapter 4 we consider three orientation angles and experimentally investigate their effects based on two proposed models to seek general guidance on selecting appropriate scanning orientations in order to reduce the occurrence of outliers. If outliers can be significantly suppressed in the data acquisition stage, less effort will be required to remove outliers.   In the data processing stage, an outlier removal algorithm using rotating scans is proposed to remove view-dependent outliers (Chapter 5), which are sensitive to the scanning orientations. This 6  approach utilizes the knowledge of scanning orientation effects in Chapter 4 to efficiently remove outliers. Although being computationally fast, this algorithm requires a specific scanning setup. A more generic outlier removal algorithm (Chapter 6) is then proposed, which does not rely on information about the scanning process. This algorithm adopts a majority voting scheme to effectively detect the challenging non-isolated outlier clusters as well as isolated outlier clusters and sparse outliers. This method benefits from a reliable normal vector estimation process as a pre-processing step. A robust normal estimation algorithm (Section 6.2) is developed to effectively estimate normal vectors around sharp features in the presence of noise and outliers.   Overall, this thesis focuses on outliers in scanned point clouds from their formation mechanism and properties to their reduction and removal. The following two sections will present a brief overview of outlier formation and outlier removal respectively.    7  True PointOutlierLight SourcennXZYdoOutlierTSOFψ nβ α α θ Light SourceXZYIn-plane Incident Angle (IIA)Out-plane Incident Angle (OIA)YZX YZXYZ XEdge Orientation Angle (EOA)0° 30°330°60°300°90°270°240°150°210°180°120°Data Acquisition Stage:Outlier Formation Data Processing Stage:Outlier Removal ObjectRaw Point Cloud with Reduced OutliersClean Point CloudTwo Outlier Formation Models (Ch 3)Scanning Orientation Effects (Ch 4)View-Dependent Outlier Removal (Ch 5)Generic Outlier Removal (Ch 6)Normal Vector Estimation (Se 6.2)Mixed Reflection Model Multi-path Reflection Model Figure 1.2 General overview of outlier formation and removal.  1.3 Outlier Formation Compared with noisy data points, which are close to the scanned surface, outliers are false measurement points that deviate significantly from the scanned surface and do not belong to the local surface geometry [5, 6].  Many researchers have investigated various factors causing measurement errors in 3D laser scanning.  However, the effects of reflective surfaces on outlier formation are seldom studied.  In principle, a laser probe emits a laser light onto the scanned object 8  surface and its cameras capture the diffusely reflected laser light.  The light intensity is commonly assumed to follow a Gaussian distribution whose centroid is detected from the captured image to calculate the 3D coordinates of the surface point based on the principle of triangulation [2, 3].  To obtain an ideal Gaussian intensity profile on the image, the best scanning condition is to scan a smooth and diffusely reflective surface without any variation in the surface reflectance, color and geometry [3, 11, 14].  Such an ideal condition is seldom met in practice. As a result, the light intensity profile will be distorted from being a Gaussian and cause biased measurement errors. When the scanned surface is highly reflective, the undesirable specular reflections will further deteriorate the scanning condition and cause erroneous light peeks in the sensor images, which can eventually cause outliers with significantly large measurement errors.   1.4 Outlier Removal Various methods have been proposed to detect sparse and dense outliers in scanned point clouds during the past decades. Regarding sparse outliers, many algorithms [5, 13, 15, 16] utilize local descriptors of each point’s neighborhood to detect irregular points as outliers. Such methods are unreliable in removing dense outliers since the outliers may dominate the local neighborhood. Other methods [17, 18] detect dense outliers in a global sense using clustering techniques. In general, most of the existing methods detect outliers through analyzing the point cloud data only without knowing the outlier formation mechanism or utilizing the scanning setup information. Their effectiveness relies on the regularity of good surface points and randomness of outliers. These methods tend to be unreliable when the outliers become extensive and complex, especially in scanning reflective surfaces.   9  In this thesis, two outlier removal algorithms will be presented to detect outliers from different perspectives. Based on the effects of scanning orientation on outlier formation in Chapter 4, Chapter 5 proposes an outlier removal scheme using rotating scans to efficiently detect view-dependent outliers. The key ingredient of the proposed method is to integrate the scanning orientation information with the point clouds to reliably detect extensive outliers in scanning reflective surfaces. However, this method requires specific rotating scan setup, which may not be generally applicable to all scanning scenarios. Therefore, a more generic outlier removal approach based on majority voting is proposed in Chapter 6. This method aims to detect the challenging non-isolated outlier clusters as well as isolated outlier clusters and sparse outliers without knowing the scanning information. To better preserve important surface points such as sharp features, this method requires a reliable normal vector estimation as a pre-processing step. A robust normal vector estimation (Section 6.2) is proposed to estimate normal around sharp features in a noisy and outlier contaminated point cloud.   1.5 Contributions The main contributions of this thesis are summarized below: 1. In Chapter 3, two outlier formation models, mixed reflections and multi-path reflections, are proposed for scanning reflective surfaces using laser scanners. These two models provide the fundamental mechanism to characterize outlier formation in scanning reflective surfaces.  2. In Chapter 4, the effects of scanning orientation on outlier formation are experimentally investigated, which was seldom studied before. The key observation is that outliers are generally view-dependent, whereas surface points are relatively view-independent. This 10  provides the foundation for the outlier removal method in Chapter 5. Moreover, a general guideline of proper scan path planning is provided.  3. In Chapter 5, an outlier removal scheme using rotating scans is developed to detect view-dependent outliers. Different from most of the existing methods, which purely rely on analyzing point clouds without knowledge of scanning process, this approach is derived from outlier formation characteristic and utilizes the scanning setup information to efficiently detect outliers.  4. In Chapter 6, a generic outlier removal algorithm using majority voting is developed to detect various kinds of outliers. This method can effectively detect non-isolated outlier clusters, which is the most challenging type of outliers, as well as isolated outlier clusters and sparse outliers.  5. In Section 6.2, a normal vector estimation algorithm is proposed to robustly estimate normal vectors in a point cloud. The key ingredient of this approach is to reliably estimate normal vectors around sharp features in the presence of noise and outliers.   Overall, this thesis provides viable methods to properly scan a reflective surface to reduce outliers in the scanning step and effectively remove outliers in the data processing step in order to obtain a clean point cloud.  11  Chapter 2: Related Work 2.1 Outlier Formation Numerous studies have been conducted to investigate the sources of general measurement errors of 3D scanners, whereas studies on outlier formation are relatively limited. Typical sources of scanning errors include the scanned surface property and the scanning geometry.  The scanned surface property directly affects the quality of the light intensity profile.  When scanning a surface with reflectance discontinuity [2], shape discontinuity like edges and corners [3, 19], speckle noise [20], color variations [21] and translucency [14, 22], the light intensity profile will be distorted and deviate from the ideal Gaussian distribution.  The detected centroid will thus shift from the true one, leading to biased measurement errors.  The scanning configuration refers to the relative posture between the scanned surface and the laser probe, and can be described by the incident angle, scan depth, projected angle [23] and scanning orientation [24].  Compensation methods have been developed to reduce the systematic errors caused by these factors [25, 26].  Other factors such as surface reflectivity [27], boundaries of occlusions [5], temperature [28] and exposure time [29] can also affect the measurement errors. Such errors can either be of small magnitude as local noise or become outliers with large deviations from the true surface.   Regarding outliers, surface reflectivity is a critical factor in causing outliers due to undesirable specular reflections. However, research on outlier formation due to surface reflectivity is limited presumably due to the fact that the surface reflectivity can be easily reduced by spray or paint. However, such a surface treatment increases the overall operation time, reduces the measurement accuracy, introduces contaminants to the objects and is inapplicable in scanning final polished 12  parts and clean room parts [6] as well as for on-line inspection systems [12]. Thus scanning reflective surfaces without surface treatments is highly desirable.   When a scanned surface is highly reflective, the specular reflection can cause multi-path reflections so that the sensors may record outliers with large errors. Trucco et al. [11] studied the effect of specular surfaces on range errors when scanning concave geometry like holes. A strict data consistency checking scheme was proposed to discard the erroneous points at the expense of removing some good surface points. Chen et al. [12] also discussed that spurious reflections from shiny surfaces could cause erroneous points in a real-time inspection system. A strategy was proposed to construct the object surface off-line and discard erroneous points not falling on the constructed surface. However, the outlier formation characteristics were not investigated. Moreover, it has been observed that the scanning orientation, which defines the relative posture between the scanner probe and the scanned surface, can systematically affect measurement errors [24]. However, the effect of scanning orientation on outlier formation is seldom studied.   In general, extensive research has been presented to investigate the sources of general measurement errors in the scanning process, whereas specific studies on outlier formation are very limited. The outlier formation mechanism in scanning reflective surfaces using laser scanners is still unclear.   2.2 Outlier Removal Various outlier removal methods have been developed in statistics and have been applied in many fields such as machine learning and data mining. Papadimitriou et al. [30] classified outlier 13  detection methods into distribution-based, depth-based and clustering approaches. However, not all the approaches are applicable to arbitrary large data sets [5]. Since a scanned point cloud may have millions of points, effective and efficient outlier detection methods are more desirable.   From a local point density perspective, outliers in a scanned point cloud can be sparsely distributed or densely clustered as shown in Figure 1.1.  The dense outlier clusters can be further classified into isolated clusters and non-isolated clusters.  The non-isolated outlier clusters seamlessly connect to the scanned object surface and cannot be separated using simple distance criteria [6].   Many methods have been proposed in the literature to detect outliers in a point cloud. Based on the assumption that the local point density of a scanned point cloud follows the Gaussian distribution, Rusu et al. [15] proposed an efficient approach to detect sparse outliers, which are erroneous measurement points with low local point density.  In practice, however, the scanned point cloud density for good surface points can be non-uniform and incomplete.  For example, small subtle geometric features with color and reflectivity variations are often sparsely sampled and would be falsely categorized as outliers.  Sotoodeh [5] proposed a density-based algorithm, which also encounters the similar issue since point density is insufficient to distinguish sparse outliers from sparse good points.  Weyrich et al. [13] applied three criteria to detect outliers in the neighborhood of each data point using user-specified parameters.  For a point in a dense outlier cluster, its neighborhood does not contain sufficient good points, which makes this approach ineffective for outlier clusters.   14  For isolated outlier clusters, which have high point density and are relatively separated from the scanned surface, clustering techniques, such as region growing [17] and spatial graphs [18], have been adopted to classify the whole scanned point cloud into many clusters.  Then, the small clusters are treated as outliers and removed.  However, small good clusters due to insufficient sampling are removed as well.  Moreover, a point cloud may have non-isolated outlier clusters that are not separable using a distance criterion.  Therefore, clustering approaches will end up with some clusters where good points and outliers coexist.  Recently, Wang et al. [16] utilized a distance-based deviation factor to detect sparse outliers and then detected small outlier clusters using region growing.  Unfortunately, non-isolated outlier clusters were not considered.  To detect non-isolated outliers, Shen et al. [6] proposed an iterative surface propagation scheme based on the assumption that all outliers are randomly distributed so that they are rarely on the same plane.  However, such an assumption is not always valid.  The outliers caused by undesirable specular reflections are systematic and can form local planar patches with an offset from the scanned surface.  As a result, these outliers will be mistakenly treated as regular points under the surface propagation scheme.  Köhler et al. [31] developed a special structured light scanning system with an aim to detect and remove outliers during object scanning through additional sensory information.  The involved data processing algorithms are only applicable to the particular scanning system.  Many point cloud smoothing algorithms can be used to reduce outliers.  In such a context, outliers are simply treated as points with large noise.  For example, common moving least-squares methods [7, 32, 33] can robustly project noisy points to the estimated surfaces in the presence of sparse 15  outliers.  However, such locally estimated surfaces can be biased towards outliers if the local neighborhood contains a large number of outliers from dense outlier clusters.  Other smoothing techniques, such as Laplacian [34], mean curvature flow [35, 36], bilateral filter [37, 38], anisotropic diffusion [39], non-local denoising [40] and statistical methods [41, 42] are all fundamentally based on the local neighborhood concept and may not work reliably among dense outlier clusters.  Most of the existing outlier removal methods rely on analyzing the point cloud coordinates only without knowing the scanning process information. They generally require relatively ideal assumptions, which may not be met if outliers are extensive and complex, especially when scanning reflective surfaces.   16  Chapter 3: Outlier Formation Model 3.1 Introduction Based on the principle of triangulation  [2, 3], 3D laser scanners typically emit laser light onto an object and their cameras capture the diffuse reflection from the object surface. However, when the scanned surfaces are highly reflective, the cameras may receive undesirable specular reflections, which can eventually record points with large measurement errors as outliers.   Notably, the factors that cause noise with relatively small magnitude have been well studied [2, 3, 14, 19, 21, 22].  However, limited research has been conducted on the effect of reflective surfaces on outlier formation.  One plausible explanation for the lack of attention is that surface reflectivity can be easily suppressed using sprays.  However, such a treatment constrains the application of laser scanning.  Sprays are a form of contaminants and inapplicable when scanning final polished parts, medical components, clean room parts, etc. [6].  Moreover, many industrial applications require scanning the part in the mist of the manufacturing operation.  For example, automated in-process inspection of weld beads for subsequent machining of the weld to smoothly blend with the welded sections does not really facilitate manual spraying.  In these situations, the laser probe is required to collect point clouds with good accuracy in the presence of reflective surfaces.  In fact, scanning reflective surfaces is a challenging task not only for laser scanners but also for other types of optical scanners such as structured light scanners [31] and stereo vision scanners [43].  Therefore, it is of great importance to investigate the effect of reflective surfaces on the formation of data outliers.   17  Extensive experiments in our work have shown that outlier formation is directly related to the scanned surface geometry.  In general, when scanning a smooth reflective surface, outliers seldom occur as long as the exposure time of the sensors is set properly.  However, if the scanned reflective surfaces have edge features or concave geometries, extensive outliers start to occur.  Considering such geometric features are common in mechanical parts, it is thus essential to examine the relationship between outlier formation and these geometrical features.   This chapter aims to experimentally investigate the formation of data outliers in the scanning of reflective surfaces using a commercial laser stripe scanner.  Two outlier formation models are proposed and verified through experiments.  One is mixed reflections of specularly and diffusely reflected lights. The other is multi-path reflections due to the secondary reflected light.  Both models lead to multiple peaks in the sensor image so that erroneous outliers occur.  Numerous experimental tests have been conducted and the results demonstrate a good agreement with the proposed models in characterizing the distribution of outliers.  Through understanding how outliers are formed in relation to reflective surfaces, this work provides the fundamental model of outlier formation, which will be used to investigate the effects of scanning orientation on outlier formation in Chapter 4.   In the next section, the scanning principle of laser stripe scanner and the related parameters to the outlier formation models will be discussed. Section 3.3 presents the two outlier formation models: mixed reflection and multi-path reflection.  Both models are experimentally verified in Section 3.4, followed by concluding remarks in Section 3.5.  18  3.2 Laser Stripe Scanner 3.2.1 Scanning Principle and Parameters This work investigates a typical type of laser scanner with one laser stripe source and dual sensors as shown in Figure 3.1. The laser probe emits a laser stripe onto the scanned object surface and the image sensors capture the diffusely reflected lights from the object surface.  The laser probe is mounted on an air-bearing based coordinate measuring machine (CMM).  The image arrays in the sensors record the light intensities in rows and columns.  The light intensity in each column is expected to be distributed as a one-dimensional Gaussian profile.  The center of the profile is detected to determine the Z  height of the point for each column using the principle of triangulation while the column position along the row is the Y  position of the point.  Together with the current X  position of the scanning plane traced by the CMM, the laser scanner records the point’s coordinates in 3D.  It should be noted that the light intensity of each column in the sensor image should have only one peak.  If more than one peak is present, erroneous points may be recorded.  19   Figure 3.1 Scanning principle and parameters of the laser stripe scanner.  There are several scanning parameters that should be introduced first.  As shown in Figure 3.1, the scanning plane is the plane swept by the laser stripe source.  The field of view (FOV) is a trapezoid region in the scanning plane within which the sensors can record data points.  The height of FOV is the depth of field.  The length of the far end of FOV is referred to as the laser line length.  The distance from the light source to the FOV far end is the standoff distance.  The light intensity is not perfectly uniform along the laser stripe.  The light tracing the center of the FOV has the highest intensity and is referred to as the central light.  The triangulation angle   defines the angle between the scanning plane and the axis of the sensor lens (Figure 3.2).  Note that the parameters stated above are only related to the hardware configuration of the laser probe and set by the manufacturer.  Other parameters like exposure time are related to the scanning setup and can be Left SensorRight SensorLaser Stripe SourceScanning PlaneField of ViewStandoff DistanceDepth of FieldRaw ImageYZCenterLight IntensityLine LengthYZXProcessed ImageCentral Light20  adjusted by the user.  The light source in general follows a Gaussian intensity profile.  The intensity profile is actually affected by exposure time, which will be detailed in the next subsection.   Figure 3.2 Triangulation angle of the laser stripe scanner.  The laser probe in Figure 3.1 has dual sensors.  Although in principle a scanner only requires one sensor to record 3D data points, most commercial laser scanners are equipped with at least dual sensors.  The primary purpose is to provide redundancy for effective scanning and data collection.  In particular, when scanning around recessed geometry and steep sidewalls, one sensor may be occluded while the other is not.  The resulting image in FOV is simply a combination of the two sensor images.  3.2.2 Exposure Time The exposure time of the sensors is directly related to outlier formation.  If the exposure time is not set properly, the sensors may either miss recording points (underexposure) or record outliers XZYScanning PlaneMoving DirectionLeft Sensor Right SensorTriangulation Angleθ θ 21  (overexposure).  Exposure time specifies the amount of time (in milliseconds) the sensor array is exposed to the laser light and in some sense, produces a similar effect as that of laser intensity.  Reflective surfaces should generally be scanned with longer exposure time than rough surfaces since diffuse reflection on reflective surfaces is weaker.  In an ideally exposed image captured by the sensor array, the light intensities for pixels in each column form a Gaussian distribution as shown in Figure 3.3b.  The center of the Gaussian distribution is then detected to establish the Z  position of the data point.  Although there are several robust centroid detection methods that can compensate for sensor noise and image distortion in the raw image data [3, 44], detecting the centroid often becomes unreliable when the image is underexposed or overexposed as shown in Figure 3.3a and Figure 3.3c.  When the image is underexposed (Figure 3.3a), the low intensity and sparsity of the raw image make it difficult to yield a Gaussian distribution and detect the centroid reliably.  If the light intensity is below the lower limit of the sensor, some points cannot even be recorded and the stripe is broken into pieces with missing points.  In the raw image of Figure 3.3a, the light intensities on the left and right sides of FOV are lower than those in the middle.  Due to the low intensities, the sensors have trouble recording the associated points.  So, the resulting point cloud misses measurement data points in these regions.  In contrast, if the image is overexposed (also known as saturated), the image will have a wide stripe due to the blooming effect as shown in Figure 3.3c.  The high intensities that are over the maximum intensity the sensor can measure are truncated, which also makes the centroid detection unreliable.  Moreover, some columns have multiple local peaks and more than one point may thus be recorded.  The erroneous points may deviate 22  significantly from the true positions and become outliers in the point cloud (Figure 3.3c).  Therefore, setting proper exposure time is of great importance in ensuring measurement accuracy.   Since this work focuses on the effect of reflective surfaces on outlier formation, the exposure time needs to be set properly in order to reduce its influences on the outlier formation.  This is achieved by monitoring the raw sensor images in scanning a planar surface so as to provide a general guideline to set the proper exposure time.  A dashed and thin stripe in the raw image indicates underexposure whereas a bright and wide stripe means overexposure.  The exposure time is adjusted according to this guideline when conducting all the scanning experiments in this work.  In a situation when the scanned surface has large varying surface reflectivity, a single fixed exposure time may not properly expose the sensor image for the whole surface.  Although the commercial laser scanner used in this work is able to set the exposure time off-line, changing the exposure time in real-time to adapt to the varying surface reflectivity during the scanning process is beyond its capability.  Therefore, the scanned surface will be scanned several times using different exposure times in order to capture the whole surface completely.  23    Figure 3.3 Scanning a planar surface: (a) underexposure: 0.2 ms; (b) good exposure: 2 ms; and (c) overexposure: 20 ms.  YZZLight IntensityRaw ImageProcessed ImagePoint Cloud(a) (b) (c) 24  3.3 Two Outlier Formation Models 3.3.1 Reflective Surfaces From an optical perspective, the light reflection on an opaque surface can be modeled by the combination of diffuse lobe, specular lobe, and specular spike [45].  The relative proportion of each component is related to the surface roughness.  All of the three components are usually present when scanning a reflective surface (Figure 3.4).  The reflective surface being studied here refers to a shiny surface for which the specular reflection is dominant.  Yet, the surface is not mirror smooth so diffuse reflection is still present.  If the sensor is positioned in the region of specular lobe or specular spike, overexposure will happen and cause outliers.  In this situation, the surface normal vector is roughly along the bisector of the triangulation angle between the laser source and the sensor.  This particular normal vector is referred to as the forbidden normal and should be carefully avoided during scanning.  Reflective surfaces alone may not deteriorate the quality of the measurement points significantly as long as the sensor image is exposed properly.  However, when scanning surfaces with certain geometries such as edge features and concave geometries, reflective surfaces can cause mixed reflections as well as multi-path reflections.  In both of these situations, the image data will have multiple peaks and the resulting scanned point cloud will have extensive outliers, no matter if there is overexposure or not. 25   Figure 3.4 Light reflection components in scanning a reflective surface.  3.3.2 Mixed Reflection Model In an ideal scanning situation, the sensor of a laser probe would only receive diffusely reflected lights without any specular reflection.  However, when scanning over edge features, the sensor may also receive specularly reflected lights, resulting in outlier formation.  Figure 3.5a demonstrates the scenario of mixed reflections when the scanning plane is parallel to the edge feature.  This figure shows the intersection of the scanning geometry with the plane containing the central light and the center of the right sensor.  The dashed lines represent the source light (red), diffusely reflected light (blue) and specularly reflected light (green).  The solid red line represents the central light with the highest intensity.  The light intensity for each light is shown using a bar length in the corresponding color.  More specifically, the laser source emits a Gaussian laser stripe onto the surface, producing both diffuse and specular reflections.  The diffusely reflected light (blue line), although still following a Gaussian distribution, only possesses a small proportion of the source light intensity (indicated by the blue bar length).  The sensor on the right side captures the diffuse reflection, detects the peak and records a point (blue dot) on the scanned surface. Light SourceDiffuse LobeSpecular LobeSpecular SpikeSensorReflective Surfacen26     Figure 3.5 Scanning an edge feature: (a) mixed reflections; and (b) outlier plane.  Due to the Gaussian distributed light intensity, the laser stripe would also shine on the edge feature, which is characterized with continuously changing surface normals.  The sensor will thus receive a specular light (green line) reflected from the edge region with the forbidden normal.  Although the source light intensity in this region is less than that of the central light, a large proportion of the light intensity contributes to the specular reflection and this makes the specular light received by the sensor high enough to form a local peak.  In consequence, the sensor image will have two peaks mixed together, one by diffuse reflection from the side surface and the other by specular reflection from the edge region with the forbidden normal.  The peak by specular reflection can eventually lead to a recorded data point if the light intensity becomes high enough.  Since any recorded point is regarded as residing on the current laser scanning plane, the data point caused by the specular reflection becomes a data outlier (green dot) as it deviates quite significantly from the True PointOutlierLight SourceSensor LensnnXZYTwo PeaksMoving DirectionSensordodlOutlierPlaneOutlierStarting LineXZYnθ (a) (b) 27  true point (blue dot).  It is evident that such an outlier is a false measurement data point and does not belong to the scanned surface.  Figure 3.5a is an instance when the laser probe scans over the edge feature as shown in Figure 3.5b. As the laser probe moves, many outliers (green dots) will occur and the distribution of these outliers is directly related to the triangulation angle of the laser probe.  When the central light hits the edge region with the forbidden normal, the diffusely reflected light and specularly reflected light received by the sensor coincide with each other.  In this situation, no outliers would occur.  This particular edge region with the forbidden normal is referred to as the outlier starting line.  As the laser stripe moves to the right, the displacement between the diffuse and specular reflections starts to increase and outliers start to occur.  As the displacement grows, the distances between these outliers and the scanned surface increase while the light intensity of the specular reflection decreases because the light source hitting the edge region is approaching the diminished tail of the Gaussian intensity profile.  The outliers formed according to the above situation all reside on a plane from the outlier starting line towards the sensor.  This plane is referred to as the outlier plane.  The angle between the outlier plane and the scanning plane is in fact the triangulation angle   of the laser probe.  When the specular light intensity becomes too low to be registered by the sensor, the outlier cannot be formed anymore.  This means that if the exposure time is set longer, more outliers may be recorded as the resulting image intensities are higher.  In other words, the exposure time affects the number of outliers.  28  To predict the outlier location, let dl  be the distance from the current scanning plane to the outlier starting line and do  the distance from the produced outlier to the outlier starting line.  As evident in Figure 3.5b, do  and dl  follow a simple geometric relationship: sindldo  (3.1) It is clear that the outlier plane is controlled by the triangulation angle   only.  Changing the orientation of the scanned surface will not affect the orientation of the outlier plane.  It should be noted that the left sensor will also receive mixed reflections and record outliers in a similar manner except the outliers will be below the outlier starting line.  If the laser probe moves to the left, outliers will also occur in the same way.  In summary, the scanning operation will produce two outlier planes towards the two sensors and the two outlier planes form a cross shape.  Mixed reflections are common and difficult to avoid in scanning reflective surfaces with edge features.  Since surface normals around an edge feature vary dramatically due to high curvatures, the forbidden normal is easily present in the edge region to produce mixed reflections. Notice that the scanned geometry in Figure 3.5 is a 2D segment of an edge feature in 3D. Thus mixed reflections may occur regardless the size of the edge feature and whether the edge is a straight line or a curve.   Mixed reflections can also happen when scanning a concave surface as long as the forbidden normal is covered by the Gaussian distributed source light.  A typical case is to scan a concave cylindrical surface as shown in Figure 3.6a.  The outliers occur in a similar way as in Figure 3.5a since the light cover the forbidden normal. As the scanning plane moves (Figure 3.6b), the outliers 29  form a plane with the same orientation as predicted by Equation 3.1. Since the probe has two sensors, two outlier planes will actually form a cross shape (Figure 3.6c).    Figure 3.6 Crossing outlier planes in scanning a concave cylindrical surface.  3.3.3 Multi-path Reflection Model Another important issue with reflective surfaces is multi-path reflections when scanning concave geometries.  Figure 3.7a shows the scanning geometry of two planar surfaces joined to form a concave shape.  The source light hits the surface and the sensor receives the diffusely reflected light and records the true point T on the surface.  Due to the concave geometry, the specularly reflected light from T would hit the adjacent surface and generate a secondary reflection on point S.  The diffusely reflected light from S also reaches the sensor and an outlier F would thus be recorded.  In other words, the sensor image may have two peaks produced by the two diffuse reflections: one directly from T and the other from S as a secondary reflection. True PointOutlierLight SourceSensor LensnXZYTwo PeaksMoving DirectionSensordodlOutlierPlaneOutlierStarting LineXZYnθ Right SensorLeft SensorOutli rPlanesOutlierStarting LinesnXZY(b) (c) (a) 30       Figure 3.7 Multi-path reflections in scanning concave geometry: (a) planar intersecting surfaces; (b) cylindrical surface; and (c) outlier starting and ending lines. doOutlierPlaneOutlierStarting LineTSOFψ nβ α α θ dlSensorLight SourceXZYSensorLight Sourceα α α θ ψ nFTOSXZYPnOXZYMovingDirectionOutlier StartingLineOutlier Surface PatchOutlier EndingLineSensorn(b) (a) (c) 31  As the laser probe scans over the concave geometry, many outliers may occur and form an outlier plane.  The sensor on the left will also record outliers and generate another outlier plane in a similar way.  The overall outlier distribution will follow a particular geometric relationship.  As shown in Figure 3.7a, let   be the off-plane incident angle between the laser scanning plane and the surface normal [26],   the dihedral angle between the two planar surfaces, and   the angle between the outlier plane and the laser scanning plane.  Then, the outlier plane orientation angle   can be derived to be: 1 sin sin(2 )cot tansin cos( )cos            (3.2) The outlier starting line is the intersection line of the two extended planar surfaces.  Knowing the outlier plane orientation, the distance from the produced outlier to the outlier starting line do  is related to the distance from the current scanning plane to the outlier starting line dl  as: sindldo  (3.3) For multi-path reflections, the focus is on the two side surfaces instead of the concave edge feature.  When scanning over the concave edge feature, mixed reflections may also occur and may further complicate the outlier formation.  If the concave surface geometry becomes more complex like that of holes, specular reflections may happen multiple times, resulting in complex outlier formation and distribution.  The multi-path reflection may also happen around concave cylindrical surface as in Figure 3.7b. In such a case, the off-plane incident angle   varies continuously instead of being constant. For an outlier, the corresponding angle   follows Equation 3.4.  32  1 (1 sin )sintan 2cos sin(2 ) cos sin             (3.4) As the scanning plane moves to the left in Figure 3.7c,   will decrease and outliers will form a curved patch as   changes with  .  The outlier surface patch does not start when 90    due to the occlusion of the side wall.  It actually starts when 90   . Meanwhile, outliers will disappear when   becomes small enough (less than 30  ). This is because the specular reflection will not hit any surface around so the secondary reflection does not occur.  It is worth noting that the presence of this outlier surface patch by Equation 3.4 is based on the precondition that the secondary reflection can always reach the sensor without considering the limited range of FOV.   Both mixed reflections and multi-path reflections cause multiple peaks in the sensor images due to undesirable specular reflections.  The major difference is that outliers from mixed reflections are caused by specularly reflected lights from the surface region with the forbidden normal, while outliers from multi-path reflections are due to diffusely reflected light from the secondary reflection. It is possible that the specularly reflected light from secondary reflected light mixed with diffusively reflected light in the multi-path reflection model. This will lead to outliers since the false stripe in the sensor image will have very high light intensity, even higher than the first diffuse reflection.   3.4 Experimental Results A series of scanning experiments have been conducted to verify the proposed mixed reflection and multi-path reflection models through analyzing the distribution of outliers in the scanned point clouds.  An LDI WS-3040 laser scanning system equipped with an SLP-250 line-laser probe (with 33  a triangulation angle of 35°) was used.  The specifications of this laser probe are shown in Table 3.1. Regarding the scanned objects, G-1 steel gauge blocks (U.S. Federal Specification GGG-G-15C) were used since they are essentially composed of reflective planar surfaces. Choosing gauge blocks with simple planar surface and line edge features instead of objects with more complex geometries can isolate the effect of edge features and help verify the proposed outlier formation model without introducing more complex factors. It should be noted that all scanning experiments in this work were performed in a practical manner.  This means that the commercial laser stripe scanner was used with its recommended settings in order to achieve the best possible scanning results.  To be more specific, the built-in spike and outlier filters were used during the scanning operations to remove obvious erroneous data in the sensor image.  Such filters detect local spikes and outliers by analyzing adjacent data points, but they become ineffective when outliers are extensive.  The intensity filter was also used to control the upper and lower bounds of light intensity the sensor can record.  The point interval along each stripe and the stripe interval were set to be 0.05 mm in order to capture the surface details [29].  Experimental results have demonstrated that these two parameters can control the number of recorded points but do not noticeably affect the distribution of outliers.  Laser Type Dual Sensors Depth of Field Accuracy Sample Rate Sample Density Size Max. Speed 3D Laser Diode 480   752 CMOS 38 mm 10 ȝm  75,000 points/sec. 30 ȝm  90   180  60 mm 700 mm/s  Table 3.1 Specifications of LDI SLP-250 laser probe  34  As discussed in Section 2, exposure time is a key parameter in controlling the resulting light intensity in the sensor image.  Exposure time is adjusted for each scanning operation and good exposure time would lead to raw images of clear and thin stripes.  It has been recommended to use the same exposure time in one scan [29].  This work follows such a guideline whenever feasible.  3.4.1 Mixed Reflections To illustrate outlier formation caused by mixed reflections, a 9-mm gauge block was set on a rotary stage and rotated to change the off-plane incident angle   between the normal of the scanned surface and the scanning plane (Figure 3.8).  The edge of the gauge block was set to be parallel to the laser scanning plane.  This is in fact the worst scenario for mixed reflections since some normals along the edge would coincide with the forbidden normal.  The rotary stage is rotated for   to be roughly 45°.  Note that the magnitude of   is in fact of little relevance since according to Equation 3.1, the outlier planes are not affected by the scanned surface orientation.  The laser probe scans from the top face to the side face of the gauge block.  The moving direction of the laser probe does not noticeably affect the scanned results in the scanning experiments.  35   Figure 3.8 Experimental setup for mixed reflections.  Figure 3.9 shows an instance when the scanning plane intersects the top gauge face and is close to the edge.  Both sensors can see the laser stripe on the top gauge face without occlusion and both raw images contain multiple stripes.  The false stripe (boxed in red) in the left sensor image is above the true stripe representing the scanned surface (Figure 3.9b) while the right sensor image shows the opposite (Figure 3.9c).  This result is consistent with the mixed reflection model depicted in Figure 3.5.  As the normal of the scanned face points to the left sensor, this sensor receives more reflected light and the resulting image is brighter than that in the right sensor.  The raw images are then processed to detect the peaks in each column and the combined resulting image is shown in Figure 3.9d.  It can be seen that the dimmed false stripe in the right sensor image has been almost completely filtered out by the built-in filters.  However, the filters have failed in processing the left sensor image because the false stripe is bright and similar to the true one.  As a result, the false stripe is still present in the processed image and will cause outliers.  It is also observed that the false stripes predominantly show in the middle area of the images.  This is due ααn36  to two reasons.  One is that the laser source has higher intensity in the middle than on the sides.  The other is that the specular reflections from the edge that are farther from the middle may not easily reach the sensors due to the large in-plane incident angles [26].  The overall scanned point cloud is shown in Figure 3.10a.  Note that the outliers on the left of the edge are more extensive than those on the right.  This is because the top and side faces of the gauge block in fact have different roughness.  The specular reflection on the smoother gauge face is stronger than that on the side face, resulting in more severe mixed reflections.    Figure 3.9 Typical scanned results: (a) scanned point cloud with outliers; (b) raw image in the left sensor; (c) raw image in the right sensor; and (d) processed image in FOV.  Regarding the distribution of outliers, it can be seen that the outliers occur around the edge and form local planar surface patches.  To verify that these outliers in fact reside on the outlier planes FOV(a) (b) (c) (d) 37  as predicted by Equation 3.1, the reference outlier planes are to be shown along with the scanned point cloud.  The angle between the outlier plane and the scanning plane is shown to be the triangulation angle of 35°.  However, the outlier starting lines are not readily available and need to be estimated.  Taking the outlier plane on the left as an example, the strategy is to first align the point cloud to the reference model surface of the gauge block, and then fit a plane to the outliers.  The intersection line between the fitted plane and the reference model surface represents a good estimate of the outlier starting line.  The classic Iterative Closest Point (ICP) algorithm [46] is used to align the point cloud to the reference model of the gauge block.  Figure 3.10b shows a typical alignment result.  The color code indicates the deviation from a point to the reference model (excluding the outliers).  The resulting average deviation of 0.017 mm indicates valid alignment as it is close to the nominal accuracy of the laser scanning system.  After alignment, the whole point cloud including the outliers is projected onto the plane perpendicular to the edge.  A least-squares plane is fitted to the outliers with the constraint that the plane is parallel to the reference edge line.  The intersection line between the fitted plane and the reference model surface is then a good estimate of the outlier starting line (indicated as the red line in Figure 3.10b).  The other outlier starting line on the right is to be obtained in a similar way.  Figure 3.10c shows the end view of the two outlier planes for the two sensors (red lines) with the scanned point cloud.  The outliers are seen to be very close to the outlier planes.  38     Figure 3.10 Mixed reflection model validation: (a) scanned point cloud; (b) estimated outlier starting line; and (c) predicted outlier planes.  To quantify how well the mixed reflection model predicts the outlier distribution, each outlier is referenced to the outlier starting line using dl  and do .  For outliers on the left, dl  and do  of each outlier are plotted together with the predicted outlier plane, as shown in Figure 3.11.  It is evident in this figure that the mixed reflection model predicts the outlier distribution very well.  Further, a linear least-squares model with zero intersect is fitted to the outlier data.  The resulting orientation angle of the fitted line is found to be 35.9°, which is close to the modeled orientation angle of 35°.  Outlier Starting LineLeft Outlier PlaneReference SurfaceRight Outlier Plane0mm0.225mm(a) (b) (c) 39   Figure 3.11 Quantitative comparison of actual and predicted outlier distributions due to mixed reflections.  Similar experiments to the above have also been conducted to scan a 20-mm gauge block with   being roughly 30°.  The scanned results are consistent with those presented above, which further validates the mixed reflection model.  To clearly demonstrate that   does not affect the orientation of the outlier planes, Figure 3.12 shows the scanned point clouds from the two gauge blocks with varying  .  The red lines represent the predicted outlier planes.  It can be seen that no matter what   is, the corresponding outlier distribution always follows the same orientation as predicted.  dodl40    Figure 3.12 Scanned point clouds from gauge blocks with varying  : (a) 9 mm; and (b) 20 mm.  As stated before, exposure time directly affects the number of outliers since long exposure time would make the light intensities of specularly reflections on the sensor image high enough to be recorded as valid points.  Therefore, the longer the exposure time is, the more extensive the outliers will be.  Figure 3.13 shows the scanned point clouds from a 10-mm gauge block with varied exposure times.  In the left figure, the scanned surface is underexposed and the point cloud has only a few outliers.  As the exposure time increases, the surface is better exposed, but the outliers become more extensive.  The light intensity of the false stripe becomes comparable to that of the good scanned points.  The processed image may thus only record the outliers without the corresponding good points and the resulting point cloud would miss many surface points as shown in the middle and right figures.  In the 2 ms case, the distance from the farthest outlier to the scanned surface is approximately 9.7 mm, which is close to the size of the gauge block (10 mm).  This apparently much deteriorates the quality of the scanned data. (a) (b) 41     Figure 3.13  Scanned point clouds from a 10-mm gauge block with different exposure time.  3.4.2 Multi-path Reflections To verify the multi-path reflection model, two gauge blocks were attached together and set on the rotary stage as shown in Figure 3.14.  Note that the focus of this scanning experiment was the specular reflection on the two intersecting planar surfaces.  To avoid mixed reflections around the intersection concave edge region, it was covered with white polymer clay.  The gauge blocks were scanned from left to right with   being roughly 45°.  The resulting scanned point cloud is shown in Figure 3.15a.  The two convex edges are seen to produce outliers along the outlier planes as predicted by the mixed reflection model.  The concave region is also seen to produce extensive outliers according to the principle illustrated in Figure 3.7.  To confirm that these outliers in fact follow the predicted outlier planes, the outlier plane orientation angle   should first be obtained 0.5 ms 1 ms 2 ms 42  using Equation 3.2.  Same as the previous mixed reflection case, the point cloud (excluding the outliers) is to be aligned to the reference surfaces of the gauge blocks.  Again, the resulting average deviation of 0.018 mm indicates valid alignment as it is close to the nominal accuracy of the laser scanning system.  With the readily available off-plane incident angle 45.1    and dihedral angle 92.1   , the predicted   is found to be 14.2° for the left outlier plane.  The intersection line of the two reference model surfaces is the outlier starting line as shown in Figure 3.15a.  Figure 3.15b depicts the point cloud together with the two predicted outlier planes.  For outliers on the left of the outlier starting line, dl  and do  are extracted and plotted in Figure 3.16.  From this plot, the approximated   is 13.7°, which agrees with the predicted   of 14.2° well.  The right outlier plane yields a similar result.   Figure 3.14 Experimental setup for multi-path reflections.  αα n43    Figure 3.15  Multi-path reflection model validation: (a) estimated outlier starting line; and (b) predicted outlier planes.   Figure 3.16 Quantitative comparison of actual and predicted outlier distributions due to multi-path reflections.  Outlier Starting LineReference SurfacesOutlier Planes0mm0.291mmdodl(a) (b) 44  It has been observed that these outliers deviate more from the predicted outlier planes than those due to mixed reflections.  This is because the multi-path reflection model illustrated in Figure 3.7 assumes that the secondary reflection is caused by the ideal specular reflection.  In reality, however, the secondary reflection contains both specular lobe and spike, which makes the footprint of the secondary-reflection light stripe wider and dimmer.  As a result, the resulting outliers diverge more.  Similar experiments have been conducted with different   and the results are all consistent with the multi-path reflection model predictions.  Also, it has been observed that the outliers can be significantly reduced by spraying the gauge blocks in the experiments described above.  This further confirms that the outliers are caused by specular reflections.  3.4.3 Case Study The proposed outlier formation models have been verified by scanning gauge blocks with planar surfaces.  The models are in fact general since the scanned geometries in the two modes are 2D segments of 3D surfaces. The models can be applied to the scanning of common and more complex object surfaces.  Figure 3.17 shows the scanned point clouds from an aluminum part.  This regular-shaped mechanical part contains planar and cylindrical faces as well as edge features and holes.  The surfaces are rougher than those of the gauge blocks, yet still reflective.  It has been shown in previous sections that mixed reflections would occur when the scan path involves forbidden normals.  Therefore, one effective way to reduce outlier occurrence would be to avoid forbidden normals in planning the scan path.  Figure 3.17 illustrates the effects of two different scan paths.  When the part was scanned using the red path, where the scanning plane was set to be roughly parallel to the edge feature lines of the cylindrical faces (similar to Figure 3.5), 45  outliers occurred around the edge regions, cylindrical faces and holes.  The holes are of concave geometry and with curved edge feature, which are subject to both mixed reflections around the edge and multi-path reflections due to the concave geometry.  The outlier distribution becomes much more complex around holes.  Still, many outlier planes (red lines) were correctly identified.     Figure 3.17 Scanning an aluminum part: two scan paths (top); results from the red path (middle two); and results from the green path (bottom).  46  It should be pointed out here that smooth convex surfaces generally do not cause outliers.  Therefore, special attention should be paid to the edge features and concave surfaces when planning a scan path.  The green path is deemed a better scan path since it avoids the forbidden normals for the edges.  Using this scan path, the scanning plane is perpendicular to the edge feature lines of the cylindrical faces.  The specular reflections associated with the forbidden normals cannot reach the sensors.  Because of this, outliers were significantly reduced.  The scanned point clouds shown in Figure 3.17 have also been analyzed to confirm outlier formation around cylindrical surfaces.  As highlighted in the black box in Figure 3.17, the outliers around the concave cylindrical surface form two intersecting planes as modeled in Figure 3.7.  Similar to the experiments in Section 3.4.1, the two planes are fitted and their orientation angles are estimated as 33.9° and 34.0°, respectively.  These estimated angles are again close to the modeled orientation angle of 35°.  This validates that these outliers are caused by mixed reflections.  Also, these outliers do not form curved surface patches as predicted by the multi-path reflection model.  It is likely that multi-path reflections were not captured by the sensors due to occlusions and the relatively small FOV of the laser probe in comparison with the cylindrical surface size.  If small concave surfaces are scanned, such as the small holes in Figure 3.17, outliers caused by multi-path reflections would occur.  The scanned point clouds in Figure 3.17 represent typical scanned data from scanning mechanical parts with reflective surfaces and complex geometry.  It can be observed that general smooth surfaces usually result in very few outliers, whereas edge features, high-curvature regions and 47  concave geometries often lead to extensive outliers.  These surface regions, thus, deserve more attention during the scanning.    3.5 Summary Scanning reflective surfaces is a challenging task for laser scanners. Undesirable specular reflections can easily cause outliers and deteriorate the quality of the scanned point cloud.  However, the effect of specular reflections on outlier formation was only limitedly studied in the past.  This chapter investigates the formation of outliers in scanning reflective surfaces.  The main contributions are the development of two outlier formation models due to mixed reflections and multi-path reflections, respectively.  These outlier formation models have been verified through a series of scanning experiments using a commercial laser stripe scanner. Regarding the scanned geometries, smooth convex surfaces usually do not cause outliers even when the surface is reflective, whereas edge features and concave geometries are the typical regions where outlier occurs due to mixed reflections and multi-path reflections.   Given a planned scan path, the developed models provide a viable means to evaluate its performance with regard to outlier occurrence.  More specifically, if the scan path covers forbidden normals on the scanned object surface, especially around edge features, this path will most likely lead to extensive outliers.  A scan path can thus be evaluated beforehand and re-planned, if necessary, before the actual scanning operation to increase scanning quality and efficiency.  This chapter presents the fundamental outlier formation models and will be used to investigate the effects of the scanning orientation on outlier formation in the next chapter, in which a more detailed guidance of scan path planning will be presented. 48  Chapter 4: Effects of Scanning Orientation on Outlier Formation 4.1 Introduction 3D laser scanners are sensitive to the light reflection on the scanned surfaces. As been studied in Chapter 3, undesirable specular reflections can cause extensive outliers modeled by mixed reflections and multi-path reflections. Different from noise, which are usually considered as randomly distributed, outliers can be systematic, extensive and complex.   The proposed outlier formation models in Chapter 3 are closely related to the relative scanning orientation between the scanned surface and the laser probe. To be more specific, the outlier extensity and regions where outliers occur can be affected by the scanning orientation. Scanning using a proper scanning orientation will result in a point cloud with much fewer outliers than using a poor scanning orientation.   Research has shown that scanning orientation related factors, such as incident angle [26], projection angle [23], orientation angle [24], can cause systematic measurement errors in the scanned point cloud.  Such errors are of relatively small magnitude. The resulting measurement points, although bias from the scanned surface, are still sufficiently close to the surface. Thus many methods [24-26] have been proposed to compensate such systematic errors. However, outliers are different from systematic noise by its nature. Outliers are false measurements not belonging to the scanned surface and should be removed instead of being moved back to the surface.   This chapter aims to investigate the effects of scanning orientation on outlier formation, which is very seldom studied. Specifically, this paper reports how the outlier extensity and occurrence 49  region changes with respect to various scanning orientations through experiments. It will be shown that the outlier extensity and occurrence region are much dependent on the scanning orientations. A proper scanning orientation can significantly reduce outliers in the scanning process. Thus less efforts will be required for outlier removal in the subsequent data processing step.   Through studying the scanning orientation effects, a general guidance of scan path planning will be presented in the effort to reduce outlier occurrence. Based on the experiments, the view-dependent property of outliers will be utilized to develop an efficient outlier removal approach, which will be presented in Chapter 5.   In the next section, the scanning orientation is defined by three angles. Their effects on mixed reflection model and multi-path reflection model are discussed in Section 4.3 and Section 4.4 respectively. The applications of this work are discussed in Section 4.5, followed by the summary in Section 4.6.  4.2 Scanning Orientation This section defines the scanning orientation to be investigated as well as the experiment setup. A commercial laser stripe scanner is shown in Figure 4.1. The laser probe is installed on a PH10 Motorized indexing head (PH10M) and moved by the coordinate measuring machine (CMM). The CMM controls the translations along X, Y and Z axes, while the PH10M provides rotations.  50   Figure 4.1 Laser scanning system.  The scanning orientation is the relative posture between the laser probe and the scanned surface. Consider scanning a simple rectangular prism as shown in Figure 4.2, if the scanned object is fixed, the laser probe can move with 6 degrees of freedom. The translations along X, Y and Z axes in the CMM coordinate system merely move the field of view (FOV) of the laser probe. Moreover, the Z-axis translation changes the scan depth and can affect the systematic errors [23]. However, it does not noticeably affect the outlier formation according to our experiments. In contrast, the rotations along the 3 axes define the scanning orientation and can significantly affect the outlier formation. As shown in Figure 4.2, the rotation along X-axis controls the in-plane incident angle PH10MLaser ProbeGauge BlocksCMM51  (IIA) between a laser light and the surface normal vector projected to the scanning plane. Y-axis rotation controls the out-plane incident angle (OIA) between the surface normal and the scanning plane. Z-axis rotation can be viewed as the relative orientation angle between the scanning plane and Y-axis. This angle controls the angle between the laser plane and the tangential line of edge features. The special attention is given to edge features because they are the typical regions where mixed reflections occur. So Z-axis rotation is referred to as edge orientation angle (EOA). These three angles can well define the relative orientation between the laser probe and the scanned surface features.    Figure 4.2 In-plane Incident Angle, Out-plane Incident angle and Edge Orientation Angle.  The next two sections experimentally investigate how the three orientation angles affect the outlier formation in terms of outlier extensity and the regions where outliers occur. Similar to the experiments in Chapter 3, gauge blocks are chosen as the objects to be scanned since they have planar reflective surfaces and edge features. To investigate the effects of these three angles (IIA, OIA, EOA) on outlier formation, the gauge blocks will be scanned by fixing two angles and In-plane I cident le (IIA)Out-plane Incident Angle (OIA)YZX YZXYZ XSurface NormalSurface NormalEdge Orientation Angle (EOA)Edge Line(a) (b) (c) 52  varying the third one for both the mixed reflection and multi-path reflection models. The effects of each angle on the two outlier formation models will be analyzed and validated through experiments.    4.3 Effects of Scanning Orientation on Mixed Reflections According to the mixed reflection model in Chapter 3, outliers occur when the image sensors receive the light caused by specular reflections. Since the direction of specularly reflected light is controlled by the incident angles between the surface normal vectors and light source plane, the scanning orientation affects whether the specular reflection can reach the sensors by changing the incident angles and thus influence the outlier formation.   The focus is how outlier extensity and occurrence regions change with respect to different scanning orientations. Figure 4.3a illustrates the mixed reflection model as Figure 3.5. When the laser probe scans over an edge feature, the high local curvature causes large variations to the surface normals around the edge. As a result, the light direction of the specular reflection varies dramatically and may reach the sensors when the light covers the forbidden normals. Thus a sensor receives two valid light stripes. One is the diffuse reflection from the side surface and the other is the false stripe due to the specular reflection from the edge. The false stripe leads to local intensity peaks in the sensor images and eventually causes outliers by the principle of triangulation.   53             Figure 4.3 (a) Mixed reflection model, and (b) Specular reflections with different IIAs.  As mentioned in Section 3.4.1, the false stripe caused by specular reflections only appear in the middle columns in the camera image array in Figure 4.3a instead of going across all columns. This is because the lights on the side columns of the camera image correspond to large in-plane incident angles and the specular reflections cannot reach the cameras as shown in Figure 4.3b.   The effects of IIA, OIA and EOA can be reasonably analyzed from the mixed reflection model. The hypotheses are: If the probe is rotated along X axis to change IIA, the false stripe will shift horizontally in the FOV from the middle to the side and the outliers will occur only in the regions corresponding to small IIAs. When IIA increases to a certain degree, the specular reflection may go out of the FOV and outliers will disappear. If out-plane incident angle (OIA) changes by rotating the probe along Y axis like in Figure 4.2b, the laser stripe can always cover the edge feature and cause mixed reflections. Thus outliers may not be eliminated by changing OIA. In True PointOutlierScanningPlanennXZYTwo PeaksDiffuse ReflectionSpecular ReflectionCamera ImageCamerann(a) (b) 54  Figure 4.3, the scanning plane is parallel to the edge feature. If the edge orientation angle (EOA) in Figure 4.2c increases, only the specular reflection in the intersection region between the scanning plane and the edge may reach the sensors. By increasing EOA, the false stripes in the sensor images will shift and eventually disappear. In an extreme situation when EOA is 90 , the specularly reflected lights reside on the scanning plane and cannot reach the two cameras.   The above hypotheses are made based on the mixed reflection mode. Similar to the experiments in Chapter 3, a 9-mm gauge block is scanned by different OIA, IIA and EOA to verify these hypotheses. Since the scanning orientation is directly related to surface normals, a planar surface of a gauge block with constant normals makes it easier to capture the distribution of outliers and verify the hypotheses than using curved surfaces with varying normals. Three sets of scans are conducted by changing one angle and setting the other two angles to be 0 . The minimum point spacing is set to be 0.05 mm to control the point density. Since the scanning orientation affects the amount of light received by the sensors, it is not feasible to use a single exposure time for all sets of scans. Thus the exposure time is properly adjusted and fixed for each set of scans.   For OIA, Figure 4.4 shows the scanned point clouds with OIA from 0  to 45 . As predicted by the mixed reflection model, outliers occur around the edge feature and form a planar patch towards the camera. Such a patch is a ghost surface that does not exist in the scanned object. In Figure 4.4, the outliers always form planar patches towards to the sensor. OIA can change the angle between an outlier patch and the gauge face of the gauge block. In other words, the outlier occurrence region rotates along the edge line of the gauge face when OIA changes. Meanwhile, the outlier extensity decreases as OIA increases. However, outliers always occur no matter what OIA is used. This is 55  because the laser stripe always covers the edge regions where the surface normals make the specular reflections reachable to the sensors.      Figure 4.4 Scanned point clouds with various OIAs in mixed reflection model.  For IIA, Figure 4.5 shows the scanned point clouds using various IIAs. The outliers around the two edges of the gauge face all shift from the middle regions of FOV to the sides as IIA increases, which agrees with the hypothesis. Outliers disappear when IIA is over 10 . In this situation, the specular reflection cannot reach the cameras due to large IIAs. Here the angle threshold when outliers disappear is a rough estimate and may vary among different scanners. The purpose is only to demonstrate that a sufficient large IIA will make the specular reflection out of the limited field of view and thus eliminate outliers.   Moving Direction0  15  30  45  56      Figure 4.5 Scanned point clouds with various IIAs in mixed reflection model.  Regarding EOA, Figure 4.6 demonstrates the effects of EOA by rotating the laser probe along Z-axis. In this case, the outliers around the two edges of the gauge face shift along the opposite direction as EOA increases, which is different from the effects of IIA. Meanwhile, the outliers disappear when EOA is roughly over 25  for the similar reason as that of IIA.      Figure 4.6 Scanned point clouds with various EOAs in mixed reflection model.  It can be seen that the outlier formation are directly affected by the scanning orientation represented by IIA, OIA and EOA. The effects of these angles generally agree with the hypotheses stated before. The regions where outliers occur and the outlier extensity vary dramatically with the changes of the orientation angles. To quantify how the outlier extensity changes with respect to Moving DirectionMoving Direction0  2.5  5  7.5  10  0  10  15  20  25  5  57  the scanning orientation, the outliers in each scanned point cloud are identified by fitting the reference surface of the gauge block. Similar to the fitting approach in Chapter 3, a rectangular geometry is aligned with a scanned point cloud using the classic Iterative Closest Point (ICP) algorithm [46]. Points with large deviations from the reference surface over a certain threshold are considered to be outliers, while the rest are good surface points. The threshold is set to be the point spacing parameter in the scanning setup and is not a critical factor since the comparison is relative using the same threshold. Since the point density is fixed by the point spacing parameter, the number of good surface points is proportional to the area of the covered scanned surface. The outlier percentage by the ratio of the outlier number to the total number of points can be calculated to describe the outlier extensity in a point cloud. Such estimates are not meant to be accurate since the focus is the trend of how outlier extensity changes with respect to each scanning angle. Besides scanning orientation angles, the amount of outliers also depends on the scanned surface area. Here the focus is the effects of scanning orientation angles in scanning the same surface area.   Figure 4.7 shows the relation between outlier percentage and the three scanning angles for the three scanning tests. The outlier percentage generally decreases with the increases of each angle. The percentage drops rapidly when IIA and EOA increase and then becomes stable until reaching 0%  when IIA and EOA are sufficiently large. OIA can reduce but fail to eliminate outliers. If larger OIA ( 45 ) is used, the other edge of the gauge face will cause outliers due to symmetry.   In overall, the outlier formation in the mixed reflection model is directly affected by the three scanning angles. Among the three angles, IIA and EOA are the major factors to affect the outlier 58  extensity and occurrence regions. When IIA and EOA are sufficient large, the outliers are almost eliminated. However, OIA is less effective in controlling the outlier extensity.    Figure 4.7 Outlier percentage with respect to OIA, IIA and EOA in mixed reflection model.  4.4 Effects of Scanning Orientation on Multi-path Reflections Multi-path reflections typically happen when scanning concave geometries with reflective surfaces. As shown in Figure 4.8, the light source bounces once or more and hit another surface region, on which the reflected light may reach the cameras. Thus the cameras receive the direct diffuse reflection and the secondary diffuse reflection, and record outliers as in Figure 3.7. It should be noted that the false stripe caused by the secondary reflection covers almost all the columns of the camera images, which is different from the case in the mixed reflections, where the false stripe is only in the middle columns. This is because the secondary reflection is diffuse reflection, which can always reach the cameras as long as the light is not occluded by the object geometry.    59   Figure 4.8 Multi-path reflection model.  Regarding the effects of OIA, IIA and EOA in the multi-path reflection model, OIA affects the direction of specularly reflected lights and indirectly affects the region where the secondary reflection happens. As a result, the outlier occurrence regions will change according to OIA. IIA has a similar effect as that in the mixed reflections. The false stripe will shift when IIA changes.   The effect of EOA is a different scenario in multi-path reflections from mixed reflections. As shown in Figure 4.9, when the scanning plane intersects with the concave edge, the footprint of the light stripe on each side surface of the edge can cause secondary reflections by treating the other side surface like a mirror. Thus there are two stripes directly caused by the source light and two mirrored stripes due to secondary reflections. The four stripes are all visible to the two cameras. Since the two cameras have different view orientations, the stripes in the two camera images are not identical. The two camera images are combined to calculate surface points through center detection. Due to the mirrored light footprints, the false stripes are present in the combined image and eventually cause outliers in the scanned point cloud.   ScanningPlaneCameraTrue PointOutliernCamera ImageXZY60  In this case, the orientation of the false stripes in the cameras images has a direct relation with EOA. More specifically, rotating EOA can rotate the false stripes in the camera images and affect where the outliers occur. Since each column of the combined image is used individually to detect the light intensity peaks and calculate point coordinates, the best scenario is when the false stripes are vertical in the image so that they only affect a few columns and thus cause a few outliers. The worst case, however, is when the false stripes are horizontal so that all columns have false peaks and outliers will be most extensive.     Figure 4.9 Outliers caused by mirrored light footprints around concave edge.  To experimentally investigate the effects of these three orientation angles on multi-path reflections, two gauge blocks are attached together to form a concave geometry similarly to the experiment in True Light FootprintMirrored Light FootprintLeft Camera Image Right Camera ImageYZXCombined ImageAfter Center Detection Scanned Point CloudFalse StripesOutliers61  Section 3.4.2. The concave edge is filled by white polymer clay to avoid the influence of the potential mixed reflections around the edge. Figure 3.10 shows the point clouds with different OIAs. As OIA increases, the outliers move from a side surface of the concave edge to the middle of the two side surfaces with decreased extensity.     Figure 4.10 Scanned point clouds with various OIAs in multi-path reflection model.  For IIA, the outliers in Figure 4.11 shift from the center to the side of the edge with the increase of IIA, which is similar to Figure 4.5 in mixed reflection model. The outlier extensity decreases but does not vanish since diffuse reflection by the secondary reflection can always reach the sensors.     Figure 4.11 Scanned point clouds with various IIAs in multi-path reflection model. Moving Direction0  5  10  15  0  15  30  45  62   Regarding EOA, Figure 4.12 illustrated the scanned point clouds with varying EOAs. The three images for each point cloud are the raw images from two cameras and the combined image after center detection. As we can see, the false stripes rotate in the camera images with EOAs. When EOA is 45 , the outlier extensity reaches the minimum, because the false stripes become vertical in both camera images and only affect a few columns. On the contrary, when the false stripes are horizontal as EOA is 0 , the outliers are most extensive due the horizontal false stripes.     Figure 4.12 Scanned point clouds with various EOAs in multi-path reflection model.  Similar to the experiments in mixed reflection models, the relation between the outlier percentage and the three angles are plotted in Figure 4.13. The outliers are identified through fitting the two gauge block models as in Section 3.4.2. Only the two side surfaces forming the concave edge are considered in calculating the outlier percentage. As we can see, the outlier percentage drops with the increase of OIA, which is similar to the case in the mixed reflection model. The outliers are always present no matter what OIA is used. When IIA increases, the outlier percentage decreases rapidly and then becomes stable when IIA is above 15 . However, outliers are not eliminated, which is different from the mixed reflection model. Regarding EOA, the outlier percentage reaches 0  15  45  75  90  63  the maximum when EOA is 0  and starts to decrease rapidly as EOA increases. It reaches the minimum and becomes stable when EOA is around 45 . Then the percentage increases quickly when EOA is above 60 .   All the three angles in the multi-path reflection model can significantly affect the outlier extensity and occurrence regions. However, no matter what angles are used, outliers always occur because the secondary reflection is diffuse reflection, which is not sensitive to surface normals and can easily reach the cameras. On the contrary, outliers can be eliminated with certain angles in the mixed reflection model since specular reflection is directly affected by surface normals. The overall effects of the three angles are summarized in Table 4.1 for both the mixed reflection and multi-path reflection models. Based on Table 4.1, it is preferable to use moderate OIA, large IIA and large EOA when scanning convex edge features as well as moderate EOA for concave geometries in order to reduce the occurrence of outliers.   Figure 4.13 Outlier percentage with respect to OIA, IIA and EOA in multi-path reflection model.    64   Mixed Reflections Multi-path Reflections Outlier Extensity Outlier Occurrence Region Outlier Extensity Outlier Occurrence Region OIA   , always present Rotate along one edge line  , always present Rotate along the concave edge line IIA   , 0 when IIA > 10  Shift in the same direction along the two edge lines  , always present Shift along the concave edge line EOA   , 0 when EOA >            25  Shift in the opposite directions along the two edge lines   until EOA = 45  then  , always present Rotate along the concave edge line  Table 4.1 Effects of scanning orientation angles on outlier formation  4.5 Discussion of Applications The above experiments investigate the effects of scanning orientation on outlier formation by scanning gauge blocks with simple geometry. When scanning common parts with complex geometry such as curved edges and holes, the outliers will become more severe and complex. For example, a curved edge can make the edge orientation angle change continuously. A free-form geometry with varying surface normals changes in-plane and out-plane incident angles as well. However, the general effects of the scanning orientation still apply. By knowing the effects of scanning orientation on outlier formation, this work can provide a general guidance on scan path planning and facilitate the design of an effective outlier removal method.    A potential application of this work is to properly plan the scan path in order to reduce the occurrence of outliers. Many methods [47, 48] have been developed to plan a scan path in automatic or semi-automatic manners. The main focus is to satisfy certain criteria such as sampling density, data completeness and measurement accuracy under several constraints. The typical constraints are limited view angle, depth of view, surface visibility and collision-free path. 65  However, many methods use spray when scanning a reflective part and manually remove abnormal outliers [47]. Such methods are inapplicable when surface treatment is inappropriate. As a result, the scanned point cloud may contain extensive outliers if the scan path is improperly planned. Additional constraints should be considered when scanning highly reflective surfaces in order to reduce outliers.   In quality inspection, the reference CAD model is available and OIA, IIA and EOA can be calculated by the surface normals, edge features and the probe rotations. According to Table 4.1. additional constraints can be included when generating the probe orientation candidates [47]. These constraints are: 1. Large IIA 2. Moderate OIA 3. Large EOA for convex edges and moderate EOA for concave shapes  Each constraint requires manually adjusted angle thresholds depending on the scanner configurations. Once the orientation candidates satisfying these constraints are obtained, the scan path can be generated by interpolating these key orientations [47].   In the applications of reverse engineering, where the reference CAD is unknown, the above-mentioned constraints can still serve as a general guidance for manually planning the scan path. An aluminum part is scanned to demonstrate the benefit of proper path planning. The part has prismatic geometries with reflective surfaces as shown in Figure 4.14a. By manually specifying the four corners of the bounding box of the part, a zigzag path can be generated to cover the top surface without considering the specific surface features. Then the path can be rotated for multi-66  times to scan the part for a complete rotation in order to cover all the side surfaces. In Figure 4.14b, the scan path with  0  IIA, 0 OIA and varying EOA is improperly planned since 0  IIA and 0OIA can cause extensive outliers around edge features. In contrast, the scan path in Figure 4.14c with 45  IIA is better to reduce outliers around convex edges according to the guidance in Table 4.1. In Figure 4.14c, the outliers are significantly reduced in comparison with Figure 4.14b, which demonstrates the importance of the path planning. However, outliers are still present around concave geometries such as holes. Since there is no guarantee to have an outlier-free point cloud regardless the scan path, an effective outlier removal process is still highly required.     Figure 4.14 Scanned point clouds from an aluminum part (a) with a poorly planned path (b) and a proper scan path (c).  Regarding outlier removal, Table 4.1 provides a critical insight that the outlier occurrence regions are much dependent on the scanning orientations. Changing the scanning views can directly change the regions where outliers occur. Such outliers are generally view-dependent. On the contrary, the scanned surface is almost always visible to the cameras without considering light occlusion. Thus the good surface points are usually independent to the scanning orientation. Based (a) (b) (c) 67  on this insight, an effective outlier removal method will be developed in Chapter 5 to distinguish view-dependent outliers from view-independent surface points.   4.6 Summary This chapter experimentally investigates the effects of scanning orientation on outlier formation in scanning reflective surfaces. The scanning orientation is defined by In-plane Incident Angle, Out-plane Incident Angle and Edge Orientation Angle. Their effects have been analyzed with respect to the outlier occurrence regions and outlier extensity in scanning gauge blocks.    The key observations are: (1) proper scanning orientations can significantly reduce outlier extensity; (2) the outlier occurrence regions are much dependent on the scanning orientations. A general guidance of scan path planning is provided in favor to reduce the occurrence of outliers. Once outliers are significantly reduced in the scanning step, less effort will be required to remove outliers in the following processing steps. Moreover, the view-dependent property of outliers can be utilized to design an efficient outlier removal method, which will be discussed in Chapter 5.  68  Chapter 5: View-Dependent Outlier Removal by Rotating Scans 5.1 Introduction Outliers can significantly deteriorate the quality of scanned point clouds and consequently affect many point cloud applications. As stated in Chapter 1, extensive outliers can cause ghost surface patches in the constructed surfaces in reverse engineering. In quality inspection, outliers indicate suspicious large deviations and may cause false rejection. The effectiveness of an outlier removal process thus plays a critical role in ensuring the performance of these applications. Detecting outliers is a challenging task since the underlying surfaces are usually unknown and any estimation of such surface geometries is subject to be inaccurate in the presence of extensive outliers, noise and data incompleteness.   As reviewed in Chapter 2, most of the existing methods detect outliers through analyzing the point cloud data only without knowing the outlier formation mechanism or utilizing the scanning setup information. Some algorithms [5, 13, 15, 16] utilize local descriptors of each point’s neighborhood to detect sparse outliers. Such methods are ineffective in removing dense outliers since the outliers may dominate the local neighborhood. Other methods [17, 18] detect dense outliers in a global sense using graph or clustering techniques. Their effectiveness much relies on ideal assumptions of the regularity of the point clouds and randomness of outliers. Thus these methods tend to be unreliable when the outliers become extensive and complex, especially in scanning reflective surfaces.   This chapter is a continuing work of Chapter 4. It has been observed that the outlier formation is directly affected by the scanning orientations. More specifically, the regions where outliers occur 69  and the outlier extensity are much dependent on the scanning orientation. Outliers are generally view-dependent since their occurrence regions changes according to the change of the scanning orientation. In contrast, ordinary surface points are usually visible from various scanning views and always distribute around the scanned surface. Thus surface points are view-independent. Based on this insight, this chapter proposes a rotating scan scheme to efficiently detect outliers through exploring the view-dependent property of outliers. Three criteria, overlap ratio, point spacing and surface variation, are proposed to distinguish outliers from ordinary surface points. The key ingredient of the proposed method is to integrate the scanning orientation information with the point clouds to reliably detect extensive outliers in scanning reflective surfaces. The superior performance of the proposed approach is demonstrated in comparison with many existing methods using various scanned point clouds.   The following sections are organized as follows: A rotating scan scheme is proposed to detect view-dependent outliers in Section 5.2. Its implementation is discussed in Section 5.3. The proposed approach is compared with several existing methods to demonstrate its effectiveness in Section 5.4, followed by the conclusion remarks in Section 5.5.   5.2 Outlier Removal by Rotating Scans 5.2.1 Outlier View Dependency From the experiments in Chapter 4, the surface regions where outliers occur are much dependent on the orientation they are scanned from. For example, the outliers caused by multi-path reflections locate around the edge feature regions where the edge orientation angles are small. Similarly, different incident angles also result in different outlier locations. To illustrate this point, the top 70  face of a cylinder is scanned as shown in Figure 5.1. This circular shape has a curved edge so that the edge orientation angle changes continuously when the laser probe scans over. It can be seen that the outliers only occur when the edge orientation angle (EOA) is about less than 20°. If the top face is scanned from other orientations in Figure 5.2, the outliers will occur in different spatial locations corresponding to the new orientations. This indicates that the outlier occurrence regions are much dependent on the scanning orientation. In contrast, the surface points on the top face can be recorded from various orientations and are much less dependent on the scanning views. In general, outliers are view-dependent and surface points are almost invariant to scanning views. The exception happens when the light is occluded by the concave geometry such as small holes. In such a scenario, the side walls of the hole may be only visible from limited views. Thus the surface points for such geometries may also become view-dependent.     Figure 5.1 (a) Scanning the top face of a cylinder; (b) Outliers in the scanned point cloud.  The above observation indicates a straightforward way to distinguish an outlier from an ordinary surface point by exploring its view-dependent property. If an object is scanned from various 20°Moving Direction(a) (b) 71  orientations by rotating the scan path as shown in Figure 5.2, outliers in a certain region will only occur for a limited number of orientations that can cause mixed reflections and multi-path reflections. In contrast, ordinary surface points are recorded as long as the surface is visible to the sensors, which correspond to many orientations. Three criteria will be proposed to estimate view-dependency of outliers and detect them from ordinary surface points.   5.2.1.1 Overlap Ratio Given n  point clouds scanned from n  different orientations in Figure 5.2, if the point clouds are well aligned together, then a surface region should contain surface points scanned from many different orientations. On the contrary, an outlier region should contain points scanned from only one or a few orientations. In other words, the ordinary surface points corresponding to different orientations should share many overlap regions, whereas outliers only have few overlaps from a few similar orientations. An overlap ratio can be introduced to estimate the view dependency for each point and help distinguish outliers. To be more specific, for a point ip  belong to scanning orientation i , its k -nearest neighborhood Q  may contain neighbors from other orientations. The number of neighbors from other orientations to the neighborhood size k  can well estimate a point’s overlap ratio. A large ratio means a point is in a region visible to many orientations and is likely to be a good point. On the other hand, a small ratio indicates that only a few orientations can record points in this neighborhood and thus this point is view-dependent and will be treated as an outlier using a ratio threshold.  72    Figure 5.2 (a) Scanned point clouds from various orientations; (b) Merged data after alignment; (c) Points with high overlaps.  Based on the experiments in Chapter 4, outliers caused by mixed reflections are quite view-dependent. These outliers move as the orientation changes and may even disappear if the edge orientation angle (EOA) and in-plane incident angle (IIA) are sufficiently large. The overlap ratio works well to detect such outliers. However, outliers caused by multi-path reflections around concave geometries are complex and almost always occur regardless the scanning orientation. In other words, an outlier caused by multi-path reflections may still have a considerable overlap ratio. A small ratio threshold may not detect such outliers, while a large threshold will indiscriminately remove some good surface points. Therefore, the overlap ratio alone is not sufficient to detect such outliers. Other measures are also required to facilitate outlier detection.   0°30°60° 90°120°150°(a) (b) (c) 73  5.2.1.2 Point Spacing Since the outliers caused by multi-path reflections are relatively sparse while ordinary surface points are very dense due to overlaps, a local point spacing threshold can be used to indicate such outliers. It is a common practice to set a minimum point spacing parameter during the scanning setup to control the point density. In each individual scan, each point’s local spacing in a point cloud is expected to be larger than the minimum point spacing no matter the point is an outlier or not. Since good surface points from various scans have many overlaps after alignment, their point spacings become much smaller than the minimum spacing parameter. The point spacings for outliers are still large due to the lack of overlaps. Therefore, the minimum point spacing in the scanning setup is a good threshold to separate dense surface points from sparse outliers.   5.2.1.3 Surface Variation Furthermore, the outliers caused by multi-path reflections form planar surface patches only around concave planar geometries. When scanning curved geometries such as round holes, the distribution of outliers will become much irregular instead of being planar. Such irregularity can be measured using the surface variation [49].  Surface variation is based on principal component analysis (PCA) in each point’s k-nearest neighborhood. It can obtain a minimal ellipsoid enclosing the k -nearest neighborhood Q  of a point p . Let p  be the centroid and C  the 3 3  covariance matrix of P  defined as  1 12 21Tk kk                     p p p pp p p pCp p p p , i p Q       (5.1) 74  Then surface variation ( )n p  of a point p  is  00 1 2( )n      p       (5.2) where 0 , 1  and 2  are the eigenvalues of C  with 0 1 2    . Surface variation can measure how closely a local neighborhood forms a smooth planar surface patch. For an ordinary surface point, its surface variation is relatively small for two reasons. One is that the neighborhood represents a good surface patch, which is relatively smoother than the neighborhood of an outlier. The other is that, even when a good surface patch has high curvature or sharp feature, its neighborhood radius is relatively small due to high overlaps and does not cover large surface variation. On the contrary, outliers due to multi-path reflections around complex geometry can point to various directions and have large surface variations. Therefore, the surface variation can help detect such outliers. In summary, the overlap ratio, local point spacing and surface variation can be used to distinguish outliers from ordinary surface points from different perspectives.   5.2.2 Rotating Scans The above three criteria are derived from the view-dependent property of outliers. Their effectiveness much relies on how the rotating scans are performed. To be more specific, the scanning orientation and the rotating angle interval in Figure 5.2 to generate each scan path should be properly selected in order to make outliers highly view-dependent and ordinary surface points remain view-independent. Regarding the selection of scanning orientation, the goal is to choose proper scanning orientations so the outliers are most view-dependent. The three orientation angles all affect the outlier extensity according the experiments in Chapter 4. However, their effects on the view-dependent property of outliers are different.  75   From the mixed reflection experiments, increasing the out-plane incident angle (OIA) reduces the outlier extensity, but does not change the view dependency significantly. In contrast, changing the in-plane incident angle (IIA) and edge orientation angle (EOA) can shift the outliers and even eliminate them when the angles are large enough. Therefore, these two angles can better ensure the view-dependent property of outliers. In the multi-path reflection scenario, all the three angles can affect the outlier distributions. In general, scanning an object with various IIAs and EOAs are preferable to generate point clouds with view-dependent outliers.   Given a general object, it is a common practice to plan a scan path to cover the bounding box of the object using a zigzag pattern if special attention to certain geometry details is not much required. Then the top and side surfaces should all be covered, which means the probe should be tilted instead of scanning the top surface perpendicularly. A scan path defines the position and orientation of the laser probe with respect to the scanned surface in any instant. From Chapter 4, changing the probe orientations significantly affects the outlier occurrence regions, whereas changing the probe positions does not. So here the scan path positions can be adjusted to scan specific features if necessary.   Based on the experiment in Chapter 4, a large IIA can effectively reduce the outliers caused by mixed reflections. Here a 45° IIA is used as shown in Figure 5.3. EOA is very flexible and can cover a complete rotation. Selecting the EOA interval is equivalent to specifying the number of rotating scans.   76    Figure 5.3 (a) A path (45° IIA and 0° EOA) to scan the bounding box of a general object; (b) One of the rotated paths (45° IIA and 30° EOA).  A few scans with a large EOA interval may not produce sufficient overlaps, while a large number of scans produce very dense point clouds so even outliers may have large overlaps and the overall data set may be unnecessarily large. It turns out the number of scans plays a critical role in the overall performance of the rotating scan scheme, which will be discussed in the next section. Figure 5.3a shows a scan path of 45° IIA and 0° EOA. This base path can then be rotated to change EOA with a predefined interval. Figure 5.3b illustrates a rotated scan path using EOA interval of 30°. Here IIA and EOA are measured with respect to the bounding box of the scanned object without considering its specific geometries. The scan depth is also not considered. As stated in Chapter 4, scan depth does not noticeably affect outlier occurrence regions. The scan path can be adjusted to scan shallow concave geometries if required without changing the scanning orientation.   (a) (b) 77  A rotating scan scheme is proposed to scan a physical object and detect the view-dependent outliers in the scanned point cloud. The overall scheme consists of two phases: data acquisition and data processing.  The data acquisition is described as bellow.  1. Specify the four corners of the bounding box covering the object by the operator. 2. Generate n  scans paths using 45° IIA and EOA interval of 360 / n . Each scan path has a unique scanning orientation.  3. If required, adjust the scanning path positions for specific surface features without changing scanning orientations. 4. Perform the scanning operations using the rotated paths and record n  raw scanned data corresponding to n  scanning orientations.  5. Merge n  scanned point clouds to a single data set S  using the scanning orientation information The resulting point cloud combines all the data from various scanning orientations. Each point in the point cloud has its 3D coordinates and the orientation angles it is scanned from.           78  Regarding the data processing, the outlier removal algorithm is described below.  Algorithm 5.1: Outlier Removal by Rotating Scans 1. for each p S  do      Q the k -nearest neighbors of p                   Overlap ratio overlapp   number of neighbors from other orientations / k                   Point spacing spacingp   the neighborhood radius of Q       Surface variation var iationp   principal component analysis in Q [49]                  if _overlapp overlap threshold                        or _spacingp spacing threshold                        or  var iationp variation_threshold then                             Mark p  as an outlier                  end if end for 2. Remove marked outliers in S  3. Iterate step 1, 2 until stable   As discussed in Section 5.2.1, a good surface point generally has a large overlap ratio, small point spacing (high point density) and low surface variation. An outlier is sensitive to the scanning orientation so it has a small overlap ratio. Outliers caused by multi-path reflections are usually sparser than good surface points and also have large surface variations. The three criteria 79  distinguish such outliers from ordinary surface points and iteratively remove them. The implementation and involved parameters will be discussed in the next section.   5.3 Case Study and Discussion This section discusses the implementation and a typical case study of the proposed outlier detection method using rotating scans. The prototype program of outlier removal is implemented on a standard PC with Intel Core-i5 CPU at 3.30 GHz and 4G RAM without parallelization.    5.3.1 Case Study An aluminum block is chosen as the test object since it has reflective surfaces and general geometries such as edge features, prismatic features and holes, which are common in mechanical parts. As shown in Chapter 4, the point cloud scanned from this part contains extensive outliers. In this case study, the part is scanned from 12 different orientations using 45° IIA and 30° EOA interval. The 12 scanned point clouds are shown in Figure 5.4. The scan paths using EOA of 0°, 90°, 180° and 270° are illustrated in Figure 5.4a. Figure 5.4b shows the complete point cloud after merging all the 12 raw data.   Several parameters require to be determined to process this point cloud. The number of scans n  is a key factor in determining the view-dependent property of outliers and will be further discussed in the next section. Here 12 rotating scans are used with EOA interval of 30°. The neighborhood size k is the same as the number of scans n . In an ideal situation, a point’s k  neighbors are all from n  different scans to have the largest overlap ratio. Three thresholds are introduced and can be adjusted empirically. In this work, the overlap ratio threshold is 0, which means a point is an 80  outlier if it has no overlap around. The point spacing threshold can be set to be the minimum point spacing parameter according to the scanning setup. The surface variation threshold is 0.1 to promote planar neighborhood. The iterating process stops if the detected outliers are less than 10 from the previous iteration or the overall iteration number exceeds 5 times. These parameters are empirically selected based on extensive tests on scanned point clouds.   0° 30°330°60°300°90°270°240°150°210°180°Point SpacingSurface VariationOverlap Ratio120°  Figure 5.4 (a) 12 scanned point clouds; (b) Merged point cloud; (c) Point cloud after outlier removal; and (d) Distributions of overlap ratio, point spacing and surface variation.  With these parameters, each point gets its 12 nearest neighbors and estimates the overlap ratio, point spacing and surface variation according to the algorithm. The distributions of these three measures are colorized in Figure 5.4d for the first iteration. In the zoom-in view (red boxes), outliers generally have smaller overlap ratio (red) than surface points (blue). For outliers caused by mixed reflections around sharp features, they have small overlap ratios (red) due to view-dependent property. For outliers caused by multi-path reflections in the yellow circle, most of them are red but some have high overlap ratios (green). This is because these outliers around the concave (a) (c) (d) (b) 81  cylindrical surface are caused by multi-path reflections and locate around the center due to the curved surface with continuously changing normals. Similar situation happens around the holes of the part. Most outliers around the holes have low overlap ratios, while some have high ratios. Therefore, a simple overlap ratio threshold is insufficient to detect these outliers. Thanks to point spacing and surface variation, the outliers with high overlap ratios usually have either large local point spacing or large surface variation, and thus can be removed. Regarding surface points, although some points on the side wall (red) does not have as high overlap ratio and low point spacing as the points on the top surface, they still have higher overlaps and lower point spacing than most of the outliers. For surface variations, surface points around sharp features like edges and corners have larger surface variations than planar surface points, yet smaller variations than outliers caused around concave geometries like the cylindrical surface and holes, although may have high overlap ratios. In general, outliers with no overlaps, large local spacings and large surface variations are gradually removed, while ordinary surface points are well kept as shown in Figure 5.4c.   To illustrate the importance of rotating scans, Figure 5.5b shows the scanned point cloud from an aluminum part (Figure 5.5a) using a poorly planned scan path as in Chapter 4. A better point cloud is recorded using the proposed rotating scans in Figure 5.5c. The outliers are much less extensive since a large IIA (45°) can significantly reduce outliers caused by mixed reflections around edge features. However, outliers caused by multi-path reflections are still present. These outliers are then effectively removed using the proposed algorithm as shown in Figure 5.5d.   82   Figure 5.5 (a) An aluminum part; (b) Scanned point cloud using poorly planned scan paths; (c) Scanned point cloud using rotating scans; and (d) Point cloud after outlier removal  5.3.2 Number of Scans The critical parameter in the proposed scheme is the number of rotating scans. It directly affects the view-dependent property of outliers. As mentioned before, a few scans may not produce sufficient overlaps, while too many scans make outliers with large overlaps and increase the data size dramatically. To investigate its effect on the performance of outlier removal, the aluminum part is scanned using various numbers of scans as shown in Figure 5.6. The parameters for each data have been adjusted to achieve the best possible results. It can be seen that only two or four scans to cover each side of the bounding box do not generate sufficient overlaps for the sidewalls. In Figure 5.6a and Figure 5.6b, the top face is covered by all scans, but each sidewall is only visible to one scan without overlaps. Thus the sidewall points will be removed together with outliers. As more scans are used, the overlaps for sidewalls increase and the algorithm starts to perform better with proper parameters. However, the time required for the scanning and data processing also (c) (d) (a) (b) 83  increase. Meanwhile, the resulting point cloud become quite large and may require further simplification. From extensive tests, the proper number of scans ranges from 8 to 12 can make a good trade-off between the effectiveness of the method and the overall processing time and data set size. For a vastly different object, the number of scans may be quite different. The actual number requires user adjustment by trial and error.    Figure 5.6 Merged data (top), overlap ratio distribution (middle) and outlier removal results using different numbers of scans.  5.4 Comparison with Existing Methods To demonstrate the effectiveness of the proposed approach, it has been compared with Rusu’s sparse distribution [15], Weyrich’s PMR (plane fitting, miniball, and nearest-neighbor reciprocity)  [13], Shen’s surface propagation [6] and Teutsch’s Region growing [17] methods. The first two methods mainly detect sparse outliers locally in each point’s neighborhood. Shen’s method iteratively estimates the underlying surface in order to detect non-isolated outliers that are so close to the good surfaces. Teutsch’s approach globally classifies the point cloud into many clusters, among which small ones are treated as outliers. The parameters involved in these methods are 2  6 4 8 12 84  either selected using the suggested values or manually adjusted to achieve the best possible results. The proposed method uses parameters as discussed in the previous section.   In the absence of the reference CAD model, this work visually evaluate the performance of various methods through comparing the original point cloud and the processed one after outlier removal as in [6]. Figure 5.7 shows the outlier removal results for the point cloud in Figure 5.4 using various methods. It can be seen that the first two methods fail to detect dense outliers due to insufficient good points in local neighborhoods. Shen’s method also leaves many dense outliers undetected. Teutsch’s approach shows a better result by treating small clusters as outliers. However, some sparse surface points (in the red circle) around the side walls are also mistakenly removed. If a smaller cluster size threshold is used, some large outlier clusters will remain undetected. In contrast, the proposed method demonstrates the best result in comparison with other methods. It effectively removes outliers around edge features as well as concave geometries without noticeably removing good surface points.   Figure 5.7 Outlier removal results using various methods.  RusuShenOriginal WeyrichTeutsch Proposed85  Figure 5.8 compares these methods on the point clouds scanned from a part with concave cylindrical surfaces. Due to specular reflections around such geometries, some outliers form planar patches and become very dense. Shen’s method based on the randomness of outliers turns out to be ineffective in detecting such systematic outliers. Moreover, some outliers (in the red circles) are so close to the good surfaces and cannot be separated using Teutsch’s approach. The proposed method again demonstrates superior results to other methods in detecting outliers.   WeyrichOriginalTeutsch ProposedRusuShen Figure 5.8 Outlier removal results using various methods on a part with concave cylindrical surfaces.  Similar to Figure 5.5, Figure 5.9 shows the point clouds scanned from the part using a poorly planned scan path and the rotating scans. The outliers around the edge features are significantly reduced using the rotating scans. The remaining outliers are further removed using the proposed methods. Other tests have also been conducted as shown in Figures 5.10 and 5.11 to demonstrate the effectiveness of the proposed method. The ball bearing does not have sharp features but contains concave circular rings. Outliers occur around the outer ring and the ball holders. A similar situation happens in scanning the round plate in Figure 5.11. The proposed method can still effectively remove these view-dependent outliers.   86    Figure 5.9 (a) A part with concave cylindrical surfaces; (b) Scanned point cloud using a poorly planned scan path; (c) Scanned point cloud using rotating scans; and (d) Point cloud after outlier removal.    Figure 5.10 (a) A metal ball bearing; (b) Scanned point cloud using rotating scans; and (c) The point cloud after outlier removal.  (a) (b) (c) (b) (c) (a) (d) 87    Figure 5.11 (a) An aluminum round plate with holes; (b) Scanned point cloud using rotating scans; and (c) Point cloud after outlier removal.  The proposed method detects outliers through locally estimating the overlap ratio, point spacing and surface variations in each point’s neighborhood. Thus it is computationally fast as other local detection methods and is much faster than Shen’s method since approximating the underlying surface is computationally expensive. Table 5.1 shows the computation time using the proposed method on various point clouds. In general, the prototype program can process 1 million points within 1 minute without optimization.   Regarding the limitations, the proposed method explores and relies on the view-dependent property of outliers. When scanning small concave features such as hole, some inner surfaces may only be visible to a few limited views due to the light occlusion and thus become view-dependent as well.  As shown in the yellow circles of Figure 5.91d and Figure 5.10c, some points inside the holes are falsely removed due to the lack of overlap. Special consideration should be given when scanning such features. For example, these local features can be further scanned from more orientations to promote overlaps as a fine scanning phase after the general rotating scans [6].   (a) (b) (c) 88  Test Data No. of Points Time (s) Data in Figure 5.2 125,325 2 Data in Figure 5.4 1,591,995 54 Data in Figure 5.8 1,426,323 49 Data in Figure 5.10 1,464,992 60 Data in Figure 5.11 1,675,241 65  Table 5.1 Computational time of the rotating scan method for various test data.  5.5 Summary Scanning reflective surfaces is a common yet challenging task due to the extensive outliers. Thus effective outlier removal methods are highly desirable to ensure the quality of point cloud applications. Based on the experiments in Chapter 4, outliers caused by mixed reflections and multi-path reflections are general dependent on the scanning orientation, whereas ordinary surface points are almost view-independent.   To explore this view-dependent property, this chapter proposes an outlier removal method using a rotating scan scheme. The key ingredient of this method is that, different from many existing methods, which analyzed the point cloud only, the proposed approach utilizes the scanning orientation information together with the point cloud to reliably identify view-dependent outliers. Three criteria, overlap ratio, point spacing and surface variation, have been proposed to distinguish outliers from surface points. Numerous tests have demonstrated the effectiveness of the proposed approach in comparison with various existing methods.   Although the proposed method is computationally efficient due to the local estimation nature, it relies on the specific rotating scan scheme and may not be general enough to be applied to other 89  scanning scenarios or other types of 3D scanners. Moreover, good surface points around concave geometries may become view-dependent and will be removed just as outliers due to the light occlusion. In the next chapter, a generic outlier removal will be presented to detect various types of outliers from a geometrical perspective without specific scanning setup.  90  Chapter 6: Generic Outlier Removal using Majority Voting 6.1 Introduction  Measurement outliers are inevitable by-products of 3D scanning and pose many problematic issues to many point cloud applications. Although the proposed method in Chapter 5 can efficiently remove view-dependent outliers, it relies on the rotating scan setup and may not be generally applicable to all scanning scenarios. It is highly desirable to develop a more flexible yet still effective approach that can detect outliers without specific scanning setup information.   As demonstrated in Figure 1.1, outliers can be sparsely distributed or densely clustered. The clustered outliers can either be isolated from the scanned surface or non-isolated from distance perspective. Many outlier removal methods have been proposed in the literature, but they generally focus on a certain type of outliers and are inapplicable to other types of outliers.  For example, methods to remove sparse outliers [13, 15] detect outliers based on low local point density and rely on the condition that the local neighborhood of each point contains sufficient data points.  Such methods are unable to detect dense outlier clusters since the local neighborhood of each point in an outlier cluster still contain a good number of data points.  To detect outlier clusters, existing methods [17, 18] segment a scanned point cloud into many clusters and then treat small clusters as outliers, which will mistakenly remove good clusters with smaller numbers of data points.  When non-isolated outlier clusters exist in the point cloud, these outliers will blend into the scanned object surface.  To remove these non-isolated outliers, Shen et al. [6] proposed a surface propagation method based on the assumption that outliers were randomly distributed and should not form smooth surface patches.  However, such an assumption is not always valid in practice since non-isolated outlier clusters are in fact systematic and can actually form planar surface 91  patches according to outlier formation models in Chapter 3.  Thus, non-isolated outliers remain undetected.  In this chapter, a comprehensive outlier detection method is developed to effectively identify sparse outliers, isolated outlier clusters, and non-isolated outlier clusters in scanned point clouds.  Among the three types of outliers, non-isolated outlier clusters are the most challenging to detect since they are connected to the scanned surface and can even form planar patches.  Common clustering methods will always end up with clusters in which non-isolated outliers are mixed together with good surface points.  To address this issue, a majority voting based approach is proposed to reliably detect and transform non-isolated outlier clusters into isolated clusters. This step requires a normal vector at each point to form a local coordinate system, in which a quadric surface can be fitted to locally approximate the scanned surface patch. A pre-processing step of normal vector estimation is thus required. In Section 6.2, a robust normal estimation algorithm is proposed to estimate normal vectors in the presence of sharp features, noise and outliers. Benefiting from the normal vector estimation, the non-isolated outlier clusters can be removed using majority voting in Section 6.3. Then, an expandable boundary criterion is employed in Section 6.4 to remove all the sparse outliers and the isolated outlier clusters, as well as to preserve critical geometric features such as sharp edges. The implementation results of the proposed method is discussed in Section 6.5, following by the summary in Section 6.6.   6.2 Robust Normal Vector Estimation Reliable estimation of the normal vector at each point in a scanned point cloud has become a fundamental step in point cloud data processing.  For example, many surface reconstruction 92  algorithms require accurate normals as input in order to generate high-quality surfaces [7, 50].  The performance of common point-based rendering techniques is much dependent on the accuracy of the input normals [51, 52].  Direct applications of normal estimation can also be found in segmentation [53], smoothing [38], simplification [54, 55], shape modeling [10] and feature detection and extraction [49, 56]. In this chapter, estimating normal vectors can help approximate the local surface patch formed on each point’s neighborhood and consequently detect non-isolated outliers close to the scanned surface.   Given a scanned point cloud, the problem being studied in this section is how to estimate the underlying surface normal vector at each data point in the presence of inevitable noise and outliers. In particular, when the underlying surface of the scanned object contains sharp features, which are common in mechanical parts, normal estimation becomes very challenging as ordinary scanning noise compensation techniques will also smooth out sharp features. The resulting normals are thus not accurately evaluated around sharp features, which negatively impacts subsequent applications of the scanned point cloud.  For instance, the reconstructed surface and point-based rendering based on inaccurate estimated normals would lose sharp features (Figure 6.1b).  If the normals around sharp features can be accurately estimated, the sharp features will be preserved well and the reconstructed surface will correctly represent the physical object geometry (Figure 6.1c).  It is thus of much importance to develop an accurate normal estimation method for scanned point clouds which can preserve sharp features well. 93                   (a)            (b)       (c) Figure 6.1 (a) A sample scanned point cloud (top) from a gear (bottom); (b) Existing neighborhood weights around a sharp-feature point (top), reconstructed surface (middle), and point-based rendering (bottom); and (c) The proposed anisotropic neighborhood weights and results.  Numerous normal estimation methods have been presented in the past. Voronoi diagram was used to estimate normals for point cloud scanned from smooth surfaces [57]. Methods based on parametric surface fitting have also been proposed to better compensate noise. Least-squares planes [58], quadric surfaces [53] and spheres [59] were used to fit the local neighborhood at each 1.0 0.0 94  point to approximate the normal vector.  A detailed comparison of most of these existing methods is available [60]. When the underlying surface of a point cloud contains sharp features, the quadric surface and sphere fitting methods described above for normal vector estimation are inapplicable near the sharp features due to the implied first-order continuity.  As the initially estimated normals are likely to be noisy, normal mollification methods [7, 61] have been proposed to smooth out the noisy normals.  Another category of methods is to extract normals by defining point set surfaces.  The well-known moving least-squares (MLSs) surfaces [62] and its variants [7, 50, 51, 63] locally approximate the points using a polynomial surface.  Such methods are not only able to compute normals and curvatures [64] but also facilitate point cloud smoothing, resampling, and mesh triangulation [65]. However, sharp features are not explicitly considered. To improve the normal estimation accuracy around sharp features, Mederos et al. [66] applied the M-estimator [67] to robustly fit a local plane at each point by penalizing neighboring points with large fitted residuals, which usually correspond to points across sharp features.  Li et al. [8] proposed a local tangent plane detection method using a random sampling strategy, which is robust to outliers, yet quite computationally expensive. Boulch and Marlet [68] adopted a robust randomized Hough transform method to estimate normals with parameters to compromise between computation time and precision. However, both methods require dense point data around sharp features, which is not always available in scanning practice [6].    The common issue in normal estimation is that, for a point close to a sharp feature, which can be the boundary of two surface patches (an edge) or more (a corner), the employed point neighborhood would enclose points from more than one surface patch.  This makes the estimated normal biased and inconsistent with the correct surface normal. Methods that can preserve sharp 95  features are rare and all have specific requirements such as user-specified parameters [7, 66] and high point density [8, 68].  To address this outstanding issue, a robust normal estimation method is proposed in this section to estimate normals through iteratively reweighted plane fitting.  In particular, the M-estimator [67] in robust statistics was adopted to effectively reduce the influence of scanned data outliers and neighboring points belonging to different surface patches across a sharp feature.  More importantly, for a point around a sharp feature, an anisotropic neighborhood containing points solely from the same surface patch is to be formed through incorporating three kinds of weight functions related to point distance, fitted residual, and normal difference.  The normal can thus be accurately estimated from the properly identified neighborhood.  It will be shown that the normal estimation process is not only highly robust with respect to scanned data noise and sparse outliers, but is also capable of handling sparsely and non-uniformly sampled point data.  6.2.1 Iterative Reweighted Plane Fitting This section briefly describes the proposed normal estimation algorithm. The detailed method has been presented in [69]. The proposed algorithm essentially estimates the normal at a point x  by fitting a local plane on the k -nearest neighbors of x . The initial normal estimation method via the weighted plane fitting by Mederos et al. [66] can be formulated as: { , } ( ( ) ) ( )Ti d id argmin d w  n x x n x          1n  (6.1) where 2( ) exp( )d i i dw   x x x is a Gaussian weight function related to the distance from a point x  to its neighbor ix  and 2 2( ) (1 exp( ( ) ))2rrx     x is the Welsch function.  d  and 96  r  are respectively the distance and fitted residual bandwidths, which control the relative contribution of each neighbor.  d  is the distance from x  to the fitted plane and n  is the plane normal.  By taking ( )r dw dx xx, Equation 6.1 can be solved iteratively as:   1{ , } ( ) ( )k k k ki d i r id argmin r w w r  n x          1k n  (6.2) where ( )k k T ki ir d  x x n is the fitted residual of a point ix  at the kth iteration.  rw  is also a Gaussian weight function related to the fitted residual, 2( ) exp( ( ) )r i i rw r r   .  The iteration starts with 0( ) 1r iw r  .  As the weights are fixed in each iteration step, Equation 6.2 becomes a constrained least-squares problem, which can be reduced to an eigenvector problem using the Lagrange multiplier.  The corresponding covariance matrix C  is T                  1 12 2N Nx - x - x x - x - xx - x - x x - x - xC... ...x - x - x x - x - x          ( ) ( )( )( ) ( )d i r i id i r iw w rw w r x x xx x (6.3) where N  is the total number of neighboring points considered.  The eigenvector corresponding to the smallest eigenvalue of C  is the normal vector n  of the current iteration, and Td  x n .  Equation 6.2 can thus be interpreted as iteratively reweighted plane fitting at a point x  from its neighboring points considering both the distance and fitted residual weights.  As shown in Figure 6.2a, the initial fitted plane 0p  with distance weight considers the neighbors of x  on two surface patches (in the red circle) and is biased towards the surface patch on the left.  Then, a normal is estimated at each point according to the same plane fitting procedure.  In the subsequent iteration of Equation 6.2, the residual weight starts to play a role (Figure 6.2b) and the fitted plane is 97  gradually tilted towards the surface patch on the right via penalizing the neighbors with large fitted residuals (on the left).  The iteration terminates when the fitted plane is stabilized.     Figure 6.2 Iterative reweighted plane fitting for a point around a sharp feature incorporating distance, residual and normal difference weights.  It should be noted that Equation 6.1 has limited capability to handle sharp features.  As shown in Figure 6.2b, the effective neighborhood (shown as the red ellipse) still contains points from the surface patch on the left.  The reason is that Equation 6.1, which penalizes neighboring points with large fitted residuals via assigning small weights, considers large residuals to be caused solely by sharp features.  Nonetheless, relatively large fitted residuals can also result from curved surface geometry.  As a result, penalizing points with large residuals is unable to effectively reduce the influence of neighboring points across sharp features without over penalizing essential neighbors in curved surface regions.  The resulting biased normal estimates, leading to uneven shading in smooth regions, have been illustrated in Figure 6.1b. Equation 6.1 thus needs to be further improved to be more accurate around sharp feature as well as in smooth surface regions. x  0in  0p  ix  ir  0n  ix  1p  kp  0ir  kin  ix  kir  kn  1n  x  x  (a) (b) (c) 98     Figure 6.3 Combined weights for neighbors of three typical points on the Fandisk model surface: (a) distance and residual weights; and (b) distance, residual and normal difference weights.  The normal at a point is in general close to the normals of its neighbors located on the same surface patch, but is quite different from those on the other surface patches across a sharp feature.  The neighbors belonging to different surface patches can be treated as outliers in the normal field, referred to as the normal outliers.  This essentially suggests the addition of another weight function related to the normal difference 2( ) exp( )n i i nw   n n n to penalize neighbors having normals much different from the normal of the point.  The improved minimization procedure becomes 1 1{ , } ( ) ( ) ( )k k k k ki d i r i n id argmin r w w r w  n x n          1k n  (6.4) 1.0 0.0 Corner Smooth region Edge Corner Smooth region Edge (a) (b) 99  where in  is the estimated normal from Equation 6.2 and n  represents the normal difference bandwidth.  Equation 6.4 can be solved using Equation 6.3 with the added term ( )n iw n .  The overall process is to firstly estimate the initial normals using Equation 6.2 and then further improves the normals by Equation 6.4.  As shown in Figure 6.2c, for neighboring points on the left side of point x , the normals estimated from the previous iteration are quite different from the estimated normal of x .  Thus, these neighbors will effectively be discarded due to their negligible normal difference weights and only the neighbors on the right side will be considered in the current iteration of Equation 6.4.  Meanwhile, the spatial outliers corresponding to large fitted residuals are also discarded due to their negligible fitted residual weights.  As shown in Figure 6.2c, the effective neighborhood (shown as the red ellipse) only encloses points from the surface on the right.  Three kinds of weight exist in Equation 6.4. The underlying concept is to firstly employ distance weight dw  in order to include nearby points and ignore points relatively far away.  Then, neighbors with large fitted residuals (spatial outliers) and those belonging to different surface patches across a sharp feature (normal outliers) are discarded by assigning negligible residual weights rw  and normal difference weights nw  during the iterative reweighted plane fitting process.  An anisotropic neighborhood only enclosing neighbors from the same surface patch is formed for each point.  The fitted plane based on such a neighborhood can thus reliably approximate the local surface shape around a sharp feature.  Figure 6.3 shows the outcome from combining two and three weights.  With the three kinds of weights in Figure 6.3b, neighbors belonging to different surface patches 100  across a sharp feature are correctly neglected since their estimated normal vectors are quite different from the normal of the point of interest.    Although Equation 6.4 is able to provide improved normal estimation around sharp features, its effectiveness relies on the selection of proper bandwidths for the weight functions.  To address this issue, it is proposed to firstly use empirical bandwidths for Equation 6.2 to estimate the initial normal to infer sharp features, then use these initial normals to evaluate the locally adaptive parameters for the bandwidths, and finally improve the normals via Equation 6.4 with the evaluated bandwidth parameters.  6.2.2 Adaptive Bandwidth Selection Bandwidth selection is a common and critical problem for all methods using weight functions since the selected bandwidth exhibits a strong influence on the estimation results [67].  In particular, the bandwidth governs the rate with which the weight varies.    The first of the three weights in Equation 6.4, the distance weight, should be formulated to contain a relatively large bandwidth d  in order to ensure that sufficient neighbors are included.  The residual and normal difference bandwidths then play an important role in assigning their respective proper weights to these neighbors.  d  is commonly selected to be at a fixed ratio with respect to the local point spacing l  of the point of interest: d d lc   .  The local point spacing is evaluated as the average distance from a point to its 6 nearest neighbors.  A small dc  shows poor resistance to noise in the point cloud while a large dc  increases the computational time.  The problem with 101  this global ratio dc  is that the effective neighbors for a sharp feature point are much less than the neighbors of a point in a smooth region, as shown in Figure 6.2b. Consequently, the estimated normals around sharp features are prone to noise due to smaller neighborhoods. In other words, larger bandwidth is preferred for sharp features. Therefore, dc  should be adaptive to whether the local neighborhood encloses sharp features or not and how close it is to sharp features.   After enclosing sufficient neighbors, the spatial outliers and normal outliers should be assigned negligible residual and the normal difference weights.  To achieve this, the residual bandwidth r  and the normal difference bandwidth n  should be relatively small in order for the involved weight functions to decrease rapidly.  Nonetheless, for a point neighborhood in curved surface regions, normals always gradually vary among the neighboring points and the plane fitting naturally leads to varying fitted residuals.  Small residual and normal difference bandwidths will result in too much penalty in curved surface regions and cause the plane fitting to falsely bias towards some neighbors.  This would in effect suggest choosing large bandwidths in order to yield relatively flat weight functions in curved surface regions.  The above statements can be easily verified via testing on a cylinder point cloud, which contains both sharp features and curved surface regions.  Figure 6.4 illustrates the normal estimation errors using Equation 6.4 with different bandwidths.  It can be seen that infinite bandwidths work very well for smooth cylindrical regions but fail around sharp features (Figure 6.4a).  When small bandwidths are employed, negligible weights would be assigned to points with large fitted residual or normal difference.  This leads to much better normal estimation near sharp features, but worse in the cylindrical surface since the rapidly decreasing weight functions causes biased plane fitting (Figure 6.4b).  It is then evident 102  that if we could adaptively apply large residual and normal difference bandwidths to points in smooth regions and gradually decrease them towards the sharp features, the normal estimation would be good for the entire object surface (Figure 6.4c).  In summary, the bandwidths for the residual and normal difference weights should be locally adaptive according to whether a point’s neighborhood is located in smooth regions, sharp feature regions, or transition regions in-between.  A feature coefficient for each point, Fcoe , is thus introduced to quantify how close a point is to a sharp feature.  The feature coefficient value ranges from 0 (a point’s neighborhood in a smooth region) to 1 (a point’s neighborhood on a sharp feature) and it will be used to determine the proper bandwidths. The feature coefficient can be estimated by normal vector clustering, which is described in Appendix A.                   (a)                   (b)                (c) Figure 6.4 Normal estimation errors for a noisy cylinder point cloud: (a) infinite large bandwidths; (b) small bandwidths; and (c) adaptive bandwidths.  1.04 0.0 103  With the feature coefficient Fcoe  at each point evaluated by automatically clustering normal in Appendix A, the three bandwidths in Equation 6.4 can now be determined in order to further improve the estimated normals.  In the present work, the distance weight bandwidth is set adaptively according to the feature coefficient. (1 )d lFcoe                (6.5)  In this way, the distance bandwidth is l  for a point in a smooth region and only neighbors within the radius of 3 l  are enclosed as the distance weights for points far away are sufficiently negligible ( 410 ). For a sharp feature point, a distance bandwidth of 2 l  can enclose more neighbors and a large proportion will be discarded by residual and normal difference weights. From all the tests in this work, this bandwidth selection shows a good compromise between noise compensation and computation time.   The fitted residual and normal difference weight bandwidths are respectively set as an adaptive fraction of the maximum fitted residual and normal difference from the previous iteration: 3k-1r maxr Fcoe         3k-1n i max Fcoe   n n  (6.6) The scalar 3 is chosen for similar reason as the distance bandwidth so that neighboring points around sharp features with large fitted residuals or normal differences are to be assigned negligible weights ( 410 ), whereas rw  and nw  for neighboring points in smooth regions are effectively equal to 1 and only the distance weight dw  plays a role.  Regarding points in transition regions, the bandwidths would be moderate and neighboring points with relatively large fitted residuals or normal differences are penalized accordingly but not excessively. It should be emphasized that the 104  bandwidth related parameters are chosen empirically from all the tests and are fixed throughout this work.    6.2.3 Case Studies and Discussion The presented normal estimation method is straightforward to implement.  The three main steps are listed as follows:  Step 1: estimate an initial normal for each point.  This is done by iterative reweighted plane fitting using Equation 6.2 with d  set as the local point spacing l  and r  one-third of the maximum fitted residual.  The initial fitted residual weight for each point is set as 1.  The iteration terminates when the involved weights stabilize or the iteration number exceeds a set limit of 20.  Step 2: estimate the local adaptive bandwidths.  For an arbitrary point, the normals of its neighbors within a distance of 3 l  are clustered in order to automatically determine its feature coefficient.  When generating the sharp feature point percentage curve, the angle threshold starts from zero and increases by an increment of 2.5°.  After finding the proper threshold and estimating the feature coefficient Fcoe  at each point, the three weight bandwidths are set using Equation 6.5 and 6.6.   Step 3: improve the initial normals.  This is done by using Equation 6.4 with the adaptive bandwidths determined in Step 2.  The iterative calculation terminates in the same way as that in Step 1.   105  To demonstrate how the normals are improved by Step 2 and Step 3 as well as the needs of the three kinds of weights, a randomly sub-sampled noisy point cloud scanned from a Gear model is tested as shown in Figure 6.5. The initial normals are estimated using dw  and rw  with global bandwidth-related parameters as Step 1 (Figure 6.5c). Figure 6.5b shows the estimated feature coefficient through automatic normal clustering as Step 2. For Step 3, Figure 6.5e shows the normals using dw , rw  and nw  with global parameters. Comparing with Figure 6.5c, the normals around sharp features (red circle) are more accurate due to nw . However, the normals in a smooth region (green circle) are noisy and do not point to the center of the circle. This is because a global small bandwidth for curved surface exaggerates the normal difference in order to extract sharp features. If adaptive bandwidth parameters are used as in Figure 6.5d and Figure 6.5f, the normals in green circles are much more accurate. This demonstrates the importance of the adaptive bandwidth parameters.  It is also necessary to adopt residual weight in the estimation. Without residual weight, the normals in Figure 6.5d for sharp features in the inner ring (red circle) are bias toward the nearby surface patches, whereas Figure 6.5f shows best normals with all the three kinds of weights.     106    Figure 6.5 (a) A randomly sub-sampled scanned point cloud; (b) Feature coefficient estimation results; (c) d rw w  with global bandwidths; (d) d nw w  with adaptive bandwidths; (e) d r nw w w   with global bandwidths; and (f) d r nw w w   with adaptive bandwidths. (a) (b) (c) (d) 1.0 0.0 (e) (f) 107   6.2.3.1 Case Studies The proposed method has been compared with five existing methods [7, 54, 66, 68, 70]. All the methods involve selecting suitable values for the associated parameters.  It should be noted that the proposed method automatically determines the parameter values with no user input while the other methods either manually adjust the parameter values to attain the best results [66] or set the parameters using some suggested values [7, 54, 68, 70].    Regarding the tests on scanned point clouds, quantitative evaluations are not possible since the exact reference normals are unknown.  Alternatively, two different qualitative (visual) comparison approaches are employed.  As the quality of the point-based rendering result of a point cloud highly depends on the accuracy of the input normals [61], straightforward visual comparison can be used to compare the point-based rendering results based on normals estimated by the various methods.  Figure 6.6 shows the point-based rendering results of the Carter point cloud.  It can be seen that sharp edges are preserved well using the estimated normals from the proposed method whereas the estimated normals from the other methods result in loss of the sharp edges.  Moreover, similar to that indicated in Figure 6.1b, the uneven shading in the curved surface regions based on the normals estimated by Mederos et al. clearly indicates that global bandwidth parameters are inapplicable to handling sharp features and smooth regions simultaneously.  Boulch’s method also shows good results on sharp features. However, the normals are noisy and the sharp edges are rough as the randomized hough transform does not smooth noise. Thanks to the smoothing effect of plane fitting, the proposed method leads to smooth normals and shows the best rendering quality due to its adaptive bandwidth values. 108    Figure 6.6 Comparison of point-based rendering results of the Carter data.    Figure 6.7 Comparison of the constructed surfaces of the Gear data based on normals estimated by the various methods.   Pauly Mitra Öztireli Mederos Proposed Boulch Pauly Mitra Öztireli Mederos Proposed Boulch 109  The second qualitative comparison approach is to visually compare the triangle mesh surfaces that are constructed by a method which requires accurate normals as input.  The robust implicit moving-least-squares method [7] has been chosen to construct the triangle mesh surfaces since it is able to reliably reconstruct sharp features if accurate normals are available.  Identical parameters have been used in the surface construction method so that the results would only reflect the quality of the input normals.  Figure 6.7 shows the constructed surfaces based on normals estimated by the various methods.  The constructed surfaces based on normals from the proposed method are seen to preserve sharp features well.  For the constructed surfaces based on normals estimated from the other methods, the edge and corner geometry is rounded and not as sharp.   Unlike the methods [8, 68], which requires densely sampled point clouds around a sharp feature, the proposed method is able to reliably process sparse and non-uniform point clouds.  More specifically, for a point around a sharp feature, the proposed method only requires several neighboring points for feature coefficient evaluation and plane fitting whereas the other two methods require hundreds of neighboring points around the sharp feature in order to reliably implement their random sampling procedure.  Figure 6.8 shows the feature coefficient evaluation and surface construction results for some randomly and sparsely sampled point clouds of about 10,000 points (sub-sampled point clouds from the original data sets).  Although small geometric details are lost due to the much reduced point density, most of the sharp feature points can still be correctly detected, leading to well-preserved sharp features.   110   Figure 6.8 Estimated normals and constructed surfaces for sub-sampled Gear and Cater data.  Another important characteristic of the proposed method is that it is equally applicable to noisy point clouds with sparse outliers, as illustrated in Figure 6.9.  It can be seen in this figure that,  although the point-based rendering results of the Carter and Ring data with the added noise and outliers, show some visually uneven surfaces, the normals for points around sharp features can still be reliably estimated with the sharp features clearly visible.  1.0 0.0 111                      (a)         (b) Figure 6.9 (a) Carter and Ring data with 0.3% noise and 3% outliers; and (b) Point-based rendering results using the estimated normals of this work (outliers not shown for better view).  6.2.3.2 Computational Time Since the proposed method iteratively fits a local plane and updates the associated fitted residual and normal difference weights at each point, it is expected to be less computationally efficient than the method by Pauly et al. [54], which only performs the plane fitting once.  Test computations were carried out on a PC with a 3.30 GHz Intel Core processor and 2GB RAM without parallel computing.  The number of points in each test data set and the resulting computational time are listed in Table 6.1.  The most time-consuming part in the proposed method is to evaluate the feature 112  coefficient at each data point.  The longer computational time is in fact well spent since the evaluated feature coefficients can be used not only for the adaptive bandwidth value determination but also for segmentation and feature extraction.  As sharp feature information is preserved well in the estimated normals, further post-processing of the scanned point cloud for sharp feature recovery may not be required.  Test Data No. of Points Time (s) Icosahedron 9,300 6 Cylinder 12,200 7 Fandisk 24,666 12 Carter 192,729 125 Gear 459,994 230 Rolling-Stage 606,542 281 Ring 949,731 370  Table 6.1 Computational time of the normal estimation method for various test data.  6.2.4 Summary A robust normal estimation method has been presented in this section to reliably estimate normals for noisy point clouds with outliers.  The proposed method incorporates three weights to effectively reduce the influence of sparse outliers both in the spatial and in the normal field on the normal estimation.  It does not impose strict restrictions on point density.  Also, the proposed method is applicable to points in smooth regions as well as around sharp features via employing locally adaptive bandwidth parameters for the weights.  The adaptive bandwidth parameter values are set according to the automatically evaluated feature coefficient at each data point.   113  Similar to the normals estimated by some existing methods [8, 68], the normals estimated by the proposed method may produce point-based rendering results showing jagged feature lines (Figs. 13 and 17), especially for sparse point clouds.  A possible solution to smooth out these jagged feature lines is to reconstruct the original smooth feature lines using the evaluated feature coefficients.  In this chapter, the normal vector estimation serves as a pre-processing step for the outlier removal method in Section 6.3. In Section 6.3, a local coordinate system will be established on the neighborhood of each point using the estimated normals. Then a quadric surface will be fitted to locally approximate the scanned surface patch and evaluate whether a point belongs to the scanned surface as a good point or is far from the surface as an outlier.   6.3 Non-isolated Outlier Detection With the estimated normal vectors from the previous section, a local coordinate system can be established in the neighborhood of each point. This can facilitate the local surface fitting to detect non-isolated outliers using majority voting in this section. Detecting the non-isolated outlier clusters are challenging since these outliers are attached to the scanned surface and cannot be easily separated using simple distance criteria.  Some non-isolated outlier clusters can even form smooth patches just like good surface patches.  To address this issue, a majority-voting scheme is proposed to cut the connections between non-isolated outlier clusters and the scanned surface so that the non-isolated outlier clusters become isolated.  114  6.3.1 Regular Point Separation The outlier connection regions where non-isolated outlier clusters are attached to the scanned surface should be identified first.  Approximating local surface patches in such regions is generally unreliable due to the large shape variation caused by the attached non-isolated outlier clusters. In contrast, fitting surface on points in smooth surface regions with small shape variations is more trustworthy. Such points are referred to as regular points and can serve as references to estimate local surface geometry.  The regions where non-isolated outlier clusters connect to the scanned surface, referred to as outlier connection regions, generally have large shape variations and can be classified as irregular points.  Points in high-curvature regions and around sharp features are also irregular points.  To identify the irregular points, this work uses the surface variation [49] in Chapter 5 and evaluates the variation in each point’s k-nearest neighborhood using principal component analysis (PCA).  PCA obtains a minimal ellipsoid enclosing a point’s k -nearest neighborhood. Let 0 , 1  and 2  present the lengths of three semi-principal axes of the ellipsoid in 3D. Surface variation ( )n p  of a point p  is  00 1 2( )n      p        (6.7) where 0 1 2    . Surface variation can measure how closely a local neighborhood forms a smooth planar surface patch. The smaller the surface variation is, the more likely the local neighborhood forms a planar surface. Figure 6.10 illustrates the surface variations of a point’s neighborhood among various scenarios in 2D. Generally, a neighborhood in a smooth surface region with low curvature and low noise has small surface variation (Figure 6.10a), whereas high 115  curvature (Figure 6.10b), sharp feature (Figure 6.10c), high noise level (Figure 6.10d), sparse outliers (Figure 6.10e) and non-isolated outliers (Figure 6.10f) can cause large surface variations. A small surface variation indicates a point’s neighborhood is regular and has high fidelity to represent the scanned surface. Such a point is the regular point that can serve as a reference to reliably approximate local surface and facilitate outlier detection.   Figure 6.10 6XUIDFHYDULDWLRQVLQDSRLQW¶VQHLJKERUKRRGDPRQJYDULRXVVFHQDULRV: first row: low noise on surface with low curvature (a), high curvature (b) and sharp feature (c); Second row: smooth surface with high noise (d), sparse outliers (e) and non-isolated outliers (f).  Once the surface variation of each point is estimated, the histogram between point population and surface variation can be generated. Then, the bi-mean clustering technique [6] can be used to classify the histogram into regular points (Figure 6.10a) and irregular points (Figure 6.10b-f). Bi-means clustering is a case of K-means algorithm to cluster n   object into k  clusters by minimizing the intra-cluster variance: (a) (b) (c) (d) (e) (f) 116  21min ( )j ikj ii x Sx           (6.8) where k  is the number of clusters and i  is the mean of i th cluster ( j ix S ). The relevant parameters such as initial means are selected according to [6].   This approach would classify points in high-curvature regions, sharp features, and the outlier connection regions as irregular points and points with low surface variations as regular points, which will then serve as references to remove outliers in the outlier connection regions. Take a slice of the scanned point cloud from a gear tooth in Figure 1.1 as an example, Figure 6.11a shows the colored surface variation of each point.  Points with large variations are classified as irregular points in Figure 6.11b.  The irregular points include outliers in the outlier connection regions (red box) as well as good surface points with high curvatures.  The outliers should be removed without affecting the good surface points.  It should be noted in Figure 6.11a that not all regular points are part of the scanned surface.  A portion of the non-isolated outlier cluster in the Figure actually forms a planar patch and is also classified as regular points.  In other words, for the outlier connection region in Figure 6.11a, its adjacent regular points include both good surface points and outliers.  A majority voting scheme is proposed to deal with this ambiguous situation.   117    Figure 6.11 A slice of scanned point cloud from a gear tooth: (a) surface variation plot; (b) regular points (blue) and irregular points (red); and (c) removal of non-isolated outliers in the connection region.  The effectiveness of the regular point separation is essential to the success of the following majority voting scheme. Figure 6.12 illustrates the surface variation and regular point separation results on some representative point clouds. The raw point cloud scanned from a Gear model (Figure 6.12a) contains sharp features, noise and all kinds of outliers. As shown in Figure 6.12d, points around sharp feature and outlier connection regions are classified as irregular points (red) as desired. Notice the outlier connection region (red box in Figure 6.12d) is where the non-isolated outlier cluster attaches to the scanned surface. Some outliers in the non-isolated outlier cluster can form a smooth patch and are classified as regular points (blue). For a point in the outlier connection region, its neighboring regular points (blue) can be good points from the scanned surfaces and outliers from the non-isolated outlier cluster. These regular points will serve as references in majority voting to detect and remove outliers in the outlier connection regions.   Regarding noise, for the Sheep model in Figure 6.12b, it contains surfaces with various curvatures, yet does not contain sharp features. The points in high curvature regions are classified as irregular (a) (b) (c) 118  points (Figure 6.12d). Gaussian noise is superimposed on the Sheep model along random directions. The standard deviation of the noise, referred to as the noise level, is specified as a percentage of the diagonal length of the bounding box of the point cloud. In Figure 6.12c, the high curvature regions can still be classified as irregular points with 0.5% noise, while some low curvature regions also become irregular points due to large noise. This is acceptable for majority voting as long as the neighboring regular points are sufficient. As the noise level increases, the irregular regions will grow and propagate, and eventually make the majority voting unreliable due to the lack of regular points. Increasing the neighborhood size k  can compensate the noise to a certain level at the expense of increased computational time.   Figure 6.12 Regular point detection results: first row: surface variation for gear model with sharp feature (a), sheep model with high curvature (b) and 0.5% noise (c); Second row: regular points (blue) and irregular points (red) for each model. (a) (b) (c) (d) (e) (f) 119   6.3.2 Majority Voting Majority voting is a group decision-making scheme and has been found to be just as effective as other more complex schemes [71].  While widely used in pattern recognition and image analysis, majority voting has also been applied to 3D shape recognition [72, 73] and urban scene classification [74, 75].  For an input sample, each classifier or voter produces a unique decision regarding the identity of the sample.  Then, the identity is assigned according to what the majority of voters agree.  It has been validated that the combined group decision is superior to that of individual voters, provided that all the voters have reasonable competence with high probability to make the correct decision.  In the context of outlier detection, the input samples are the irregular points and the identity of each irregular point is either a good point or an outlier.  The regular points are deemed trustworthy and thus served as voters to make decisions on the irregular points.  For each irregular point p , only the neighboring regular points are selected as voters whereas regular points farther away from p  are ignored.  Each voter makes a decision by evaluating how well the irregular point follows the local surface geometry of the voter.  If the majority of neighboring regular points vote p  as an outlier, p  will be set as an outlier.  The advantage of this simple majority voting scheme is that, even some neighboring regular points of p  are in fact outliers and falsely vote p  as a good point, a correct decision can still be made as long as the majority of voters vote correctly.  120  The majority voting procedure is illustrated in Figure 6.13 using the point data inside the red box of Figure 6.12b.  For an arbitrary irregular point p , its neighborhood Q  encloses k-nearest regular points as voters.  Then, for each neighboring regular point iq , a local surface patch is fitted by the moving least-squares method [7, 32, 33, 63] on the local coordinate system of iq .  The local geometry at iq  can be treated as a height field over its tangent plane.  The normal of this tangent plane has been estimated using the proposed normal estimation algorithm in Section 6.2. A local bivariate polynomial can then be fitted to the spherical neighborhood R  of iq , where the radius is the distance between iq  and p .  Note that some neighboring regular points in Q  are outliers.  A simple least-squares fitting of points in R  will thus be biased towards the outliers.  To address this issue, a robust quadric surface fitting using iteratively reweighted least squares (IRLSs) [76] is adopted to penalize points with large fitted residuals (likely outliers) by assigning negligible weights and iteratively refine the surface fitting result.    To fit a parabolic quadric surface at p , a local coordinate system should be constructed first. Here the normal vector estimated in Section 6.2 can serve as the local Z-axis and the other axes are the eigenvectors of covariance matrix C  in Equation 6.3 with normal weight term. With the local frame at p , its neighbors can then be transformed into this frame. The local surface geometry around p  can be viewed as a height field over its tangent plane. The quadric surface is modeled as: ( ) Tf  x β x           (6.9) 121  where  , , , , ,a b c d e fβ  is the coefficient vector and 2 2, , , , ,1x xy y x y   x is the quadric basis vector. To compensate noise and surface discontinuities, we adopt iteratively re-weighted least squares (IRLSs) to minimize the sum of weighted residuals along the local z-axis as the following form: 2argmin ( ) ( ) ( )d i x i i iiw w f z  x x x      (6.10) where 2 2( ) exp( / 2 )d i dw   x x x and 2 2( ) exp( ( ) / 2 )i i xw f z   x x are Gaussian weight functions to penalize neighbors far from the point of interest and those with large fitting residuals. The bandwidths d , x  and other relevant parameters are selected according to [76].   In Figure 6.13a, the outlier cluster forms a branch from the scanned object surface and should be pruned.  This raises the question whether the fitted surface is a good approximate of the object surface (green) or the branch (red dashed).  It is assumed that non-isolated outliers, as they often do not follow the scanned object surface geometry, are simply attached to the scanned surface while the scanned surface varies more smoothly.  Since the iteratively reweighted least-squares fitting is good at approximating the low curvature-varying surface geometry, the green surface patch should be the fitted result as desired. 122      Figure 6.13 Majority voting: (a) regular point iq  as a voter for p ; and (b) majority in  Q  voting p  as an outlier.  After fitting the quadric surface at iq , iq  will vote p  as a good point or an outlier based on whether p  falls within a set distance threshold from the fitted surface.  For all the regular points in R , the standard deviation r  of the fitted residuals is calculated.  Since these regular points follow the local surface geometry better than the irregular points, r  represents a good estimate of the local scanning noise level without much interference from the potential outliers.  So, if the pQRQuadratic CurvenZ-offsetiqp8 voters vote p as outlier9 voters vote p as outlier10 voters vote p as good pointiq jqkq(a) (b) Quadric Surface Fitted Residual 123  fitted residual at p  is less than rs , where s  a scalar, p  is considered as following the local surface geometry at iq  well.  Otherwise, iq  votes p  as an outlier.  A small s  is clearly aggressive and would treat noisy points as outliers.  This will remove many good points in the connection region.  A large s  is tolerant and would not make a clear cut between the non-isolated outliers and the scanned surface.  It has been found from extensive tests that 2s   generally yields satisfactory results.  It should be noted that the quadric surface fitting requires at least 6 points.  So, if R  contains less than 6 neighboring points when iq  and p  are very close, iq  would simply vote p  as a good point due to the close proximity.  Regarding the tip points of sharp features, they correspond to shape discontinuity where two or more surface patches meet. If the fitted surface of each patch cannot extrapolate the tip points well, their fitting residuals may be larger than the residuals of adjacent regular points. In this case, if large noise are present around such tip points and cause large standard deviation r , then the residuals of tip points are not significant and they can be preserved as good points. Otherwise, some tip points may be treated as outliers and removed. Again, a tradeoff of s  is needed to leverage these scenarios.   The above procedure is to be conducted by each regular point in Q  and this allows each regular point to vote independently. Figure 6.13b illustrates the voting result for p .  It can be seen that although 10 regular points in the outlier cluster vote p  as a good point, the majority of the voters vote p  as an outlier.  Thus, p  is set as an outlier.  If p  is a point closer to the center of the outlier cluster, the outliers will dominate the neighborhood Q  and p  will be set as a good point.  This is 124  in fact acceptable since the objective of the voting is simply to cut the connection of the non-isolated outlier cluster from the scanned surface and thus make it an isolated outlier cluster, which will then be removed in the subsequent step.  If p  is a good point in the connection region, its neighboring points from the scanned object surface will dominate the neighborhood Q  and p  will be retained.  The pseudo code of the majority voting procedure is shown in Algorithm 6.1.  Typical implementation results are shown in Figure 6.11c where the outliers in the connection region (red box) have been reliably removed so that the non-isolated outlier cluster becomes an isolated one.  For the irregular regions with high curvatures (purple and green boxes), the voting procedure works well without any interference from the non-isolated outliers.  Sharp feature points are all preserved well.             125  Algorithm 6.1. Non-isolated Outlier Detection Using Majority Voting IR  all irregular points for each p IR  do     Q  the k-nearest regular points of p       for each i q Q  do         R  the neighboring point set of iq  within distance of ip q          Fit a quadric surface on R  using IRLS         Get mean r  and r  of the fitted residuals for all regular points in R          if fitted residual of p 2 rr    then              , 1iV q p , iq  voting p  as an outlier         end if     end for     if sum of  ,iV q p  size of Q /2         p  is an outlier     else         p  is a good point     end if end for Remove all outliers in IR   126  The Q  neighborhood selection directly affects the overall performance of the outlier removal in the connection region.  The surface variation of a point varies with the point’s k -nearest neighborhood [49].  A small k  is unable to classify sufficient outliers in connection regions as irregular points.  On the contrary, a large k  leads to large regions of irregular points.  Then, the closest regular points may be too far from the local geometry of the irregular points and this will aggressively remove irregular points as outliers.  Good points in high-curvature regions may thus be mistakenly removed.  As a compromise and from extensive tests, this work has adopted 40k   for surface variation estimation.  Each irregular point then uses its k -nearest regular points as voters in the majority voting procedure.  The majority voting procedure presented above is robust because a few wrong votes will generally not alter the correct result, even when the voters include outliers.  In contrast, the method by Shen et al. [6] propagates surface patches from regular points, which would potentially include outliers.  Figure 6.14 shows the comparison of the outlier removal results for the Gear point cloud.  The proposed method is seen to effectively remove the connections between the non-isolated outliers and the scanned surface even when points in some outlier clusters are deemed regular points.  Meanwhile, the good irregular points around sharp features remain almost untouched.  127            (a)                         (b)   Figure 6.14 Non-isolated outlier removal: (a) Shen et al.; and (b) the proposed method.  6.4 Isolated Outlier Removal 6.4.1 Segmentation After cutting the connections between the non-isolated outliers and the scanned surface, the point cloud would only contain isolated outlier clusters and sparse outliers.  Such a point cloud can be easily segmented through a region growing process [17].  Starting from an arbitrary point as the seed for the initial region, it grows by enclosing adjacent points according to a pre-defined Euclidean distance threshold.  Then, for each new point added to the region, its adjacent points within the threshold will be enclosed as well until no further points can be added.  After forming one region, the same procedure is repeated until all the points have been visited.  The point cloud is thus segmented into many clusters. 128   The distance threshold can be set according to the particular scanning setup parameters such as point spacing [17].  If such information is unavailable, the threshold can also be set adaptively according to the overall point spacing distribution.  For points within a cluster, the local point spacing is expected to be much smaller than that for points between clusters.  Thus, the threshold has been set empirically as 2d  , where d  is the average and   the standard deviation of the point spacing in the point cloud [15].  According to the various scanning tests carried out in this work, this threshold setting has been demonstrated to be able to segment the scanned point cloud into many clusters and each cluster contains good points or outliers only.  For surface regions with low point density, these regions are likely to be segmented into many small clusters.  This is a minor issue as the low-point-density surface regions will still be preserved by a subsequent data processing step.  Sparse outliers become small clusters as well and will be removed.  As shown in Figure 6.15a, a point cloud scanned from a digital camera has been segmented into many clusters.  It should be noted that the spike-shaped outlier clusters around the camera lens (red box) are actually non-isolated.  These non-isolated outlier clusters have become isolated after applying the majority voting procedure.  Without cutting the outlier connections, these outliers are mixed into good point clusters.  6.4.2 Outlier Cluster Removal After segmentation, the outlier clusters are to be removed.  A straightforward way [17] is to simply treat small clusters as outliers using a cluster size threshold.  However, this criterion may mistakenly remove good small clusters from surface regions with low point density.  As shown in Figure 6.15b, the number of scanned points for each camera button is not large and these scanned 129  points form small clusters.  A moderate cluster size threshold will falsely remove these good clusters.  Meanwhile, some large outlier clusters remain undetected within the red box in Figure 6.15b.  An aggressive strategy is to keep the largest cluster only, which will definitely remove good clusters, as indicated in Figure 6.15c.  To address these issues, a novel expandable boundary criterion has been proposed to remove outlier clusters more reliably while preserving good clusters (Figure 6.15d).    Figure 6.15 A scanned point cloud from a digital camera after majority voting: (a) segmentation; (b) small cluster removal; (c) largest cluster only; and (d) isolated outlier removal.  In an ideal scanning situation, an object surface should be sufficiently sampled and form only one good cluster.  Due to factors such as surface reflectivity variation, color variation, detailed (a) (b) (c) (d) 130  geometric features and occlusion due to concave geometry, the scanned point cloud often contains sparse points or holes in some surface regions, leading to many segmented patches instead of one ideal patch.  Since these good clusters are still part of the scanned surface, they can be joined together by expanding the patch boundary of each cluster.  On the contrary, outlier clusters would form ghost surface patches that are not part of the scanned surface geometry and thus in general unable to join with good clusters through expanding boundaries.  Instead, they would intersect the good clusters when expanding their boundaries.  This indicates that the surface patch boundary can be used to distinguish between good clusters and outlier clusters.  Given a point cluster, its boundary points can be identified by the largest open angle of a point’s neighborhood [9].  Instead of using a global angle threshold, an adaptive boundary estimation approach is adopted in this work.  A point is considered to be a boundary point if the largest open angle of its neighborhood is consistent when the neighborhood is expanded.  More specifically, for an arbitrary point p  in a cluster, its initial small neighborhood of points, composed of typically 8-nearest neighboring points in the same cluster [66], are projected onto the tangent plane at p  to obtain the largest open angle   as shown in Figure 6.16a.  Then, the neighboring points of each point in this initial neighborhood are added to expand the neighborhood and another largest open angle   is obtained (Figure 6.16b).  Given the sides PA, PB of   and PC, PD of  , if PC is within / 4  of PA and PD is within / 4  of PB, the largest open angle   for the expanded neighborhood is considered to be consistent with respect to the largest open angle   for the initial neighborhood.  Whenever this condition is met, p  is deemed as a boundary point.  The neighborhood only needs to be expanded once according to our numerous test results.  As for a 131  small cluster with less than 6 points, it is considered as insufficient to represent a surface patch and thus no boundary is to be formed.    Figure 6.16 Boundary point estimation: (a) initial largest open angle  ; and (b) largest open angle   after expanding the neighborhood.  As described previously, good clusters can be connected by expanding their boundaries whereas outlier clusters do not have this property.  Starting from a good cluster representing part of a scanned surface, other clusters can join this good cluster by checking boundaries.  The first assumption is that the largest cluster is a good cluster if the point cloud is scanned from a single object.  Given a good cluster G  and a candidate cluster C , each boundary point ic  in C  can get its closest point jg  in G .  If jg  is also a boundary point in G , ,i j c g  is a boundary-to-boundary pair from C  to G .  If m  stands for the number of boundary-to-boundary pairs and n  the total number of boundary points in C , ( , )r m nC G  is the boundary-to-boundary ratio from C  to G .  If ( , )r C G  is larger than an empirical threshold of 0.25 (from our extensive tests), C  is α α/4 A B A, C BDppα/4 α/4 α/4 β (a) (b) 132  considered to be able to connect to G  through the expanded boundary.  Otherwise, C  is taken as an outlier cluster.  The detailed procedure is listed in the Algorithm 6.2 below. Algorithm 6.2. Outlier Cluster Detection via the Expandable Boundary Criterion Identify boundary points for each cluster Good cluster group GG  the largest cluster Candidate clusters CC  the remaining clusters Sort CC  from closest to farthest by the minimum distance to GG  for each candidate cluster C CC  do        for each good cluster G GG  do               Get boundary-to-boundary ratio ( , )r C G                if ( , ) 0.25r C G  then                      move C  to GG                       break               end if        end for end for Keep GG  and remove CC   Figure 6.17 illustrates the presented outlier cluster removal procedure on a scanned point cloud of a camera.  In Figure 6.17b, the points around the digit “4” on the camera casing (purple box) and a button (green box) are separated from the main camera surface due to low point density.  These point clusters are able to join the main camera surface by expanding their boundaries.  In contrast, 133  the spike-shaped outlier cluster (red box) cannot join but can only intersect with the main camera surface.  Thus, it is removed as an outlier cluster (Figure 6.17c).  The sparse outliers are also removed in a similar manner.  Compared with the cluster size threshold criterion, which indiscriminately removes all small good clusters, the presented expandable boundary criterion is able to detect outlier clusters and preserve good small features much more reliably    Figure 6.17 Scanned point cloud of a camera: (a) segmented point clusters; (b) identified boundary points; and (c) outlier clusters removed.  6.5 Implementation Results and Discussion This section demonstrates the effectiveness of the proposed outlier detection method in processing real point cloud data sets collected by a high-precision LDI Surveyor laser scanning system or a low-cost Microsoft Kinect sensor.  To be consistent with practical applications, the scans were done without spray coating the scanned object.  To evaluate the outlier removal results, the accepted method of qualitative comparisons [6] was adopted to visually inspect a processed point cloud data set after outlier removal against the original raw scanned point cloud.  (a) (b) (c) 134  6.5.1 Comparison with Existing Methods When scanning the Gear object, which had many sharp features and was shiny around the teeth and inner ring, the raw scanned point cloud contained many sparse outliers, isolated outlier clusters and non-isolated outlier clusters.  Moreover, some outlier clusters formed planar surface patches.  The method by Weyrich et al. [13] using plane fitting, miniball, and nearest-neighbor reciprocity (PMR), the method by Shen et al. [6] using surface propagation (SP), and the method by Teutsch et al. [17] using region growing (RG), were respectively used to detect each type of outliers for comparison purposes.  The involved parameter values in these existing studies were manually adjusted to attain the best possible results while the proposed method in this paper used fixed parameter values as indicated in previous sections of this paper.  Figure 6.18 shows the comparison of the outlier detection results.  The PMR method is only able to detect sparse outliers and fails to remove outlier clusters.  The SP method iteratively propagates a surface from smooth regions and will mistakenly enclose non-isolated outliers when such outliers form smooth patches.  The RG method segments the point cloud into many regions and can remove isolated outlier clusters as well as sparse outliers.  Unfortunately, it fails in the presence of non-isolated outlier clusters.  These three existing methods have also been combined and applied in sequence for a superior result as shown in Figure 6.18e.  Nonetheless, as long as non-isolated outlier clusters exist, even the combined approach will end up with some non-isolated outlier clusters mingled with good scanned points.  In comparison, the proposed method using majority voting is able to effectively cut the connections between non-isolated outlier clusters and good surface points, even when the non-isolated clusters form smooth patches.  These outliers are thus well separated from the good points and the good point clusters are preserved well using the expandable boundary criterion.  The 135  resulting point cloud shown in Figure 6.18f does not contain noticeable outliers and good scanned points are almost untouched.            Figure 6.18 Outlier removal for the Gear scanned point cloud: (a) raw data; (b) PMR; (c) SP; (d) RG; (e) combined; and (f) proposed. ori pmr nonrg combine Vot rg final(a)  (b)  (c)  (d)  (e)  (f)  136   A raw point cloud scanned from the Digital Camera object with shiny surfaces and geometrically complex features was also tested.  As shown in Figure 6.19a, the raw point cloud contains some sparsely distributed good points (green box) due to fine features like buttons as well as extensive non-isolated outlier clusters like spikes around the lens region (red box).  Since these spikes are located inside a concave surface, it is hard to manually select and remove them without affecting the nearby good points.  Moreover, some of the spike-shaped outlier clusters are non-isolated and form planar patches with similar point density as that of nearby good points.  The existing surface propagation method is likely to propagate from these smooth outlier patches.  As a result, the processed point cloud using all the three existing methods combined, even only keeping the largest cluster, still contains non-isolated outlier clusters (red box in Figure 6.19b).  In contrast, the proposed method effectively removes these non-isolated outlier clusters via the majority voting scheme and well preserves the small good clusters via the expandable boundary criterion (Figure 6.19c).    137    Figure 6.19 Outlier removal for the Digital Camera scanned point cloud: (a) raw data; (b) combined; and (c) proposed.  For a raw point cloud collected from the Ball-End Cutter object (Figure 6.20), extensive outliers can be found around the cutting edges at the cutter tip due to their complex geometry and some outliers around the cutter cylindrical shank due to undesirable specular reflections.  The proposed method still outperforms all the three existing methods combined.  The proposed method was also tested on a Room point cloud captured from a room by a Microsoft Kinect sensor (Figure 6.21).  Since the room wall is relatively far from the Kinect sensor, the measured points are very noisy and contain many outliers.  The proposed method is seen to be able to remove these outliers and preserve desired features quite satisfactorily.  c(a)  (b)  (c)  138    Figure 6.20 Outlier removal for the Ball-End Cutter scanned point cloud: (a) photo; (b) raw data; (c) combined; and (d) proposed.    Figure 6.21 Outlier removal for the Room point cloud: (a) original data; and (b) outliers near the room wall removed. (a) (b) (c) (d) (a)  (b)  139   The proposed method is a more comprehensive outlier removal method than the existing methods as it locally detects non-isolated outlier clusters and globally removes isolated sparse outliers and outlier clusters.  The processed point cloud data after outlier removal can then be used for many subsequent applications such as quality inspection and surface reconstruction.  For the surface reconstruction application, a robust implicit moving least-squares method is adopted to locally approximate the scanned surface and to preserve sharp features [7].  The required input normal vectors are estimated using the method in Section 6.2.  Figure 6.22 shows the reconstructed surfaces of the outlier-removed point clouds using the combined method (Figure 6.18e) and the proposed method (Figure 6.18f), respectively.  The undetected non-isolated outlier clusters in Figure 6.18e lead to ghost surface patches in the reconstructed surface (Figure 6.22a), whereas the reconstructed surface benefits from the proposed method and a clean surface is obtained (Figure 6.22b).    Figure 6.22 Reconstructed surfaces from the outlier-removed Gear point clouds from; (a) the combined method; and (b) the proposed method.  (a)  (b)  140  6.5.2 Computational Time The proposed algorithm can partially run in parallel since most steps, such as principal component analysis, surface fitting and boundary estimation, can be conducted on each point’s local neighborhood independently. Regarding the computational time, the proposed method was implemented on a standard PC with Intel Core i5 at 3.30 GHz and 2GB RAM.  Table 6.2 lists the sizes of the various test data sets and their corresponding computational time.  It should be noted that a larger data set does not necessarily lead to longer computational time.  The computational time for the majority voting depends on the number of irregular points to be voted whereas the computational time for the isolated outlier removal is related to the number of segmented point clusters.  Data Set No. of Points Time(s) Gear 280,185 63 Digital Camera 148,482 53 Ball-End Cutter 191,502 28 Room 968,520 282 Elbow Pipe Joint 127,919 31  Table 6.2 Computational time of the majority voting method for various test data.  6.5.3 Discussions It is worthy to compare the propose majority voting method with the rotating scan method in Chapter 5. The former detects outliers through surface fitting from a geometrical perspective, while the later relied on the view-dependency property of outliers. The former does not require specific scanning setup and scanning information. Thus it is more flexible and generally applicable to process point clouds scanned from difference types of scanning devices. In terms of effectiveness, 141  the point cloud in Figure 5.9 is processed using the proposed majority voting method. As illustrated in Figure 6.23, the proposed majority voting method demonstrates much better capability in preserving the points around the hole (red circle) by the quadric surface fitting, whereas the rotating scan method falsely detect these view-dependent points as outliers due to the light occlusion. Regarding computational efficiency, the processing time of the majority voting method is much longer than the rotating scan method. This is because the iterative quadric surface fitting is more computationally expensive than the local estimation of overlap ratio, point spacing and surface variation for the rotating scan method.      Figure 6.23 Outlier removal results for a point cloud (a) using rotating scan method (b) and majority voting method (c).  As for the limitations, the proposed majority voting method builds on the premise that sufficient regular voters exist to detect the irregular points in the majority voting process.  If such regular points are sparse or insufficient, the majority voting process will not work properly.  For the scanned point cloud from the Elbow Pipe Joint object (Figure 6.24), the threads were not sufficiently sampled.  Although the result of the proposed method was still seen to be in general superior to that of the combined method, the majority voting process could not successfully detect all the non-isolated outlier clusters due to lack of neighboring regular points (circled in red in Figure 6.24d).  Also, some good point clusters (circled in green in Figure 6.24d) were mistakenly (a)  (b)  (c)  142  removed since the boundary points could not be reliably detected, again due to insufficient data points.    Figure 6.24 Outlier removal for the Elbow Pipe Joint scanned point cloud: (a) photo; (b) raw data; (c) combined; and (d) proposed.  The majority voting scheme is sensitive the point distribution by its nature. The points with high density will have a strong influence on the majority voting result. To be more specific, for a point in an outlier connection region with large point density variation, the non-isolated outlier neighbors may be denser than the surface neighbors in a rare scenario. The majority voting will be biased to favor non-isolated outliers. Therefore, the input point cloud is required to be relatively uniform (a)  (b)  (c)  (d)  143  with low density variation. This can be achieved by setting point spacing parameters in the scanning setting or fast uniform resampling algorithms such as voxel grid filter [77] as a pre-processing step. In the case such processing is inapplicable, resampling neighbors by discretizing the neighborhood ball of a point [68] can also be used to alleviate the effect of density variation.   Regarding the proposed expandable boundary criterion, it has been demonstrated to be practically more effective than cluster size threshold by testing on various scanned point clouds. Singularity cases do exist, such as outliers appear around a main surface boundary due to boundary occlusion as shown in the green circle in Figure 6.21b. However, according to numerous tests, the singularity cases for the proposed criterion happen much less often than the ones for cluster size criterion from a practical perspective. Considering the rarity of existing methods to extract good clusters, the proposed criterion is still an improvement in comparison with cluster size threshold. Since single criterion may not be able to handle all situations, it may be feasible to combine the expandable boundary criterion, cluster size threshold and other potential criteria in a weighted manner to achieve an overall satisfactory result. Exploring this idea is among the future work.  6.6 Summary A robust method has been presented in this paper to effectively detect all types of outliers in a scanned point cloud.  This method is generally applicable to scanned point clouds without additional scanning setup information. The main feature of the developed method is the majority voting scheme to effectively remove the connections between non-isolated outlier clusters and the scanned object surface even when these outlier clusters form planar patches. The resulting point cloud then only contains isolated outlier clusters and sparse outliers, which can be segmented into 144  clusters. Instead of applying a cluster size threshold to indiscriminately remove all small clusters regardless outliers or good points, an expandable boundary criterion is proposed to more reliably detect and remove the isolated outliers and preserve good points. The proposed outlier removal approach benefits from the proposed robust normal estimation method. This method can reliably estimate normal around sharp features in the presence of noise and outliers. The effectiveness of the normal estimation and outlier removal methods have been demonstrated through comparison with various existing methods.  145  Chapter 7: Conclusions and Future Research Directions 7.1 Conclusions Despite the popularity and wide applications of 3D scanners, the raw scanned point clouds are often contaminated by outliers due to various factors, such as surface reflectivity, sensor over-exposure, shape variation, boundary occlusion, etc., and thus are not directly applicable to many applications. When scanning reflective surfaces, outliers become much more extensive due to the undesirable specular reflections. Thus the raw data highly rely on an outlier detection process to obtain clean point clouds in order to ensure the quality of many point cloud applications. Considering the commonness of reflective surfaces in mechanical parts, it is critical to investigate the outlier formation mechanism in the scanning process and develop methods to effectively remove outliers. However, research on how outliers are formed in scanning reflective surfaces is rare. Moreover, existing outlier removal methods show limited effectiveness in detecting extensive outliers, especially when scanning reflective surfaces.  This thesis investigates the formation of outliers in scanning reflective surfaces using laser scanners, and develop two outlier removal methods to effectively and efficiently detect outliers in the raw scanned point clouds. In particular, two outlier formation models, mixed reflections and multi-path reflections, are proposed and verified through experiments. The effects of scanning orientation on the outlier formation have also been experimentally investigated. Based on the experimental results, a general guidance of proper scan path planning is provided in order to reduce the occurrence of outliers. Once outliers are significantly reduced in the scanning step, less effort will be required for outlier removal in the data processing. Regarding outlier removal, a rotating scan method has been proposed to efficiently remove view-dependent outliers. A more flexible 146  and effective method is also presented to detect outliers using majority voting. Meanwhile, a robust normal estimation algorithm is developed to reliably estimate normal vectors around sharp features.   In summary, the main contributions of this thesis are: 1. Two outlier formation models have been proposed to characterize the outlier formation in scanning reflective surfaces using laser scanners. One is mixed reflection model around edge features and the other is multi-path reflection model around concave geometries. Both models cause false stripes in sensors’ images due to undesirable specular reflections. The proposed models serve as the fundamental mechanism of outlier formation and have been verified through experiments.  2. Based on the two outlier formation models, the effects of scanning orientation, which defines the relative orientation between a scanned surface and the laser probe, on the outlier formation have been experimentally investigated. It has been found that the outlier extensity and outlier occurrence regions are directly affected by the scanning orientation a surface is scanned from. As been demonstrated, a proper scanning orientation can significantly reduce the outliers and also control where outliers occur. A general guidance on proper scan path planning is provided in order to suppress outlier occurrence.  3. From the effects of scanning orientation, it has been observed that the outlier occurrence regions vary with the changes of scanning orientations, whereas good surface points are usually visible to almost all scanning views and are view-independent. A novel outlier removal method using rotating scans has been developed to detect such view-dependent 147  outliers. Although requiring specific rotating scan setup, this method is computationally efficient and demonstrates better results in comparison with various existing methods.  4. A flexible and effective outlier removal method is proposed to detect the challenging non-isolated outliers, as well as isolated outliers and sparse ones without the necessity of the scanning process information. This method benefits from a reliable normal vector estimation to construct local coordinate systems. A normal estimation algorithm is developed to accurately estimate normal vectors around sharp features in the presence of outliers and noise. Once a local coordinate system is established for each point, a quadric surface can be fitted to reliably approximate the local surface. The proposed outlier removal method utilizes a majority voting scheme to effectively cut the connections between non-isolated outlier clusters and the main surface so the resultant isolated outliers can be detected using an expandable boundary criterion. The superior results of the proposed outlier removal approach have been demonstrated in comparison with various existing methods.   This thesis presents the fundamental models of how outliers are formed in scanning reflective surfaces using laser scanners and develops effective and efficient methods to remove outliers in order to obtain clean point clouds.   7.2 Future Research Directions There are several worthwhile future research topics: 1. Image filter: from the two outlier formation models in Chapter 3, outliers are recorded when there are false stripes in sensors’ images due to undesirable specular reflections. It is 148  highly desirable to improve the image filters to detect such false stripes so that the outliers can be reduced from the source by the scanning system.  2. Scan path planning: as mention in Chapter 4, the investigation of scanning orientation on outlier formation provides a general guideline of proper scan path planning manually. In the application of quality inspection, when the reference CAD model is available, it is of great potential to automatically generate a scan path with the constraints of proper scanning orientations so that the resultant scanned point cloud contains minimal outliers. Such an approach can be also be used to generate the rotating scan paths automatically for the outlier removal method in Chapter 5.  3. Computational efficiency: although being flexible and effective, the proposed outlier removal method using majority voting in Chapter 6 is still computationally expensive, especially for the iterative quadric surface fitting. It is desirable to investigate certain optimization approaches to boost its efficiency.  4. Sharp feature detection: the feature coefficient of the normal vector estimation approach in Section 6.2 can estimate sharp feature points as by-products. Such feature point information can be further utilized in applications such as sharp feature line detection and sharp feature recovery.  5. Point cloud denoising: the consistent neighborhood established by the three weight functions in Section 6.2 can increase the reliability of the local surface approximation around sharp feature and benefit the point cloud denoising.   The ultimate goal is to process a raw point cloud to generate an outlier-free, low-noise, accurate point cloud with high quality so that the subsequent applications can perform well.  149  References  [1] Blais F. Review of 20 years of range sensor development. Journal of Electronic Imaging 2004;13(1):231-43. [2] Soucy M, Laurendeau D, Poussart D, Auclair F. Behaviour of the center of gravity of a reflected gaussian laser spot near a surface reflectance discontinuity. Industrial Metrology 1990;1(3):261-74. [3] Curless B, Levoy M. Better optical triangulation through spacetime analysis. In:  Proceedings of the Fifth International Conference on Computer Vision. 1995. p. 987. [4] Hodge V, Austin J. A survey of outlier detection methodologies. Artificial Intelligence Review 2004;22(2):85-126. [5] Sotoodeh S. Outlier detection in laser scanner point clouds. In: International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences. 2006. p. 297-302. [6] Shen J, Yoon D, Shehu D, Chang SY. Spectral moving removal of non-isolated surface outlier clusters. Computer-Aided Design 2009;41(4):256-67. [7] Öztireli AC, Guennebaud G, Gross M. Feature preserving point set surfaces based on non-linear kernel regression. Computer Graphics Forum 2009;28(2):493-501. [8] Li B, Schnabel R, Klein R, Cheng ZQ, Dang G, Jin SY. Robust normal estimation for point clouds with sharp features. Computers & Graphics 2010;34(2):94-106. [9] Gumhold S, Wang X, MacLeod R. Feature extraction from point clouds. In:  Proceedings of 10th International Meshing Roundtable. 2001. p. 293-305. [10] Pauly M, Keiser R, Kobbelt LP, Gross M. Shape modeling with point-sampled geometry. ACM Transactions on Graphics 2003;22(3):641-50. [11] Trucco E, Fisher RB, Fitzgibbon AW. Direct calibration and data consistency in 3-D laser scanning. In:  Proceedings of the Conference on British Machine Vision. 1994. p. 489-98. [12] Chen J, Yang D, Zhou H, Buckley S. Avoiding spurious reflections from shiny surfaces on a 3D real-time machine vision inspection system. In: Proceedings of Instrumentation and Measurement Technology Conference. 1998. p. 364-8. [13] Weyrich T, Pauly M, Keiser R, Heinzle S, Scandella S, Gross M. Post-processing of scanned 3D surface data. In:  Symposium on Point-based Graphics. 2004. p. 85-94. 150  [14] Godin G, Rioux M, Beraldin JA, Levoy M, Cournoyer L, Blais F. An assessment of laser range measurement of marble surfaces. In: Proceedings of the Fifth Conference on Optical 3D Measurement Techniques. 2001. p. 49-56. [15] Rusu RB, Marton ZC, Blodow N, Dolha M, Beetz M. Towards 3D point cloud based object maps for household environments. Robotics and Autonomous Systems 2008;56(11):927-41. [16] Wang J, Xu K, Liu L, Cao J, Liu S, Yu Z, Gu XD. Consolidation of low-quality point clouds from outdoor Scenes. Computer Graphics Forum 2013;32(5):207-16. [17] Teutsch C, Trostmann E, Berndt D. A parallel point cloud clustering algorithm for subset segmentation and outlier detection. In: Proceedings of SPIE 8085, Videometrics, Range Imaging, and Applications XI, 808509. 2011. [18] Sotoodeh S. Hierarchical clustered outlier detection in laser scanner point clouds. In:  International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences. 2007. p. 383-8. [19] Buzinski M, Levine A, Stevenson WH. Performance characteristics of range sensors utilizing optical triangulation. In: Proceedings of the IEEE National Aerospace and Electronics Conference. 1992. p. 1230-6. [20] Dorsch RG, Häusler G, Herrmann JM. Laser triangulation: fundamental uncertainty in distance measurement. Applied Optics 1994;33(7):1306-14. [21] Blais F, Taylor J, Cournoyer L, Picard M, Borgeat L, Dicaire LG, Rioux M, Beraldin JA, Godin G, Lahnanier C, Aitken G. Ultra-high resolution imaging at 50µm using a portable XYZ-RGB color laser scanner. International  Workshop  on  Recording,  Modeling  and  Visualization  of  Cultural  Heritage 2005. [22] Guidi G, Remondino F, Russo M, Spinetti A. Range sensors on marble surfaces: quantitative evaluation of artifacts. In: Proceedings of SPIE 7447, Videometrics, Range Imaging, and Applications X, 744703. 2009. [23] Feng H-Y, Liu Y, Xi F. Analysis of digitizing errors of a laser scanning system. Precision Engineering 2001;25(3):185-91. [24] Abbasinejad F, Kil YJ, Sharf A, Amenta N. Rotating scans for systematic error removal. In:  Proceedings of the Symposium on Geometry Processing. 2009. p. 1319-26. [25] Xi F, Liu Y, Feng HY. Error compensation for three-dimensional line laser scanning data. International Journal of Advanced Manufacturing Technology 2001;18(3):211-6. [26] Isheil A, Gonnet JP, Joannic D, Fontaine JF. Systematic error correction of a 3D laser scanning measurement device. Optics and Lasers in Engineering 2011;49(1):16-24. 151  [27] Smith KB, Zheng YF. Accuracy analysis of point laser triangulation probes using simulation. Journal of Manufacturing Science and Engineering 1998;120(4):736-45. [28] Harris JO, Spence AD. Geometric and quasi-static thermal error compensation for a laser digitizer equipped coordinate measuring machine. International Journal of Machine Tools and Manufacture 2004;44(1):65-77. [29] Cuesta E, Rico JC, Fernández P, Blanco D, Valiño G. Influence of roughness on surface scanning by means of a laser stripe system. International Journal of Advanced Manufacturing Technology 2009;43(11-12):1157-66. [30] Papadimitriou S, Kitagawa H, Gibbons PB, Faloutsos C. Loci: Fast outlier detection using the local correlation integral. In: Proceedings of the 19th International Conference on Data Engineering. 2003. p. 315-26. [31] Köhler J, Nöll T, Reis G, Stricker D. Robust outlier removal from point clouds acquired with structured light. In: Proceedings of Eurographics. 2012. p. 21-4. [32] Alexa M, Behr J, Cohen-Or D, Fleishman S, Levin D, Silva CT. Point set surfaces. In: Proceedings of the IEEE Conference on Visualization. 2001. p. 21-8. [33] Fleishman S, Cohen-Or D, Silva CT. Robust moving least-squares fitting with sharp features. ACM Transactions on Graphics 2005;24(3):544-52. [34] Taubin G. A signal processing approach to fair surface design. In: Proceedings of ACM SIGGRAPH 95. 1995. p. 351-8. [35] Clarenz U, Diewald U, Rumpf M. Anisotropic geometric diffusion in surface processing. In: Proceedings of the IEEE Conference on Visualization. 2000. p. 397-405. [36] Lange C, Polthier K. Anisotropic smoothing of point sets. Computer Aided Geometric Design 2005;22(7):680-92. [37] Fleishman S, Drori I, Cohen-Or D. Bilateral mesh denoising. ACM Transactions on Graphics 2003;22(3):950-3. [38] Jones TR, Durand F, Desbrun M. Non-iterative, feature-preserving mesh smoothing. ACM Transactions on Graphics 2003;22(3):943-9. [39] Desbrun M, Meyer M, Schrder P, Barr A. Anisotropic feature-preserving denoising of height fields and bivariate data. In: Proceedings of Graphics Interface. 2000. p. 145-52. [40] Schall O, Belyaev A, Seidel HP. Adaptive feature-preserving non-local denoising of static and time-varying range data. Computer-Aided Design 2008;40(6):701-7. [41] Yoon M, Ivrissimtzis I, Lee S. Variational Bayesian noise estimation of point sets. Computers & Graphics 2009;33(3):226-34. 152  [42] Schall O, Belyaev A, Seidel HP. Robust filtering of noisy scattered point data. In: Proceedings of the Symposium on Point-based Graphics. 2005. p. 71-7. [43] Chung HS, Jia J. Efficient photometric stereo on glossy surfaces with wide specular lobes. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2008. p. 1-8. [44] Forest J, Salvi J, Cabruja E, Pous C. Laser stripe peak detector for 3D scanners. a FIR filter approach. In:  Proceedings of 17th International Conference on Pattern Recognition. 2004. p. 646-9. [45] Nayar SK, Ikeuchi K, Kanade T. Surface reflection: physical and geometrical perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence 1991;13(7):611-34. [46] Besl PJ, McKay ND. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence 1992;14(2):239-56. [47] Mahmud M, Joannic D, Roy M, Isheil A, Fontaine J-F. 3D part inspection path planning of a laser scanner with control on the uncertainty. Computer-Aided Design 2011;43(4):345-55. [48] Lee KH, Park H-p. Automated inspection planning of free-form shape parts by laser scanning. Robotics and Computer-Integrated Manufacturing 2000;16(4):201-10. [49] Pauly M, Keiser R, Gross M. Multi-scale feature extraction on point-sampled surfaces. Computer Graphics Forum 2003;22(3):281-9. [50] Kolluri R. Provably good moving least squares. ACM Transactions on Algorithms 2008;4(2):1-25. [51] Alexa M, Behr J, Cohen-Or D, Fleishman S, Levin D, Silva CT. Point set surfaces. In: Proceedings of the IEEE Conference on Visualization. 2001. p. 21-8. [52] Alexa M, Behr J, Cohen-Or D, Fleishman S, Levin D, Silva CT. Computing and rendering point set surfaces. IEEE Transactions on Visualization and Computer Graphics 2003;9(1):3-15. [53] Yang M, Lee E. Segmentation of measured point data using a parametric quadric surface approximation. Computer-Aided Design 1999;31(7):449-57. [54] Pauly M, Gross M, Kobbelt LP. Efficient simplification of point-sampled surfaces. In: Proceedings of the IEEE Conference on Visualization. 2002. p. 163-70. [55] Song H, Feng HY. A global clustering approach to point cloud simplification with a specified data reduction ratio. Computer-Aided Design 2008;40(3):281-92. 153  [56] Demarsin K, Vanderstraeten D, Volodine T, Roose D. Detection of closed sharp edges in point clouds using normal estimation and graph theory. Computer-Aided Design 2007;39(4):276-83. [57] OuYang D, Feng HY. On the normal vector estimation for point cloud data from smooth surfaces. Computer-Aided Design 2005;37(10):1071-9. [58] Hoppe H, Derose T, Duchamp T, Mcdonald J, Stuetzle W. Surface reconstruction from unorganized points. In: Proceedings of SIGGRAPH’92. 1992. p. 71-8. [59] Guennebaud G, Gross M. Algebraic point set surfaces. ACM Transactions on Graphics 2007;26(3): Article No. 23. [60] Klasing K, Althoff D, Wollherr D, Buss M. Comparison of surface normal estimation methods for range sensing applications. In: Proceedings of the IEEE International Conference on Robotics and Automation. 2009. p. 1977-82. [61] Jones TR, Durand F, Zwicker M. Normal improvement for point rendering. IEEE Computer Graphics and Applications 2004;24(4):53-6. [62] Levin D, Mesh-independent surface interpolation. In: Geometric Modeling for Scientific Visualization. Springer-Verlag. 2003. p. 37-49. [63] Liu Y, Qian X. Computing point set surfaces with controlled spatial variation of residuals. Computer-Aided Design 2011;43(8):957-70. [64] Yang P, Qian X. Direct computing of surface curvatures for point-set surfaces. In:  Proceedings of the Eurographics Symposium on Point-based Graphics. 2007. p. 29-36. [65] Scheidegger CE, Fleishman S, Silva CT. Triangulating point set surfaces with bounded error. In: Proceedings of the Third Eurographics Symposium on Geometry Processing. 2005. Article #63. [66] Mederos B, Velho L, de Figueiredo LH. Robust smoothing of noisy point clouds. In: Proceedings of SIAM Conference on Geometric Design and Computing. 2003. [67] Huber PJ, Robust statistics. Wiley; 2005. [68] Boulch A, Marlet R. Fast and robust normal estimation for point clouds with sharp features. Computer Graphics Forum 2012;31(5):1765-74. [69] Wang Y, Feng H-Y, Delorme F-É, Engin S. An adaptive normal estimation method for scanned point clouds with sharp features. Computer-Aided Design 2013;45(11):1333-48. [70] Mitra NJ, Nguyen A, Guibas L. Estimating surface normals in noisy point cloud data. International Journal of Computational Geometry & Applications 2004;14(4-5):261-76. 154  [71] Lam L, Suen SY. Application of majority voting to pattern recognition: An analysis of its behavior and performance. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans 1997;27(5):553-68. [72] Zhou Y, Liu K, Barner E. Non-rigid 3D shape recognition via dictionary learning. In: Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. 2013. Paper #6. [73] Spreeuwers L. Fast and accurate 3D face recognition. International Journal of Computer Vision 2011;93(3):389-414. [74] Salah M, Trinder J, Shaker A, Hamed M, Elsagheer A. Integrating multiple classifiers with fuzzy majority voting for improved land cover classification. In:  International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences. 2010. p. 7-12. [75] Posner I, Schroeter D, Newman P. Online generation of scene descriptions in urban environments. Robotics and Autonomous Systems 2008;56(11):901-14. [76] Fan H, Yu Y, Peng Q. Robust feature-preserving mesh denoising based on consistent subneighborhoods. IEEE Transactions on Visualization and Computer Graphics 2010;16(2):312-24. [77] Rusu RB, Cousins S. 3D is here: Point Cloud Library (PCL). In: Proceedings of the IEEE International Conference on Robotics and Automation. 2011. p. 1-4. [78] Nordhausen K. The elements of statistical learning: data mining, inference, and prediction, second edition by T. Hastie, R. Tibshirani, J. Friedman. International Statistical Review 2009. [79] Lanczos C, Applied analysis, Prentice Hall; 1956. 155  Appendices  Appendix A  Feature Coefficient Estimation Given a point cloud, feature coefficient Fcoe estimates whether an arbitrary point is a sharp feature point, non-sharp feature point, or a point in the transition regions in-between. It is essentially similar to sharp feature point detection. This work proposes a normal clustering approach based on Gauss map clustering to estimate feature coefficient.   In general, a Gauss map directly maps the normals of a surface in the Euclidean space onto a unit sphere. Figure A.1 shows Gauss maps for three typical point neighborhoods on the Fandisk model surface. Such clustering results are to be utilized to quantify the feature coefficient at each point.  Ideally, when moving a point of interest gradually from a smooth region towards a sharp edge, the normals within its neighborhood will initially be in one cluster and then changed into two clusters.  The ratio of the size of the smaller cluster to that of the bigger (primary) cluster gradually increases from 0 to 1, with 1 meaning that the point is exactly on the sharp edge.  A primary cluster is defined as: primary cluster: cluster size number of neighbors number of clusters  The feature coefficient, Fcoe , for a specific point is then evaluated as: 220 1min ,1 11 1lii non primary  clusterlii primary  clusternumber of clusters= Fcoe s number of primary clusters=          number of primary clusters>          (A.1) 156  where l  is the local point spacing of a point.  When there is only one primary cluster, the ratio between the number of points in non-primary clusters and the primary one can measure how close the neighborhood of a point is to a sharp feature. However, such an estimate is biased towards densely sampled surface side when the points around a sharp feature are not uniformly distributed. Since scanned point clouds are often characterized with non-uniform point density, the local point spacing of each neighbor is also introduced in Equation A.1 so that the sparse points are not downplayed. The ratio formulated in Equation A.1 for a sharp edge point is seldom to be exactly 1.  A rounding factor s is employed to indicate the proximity to a sharp feature.  The factor s is set as 2 in this work based on a large number of test cases.  This means that a point with a ratio value above 0.5 is considered as a sharp feature point.  In summary, the evaluated Fcoe  is to be used as follows: the neighborhood of a point is deemed to be in a smooth region if 0Fcoe  , in a transition region if 0 1Fcoe  , or on a sharp feature if 1Fcoe  . 157   Figure A.1 Typical Gauss map clustering of normals on the Fandisk model surface.  To reliably evaluate the feature coefficient of a point, the normals of its neighbors must be correctly clustered.  In this work, the hierarchical agglomerative clustering method is employed [78].  The elements to be clustered are the initially estimated normals by Equation 6.2 with small bandwidths in favor to sharp features. As the normals are mapped to points in the unit Gauss sphere, the angle between two normal vectors in , jn is the geodesic distance d  between two points ix  and jx  in the sphere.  ( , ) arccos( , )i j i jd   x x n n       (A.2)  Corner Smooth region Edge 158  The distance describes the similarity of two normals. To cluster the points in the Gauss sphere, the hierarchical agglomerative clustering method treats each point as a distinct cluster in the beginning and then gradually merges the two closest clusters into one larger cluster until the distance between any two clusters are larger than a specified threshold. To define the distance between two clusters, also known as linkage criterion, the commonly-used average distance D  shows the best performance in the presence of noise.   1( , ) ,a A b BD A B d a bA B          (A.3) The common challenge of this clustering method is how to find the proper angle threshold to produce reliable clustering results.  A small angle threshold can correctly classify the neighbors of a point around a sharp feature into distinct clusters while it may falsely generate more than one cluster for a point in a smooth region.  Inversely, a relatively large angle threshold can form one cluster for a point in a smooth region but falsely merge all the normals across a sharp feature into one cluster as well.  As a result, it is proposed in this work to automatically determine the proper angle threshold by exploiting the varying trend of the sharp feature point percentage with respect to the angle threshold.  Let the angle threshold start from zero and increase with small increments.  For each threshold, the feature coefficient at every point is calculated based on the corresponding clustering results from Equation A.1.  The percentage of sharp feature points in the point cloud is then readily available, which always decreases with increased angle threshold.  The decreasing rate of the sharp feature points is to be used to determine the proper threshold.  Fiure A.2 shows the variation of the sharp feature point percentage with the angle threshold for the Fandisk, Rolling-Stage and Bunny 159  model.  Initially, the percentage is at 100% because a zero threshold makes every neighbor a distinct cluster, which implies that every point is a sharp feature point.  When the angle threshold reaches 180°, the percentage becomes zero since all neighbors would form one single cluster.  In other words, all points in the point cloud are initially regarded as sharp feature points and then gradually transformed into non-sharp feature points with increasing angle threshold.    Figure A.2 Sharp feature point percentages (top) and their second derivatives (bottom) with respect to the angle threshold for: (a) Fandisk; (b) Rolling-Stage; and (c) Bunny.  For the Fandisk and Rolling-Stage models with various sharp feature sizes, points in smooth regions are the first to change their feature coefficients and points around sharp features then Angle Threshold (deg.) Sharp Feature Points (%) Second Derivative  Smooth  Regions Sharp Features Smooth  Regions Sharp Features Smooth  Regions (a) (b) (c) 160  follow.  The reason is that normal vector variation for a neighborhood of points in smooth regions is generally much smaller than that for neighborhood points across sharp features.  As a result, the sharp feature point percentage would decrease rapidly in the beginning until points in smooth regions have mostly been changed to non-sharp feature points.  The sharp feature point percentage then becomes stable since most points on sharp features would remain unchanged.  It should be noted that when the angle threshold becomes larger than the normal variation around a sharp feature, for example, a small dihedral angle between two surface patches in a sharp edge, the sharp feature point percentage will again drop rapidly.  Then the percentage may become stable again before reaching another larger dihedral angle and then drop again. More than one stabilized regions may occur according to the various dihedral angles among sharp features. The first stable region can separate smooth points (on the left) and sharp feature points (on the right) well. To determine this stable zone, the second derivative of the sharp feature percentage is calculated using low-noise Lanczos differentiator [79]. In Figure A.2a and A.2b, the first zero point (inflection point) from positive to negative (red dot) of the second derivative curve is taken as the angle threshold in this work.  With the automatically determined angle threshold, normal clustering for every point in a given point cloud can be done.  The feature coefficient can then be calculated from the clustering results.  For the very complex corner of the Icosahedron model with 0.5% imposed noise, reliable clustering result can still be achieved (Figure A.3). The Bunny model (Figure A.2c) contains curved smooth surface with various non-sharp feature sizes. The gradually changed curvatures make the feature percentage curve decrease smoothly without clearly stable regions and sudden drops after. The inflection point does not show in the second derivative curve. Therefore, the point cloud is considered to be smooth without noticeable sharp features. Figure A.4 shows the feature coefficients are well estimated for several models with noise and outliers. With the estimated 161  feature coefficients, the bandwidths of the three weight functions in Section 6.2 can be determined to estimate normal vectors. The feature coefficient results can also be used to detect sharp feature lines and other applications.    Figure A.3 Normal clustering result for a corner point neighborhood (Icosahedron model with 0.5% imposed noise)   Figure A.4 Feature coefficient estimation results for models with 0.5% noise and 0.3% outliers. 1.0 0.0 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0167059/manifest

Comment

Related Items