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

A. Osokin; D. Vetrov; Kolmogorov V.

doi:10.1109/CVPR.2011.5995361

Publications

?

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

P. 1889–1896.

Osokin A., Vetrov D., Kolmogorov V.

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, submodular 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.

Language: English

DOI

Text on another site

Keywords: markov random field Algorithms for Discrete Optimization graph cuts energy minimization

In book

Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2011)

Colorado Springs: IEEE, 2011.

Optimal Two-Sided Embeddings of Complete Binary Trees in Rectangular Grids

Высоцкий Л. И., Ложкин С. А., Computational Mathematics and Modeling 2019 Vol. 30 No. 2 P. 115–128

The article considers the construction of optimal-area homeomorphic embeddings of complete binary trees in rectangular grids such that the leaf images are on the opposite sides of the grid and the edge images intersect only at node images. The minimum grid area that admits the embedding of a complete binary tree of depth n is ...

Added: November 10, 2020

Large-Scale and Distributed Optimization

Giselsson P., Rantzer A., Springer, 2018.

This book presents tools and methods for large-scale and distributed optimization. Since many methods in "Big Data" fields rely on solving large-scale optimization problems, often in distributed fashion, this topic has over the last decade emerged to become very important. As well as specific coverage of this active research field, the book serves as a ...

Added: October 29, 2020

Marginal Weighted Maximum Log-likelihood for Efficient Learning of Perturb-and-Map models

Shpakova T., Bach F., Osokin A., , in: Proceedings of the international conference on Uncertainty in Artificial Intelligence (UAI 2018).: [б.и.], 2018. P. 1–11.

We consider the structured-output prediction problem through probabilistic approaches and generalize the ``''perturb-and-MAP'' framework to more challenging weighted Hamming losses, which are crucial in applications. While in principle our approach is a straightforward marginalization, it requires solving many related MAP inference problems. We show that for log-supermodular pairwise models these operations can be performed efficiently ...

Added: October 29, 2018

Tree-Serial Parametric Dynamic Programming With Flexible Prior Model For Image Denoising

Pham Cong T., Копылов А. В., Computer Optics 2018 P. 1–8

We consider here image denoising procedures, based on computationally effective tree-serial parametric dynamic programming procedures, different representations of an image lattice by the set of acyclic graphs and non-convex regularization of a new type which allows to flexibly set a priori preferences. Experimental results in image denoising, as well as comparison with related methods, are ...

Added: July 21, 2018

A Principled Deep Random Field Model for Image Segmentation

Kohli P., Osokin A., Jegelka S., , in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2013).: Portland: IEEE, 2013. P. 1971–1978.

We discuss a model for image segmentation that is able to overcome the short-boundary bias observed in standard pairwise random field based approaches. To wit, we show that a random field with multi-layered hidden units can encode boundary preserving higher order potentials such as the ones used in the cooperative cuts model of [11] while ...

Added: October 19, 2017

Minimizing sparse high-order energies by submodular vertex-cover

Delong A., Veksler O., Osokin A. et al., , in: Advances in Neural Information Processing Systems 26 (NIPS 2012).: Lake Tahoe: Curran Associates, Inc., 2012.

Inference in high-order graphical models has become important in recent years. Several approaches are based, for example, on generalized message-passing, or on transformation to a pairwise model with extra 'auxiliary' variables. We focus on a special case where a much more efficient transformation is possible. Instead of adding variables, we transform the original problem into ...

Added: October 18, 2017

Fast Approximate Energy Minimization with Label Costs

Delong A., Osokin A., Isack H. et al., International Journal of Computer Vision 2012 Vol. 96 No. 1 P. 1–27

The α-expansion algorithm has had a significant impact in computer vision due to its generality, effectiveness, and speed. It is commonly used to minimize energies that involve unary, pairwise, and specialized higher-order terms. Our main algorithmic contribution is an extension of α-expansion that also optimizes “label costs” with well-characterized optimality bounds. Label costs penalize a solution based ...

Added: October 18, 2017

Fast approximate energy minimization with label costs

Delong A., Osokin A., Isack H. et al., , in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2010).: San Francisco: IEEE, 2010. P. 2173–2180.

The α-expansion algorithm [4] has had a significant impact in computer vision due to its generality, effectiveness, and speed. Thus far it can only minimize energies that involve unary, pairwise, and specialized higher-order terms. Our main contribution is to extend α-expansion so that it can simultaneously optimize “label costs” as well. An energy with label ...

Added: October 18, 2017

Image Processing Procedures Based on Multi-Quadratic Dynamic Programming

Pham Cong Thang, Informatica (Ljubljana) 2017 No. 41 P. 255–256

Added: October 3, 2017

Learning a Model for Shape-Constrained Image Segmentation from Weakly Labeled Data.

Yangel B. K., Vetrov D., Lecture Notes in Computer Science 2013 Vol. 8081 P. 137–150

In the paper we address a challenging problem of incorporating preferences on possible shapes of an object in a binary image segmentation framework. We extend the well-known conditional random fields model by adding new variables that are responsible for the shape of an object. We describe the shape via a flexible graph augmented with vertex ...

Added: July 12, 2014