The following method for registration of point sets is part of many publications, so only a short summary is given here. The complete algorithm was invented in 1992 and can be found, e.g., in [5]. The method is called Iterative Closest Points (ICP) algorithm.
Given two independently acquired sets of 3D points, (model set,
) and
(data set,
) which correspond to
a single shape, we want to find the transformation consisting of
a rotation
and a translation
which minimizes the
following cost function:
The ICP algorithm calculates iteratively a local minimum of
equation (1). In each iteration step, the algorithm
selects the closest points as correspondences and
calculates the transformation (
) for minimizing
equation (1). Fig. 2 shows three steps
of the ICP algorithm. Besl and McKay prove that the method
terminates in a minimum [5]. The assumption is that
in the last iteration step the point correspondences are correct.
In each ICP iteration, the transformation is calculated by the
quaternion based method of Horn [15]: A unit
quaternion is a 4 vector
, where
. It describes a
rotation axis and an angle to rotate around that axis. A
rotation matrix
is calculated from the unit
quaternion according the the following scheme:
To determine the transformation, the mean values of the paired
points (centroid vectors) and
are subtracted from
all points in
and
, respectively, resulting in the sets
and
. The rotation expressed as quaternion that
minimizes equation (1) is the largest eigenvalue of the
cross-covariance matrix
with
, ...After calculation the
rotation
, the translation is determined by
[15]. Fig. 2 shows two
3D scans in their initial, i.e., odometry-based pose, after 5
iterations, and the final pose. 40 iterations are needed to align
these two 3D scans correctly.
![]() ![]() ![]() |