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^[3–6] and local registration^[7–9] are the two main research directions. Since the scale of the point clouds may be inconsistent, scale registration^[10–12] 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^[18–22] 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 $\mathrm{\Omega }$ be the point set $\{p_1,p_2,\dots ,p_n\}$ and a source point cloud $\mathrm{\Gamma }$ be the point set $\{q_1,q_2,\dots ,q_n\}$ in $R^3$. Furthermore, assume that the relationship between points in $\mathrm{\Omega }$ and $\mathrm{\Gamma }$ is one-to-one mapping. Without loss of generality, a reversible operator is defined as where the affine matrix $A\in R^3$, $\mathrm{Rank}(A)=3$ and the translation vector $p_0={(x_0,y_0,z_0)}^T$.

The registration problem of the two point clouds is to find the reversible operator $T•$ so that $T(p_k)$ is infinitely close to $q_k$. Then the corresponding point between $p_k$ and $q_k$ 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 $\Vert ·\Vert$ 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=\{p_1,p_2,\dots ,p_n\}$, $Y=\{q_1,q_2,\dots ,q_m\}$. Then, where $I_n\in R^{1\times n}$ is the vector whose elements are all 1, and $\leftrightarrow$ 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, $\tilde{Y}\leftrightarrow A\tilde{X}$. 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 $\widehat{X}$ and $\widehat{Y}$ is a rigid transformation.

At present, many algorithms^{[3–7,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<M_1\le g_k\le M_2$, and $M_1$ and $M_2$ are the infimum and supremum of $g_k$, respectively. The global vector features of point clouds $\widehat{X}$ and $\widehat{Y}$ are defined as where ${\widehat{x}}_k$ and ${\widehat{y}}_k$ denote the $k$th column vector of $\widehat{X}$ and $\widehat{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 $\widehat{X}$ in $\widehat{Y}$; ${\Vert ·\Vert }_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 $z_i^{(k)}$ denotes the $i$th 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 $\epsilon =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.

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(n\log n)$, so the time and space complexities of our method can be simply written as $O(n\log n)$ 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.

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+p_0{I}_n$ in the point cloud $Y$.

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.

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.

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.

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.

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.