Minimizing Nonsubmodular Functions with Graph Cuts-A Review

By Vladimir Kolmogorov, Carsten Rother. 2007

438 citations recorded by the source corpus.

Subfields: Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “2 (right).”
Optical flow modeling and computation: A survey (2015, methodology): “Finding good approximate solution can be achieved with the Quadratic Pseudo Boolean Optimization (QPBO) [35,148,209], leading to an optimal but partial labeling.”
Global Hypothesis Generation for 6D Object Pose Estimation (2016, methodology): “[17], Proposition 1 is generally applicable to all such models.”
A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors (2008, methodology): “Furthermore, the QBPO algorithm described in [29] can often solve problems that violate the regularity condition.”
Context-Aware CNNs for Person Head Detection (2015, methodology): “ation problems of (4) can be solved exactly using exhaustive search. When the number of candidates becomes larger, the exhaustive search becomes too slow. In this case one can use the cascade of QPBO [17] and TRWS [16] methods to approximate s i. Speciﬁcally, QPBO allows to quickly determine the opt”
Layered segmentation and optical flow estimation over time (2012, methodology): “In contrast to gradient-based methods, discrete optimization methods like graph cuts [4, 14] can substantially change the configuration of the solution in a single move.”
Global Optimization for Shape Fitting (2007, neutral): “The algorithm initializes some band around an initial guess, and then modifies the band in a series of touch-expand steps.”
Advanced Structured Prediction (2014, methodology): “These include, for example, cut based algorithms (Boykov et al., 1999; Kolmogorov and Rother, 2007), accelerated gradient methods (Jojic et al.”
Minimizing Energies with Hierarchical Costs (2012, methodology): “Ours is therefore a graph cut approach that does not rely on QPBO, message passing (Kolmogorov 2006), or other LP relaxations (Werner 2008).”
Training structural SVMs when exact inference is intractable (2008, methodology): “Cut is quadratic pseudo-Boolean optimization using a graph-cut ( Kolmogorov & Rother, 2004 ).”
ClassCut for Unsupervised Class Segmentation (2010, methodology): “We discussed in the introduction that our method employs energy minimization techniques used in interactive segmentation [1,3,4,14,15], and how it is related to supervised [5,7,19] as well as to unsupervised [2,10–12] class segmentation methods.”
Structured Learning and Prediction in Computer Vision (2011, methodology): “For energies which do not satisfy regularity conditions, Kolmogorov and Rother [79] give a graphcut-based iterative algorithm, QPBO, that uses probing techniques from combinatorial optimization, producing an approximate minimizer.”
Higher-order clique reduction in binary graph cut (2009, methodology): “Although it is not a solution to every problem, the QPBO technique often allows solving a non-submodular problem approximately by giving a large enough part of the globally optimal move to iteratively improve the solution.”
Optimizing Binary MRFs via Extended Roof Duality (2007, methodology): “We have done this for one Brodatz texture D103 (see [18]) where the test error (averaged over 20 examples) reduces from25.”
Perturb-and-MAP random fields: Using discrete optimization to learn and sample from energy models (2011, methodology): “We used our Perturb-and-MAP sampling algorithm with order-2 Gumbel perturbation and QPBO optimization [16] to learn the weights of the poten tials - 5 weights in total, one for the unary and one for each of the 4 pairwise connections of the center pixel with its S, E, NE, SE neighbors.”
Spectral Matting (2007, background): “(see [12] for a review on such methods ).”