Submodular Relaxation for MRFs with High-Order Potentials
Abstract
In the paper we propose a novel dual decomposition scheme for approximate MAP-inference in Markov Random Fields with sparse high-order potentials, i.e. potentials encouraging relatively a small number of variable configurations. We construct a Lagrangian dual of the problem in such a way that it can be efficiently evaluated by minimizing a submodular function with a min-cut/max-flow algorithm. We show the equivalence of this relaxation to a specific type of linear program and derive the conditions under which it is equivalent to generally tighter LP-relaxation solved in [1]. Unlike the latter our relaxation has significantly less dual variables and hence is much easier to solve. We demonstrate its faster convergence on several synthetic and real problems.
Cite
Text
Osokin and Vetrov. "Submodular Relaxation for MRFs with High-Order Potentials." European Conference on Computer Vision, 2012. doi:10.1007/978-3-642-33885-4_31Markdown
[Osokin and Vetrov. "Submodular Relaxation for MRFs with High-Order Potentials." European Conference on Computer Vision, 2012.](https://mlanthology.org/eccv/2012/osokin2012eccv-submodular/) doi:10.1007/978-3-642-33885-4_31BibTeX
@inproceedings{osokin2012eccv-submodular,
title = {{Submodular Relaxation for MRFs with High-Order Potentials}},
author = {Osokin, Anton and Vetrov, Dmitry P.},
booktitle = {European Conference on Computer Vision},
year = {2012},
pages = {305-314},
doi = {10.1007/978-3-642-33885-4_31},
url = {https://mlanthology.org/eccv/2012/osokin2012eccv-submodular/}
}