A review of recent range image registration methods with accuracy evaluation <s> Iterative closest point (ICP) <s> 1. Introduction. 2. Simple Regression. 3. Multiple Regression. 4. The Special Case of One-Dimensional Location. 5. Algorithms. 6. Outlier Diagnostics. 7. Related Statistical Techniques. References. Table of Data Sets. Index. <s> BIB001 </s> A review of recent range image registration methods with accuracy evaluation <s> Iterative closest point (ICP) <s> The authors describe a general-purpose, representation-independent method for the accurate and computationally efficient registration of 3-D shapes including free-form curves and surfaces. The method handles the full six degrees of freedom and is based on the iterative closest point (ICP) algorithm, which requires only a procedure to find the closest point on a geometric entity to a given point. The ICP algorithm always converges monotonically to the nearest local minimum of a mean-square distance metric, and the rate of convergence is rapid during the first few iterations. Therefore, given an adequate set of initial rotations and translations for a particular class of objects with a certain level of 'shape complexity', one can globally minimize the mean-square distance metric over all six degrees of freedom by testing each initial registration. One important application of this method is to register sensed data from unfixtured rigid objects with an ideal geometric model, prior to shape inspection. Experimental results show the capabilities of the registration algorithm on point sets, curves, and surfaces. > <s> BIB002 </s> A review of recent range image registration methods with accuracy evaluation <s> Iterative closest point (ICP) <s> Abstract We describe RICP, a robust algorithm for registering and finding correspondences in sets of 3-D points with significant percentages of missing data, and therefore useful for both motion analysis and reverse engineering. RICP exploits LMedS robust estimation to withstand the effect of outliers. Our extensive experimental comparison of RICP with ICP shows RICP's superior robustness and reliability. <s> BIB003 </s> A review of recent range image registration methods with accuracy evaluation <s> Iterative closest point (ICP) <s> Investigates the use of Euclidean invariant features in a generalization of iterative closest point (ICP) registration of range images. Pointwise correspondences are chosen as the closest point with respect to a weighted linear combination of positional and feature distances. It is shown that, under ideal noise-free conditions, correspondences formed using this distance function are correct more often than correspondences formed using the positional distance alone. In addition, monotonic convergence to at least a local minimum is shown to hold for this method. When noise is present, a method that automatically sets the optimal relative contribution of features and positions is described. This method trades off the error in feature values due to noise against the error in positions due to misalignment. Experimental results suggest that using invariant features decreases the probability of being trapped in a local minimum and may be an effective solution for difficult range image registration problems where the scene is very small compared to the model. <s> BIB004 </s> A review of recent range image registration methods with accuracy evaluation <s> Iterative closest point (ICP) <s> A novel solution is presented to the Nearest Neighbor Problem that is specifically tailored for determining correspondences within the Iterative Closest Point Algorithm. The reference point set P is preprocessed by calculating for each point p/spl I.oarr//sub i//spl isin/P that neighborhood of points which lie within a certain distance /spl epsiv/ of p/spl I.oarr//sub i/. The points within each /spl epsiv/-neighborhood are sorted by increasing distance to their respective p/spl I.oarr//sub i/. At runtime, the correspondences are tracked across iterations, and the previous correspondence is used as an estimate of the current correspondence. If the estimate satifies a constraint, called the Spherical Constraint, then the nearest neighbor falls within the /spl epsiv/-neighborhood of the estimate. A novel theorem, the Ordering Theorem, is presented which allows the Triangle Inequality to efficiently prune points from the sorted /spl epsiv/-neighborhood from further consideration. The method has been implemented and is demonstrated to be more efficient than both the k-d tree and Elias methods. After /spl sim/40 iterations, fewer than 2 distance calculations were required on average per correspondence, which is close to the theoretical minimum of 1. Furthermore, after 20 iterations the time expense per iteration was demonstrated to be negligibly more than simply looping through the points. <s> BIB005 </s> A review of recent range image registration methods with accuracy evaluation <s> Iterative closest point (ICP) <s> Registration of range images requires the identification of common portions of surfaces between which a distance minimization is performed. This paper proposes a framework for the use of dense attributes of range image elements as a matching constraint in the registration. These attributes are chosen to be invariant to rigid transformations, so that their value is similar in different views of the same surface portion. Attributes can be derived from the geometry information in the range image, such as surface curvature, or be obtained from associated intensity measurements. The method is based on the Iterative Closest Compatible Point algorithm augmented with a random sampling scheme that uses the distribution of attributes as a guide for point selection. Distance minimization is performed only between pairs of points considered compatible on the basis of their attributes. The performance of the method is illustrated on a rotationally symmetric object with color patterns. <s> BIB006 </s> A review of recent range image registration methods with accuracy evaluation <s> Iterative closest point (ICP) <s> The iterative closest point (ICP) algorithm is widely used for the registration of geometric data. One of its main drawbacks is its quadratic time complexity O(N/sup 2/) with the shape number of points N, which implies long processing time, especially when using high resolution data. This paper proposes to accelerate the process by a coarse to fine multiresolution approach in which a solution at a coarse level is successively improved at a finer level of representation. Specifically, it investigates this multiresolution ICP approach when coupled with the tree search or the neighbor search closest point algorithms. A theoretical and practical analysis and a comparison of the considered algorithms are presented. Confirming the success of the multiresolution scheme, the results also show that this combination permits us to create a very fast ICP algorithm, gaining speed up to a factor of 27 over a standard fast ICP algorithm. <s> BIB007 </s> A review of recent range image registration methods with accuracy evaluation <s> Iterative closest point (ICP) <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> BIB008
The ICP method was presented by Besl and McKay BIB002 . The goal of this method is to obtain an accurate solution by minimizing the distance between point-correspondences, known as closest point. When an initial estimation is known, all the points are transformed to a reference system applying the Euclidean motion. Then, every point in the first image (p i ) is taken into consideration to search for its closest point in the second image (m i ), so that the distance between these correspondences is minimized, and the process is iterated until convergence (see Eq. (18)). In order to minimize the previous equation, a symmetric 4 · 4 matrix QðR pm Þ is defined as follows, where tr is the trace, T is the transpose of D, I 3 is the identity matrix and R pm is the cross-covariance matrix of the points P and M given by: The unit eigenvector q ! R ¼ ½q 0 q 1 q 2 q 3 t corresponding to the maximum eigenvalue of the matrix Q is selected as the optimal rotation expressed in quaternions. Once R is computed (see Eq. (21)), the translation vector can be easily computed (see Eq. (22)) and the motion determined by R and t.  The motion is applied to the first surface and the process is repeated until distances between corresponding points decrease below a threshold. ICP obtains good results even in the presence of Gaussian noise. However, the main drawback is that the method can not cope with non-overlapping regions because the outliers are never removed. Moreover, when starting from a rough estimation of the motion, the convergence is not guaranteed. Some modifications of ICP have been presented in recent years. In 2001, Greenspan and Godin BIB005 applied the Nearest Neighbor Problem to facilitate the search of closest points. The first range image is considered as a reference set of points, which is preprocessed in order to find, for every point, the neighborhood of points in the second view located at a certain distance. The points of the neighborhood are sorted according to that distance. The use of this pretreatment leads to consider the closest point of the previous iteration as an estimation of the correspondence in the current iteration. If this estimation satisfies the spherical constraint, the current closest point is considered to belong to the neighborhood of the estimate. A property of the spherical constraint holds that any point that is closer to q ! (a point in the second range image) than the current estimate p c ! (the closest point obtained in the last iteration) must be located inside a sphere centered at p c ! with a radius of 2k q ! À p c ! k. This pretreatment decreases the computing time drastically. A year later, Jost and Hugli BIB007 presented the Multi-resolution Scheme ICP algorithm, which is a modification of ICP for fast registration. The main idea of the algorithm is to solve the first few iterations using down sampled points and to progressively increase the resolution by increasing the number of points considered. The author divides the number of points by a factor in each resolution step. The number of iterations in each resolution step is not fixed, so that the algorithm goes to the next resolution when the distance between correspondences falls below a threshold. In the same year, Sharp et al. BIB004 proposed the ICP using invariant features ICPIF. In this case, points are matched using a weighted feature distance as follows, BIB006 presented a similar work, where color and curvature were used as feature information. As color is used as a matching constraint, symmetric objects can be well registered. However the author only presents results with simple objects without shadows, occlusions or luminance changes. In addition, other authors proposed some improvements to increase the robustness of ICP. For instance, Trucco et al. BIB003 implemented the RICP method making use of the Least Median of Squares approach. The method is based on executing the registration with just a sample of random points (m points), computing this operation a sufficient number of times with the aim of finding a registration without outliers. The Monte Carlo algorithm was used to estimate the number of executions. Once all the potential registrations were computed, the one that minimizes the median of the residuals is chosen as the solution. Finally, the correspondences with a residual larger than 2.5r were removed and the transformation between both views was computed using only the remaining points (inliers). Note that r was estimated by using a robust standard deviation BIB001 . Moreover, Zinsser et al. BIB008 proposed a robust method based on outlier thresholding known as the Picky ICP algorithm. The main difference with respects to the previous methods is that at every iteration only the pairs of correspondences with the smallest distances are used in the motion computation. The threshold was fixed at a given multiple of the standard deviation. Overall, ICP is the most common registration method used and the results provided by authors are very good. However, this method usually presents problems of convergence, lots of iterations are required, and in some cases the algorithm converges to a local minimum. Moreover, unless a robust implementation is used, the algorithm only can be used in surface-to-model registration.