Many-to-Many Feature Matching in Object Recognition

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 paper, we 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. First, 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. Next, we define a low-dimensional, spectral encoding of graph structure and use it to match entire subgraphs whose size can be different. 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.

Authors and Affiliations

1. Computer Science Department, Drexel University, 3200 Chestnut St, Philadelphia, PA, 19104, USA

   Ali Shokoufandeh & Fatih Demirci

2. School of Computer Science, DePaul University, 243 S. Wabash Ave, Chicago, IL, 60604, USA

   Yakov Keselman

3. Department of Computer Science, University of Toronto, 6 King’s College Rd, Toronto, Ontario, M5S 3G4

   Diego Macrini & Sven Dickinson

Editors and Affiliations

1. GVU Center & School of Interactive Computing, College of Computing, Georgia Institute of Technology, 30308, Atlanta, GA, USA

   Henrik I. Christensen

2. Institut für Algorithmen und Kognitive Systeme, Fakultät für Informatik, Universität Karlsruhe (TH), 76128, Karlsruhe, Germany

   Hans-Hellmut Nagel

Reprints and permissions

© 2006 Springer-Verlag Berlin Heidelberg

Policies and ethics