A review of recent range image registration methods with accuracy evaluation <s> Classification of registration methods <s> A popular approach for 3D registration of partially-overlapping range images is the ICP (iterative closest point) method and many of its variations. The major drawback of this type of iterative approaches is that they require a good initial estimate to guarantee that the correct solution can always be found. In this paper, we propose a new method, the RANSAC-based DARCES (data-aligned rigidity-constrained exhaustive search) method, which can solve the partially-overlapping 3D registration problem efficiently and reliably without any initial estimation. Another important characteristic of our method is that it requires no local features in the 3D data set. An extra characteristic is that, for the noiseless case, the basic algorithm of our DARCES method can guarantee that the solution it finds is the true one, due to its exhaustive-search nature. Even with the nature of exhaustive search, its time complexity can be shown to be relatively low. Experiments have demonstrated that our method is efficient and reliable for registering partially-overlapping range images. <s> BIB001 </s> A review of recent range image registration methods with accuracy evaluation <s> Classification of registration methods <s> We present a 3D shape-based object recognition system for simultaneous recognition of multiple objects in scenes containing clutter and occlusion. Recognition is based on matching surfaces by matching points using the spin image representation. The spin image is a data level shape descriptor that is used to match surfaces represented as surface meshes. We present a compression scheme for spin images that results in efficient multiple object recognition which we verify with results showing the simultaneous recognition of multiple objects from a library of 20 models. Furthermore, we demonstrate the robust performance of recognition in the presence of clutter and occlusion through analysis of recognition trials on 100 scenes. <s> BIB002 </s> A review of recent range image registration methods with accuracy evaluation <s> Classification of registration methods <s> Few systems capable of recognizing complex objects with free-form (sculptured) surfaces have been developed. The apparent lack of success is mainly due to the lack of a competent modelling scheme for representing such complex objects. In this paper, a new form of point representation for describing 3D free-form surfaces is proposed. This representation, which we call the point signature, serves to describe the structural neighbourhood of a point in a more complete manner than just using the 3D coordinates of the point. Being invariant to rotation and translation, the point signature can be used directly to hypothesize the correspondence to model points with similar signatures. Recognition is achieved by matching the signatures of data points representing the sensed surface to the signatures of data points representing the model surface. ::: ::: The use of point signatures is not restricted to the recognition of a single-object scene to a small library of models. Instead, it can be extended naturally to the recognition of scenes containing multiple partially-overlapping objects (which may also be juxtaposed with each other) against a large model library. No preliminary phase of segmenting the scene into the component objects is required. In searching for the appropriate candidate model, recognition need not proceed in a linear order which can become prohibitive for a large model library. For a given scene, signatures are extracted at arbitrarily spaced seed points. Each of these signatures is used to vote for models that contain points having similar signatures. Inappropriate models with low votes can be rejected while the remaining candidate models are ordered according to the votes they received. In this way, efficient verification of the hypothesized candidates can proceed by testing the most likely model first. Experiments using real data obtained from a range finder have shown fast recognition from a library of fifteen models whose complexities vary from that of simple piecewise quadric shapes to complicated face masks. Results from the recognition of both single-object and multiple-object scenes are presented. <s> BIB003
The goal of registration is to find the Euclidean motion between a set of range images of a given object taken from different positions in order to represent them all with respect to a reference frame. The proposed techniques differ as to whether initial information is required, so that a rough registration can only be estimated without an initial guess. If an estimated motion between views is available, a fine registration can then be computed. The classification of the surveyed methods is revealed in Table 1 . In coarse registration, the main goal is to compute an initial estimation of the rigid motion between two clouds of 3D points using correspondences between both surfaces, as explained in Section 3. These methods can be classified in terms of (a) the kind of correspondences used; (b) the method used to compute the motion; (c) the robustness of the method; (d) the registration strategy (see Table 1 ). In general, the most common correspondence method used is point-to-point, such as the Point Signature method (see Section 3.1) and the method of Spin Image (see Section 3.2). However, there are other methods that align lines, like methods of bitangent curves (see Section 3.6) and others that match the surfaces directly, like the algebraic surface model (see Section 3.5) . Another important aspect of coarse registration is the way of computing the motion when correspondences are found. Robustness in the presence of noise is another important property, because there are usually no corresponding regions between views. Most methods are robust, looking for the best combination of correspondences BIB003 BIB001 BIB002 . Other methods may converge to a local solution  , and in theory this increases the speed of the method but the solution is not always the best, and in some cases it is far from the right solution. In general, coarse registration methods are iterative, usually maximizing the rate of overlapping points. However, a few provides linear solutions, like the methods based on Principal Component Analysis or the Algebraic Surface model (see Sections 3.3 and 3.5, respectively). In fine registration, the goal is to obtain the most accurate solution as possible. These methods use an initial estimate of the motion to first represent all range images with respect to a reference system, and then refine the transformation matrix by minimizing the distances between temporal correspondences, known as closest points. Table 1 also classifies fine registration methods in terms of: (a) the registration strategy; (b) the use of an efficient search method, such as k-d trees in order to speed up the algorithm; (c) the way of computing the minimization distance, either pointto-point or point-to-plane; (d) the way of computing the motion in each iteration; (e) the robustness of the method. The registration strategy can differ according to whether all range views of the object are registered at the same time (multi-view registration) or the method registers only a pair of range images in every execution (pair-wise registration). Moreover, fine registration methods need a lot of processing time to decide which is the closest point. In order to deal with this problem, several proposals to increase the searching speed have been presented, such as the use of k-d trees to alleviate the problem of searching neighbors. Another important parameter is the distance to minimize. Most methods use the distance between point-correspondences, while others use the distance between a given point in the first range image and the corresponding tangent plane in the second. The problem of point-to-point distance is that the correspondence of a given point in the first view may not exist in the second view because of the limited number of points acquired by the sensor, especially on low resolution surfaces. To address this problem, some authors use the point-to-plane distance. In this case, a tangent plane in the second view is computed at the position pointed by the given point in the first view. The distance between the point in the first view and that tangent plane in the second is the minimization distance. Theoretically, point-to-plane converges in less iterations than point-to-point. Finally, robust methods can cope with noise and false correspondences due to the presence of non-overlapping regions. In real images, the robustness is very important, especially when only a small part of the first view has a correspondence in the second, that is in the presence of a reduced overlapping region.