/LP_MP-QAP

Dual decomposition solvers for the quadratic assignment problem (QAP), also called graph matching in computer vision based on the LP_MP library.

Primary LanguageC++

LP_MP-QAP

Build Status

Dual decomposition solvers for the quadratic assignment problem (QAP), also called graph matching in computer vision, based on the LP_MP library.

Solvers

  • Minimum cost flow based solver [1].
  • Pure message passing based solver [1].
  • SRMP with the QAP reformulated as a graphical model [2].
  • Hungarian belief propagation [3].

Input formats

We use the input format of the solver [4], see here for the definition of this format.

Installation

Type git clone https://github.com/pawelswoboda/LP_MP-QAP.git to download the main repository and git submodule update --init --remote --recursive the dependencies. Then type cmake . to configure and make to build.

References

  • [1]: Swoboda, P., Rother, C., Abu Alhaija, H., Kainmuller, D. and Savchynskyy, B. A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching. CVPR, July 2017.
  • [2]: V. Kolmogorov. A New Look at Reweighted Message Passing. IEEE Trans. Pattern Anal. Mach. Intell., 37(5):919–930, 2015.
  • [3]: Zhang, Z. , Shi, Q. , McAuley, J. , Wei, W. , Zhang, Y. and van den Hengel, A. Pairwise Matching Through Max-Weight Bipartite Belief Propagation. CVPR, June 2016.
  • [4]: Torresani, L., Kolmogorov, V. and Rother, C. A Dual Decomposition Approach to Feature Correspondence. IEEE Trans. Pattern Anal. Mach. Intell., 35(2):259–271, 2013.