Dual decomposition solvers for the quadratic assignment problem (QAP), also called graph matching in computer vision based on the LP_MP library.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
external
include
src
test
.gitmodules
.travis.yml
CMakeLists.txt
README.md

README.md

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.