Efficient Methods for Graph Matching and MAP Inference

Graph Matching and MAP Inference in Markov Random Fields are important problems in computer vision that arise in many current applications. Here we present several efficient methods for graph and hyper-graph matching, MAP inference and parameter learning. We provide links to our publications, code and the datasets, on which we performed experiments and comparisons with other current approaches.

Papers and Code

1. Spectral Graph Matching (SM)
 
An efficient method for fast approximate solutions to the general formulation of graph matching as a Quadratic Assignment Problem (QAP).
 
Marius Leordeanu and Martial Hebert. "A spectral technique for correspondence problems using pairwise constraints.", International Conference on Computer Vision (ICCV), 2005.   PDF   Matlab Code
 
2. Spectral MAP Inference (SM - MAP) 
 
An efficient method with for inference in Markov Random Fields and Conditional Random Fields. It is related to Spectral Graph Matching and also based on a Quadratic Programming formulation. It has certain optimality properties for arbitrarily (possibly dense) structured graphs with arbitrary energy functions.
 
Marius Leordeanu and Martial Hebert. "Efficient MAP approximation for dense energy functions." ACM-International Conference on Machine Learning (ICML), USA, 2006.
 
3. Integer Projected Fixed-Point Method for Graph Matching and MAP Inference (IPFP)
 
Efficient method for obtaining a discrete solution obeying one-to-one constraints (for graph matching problems) or many-to-one (for labeling and MAP inference problems). It is a competitive method even by itself, when initialized with uniform solutions. In the case of Graph Matching it could also be seen as a parallel version of the Iterative Conditional Modes (ICM) method with theoretically guaranteed climbing and convergence properties for arbitrary structured graphs with arbitrary energy functions.
 
Marius Leordeanu, Martial Hebert and Rahul Sutkhankar, "An Integer Projected Fixed Point Method for Graph Matching and MAP Inference",  Neural Information Processing Systems (NIPS), 2009.   PDF   Matlab Code 
 
4. Learning for Graph Matching
 
A method for learning the objective energy function for graph matching in an unsupervised or semi-supervised manner, based on an efficient and original computation of the principal eigenvector of the graph matching matrix.
 
Marius Leordeanu, Rahul Sukthankar and Martial Hebert. "Unsupervised learning for graph matching." International journal of computer vision 96.1 (2012): 28-45.
PDF  Matlab Code
 
5. Learning and Optimization for Hypergraph Matching  
 
A novel hyper-graph matching method with state-of-the-art performance and an efficient algorithm for unsupervised and semi-supervised learning for hypergraph matching.
 
Marius Leordeanu, Andrei Zanfir and Cristian Sminchisescu, "Semi-supervised Learning and Optimization for Hypergraph Matching", International Conference on Computer Vision (ICCV), Barcelona, 2011.  PDF 
 
6. Efficient Hypergraph Clustering
 
A method for efficient clustering related to [3,5] from above.
 
Marius Leordeanu and Cristian Sminchisescu, "Efficient Hypergraph Clustering", Artificial Intelligence and Statistics (AISTATS), La Palma, 2012. PDF  
 
7. Spectral Graph Matching: Learning and Inference
 
Marius Leordeanu, "Spectral Graph Matching, Learning and Inference for Computer Vision", PhD Thesis, Carnegie Mellon University, 2009.  PDF
 

Datasets

Cars and Motorbikes graph matching dataset available for download here. The Datasets consist of 30 pairs of cars and 20 pairs of motorbikes from VOC PASCAL 2007 with extracted contours, annotated ground truth correspondences and a significant number of outliers. 
 
For questions or bugs please email Marius Leordeanu at leordeanu at gmail.