Comparison of Several Different Registration Algorithms

With the rapid development of computer-aided design and computer-aided manufacturing technology, reverse engineering technology, which generates digital model through physical model, has been widely concerned. In reverse engineering, computer vision, 3D image processing and other fields, it is difficult to obtain all the data of the measured object in all directions at one time due to the influence of data acquisition equipment, the shape of the 3D object itself, external environment and so on. Usually, the point cloud data of three-dimensional objects are acquired from different angles by data acquisition equipment for many times, and the point cloud registration algorithm is used to splice the point clouds of various perspectives into the complete point cloud data. Point cloud registration is an important and difficult part of reverse engineering. The registration degree between point clouds will directly affect the accuracy of the whole 3D model, so point cloud registration has become a research hotspot in the field of point cloud processing.

Point cloud registration includes manual registration, instrument dependent registration and automatic registration, point cloud automatic registration algorithm is usually used. Automatic registration of point cloud is to calculate the dislocation between two groups of point clouds by algorithm, so as to achieve the purpose of automatic registration of point clouds. From the process of registration, it can be divided into two schemes: initial registration and accurate registration. The initial registration provides the initial transformation matrix for the accurate registration. The accurate registration is the secondary registration based on the initial transformation matrix, which can get more accurate solution and improve the final registration accuracy. Common registration algorithms include ICP algorithm[1], NDT algorithm[2], SAC-IA algorithm, etc. Among them, the accurate registration has been basically fixed to use ICP algorithm and various improved algorithms[3]∼[8]. ICP algorithm has high accuracy, but it has strict requirements on the initial matrix. The results of the initial registration are not ideal, which will seriously affect the performance of the algorithm, so that the iteration cannot converge to the global optimal registration results, and even lead to the local optimal situation. Therefore, the initial registration algorithm is also very important in the registration process Important.

In this paper, SAC-IA algorithm and ICP accurate registration algorithm based on three different descriptors are selected to perform initial registration and accurate registration for two groups of point cloud data collected from different angles. Finally, the experimental results are compared to compare the advantages and disadvantages of several different descriptors in the initial registration algorithm and accurate registration algorithm, and the descriptor more suitable for SAC-IA algorithm and ICP algorithm are selected.

The principle of point cloud registration algorithm is to match the source point cloud Q to the reference system of the target point cloud P through the transformation matrix, that is, P = R * Q + T, where R is the rotation transformation matrix and T is the translation transformation matrix. The essence of point cloud registration algorithm is the process of solving R and T. The specific implementation steps are as follows:

Step 1. Extract key points from two sets of point cloud data sets according to the same key point selection criteria;

Step 2. Calculate the feature descriptors of all the selected key points;

Step 3. Combined with the coordinate position of the feature descriptors in the two sets of point cloud data sets, based on the similarity of the features and positions between the two sets of point cloud data sets, the corresponding relationship between them is estimated, and the corresponding point pairs are preliminarily estimated;

Step 4. For the noise problem of point cloud data, remove the wrong corresponding point pairs that have influence on registration;

Step 5. Use the residual correct correspondence to estimate the rigid body transformation and complete the registration.

The initial registration is to prepare for the subsequent accurate registration. The initial registration is carried out for two pieces of point clouds, and the initial values of translation matrix and rotation matrix are calculated. Then the point cloud data to be registered is transformed into a unified coordinate system, providing a better initial position for accurate registration.

For the rough estimation of the initial transformation matrix, greedy initial registration method has a lot of work, using the point cloud data rotation invariant feature, and the computational complexity is high, so it is necessary to check all possible correspondence of the feature descriptors; in addition, greedy algorithm may fall into the local optimal solution. Therefore, for the initial registration method of point cloud, we usually choose the sampling consistency method to try to maintain the geometric relationship of the same correspondence, rather than trying to understand all combinations of finite correspondence. Sample Consistence Initial Alignment (sAC-IA for short) algorithm takes a large number of samples from the candidate correspondence, and quickly finds a good transformation by looking at a large number of correspondences. Until the best rotation and translation errors are obtained and stored.

In the initial registration algorithm of point cloud, 3D point cloud feature description and extraction is the most basic step, and also the most critical part of the initial registration algorithm of sampling consistency. sampling consistency registration algorithm is based on local feature description. This chapter mainly realizes the initial registration algorithm of sampling consistency based on three descriptors: 3D shape content descriptors, point feature histogram descriptors and fast point feature histogram descriptors, the optimal results of the initial registration algorithm are obtained by experiments.

A.

3D shape context

3D shape context (3dsc for short) uses a vector to describe the shape features of the specified points and their fields on the surface, and establishes the corresponding relationship between the points of different surfaces by matching the values of the vector, which is the descriptor of the specified points. 3Dsc descriptors are simple in structure, strong in discrimination and insensitive to noise. The construction method is as follows: in the spherical support domain with designated point P as the center, the grid is divided into three coordinate directions: radial direction, direction angle and pitch angle, the number of points falling into the grid is counted, and the vector V is constructed. Each element of V corresponds to a grid in the support domain. The value of the element is the number of points in the corresponding grid. The vector V is the descriptor of point P[10]. 3Dsc grid division is shown in Fig. 1.

Figure 1.

B.

Point Feature Histograms

Point Feature Histograms (PFH for short) refer to the spatial differences between query points and neighboring points by parameterization, and form a multi-dimensional histogram to describe the neighbor geometric properties of point k. The high-dimensional hyperspace of histogram provides a measurable information space for feature representation, which is invariant to the 6-dimensional pose of the corresponding surface of point cloud, and robust under different sampling density or neighborhood noise level. PFH representation is based on the relationship between points and their k neighbors and their estimated normal, considering all the interactions between normal directions, trying to capture the best change of sample surface to describe the geometric characteristics of samples. Therefore, the synthetic feature hyperspace depends on the quality of the surface discovery estimation of each point. Fig. 2 shows the influence area of PFH calculation of a query point (P_q). P_q is marked in red and placed in the middle of the ball. The radius is r, and all K-neighbor elements of P_q (all points whose distance from point P_q is less than radius r) are all connected in a network. The final PFH descriptor get histogram by calculating the relationship between all two points in the domain.

Figure 2.

C.

Fast Point Feature Histograms

Fast point feature histograms[11](FPFH for short) is a feature descriptor based on the normal angle between points and their neighbors and the angle between the lines between points. It is an improved algorithm by PFH, which retains the main geometric characteristics of point-to-point description in PFH, and reduces the computational complexity from O(nk²) to O(nk), where n is the number of points in the point cloud data, and k is the number of neighbors considered when calculating the eigenvector of each point.

For a persistent query point P_q, FPFH first uses the pairing between P_q and its neighborhood points (represented by the red line in Fig. 3) to estimate its Simplified Point Feature Histograms (SPFH) value. Compared with the standard calculation of PFH, FPFH has less inter neighborhood interconnection. All points in the point cloud data set need to calculate and obtain SPFH, and calculate the weight according to the SPFH value of the adjacent point of P_q point and the SPFH value of P_q point, and finally get the FPFH value of P_q point. For the calculation connection pairs added in FPFH calculation, the black line in Fig. 3 indicates that some important point pairs (points directly connected with P_q points) are represented by repeated cardinality twice (the thick line in Fig. 3 indicates), and other connected points are represented by thin black line.

Figure 3.

D.

Experimental Verification

In this experiment, the classic Bunny point cloud model of Stanford University (as shown in Fig. 4 (a)) is used to compare the efficiency and accuracy of the three algorithms. Finally, the tooth point cloud collected by the laboratory point cloud acquisition equipment (as shown in Fig. 4 (b)) is registered to verify the feasibility of the algorithm comparison results. In Fig. 4, the green point cloud is the source point cloud and the red point cloud is the target point cloud. In Bunny point cloud model, the number of source point cloud is 40256, and the number of target point cloud is 35336; the number of tooth point cloud data source point cloud collected in laboratory is 140450, and the number of target point cloud is 145366.

Figure 4.

The general evaluation standard of point cloud registration is LCP (Largest Common Pointset). That is to say, given two groups of point set P and Q, a transformation T (P) is found, which makes the maximum overlap of P and Q after transformation. If there is another Q point in the tolerance range at any point in the transformed P, it is considered to be a coincidence point. The proportion of coincident points to the number of all points is the degree of overlap. In this paper, the registration accuracy is determined by the rotation and translation errors and distance errors of the registration point cloud relative to the target point cloud on the x-axis, y-axis and z-axis. Compared with LCP, the registration accuracy of the point cloud can be more intuitively expressed. The experimental results of SAC-IA algorithm registration based on 3Dsc, PFH and FPFH feature descriptors are shown in Fig. 5, among them, the red point cloud is the target point cloud, and the blue point cloud is the registered point cloud.

Figure 5.

The registration time, rotation angle error on XYZ axis, translation distance error and distance error between registration point cloud and target point cloud of two sets of bunny point cloud are shown in Table I.

TABLE I

INITIAL REGISTRATION ERROR TABLE

Comparison of registration algorithms	Feature Descriptors
	3Dsc	PFH	FPFH
SAC-IA runtime	417.381 s	22.727 s	8.085 s
x-axis rotation error	0.0400952 °	0.0474209 °	0.0265896 °
y-axis rotation error	0.811471 °	0.758933 °	0.709945 °
z-axis rotation error	-0.740596 °	-0.734409 °	-0.756489 °
x-axis translation error	0.012691 mm	0.007121 mm	0.019262 mm
y-axis translation error	-0.297463 mm	-0.29991 mm	-0.298785 mm
z-axis translation error	-0.192225 mm	-0.194115mm	-0.194264 mm
distance error	0.354395 mm	0.357320 mm	0.356906 mm

In terms of algorithm efficiency, 3Dsc needs to calculate the surface shape characteristics of point cloud, which increases the calculation amount; compared with PFH and FPFH, it takes a long time, and FPFH is an improved algorithm based on PFH, that is, FPFH algorithm is more efficient and takes the shortest time. In terms of algorithm accuracy, the smaller the rotation, translation and distance errors of x-axis, y-axis and z-axis are, the higher the accuracy of the algorithm is. From Table I, it can be seen that the accuracy of 3Dsc algorithm combined with SAC-IA algorithm is higher than that of FPFH and PFH algorithm. Therefore, the experimental results show that the algorithm based on FPPH feature descriptor has the shortest registration time and the highest efficiency, and the algorithm based on 3Dsc feature descriptor has relatively high accuracy.

Through the initial registration, the two sets of point cloud data roughly coincide, but the registration accuracy is still far from the requirements of practical applications. Therefore, accurate registration of point cloud data is required to reduce registration errors. In order to register the two groups of point cloud as much as possible and minimize the error between them, this paper uses the classic Iterative Closest Point (ICP for short) algorithm for accurate registration.

ICP algorithm[12][13] is the mainstream algorithm for 3D model registration. For each point in the source point cloud, an exhaustive search method is used in the target point cloud to search for the closest point as the corresponding point; then the transformation matrix of all corresponding point pairs is registered and aligned, and the source point cloud is finally calculated according to The obtained transformation matrix is transformed. If the measurement error is not considered, the accuracy of the ICP algorithm is affected by the measurement sampling density, and the error value is proportional to the average sampling distance. That is, the higher the sampling density, the higher the accuracy of the stitching.

The basic principle of ICP algorithm is to find the nearest point (P_i, Q_i) in the target point cloud P and source point cloud Q to be registered according to certain constraints, and then calculate the optimal matching parameter rotation matrix R and translation matrix T to minimize the error function. The error function F(R, T) conforms to equation (1).(1)F(R,T)=1n∑i=1n∥Qi−(RPi+T)∥2

Where n is the number of nearest neighbor point pairs, P_i is a point in the target point cloud P, Q_i, is the nearest point corresponding to P_i in the source point cloud Q, R is the rotation matrix, and T is the translation matrix.

A.

Experimental Verification

According to the initial registration results, the point cloud data is accurately registered by the ICP algorithm. The SCA-IA algorithm based on the 3Dsc, PFH, and FPHF feature descriptors combined with the accurate results of ICP is shown in Fig. 6.

Figure 6.

After ICP precise registration, the initial registration time, precise registration time, rotation angle error on XYZ axis, translation distance error, and the distance error between the two point clouds of the registration point cloud and the target point cloud are as follows: Table II.

TABLE II

ACCURATE REGISTRATION ERROR TABLE

Comparison of registration algorithms	Feature Descriptors
	3Dsc	PFH	FPFH
total time	415.765 s	23.804 s	9.094 s
SAC-IA runtime	414.86 s	23.15 s	8.435 s
ICP runtime	0.905 s	0.654 s	0.659 s
x-axis rotation error	0.0141387 °	0.0325149 °	0.0134278 °
y-axis rotation error	0.764633 °	0.721214 °	0.744733 °
z-axis rotation error	-0.758194 °	-0.76543 °	-0.770207 °
x-axis translation error	0.0128116 mm	0.013648 mm	0.015574 mm
y-axis translation error	-0.298834 mm	-0.29914 mm	-0.299785 mm
z-axis translation error	-0.194931 mm	-0.19437 mm	-0.193715 mm
distance error	0.357021 mm	0.357004 mm	0.357266 mm

As can be seen from Table II, in terms of algorithm efficiency, the SAC-IA algorithm based on the FPFH feature descriptor combined with the ICP algorithm is relatively shorter. From the perspective of algorithm accuracy, the registration accuracy of SAC-IA algorithm based on 3DSC, PFH, FPFH feature descriptors and ICP precise registration algorithm is not much different. Therefore, for the dental point cloud model collected in the laboratory, the accuracy of the three descriptors is not much different, but in terms of efficiency, the FPFH descriptor is more suitable for point cloud data with a large amount of data. Therefore, the tooth model is registered using the SAC-IA algorithm based on the FPFH feature descriptor and the ICP precise registration algorithm. The registration result is shown in Fig. 7.

Figure 7.

In this paper, based on the SAC-IA algorithm of 3Dsc, PFH and FPFH, the bunny point cloud is registered, and the efficiency and accuracy of the initial registration algorithm are analyzed and compared. In the initial registration, SAC-IA algorithm based on 3dsc feature descriptor has a relatively high accuracy, but it takes a long time, which is suitable for the registration with a small number of point clouds and high accuracy requirements; SAC-IA algorithm based on FPFH feature descriptor has a high efficiency, which is suitable for the registration with a large number of point clouds and high efficiency requirements. For the accurate registration algorithm, the ICP algorithm of PCL is used in this paper, and the effect is not ideal from the registration results; in addition, the ICP algorithm can be improved to improve the overall accuracy of the registration algorithm.