Submodular decomposition framework for inference in associative Markov networks with global constraints

A. Osokin, D. Vetrov, V. Kolmogorov, in:, IEEE, 2011, pp. 1889–1896.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ;
Abstract
In this paper we address the problem of finding the most probable state of discrete Markov random field (MRF) with associative pairwise terms. Although of practical importance, this problem is known to be NP-hard in general. We propose a new type of MRF decomposition, submod-ular decomposition (SMD). Unlike existing decomposition approaches SMD decomposes the initial problem into sub-problems corresponding to a specific class label while preserving the graph structure of each subproblem. Such decomposition enables us to take into account several types of global constraints in an efficient manner. We study theoretical properties of the proposed approach and demonstrate its applicability on a number of problems.
Publishing Year
Date Published
2011-08-22
Page
1889 - 1896
Conference
CVPR: Computer Vision and Pattern Recognition
IST-REx-ID

Cite this

Osokin A, Vetrov D, Kolmogorov V. Submodular decomposition framework for inference in associative Markov networks with global constraints. In: IEEE; 2011:1889-1896. doi:10.1109/CVPR.2011.5995361
Osokin, A., Vetrov, D., & Kolmogorov, V. (2011). Submodular decomposition framework for inference in associative Markov networks with global constraints (pp. 1889–1896). Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2011.5995361
Osokin, Anton, Dmitry Vetrov, and Vladimir Kolmogorov. “Submodular Decomposition Framework for Inference in Associative Markov Networks with Global Constraints,” 1889–96. IEEE, 2011. https://doi.org/10.1109/CVPR.2011.5995361.
A. Osokin, D. Vetrov, and V. Kolmogorov, “Submodular decomposition framework for inference in associative Markov networks with global constraints,” presented at the CVPR: Computer Vision and Pattern Recognition, 2011, pp. 1889–1896.
Osokin A, Vetrov D, Kolmogorov V. 2011. Submodular decomposition framework for inference in associative Markov networks with global constraints. CVPR: Computer Vision and Pattern Recognition 1889–1896.
Osokin, Anton, et al. Submodular Decomposition Framework for Inference in Associative Markov Networks with Global Constraints. IEEE, 2011, pp. 1889–96, doi:10.1109/CVPR.2011.5995361.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar