Iterative Closest Point

Iterative Closest Point (ICP) is an 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 (especially when wheel odometry is unreliable due to slippery terrain), to co-register bone models, etc.

The algorithm is conceptually simple and is commonly used in real-time. It iteratively revises the transformation (translation, rotation) needed to minimize the distance between the points of two raw scans.

Inputs: points from two raw scans, initial estimation of the transformation, criteria for stopping the iteration.

Output: refined transformation.

Essentially the algorithm steps are :

  1. Associate points by the nearest neighbor criteria.
  2. Estimate transformation parameters using a mean square cost function.
  3. Transform the points using the estimated parameters.
  4. Iterate (re-associate the points and so on).

In, a modified K-D tree algorithm is proposed for efficient closest point computation, and a statistical method based on the distance distribution is used to deal with outliers, occlusion, appearance and disappearance, which enables subset-subset matching.

Famous quotes containing the words closest and/or point:

    “It is a fearful thing to lead this great peaceful people into war, into the most terrible and disastrous of all wars, civilization itself seeming to be in the balance. But the right is more precious than peace, and we shall fight for the things we have always carried closest to our hearts.”
    —Woodrow Wilson (1856–1924)

    “A set of ideas, a point of view, a frame of reference is in space only an intersection, the state of affairs at some given moment in the consciousness of one man or many men, but in time it has evolving form, virtually organic extension. In time ideas can be thought of as sprouting, growing, maturing, bringing forth seed and dying like plants.”
    —John Dos Passos (1896–1970)