Fast Area Certification Method For Point Cloud Registration

A project of the Robotics 2020 class of the School of Information Science and Technology (SIST) of ShanghaiTech University. Course Instructor: Prof. Sören Schwertfeger.

Chengzhang He


We propose a fast area certification algorithm to limit the searching region of point cloud registration problem.This algorithm is robust to 2D and 3D point cloud data.The speed of this area certification for the registration of two sets of points clouds is irrelevant to its parameters.

An area certification algorithm is one that attempts to find whether the answer of optimization problem is located in bounding box.By splitting the searching area of Rotation and Translation,the final result is restricted in some small areas.This algorithm can be used to initially reduce search area.

We provide two different algorithms,one using invariant measurement of feature and another using original feature. The searching for translation using a technique called rotation invariant measurement.

The optimization problem to certificate is conseus maximization problem, which is an NP problem and could be checked in polynomial time.In 2D part,the area certification algorithm is using the group structure of it.In 3D part,we use a group structure to approximately represent the points on 2 dimension spherecal.

The techniques of area certification is related to rotation search and interval caculation.

We test their performance of our algorithm on standard benchmarks and 2D SLAM.It averagely speed up 15 percent of GO-ICP.


The Iterative closest point algorithm is a fundamental method for point-set registration problem.Based on local iterative optimization, ICP can reach a local minimum.

As local minimum might not match the ground-truth in SLAM area,

there should be some methods to find a global minimum and produce reliable registration results regardless of initialization. Obviously, in most area,ICP will give a big error that far away from the ground-truth,and such distance can be bounded by information given by the features of several boundings.

Point-Set registration is one of the most important part in SLAM. The Lidar or the pose information given by camera gives some sets of points and point data registration aims at matching these two set of points. The close-loop or data fusion all relies on the result of point data registration.

Non-linear least square is relating to maximum likelihood in sense of Gaussian noise but:

1. Feature may not be Gaussian

2. Don’t know the bound after getting optimized value.

Consensus maximization is more friendly to set approaches and meaningful to result.

1. Setting how much points overlaped

2. Setting upper bound

System Description