Carnegie Mellon University
Spectral Graph Matching, Learning, and Inference for Computer Vision

Marius Leordeanu
doctoral dissertation, tech. report CMU-RI-TR-09-27, Robotics Institute, Carnegie Mellon University, July, 2009

  • Adobe portable document format (pdf) (66MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Several important applications in computer vision, such as 2D and 3D object matching, object category and action recognition, object category discovery, and texture discovery and analysis, require the ability to match features efficiently in the presence of background clutter and occlusion. In order to improve matching robustness and accuracy it is important to take in consideration not only the local appearance of features but also the higher-order geometry and appearance of groups of features. In this thesis we propose several efficient algorithms for solving this task, based on a general quadratic programming formulation that generalizes the classical graph matching problem. First, we introduce spectral graph matching, which is an efficient method for matching features using both local, first-order information, as well as pairwise interactions between the features. We study the theoretical properties of spectral matching in detail and show efficient ways of using it for current com- puter vision applications. We also propose an efficient procedure with important theoretical properties for the final step of obtaining a discrete solution from the continuous one. We show that this discretization step, which has not been studied previously in the literature, is of crucial importance for good performance. We demonstrate its efficiency by showing that it dramatically improves the performance of state-of-the art algorithms. We also propose, for the first time, methods for learning graph matching in both supervised and unsupervised fashions. Furthermore, we study the connections between graph matching and the MAP inference problem in graphical models, for which we propose novel inference and learning algorithms. In the last part of the thesis we present an application of our matching algo- rithm to the problem of object category recognition, and a novel algorithm for grouping image pixels/features that can be effectively used for object category segmentation.

Number of pages: 236

Text Reference
Marius Leordeanu, "Spectral Graph Matching, Learning, and Inference for Computer Vision," doctoral dissertation, tech. report CMU-RI-TR-09-27, Robotics Institute, Carnegie Mellon University, July, 2009

BibTeX Reference
   author = "Marius Leordeanu",
   title = "Spectral Graph Matching, Learning, and Inference for Computer Vision",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   month = "July",
   year = "2009",
   number= "CMU-RI-TR-09-27",
   address= "Pittsburgh, PA",