New iterative closest point algorithm for isotropic scaling registration of point sets with noise

https://doi.org/10.1016/j.jvcir.2016.02.019Get rights and content

Highlights

  • The one-to-one correspondence is adopted to accelerate the speed.

  • The idea of from coarse to fine is employed to prevent local minimum.

  • The proposed approach achieves fast speed and high accuracy.

Abstract

This paper proposes a new probability iterative closest point (ICP) approach with bounded scale based on expectation maximization (EM) estimation for isotropic scaling registration of point sets with noise. The bounded-scale ICP algorithm can handle the case with different scales, but it could not effectively yield the alignment of point sets with noise. Aiming at improving registration precision, a Gaussian probability model is integrated into the bounded-scale registration problem, which is solved by the proposed method. This new method can be solved by the E-step and M-step. In the E-step, the one-to-one correspondence is built up between two point sets. In the M-step, the scale transformation including the rotation matrix, translation vector and scale factor is computed by singular value decomposition (SVD) method and the properties of parabola. Then, the Gaussian model is updated via the distance and variance between transformed point sets. Experimental results demonstrate the proposed method improves the performance significantly with high precision and fast speed.

Introduction

Point set registration is a fundamental problem of great importance that continues to attract considerable interest in pattern recognition and image processing, such as image retrieval [1], [2], [3], image registration and segmentation [4], [5], [6], 3D reconstruction and mobile visual search [7], [8], [9], [10]. The goal of registration is to establish the corresponding relationship between two point sets, and recover the optimal spatial transformation which yields the best alignment. The Iterative Closest Point (ICP) algorithm is the most popular approach for its good performance and simplicity [11], [12], [13]. Moreover, many scholars studied the speed [14], [15] and robustness [16], [17] of the ICP algorithm.

In the past few decades, a great number of scholars make great efforts to improve the performance of ICP for registration of point sets with a large amount of outliers and noise which exist widely in practice. To handle the outliers, it has derived many methods. For instance, one simple way is to employ geometry constraint method [18], which often varied according to the shapes of the point sets, so it is not robust enough. Meanwhile, the distance threshold was also utilized [19], [20], [21]. Furthermore, the partial registration methods based on overlapping percentage are proposed for dealing with the outliers [22], [23]. To improve the precision of the registration of point sets with noise, the probability was introduced to the registration algorithms. Based on expectation maximization (EM) principle, the EM-ICP algorithm [24] was proposed which was weighted by normalized Gaussian weights, and then Du et al. [25] proposed a probability ICP algorithm for accurate rigid point set registration with noise, but all of them did not take the scale into account.

In the meanwhile, the original ICP algorithm does not take the scale factor into consideration. To tackle with the isotropic scaling issue, Zinßer et al. [26] introduced integrated estimation of the scale factor. However, it requires a rough pre-alignment of the point sets. Therefore, Ying and Du et al. [27], [28] instead proposed a novel approach named the Iterative Closest Point with Bounded Scale (ICPBS) algorithm which integrated a scale with boundaries into the traditional ICP algorithm for isotropic scaling registration with few outliers. Meanwhile, a lot of scholars extend the approach to varied cases. To improve the performance, Li et al. [29] introduced a sparse-to-dense hierarchical model in ICP algorithm to speed up the isotropic scaling registration. Moreover, Du et al. [30] extended it to deal with outliers by the scaling registration of partially overlapping point sets. However, it is lack of methods to deal with the scaling registration of point sets with noise to improve the precision.

For the purpose of taking the scale factor and noise into account, the coherent point drift algorithm (CPD) [31] is extended to the scaling registration, which adopts full correspondence relationship for all the points in the model point set and the shape point set. Therefore, it increases the computational complexity and the accuracy is limited for the small probabilities of incorrect point pairs which are assigned by full correspondence of CPD algorithm. To handle the problem of isotropic scaling registration with noise, we introduce the EM principle and the scale factor, and then one-to-one correspondence is employed which is for all the points in the shape point set only needing to find the closest points in the model set. The one-to-one correspondence is able to decrease the influence of the incorrect points and maintain the original information of point pairs without the interference of noise, which can achieve high accuracy. However, the one-to-one correspondence may cause the proposed algorithm trapped into the local minimum, so the variance of Gaussian probability model is updated from large to small step by step dynamically, which results in the registration from coarse to fine. In the first stage, the variance is assigned to be a big value, so all the points are close to uniform distribution which is the coarse registration. As the variance decreases, the distribution becomes close to the real distribution of the registration error which is the fine registration. Experimental results on part B of CE-Shape-1, the Stanford 3D Scanning Repository databases and the real map mergence verify the proposed method has fast speed and high accuracy.

The rest of this paper is organized as follows. In Section 2, the ICPBS algorithm is briefly reviewed. Following that is Section 3, for the purpose of solving the isotropic scaling registration of point sets with noise, by introducing the Gaussian probability model, the probability iterative closest point algorithm with bounded scale is presented. A series of experiments demonstrate the effectiveness of our method in Section 4. Finally, the conclusion is drawn.

Section snippets

Iterative closest point with bounded scale

In the field of pattern recognition, training samples need to be aligned which can be accomplished by image registration methods. As points are basic features of images, point set registration is important in image registration. The ICP is the classical algorithm for the rigid registration of point sets. However, it cannot deal with the isotropic scaling registration problems which exist widely such as multi-resolution image registration. In practice, the isotropic scaling registration needs to

Problem statement

In practice, the noise captured by the sensor or produced by the image processing exists widely in point sets which is called shape noise. Therefore, it is necessary to accomplish the isotropic scaling registration for point sets with noise. The ICPBS algorithm can yield the isotropic scaling registration with good accuracy and fast speed, but it could not register two point sets with noise preciously. Fig. 1 exhibits a registration result of 2D noisy point sets.

In Fig. 1, the red points

Experimental results

In this part, to demonstrate the precision and computation complexity of the proposed scaling probability ICP (sPICP), the experiments are conducted on the part B of CE-Shape-1 [34], the Stanford 3D Scanning Repository [35] and the real map dataset. We compare the root mean square (RMS) and the computation time with ICPBS [27] and CPD [31]. All the tests are conducted in Matlab on Intel Core 2 Duo 2.09 GHz CPU, 2.00 GB RAM.

Conclusion

This paper proposes the scaling probability ICP algorithm based on EM principle to tackle the issue of isotropic scaling registration of point sets with shape noise. To achieve this aim, a Gaussian model is incorporated into the isotropic scaling registration problem, which is solved by iterations. The experimental results of 2D, 3D and real map mergence registration demonstrate the sPICP is more accurate than other scaling registration algorithms. The main contributions of our algorithm are as

Acknowledgements

This work was supported by the National Natural Science Foundation of China under Grant Nos. 61573274 and 91320301, 973 Program under Grant No. 2015CB351703, and the Program of Introducing Talents of Discipline to University under Grant No. B13043.

References (35)

  • L. Zhang et al.

    A probabilistic associative model for segmenting weakly supervised images

    IEEE Trans. Image Process.

    (2014)
  • L. Zhang et al.

    Representative discovery of structure cues for weakly-supervised image segmentation

    IEEE Trans. Multimedia

    (2014)
  • T. Guan et al.

    On-device mobile visual location recognition by integrating vision and inertial sensors

    IEEE Trans. Multimedia

    (2013)
  • T. Guan et al.

    Efficient BOF generation and compression for on-device mobile visual location recognition

    IEEE Multimedia

    (2014)
  • B. Wei et al.

    Projected residual vector quantization for ANN search

    IEEE Multimedia

    (2014)
  • Z. Zhang

    Iterative point matching for registration of free-form curves and surfaces

    Int. J. Comput. Vis.

    (1994)
  • P.J. Besl, N.D. McKay, Method for registration of 3-D shapes, in: Robotics-DL Tentative, 1992, pp....
  • Cited by (31)

    • Scale-Adaptive ICP

      2021, Graphical Models
      Citation Excerpt :

      The first one [52] solves for rotation, scaling, and translation independently in this order[13]., and its extensions by the same research group Du et al. [11,12,22,48], inject the scale matrix directly into the ICP least-squares problem with a constraint condition that the matrix is bounded. Although it is not demonstrated in their result sets, the reason of finding a scaling matrix instead of a scaling factor is to handle non-uniform scaling.

    • Precise iterative closest point algorithm for RGB-D data registration with noise and outliers

      2020, Neurocomputing
      Citation Excerpt :

      The ICP algorithm has become the main method for the processing of distance image registration for 3D reconstruction and Simultaneous Location and Mapping (SLAM) [23–25], and has been continuously optimized and improved by researchers. Some scholars have proposed registration on the geometry of point clouds [26–28]. Thirion et al. [29] proposed a point cloud registration algorithm based on geometrically invariant 3D surface key points, which has rotation invariance for rigid transformation but has higher time complexity.

    • Robust rigid registration algorithm based on pointwise correspondence and correntropy

      2020, Pattern Recognition Letters
      Citation Excerpt :

      Chetverikov et al. [16] proposed the trimmed ICP (TrICP) algorithm for partially overlapping registration. Du et al. [17,18] proposed probability ICP for registration of point sets with noises. Granger et al. [19] proposed multi-scale EM-ICP algorithm which introduced the full correspondence relationships of all the points.

    • Correntropy based scale ICP algorithm for robust point set registration

      2019, Pattern Recognition
      Citation Excerpt :

      Firstly, we formulate the scale registration problem into an equality constraint optimization problem by applying the maximum correntropy criterion (MCC) [24–28]. To solve such an optimization problem, we imitate the process of ICP and design a fast and accurate iterative procedure based on the half-square technique [24] and singular value decomposition (SVD) method [15]. We also give several comparative experiments to verify that the proposed algorithm is very fast and robust for scale registration with noisy point sets.

    View all citing articles on Scopus

    This paper has been recommended for acceptance by M.T. Sun.

    View full text