Laser point cloud series III: Point cloud registration.

Author | Xiao Shaohua

In the first article, “Detailed Analysis of the Processing of LiDAR Point Cloud Data,” and the second article, “Problems and Countermeasures Encountered in LiDAR Point Cloud Processing,” of the LiDAR point cloud series, the author analyzed the processing flow and typical problems and strategies encountered in the point cloud processing links of the LiDAR system respectively. In this article, the author will focus on analyzing the point cloud registration technology in the positioning link of the LiDAR point cloud.

Due to the limitations of the field of view, when real-time point cloud data is collected by the LiDAR, it can only obtain point cloud images within a limited field of view. In order to obtain point cloud data of a three-dimensional scene, perception algorithm personnel need to convert two different point clouds collected before and after into a unified coordinate system based on known initial posture information. They should stitch together the overlapping parts of the point clouds. This is the point cloud registration technology.

The following will analyze in detail what point cloud registration is, the technical methods of point cloud registration, and the problems and strategies faced by point cloud registration.

The Application of Point Cloud Registration in Autonomous Driving

In the past, point cloud registration was mainly used in the construction industry’s building information models (BIM), mining industry’s mining area excavation, and other fields. In the field of autonomous driving, its role mainly includes three aspects: 3D map building, high-precision map positioning, and attitude estimation.

First, 3D map building. When building high-precision maps, the LiDAR system collects adjacent frame point clouds and registers them. This unifies the point clouds collected from different locations into one coordinate system, creating a three-dimensional high-precision map.

Second, high-precision map positioning. When the autonomous driving vehicle is traveling, it needs to achieve precision positioning at the centimeter level. For example, autonomous vehicles need to estimate their precise position on the map and the distance between the vehicle and the roadside. Through point cloud registration technology, the autonomous driving system matches real-time collected point cloud data with high-precision map data to provide an accurate position for the autonomous vehicle.

Third, attitude estimation. The autonomous driving system estimates the relative attitude information of the vehicle by point cloud registration technology, which is conducive to making decision planning for the vehicle.

Working Principle and Technical Methods of Point Cloud Registration### 2.1 Working Principle of Point Cloud Registration

The working principle of point cloud registration is that due to various environmental factors, the LiDAR can only cover a part of the surface of the target object in a single acquisition during point cloud collection. To obtain complete point cloud information of the target object, multiple scans of the target object are required, and the obtained 3D point cloud data is transformed by rigid body transformation of the coordinate system to align the local point cloud data on the target object to the same coordinate system.

In simple terms, the key to point cloud registration is to find the correspondence between the initial point cloud and the target point cloud, then match the original point cloud and the target point cloud through this correspondence, and calculate their feature similarity. Finally, they are unified into one coordinate system.

Figure: 3D mapping of point clouds (Data source: the Internet)

Point cloud registration can usually be divided into two steps: rough registration and fine registration.

Rough registration is the initial registration of point clouds, which refers to aligning two point clouds with different positions as closely as possible through an initial rotation and translation matrix. The mainstream methods of rough registration include RANSAC, 4PCS, and others.

After rough registration, the overlapping parts of the two point clouds can be roughly aligned, but the accuracy is still far from the positioning requirements of autonomous vehicles, and further fine registration is needed.

Fine registration refers to calculating an approximate rotation and translation matrix between two point clouds on the basis of initial registration. The mainstream methods of fine registration include ICP, NDT, deep learning, and others.

2.2 Technical Methods of Point Cloud Registration

The previous section mentioned some specific methods for point cloud registration. Due to differences in the technical level and technical solutions of various autonomous driving companies, they will adopt different methods for point cloud registration. Some companies will adopt only one method in the process of rough or fine registration, while others will use a combination of multiple methods. For example, in the fine registration process, some companies will use the combination of ICP and deep learning. This section will discuss in detail the various methods of point cloud registration mentioned earlier.## 2.2.1 Techniques for Rough Alignment

(1) RANSAC (Random Sample Consensus)

Methodology: This algorithm randomly selects some samples from the given sample set, estimates a mathematical model, and verifies the remaining samples in the mathematical model. If enough error samples are within the given range, the mathematical model is optimal. Otherwise, this step is repeated in a loop.

The RANSAC algorithm was introduced to the field of 3D point cloud registration where it continuously performs a random sample on the source point cloud and calculates the corresponding transformation model. Then, the random transformation model is tested and the process continues until the optimal transformation model as the final result is selected.

Specific Steps:

1) Downsample and filter the point cloud to reduce computational complexity.

2) Extract features based on the downsampled and filtered point cloud data.

3) Use the RANSAC algorithm to obtain an ideal transformation matrix by iterative sampling.

4) Use the obtained transformation matrix to transform the point cloud.

Advantages: Suitable for larger point cloud data volumes, which can achieve rough alignment of point clouds without considering the distance between point clouds.

Disadvantages: There are unstable issues with alignment accuracy.

(2) 4PCS (4-Points Congruent Sets)

Methodology: This algorithm uses the geometric invariance of rigid transformations (such as vector/segment ratios and Euclidean distances between points) and searches for four approximate coplanar points (approximate congruent four-point sets) in the target point cloud and its corresponding points according to the characteristics where the ratio occupied by the intersection of rigid transformation wire segments remains unchanged and the Euclidean distance between points is constant after the rigid transformation. The transform matrix is calculated using the least-squares method, and multiple bases are iteratively selected based on the RANSAC algorithm framework. The optimal transformation is obtained based on the evaluation criteria of the Largest Common Point Set (LCP).

Specific Steps:

1) Search for coplanar four-point bases satisfying the long baseline requirements in the target point cloud that are determined by overlap in the input parameters, where the larger overlap is, the longer the baseline is selected. A long baseline can ensure the matching robustness, and fewer matches are required.

2) Extract the topological information of the coplanar four-point bases and calculate the two proportion factors between them.### 2.2.2 Techniques for accurate registration

(1) ICP (Iterative Closest Point algorithm)

ICP selects the closest points between two point clouds as corresponding points. By iteratively fitting and refining the rigid transformation matrix using the corresponding points, the registration error between two point clouds can be reduced until it meets the pre-set threshold or maximum number of iterations. The specific steps include:

  1. Calculate the closest points in the target point cloud for each point in the source point cloud.
  2. Find the rigid transformation matrix that minimizes the average distances of corresponding point pairs.
  3. Apply the transformation matrix to the source point cloud to obtain a new set of transformed points.
  4. If the average distance between the new transformed point cloud and the reference point cloud is less than a given threshold or the maximum number of iterations is reached, stop the iteration; otherwise, use the new transformed point cloud as the new source point cloud and repeat the iteration until the target function is satisfied.

Advantages:

  1. No need for segmentation or feature extraction of point clouds.
  2. Good convergence performance if the initial position is reasonable.

Disadvantages:

  1. Large computation in the process of searching for corresponding points, leading to slow registration speed.
  2. Certain requirements for the initial position of the point cloud, otherwise the algorithm may converge to a local optimal solution.
  3. ICP assumes the closest points between any two point clouds as corresponding points, which may generate a certain number of wrong correspondences.

(2) NDT (Normal Distribution Transform algorithm)

NDT transforms the point clouds into grids of a specified size and constructs probability density functions for each grid using Gaussian modeling. The optimal transformation parameters are then optimized to maximize the likelihood of the transformed points following the probability density function of the target point cloud, achieving the best alignment between two point clouds.

Advantages:

  1. No need for segmentation or feature extraction of point clouds.
  2. Robust and accurate performance, especially for datasets with significant changes in overlapping regions.

Disadvantages:

  1. Requires a large amount of computation in the process of optimizing the transformation parameters.
  2. Sensitivity to hyperparameters such as the size of the grid and the number of iterations.
  3. May suffer from local optimal solutions if the initial position is not reasonable.

3) Calculate the four possible intersection points and determine the matching set based on comparing their coordinates. Find the consistent and identical four points. Then calculate the coordinates of the intersection points for all point pairs with medium to long baselines.

4) Find all sets of coplanar four points in the point cloud and repeat the previous steps to obtain the optimal set of consistent and identical four points for registration.

Advantages:

Applicable for point cloud registration in scenarios with small overlapping regions or significant changes in overlapping regions without preprocessing or noise reduction of input data.

Disadvantages:

Not suitable for engineering applications.Steps:

1) Divide the space into cells (also called voxels) of a voxel grid.

2) Project the reference point cloud into each of these cells.

3) Based on the points in the cell, calculate the parameters of the cell’s probability density function (PDF).

4) Transform each point of the second point cloud according to the transformation matrix.

5) Determine which cell of the reference point cloud the point from the second scan falls into and calculate the corresponding probability distribution function (PDF).

6) Maximize the likelihood function to obtain the optimal transformation parameters.

Advantages:

1) It does not require high accuracy of initial registration, even if the initial value error is large, it can still perform well.

2) It does not require feature matching between point clouds, avoiding problems that may arise in feature matching, such as point cloud noise, object motion, and influence of point cloud overlap on feature matching.

Disadvantages:

1) It requires high voxel grid size demand. Too large voxel grid size reduces the registration accuracy, while too small voxel grid size increases the computing load.

2) The registration accuracy is slightly lower than that of the ICP algorithm.

(3) Point cloud registration based on deep learning

Apart from its application in perception, deep learning is also applied to the point cloud registration stage of localization.

Based on deep learning, point cloud registration refers to using a deep learning model to extract the features of the original point cloud and obtain the initial configuration value of the point cloud, and then perform accurate registration based on the features. In recent years, common point cloud registration methods based on deep learning include PointNetLK, Deep ICP, DCP, PRNet, IDAM, RPM-Net, 3DRegNet, DGR, among others.

Compared with other traditional registration methods (such as ICP and NDT), deep learning-based methods can speed up the calculation and learn higher-level features, achieving higher robustness.

Based on whether the structure of the registration method is entirely composed of deep neural networks or whether some components of non-deep learning registration methods are replaced with deep learning-based networks, learning-based point cloud registration methods can be divided into partially deep learning-based methods and end-to-end deep learning methods.

Partially deep learning-based point cloud registration methods directly replace a component of non-deep learning-based registration methods with a deep learning component, which may bring improvement in speed or robustness to the original algorithm. The largest advantage of partially-based learning methods lies in their flexibility.## End-to-End Point Cloud Registration

End-to-end point cloud registration method refers to that the input of point cloud to the final registration result is achieved in a complete network. End-to-end point cloud registration method can maximize the efficiency and intelligence of deep learning methods, and also make better use of the parallel computing capability of GPUs, resulting in faster calculation speed.

Currently, the application of point cloud registration technology in the autonomous driving industry is still in the early stage. A perception algorithm engineer of an autonomous driving company said, “The point cloud registration based on deep learning is still in its early stages, and its accuracy cannot be guaranteed. Moreover, the application combining traditional methods such as ICP also requires a lot of computation time.”

Problems and Countermeasures of Point Cloud Registration

3.1 Problem of Too Many Point Clouds during Registration and Countermeasures

Currently, the data on the car is uploaded to the cloud for processing. However, on the one hand, the cost of data transmission is very high, and on the other hand, the real-time processing of data cannot be achieved, which makes it difficult to guarantee the safety of autonomous driving vehicles. Therefore, it is necessary to complete the data processing on the car.

The existing computing power of mass-produced cars is limited and cannot directly process large amounts of point cloud data, which has become a major obstacle in point cloud registration. The main solution to this problem is point cloud simplification.

Point cloud simplification refers to the removal of useless point clouds from the target point cloud dataset. There are mainly two ways to achieve this:

1) Removing redundant means removing data from some redundant areas after data registration. This part of data has a large data volume and is mostly useless data, which has a great influence on the speed and quality of modeling.

2) Subsampling simplification means that because the point cloud data obtained by the LiDAR scanning is too dense and the quantity is too large, some of the data is not useful for later modeling. Therefore, this part of data needs to be simplified while ensuring a certain accuracy and maintaining the geometric characteristics of the measured object, in order to improve the actual computational speed, modeling efficiency, and model accuracy.

3.2 Problem of Initial Point Cloud Registration and Countermeasures

As mentioned earlier, initial registration, also called coarse registration, is a key point in point cloud registration. Generally, the initial value of registration is obtained through IMU and vehicle speed data, but the efficiency of point cloud initial registration in the industry is not high.

Improving the efficiency of initial registration can reduce the rotation and translation errors between point clouds under different perspectives, and can also improve the overall success rate and efficiency of point cloud registration.

ICP and NDT algorithm

For ICP algorithm, the accuracy of the initial registration value will have a significant impact on the accuracy of the algorithm. For NDT algorithm, improving the efficiency and quality of initial registration can also enhance the registration accuracy of NDT algorithm.

So, how do technicians improve the efficiency of point cloud initial registration in the field of autonomous driving?

One is to extract target key points. Tang Qiang, a perception algorithm engineer at FutureEye, said: “To improve the initial registration of point clouds, the most direct method is to select a key target, such as a car, and then select several key points from this key target to make rotation and translation matrices.”

The other is feature extraction, such as FPFH (fast point feature histogram). Dr. Xu Jian, the head of TuDaTong algorithm, said: “Different from ICP and NDT algorithms, point cloud registration methods based on feature extraction can improve the speed and accuracy of point cloud registration. By extracting some features (such as edges or lines and surfaces), it uses the spatial topological structure between the two point clouds to match the point clouds. In addition, online point cloud registration technologies such as data association and system bias estimation are also very important in practical engineering applications.”

3.3 Problems and countermeasures of homogeneous point cloud registration

Homogeneous point cloud registration refers to the point cloud registration performed on point cloud data obtained from sensors of the same type but generated at different times and views.

In addition to a main LiDAR sensor, self-driving vehicles may also be equipped with some supplementary LiDAR sensors or adopt a scheme of two or more main LiDAR sensors. These LiDAR sensors collect point clouds that belong to homogeneous point cloud data, but due to the time and perspective differences in the acquisition from different LiDAR sensors, some issues may arise in point cloud registration.

On one hand, point cloud data obtained from multiple LiDAR sensors at different angles have different three-dimensional coordinate systems, and the coordinate system where the noise points are located is also different. To achieve more accurate registration effects, point cloud data needs to be unified into one coordinate system.

Xu Jian said: “To unify the point clouds collected by multiple LiDAR sensors into the same coordinate system, multi-target point cloud registration in joint calibration will bring more information than single-target point cloud registration, making the registration accuracy higher. For a single target, when the LiDAR scans the object, the edge point clouds of the target may be incomplete, which will affect the accuracy of registration. For multi-targets, more point cloud information will be collected from LiDAR sensors. For example, when the target is static, topological structure information will be formed between multiple targets, making the information of point cloud initial registration richer and more conducive to improving the overall registration accuracy.”On the other hand, hardware performance indicators may differ among different LiDARs which can cause different numbers of point clouds covering the same target surface. Tang Qiang stated that “LiDARs with different performance have different angular resolution parameters, which means different point cloud densities, resulting in the final effect of point cloud registration being affected. To address the difference in point cloud density, perceptual algorithm personnel can apply point cloud simplification methods to reduce the parameters of LiDARs with high point cloud densities, or adjust them from the hardware perspective. For example, technicians may adjust the angular resolution of two LiDARs to the same level.”

3.4 Problems and Countermeasures for Cross-Source Point Cloud Registration

Cross-source point cloud registration refers to the registration of point clouds from different types of sensors. Its advantage is to combine the advantages of multiple types of sensors to provide more abundant 3D point cloud information for the autonomous driving system. Compared with same-source point cloud registration, cross-source point cloud registration is still in the academic stage, and its application in the field of autonomous driving is also in the pre-research stage.

A technical expert from an autonomous driving solution provider stated that “cross-source point cloud registration is one of the main challenges of future point cloud registration technology.”

Specifically, due to the different working principles between different types of sensors, the resolution, density quality, image scale, distance information, etc. of the point cloud between sensors will differ, increasing the technical difficulty of cross-source point cloud registration.

For example, in the case of 4D imaging radar and LiDAR, although 4D imaging radar can generate point cloud data like LiDAR, the point cloud density of 4D imaging radar may only be able to reach that of some low line-number LiDARs (such as 16 lines, 32 lines, etc.), and cannot achieve the point cloud density of high line-number LiDARs (such as 128 lines). In addition, in terms of angular resolution parameters, 4D imaging radar can only approach the parameter level of 1°, while some LiDARs can achieve a level of 0.1°. When the two sensors scan the same object surface, the point cloud data they collect will also be different. For example, in point cloud data of a vehicle in the far distance, the point cloud quality of the LiDAR may be better than that of the 4D millimeter wave (the former has more energy return and more point clouds), which results in the decrease of registration accuracy.

In the current academic research, there are many methods for cross-source point cloud registration, but they are mainly applied in the fields of augmented reality and building construction, and there are almost no corresponding applications in the field of autonomous driving. The following figure shows some methods for cross-source point cloud registration that the author has compiled. For example, CSGM transforms the registration problem into a graph matching problem and uses graph matching theory to overcome the problem of cross-source point cloud registration. FMR explores the application of deep learning in cross-source point cloud registration.“`
Figure: Cross-source point cloud registration method (data source: "Comprehensive review of point cloud registration in 2021")

References

[1] Point cloud registration, the “blood relationship” in autonomous driving.
https://mp.weixin.qq.com/s/xjg0UOqOsukgx1swxBKwHA

[2] Comprehensive review of point cloud registration in 2021.
https://mp.weixin.qq.com/s/SOtHePcis9S9hpN1oqP9Ug

[3] RANSAC algorithm ideas and implementation for point cloud rough registration.
https://blog.csdn.net/qq_42537872/article/details/126069525

[4] 3D point cloud registration algorithm – 4PCS (4-point congruent sets registration algorithm).
https://blog.csdn.net/weixin_42755079/article/details/126638986

[5] ICP point cloud registration algorithm.
https://blog.csdn.net/

[6] Point cloud registration ICP&NDT.
https://blog.csdn.net/weixin_49024732/article/details/124794910

[7] Learning-based point cloud registration method.
https://zhuanlan.zhihu.com/p/501503130
“`

This article is a translation by ChatGPT of a Chinese report from 42HOW. If you have any questions about it, please email bd@42how.com.