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, 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.


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


  • Pairwise Matching through Max-Weight Bipartite Belief Propagation
    In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016
  • Dynamic Programming Bipartite Belief Propagation For Hyper Graph Matching
    In The 26th International Joint Conference on Artificial Intelligence (IJCAI-17)