1.

Introduction

Point set registration is important and complex in image processing. One robust and efficient approach to handle this problem is the iterative closest point (ICP) algorithm,¹ but it cannot effectively register point sets with outliers including noise and missing data, which exist widely in applications.² To overcome this problem, some scholars used thresholds or probability of distances to discard outliers,³ but these methods need an appropriate threshold which depends on the structure of point sets and thus is hard to choose. Meanwhile, some researchers attempted to reject outliers by adopting a coarse to fine process,⁴ but the methods often perform poorly in the case of a large amount of outliers in point sets.

Different from the above-mentioned work, Chetverikov ⁵ proposed the trimmed ICP (TrICP) algorithm for partially overlapping registration, which incorporates an overlapping percentage into a least square function to trim outliers. This algorithm, however, is time-consuming in that it needs to be repeated by traveling all possible overlapping percentage to search the best result even though Golden Section Search is used to accelerate the search speed. Based on this work, Phillips ⁶ presented the fractional ICP (FICP) algorithm for much faster speed, which computes the best correspondence and the overlapping percentage simultaneously, whereas the method depends greatly on a parameter which may lead to a false registration. To cope with the problem, this paper proposes a new objective function. Moreover, a novel robust and efficient ICP algorithm is presented to compute optimal overlapping percentage automatically and to complete the registration successfully.

2.

Problem Statement

Given two point sets in [TeX:] \documentclass[12pt]{minimal}\begin{document}${\mathbb {R}^m}$\end{document} ${\mathbb{R}}^m$ , a model shape [TeX:] \documentclass[12pt]{minimal}\begin{document}$M \buildrel\Delta \over = \lbrace \vec{m}_i \rbrace _{i = 1}^{N_m }$\end{document} $M\genfrac{}{}{0pt}{}{\Delta }{=}{\left\{{\vec{m}}_i\right\}}_{i=1}^{N_m}$ and a data shape [TeX:] \documentclass[12pt]{minimal}\begin{document}$P \buildrel\Delta \over = \lbrace \vec{p}_i \rbrace _{i = 1}^{N_p } \quad (N_m ,N_p \in {\mathbb N})$\end{document} $P\genfrac{}{}{0pt}{}{\Delta }{=}{\left\{{\vec{p}}_i\right\}}_{i=1}^{N_p}(N_m,N_p\in \mathbb{N})$ . The rigid registration of m-D point sets is to build up correspondence and calculate rigid transformation (R, t) between P and M, hence

For partially overlapping point sets P and M, assume P_r is the overlapping part of P, which can match with M, and r denotes the overlapping percentage of P. The goal of partial registration is to build up the correspondence of P_r and M, and the distance is [TeX:] \documentclass[12pt]{minimal}\begin{document}$\sum _{\vec{p}_i \in P_r } {\vert \vert {\rm {\bf R}}\vec{p}_i + \vec{t} - \vec{m}_{c(i)} \vert \vert _2^2 }$\end{document} ${\sum }_{{\vec{p}}_i\in P_r}\left|\right|\mathbf{R}{\vec{p}}_i+\vec{t}-{\vec{m}}_{c\left(i\right)}{\left|\right|}_2^2$ which increases with r. Hence, to include enough corresponding points as well as to exclude outliers, we divide the square distance by a penalty function g(r), an increasing function with respect to r. As too little overlapping part does not provide enough information, we assume the overlapping percentage r varies from 0.5 to 1. Therefore,

In Eq. 2, it is easily proved that the objective function is a convex function with respect to r, which means the computation of r can be easily completed by iteration.

3.

Point Set Registration with Outliers

ICP is good in minimizing Eq. 1 by repeating two steps: compute the closest point in model shape for each point in data shape and calculate the rigid transformation. As Eq. 2 is a convex function with respect to r, we compute r at each iterative step. Hence, similar to ICP, the objective function 2 can be optimized iteratively after the initialization:

Step 1. Set up the correspondence with the (k − 1)'th rigid transformation [TeX:] \documentclass[12pt]{minimal}\begin{document}$({\rm {\bf R}}_{k - 1} ,\vec{t}_{k - 1} )$\end{document} $({\mathbf{R}}_{k-1},{\vec{t}}_{k-1})$ :

Step 2. Compute the k'th overlapping percentage r_k and the subset [TeX:] \documentclass[12pt]{minimal}\begin{document}$P_{r_k }$\end{document} $P_{r_k}$ according to the known control parameter λ and the corresponding point sets [TeX:] \documentclass[12pt]{minimal}\begin{document}$\lbrace {\rm {\bf R}}_{k - 1} \vec{p}_i + \vec{t}_{k - 1} \rbrace _{i = 1}^{N_p }$\end{document} ${\{{\mathbf{R}}_{k-1}{\vec{p}}_i+{\vec{t}}_{k-1}\}}_{i=1}^{N_p}$ and [TeX:] \documentclass[12pt]{minimal}\begin{document}$\lbrace \vec{m}_{c_k (i)} \rbrace _{i = 1}^{N_p }$\end{document} ${\left\{{\vec{m}}_{c_k\left(i\right)}\right\}}_{i=1}^{N_p}$ by minimizing the objective functions:

Step 3. Compute the rigid transformation by minimizing the following squared distance:

Step 4. Let [TeX:] \documentclass[12pt]{minimal}\begin{document}$\varepsilon _k = \sum _{\vec{p}_i \in P_{r_k } } {\vert \vert {\rm {\bf R}}_k \vec{p}_i + \vec{t}_k - \vec{m}_{c_k (i)} \vert \vert _2^2 } / (e^\lambda r_k^\lambda )$\end{document} ${\varepsilon }_k={\sum }_{{\vec{p}}_i\in P_{r_k}}\left|\right|{\mathbf{R}}_k{\vec{p}}_i+{\vec{t}}_k-{\vec{m}}_{c_k\left(i\right)}{\left|\right|}_2^2/\left(e^{\lambda }{r}_k^{\lambda }\right)$ . If |ε_k − ε_{k − 1}| is sufficiently small or k reaches a maximum number of iterations, the inside loop stops with ϕ(λ) = ε_k and λ is updated by λ = λ − λ_step. Repeat steps 1 through 3 by decreasing the parameter λ from its maximal value λ_max to its minimal value λ_min.

Finally, ϕ(λ) decreases at the initial stage when λ increases from λ_min to λ_max, and the best registration result is located at the first increasing point of ϕ(λ).

Discussion on the parameter λ. For Eq. 2, r increases with λ, namely, a larger λ leads to more point pairs. Following this, we run the iteration by changing λ in a decreasing order, which keeps as many point pairs as possible at the beginning and filters outliers gradually. Otherwise, the algorithm may easily drop into a local minimum because of insufficient points.

For partial registration, using as many point pairs as possible will yield a more reliable and accurate result. When two point sets are matched, it is easily proved ϕ(λ) is a decreasing function with respect to λ. As λ varies from λ_min to λ_max, ϕ(λ) decreases at first and then increases when mismatching points are found. Therefore, the optimal result is located at the first increasing point of ϕ(λ) which guarantees enough information used in registration.

The proposed algorithm iterates in a similar way as the ICP algorithm. Despite more steps of our algorithm than the ICP algorithm at each iteration, both algorithms spend the same time on the correspondence computation which is the most time-consuming part. Compared with this, the calculation time of other steps can be relatively ignored. Therefore, our algorithm can get similar computation time as ICP, which is quite fast.

4.

Experimental Results

We compare our algorithm with ICP,¹ TrICP,⁵ and FICP,⁶ in which the latter two are given different values of λ, and the results are reported in root-mean-square (RMS) error.

4.1.

2D Shapes Registration

Experiments are conducted here on part B of CE-Shape-1 (Ref. 9), where random noise exists on shapes. First, the totally overlapping bat and horse shapes are used to demonstrate our algorithm is robust for full registration. Second, to show the robustness of our algorithm for partial registration, we select one shape pair and trim down one part of each shape to make them partially overlap. The compared results are displayed in Table 1.

Table 1

Compared results on two-dimensional shapes.

	bat			horse			trimmed bat			trimmed horse
Algorithms	λ	r	RMS	λ	r	RMS	λ	r	RMS	λ	r	RMS
ICP	–	1	0.55	–	1	0.52	–	1	19.41	–	1	13.69
TrICP	2	0.98	0.51	2	0.51	6.94	2	0.69	0.49	2	0.88	6.44
TrICP	4	0.98	0.51	4	0.64	9.99	4	0.69	0.49	4	0.88	6.44
TrICP	6	0.98	0.51	6	0.71	13.52	6	0.69	0.49	6	0.88	6.44
FICP	1.3	0.5	9.11	1.3	0.5	6.80	1.3	0.51	15.02	1.3	0.5	8.39
FICP	3	1	0.55	3	0.70	12.59	3	0.70	0.51	3	1	14.26
FICP	5	1	0.55	5	1	0.52	5	1	19.41	5	1	13.69
Ours	6	1	0.53	6	1	0.51	6	0.70	0.50	4	0.80	0.59

As is shown in Table 1, our method always yields a good registration with small RMS. ICP only deals with registration of totally overlapping shapes and performs poorly for trimmed shapes that have a large amount of missing data. TrICP can complete some partial registration though, it is quite unstable for different shapes. As TrICP searches the best overlapping percentage by traveling all possible values, the results are likely to be similar. FICP achieves on some shapes, but it substantially relies on the preset value of λ which varies for different shapes registration. Therefore, both TrICP and FICP cannot complete full and partial registration well. In addition, our method automatically obtains an appropriate value of parameter λ, which not only guarantees a proper overlapping percentage r but also uses as many point pairs as possible to obtain more accurate registration results. In bat and horse shapes registration, the largest overlapping percentage reaches while RMS is small. One intutive example of the registration results is shown in Fig. 1.

Fig. 1

Registration results on two-dimensional horse shapes. (a) The original shapes. (b) ICP's result. (c) TrICP's result with λ=4. (d) FICP's result with λ=1.3. (e) FICP's result with λ=5. (f) Our method's result.

4.2.

3D Range Data Registration

We compare our algorithm with ICP and FICP on Stanford 3D Scanning Repository¹⁰ which is acquired from different viewpoints in practice. As the database has too many points and TrICP is too slow and unstable, we do not give the results of TrICP. In the database, Stanford Bunny (bun000 with 40,256 points and bun 045 with 40,097 points), Dragon (dragonStandRight_0 with 41,841 points and dragonStandRight_24 with 34,836 points), and Happy Budda (happyStandRight_0 with 78,056 points and happyStandRight_24 with 75,582 points) are adopted. The compared results are shown in Table 2.

Table 2

Compared results on Stanford Database.

	Bunny			Dragon			Happy Budda
Algorithms	λ	r	RMS (× 10−3)	λ	r	RMS (× 10−3)	λ	r	RMS (× 10−3)
ICP	–	1	2.05	–	1	1.86	–	1	2.28
FICP	0.95	0.50	0.87	0.95	0.50	0.60	0.95	0.50	0.69
FICP	3	0.91	0.38	3	0.90	0.35	3	0.82	0.26
FICP	5	0.93	0.40	5	0.92	0.38	5	0.83	0.29
Ours	5	0.91	0.35	5	0.90	0.32	5	0.81	0.24

Table 2 shows that our method gives the best registration results with least RMS, and computes the parameter λ automatically while ICP produces worse results and FICP performs well only when λ is equal to 3 or 5, which demonstrates FICP depends on the parameter λ and its results are unstable. The registration results are displayed in Fig. 2.

Fig. 2

Registration results on three-dimensional Stanford Bunny. (a) The original shapes. (b) ICP's result. (c) FICP's result with λ = 0.95. (d) FICP's result with λ = 3. (e) FICP's result with λ = 5. (f) Our method's result.

5.

Conclusion

This paper proposes a novel approach for registration between two m-D point sets with outliers in the way of incorporating an overlapping percentage into the ICP algorithm. Compared with previous works, our algorithm can automatically compute rigid transformation, correspondence, and overlapping percentage without influence of a parameter. Furthermore, the best overlapping percentage is computed by including as much information as possible, which leads to a satisfying registration. A series of compared experiments demonstrate that our algorithm is stable and precise.