Iterative closest point


Iterative closest point is a point cloud registration algorithm employed to minimize the difference between two clouds of points. ICP is often used to reconstruct 2D or 3D surfaces from different scans, to localize robots and achieve optimal path planning, to co-register bone models, etc.

Overview

The Iterative Closest Point algorithm keeps one point cloud, the reference or target, fixed, while transforming the other, the source, to best match the reference. The transformation is iteratively estimated in order to minimize an error metric, typically the sum of squared differences between the coordinates of the matched pairs. ICP is one of the widely used algorithms in aligning three dimensional models given an initial guess of the rigid transformation required.
The ICP algorithm was first introduced by Chen and Medioni, and Besl and McKay.
Inputs: reference and source point clouds, initial estimation of the transformation to align the source to the reference, criteria for stopping the iterations.
Output: refined transformation.
Essentially, the algorithm steps are:
  1. For each point in the source point cloud, match the closest point in the reference point cloud.
  2. Estimate the combination of rotation and translation using a root mean square point-to-point distance metric minimization technique which will best align each source point to its match found in the previous step. This step may also involve weighting points and rejecting outliers prior to alignment.
  3. Transform the source points using the obtained transformation.
  4. Iterate.
Zhang proposes a modified k-d tree algorithm for efficient closest point computation. In this work a statistical method based on the distance distribution is used to deal with outliers, occlusion, appearance, and disappearance, which enables subset-subset matching.
There exist many ICP variants, from which point-to-point and point-to-plane are the most popular. The latter usually performs better in structured environments.

Non-rigid ICP

While traditional ICP assumes rigid transformations, non-rigid ICP methods extend the algorithm to handle deformable objects and non-rigid registration scenarios. These methods incorporate additional constraints and regularization terms to model local deformations while maintaining surface coherence.

Implementations