Page 401 -

Section 12.1 Registering Rigid Objects 369

the index of this point depends on j, but also on the particular transformation
(s, θ, t). Write the index of the closest such point c(i, (s, θ, t)). Assume we have an
estimate of the transformation (s, θ, t) (n) . Then, we could refine this estimate by
iterating: (a) transforming the points of S; (b) for each, finding the closest point
in T ; and (c) re-estimating the transformation with least squares. This yields an
iterative algorithm, due to Besl and McKay (1992), known as the iterated closest
points algorithm (which is described in greater detail in Section 14.3.2). It should
be clear that the algorithm can converge to the right answer.
In practice, it usually does. Two points can help improve its behavior. First,
the re-estimation procedure does not need to converge to make the algorithm use-
ful. For example, rather than fully re-estimating the transformation, we could do a
single step of gradient descent. This will improve the transformation slightly, and
should change the corresponding closest points. Second, we do not need to incor-
porate all points in the minimization process. In particular, if the closest point is
relatively far away, it might be better to omit it from the least squares for the next
step. Doing so will help ensure the algorithm is robust.
You should regard this more as an algorithmic template than an algorithm;
numerous features can be changed successfully. For example, it could be speeded
up with care in data structures to keep track of the closest points. As another ex-
ample, an alternative strategy to obtain robust behavior is to replace the squared
error term with an M-estimator. In fact, this algorithm does not require that both
S and T be point sets. For example, it is relatively straightforward to adapt to
the case where S is a mesh and T is a point set (Besl and McKay 1992). Fur-
thermore, there is good evidence that the objective function in (s, θ, t)thatwe are
minimizing is quite well-behaved in practice. For example, even though it is not
differentiable (because the closest point changes, leading to step changes in the
derivative), second-order methods such as Newton’s method or LBFGS actually
behave rather well in practice (Fitzgibbon 2003).

12.1.2 Searching for Transformations via Correspondences
Iterated closest points repeatedly re-estimates a correspondence between source
and target points, then uses it to estimate a transformation. As we have seen,
this search might encounter numerous local minima. One alternative is to search
the space of correspondences. This might seem unpromising, because there appear
to be a lot of correspondences, but in the case of rigid objects a relatively small
set of correspondences is enough to register the whole object. Another advantage
of thinking about correspondences directly is that we can then work in terms of
tokens, rather than points. For example, we might place line-segments, corners, or
even point-like features such as blobs in correspondence; the type of the token can
sometimes change details, but has little effect on the overall algorithmic approach.
Quite a small group of source tokens, placed in correspondence with target
tokens, is enough to estimate a transformation. The size of the group depends
somewhat on the transformation and on the tokens. We refer to a group of tokens
from which a transformation could be computed as a frame-bearing group (some-
times frame group for short). Table 12.1 gives some examples of frame-bearing
groups for the 2D to 2D case, and Table 12.2 gives some examples for the 3D to