Point set registration

1 Problem statement
2 Iterative closest point
3 Improvements
1. 3.1 Soft correspondences
2. 3.2 Initialization using RANSAC
4 References

Point set registration means to align two sets of points. For example, stars in the night sky.

FIGURE 1 The Big Dipper, seen from Kauai (left) and from Suffolk (right). (Image credit: Gh5046 and Maxiesnax).

We would like to align the two images and find out which stars are the same ones. Unfortunately, all the stars look very similar, and we don’t know which ones correspond to which other ones. Below is a demo of an algorithm that solves this problem. The algorithm automatically moves the orange red points to align with the periwinkle blue ones on the right (the light grey lines connect the original orange red point to its moved counterpart). Click or tap to add more points.

1 Problem statement

Given two sets of points, the moving (model) point cloud $\mathcal M$ and the static (scene) point cloud $\mathcal S$ , we want to move $\mathcal M$ to $\mathcal S$ such that they line up properly.

This problem arises in many interesting topics:

A robot trying to map out the world using a laser rangefinder
A surgeon trying to find out where someone’s lumbar spine is using an ultrasound scanner
A computer trying to read
Stabilizing videos or image sequences, e.g. of a Pluto flyby.
Figuring out where you are by looking at the stars

2 Iterative closest point

The simplest and most well-known point set registration algorithm is iterative closest point (ICP). It operates in two steps:

Assign every point in $\mathcal M$ to the nearest point in $\mathcal S$ .
Using least squares, minimize the sum of squares of distances between corresponding points.

These two steps are repeated until convergence. Unfortunately, there are a bunch of problems.

It requires a good initial guess. Even then, it is prone to getting stuck in a local minima.
There might be missing points in $\mathcal S$ , so not all points would have a correspondence.

3 Improvements

The implementation shown in the demo makes some improvements to ICP in order to deal with the drawbacks of iterative closest point.

3.1 Soft correspondences

Soft correspondences mean that every point in $\mathcal M$ is assigned not to one point, but to several nearby points in $\mathcal S$ . Here, each point in $\vec{m} \in \mathcal M$ is assumed to correspond to each point $\vec{s} \in \mathcal S$ with Gaussian weight:

1 $\displaystyle{\begin{align}P = \exp \left(\frac{-\|\vec{m} - \vec{s}\|^2}{2\sigma}\right)\end{align}}$

This deals with the issue of missing points as well as noise.

Since Gaussians are ubiquitous in nature, many papers have used Gaussian weights for point set registration. For example, this implementation is similar to coherent point drift by Myronenko and Song cpd.

In the worst case when registering points to points, a naive implementation will run in O(mn) when finding correspondences. However, the Fast Gauss Transform is an algorithm that can compute this in O(m + n) .

3.2 Initialization using RANSAC

To deal with the initialization issue, we randomly pick some points and try to do point set registration. For dimensions, we need to randomly pick points from $\mathcal M$ and associate them with random points from $\mathcal S$ . After each time we do this, we compute the total correspondence weights for all points, as described in the previous section (this is a measure of the consensus). After doing this for times, we keep the transformation that resulted in the best consensus. Hence this algorithm is a kind of random sample consensus (RANSAC) algorithm. This transformation is then used to initialize the point set registration.

Suppose there are points in $\mathcal M$ as well as in $\mathcal S$ , and some fraction $\rho$ of them have correspondences. The probability of each pair of correspondence of being correct is

2 $\displaystyle{\begin{align}p_{\text{corr}} \approx \frac{\rho}{n}\end{align}}$

To reach a $99\%$ success rate, we need trials where

3 $\displaystyle{\begin{align}0.99 = (1 - p_{\text{corr}}^d)^k\end{align}}$

For 2D point clouds where is around 1000 and $\rho$ is around 0.5, we just need k=40000 trials. This is easily done in a split second.

For 3D, the curse of dimensionality makes the trials we need more and more. Moreover, many laser scanners produce a million points per second. For these scenarios, one way is to run RANSAC only on a subset of interesting keypoints, for example, keypoints detected using the Fast Point Feature Histogram (FPFH) algorithm fpfh.

4 References

cpd Myronenko, A., & Song, X. (2010). Point set registration: Coherent point drift. IEEE transactions on pattern analysis and machine intelligence, 32(12), 2262-2275.
fpfh Rusu, R. B., Blodow, N., & Beetz, M. (2009, May). Fast point feature histograms (FPFH) for 3D registration. In Robotics and Automation, 2009. ICRA’09. IEEE International Conference on (pp. 3212-3217). IEEE.