Iterative Closest Point

ICP

1. Initialize: $f^0=\{\mathbf{R}=\mathbf{I},\mathbf{t}=\bar{\mathbf{y}}-\bar{\mathbf{x}},s=1\}$
2. Correspondences: ${\mathbf{x}}_i^{j+1}=\arg {\min }_{\mathbf{x}\in \mathbf{X}}\Vert f^j(\mathbf{x})-{\mathbf{y}}_i{\Vert }^2$
3. Transform with Procrustes: $f^{j+1}=\arg {\min }_f{\sum }_i\Vert f({\mathbf{x}}_i^{j+1})-{\mathbf{y}}_i{\Vert }^2$
4. Stop if the error is below a threshold, otherwise go to 2.
5. Converges to a local minimum.

Improvements: kd-tree for closest points ($O(\log n)$ instead of $O(n^2)$), random subsampling, correspondences from target to source, robust costs against outliers, normals, RANSAC, point-to-surface instead of point-to-point distances.

Gradient-based ICP: for non-rigid transforms, replace Procrustes by a descent step on the energy (gradient descent, Gauss-Newton, LM, BFGS) with automatic differentiation. More generic, but non-convex for general deformation models.

Appears in

• Lecture 5, The ICP Algorithm
• Lecture 5, Improvements
• Lecture 5, Gradient-based ICP

Related concepts

• Procrustes Alignment
• RANSAC
• Mesh