Page 402 -

Section 12.1 Registering Rigid Objects 370

Transformation Frame-bearing groups
One point and one direction, or
Rigid (Euclidean) two points, or
one line and one point
Two points, or
Rigid and scale
one line and one point off the line
Affine Three points, not co-linear

TABLE 12.1: Some frame-bearing groups for estimating transformations from 2D to 2D.
Assume we have one such group in the source, another in the target, and a correspondence
between the items in the group; then, we can estimate the transformation uniquely (see
the exercises).

3D case. These are explored further in the exercises, too.
Now assume we have a frame-bearing group in the source and in the target.
Then, if we have correspondences between the tokens, we could compute the rel-
evant transformation to place the source on the target. There might be only one
possible correspondence. For example, if the group is a line and a point, then we
can only place the source line (point) in correspondence with the target line (point).
But there might also be multiple possible correspondences; for example, the group
might consist of three points, yielding six total possibilities.
If one of the groups or the correspondence is incorrect, then most of the source
tokens will transform to locations well away from the target. But if they are correct,
then many or most transformed source tokens should lie near target tokens. This
means we can use RANSAC (Section 10.4.2), by repeatedly applying the following
steps, then analyzing the results:
• Select a frame-bearing group for the target and for the source at random;
• Compute a correspondence between the source and target elements (if there
is more than one, we could choose at random), and from this compute a
transformation;
• Apply the transformation to the source data set, and compute a score com-
paring the transformed source to the target.

If we have done this sufficiently often, then we will very probably see at least one
good correspondence between good groups, and we can identify this by looking at
the scores of each probe. From this good correspondence, we can identify pairs of
source and target points that match, and finally compute a transformation using
least squares.

12.1.3 Application: Building Image Mosaics
One way to photograph a big, imposing object in detail is to take numerous small
photographs, then patch them together. Back when it was usual to get photographs
developed and printed, one way to do this was to overlay the pieces of paper on a
corkboard, so that they joined up properly. This led to an image mosaic,a set of
overlapping images. Image mosaics can now be built by registering digital images.