An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision

By Yuri Boykov, Vladimir Kolmogorov. 2001

5,382 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

Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, methodology): “For OCR and CoNLL, the max oracle consists of the Viterbi algorithm (Viterbi, 1967); for HorseSeg – in graph cut (Boykov & Kolmogorov, 2004), for LSP – in belief propagation on a tree with messages passed by a generalized distance transform (Felzenszwalb & Huttenlocher, 2005).”
Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “The models are close to submodular and the local relaxation is a good approximation to the marginal polytope.”
Extreme Clicking for Efficient Object Annotation (2017, methodology): “Most of this work is based on the seminal GrabCut algorithm [51], which iteratively alternates between estimating appearance models (typically Gaussian Mixture Models [6]) and refining the segmentation using graph cuts [9].”
Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent (2011, background): “Problems involving minimum cuts in graphs frequently arise in machine learning (see [6] for a comprehensive survey).”
Structured Prediction Energy Networks (2015, background): “(Boykov & Kolmogorov, 2004; Globerson & Jaakkola, 2008).”
ScribbleSup: Scribble-Supervised Convolutional Networks for Semantic Segmentation (2016, background): “(5) can be solved by the graph cuts solution [3, 2].”
Instance-Level Segmentation for Autonomous Driving with Deep Densely Connected MRFs (2015, methodology): “In interactive segmentation, approaches like Grabcut [24, 4] require a user-supplied box, or a scribble on the foreground and background, in order to segment the objects.”
A comparative evaluation of interactive segmentation algorithms (2010, positive): “Using this graph, an optimal minimization of (1) can be found efficiently using min-cut/max-flow algorithm described in [17].”
Ensemble Video Object Cut in Highly Dynamic Scenes (2013, methodology): “This type of links are called N -links [2].”
Saliency filters: Contrast based filtering for salient region detection (2012, methodology): “One option to significantly reduce this effect is to perform a single min-cut segmentation [6] as a post process, using our saliency maps as a prior for the min-cut data term, and color differences between neighboring pixels for the smoothness term.”
Training Object Class Detectors from Eye Tracking Data (2014, positive): “The first step is solved globally optimally by minimizing (1) using graph-cuts [5] as our pairwise potentials are submodular.”
Superpixel segmentation using Linear Spectral Clustering (2015, methodology): “formulated superpixel segmentation as an energy optimization problem which was then solved using the min-cut/max-flow algorithm [4][3][10].”
Multi-View Stereo: A Tutorial (2015, methodology): “Given the MRF formulation, the α-expansion algorithm is used to minimize the energy and estimate a planemap [44, 45, 121].”
3D all the way: Semantic segmentation of urban scenes from start to end in 3D (2015, methodology): “The final assignment is optimized with a multi-label graphcut [7, 6, 23], which assigns all original 3D points P w.”