• Chinese Optics Letters
  • Vol. 18, Issue 7, 071001 (2020)
Qin Shu1, Xiuli He1, Chang Wang1、*, and Yunxiu Yang2
Author Affiliations
  • 1College of Electrical Engineering, Sichuan University, Chengdu 610065, China
  • 2Southwest Institute of Technical Physics, Chengdu 610041, China
  • show less
    DOI: 10.3788/COL202018.071001 Cite this Article Set citation alerts
    Qin Shu, Xiuli He, Chang Wang, Yunxiu Yang. Parallel registration algorithm with arbitrary affine transformation[J]. Chinese Optics Letters, 2020, 18(7): 071001 Copy Citation Text show less

    Abstract

    The point clouds scanned by a 3D laser scanner may be affine transformed when the size and posture of the objects being scanned are different. This type of problem is common, but few algorithms can solve it. Therefore, this Letter proposes a parallel registration algorithm. The algorithm eliminates the effects of the affine matrix in the point cloud, based on a simple whitening operation. Moreover, it also has strong anti-noise performance. The algorithm proposed in this Letter is not only simple in structure, but also shows excellent effects in practical applications and simulations.

    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[1,2]. At present, global registration[36] and local registration[79] are the two main research directions. Since the scale of the point clouds may be inconsistent, scale registration[1012] is proposed based on global registration. The scale registration algorithm generally introduces a scale coefficient based on the global registration algorithm. However, in practical engineering applications, due to different types of three-dimensional laser scanners, thermal expansion of the objects being scanned, and differences in the types of scanned objects, point clouds may be arbitrarily affine transformed. This problem is very common, for example, the relationship between iphone 6 and iphone 6 plus is an affine transformation. Therefore, we focus on the problem of arbitrary affine point clouds registration.

    Besl et al.[3] proposed the classic iterative closest point (ICP) algorithm in 1992, which is commonly used for point set registration, but it is not suitable for affine registration. On the basis of ICP, many scholars are committed to improving the ICP algorithm in order to complete a more complex point set registration. Ying et al.[10] put forward a scale registration algorithm that introduced an affine factor and searched for seven undetermined variables to register point clouds on different scales. In Ref. [11], Makovetskii et al. presented an affine registration algorithm based on a point-to-plane approach, which is used to register point clouds that are affine transformed in three fixed directions. The methods[12,13] solved the same problem like in Ref. [11]. A multi-scale affine registration algorithm[14] can only be used for image registration. In Ref. [15], an affine registration algorithm of point sets using ICP and ICA (independent component analysis) was proposed. Indeed, the algorithm can solve the affine registration problem. However, both ICA and ICP require iterative operations, and the ICA algorithm requires the order of point sets. Some scholars also presented a correntropy-based method to improve the affine ICP[16,17]. Those algorithms can obtain good results on some simple affine registrations while they cannot register point clouds with an arbitrary affine transformation.

    Some algorithms[1822] based on probability estimation have been developed to solve the nonrigid registration problem. They use Gaussian mixture models (GMMs); the coherent point drift (CPD) algorithm[18] is a classic example that is widely used for point cloud registration. These algorithms can achieve rigid and nonrigid registration for point clouds; they avoid the iteration of the ICP, but the probability estimation algorithm relies on the EM (expectation maximization algorithm). The EM iteration process may consume more time than the ICP. More recently, Ma et al.[23] proposed the global and local structure preserving point set registration (PRGLS) algorithm, which improved CPD by obtaining a binary corresponding matrix that updates the transformation under preserving global and local structures. Zhang et al.[24] also used the method of the global-local structural preservation to solve a nonrigid point set registration. In addition, Ma et al., who keep focusing on spatial structure preservation, proposed locality preserving matching (LPM)[25] and they put forward the MR-RPM algorithm[26] by learning nonrigid transformation between two given point sets with manifold regularization to complete the registration. It has to be said that these methods have achieved good registration results, but they take a relatively long time to complete the registration when they are applied to large-scale 3D point cloud registration.

    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 {p1,p2,,pn} and a source point cloud Γ be the point set {q1,q2,,qn} in R3. 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 AR3, Rank(A)=3 and the translation vector p0=(x0,y0,z0)T.

    The registration problem of the two point clouds is to find the reversible operator T so that T(pk) is infinitely close to qk. Then the corresponding point between pk and qk 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 X, and the source point cloud be matrix Y and X={p1,p2,,pn}, Y={q1,q2,,qm}. Then, where InR1×n 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 (7) can be obtained by the principal component analysis (PCA) method:

    In fact, Y˜AX˜. According to Eq. (7) and statistical principles, Eq. (8) can be obtained:

    Then, Eq. (8) can be rewritten as

    Equation (9) can be decomposed into two parts. Since the decomposition is not unique, there must be an orthogonal matrix R that satisfies

    In addition, the two sets of point clouds can be whitened as follows:

    By Eqs. (5), (10), and (11), where the relationship between X^ and Y^ is a rigid transformation.

    At present, many algorithms[37,14,15] can solve the registration problem in Eq. (12). Here, we give a fast algorithm to solve it. Define the global structure feature and introduce a continuous bounded nonlinear real function cluster where 0<M1gkM2, and M1 and M2 are the infimum and supremum of gk, respectively. The global vector features of point clouds X^ and Y^ are defined as where x^k and y^k denote the kth column vector of X^ and Y^, respectively. After taking the weighted average of the data, some features of the point cloud become more stable. According to statistical principles,

    According to the linear operator theory, the orthogonal matrix R is a unitary matrix. Then,

    Clearly, Eq. (16) can be rewritten as

    For convenience, the characteristic matrices for two point clouds are defined as

    Then, the following equation can be derived from Eqs. (17) and (18):

    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 J(R,t) can be built, where Z represents the corresponding point of X^ in Y^; ·F stands for the Frobenius norm; and t is the translation vector. Minimize J(R,t) and the optimal parameters can be obtained. Clearly, the registration Eq. (22) may require multiple calculations. Then where zi(k) denotes the ith column vector of Z(k) and k is the number of iterations. In addition, there may be an error in the whitening process, hence R may not be an orthogonal matrix. Then, Eq. (25) can be reduced to where ε=0.5 in the experiment. However, it is important to choose which iteration formula to use. In order to quickly calculate the optimal value, we use a parallel computing structure. That is, two iteration formulas are simultaneously calculated for several cores. An optimal convergent solution (R*,t*) can be obtained with a differential optimization algorithm. Then

    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 X and source point cloud Y;
    Step 1: Remove the mean of the point clouds X and Y using Eq. (6);
    Step 2: Whiten X and Y using Eqs. (7) and (11);
    Step 3: Estimate the value of R using Eq. (20);
    Step 4: Parallel compute the following two steps:
    Step 4.1: Optimize Eq. (25) until i=1nR(k)xi+t(k)zi(k)2<i=1nR(k+1)xi+t(k+1)zi(k+1)2;
    Step 4.2: Optimize Eq. (26) until i=1nR(k)xi+t(k)zi(k)2<i=1nR(k+1)xi+t(k+1)zi(k+1)2;
    Step 5: Using Eq. (28), estimate the parameters and register the point clouds.

    The time complexity of Step 1 in the Whitening-ICP algorithm is O(1), the time complexity of Step 2 is O(n), Step 3 cost O(1) 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 O(nlogn), so the time and space complexities of our method can be simply written as O(nlogn) and O(n), 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. 1 is when the signal-to-noise ratio (SNR) is 20 dB.

    Schematic diagram of the registration process: (a) initial state, (b) point clouds after being whitened, (c) point cloud after registration.

    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. 1 that the source point cloud is very unclear because it is affine transformed and disturbed by noise. When both point clouds are whitened, the outline of the source point cloud can be seen roughly. This fully proves that the whitening process is very effective. In order to verify the stability of the algorithm, experiments were carried out under different SNRs. The experimental results are shown in Table 1 and Fig. 2 in which the root mean square error (RMSE) representation is where Z is the corresponding point of the point cloud AX+p0In in the point cloud Y.

    MetricSNRCPDAffine-ICPMDARWhitening-ICP
    Ave. Error (mm)200.68341.82350.97310.2641
    250.68821.91110.92080.3684
    300.18252.30220.63750.0788
    350.62372.04440.85720.0612
    Ave. Time (s)201219195.243.640.3
    251410170.928.252.8
    301484344.624.919.4
    35133070.341.513.4

    Table 1. Registration Effect Under Different Signal-to-Noise Ratios

    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.

    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 31,600 points) as an example, we test the accuracy and the elapsed time of several algorithms: CPD[18], Affine-ICP[15], MDAR[13], and the algorithm proposed in this Letter. In order to prove the effectiveness of the algorithm in this Letter, we calculated the average running time and registration error on 100 trials in Table 1. In addition, to make a quantitative comparison of different methods, we analyzed the standard deviation of the errors for all the trials in Fig. 2. It can be seen from Table 1 and Fig. 2 that the Whitening-ICP algorithm has a strong anti-noise performance.

    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[23] for comparison. Since PR-GLS makes MATLAB exceed the memory limit when performing large-scale point cloud registration, here we only use the Face point cloud for testing. It can be seen from Figs. 3 and 4 that CPD and MDAR distort the point cloud, Affine-ICP cannot register the point cloud under any affine change at all, and the registration effect of PR-GLS is not ideal. By contrast, Whitening-ICP can achieve the best performance. In Tables 1 and 2, obviously, the time consumption of Whitening-ICP is relatively optimal. In Table 2, although the error in CPD is the smallest, it consumes dozens of times the time of Whitening-ICP. So, it can be concluded that Whitening-ICP has the best performance.

    Bunny point cloud registration effect of several algorithms under the condition that the point cloud is affine transformed.

    Figure 3.Bunny point cloud registration effect of several algorithms under the condition that the point cloud is affine transformed.

    Face 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.

    MetricCPDAffine-ICPPR-GLSMDARWhitening-ICP
    Ave. Error (mm)0.09110.41510.38030.27960.1314
    Ave. Time (s)3.50.135.10.60.1

    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. 5.

    Point cloud and objects.

    Figure 5.Point cloud and objects.

    Figures 5(a) and 5(b) show the scanned objects and scanned point cloud data (Bottle: 21,400 points, Cup: 34,000 points, Banana: 16,800 points). As can be seen from Fig. 5(b), there are holes in the surface of some point clouds. The collected point cloud data is not complete due to the reflection of the object surface. Therefore, registering point clouds during the experiment is more challenging than in simulation. In order to fully demonstrate the superiority of the algorithm, this Letter uses CPD[18], Affine-ICP[15], and MDAR[13] to compare with the algorithm. Their registration results are shown in Fig. 6.

    Registration results of several algorithms.

    Figure 6.Registration results of several algorithms.

    Figure 6 shows that the other methods have shown better performance except for Affine-ICP because the three objects did not undergo obvious affine deformation during actual scanning. However, it can be seen from Table 3 that Whitening-ICP has better stability and accuracy and higher efficiency.

    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.

    MetricAlgorithmBottleCupBanana
    Ave. Error (mm)CPD0.48460.34480.6374
    Affine-ICP0.76820.310218.0051
    MDAR1.38730.88580.4394
    Whitening-ICP0.40360.29640.4511
    Ave. Time (s)CPD550902263
    Affine-ICP12968.4294
    MDAR9.816.47.09
    Whitening-ICP145.479.051.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

    [1] L. Li, Z. Pan, H. Cui, J. Liu, S. Yang, L. Liu, Y. Tian, W. Wang. Chin. Opt. Lett., 17, 061001(2019).

    [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).

    Qin Shu, Xiuli He, Chang Wang, Yunxiu Yang. Parallel registration algorithm with arbitrary affine transformation[J]. Chinese Optics Letters, 2020, 18(7): 071001
    Download Citation