Biomedical Engineering Reference
In-Depth Information
ing the rotation transformation and
t
is a vector representing the translation
transformation, with their closest points in the model data set. A least-squares
estimation is then used to reduce the average distance between the matched
points in the two data sets. The algorithm is relatively straightforward and can
be summarized as follows:
1. Given a motion transformation that initially aligns two data sets to some
degree, a set of correspondence is developed between the points in each
set. This is done using a simple metric: for each point in the first data set,
pick the point in the second set which is closest to it under the current
transformation.
2. From this set of correspondence an incremental motion can be computed
which further aligns these points to one another.
3. Those two steps are iterated until some convergence criterion is satisfied.
Figure 1.1 illustrates these steps. The ICP algorithm tries to find the opti-
mal transformation matrix
T
between two shapes
S
and
S
such that Eq.
(1.3) is minimized using the closest point operator in distance calculations as
follows:
d
(
y
i
,
S
)
=||
y
i
−
C
(
y
i
,
S
)
||
(1.4)
where
C
(
·
) is defined as the closest point operator, i.e.,
C
(
·
) finds the closest
point in shape
S
to the point
y
i
. At each step of the minimization process, a
correspondent point on
S
has to be found for each point
Ry
i
+
t
on
S
. This
makes the operation of registration of order
O
(
mn
) and as a result ICP has
many drawbacks:
1. One of the main disadvantages of the ICP algorithm is its computation
complexity. This makes the algorithm not suitable for applications where
near real-time performance is required.
2. The algorithm converges successfully to a local solution but there is no
guarantee that it will reach a global solution.
3. Proper convergence only occurs if one of the data sets is a subset of the
other. The presence of points in each set that are not in the other leads
to incorrect correspondences, which subsequently generates nonoptimal
transformations.
