Graph Matching through Max-Weight Bipartite Belief Propagation

Abstract

Graph matching is a key problem in computer vision and pattern recognition. One way to encode the essential interdependence between potential feature matches is to cast the problem as inference in a graphical model (pairwise model for graph matching and higher-order for hyper graph matching problems). Though recently alternatives such as spectral methods, multt-linear relaxations, or approaches based on the convex-concave procedure have achieved the state-of-the-art. In this project, we revisit the use of graphical models for feature matching, and propose a belief propagation scheme which exhibits the following advantages: (1) we explicitly enforce one-to-one matching constraints; (2) we offer a tighter relaxation of the original cost function than previous graphical-model-based approaches; (3) our sub-problems decompose into max-weight bipartite matching, which can be solved efficiently, leading to orders-of-magnitude reductions in execution time; (4) for hyper-graph matching problem, the dynamic programming technique can be used to further accelerate the algorithm. Experimental results show that the proposed algorithm produces results superior to those of the current state-of-the-art.

Code

The code for pairwise matching is avaible from HungarianBP. The code for higher order matching is avaible from HyperBP.

Publication