Memory Efficient Max Flow for Multi-Label Submodular MRFs

Thalaiyasingam Ajanthan, Richard Hartley, Mathieu Salzmann

Abstract

Multi-label submodular Markov Random Fields (MRFs) have been shown to be solvable using max-flow based on an encoding of the labels proposed by Ishikawa, in which each variable <inline-formula><tex-math notation="LaTeX">$X_i$</tex-math></inline-formula> is represented by <inline-formula><tex-math notation="LaTeX">$\ell$</tex-math></inline-formula> nodes (where <inline-formula><tex-math notation="LaTeX">$\ell$</tex-math></inline-formula> is the number of labels) arranged in a column. However, this method in general requires <inline-formula><tex-math notation="LaTeX">$2\;\ell ^2$</tex-math></inline-formula> edges for each pair of neighbouring variables. This makes it inapplicable to realistic problems with many variables and labels, due to excessive memory requirement. In this paper, we introduce a variant of the max-flow algorithm that requires much less storage. Consequently, our algorithm makes it possible to optimally solve multi-label submodular problems involving large numbers of variables and labels on a standard computer.
BibTeX
@article{ajanthan2019memory,
  author = {Thalaiyasingam Ajanthan and Richard Hartley and Mathieu Salzmann},
  title = {{Memory Efficient Max Flow for Multi-Label Submodular MRFs}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2019},
  url = {https://openreview.net/forum?id=k4lJE-20Re6X},
}

Loading related content...

Figure