CISC 472 - Iterated Closest Point

The iterated closest point (ICP) algorithm finds a minimal-error transformation of a point set to a model.

The point set consists of sample points, usually from a physical object such as a patient's bone, and might be obtained by touching a tracked stylus to many points on the patient's bone. The point set is in one coordinate system.

The model is a computer representation of the object being sampled, and is usually a 3D triangulated surface of a segmented CT or MRI scan of the patient's anatomy. The model is in another coordinate system. The model might also be a set of points, although this is less common.

Algorithm

The algorithm is attributed to several authors: [Besl and McKay 1992], [Chen and Mediono 1992], and [Zhang 1994].

Let $P = \{ p_1, p_2, \ldots, p_n \}$ be the point set.

Let $M$ be the model.

Let $T$ be the transformation (a homogeneous $4 \times 4$ matrix). Initially, $T$ is the identity matrix.

For each $p_i \in P$, find the closest model point, $m_i \in M$.
Given the paired points, $(p_i,m_i)$, apply Procrustes to find a transformation, $T'$, to move the $p_i$ to the correspoinding $m_i$.
Add $T'$ to the accumulated transformation: $T \leftarrow T'\ T$.
Update the points using the transformation: $p_i \leftarrow T'\ p_i$.
Determine the error between the $p_i$ and the corresponding $m_i$. This is usually the RMS error.
If the error is too large, return to Step 1.

Problems with ICP

The algorithm can get stuck in a local minimum.
Solutions:
- Make an initial alignment of $P$ to $M$ manually.
- Make an initial automatic alignment based on landmarks [Ma and Ellis 2003].
- Try several different initial alignments [Besl and McKay 1992]
- Apply simulated annealing.
Point pairing is expensive.
Solutions:
- Use a kd-tree for to find closest points [Besl and McKay 1992].
- "Approximate kd tree search for efficient ICP" [Greenspan and Yurick 2003]
Procrustes assumes (a) no outliers and (b) isotropic error.
Solutions:
- Use RANSAC.
- Weight point $p_i$ by ${1 \over |p_i - m_i|}$ so that distant matches count for less.
- Reject far-separated points.

Example

Below are three short videos showing the ICP registration of 17 sampled points to a femur model. The 17 points are the same in each video, but the starting positions are different. Lines are shown from the sampled points to the corresponding closest femur points.

The first two videos show poor registrations; the third shows a good registration.

The takeaway is that ICP can easily fall into a local minimum, so you should run it with many different initial positions.

Example 1: Poor registration

Example 2: Poor registration

Example 3: Good registration

up to Schedule & Notes