Registration Of Point Clouds Basing On Sample-Sphere And ICP Algorithm

Registration of point clouds is one of the most important problems in3D reconstruc-tion. Since it is the first step of the whole process, the precision of registration determinesthe quality of the reconstruction. This thesis focuses on rigid pair-wise registration. Threetechniques are proposed to solve the problems and to improve the existing methods. Therationality and efectiveness of these techniques are supported by a large number of ex-periments and comparisons. The contributions are as follows:1. A sample-sphere method is proposed to roughly align point clouds. Assuming thatP and Q are two point clouds, P is fixed, while Q is going to be aligned to P. ARANSAC framework is employed by sample-sphere method. First, three points areselected randomly from P as a base, and then all the triplets of points, which canbe overlapping with the base under rigid transformation, are abstracted from Q. Agroup of transforming parameters can be computed based on the triplets and thebase. Comparing with other methods of rough alignment, sample-sphere methodhas two advantages. First, it owns lower complexity. For a given base, sample-sphere method is able to find all the potential triplets of points in O(knQlog nQ)time, where k is a constant that only depends on a tolerance to the rotation error,and nQis the number of points in Q. While the complexity of the fastest roughaligning method in my survey is O(n_~2) Second, it is much more robust when theinput data have noise and outliers.2. A normal-based approach is proposed to accelerate the original sample-spheremethod. By simplifying the model of sample-sphere and checking normal consis-tence, this approach reduces the number of operations of counting approximatelyoverlapping points, and therefore efectively speeds up the aligning process. Acommon problem of feature-based methods is that they are sensitive to the noise,but this approach is much more robust. Because that how much this approachdepends on the normals is able to be adjusted automatically according to the seri-ousness of noise.3. An adaptive distance restriction is proposed to improve ICP algorithm. The adap-tive distance restriction has the ability to exclude irrational corresponding pointpairs. The improved ICP algorithm has two phases. In the first phase, the distance restriction is updated automatically according to the convergence degree of the it-eration, thus the irrational corresponding point pairs can be excluded gradually. Inthis phase, the speed of convergence is considered as the main problem first, whileat the end of this phase, the precision becomes the main problem. In the secondphase, the distance restriction is fixed, and a least-square error is used to controlthe precision of the registration results. With the adaptive distance restriction, theICP algorithm is able to precisely align point clouds which are only partially over-lapping.