Graph cuts in computer vision and artificial intelligence

As applied in the field of computer vision, graph cut optimization can be employed to efficiently solve a wide variety of low-level computer vision problems (early vision^[1]), such as image smoothing, the stereo correspondence problem, image segmentation, object co-segmentation, numerous military applications (eg Automatic target recognition) and many other problems that can be formulated in terms of energy minimization (eg Climate Science and Environmental modelling).

Graph cut techniques are now increasingly being used in combination with more general spatial Artificial intelligence techniques (eg to enforce structure in Large language model output to sharpen tumour boundaries and similarly for various Augmented reality, Self-driving car, Robotics, Google Maps applications etc).

Many of these energy minimization problems can be approximated by solving a maximum flow problem in a graph^[2] (and thus, by the max-flow min-cut theorem, define a minimal cut of the graph). Under most formulations of such problems in computer vision, the minimum energy solution corresponds to the maximum a posteriori estimate of a solution.

Although many computer vision algorithms involve cutting a graph (e.g. normalized cuts), the term "graph cuts" is applied specifically to those models which employ a max-flow/min-cut optimization (other graph cutting algorithms may be considered as graph partitioning algorithms).

"Binary" problems (such as denoising a binary image) can be solved exactly using this approach; problems where pixels can be labeled with more than two different labels (such as stereo correspondence, or denoising of a grayscale image) cannot be solved exactly, but solutions produced are usually near the global optimum.

History

The foundational theory of graph cuts in computer vision was first developed by Margaret Greig, Bruce Porteous and Allan Seheult (GPS) of Durham University in a now legendary discussion contribution to Julian Besag's 1986 paper^[3] and a more detailed follow on paper^[4] in 1989. In the Bayesian statistical context of smoothing noisy images, using a Markov random field as the image prior distribution, they showed with a mathematically beautiful proof how the maximum a posteriori estimate of a binary image can be obtained exactly by maximizing the flow through an associated image network, or graph, involving the introduction of a source and sink and Log-likelihood ratios. The problem was shown to be efficiently solvable exactly, an unexpected result as the problem was believed to be computationally intractable (NP hard).

GPS also addressed the computational cost of the max-flow algorithm on large graphs, a significant concern at the time. They proposed a partitioning algorithm (see Section 4 of GPS) involving the recursive amalgamation of non-overlapping blocks, or tiles, which gave a 12X increase in speed. This approach recursively solved and amalgamated independent sub-graphs until the whole graph was solved. While contemporaries like Geman and Geman^[5] had advocated Parallel computing in the context of Simulated annealing, the GPS blocking strategy offered a deterministic structure amenable to parallelisation and anticipated modern artificial intelligence design across multiple GPUs. However, until recently, this aspect of the paper was largely ignored and subsequent research focused on Serial computer global search trees, such as the Boykov-Kolmogorov^[6] algorithm.

Although the general $k$ -colour problem is NP hard for $k>2,$ the GPS approach has turned out to have very wide applicability in general computer vision problems. This was first demonstrated by Boykov, Veksler and Zabih^[2] who, in a seminal paper published more than 10 years after the original GPS paper, and in other important works, lit the blue touch paper for the general adoption of graph cut techniques in computer vision. They showed that, for general problems, the GPS approach can be applied iteratively to sequences of binary problems, using their now ubiquitous alpha-expansion algorithm, yielding near optimal solutions. Prior to these results, approximate local optimisation techniques such as simulated annealing (as proposed by the Geman brothers^[5]) or iterated conditional modes (a type of greedy algorithm suggested by Julian Besag^[3]) were used to solve such image smoothing problems.

Building on these advancements, GPS graph cut optimization was subsequently adapted for interactive image segmentation, most notably through the "GrabCut" algorithm introduced by Carsten Rother, Vladimir Kolmogorov, and Andrew Blake^[7] of Microsoft Research, Cambridge. GrabCut extended earlier interactive graph cut methods by replacing monochrome image histograms with Gaussian mixture models to estimate colour distributions, and by employing an iterative GPS energy minimisation scheme. This approach significantly simplified user interaction, requiring only a rough bounding box around the target object rather than detailed user-drawn strokes, and it quickly became a standard tool in both academic research and commercial image editing software.

The GPS paper connected and bridged profound ideas from Mathematical statistics (Bayes' theorem, Markov random field^[8]^[9]), Physics (Ising model), Optimisation (Energy function) and Computer science (Network flow problem) and led the move away from approximate local and slow optimisation approaches (eg simulated annealing) to more powerful exact, or near exact, faster global optimisation techniques. It is now recognised as seminal as it was well ahead of its time and, in particular, was published years before the computing power revolution of Moore's law and GPUs.

Significantly, GPS was published in a mathematical statistics (rather than a computer vision) journal, and this led to it being overlooked by the computer vision community for many years. It is unofficially known as "The Velvet Underground" paper of computer vision (ie although very few computer vision people read the paper [bought the record], those that did, most importantly Boykov, Veksler and Zabih^[2], started new and important research [formed a band]). This is confirmed by GPS' very large amplification ratio (2nd order citations/first order citations), estimated at well in excess of 100.

Despite the foundational nature of the GPS work, formal recognition from the computer vision community has predominantly gone to the researchers who followed to extend and popularise the graph cut method. For example, Boykov, Veksler and Zabih ^[2] deservedly received a Helmholtz Prize from the ICCV in 2011^[10]. This prize recognises ICCV papers from 10 or more years earlier that have had a significant impact on computer vision research.

In 2011, Couprie et al.^[11] proposed a general image segmentation framework, called the "Power Watershed", that minimized a real-valued indicator function from [0,1] over a graph, constrained by user seeds (or unary terms) set to 0 or 1, in which the minimization of the indicator function over the graph is optimized with respect to an exponent $p$ . When $p=1$ , the Power Watershed is optimized by graph cuts, when $p=0$ the Power Watershed is optimized by shortest paths, $p=2$ is optimized by the random walker algorithm and $p=\infty$ is optimized by the watershed algorithm. In this way, the Power Watershed may be viewed as a generalization of graph cuts that provides a straightforward connection with other energy optimization segmentation/clustering algorithms.

Binary segmentation of images

Notation

Image: $x\in \{R,G,B\}^{N}$
Output: Segmentation (also called opacity) $S\in R^{N}$ (soft segmentation). For hard segmentation $S\in \{0{\text{ for background}},1{\text{ for foreground/object to be detected}}\}^{N}$
Energy function: $E(x,S,C,\lambda )$ where C is the color parameter and λ is the coherence parameter.
$E(x,S,C,\lambda )=E_{\rm {color}}+E_{\rm {coherence}}$
Optimization: The segmentation can be estimated as a global minimum over S: ${\arg \min }_{S}E(x,S,C,\lambda )$

Existing methods

Standard Graph cuts: optimize energy function over the segmentation (unknown S value).
Iterated Graph cuts:

First step optimizes over the color parameters using K-means.
Second step performs the usual graph cuts algorithm.

These 2 steps are repeated recursively until convergence

Dynamic graph cuts:
Allows to re-run the algorithm much faster after modifying the problem (e.g. after new seeds have been added by a user).

Energy function

\Pr(x\mid S)=K^{-E}

where the energy $E$ is composed of two different models ( $E_{\rm {color}}$ and $E_{\rm {coherence}}$ ):

Likelihood / Color model / Regional term

$E_{\rm {color}}$ — unary term describing the likelihood of each color.

This term can be modeled using different local (e.g. texons) or global (e.g. histograms, GMMs, Adaboost likelihood) approaches that are described below.

Histogram

We use intensities of pixels marked as seeds to get histograms for object (foreground) and background intensity distributions: P(I|O) and P(I|B).
Then, we use these histograms to set the regional penalties as negative log-likelihoods.

GMM (Gaussian mixture model)

We usually use two distributions: one for background modelling and another for foreground pixels.
Use a Gaussian mixture model (with 5–8 components) to model those 2 distributions.
Goal: Try to pull apart those two distributions.

Texon

A texon (or texton) is a set of pixels that has certain characteristics and is repeated in an image.
Steps:

Determine a good natural scale for the texture elements.
Compute non-parametric statistics of the model-interior texons, either on intensity or on Gabor filter responses.

Examples:
- Deformable-model based Textured Object Segmentation
- Contour and Texture Analysis for Image Segmentation

Prior / Coherence model / Boundary term

$E_{\rm {coherence}}$ — binary term describing the coherence between neighborhood pixels.

In practice, pixels are defined as neighbors if they are adjacent either horizontally, vertically or diagonally (4 way connectivity or 8 way connectivity for 2D images).
Costs can be based on local intensity gradient, Laplacian zero-crossing, gradient direction, color mixture model,...
Different energy functions have been defined:
- Standard Markov random field: Associate a penalty to disagreeing pixels by evaluating the difference between their segmentation label (crude measure of the length of the boundaries). See Boykov and Kolmogorov ICCV 2003
- Conditional random field: If the color is very different, it might be a good place to put a boundary. See Lafferty et al. 2001; Kumar and Hebert 2003

Criticism

Graph cuts methods have become popular alternatives to the level set-based approaches for optimizing the location of a contour (see^[12] for an extensive comparison). However, graph cut approaches have been criticized in the literature for several issues:

Metrication artifacts: When an image is represented by a 4-connected lattice, graph cuts methods can exhibit unwanted "blockiness" artifacts. Various methods have been proposed for addressing this issue, such as using additional edges^[13] or by formulating the max-flow problem in continuous space.^[14]
Shrinking bias: Since graph cuts finds a minimum cut, the algorithm can be biased toward producing a small contour.^[15] For example, the algorithm is not well-suited for segmentation of thin objects like blood vessels (see^[16] for a proposed fix).
Multiple labels: Graph cuts is only able to find a global optimum for binary labeling (i.e., two labels) problems, such as foreground/background image segmentation. Extensions have been proposed that can find approximate solutions for multilabel graph cuts problems.^[2]
Memory: the memory usage of graph cuts increases quickly as the image size increases. As an illustration, the Boykov-Kolmogorov max-flow algorithm v2.2 allocates $24n+14m$ bytes ( $n$ and $m$ are respectively the number of nodes and edges in the graph). Nevertheless, some amount of work has been recently done in this direction for reducing the graphs before the maximum-flow computation.^[17]^[18]^[19]

Historic Limitations

While graph cuts provide mathematically optimal solutions for specific energy functions, their use as a standalone method for general object recognition declined with the advent of deep learning. The primary limitations include:

Semantic gap: Graph cuts rely on low-level cues (pixel intensity, color, texture) and lack high-level semantic understanding. They cannot distinguish between semantically different objects that share similar visual characteristics (e.g., distinguishing a dog from a cat of the same color).
Computational cost: The iterative nature of max-flow algorithms (typically $O(V^{2}E)$ or $O(V^{3})$ ) makes them computationally expensive for high-resolution video compared to the feed-forward inference of neural networks.
Parallelization: Unlike matrix multiplications in neural networks, graph cut algorithms are difficult to parallelize efficiently on modern GPUs, creating a bottleneck in real-time pipelines.

However, they remain a standard tool for interactive segmentation (e.g., rotoscoping in visual effects), where a user provides the semantic intent (via scribbles) and the algorithm handles the boundary precision. As described below, they are increasingly being integrated into modern artificial intelligence.

Modern Applications

In the era of deep learning, graph cuts have transitioned from standalone segmentation solvers to integrated components within complex neural architectures. While early applications focused on discrete 2D image labeling, modern use cases leverage the algorithm's ability to provide mathematically rigorous spatial and temporal structure to "soft" neural network outputs.

Integration with Deep Learning

The primary challenge in modern AI integration is that the discrete nature of the min-cut/max-flow algorithm is not naturally differentiable.

Differentiable Layers: Recent frameworks have introduced "soft" or continuous relaxations of the graph cut energy. This allows the algorithm to be used as a Structured Layer within a Convolutional Neural Network (CNN) or Transformer. The network learns to output optimal edge weights and node potentials, which the graph cut layer then optimizes to produce spatially consistent results.
Hybrid Loss Functions: Modern methodologies use graph cut energy as a loss function during training. This forces the model to learn segmentations that align with high-contrast boundaries in the raw input, effectively teaching the AI to respect "physical" edges without requiring massive amounts of pixel-perfect training data.

Foundation Models and Promptable Segmentation

With the advent of large-scale Foundation Models, such as the Segment Anything Model (SAM), graph cuts have found a new role in "refinement heads." While these models are excellent at identifying general objects, they can produce "fuzzy" or non-manifold boundaries. Graph cuts are applied as a post-processing step to "snap" the mask boundaries to high-contrast edges. In low-data regimes, graph cuts propagate labels from a few user-provided "guide points" across the high-dimensional feature embeddings generated by the transformer.

Medical Imaging and 3D Reconstruction

Graph cuts remain a gold standard in medical diagnostics where data is often noisy or sparse.

Volumetric Segmentation: In MRI and CT analysis, graph cuts ensure "topological consistency" in 3D. While a neural network might misidentify individual pixels, the graph cut ensures that anatomical structures, such as blood vessels or tumors, are represented as continuous, connected volumes.
Interactive Segmentation: Modern medical platforms (e.g., MONAI) use graph cuts to enable "human-in-the-loop" AI. A radiologist provides a few "guide clicks" (seeds), and the graph cut combines these manual constraints with deep-learning feature maps to calculate a globally optimal boundary in real-time.

Defense and Remote Sensing

In defense and intelligence, graph cuts are applied to high-resolution sensor data where false positives must be minimized.

SAR and Satellite Analysis: Synthetic Aperture Radar (SAR) imagery is often degraded by "speckle" noise. Graph cuts are used to de-noise and segment these images, allowing for the detection of camouflaged vehicles or changes in terrain.
Spatio-Temporal Tracking: For autonomous surveillance, graph cuts extend into the temporal dimension. By linking pixels across time-frames, the system enforces a "physicality constraint," ensuring that tracked targets maintain a consistent 3D volume and do not "jitter" or fragment across video frames.

Climate Modeling and Environmental Science

Modern climate science utilizes graph-based optimization to bridge the gap between discrete weather station data and continuous atmospheric models.

Multi-Model Ensembles: When combining different Global Climate Models (GCMs), graph cuts select the most accurate model for specific geographic regions. This ensures that the transitions between regional models are spatially smooth and physically consistent, preventing "seams" or artifacts in global precipitation and temperature maps.
Land-Cover Monitoring: By treating satellite time-series data as a 3D graph, researchers use graph cuts to differentiate between permanent land-cover change (deforestation, urbanization) and temporary seasonal variations.

Robotics and Path Planning

In robotics, graph cuts are used for Semantic Mapping . A robot moving through an environment must partition its 3D point cloud into navigable floor space, obstacles, and "unknown" regions. Graph cuts provide a robust way to merge noisy LIDAR data with visual semantic labels, ensuring that the resulting map is segmented into logical, non-overlapping zones that a path-planning algorithm can navigate.

Privacy-Preserving AI and Data Synthesis

Graph cuts are increasingly used in the field of Privacy-Preserving Machine Learning. When generating synthetic datasets or "anonymizing" images, graph cuts can be used to identify and extract sensitive regions (such as faces or license plates) based on energy minimization. This ensures that the boundaries of the removed data are precise enough that no "residual" private information remains at the edges of the cut, which is a common failure point for purely generative (GAN-based) blurring techniques.

Computational Fluid Dynamics (CFD)

In aerospace and weather forecasting, graph cuts assist in Dynamic Mesh Partitioning. To optimize supercomputing resources, graph cuts identify high-complexity regions—such as the eye of a hurricane or the edge of a turbine blade—and partition the computational workload accordingly. This ensures that the "cut," where the most complex physics occurs, receives the highest density of processing power.

Algorithm

Minimization is done using a standard minimum cut algorithm.
Due to the max-flow min-cut theorem we can solve energy minimization by maximizing the flow over the network. The max-flow problem consists of a directed graph with edges labeled with capacities, and there are two distinct nodes: the source and the sink. Intuitively, it is easy to see that the maximum flow is determined by the bottleneck.

Implementation (exact)

The Wikibook Algorithm Implementation has a page on the topic of: Graphs/Maximum flow/Boykov & Kolmogorov

The Boykov-Kolmogorov algorithm^[6] is an efficient way to compute the max-flow for computer vision-related graphs.

Implementation (approximation)

The Sim Cut algorithm^[20] approximates the minimum graph cut. The algorithm implements a solution by simulation of an electrical network. This is the approach suggested by Cederbaum's maximum flow theorem.^[21]^[22] Acceleration of the algorithm is possible through parallel computing.

Software

http://pub.ist.ac.at/~vnk/software.html — An implementation of the maxflow algorithm described in "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Computer Vision" by Vladimir Kolmogorov
http://vision.csd.uwo.ca/code/ — some graph cut libraries and MATLAB wrappers
http://gridcut.com/ — fast multi-core max-flow/min-cut solver optimized for grid-like graphs