Abstract
Registration technology is an important digital detection technology that is used in many fields such as NDT (non-destructive testing), pattern recognition, virtual reality, robots, and related fields[
Besl et al.[
Some algorithms[
Sign up for Chinese Optics Letters TOC. Get the latest issue of Chinese Optics Letters delivered right to you!Sign up now
As in engineering applications, arbitrary affine phenomena are common in point cloud registration, and given that there are currently few affine algorithms to solve such problems, and some classic nonrigid registration algorithms either run for a long time or have higher requirements for operating equipment, this Letter focuses on how to solve the relationship between two given point sets in a simple way and how to accurately and quickly estimate the affine transformation. Finally, we propose a simple structured and fast affine registration algorithm.
The contributions of this Letter include the following three aspects. First, the whitening operation is introduced to the point set registration problem to find the relationship between the two point sets, which makes the affine registration problem be a rigid registration problem. Second, in the relationship after the whitening operation, the global vector features of point clouds are introduced and combined with the least squares method to achieve a fast coarse registration. Third, fast registration is provided for the proposed method using parallel computing, especially for large-scale 3D point clouds, which means the algorithm can work on low-performance computers.
Let a target point cloud be the point set and a source point cloud be the point set in . Furthermore, assume that the relationship between points in and is one-to-one mapping. Without loss of generality, a reversible operator is defined as where the affine matrix , and the translation vector .
The registration problem of the two point clouds is to find the reversible operator so that is infinitely close to . Then the corresponding point between and is as follows:
How to obtain the reversible operator is the key point in registration, and many researchers describe the problem using a cost function where represents 2-norm, and further minimizes the cost function to obtain an estimate of the reversible operator
Let the target point cloud be matrix , and the source point cloud be matrix and , . Then, where is the vector whose elements are all 1, and indicates that two point clouds have been registered. Since the relationship between point clouds does not correspond exactly, cannot be used to describe their relationship.
We first remove the mean of the point clouds and ensure that the center of the point clouds is at the origin of the coordinate space. After the mean value is removed, the point clouds are as follows:
Equation (
In fact, . According to Eq. (
Then, Eq. (
Equation (
In addition, the two sets of point clouds can be whitened as follows:
By Eqs. (
At present, many algorithms[
According to the linear operator theory, the orthogonal matrix R is a unitary matrix. Then,
Clearly, Eq. (
For convenience, the characteristic matrices for two point clouds are defined as
Then, the following equation can be derived from Eqs. (
According to the least squares method,
According to the singular value decomposition,
Considering the effect of the calculation error, R may not be an orthogonal matrix. Therefore, R is corrected to
Clearly,
The above algorithm runs fast in computers, and its step is very simple. Therefore, the algorithm is called a fast algorithm.
However, there may be some errors in the previous registration process. Then, to further register the point cloud, a cost function can be built, where represents the corresponding point of in ; stands for the Frobenius norm; and is the translation vector. Minimize and the optimal parameters can be obtained. Clearly, the registration Eq. (
Further,
For convenience, we call the algorithm proposed in this Letter as the whitening iteration closest point (Whitening-ICP) algorithm. The algorithm flow is as follows.
Whitening-ICP Algorithm |
---|
Input: Target point cloud |
Step 1: Remove the mean of the point clouds |
Step 2: Whiten |
Step 3: Estimate the value of R using Eq. ( |
Step 4: Parallel compute the following two steps: |
Step 4.1: Optimize Eq. ( |
Step 4.2: Optimize Eq. ( |
Step 5: Using Eq. ( |
The time complexity of Step 1 in the Whitening-ICP algorithm is , the time complexity of Step 2 is , Step 3 cost complexity, and the major cost is Step 4 that searches the nearest point in two point sets by a Delaunay irregular network; its complexity is close to , so the time and space complexities of our method can be simply written as and , respectively.
To prove the effectiveness of the algorithm proposed in this Letter, Bunny point cloud data provided by Stanford University and Face point cloud data provided by CPD were used for registration verification. The simulation was based on MATLAB 2016a, whose environment was configured for a 2.5 GHz CPU with 8 GB RAM.
In this section we consider the case where the point cloud is disturbed by white noise. The registration result of the point cloud shown in Fig.
Figure 1.Schematic diagram of the registration process: (a) initial state, (b) point clouds after being whitened, (c) point cloud after registration.
It can be seen from Fig.
Metric | SNR | CPD | Affine-ICP | MDAR | Whitening-ICP |
---|---|---|---|---|---|
Ave. Error (mm) | 20 | 0.6834 | 1.8235 | 0.9731 | |
25 | 0.6882 | 1.9111 | 0.9208 | ||
30 | 0.1825 | 2.3022 | 0.6375 | ||
35 | 0.6237 | 2.0444 | 0.8572 | ||
Ave. Time (s) | 20 | 1219 | 195.2 | 43.6 | |
25 | 1410 | 170.9 | 28.2 | ||
30 | 1484 | 344.6 | 24.9 | ||
35 | 1330 | 70.3 | 41.5 |
Table 1. Registration Effect Under Different Signal-to-Noise Ratios
Figure 2.Comparison of Whitening-ICP with Affine-ICP, CPD, and MDAR on different SNR for the Bunny point cloud. Error bars: registration error means and standard deviations over 100 trials.
Taking the Bunny point cloud (approximately
In order to better verify the effect of an arbitrary affine registration, a Face point cloud (392 points) was added for an affine registration test. At the same time, we added a state-of-the-art classic algorithm PR-GLS[
Figure 3.Bunny point cloud registration effect of several algorithms under the condition that the point cloud is affine transformed.
Figure 4.Face point cloud registration effect of several algorithms under the condition that the point cloud is affine transformed.
Metric | CPD | Affine-ICP | PR-GLS | MDAR | Whitening-ICP |
---|---|---|---|---|---|
Ave. Error (mm) | 0.4151 | 0.3803 | 0.2796 | ||
Ave. Time (s) | 0.1 | 35.1 | 0.6 |
Table 2. Registration Results on 100 Trials for Face Point Cloud
In this Letter, we use the portable laser scanner (HANDYSCAN 700TM portable laser scanner) to collect data from objects. Considering the existence of the ground truth affine transformation, we first label the object and then the object can be automatically located by the scanner in the scanning process so that the interference of the ground and the background can be ignored. The data collected by the scanner was exported to the software MeshLab and the point clouds were reconstructed, which is shown in Fig.
Figure 5.Point cloud and objects.
Figures
Figure 6.Registration results of several algorithms.
Figure
In simulations and experiments, the Affine-ICP algorithm often has poor registration results due to the limitations of the convergence domain. For CPD, in fact, we can also adjust the parameters of the CPD algorithm so that it may have a better registration effect. However, the CPD depends on the initial state of the point clouds and inevitably distorts the point cloud. MDAR is just a multi-directional affine algorithm; it allows the point cloud to expand and contract in the three directions of X, Y, and Z. Therefore, its effect is not stable during arbitrary affine registration, which depends on the degree of affine deformation. However, Whitening-ICP shows excellent point clould registration results under arbitrary affine transformation.
Metric | Algorithm | Bottle | Cup | Banana |
---|---|---|---|---|
Ave. Error (mm) | CPD | 0.4846 | 0.3448 | 0.6374 |
Affine-ICP | 0.7682 | 0.3102 | 18.0051 | |
MDAR | 1.3873 | 0.8858 | ||
Whitening-ICP | 0.4511 | |||
Ave. Time (s) | CPD | 550 | 902 | 263 |
Affine-ICP | 129 | 68.4 | 294 | |
MDAR | 9.8 | 16.4 | ||
Whitening-ICP | 51.4 |
Table 3. Registration Results on 50 Trials for Three Actual Objects
In conclusion, we proposed a novel approach named Whitening-ICP for point cloud registration under arbitrary affine transformation. Our approach uses a simple whitening operation to find the relationship between two point clouds, and the global vector features of point clouds are introduced and combined with the least squares method to achieve fast coarse registration. The proposed algorithm based on parallel computing can work on low-performance computers. We validated the effectiveness of our method both in simulations and experiments, and it realizes a more advanced performance compared with other state-of-the-art methods. However, Whitening-ICP can register complete point clouds. When the point clouds are incomplete, Whitening-ICP may fail to register them. We will improve this algorithm in future work and try to solve this problem.
References
[2] C. T. Seo, S. W. Kang, M. Cho. Chin. Opt. Lett., 15, 081102(2018).
[3] P. J. Besl, N. D. McKay. IEEE Trans. Pattern Anal., 14, 239(1992).
[4] X. Ge. ISPRS J. Photogramm., 130, 344(2017).
[5] M. Bueno, H. Gonzalez-Jorge, J. Martinez-Sanchez, H. Lorenzo. Automat. Constr., 81, 134(2017).
[6] S. Ji, Y. Ren, J. Zhao, X. Liu, H. Gao. Optik, 140, 451(2017).
[7] X. Huang, J. Zhang, L. Fan, Q. Wu, C. Yuan. IEEE Trans. Image Process., 26, 3261(2017).
[8] S. Byun, K. Jung, S. Im, M. Chang. Int. J. Precis. Eng. Man., 18, 1221(2017).
[9] Y. He, B. Liang, J. Yang, S. Li, J. He. Sensors., 17, 1862(2017).
[10] S. Ying, J. Peng, S. Du, H. Qiao. IEEE Trans. Autom. Sci. Eng., 6, 559(2009).
[11] A. Makovetskii, S. Voronin, V. Kober, D. Tihonkih. Procedia Eng., 201, 322(2017).
[12] J. Ho, A. Peter, A. Rangarajan, M.-H. Yang, 1335(2009).
[13] C. Wang, Q. Shu, Y. Yang, F. Yuan. IEEE Photonics J., 10, 6901215(2018).
[14] J. Kannala, E. Rahtu, J. Heikkila, III-1064(2005).
[15] S. Du, N. Zheng, S. Ying, J. Liu. Pattern Recognit. Lett., 31, 791(2010).
[16] Z. Wu, H. Chen, S. Du, 1415(2016).
[17] H. Chen, H. Zhang, S. Du, Z. Wu, N. Zheng. IEEE/CAA J. Automa. Sin., 6, 981(2019).
[18] A. Myronenko, X. Song. IEEE Trans. Pattern Anal., 32, 2262(2010).
[19] B. Jian, B. Vemuri. IEEE Trans. Pattern Anal., 33, 1633(2011).
[20] M. Lu, J. Zhao, Y. Guo, Y. Ma. IEEE Trans. Geosci. Remote Sens., 13, 162(2016).
[21] S. Du, J. Liu, C. Zhang, J. Zhu, K. Li. Neurocomputing, 157, 187(2015).
[22] W. Tao, K. Sun. IEEE Trans. Image Process., 24, 3754(2015).
[23] J. Ma, J. Zhao, A. L. Yuille. IEEE Trans. Image Process., 25, 5867(2016).
[24] S. Zhang, K. Yang, Y. Yang, Y. Luo, Z. Wei. Pattern Recogn., 80, 183(2018).
[25] J. Ma, J. Zhao, J. Jiang, H. Zhou, X. Guo. Int. J. Comput. Vision., 127, 512(2019).
[26] J. Ma, J. Zhao, J. Jiang, H. Zhou, Q. Z. Sheng. IEEE Trans. Neur. Netw. Learn. Syst., 30, 3584(2019).
Set citation alerts for the article
Please enter your email address