Graphics Reference
In-Depth Information
an immediate estimate of the 3D rigid motion relating them, since each descriptor is
associated with a full coordinate frame.
The second issue is how to minimize the sum-of-distances function in
Equation (
8.15
). When
e
in Equation (
8.15
) is the squared Euclidean distance,
we can apply a classic result by Umeyama [
504
]. Suppose the two ordered point sets
are denoted by
(
p
,
q
)
{
(
p
i
,
q
i
)
=
...
}
µ
p
and
µ
q
to be the mean values of
,
i
1,
,
N
. We define
{
p
i
}
{
q
i
}
×
the sets
and
respectively, and compute the 3
3 covariance matrix
N
1
N
p
i
−
µ
p
)
=
1
(
q
i
−
µ
q
)(
(8.16)
i
=
be given by
UDV
, where the entries of
D
decrease along the diagonal. Then the rigid motion
Let the singular value decomposition of
(
R
,
t
)
that minimizes
N
1
N
2
1
q
i
−
(
Rp
i
+
t
)
(8.17)
i
=
is given in closed form by
USV
R
=
(8.18)
t
=
µ
q
−
R
µ
p
(8.19)
where
S
otherwise.
While the ICP algorithm underlies almost every 3D registration algorithm,
researchers have suggested various modifications to improve its convergence, make
it more robust to outliers, and make it more generally applicable to large-scale, clut-
tered scans in which many points in one set may have no valid correspondences in
the other set. Rusinkiewicz and Levoy [
411
] gave an excellent overview of proposed
variants to the basic algorithm described previously. We briefly mention some of the
most effective refinements here.
=
I
3
×
3
if det
≥
0 and
S
=
diag
(
1, 1,
−
1
)
•
P
Instead of using all the points from
in the closest-point and distance-
minimization steps, only use a subset of the points (e.g., chosen randomly
in space, at the locations of detected features, or so that the normal vectors'
angles are widely distributed).
•
Choose the “closest” point
q
not simply as the point that minimizes the
Euclidean distance, but as the closest point whose normal vector is within a
specified angle of the normal at
T
(
p
)
(
p
)
.
•
Don't allow points near the boundary of scans to participate in matching, to
preventmany points in one scanbeingmatched to the same point in the other.
This is especially important when the scans represent partial views of a larger
scene.
•
Instead of using the Euclidean distance in the distance-minimization step,
use the
point-to-plane
distance illustrated in Figure
8.35
. The error function
in Equation (
8.15
)is
))
η
2
e
(
T
(
p
)
,
q
(
p
))
=
((
T
(
p
)
−
q
(
p
)
)
(8.20)
q
(
p
