Memory Efficient Max Flow for Multi-Label Submodular MRFs

Thalaiyasingam Ajanthan, Richard Hartley, Mathieu Salzmann

CVPR 2016

doi:10.1109/CVPR.2016.632 /cvpr/2016/ajanthan2016cvpr-memory/

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 X_i is represented by l nodes (where l is the number of labels) arranged in a column. However, this method in general requires 2l^2 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.

PDF CVPR Semantic Scholar

Cite

Text

Ajanthan et al. "Memory Efficient Max Flow for Multi-Label Submodular MRFs." Conference on Computer Vision and Pattern Recognition, 2016. doi:10.1109/CVPR.2016.632

Markdown

[Ajanthan et al. "Memory Efficient Max Flow for Multi-Label Submodular MRFs." Conference on Computer Vision and Pattern Recognition, 2016.](https://mlanthology.org/cvpr/2016/ajanthan2016cvpr-memory/) doi:10.1109/CVPR.2016.632

BibTeX

@inproceedings{ajanthan2016cvpr-memory,
  title     = {{Memory Efficient Max Flow for Multi-Label Submodular MRFs}},
  author    = {Ajanthan, Thalaiyasingam and Hartley, Richard and Salzmann, Mathieu},
  booktitle = {Conference on Computer Vision and Pattern Recognition},
  year      = {2016},
  doi       = {10.1109/CVPR.2016.632},
  url       = {https://mlanthology.org/cvpr/2016/ajanthan2016cvpr-memory/}
}