Optimizing Binary MRFs via Extended Roof Duality

By Carsten Rother, Vladimir Kolmogorov, Victor S. Lempitsky, Martin Szummer. 2007

510 citations recorded by the source corpus.

Subfields: Computer Vision and Pattern Recognition

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

Citations in the corpus

Learning human activities and object affordances from RGB-D videos (2012, methodology): “However, its equivalent formulation as the following mixed-integer program has a linear relaxation which can be solved efficiently as a quadratic pseudo-Boolean optimization problem using a graph-cut method (Rother et al., 2007).”
Anticipating Human Activities Using Object Affordances for Reactive Robotic Response (2013, positive): “…program has a linear relaxation which can be solved efficiently as a quadratic pseudo-Boolean optimization problem using a graph-cut method [79] as described in [5] ^ y ¼ argmax y max z X i2V X k2K y k i w k n Á f n ðiÞ Â Ã þ X ði;jÞ2E X ðl;kÞ2KÂK z lk ij w lk e Á f e ði; jÞ Â Ã (11) 8i;…”
ClassCut for Unsupervised Class Segmentation (2010, methodology): “Our segmentation model for stage (2) is a binary pairwise energy function, which can be optimized eﬃciently by techniques used in interactive segmentation [1, 3, 22], but jointly over all images rather than on a single image [1] (sec.”
An Exemplar-Based CRF for Multi-instance Object Segmentation (2014, methodology): “We resort to QBPO to solve minimization in the expansion moves [20].”
Relating Things and Stuff via ObjectProperty Interactions (2014, methodology): “Notice that our inference algorithm does not rely on sophisticated techniques such as QPBO [31] which requires more memory and computation time.”
Human Activity Learning using Object Affordances from RGB-D Videos (2012, background): “However, its equivalent formulation as the following mixed-integer program has a linear relaxation which can be solved efﬁciently as a quadratic pseudo-Boolean optimization problem using a graph-cut method [27].”
3D Scene Flow Estimation with a Piecewise Rigid Scene Model (2015, methodology): “We apply the QPBO-I algorithm to the optimization problem given by our three-frame version ( VC-3F ) and count the number of unlabeled nodes and supermodular edges over the course of the optimization.”
Fast Supervised Hashing with Decision Trees for High-Dimensional Data (2014, unknown): “Hence ∀i, j ∈ B, θij(1, 1) + θij(−1,−1) ≤ 0 ≤ θij(1,−1) + θij(−1, 1), which prove the sub-modularity of (8a) [19].”
A convex relaxation approach for computing minimal partitions (2009, background): “While the discrete problem can be tackled using iterated binary optimization via αexpansion [5] or roof duality relaxation [27], such algorithms tend to exhibit a grid bias (metrication errors) in representing the continuous perimeters in (1).”
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.”
Object scene flow for autonomous vehicles (2015, methodology): “…and stereo [2,3,42], Vogel et al. [35,37] proposed a slanted-plane model which assigns each pixel to an image segment and each segment to one of several rigidly moving 3D plane proposals, thus casting the task as a discrete optimization problem which can be solved using α -expansion and QPBO [26].”
Piecewise Rigid Scene Flow (2013, background): “The weight γ balances plain boundary distance vs. curvature.”
Higher-order clique reduction in binary graph cut (2009, methodology): “This method by Boros, Hammer, and their co-workers [2, 4, 9] is variously called QPBO[15] or roof-duality[26].”
Robust Multiperson Tracking from a Mobile Platform (2009, methodology): “, the multibranch method of [46], or QBPO-I [44].”
Learning latent structure for activity recognition (2014, methodology): “For inference in the loopy graph, they solve it as a quadratic optimization problem using the graph-cut method [13].”
Discriminative Models for Multi-Class Object Layout (2009, result): “2We also tested QPBO (Rother et al. 2007) which gave similar results.”