Global Energy Minimization via Graph Cuts

This direction is merged into another direction: graph-cut energy minimization. Its last version stays readable and citable here.

Version 1 of 181 papers87 conceptsfrozen 2026-10-04

In computer vision, many problems can be framed as a "labeling problem." Whether we are determining the depth of a pixel in a stereo pair, identifying which pixels belong to a foreground object, or tracking a tongue contour in an ultrasound, we are essentially assigning a discrete label to every node in a grid.

The challenge is that these labels are rarely independent. If a pixel is part of a "tree," its neighbor is likely part of a "tree" too. This spatial dependency turns a simple classification task into a massive combinatorial optimization problem. Yuri Boykov, Olga Veksler, and Ramin Zabih pioneered a way to solve these problems by treating them as energy minimization tasks on a graph, a direction that has become a cornerstone of robust image analysis.

The Energy Minimization Framework

To find the "best" labeling, researchers define an energy function $E(L)$ that consists of two competing parts:

  1. Data Fidelity: How well does the label match the observed pixel data?
  2. Smoothness (Prior): How well do the labels of neighboring pixels agree?

The goal is to find the configuration of labels that minimizes this total energy. In Markov Random Fields with Efficient Approximations, the authors demonstrated that for a specific class of energy functions—those that are "submodular" or "associative"—the global minimum can be found exactly and efficiently using a minimum cut algorithm on a graph.

The intuition is elegant: you construct a graph where nodes represent pixels and two special nodes (terminals) represent the labels (e.g., "Foreground" and "Background"). The edges between pixels represent the "cost" of them having different labels. By finding the "minimum cut"—the set of edges with the lowest total weight that, if removed, would separate the two terminals—you effectively find the boundary that minimizes the energy function.

From Binary to Multi-Label: Expansion Moves

While binary segmentation (foreground vs. background) is straightforward, most real-world tasks like stereo matching or semantic segmentation require choosing from dozens of labels. Finding the global minimum for multi-label problems is generally NP-hard.

To solve this, Ramin Zabih and Vladimir Kolmogorov introduced the $\alpha$-expansion algorithm in Computing Visual Correspondence with Occlusions via Graph Cuts. Instead of trying to solve the whole problem at once, the algorithm iterates through each possible label $\alpha$. In each step, it asks: "Which pixels should keep their current label, and which should switch to label $\alpha$ to reduce the total energy?"

This reduces a complex multi-choice problem into a series of binary decisions that can each be solved optimally with a graph cut. This approach is remarkably powerful; Hunter Lang and David Sontag recently showed in Graph Cuts Always Find a Global Optimum for Potts Models (With a Catch) that the local minima found by $\alpha$-expansion are actually global optima for a slightly perturbed version of the original problem, explaining why the algorithm performs so well in practice.

Bridging the Gap to Continuous Spaces

A traditional limitation of graph cuts was their discrete nature—they work on pixels and fixed labels. However, recent work has pushed these boundaries. Tatsunori Taniai developed Graph Cut Based Continuous Stereo Matching Using Locally Shared Labels, which combines the global reasoning of graph cuts with the randomized search of PatchMatch. By proposing "candidate planes" and using graph cuts to fuse them, the method achieves sub-pixel accuracy that discrete methods usually miss.

Similarly, Richard Hartley and Mathieu Salzmann introduced Iteratively Reweighted Graph Cut (IRGC) in Iteratively reweighted graph cut for multi-label MRFs with non-convex priors. This allows the framework to handle non-convex "robust" priors—which are better at preserving sharp edges than standard smoothness terms—by approximating them with a sequence of easier, weighted subproblems.

Applications Across Domains

The versatility of this "labeling-as-optimization" framing has led to its adoption in diverse fields:

By transforming messy, noisy sensor data into a structured graph and finding the "minimum cut," this research direction provides a mathematically rigorous way to enforce global consistency in a world of local uncertainty.

Papers in this version

Showing 60 of 81 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_global_energy_minimization_via_graph_cut_150a65d5,
  title = {Global Energy Minimization via Graph Cuts},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-energy-minimization-via-graph-cuts/rdr_150a65d58da74c73b7ad7e3d21b56c90},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_energy_minimization_via_graph_cut_150a65d5_v1,
  title = {Global Energy Minimization via Graph Cuts},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-energy-minimization-via-graph-cuts/rdr_150a65d58da74c73b7ad7e3d21b56c90/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}