Laser point cloud series three: point cloud registration

In the first article "Detailed Explanation of the Processing Process of Lidar Point Cloud Data" and the second article "Problems and Countermeasures Encountered in Lidar Point Cloud Processing" in the laser point cloud series, the author analyzed the point cloud processing of Lidar respectively. Typical problems and countermeasures encountered in the process and point cloud processing. In this article, the author will focus on analyzing the point cloud registration technology of laser point cloud in the positioning process.

Due to the limitation of the field of view, when lidar collects point cloud data in real time, it can only obtain point cloud images within a limited field of view. In order to obtain the point cloud data of the three-dimensional scene, the perception algorithm personnel need to convert the different point clouds collected in the two frames before and after the collected frame into a unified coordinate system under the known initial attitude information, and splice the overlapping parts of the point clouds together—— This is point cloud registration technology.

The following will analyze one by one what point cloud registration is, the technical methods of point cloud registration, and the problems and countermeasures faced by point cloud registration.

01. Application of point cloud registration in autonomous driving

Point cloud registration was previously mainly used in Building Information Modeling (BIM) in the construction industry, mining areas in the mining industry, etc., and its role in the field of autonomous driving mainly falls into three categories: three-dimensional map construction, high-precision map positioning, Pose estimation.

First, three-dimensional map construction. When building a high-precision map, the autonomous driving system performs point cloud registration on adjacent frame point clouds collected by lidar, unifies the point clouds collected at different locations into one coordinate system, and then constructs a three-dimensional high-precision map. Precision map.

Second, high-precision map positioning. When a self-driving vehicle is driving, the vehicle needs to achieve centimeter-level precise positioning. For example, a self-driving vehicle needs to estimate its precise location on a map and its distance from the road curb. The autonomous driving system uses point cloud registration technology to match point cloud data collected in real time with high-precision map data to provide accurate positioning for autonomous vehicles.

Third, pose estimation. The autonomous driving system uses point cloud registration technology to estimate the relative attitude information of the vehicle, and then facilitates decision-making and planning for the vehicle.

02. Working principles and technical methods of point cloud registration

2.1 How point cloud registration works

The working principle of point cloud registration is that due to the limitations of lidar due to various factors such as the environment, the point cloud collected in a single time during the point cloud collection process can only cover a part of the target surface. In order to obtain a complete target point cloud To obtain information, it is necessary to scan the target object multiple times, perform rigid body transformation of the coordinate system on the obtained three-dimensional point cloud data, and convert the local point cloud data on the target object to the same coordinate system.

In layman's terms, the key to point cloud registration is how to find the correspondence between the initial point cloud and the target point cloud, and then use this correspondence to match the original point cloud and the target point cloud, and calculate their characteristics. The similarity is finally unified into one coordinate system.

Point cloud registration can usually be divided into two steps, namely coarse registration and fine registration.

Coarse registration, that is, the initial registration of point clouds, refers to aligning two point clouds with different positions as much as possible through the initial value of a rotation and translation matrix. Mainstream methods of coarse registration include RANSAC, 4PCS, etc.

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

Fine registration refers to further calculating the approximate rotation and translation matrices of two point clouds based on the initial registration. Mainstream methods of precision registration include ICP, NDT, deep learning, etc.

2.2 Technical methods of point cloud registration

Some specific point cloud registration methods are mentioned above. Since each autonomous driving company has different technical levels and technical solutions, they will use different point cloud registration methods - some companies will use coarse registration or fine registration. Only one method is used in the registration process, and some companies use a combination of methods. For example, in the precise matching process, some companies will use ICP + deep learning. This chapter will discuss in detail the above point cloud registration methods.

2.2.1 Technical methods of coarse registration

(1) RANSAC (RAndom SAmple Consensus, random sampling consistent)

Method principle: This algorithm randomly selects some samples from a given sample set and estimates a mathematical model, and brings the remaining samples in the sample into the mathematical model for verification. If there are enough sample errors within the given range, then the The mathematical model is optimal, otherwise the cycle continues.

The RANSAC algorithm was introduced into the field of 3D point cloud registration. Its essence is to continuously sample random samples from the source point cloud and find the corresponding transformation model. Then, it tests each random transformation model, and continuously loops this process until it is selected. The optimal transformation model is used as the final result.

Specific steps:

1) Downsample and filter the point cloud to reduce the calculation amount of the point cloud.

2) Feature extraction is performed based on the point cloud data after downsampling and filtering.

3) Use the RANSAC algorithm for iterative sampling to obtain a more ideal transformation matrix.

4) Use the obtained transformation matrix to perform point cloud transformation operations.

Advantages: It is suitable for large amounts of point cloud data, and can achieve coarse registration of point clouds without considering the distance between point clouds.

Disadvantages: There is the problem of unstable registration accuracy.

(2) 4PCS (4-Points Congruent Sets, congruent four-point sets)

Method principle: This algorithm uses the geometric invariance in rigid body transformation (such as vector/line segment ratio, Euclidean distance between points), and based on the invariant proportion of line segments occupied by intersection points after rigid transformation and the Euclidean distance between points Invariant characteristics, try to find 4 approximately coplanar points (approximately congruent four point sets) corresponding to them in the target point cloud, and then use the least squares method to calculate the transformation matrix, and iteratively select multiple groups of basis based on the RANSAC algorithm framework , the optimal transformation is obtained by comparison according to the evaluation criterion of the largest set of common points (LCP).

Specific steps:

1) Find a coplanar four-point basis in the target point cloud set that meets the long baseline requirements (the determination of the baseline has a great relationship with the overlap in the input parameters. The larger the overlap, the longer the baseline selection, and the long baseline can ensure robust matching . sex , and the number of matches is small).

2) Extract the topological information of the coplanar four-point basis and calculate the two scaling factors between the four-point basis.

3) Calculate four possible intersection positions, and then calculate the intersection coordinates of all medium and long baseline point pairs, compare the intersection coordinates and determine the matching set, and find the corresponding four congruent points.

4) Find all coplanar four-point sets in the point cloud. Repeat the above steps to obtain the congruent four-point set, and find the optimal congruent four-point pair.

Advantages: It is suitable for point cloud registration in scenes with small overlapping areas or large changes in the overlapping areas. There is no need to pre-filter and denoise the input data.

Disadvantages: Not suitable for engineering applications.

2.2.2 Technical methods of precision registration

(1) ICP (Iterative Closest Point, closest point iteration method)

Principle of the method: Select the closest point in the two point clouds as the corresponding point, solve the rotation and translation transformation matrices through all corresponding point pairs, and make the registration error between the two point clouds smaller and smaller through continuous iterations , until the threshold requirements or the number of iterations we set in advance are met.

Specific steps:

1) Calculate the corresponding close point of each point in the source point cloud in the target point set.

2) Find the rigid body transformation that minimizes the average distance between the above corresponding point pairs, and find the translation parameters and rotation parameters.

3) Perform spatial transformation on the obtained translation and rotation matrices to obtain a new transformation point set.

4) If the new transformation point set and the reference point set satisfy that the average distance between the two point sets is less than a given threshold, or the number of iterations reaches the set maximum value, the iterative calculation will stop, otherwise the new transformation point set will be used as the new The source point cloud continues to iterate until the requirements of the objective function are met.