A review of recent range image registration methods with accuracy evaluation <s> Experimental results <s> We present a multiview registration method for aligning range data. We first align scans pairwise with each other and use the pairwise alignments as constraints that the multiview step enforces while evenly diffusing the pairwise registration errors. This approach is especially suitable for registering large data sets, since using constraints from pairwise alignments does not require loading the entire data set into memory to perform the alignment. The alignment method is efficient, and it is less likely to get stuck into a local minimum than previous methods, and can be used in conjunction with any pairwise method based on aligning overlapping surface sections. <s> BIB001 </s> A review of recent range image registration methods with accuracy evaluation <s> Experimental results <s> We propose a method to construct a 3-D geometric shape model by registering and integrating multiple range images under a unified framework. We use 3-D points around the object surface as the correspondence key, because the closest data point from an arbitrary 3-D point should be matched if the data are registered correctly with some exceptional cases. We assume that the input shapes are roughly registered in advance, and then we solve the problem by iterative loops that consist of establishing correspondence by searching closest data points, integration of corresponded data points, and registration of each data to the integrated shape. The error function is defined by the weighted variances of the signed distance field from the surface. The weighting values are determined to trim out wrong correspondences typically caused by different sampling and measurement error. We do not need to consider the cumulative pairwise registration error because each data is registered to the integrated shape. The integrated shape information is directly used to generate a surface model. We tested the method on synthetic and real range images. <s> BIB002 </s> A review of recent range image registration methods with accuracy evaluation <s> Experimental results <s> Robust registration of two 3-D point sets is a common problem in computer vision. The iterative closest point (ICP) algorithm is undoubtedly the most popular algorithm for solving this kind of problem. In this paper, we present the Picky ICP algorithm, which has been created by merging several extensions of the standard ICP algorithm, thus improving its robustness and computation time. Using pure 3-D point sets as input data, we do not consider additional information like point color or neighborhood relations. In addition to the standard ICP algorithm and the Picky ICP algorithm proposed in this paper, a robust algorithm due to Masuda and Yokoya and the RICP algorithm by Trucco et al. are evaluated. We have experimentally determined the basin of convergence, robustness to noise and outliers, and computation time of these four ICP based algorithms. <s> BIB003 </s> A review of recent range image registration methods with accuracy evaluation <s> Experimental results <s> The registration of full 3-D models is an important task in computer vision. Range finders only reconstruct a partial view of the object. Many authors have proposed several techniques to register 3D surfaces from multiple views in which there are basically two aspects to consider. First, poor registration in which some sort of correspondences are established. Second, accurate registration in order to obtain a better solution. A survey of the most common techniques is presented and includes experimental results of some of them. <s> BIB004 </s> A review of recent range image registration methods with accuracy evaluation <s> Experimental results <s> This paper addresses the problem of large scale multiview registration of range images captured from unknown viewing directions. To reduce the computational burden, we decouple the local problem of pairwise registration on neighboring views from the global problem of distribution of accumulated errors. We define the global problem over the graph of neighboring views, and we show that this graph can be decomposed into a set of cycles such that the optimal transformation parameters for each cycle can be solved in closed form. We then describe an iterative procedure that can be used to integrate the solutions for the set of cycles across the graph. This method for error distribution does not require point correspondences between views, and therefore can be used together with robot odometry or any method of pairwise registration. Experimental results demonstrate the effectiveness of this technique on range images of an indoor facility. <s> BIB005
Although many authors evaluated the accuracy of their methods, very few provided a comparison between already published approaches   BIB004 . In order to provide such a useful comparison, some methods to evaluate the accuracy have been tested which allow us to decide the best method in every situation. The computing time has also been considered, which might be critical in some applications. The measures used to determine the accuracy are the following: rotation error, translation error and RMS (root mean square). In order to evaluate the accuracy in rotation, it is represented as a directional vector and a rotating angle around such a vector, which both can be easily extracted from any rotating matrix. Then, the estimated rotation is compared to a real one. So, the error is determined as the angle between both directional vectors (c) and the discrepancy between both angles of rotation (a-b). The translation error is defined as the distance between the origin of the coordinate system estimated by registration with respect to the real one, that is, the norm of the difference between both translation vectors. The RMS error is defined as the mean of the distances between point-correspondences considering all views in the same reference frame. In order to compare the main algorithms, synthetic data is used to evaluate the registration errors. First of all, synthetic test scenes are generated. Additionally more realistic synthetic data is used, and finally experiments with real data are realized. The first test scenes used are Wave and Fractal landscape (see Fig. 1 ). These surfaces have been used by other authors BIB003  to test their algorithms. These surfaces are contained in a range of 1 in X and Y-axis and approximately 0.5 in Zaxis. Although these scenes certainly do not cover all sort of scanned objects, they are quite representative of many real scannings. Several experiments are performed to evaluate the precision in front of different error sources, as shape measurement error (noise, surface sampling, etc.), and correspondence error (occlusion, outliers, etc.), among others. Although it is very difficult to distinguish these error sources, because they are usually related, these experiments are organized to show basically the effects of each source of error. As final results can change depending on the implementation of the algorithm, details of this implementation are briefly commented. Ransac-based approach is programmed using a subset of 5% of the points of the first view to search for correspondences using all the points in the second view. Moreover, as distances between primary, secondary and auxiliary points can not be exactly found, a variation of a 2% of such a distance is permitted. Furthermore, the distance between the 3 control points is limited to a 15% of the maximum distance to speed up the process. In the spin image algorithm, the number of correspondences searched is fixed to the 5% of the number of points, and 25% of points are used to compute the spin image. In the implementation of the genetic algorithm of Brunnström, only 5% points of one surface are searched in the second. In this situation, the second surface have all points, differing from the author that used only 50 points in every surface. However, it is still difficult to work with accuracy using such large number of points. In fine registration algorithms, a threshold of 0.00001 is fixed to guarantee convergence. However, a maximum number of iterations is fixed to 20 in all the algorithms, except in the case of Chow which number of iterations is fixed to 600 due to the fact that the method is based on genetic algorithms. In order to evaluate the effects of shape measurement error, two experiments have been done. First of all, Gaussian noise is independently added into the test scenes. Experiments are performed using different values of standard deviation error; the first with an error of 1% of the range dimension in each angle direction, and in the second one with 2% of standard deviation. In Coarse registration algorithm fractal surface and wave surface are subsampled to 512 points. The motion between both surfaces is a rotation of 45°in each angle and a displacement of 1 unity in each axis. The results obtained shown that the final result is not very influenced by the noise, because this noise is negligible with respects to the errors in coarse registration techniques. In order to test the fine registration algorithms, a sequence of surfaces of 2000 points are registered. Every surface is related to the previous by a rotation of 5°around every axis and a displacement of 0.2 unities in the Z-axis. This initial motion is similar to the pre-alignment used by Rusinkiewicz and Levoy  . The same percentage of noise is independently added in each surface. Results obtained in Fig. 2 shown that while the error obtained by Chen algorithm is directly related to the noise introduced, Besl and Chow have always a residual error not depending on the noise introduced. This error is usually consequence of the convergence to a local minima. As Chen approach solves better the problem of local minima, excellent results are obtained without noise. Fig. 1 . Test scenes used throughout this paper. Another case of misalignments is the surface sampling. Theoretically when surfaces are scanned with low resolution, worse results are obtained. As surfaces have less points, points correspondences are found with low precision. In order to test the effects, original surfaces are independently subsampled into different resolutions: (a) (12.5% and 25% of the initial size (2048 points) in coarse registration; and (b) 12.5% and 25% of the initial size (4096 points) in fine registration). As is shown in Fig. 3 , errors in Fine registration algorithms extremely depends on the sampling surface. While the variations in Trucco, Besl and Chow are not significative, in Chen and Zinsser algorithms, the errors using surfaces of 2000 points are approximately the half than using a subsampling of 500 points. Furthermore, in the case of low sampling (500 points), Zinsser and Chen algorithms presented the best solutions. As the Chen approach use a point-to-plane distance, the accuracy is better compared to point-to-point because the plane interpolation decrements the effects of the subsampling. Although Zinsser algorithms presents similar results in RMS errors, the rotation errors of Zinsser's are considerably larger compared to Chen's (see Table 2 ). The fact is that not always RMS errors are representative of a correct registration, especially in robust variant when correspondences related with large distances are removed, and only the correspondences with small distances remains. On the other hand, in most part of results obtained with Coarse Registration methods, sampling does not effect considerably the final results, and low resolution surfaces can be used in this situation. In this experiment only Ransacbased is clearly effected by the sampling. This is because it is difficult to find 3 points in both surfaces that corresponds exactly to the same position. Besides, PCA does not use directly the points to computed the motion, and spin image and the genetic algorithm use more points reducing the error in the motion estimation. However, experiments realized with more complex objects show that in this situation, results are more influenced by the sampling. In both experiments realized, 100% of overlapping area is used. However, in most part of real applications both surfaces contains non-overlapping regions. In these situations, false correspondences are very common, and they affect considerably the final resolution. In this experiment, several percentages (5%, 10%, 20% and 50% of the surface) of non-overlapping region are introduced. Results obtained shown that the presence of non-overlapping regions do not effect significantly coarse registration techniques. In general, coarse registration techniques only use a few part of points to obtain the motion, and, if these points are correctly selected, the result is similar to the one obtained without outliers. On the other hand, Principal Component Analysis obtained similar eigenvalues from the surfaces with or without non-overlapping regions because they are almost planar. In fine registration techniques, errors in Besl and Chow algorithms increase directly proportional to the percentage of non-overlapping region. This change is specially significant with 50% of outliers (see Fig. 4 ). On the other hand, Zinsser algorithm can cope with 5% and 10% of outliers, however, the accuracy decreases. Finally, Chen approach is robust to outliers. This is because point-correspondences are computed using the projection of points in a grid Z space, and points whose projection belongs to an empty cell are not considered. Most part of outliers are removed and motion is only computed using points belonging to both surfaces. Other experiments are realized using more realistic objects. Tables 3 and 4 show the experimental results obtained by using synthetic clouds of 3D points of Fig. 6 , taken from the database of RapidForm2004. Finally, real scanned objects are used to take into account the effects of the shape measurement error. Results are shown in Tables 5 and 6 . It can be shown in Fig. 5 that the executing time of Ransac algorithm is surprisingly smaller in the case of 500 points compared to the case of 250 points. This is because in the case of 250 points, the distance between three points is larger compare to the case of 500 and no good correspondences might be found without increasing the searching distance. Although the time required is very important, all the methods have been programmed using Matlab 6.5 in a Pentium IV 2,6 GHz because we are just interested in the comparison among the methods and Matlab guarantees an easy implementation. Furthermore kd-tree or other velocity improvements are not used in these experiments to easy again the comparison. The 3D clouds of points have been acquired using a Minolta Vivid 700 laser scanner, obtaining up to 8 views of a given object. The registration results obtained are shown in Fig. 10 . The real positions of the object are known and so the accuracy of the methods compared because the real objects have been scanned on a turnable table with a the precision of less than 1°. Several objects have been registered and we have observed that the shape of the object affects the accuracy of the registration considerably and independently of the registration method used. Overall, when the views have poor details, planarity or symmetry, the registration does not converge (see Fig. 9 ). Moreover, a robust method is essential to register real range images. See, for instance, Fig. 10a compared to the rest of registrations (b, c and d) in which the registrations are more accurate because only the points belonging to the overlapping region have been used in the computation. Although this paper is focused on pair-wise registration so that the interest is centered in the alignment of two views, the same algorithms may be used to register large surfaces. The topic of large surface registration is focused on the registration of several views among them with the aim of obtaining a complete model, but then we have to make additional considerations besides of just a change of resolution. First, information of vicinity is required to know which pairs of views contain enough overlapping area. Second, the drift or error propagation problem has to be considered to reduce the residual in the registration. With the aim of solving both difficulties, multi-view registration techniques appeared. Basically, these techniques register a set of views simultaneously and the drift is distributed between the views BIB002 BIB001 . However, classic multi-view algorithms are not the best option because in large surfaces there are lots of views without overlapping area. So, some authors proposed to build adjacent graphs to determine loops which are further register using a multi-view algorithm BIB005 . Fig. 11 shows the registration of a large object composed of 27 different views (see Fig. 12 ). The algorithm implemented is based on the graph of adjacencies which is built from consecutive pair-wise registration. Then, a multi-view algorithm is applied to minimize the drift of every loop in the graph Fig. 13 .