Point-set registration

3D point clouds can also be generated from computer vision algorithms such as triangulation, bundle adjustment, and more recently, monocular image depth estimation using deep learning.

Point cloud registration has extensive applications in autonomous driving,[1] motion estimation and 3D reconstruction,[2] object detection and pose estimation,[3][4] robotic manipulation,[5] simultaneous localization and mapping (SLAM),[6][7] panorama stitching,[8] virtual and augmented reality,[9] and medical imaging.

In this article, we will only consider algorithms for rigid registration, where the transformation is assumed to contain 3D rotations and translations (possibly also including a uniform scaling).

More recently, Briales and Gonzalez-Jimenez have developed a semidefinite relaxation using Lagrangian duality, for the case where the model set

Maximum consensus seeks to find the largest set of correspondences that are consistent with the generative model (cb.1) for some choice of spatial transformation

The algorithm terminates either after it has found a consensus set that has enough correspondences, or after it has reached the total number of allowed iterations.

RANSAC is highly efficient because the main computation of each iteration is carrying out the closed-form solution in Horn's method.

[20] To fill the gap between the fast but inexact RANSAC scheme and the exact but exhaustive BnB optimization, recent researches have developed deterministic approximate methods to solve consensus maximization.

[21][22][27][23] Outlier removal methods seek to pre-process the set of highly corrupted correspondences before estimating the spatial transformation.

[20] GORE has been shown to be able to drastically reduce the outlier ratio, which can significantly boost the performance of consensus maximization using RANSAC or BnB.

Therefore, using efficient algorithms for computing the maximum clique of a graph can find the inliers and effectively prune the outliers.

[4] The maximum clique based outlier removal method is also shown to be quite useful in real-world point set registration problems.

the least squares loss), algorithms for solving the non-convex M-estimation are typically based on local optimization, where first an initial guess is provided, following by iterative refinements of the transformation to keep decreasing the objective function.

[33] Using Black-Rangarajan duality and GNC tailored for the Geman-McClure function, Zhou et al. developed the fast global registration algorithm that is robust against about

Very recently, Yang et al. has developed the first certifiably robust registration algorithm, named Truncated least squares Estimation And SEmidefinite Relaxation (TEASER).

[36] The algorithm performs rigid registration in an iterative fashion by alternating in (i) given the transformation, finding the closest point in

In pseudocode, the basic algorithm is implemented as follows: Here, the function least_squares performs least squares optimization to minimize the distance in each of the

[37] Nonetheless, because ICP is intuitive to understand and straightforward to implement, it remains the most commonly used point set registration algorithm.

[37] Many variants of ICP have been proposed, affecting all phases of the algorithm from the selection and matching of points to the minimization strategy.

chosen for point set registration is typically symmetric and non-negative kernel, similar to the ones used in the Parzen window density estimation.

Unlike the ICP and related methods, it is not necessary to find the nearest neighbour, which allows the KC algorithm to be comparatively simple in implementation.

Compared to ICP and EM-ICP for noisy 2D and 3D point sets, the KC algorithm is less sensitive to noise and results in correct registration more often.

[13][41] The algorithm takes a probabilistic approach to aligning point sets, similar to the GMM KC method.

To preserve the topological structure of the point sets, the GMM centroids are forced to move coherently as a group.

is defined as the posterior probability of the GMM centroid given the data point: The expectation maximization (EM) algorithm is used to find

such that the aligned point set is: The solve_affine function for rigid registration can then be written as follows, with derivation of the algebra explained in Myronenko's 2010 paper.

The point cloud registration is formulated as a maximum likelihood estimation (MLE) problem and solve it with the Expectation-Maximization (EM) algorithm.

In the M step, an unconstrained optimization on a matrix Lie group is designed to efficiently update the rigid transformation of the registration.

Taking advantage of the local geometric covariances, the method shows a superior performance in accuracy and robustness to noise and outliers, compared with the baseline CPD.

[47] These types of images tend to have high amounts of noise, so it is expected to have many outliers in the point sets to match.

Point set registration is the process of aligning two point sets. Here, the blue fish is being registered to the red fish.
Data from two 3D scans of the same environment need to be aligned using point set registration.
Data from above, registered successfully using a variant of iterative closest point.
Registered point cloud from a lidar mounted on a moving car.
Animation of 2D non-rigid registration of the green point set to the magenta point set corrupted with noisy outliers. The size of the blue circles is inversely related to the control parameter . The yellow lines indicate correspondence.
Rigid (with the addition of scaling) registration of a blue point set to the red point set using the Coherent Point Drift algorithm. Both point sets have been corrupted with removed points and random spurious outlier points.
Affine registration of a blue point set to the red point set using the Coherent Point Drift algorithm.
Non-rigid registration of a blue point set to the red point set using the Coherent Point Drift algorithm. Both point sets have been corrupted with removed points and random spurious outlier points.