New iterative closest point algorithm for isotropic scaling registration of point sets with noise☆
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)
- et al.
Building dynamic population graph for accurate correspondence detection
Med. Image Anal.
(2015) - et al.
Fast terrain mapping from low altitude digital imagery
Neurocomputing
(2015) - et al.
Object modelling by registration of multiple range images
Image Vis. Comput.
(1992) - et al.
A fast algorithm for ICP-based 3D shape biometrics
Comput. Vis. Image Underst.
(2007) - et al.
Pair-wise range image registration: a study in outlier classification
Comput. Vis. Image Underst.
(2002) - et al.
Probability iterative closest point algorithm for m-D point set registration with noise
Neurocomputing
(2015) - et al.
Scaling iterative closest point algorithm for registration of m-D point sets
J. Vis. Commun. Image Represent.
(2010) - Y. Zhang, Z. Jia, T. Chen, Image retrieval with geometry-preserving visual phrases, in: IEEE Conference on Computer...
- et al.
3-d object retrieval and recognition with hypergraph analysis
IEEE Trans. Image Process.
(2012) - et al.
Visual-textual joint relevance learning for tag-based social image search
IEEE Trans. Image Process.
(2013)
A probabilistic associative model for segmenting weakly supervised images
IEEE Trans. Image Process.
Representative discovery of structure cues for weakly-supervised image segmentation
IEEE Trans. Multimedia
On-device mobile visual location recognition by integrating vision and inertial sensors
IEEE Trans. Multimedia
Efficient BOF generation and compression for on-device mobile visual location recognition
IEEE Multimedia
Projected residual vector quantization for ANN search
IEEE Multimedia
Iterative point matching for registration of free-form curves and surfaces
Int. J. Comput. Vis.
Cited by (31)
Adaptive weighted robust iterative closest point
2022, NeurocomputingScale-Adaptive ICP
2021, Graphical ModelsCitation 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, NeurocomputingCitation 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 LettersCitation 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 RecognitionCitation 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.
Data processing of 3D and 4D in-vivo electron paramagnetic resonance imaging co-registered with ultrasound. 3D printing as a registration tool
2019, Computers and Electrical Engineering
- ☆
This paper has been recommended for acceptance by M.T. Sun.