Iterative Closest Point Algorithm

from Wikipedia, the free encyclopedia
Idea behind the Closest Point Algorithm

The Iterative Closest Point Algorithm (ICP) is an algorithm that enables point clouds to be adapted to one another. To use the method, the point clouds must already be approximately aligned with one another in advance.

When performing the algorithm, an attempt is made to bring the point clouds into congruence as well as possible by means of rotation and translation. Based on a set of approximately determined initial transformation parameters for rotation and translation, the closest point in each case from the other point cloud is determined for each point from one point cloud. Then the sum S of the squares of the distances is formed over all these pairs of points. This gives a measure of the quality of the correspondence between the point clouds. The aim is to minimize this optimization measure, that is to say the above sum S , by changing the transformation parameters. There are different approaches for determining the appropriate transformation parameters. T. based on the structure of the underlying point clouds. In any case, this is an iterative process that is continued until an acceptable optimum has been found.

  • Step 0: Approximate determination of the initial transformation parameters for rotation R (0) and translation T (0)
  • ...
  • Step n.1: Applying the transformation with the parameters R (n-1) and T (n-1)
  • Step 2: For each point from one point cloud, determination of the closest point from the other point cloud
  • Step n.3: Calculation of the sum S of the squares of the above-mentioned pairs of points
  • Step n.4: Determination of new transformation parameters R (n) and T (n) [derived from the structure of the point clouds]
  • ...
  • The iteration is terminated if the sum S (n) falls below a defined threshold in the nth step .

The algorithm is mainly used for the relative registration of point clouds , with which an overall model can be generated from several point clouds. The single point clouds can z. B. by laser scanning or photogrammetric methods of automatic image allocation ( dense image matching ). Another area of ​​application is localization in robotics , a sub-problem of Simultaneous Localization and Mapping .

Web links

  • FastICP paper - Comparison of different ICP variants (PDF file; 784 kB)
  • Basis for ICP - the conversion of coordinate systems into one another with the help of quaternions (PDF file; 1.6 MB)