Iterative closest point (ICP) is a

point cloud registration In computer vision, pattern recognition, and robotics, point-set registration, also known as point-cloud registration or scan matching, is the process of finding a spatial transformation (''e.g.,'' scaling, rotation and translation) that aligns ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

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 Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used ...

(especially when wheel odometry is unreliable due to slippery terrain), to co-register

bone A bone is a rigid organ that constitutes part of the skeleton in most vertebrate animals. Bones protect the various other organs of the body, produce red and white blood cells, store minerals, provide structure and support for the body, ...

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 (combination of translation and rotation) 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 In mathematics, a rigid transformation (also called Euclidean transformation or Euclidean isometry) is a geometric transformation of a Euclidean space that preserves the Euclidean distance between every pair of points. 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 (optional), criteria for stopping the iterations. Output: refined transformation. Essentially, the algorithm steps are: # For each point (from the whole set of vertices usually referred to as dense or a selection of pairs of vertices from each model) in the source point cloud, match the closest point in the reference point cloud (or a selected set). # 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. # Transform the source points using the obtained transformation. #

Iterate Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...

(re-associate the points, and so on). 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.François Pomerleau, Francis Colas, Roland Siegwart, and Stéphane Magnenat
Comparing ICP Variants on Real-World Data Sets.
In Autonomous Robots, 34(3), pages 133–148, DOI: 10.1007/s10514-013-9327-2, April 2013.

Implementations

MeshLab MeshLab is a 3D mesh processing software system that is oriented to the management and processing of unstructured large meshes and provides a set of tools for editing, cleaning, healing, inspecting, rendering, and converting these kinds of mesh ...

an open source mesh processing tool that includes a GNU General Public License implementation of the ICP algorithm. *

CloudCompare CloudCompare is a 3D point cloud processing software (such as those obtained with a laser scanner). It can also handle triangular meshes and calibrated images. Originally created during a collaboration between Telecom ParisTech and the R&D divi ...

an open source point and model processing tool that includes an implementation of the ICP algorithm. Released under the GNU General Public License. * PCL (Point Cloud Library) is an open-source framework for n-dimensional point clouds and 3D geometry processing. It includes several variants of the ICP algorithm. * Open source C++ implementations of the ICP algorithm are available in VTK, ITK an
Open3D
libraries.
libpointmatcher
is an implementation of point-to-point and point-to-plane ICP released under a BSD license.
simpleICP
is an implementation of a rather simple version of the ICP algorithm in various languages.

References

{{reflist, 30em Geometry in computer vision Robot navigation

Overview

Implementations

See also

References