Graph cuts are a cornerstone of computer vision. By mapping an image labeling problem to a network graph, researchers can find the exact global minimum of an energy function in polynomial time using standard max-flow/min-cut algorithms. This approach powers everything from basic foreground-background segmentation to dense stereo matching.
However, this elegant mathematical guarantee relies entirely on a strict condition called submodularity. In a binary labeling problem (where every pixel must be assigned a label of 0 or 1), an energy function is submodular if its pairwise interactions satisfy a "diminishing returns" property: the cost of assigning neighboring pixels different labels must be greater than or equal to the cost of assigning them the same label. Visually, submodularity acts as a smoothing prior, penalizing ragged boundaries and rewarding consistency.
The Wall of Non-Submodularity
Real-world computer vision problems quickly break this assumption. When an energy function contains non-submodular (or supermodular) terms, mapping the problem directly to a graph would require edges with negative capacities. This breaks standard max-flow algorithms, turning an easily solvable problem into an NP-hard challenge.
Non-submodular terms naturally emerge whenever we try to model complex physical or geometric constraints:
- Exclusion Constraints: When segmenting thousands of dense, closely packed objects like biological cells, we must explicitly forbid them from overlapping. As Jensen et al. and Jeppesen et al. demonstrate, enforcing that two distinct objects cannot occupy the same spatial pixel introduces rigid non-submodular penalties.
- High-Order Geometry: Standard submodular graph cuts minimize boundary length, which introduces a notorious "shrinking bias" that accidentally destroys thin, elongated structures. To preserve fine details, we need higher-order geometric priors like squared curvature (Nieuwenhuis et al.) or global shape convexity (Gorelick et al.). These sophisticated structural priors inherently generate non-submodular energy landscapes.
- System Inversions and Ray Physics: Tasks like generalized image deconvolution (Raj et al.), multi-view volumetric reconstruction (Savinov et al.), and light-field triangulation (Yu et al.) involve non-diagonal system matrices or complex visibility constraints across camera rays. These relationships create highly connected graphs with pervasive non-submodular interactions.
Relaxations and the Integrality Gap
To bypass this wall, a traditional workaround is Quadratic Pseudo-Boolean Optimization (QPBO). Instead of forcing every pixel to take a strict binary label, QPBO relaxes the problem. It builds a graph with twice as many nodes—representing both the literal label and its mathematical inverse—allowing the optimization to proceed despite non-submodular terms.
As shown in applications ranging from high-order stereo reconstruction (Jung et al.) to multi-object tracking, QPBO guarantees that any pixel it successfully labels is part of the global optimum. However, for highly non-submodular problems, QPBO suffers from a severe integrality gap: it frequently leaves a massive portion of the pixels "unlabeled" or ambiguous. Resolving these unlabeled regions requires secondary, computationally expensive heuristics like alpha-expansion or local search.
The Intuition of Local Submodular Approximations
To avoid the ambiguous, unlabeled pixels left behind by relaxations, a powerful alternative paradigm emerged: Local Submodular Approximation (LSA), formalized by Gorelick et al..
Instead of changing the optimization algorithm to accommodate a difficult energy function, LSA changes the energy function itself, iteratively. The core intuition is highly analogous to gradient descent. If a complex, non-convex function is too difficult to minimize globally, we can approximate it with a simpler, well-behaved function within a small neighborhood, take an optimal step, and repeat.
[Original Non-Submodular Energy]
│
▼
[Isolate Supermodular Terms]
│
▼
[First-Order Taylor Expansion] ──► (Converts terms to linear/submodular)
│
▼
[Enforce Trust Region] ──► (Restricts how many labels can flip)
│
▼
[Standard Max-Flow Solver] ──► (Finds exact minimum for this step)
│
▼
[Update Expansion Point] ──► (Iterate until convergence)
The LSA framework executes this strategy through three precise mathematical steps:
- Isolate the Problem: The global energy function is split into two parts: its naturally submodular components (which are easy to map to a graph) and its supermodular components (the problematic non-submodular terms).
- Linearize via Taylor Expansion: The authors show that computing a first-order Taylor expansion of the supermodular components around the current labeling configuration completely neutralizes them. Because linear functions inherently satisfy the submodularity condition with strict equality, this mathematical transformation converts the entire local energy function into a purely submodular form. Other variations on this theme construct strict submodular overestimates (Fix et al.) or dynamically reweight non-compliant edges to satisfy submodularity (Liu et al.).
- Enforce a Trust Region: A Taylor expansion is only an accurate reflection of the true energy surface in a small neighborhood around the current state. To prevent the optimization from making wild, inaccurate moves, the approximation is bound within a trust region. This constraint strictly limits the number of variables allowed to change their labels during a single iteration.
Because the approximated energy function within the trust region is guaranteed to be submodular, researchers can deploy standard, lightning-fast max-flow solvers to find the exact optimal step within that neighborhood. By updating the expansion point and shifting the trust region iteratively, the algorithm smoothly converges to a high-quality local minimum.
Why It Works
Local submodular approximations provide a major computational leap forward for complex vision tasks. For instance, in large-scale object detection modeled via point processes, Rezatofighi et al. utilized local submodular approximations to optimize complex interaction terms that were previously considered computationally intractable. Similarly, Nieuwenhuis et al. demonstrated that combining LSA with trust regions allows high-resolution curvature models to run orders of magnitude faster than traditional linear programming methods, completely avoiding blocky artifacts.
Ultimately, this direction succeeds because it unlocks the hidden potential of existing optimization infrastructure. As Arora 0001 et al. observed, solvers designed strictly for submodular potentials possess a surprising, latent capacity to effectively approximate non-submodular problems. By breaking down non-convex, non-submodular challenges into a controlled sequence of submodular sub-problems, LSA allows computer vision to retain the speed, determinism, and elegance of classic graph cuts while conquering highly complex physical and geometric models.
Key Foundational Work
A Graph Cut Algorithm for Generalized Image Deconvolution (2005) — contributed 1 concept elements to this direction.
Stereo reconstruction using high order likelihood (2011) — contributed 1 concept elements to this direction.