Many-to-Many Feature Matching in Object Recognition

               Sven Dickinson

            University of Toronto
       http://www.cs.toronto.edu/~sven/

One of the bottlenecks of current recognition (and graph matching)
systems is their assumption of one-to-one feature (node)
correspondence.  This assumption breaks down in the generic object
recognition task where, for example, a collection of features at one
scale (in one image) may correspond to a single feature at a coarser
scale (in the second image).  Generic object recognition therefore
requires the ability to match features many-to-many.  In this talk, I
will review our progress on three independent object recognition
problems, each formulated as a graph matching problem and each solving
the many-to-many matching problem in a different way.  In the first
problem, we define a low-dimensional, spectral encoding of graph
structure and use it to match entire subgraphs whose size can be
different.  Next, we explore the problem of learning a 2-D shape class
prototype (represented as a graph) from a set of object exemplars
(also represented as graphs) belonging to the class, in which there
may be no one-to-one correspondence among extracted features.
Finally, in very recent work, we embed graphs into geometric
spaces,reducing the many-to-many graph matching problem to a weighted
point matching problem, for which efficient many-to-many matching
algorithms exist.