In computer vision and machine learning, many problems are framed as discrete optimization tasks. Whether we are assigning a foreground/background label to pixels in an image, matching stereo pairs, or parsing complex scene grammars, we ultimately seek a configuration of variables that minimizes a global energy function.
For a long time, these problems were considered computationally intractable. Because the state space grows exponentially with the number of variables, finding the exact global minimum of a Markov Random Field (MRF) or Conditional Random Field (CRF) is generally NP-hard.
However, a major breakthrough occurred when researchers realized that a large class of these discrete energy functions possesses a structural property called submodularity (often referred to as regularity in computer vision). When an energy function is submodular, the daunting task of combinatorial optimization can be mapped directly to a network flow problem and solved exactly and efficiently in polynomial time using graph cuts.
The Core Intuition: Submodularity and the Regularity Condition
To understand why submodularity enables exact optimization, let us look at the simplest case: a binary pairwise energy function. Here, we want to assign a label $x_i \in \{0, 1\}$ to each node in a graph to minimize an energy function of the form:
$$E(x) = \sum_{i} E_i(x_i) + \sum_{i,j} E_{ij}(x_i, x_j)$$
In a seminal paper, Ramin Zabih and Vladimir Kolmogorov established the definitive mathematical rulebook for this domain in What Energy Functions Can Be Minimized via Graph Cuts?. They proved that a binary pairwise energy function can be minimized exactly via graph cuts if and only if every pairwise term satisfies the regularity condition:
$$E_{ij}(0,0) + E_{ij}(1,1) \le E_{ij}(0,1) + E_{ij}(1,0)$$
Intuitively, this inequality states that the cost of neighboring variables choosing identical labels must be less than or equal to the cost of them choosing different labels. This is the definition of submodularity for binary pairs. It represents an "attractive" potential that encourages spatial consistency or smoothness.
Why does this condition make the problem solvable? It allows us to construct a directed $s-t$ network graph where:
- The source node $s$ represents the label
0and the sink node $t$ represents the label1. - Each variable becomes a node in the graph connected to $s$ and $t$.
- The pairwise penalties $E_{ij}$ are mapped to directed edge capacities between variable nodes.
Because the regularity condition guarantees that all edge capacities are non-negative, we can apply standard max-flow/min-cut algorithms (such as the Boykov-Kolmogorov algorithm). A minimum cut splits the graph into two disjoint sets, effectively assigning a 0 or 1 label to every node. The total capacity of the cut corresponds exactly to the minimum energy of the function.
Expanding on this foundation, David A. Cohen et al. demonstrated in A Maximal Tractable Class of Soft Constraints that any binary submodular function can be decomposed into simpler "interval" functions. This functional decomposition guarantees a global optimum in cubic time, establishing submodularity as the largest possible tractable class of binary soft constraints.
Breaking the Pairwise and Binary Barriers
While binary pairwise formulations are powerful, real-world applications often demand more expressive models. Modern research focuses on extending the tractability of graph cuts to higher-order interactions (cliques of three or more variables) and multi-label spaces.
Higher-Order Cliques
Pairwise terms can only capture immediate pixel-to-pixel transitions, which often leads to oversmoothing or a failure to capture complex textures and geometric shapes. To capture richer context, we need higher-order potentials that look at patches of pixels simultaneously.
Pushmeet Kohli et al. broke the pairwise barrier in P3 & Beyond: Solving Energies with Higher Order Cliques by introducing the $P^n$ Potts model. They showed that if higher-order functions are defined as concave or linear functions of a pairwise sum, they remain submodular and can be solved in polynomial time using expansion moves.
For even more complex interactions, researchers utilize a Sum-of-Submodular (SoS) decomposition. Global energy functions are broken down into a sum of smaller, localized submodular functions representing individual cliques. Alexander Fix et al. leveraged this structure in Structured Learning of Sum-of-Submodular Higher Order Energy Functions to automatically learn higher-order image priors using a Structural SVM framework.
To optimize these SoS functions efficiently without treating the entire system as a single monolithic block, Ishant Shanu et al. introduced the SoS-MinNorm algorithm in Min Norm Point Algorithm for Higher Order MRF-MAP Inference. By performing block coordinate descent on individual submodular components, they scaled optimal inference to cliques containing hundreds of pixels. Furthermore, the authors of Exact inference in multi-label CRFs with higher order cliques proved that higher-order submodular functions can be systematically reduced to quadratic boolean forms, allowing practitioners to reuse highly optimized $s-t$ min-cut solvers directly.
Multi-Label Optimization
When moving from binary choices to multiple labels (e.g., assigning depth values or identifying dozens of distinct object classes), preserving submodularity becomes more challenging.
Algorithms like $\alpha$-expansion solve multi-label problems by making a sequence of binary decisions (whether a variable should switch to label $\alpha$ or stay as its current label). To maintain efficiency, the geometric constraints at each step must preserve submodularity. For instance, Hossam Isack et al. utilized a modified, submodular $\alpha$-expansion algorithm in Hedgehog Shape Priors for Multi-Object Segmentation to enforce surface normal constraints across multiple interacting objects.
For direct multi-label inference, Chetan Arora 0001 and S. N. Maheshwari proposed Multi-label Generic Cuts (MLGC) in Multi-label Generic Cuts: Optimal Inference in Multi-label Multi-clique MRF-MAP Problems. By transforming multi-label cliques into binary representations using specific encodings, they preserved submodularity across higher-order cliques. This was later scaled by Ishant Shanu et al. in An Inference Algorithm for Multi-label MRF-MAP Problems with Clique Size 100 via an algorithm called MLHybrid, which splits the optimization into valid and invalid state blocks to handle large cliques and multiple labels simultaneously.
Submodular Relaxations and Discretization
What happens when the natural energy function of a problem is not submodular? Instead of abandoning graph cuts, researchers have developed techniques to approximate or transform non-submodular problems into submodular ones.
Lagrangian and Bound Relaxations
One approach is to relax the problematic constraints. Anton Osokin proposed Submodular Relaxation (SMR) in Submodular Relaxation for Inference in Markov Random Fields. Instead of relaxing the graph structure as traditional dual decomposition methods do, SMR relaxes the label consistency constraints. This reformulates the complex energy minimization problem into a series of submodular binary subproblems that can be solved rapidly via graph cuts, yielding tighter lower bounds and faster convergence.
Similarly, the authors of Generalized Roof Duality for Multi-Label Optimization: Optimal Lower Bounds and Persistency extended binary roof duality to multi-label problems with ordered labels. They used a closed-form formula to construct the tightest possible submodular lower bound, which prunes the search space by identifying a guaranteed range of optimal labels for each variable. When dealing with non-polynomial higher-order functions, the authors of Higher Order Energies for Image Segmentation showed that lower-order Taylor expansions retain submodularity if the underlying function is submodular, keeping the subproblems efficiently solvable.
Discretizing Continuous Free Energies
A fascinating connection exists between discrete submodular optimization and continuous variational inference. In graphical models, finding the marginal probabilities often involves minimizing the Bethe free energy. Standard methods like Belief Propagation frequently get trapped in local minima because the continuous free energy function is non-convex.
In Bethe Bounds and Approximating the Global Optimum, Adrian Weller and Tony Jebara proved that if you discretize the Bethe free energy over a mesh in associative (attractive) binary pairwise MRFs, the resulting discrete optimization problem is submodular. This allows researchers to bypass local optima entirely and use graph cuts to find a guaranteed $\epsilon$-approximate global solution. Adrian Weller later extended this guarantee to a much larger family of variational entropy approximations in Bethe and Related Pairwise Entropy Approximations, proving that discrete submodularity emerges across arbitrary counting numbers when interactions are attractive.
Broad Applications
The mathematical guarantee of submodular energy minimization has made it a foundational tool across diverse domains:
- Image Parsing and Object Proposals: Abram L. Friesen et al. introduced Submodular Field Grammars in Submodular Field Grammars: Representation, Inference, and Application to Image Parsing, turning hierarchical shape parsing into a tractable graph-cut problem. For object detection, Philipp Kraehenbuehl et al. demonstrated in Learning to propose objects that framing ensemble selection as a submodular facility location problem enables near-real-time generation of high-quality foreground segmentation proposals.
- Co-Segmentation and Multi-View Consistency: In From co-saliency to co-segmentation: An efficient and fully unsupervised energy minimization model, Kai-Yueh Chang et al. used a submodular formulation to discover and outline common objects across entirely unsupervised image sets. Similarly, Chi Zhang 0069 et al. solved the joint problem of 3D camera localization and silhouette segmentation in Joint Multiview Segmentation and Localization of RGB-D Images Using Depth-Induced Silhouette Consistency by framing multi-view consistency terms as submodular functions.
- Stereo and Surface Reconstruction: Traditional 3D surface reconstruction often relies on complex higher-order triple cliques to enforce smoothness. In In Defense of 3D-Label Stereo, Carl Olsson et al. showed that by using 3D labels (tangent planes) and restricting fusion moves to planar candidate solutions, the optimization becomes submodular, allowing fast and stable convergence via min-cut/max-flow algorithms.
- Diverse Solution Generation: Often, we do not just want a single MAP assignment, but a set of diverse, highly probable solutions. Alexander Kirillov et al. proved in M-Best-Diverse Labelings for Submodular Energies and Beyond that for submodular energies, the optimal set of diverse solutions follows a natural partial order. This allowed them to replace an exponentially expensive joint optimization with a sequence of linear-time submodular graph cuts.
- Information Theory and NLP: The framework extends beyond vision. Ravi Kiran Raman proved in Universal joint image clustering and registration using partition information that multivariate information functionals for joint image clustering are inherently submodular. In natural language processing, Ashish Kulkarni et al. utilized submodular potentials in An Approach to Collective Entity Linking to solve global entity disambiguation exactly in polynomial time.
By anchoring complex discrete optimization problems to the mathematical bedrock of submodularity, these techniques transform intractable combinatorial explosions into elegant, globally optimal network flow solutions.
Key Foundational Work
Generalized Multi-camera Scene Reconstruction Using Graph Cuts (2003) — contributed 2 concept elements to this direction.
What Energy Functions Can Be Minimized via Graph Cuts? (2002) — contributed 2 concept elements to this direction.
A Maximal Tractable Class of Soft Constraints (2003) — contributed 1 concept elements to this direction.