MAPMAP MRF Solver

MAPMAP – Minimal Assumption, High-Performance MAP solver

Abstract

Given the increasing availability of high-resolution input data, today’s computer vision problems tend to grow beyond what has been considered tractable in the past. This is especially true for Markov Random Fields (MRFs), which have expanded beyond millions of variables with thousands of labels. Such MRFs pose new challenges for inference, requiring massively parallel solvers that can cope with large-scale problems and support general, irregular input graphs. We propose a block coordinate descent based solver for large MRFs designed to exploit many-core hardware such as recent GPUs. We identify tree-shaped subgraphs as a block coordinate scheme for irregular topologies and optimize them efficiently using dynamic programming. The resulting solver supports arbitrary MRF topologies efficiently and can handle arbitrary, dense or sparse label sets as well as label cost functions. Together with two additional heuristics for further acceleration, our solver performs favorably even compared to modern specialized solvers in terms of speed and solution quality, especially when solving very large MRFs.

Publications

  • A Fast, Massively Parallel Solver for Large, Irregular Pairwise Markov Random Fields
    Daniel Thuerck, Michael Waechter, Sven Widmer, Max von Buelow, Patrick Seemann, Marc E. Pfetsch, and Michael Goesele
    In: Proceedings of High Performance Graphics (HPG 2016), Dublin, Ireland, 2016.

Reprint

  • Paper (3.2 MB)
  • Supplemental Material (3.8 MB)
  • BibTeX

Source code

For the source code, please head over to GitHub by clicking on the image to the left. Once there, please clone the repository and read the README.md. Build intructions and general information is provided in the readme. For more information, especially on how to use mapMAP as a library in your own projects, consider reading the project's 'understanding the demo' wiki page.

Note that the provided source code is a reimplemented version of the algorithm described in our paper – it has more features, is extensible and production-quality, while only slightly less fast than the version presented in the paper. If you are interested in the research code of either CPU or GPU version as well as the binary data sets, please us.

Contact

If you have bug reports, questions or suggestions, please e-mail us: or use the project's integrated issue tracker over at Github.