Graph Matching through Max-Weight Bipartite Belief Propagation


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, or approaches based on the convex-concave procedure have achieved the state-of-the-art. In this project, Here 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; and (3) our sub-problems decompose into max-weight bipartite matching, which can be solved efficiently, leading to orders-of-magnitude reductions in execution time. Experimental results show that the proposed algorithm produces results superior to those of the current state-of-the-art.

Code (Matlab&C++)

Avaible from our GitHub repository.


  • Pairwise Matching through Max-Weight Bipartite Belief Propagation
    In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016