Biomedical Engineering Reference
In-Depth Information
3.4.2.3 Iterative Closest Point (ICP)
The ICP algorithm was proposed by Besl and McKay in for the reg-
istration of 3D shapes. It was not designed with medical images in mind, but
has subsequently been applied to medical images with considerable success,
and is now probably the most widely used surface matching algorithm in
medical imaging applications.
25-27
The original paper is written in terms of
registration of collected data to a model. The collected data,
1992
24
, could come
from any sensor that provides 3D surface information, including laser scan-
ners, stereo video, and so forth. The model data,
P
, could come from a com-
puter-aided design model. In medical imaging applications, both sets of
surface data might be delineated from radiological images, or the model
might be derived from a radiological image and the data from stereo video
acquired during an operation. The algorithm is designed to work with seven
different representations of surface data: point sets, line segment sets
(polylines), implicit surface, parametric curves, triangle sets, implicit sur-
faces, and parametric surfaces. For medical image registration the most rele-
vant representations are likely to be point sets and triangle sets, as algorithms
for delineating these from medical images are widely available.
The algorithm has two stages and iterates. The first stage involves identi-
fying the closest model point for each data point, and the second involves
finding the least square rigid-body transformation relating these point sets.
The algorithm then redetermines the closest point set and continues until it
finds the local minimum match between the two surfaces, as determined by
some tolerance threshold.
Whatever the original representation of the data surface
, it is first con-
verted to a set of points . The model data remain in their original rep-
resentation. The first stage involves identifying, for each point
p
i
on the
data surface
P
{}
p
i
P
, the closest point on the model surface
. This is the point
x
in
for which the distance
d
between
p
i
and
x
is minimum.
d
p
i
,
(
)
min
xp
i
x
The resulting set of closest points (one for each
p
i
) is . For a triangulated
surface, which is the most likely model representation from medical image
data, the model
{}
q
i
comprises a set of triangles . The closest model point to
each data point is found by linearly interpolating across the facets. If triangle
t
i
has vertices
r
1
,
r
2
, and
r
3
, then the smallest distance between the point
p
i
and
the triangle
t
i
is
{}
t
i
d
p
i
,
t
i
(
)
min
u
r
1
v
r
2
w
r
3
p
i
u
v
w
1
where
u
[0, 1],
v
[0, 1] and
w
[0, 1]. The closest model point to the data
point
p
i
is, therefore,
q
i
(
u
r
1
,
v
r
2
,
w
r
3
).
