Point set registration

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

The Big Dipper
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:

2 Iterative closest point

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

  1. Assign every point in \mathcal M to the nearest point in \mathcal S.
  2. 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.

  1. It requires a good initial guess. Even then, it is prone to getting stuck in a local minima.
  2. 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{P = \exp \left(\frac{-\|\vec{m} - \vec{s}\|^2}{2\sigma}\right)}

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 n points to m 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 d dimensions, we need to randomly pick d points from \mathcal M and associate them with d 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 k 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 n 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{p_{\text{corr}} \approx \frac{\rho}{n}}

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

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

For 2D point clouds where n 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