Page 420 -

Section 12.4 Notes 388

12.4 NOTES
Registration is useful. Useful recent image registration surveys include Zitova and
Flusser (2003); and Dawn et al. (2010). Registration algorithms were once used for
object recognition—one registers a model to an image, then accepts the hypothesis
based on a final score—but different algorithms now dominate in this area. We
believe that future work will integrate what is known about registration with the
statistical methods of Chapters 16 and 17.
A major difficulty in registration is computing the distance to the nearest
point. Chamfer matching uses a representation of distance to the nearest point,
cached on a grid; computing the cache is sometimes known as a distance transfor-
mation. Borgefors (1988) gives what we believe to be the first hierarchical search
algorithm for registering objects using a distance transformation.

Model-Based Vision
The term alignment is due to Huttenlocher and Ullman (1990). It is a convenient
term for a general class of algorithm that reasons about pose consistency. It is hard
to determine who used the approach first, though it is quite likely Roberts (1965);
other possibilities include Faugeras et al. (1984). A contemporary survey is Chin
and Dyer (1986). The noise behavior of some alignment algorithms has been studied
in detail (Grimson et al. 1992, Grimson et al. 1994, Grimson et al. 1990, Sarachik
and Grimson 1993). As a result, alignment algorithms are widely used and there
are numerous variants.
These algorithms fell away as object recognition methods because they have
difficulty in the presence of rich textures, because they scale poorly with increasing
numbers of models, and because they don’t apply to objects that aren’t rigid. Fur-
thermore, although constrained search for a model that is present can be efficient,
showing that a model is absent is expensive (Grimson 1992).
Pose clustering is due to Thompson and Mundy (1987). The analogy to the
Hough transform means that the method can behave quite badly in the presence
of noise (Grimson and Huttenlocher 1990).
Pose consistency can be used in a variety of forms. For example, recognition
hypotheses yield estimates of camera intrinsic parameters. This means that if there
are several objects in an image, all must give consistent estimates of camera intrinsic
parameters (Forsyth et al. 1994).
Tokens could be more abstract than points and lines, and might be as complex
as a stripey patch, an eye, or a nose (Ettinger 1988, Ullman 1996). Verification
has been extremely poorly studied, (but see Grimson and Huttenlocher (1991)).
Verification based on generic evidence—say, edge points—has the difficulty that
we cannot tell which evidence should be counted. Similarly, if we use specific
evidence—say, a particular camouflage pattern—we have problems with abstrac-
tion.

Deformable Models
Registering deformable models is a well-established problem with a long history.
Jain et al. (1996) give an important early methods that applies to purely geometri-