Fast approximate energy minimization via graph cuts

By Yuri Boykov, Olga Veksler, Ramin Zabih. 2001

8,381 citations recorded by the source corpus.

Subfields: Computer Vision and Pattern Recognition, Mathematical Optimization, Algorithms & Complexity

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 Mathematical Optimization

In Algorithms & Complexity

Citations in the corpus

Open-World Instance Segmentation: Exploiting Pseudo Ground Truth From Learned Pairwise Affinity (2022, methodology): “Pairwise affinity is used in most graph-based segmentation methods [7, 23, 24] as an important term defining a relation graph of pixels for segmentation.”
Seeing Stars: Exploiting Class Relationships for Sentiment Categorization with Respect to Rating Scales (2005, methodology): “…multi-label optimization problem is intractable, but for many families of f functions (e.g., convex) there exist practical exact or approximation algorithms based on techniques for ﬁnding minimum s-t cuts in graphs (Ishikawa and Geiger, 1998; Boykov, Veksler, and Zabih, 1999; Ishikawa, 2003).”
A Sentimental Education: Sentiment Analysis Using Subjectivity Summarization Based on Minimum Cuts (2004, methodology): “Our approach is inspired by Blum and Chawla (2001), although they focused on similarity between items (the motivation being to combine labeled and unlabeled data), whereas we are concerned with physical proximity between the items to be classiﬁed; indeed, in computer vision, modeling proximity…”
Countering Adversarial Images using Input Transformations (2018, methodology): “The algorithm places appropriate patches in the database for a predeﬁned set of grid points, and computes minimum graph cuts (Boykov et al., 2001) in all overlapping boundary regions to remove edge artifacts.”
ScribbleSup: Scribble-Supervised Convolutional Networks for Semantic Segmentation (2016, background): “(5) can be solved by the graph cuts solution [3, 2].”
An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision (2001, background): “Journal of the Asso iation for Computing Ma hinery, 35(4):921{940, O tober 1988.”
SIFT Flow: Dense Correspondence across Scenes and Its Applications (2011, background): “The chance that some of the nearest neighbors share the same scene characteristics with a query image increases as the database grows, and the correspondence obtained by SIFT flow can be semantically meaningful.”
Discovering states and transformations in image collections (2015, methodology): “State classification To implement state classification we optimize our CRF model from Equation 4 using the method from [2].”
An empirical study of context in object detection (2009, methodology): “Inference: Each candidate detection is segmented using graph cuts [3], after resizing the image so that the object length is 100 pixels.”
Image Segmentation Using Deep Learning: A Survey (2020, methodology): “Numerous image segmentation algorithms have been developed in the literature, from the earliest methods, such as thresholding [4], histogram-based bundling, regiongrowing [5], k-means clustering [6], watershed methods [7], to more advanced algorithms such as active contours [8], graph cuts [9], cond”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “ng convex optimization problems involving the Lov´asz extension. Extensions. Note that cut functions can be extended to cuts in hypergraphs, which may have interesting applications in computer vision [31]. Moreover, directed cuts (i.e., when 1More precisely, if the directed graph G = (V,E) is strong”
Discrete optimization of ray potentials for semantic 3D reconstruction (2015, methodology): “As a graph-cut solver, we eventually used the IBFS algorithm [10] algorithm, which was typically 5−50× faster than commonly used Boykov-Kolmogorov [3] algorithm optimized for lattice graphs.”
What, Where and How Many? Combining Object Detectors and CRFs (2010, methodology): “The CRF was solved efﬁciently using the graph cut based α -expansion algorithm [2,23].”
A Fully Convolutional Two-Stream Fusion Network for Interactive Image Segmentation (2018, methodology): “With this graph structure, interactive image segmentation is formulated as an energy minimization problem which can be solved by graph cuts [22, 23].”