Материал: [2.1] 3D Imaging, Analysis and Applications-Springer-Verlag London (2012)

Fig. 6.6 Distance formulation. Point-to-point distance (left) and point-to-plane distance (right)

Distance Formulation Another crucial factor affecting the speed of ICP is the point-to-point or point-to-plane distance used in the problem described by Eq. (6.1). Figure 6.6 shows a schema of the two kinds of distances: point-to-point computes the Euclidean distance between the data-point and model-point (left), point-to-plane distance computes the projection of the data-point onto the surface of the modelview, which is encoded in terms of piecewise planar patches (for instance a triangular mesh). In spite of an increased complexity of the distance formulation, the number of ICP iterations required to converge is reduced [65, 69]. Whether this results in a reduced registration time depends on the trade-off between the increased per-iteration time and the reduced number of iterations. Results regarding this aspect on example 3D scans are presented in Sect. 6.4.

Recently a new “distance formulation” has been proposed [66] where the model surface is implicitly represented as the zero-isosurface of a fitted radial basis function (RBF), s(x) = 0, for any 3D point x, where the function s represents distance- to-surface. For any point on the data scan (or on a pre-computed 3D grid), the distance and direction (gradient) to the zero isosurface can be computed directly from the RBF. The advantage of this RBF distance formulation is that it interpolates over holes that may exist in the model scan. Particularly for lower resolution scans, the interpolation is more accurate than the piecewise linear point-to-plane method. Both RBF model fitting and RBF model evaluation have a computational complexity of

O(n log n).

6.2.3.3 Techniques for Improving Accuracy

The accuracy of the alignment is the most critical aspect of the registration, since even a small misalignment between two views can affect the whole 3D model reconstruction procedure. The simplest strategy that can be used is outlier rejection. Other methods improve the accuracy by using additional information such as color and texture or local geometric properties. Finally, an effective class of methods devoted to the improvement of accuracy are probabilistic methods.

Outlier Rejection Closest point computation may yield spurious correspondences due to errors or to the presence of non-overlapping parts between the views. Typically, outlier rejection techniques threshold the residuals. The threshold can be fixed manually, or as a percentage of worst pairs (e.g., 10 % [71, 78]). Other techniques perform statistics on the residual vector and set the threshold as 2.5σ or apply the

so-called X84 rule [17, 40]. More recently, statistical analysis has been introduced into the general registration problem (Eq. (6.1)) by proposing a new error function named Fractional Root Mean Squared Distance [67].

Additional Information The basic ICP algorithm computes the correspondences by taking into account only the proximity of points. However, corresponding points should be similar with respect to other aspects. Several studies have attempted to exploit additional information available from the acquisition process or from the analysis of the surface properties. In practice, the distance formulation is modified to integrate this information, such as local surface properties [36], intensity derived from the sensor [36, 98], or color [72]. In [45] the authors proposed to use color and texture information. In [85] the so-called ICP using invariant features (ICPIF) was introduced where several geometric features are employed, namely curvatures, moments invariants and Spherical Harmonics Invariants. In [14] additional information was integrated in the point descriptors using the spin-image with color.

Probabilistic Methods In order to improve the robustness of the registration, several probabilistic version of the standard ICP have been proposed [38, 73, 74]. In [73, 74] the idea of multiple weighted matches justified by a probabilistic version of the matching problem is introduced. A new matching model is proposed based on Gaussian weights (SoftAssign [74]) and Mutual Information [73], leading to a smaller number of local minima and thus presenting the most convincing improvements. In [38] the authors introduced a probabilistic approach based on the Expectation Maximization (EM) paradigm, namely EM-ICP. Hidden variables are used to model the point matching. Specifically, in the case of Gaussian noise, the proposed method corresponds to ICP with multiple matches weighted by normalized Gaussian weights. In practice, the variance of the Gaussian is interpreted as a scale parameter. At high scales EM-ICP gets many matches, while it behaves like standard ICP at lower scales.

6.3 Advanced Techniques

Although registration is one of the most studied problems in computer vision, several cases are still open and new issues have emerged in the recent years. In this section we focus on some scenarios where registration becomes more challenging: registration of more than two views, registration in cluttered scenes and registration of deformable objects. We also describe some emerging techniques based on machine learning to solve the registration problem. Figure 6.7 illustrates the proposed taxonomy for advanced registration techniques.

Fig. 6.7 A taxonomy of advanced registration techniques

6.3.1 Registration of More than Two Views

Once registration has been performed pairwise, all the views need to be transformed into a global reference system by applying a multiple-view registration technique. There are two main issues: (i) error accumulation and (ii) automation of the process.

Reducing Error Accumulation When the ordering of the sequence of views N1, . . . , Np is available, registration can be performed pairwise between consecutive views (i.e., between views Ni and Ni+1). In general, even if all the pairs are apparently well registered, some misalignment typically appears when the full model is reconstructed due to the accumulation and propagation of the registration error. The general idea of multiple-view registration techniques is to solve simultaneously for the global registration by exploiting the interdependences between all views at the same time. This introduces additional constraints which reduce the global error. A comparative study of similar multiple-view registration schemes was performed [27]. In [71] a method is presented that first aligns the scans pairwise with each other and then uses the pairwise alignments as constraints in a multi-view step. The aim is to evenly distribute the pairwise registration error, but the method itself is still based on pairwise alignments. In [17] a method that distributes registration errors evenly across all views was proposed. It operates in the space of estimated pairwise registration matrices, however ordering of the views is required. More recently, [91] proposed a new approach based on the well-known Generalized Procrustes Analysis, seamlessly embedding the mathematical theory in an ICP framework. A variant of the method, where the correspondences are non-uniformly weighted using a curvature-based similarity measure was also presented.

Automating Registration Especially when the full model is composed of a large number of scans, the view order might not be available and therefore should be manually specified. Many methods have been proposed to improve the automation

Fig. 6.8 Example of large scan acquisition (left) and scene with multiple mechanical objects (right)

is proposed that creates a global model description using an oriented point pair feature and matches it using a fast voting scheme. This fast voting scheme, similar to the Generalized Hough Transform, is used to optimize the model pose in a locally reduced search space. This space is parametrized in terms of points on the model and rotation around the surface normals.

6.3.3 Deformable Registration

While rigidity in the aligning transformation is a largely applicable constraint, it is too restrictive in some cases. Imagine indeed that the object that has to be registered is not rigid but deformable. Deformable registration has two main issues: the computation of stable correspondences and the use of an appropriate deformation model. Note that the need for registration of articulated or deformable objects has recently increased due to the availability of real-time range scanners [21, 22, 51, 58]. Roughly speaking, we can emphasize two classes of deformable registration methods: (i) methods based on general optimization techniques, and (ii) probabilistic methods.

Methods Based on General Optimization Techniques The general formulation of deformable registration is more involved than the rigid case and it is more difficult to solve in closed-form. Advanced optimization techniques are used instead. The advantage of using general optimization techniques consists of jointly computing the estimation of correspondences and the deformable parameters [21, 22, 24, 51]. Moreover, other unknowns can be used to model further information like the overlapping area, the reliability of correspondences, the smoothness constraint and so on [51]. Examples of transformation models which have been introduced for surface deformations are (i) affine transforms applied to nodes uniformly sampled from the range images [51], (ii) rigid transforms on patches automatically extracted from