https://ift.tt/pdNwxEA Point Cloud Registration: Classic Approaches Introduction to Iterative Closest Point (ICP) and Coherent Point Drift...
Point Cloud Registration: Classic Approaches
Introduction to Iterative Closest Point (ICP) and Coherent Point Drift (CPD) Methods
In my work as an algorithm developer, I use point clouds as 3D representation to solve several problems. Some of my projects required aligning two sets of points with one another, which is not trivial.
This problem is called Point Cloud registration. Given several sets of points in a different coordinate system, the goal of the registration is to align them one to another. The alignment is done by finding a transformation that minimizes the difference between them.
Like many computer vision tasks, the registration problem is not easy and has many challenges. For example, in some real-world scenarios, the point clouds have different densities and limited overlap. In other scenarios, the point sets may be symmetric or incomplete. Those examples affect the accuracy and efficiency of the results. Extensive studies have been done to improve point cloud registration accuracy, efficiency, and robustness.
In this post, I will describe the two main classic and popular suggested approaches.
Iterative Closest Points (ICP)
Given two sets of points P and Q, ICP optimizes the rigid transformation to align P with Q:
The ICP starts with an initial alignment and iterates between two steps -
- The correspondence step — find the closest point q_i in Q for each point p_j in P.
- The alignment step — update the transformation by minimizing the L2 distance between the corresponding points.
This is a simple and straightforward algorithm for both understanding and implementation. At the same time, it also has several limitations.
Limitations of the ICP Algorithm
- The accuracy of the results strongly relies on a good initial alignment.
- Tends to converge to local minima.
- Sensitive to outliers and partial overlaps.
- Works only with rigid transformations.
Much research was done in this area and many variants were proposed to the ICP algorithm to tackle the limitations above.
A different family of registration methods is probabilistic ones. These methods use soft-assignment of correspondences, which means assigning correspondences between all points according to some probability. This is in contrast to the ICP algorithm which uses binary assignments. One example of such an algorithm is the Coherent Point Drift (CPD).
Coherent Point Drift (CPD)
Coherent point drift is a probabilistic approach for the registration problen, which works on both rigid and non-rigid transforms. As the authors explain in the original paper³:
“The alignment of two point sets is considered a probability density estimation problem. One point set represents the Gaussian Mixture Model (GMM) centroids, and the other one represents the data points. The registration is done by fitting the GMM centroids to the data by maximizing the likelihood.”
The CPD is more robust to noise, outliers, and missing points than ICP.
Limitations of the CPD Algorithm
- An assumption about the amount of noise and outliers is used. Incorrect assumptions will lead to poor registration.
- For data with density variations, the registration tends to converge to a local extremum (local minimum or local maximum)
Summary
The registration task is a popular task in the computer vision field. Most methods rely on finding correspondences between the two point clouds. Two main approaches are suggested—hard correspondences like those used in ICP, and soft-assignment of correspondences like those used in CPD. Each method has many different variants with different pros and cons.
Which one is the best for you? It depends on your data, whether you need a rigid or non-rigid method, the amount of noise and outliers, density variations, and more. As I mentioned before, a lot of variants exist to those methods. I recommend finding the one that best suits your task and data.
References
This is the list of papers I used for this post. You can read them for more information.
- Iterative Global Similarity Points: A Robust Coarse-to-Fine Integration Solution for Pairwise 3D Point Cloud Registration
- Fast and Robust Iterative Closest Point
- Point Set Registration: Coherent Point Drift
- A refined coherent point drift (CPD) algorithm for point set registration - Science China Information Sciences
- Density-Adaptive and Geometry-Aware Registration of TLS Point Clouds Based on Coherent Point Drift
Point Cloud Registration — Classic Approaches was originally published in Towards Data Science on Medium, where people are continuing the conversation by highlighting and responding to this story.
from Towards Data Science - Medium https://ift.tt/GpCorT0
via RiYo Analytics
No comments