Graphics Reference
In-Depth Information
T(p)
P
(a)
q(p)
Q
(b)
Q
P
Figure 8.34.
The basic Iterative Closest Points (ICP) algorithm alternates between two steps to
align two 3D point sets
P
Q
and
. (a) For a fixed candidate transformation
T
, the closest point
is determined. (b) A new rigid motion
T
is computed that
minimizes the sum of distances between the estimated correspondences.
)
∈
Q
)
∈
P
q
(
p
to each point in
T
(
p
In this section, we review the
Iterative Closest Points (ICP)
algorithm, the most
commonly usedmethod for 3D scan registration. This fundamental approach to reg-
istration was discovered and described roughly simultaneously by several research
groups, including Besl and McKay [
41
], Chen and Medioni [
89
], and Zhang [
573
].
The basic idea is simple: given two unordered sets of 3D points
to be regis-
tered and an initial rigid motion
T
, we alternate between two steps, as illustrated in
Figure
8.34
:
P
and
Q
P
=
1. Transform the points in
P
by
T
to obtain a new set of points
T
(P)
. For
each
p
∈
P
, compute the closest point
q
(
p
)
∈
Q
, i.e.,
q
(
p
)
=
argmin
q
∈
Q
T
(
p
)
−
q
(8.14)
2
2. Estimate the rigid motion
T
that minimizes the sum of errors
E
(
T
)
=
e
(
T
(
p
)
,
q
(
p
))
(8.15)
p
∈
P
where
e
is a suitable error function between pairs of 3D points. That is, we alter-
nate between fixing the transformation and estimating the correspondence, and vice
versa. The algorithm stops when
E
(
p
,
q
)
(
T
)
falls below a user-specified threshold. Besl and
McKay proved that when
e
(
p
,
q
)
in Equation (
8.15
) is the squared Euclidean distance
2
2
, then the ICP algorithm converges monotonically to a local minimum of the
cost function
E
p
−
q
.
We must address two additional issues. First, how can we obtain a good initial-
ization
T
before starting the ICP iterations? This is where the feature detection and
matching results from the previous section come in. Any three feature matches in
3D (e.g., obtained using spin images or shape contexts) define a rigid transformation
T
. Furthermore, if co-registered RGB images are available, matching a single pair of
back-projected SIFT or physical scale keypoints between two different scans gives
(
T
)
