Binary MRF Optimization using Min-Cut Setup

mediumFREEGraphsGraphs, Image ProcessingCV - DSA

Problem Statement

In image processing, minimizing the energy function of a Binary Markov Random Field (MRF) is a common method for tasks like image denoising or segmentation. The goal is to assign a binary label ( $w_n \in \{0,1\}$ ) to every pixel $n$ to minimize the total energy:

$E(w) = \sum_n U_n(w_n) + \sum_{(m,n) \in C} P_{mn}(w_m, w_n)$

where $U_n(w_n)$ is the unary cost (fitting the label to local data) and $P_{mn}(w_m, w_n)$ is the pairwise cost (enforcing smoothness/prior constraints).

A fundamental technique for solving this optimization problem exactly when the pairwise costs are submodular is by transforming it into a Minimum Cut (Min-Cut) problem on a constructed graph.

Your Task

Implement the graph construction step for a simplified 2×1 image (two pixels, $w_1$ and $w_2$ ) where $w_1$ is adjacent to $w_2$ . Given the unary costs and the fixed pairwise costs, calculate the capacities of the required links in the Max-Flow/Min-Cut graph:

Source-to-w₁ link capacity: $C(s, w_1)$
w₁-to-Sink link capacity: $C(w_1, t)$
Source-to-w₂ link capacity: $C(s, w_2)$
w₂-to-Sink link capacity: $C(w_2, t)$
w₁-to-w₂ directional capacity: $C(w_1, w_2)$
w₂-to-w₁ directional capacity: $C(w_2, w_1)$

Pairwise Costs

Assume the pairwise costs are fixed as:

$P_{12}(0,1) = 4.0$ (cost if w₁=0, w₂=1)
$P_{12}(1,0) = 4.0$ (cost if w₁=1, w₂=0)
$P_{12}(0,0) = 0$ and $P_{12}(1,1) = 0$ (zero-diagonal form)

Graph Construction Rules

Using the standard convention:

$C(s, w_n) = U_n(1)$ — Cost if wₙ is separated from source (assigned wₙ=1)
$C(w_n, t) = U_n(0)$ — Cost if wₙ is separated from sink (assigned wₙ=0)
C(w₁, w₂) = C(w₂, w₁) = P(0,1) = P(1,0) — Symmetric capacity for disagreement cost

Example

Input

U1(0)=5.0, U1(1)=1.0, U2(0)=2.0, U2(1)=6.0

Output

[1.0, 5.0, 6.0, 2.0, 4.0, 4.0]

Reasoning

Inputs: four unary costs, two per pixel. $U_1(0)=5.0$ and $U_1(1)=1.0$ say pixel $w_1$ is much cheaper as label 1; $U_2(0)=2.0$ and $U_2(1)=6.0$ say $w_2$ prefers label 0. The pairwise disagreement cost is fixed at $4.0$ .
Terminal links for $w_1$ : $C(s,w_1)=U_1(1)=1.0$ and $C(w_1,t)=U_1(0)=5.0$ . Cutting $s\to w_1$ puts $w_1$ on the sink side (label 1), so that link carries $U_1(1)$ ; cutting $w_1\to t$ keeps it on the source side (label 0), so it carries $U_1(0)$ . That is why the two values swap places relative to the input order.
Terminal links for $w_2$ : likewise $C(s,w_2)=U_2(1)=6.0$ and $C(w_2,t)=U_2(0)=2.0$ .
Neighbour links: both directions get the disagreement cost, $C(w_1,w_2)=C(w_2,w_1)=4.0$ .
Output: [1.0, 5.0, 6.0, 2.0, 4.0, 4.0], in the order source/sink for $w_1$ , source/sink for $w_2$ , then the two neighbour links.
Sanity check: with the source side meaning label 0, the labeling $w_1=1, w_2=0$ cuts $s\to w_1$ , $w_2\to t$ and $w_2\to w_1$ , costing $1+2+4=7$ , exactly $E(w)=U_1(1)+U_2(0)+P_{12}(1,0)$ . Notice that the cut cost equals the MRF energy for every labeling, which is why the min-cut gives the optimal labels.

Constraints

Uₙ(wₙ) inputs are floats ≥ 0
Output capacities must be floats
The pairwise costs P₁₂(0,0) = 0 and P₁₂(1,1) = 0 are fixed
P₁₂(0,1) = P₁₂(1,0) = 4.0 (representing the smoothness cost for disagreement)

More from CV - DSA

Concept primer

1. Background Knowledge

Binary Markov Random Fields (MRFs) model image pixels as nodes in a graph, where labels $w_n \in \{0,1\}$ represent assignments (e.g., foreground/background in segmentation). The energy function is:

$E(w) =$ \sum $_n U_n(w_n) +$ \sum_{(m,n) \in C} $P_{mn}(w_m, w_n)$

Unary term $U_n(w_n)$ : Data fidelity cost (e.g., how well label fits pixel intensity).
Pairwise term $P_{mn}(w_m, w_n)$ : Smoothness penalty, high for label disagreements.

For submodular pairwise costs—where $P_{mn}(0,1) + P_{mn}(1,0) \geq P_{mn}(0,0) + P_{mn}(1,1)$ —exact minimization is possible via reduction to Min-Cut/Max-Flow.

Graph Construction: Add source $s$ (label 0) and sink $t$ (label 1).

$C(s, n) = U_n(1)$ : Cutting assigns $n$ to 0.
$C(n, t) = U_n(0)$ : Cutting assigns $n$ to 1.
For neighbors $m,n$ , add bidirectional edge $C(m,n) = C(n,m) = P_{mn}(0,1) = P_{mn}(1,0)$ (since $P(0,0)=P(1,1)=0$ ).

The Min-Cut capacity equals $E(w^*)$ ; the source-set gives optimal labels.

Submodularity Check: Here, $P_{12}(0,1) + P_{12}(1,0) = 8 \geq 0 + 0$ , so solvable exactly.

2. Algorithm Approach

Max-Flow/Min-Cut Algorithms:

Ford-Fulkerson: Basic, $O(|E||F|)$ (slow for images).
Edmonds-Karp (BFS): $O(VE^2)$ .
Dinic's: $O(V^2 E)$ , fast for grid graphs.
Push-Relabel: $O(V^3)$ or $O(V^2$ \sqrt{E} $)$ , practical for vision.

For grid-like images (pixels as 4/8-neighbors), specialized GridCut excels. Modern implementations use GPU acceleration.

Why Min-Cut Works: By max-flow min-cut theorem, min-cut partitions graph optimally for submodular energies.

3. Step-by-Step Strategy

For 2×1 image ( $w_1 \leftrightarrow w_2$ ):

Input: $U_1(0), U_1(1), U_2(0), U_2(1)$ (floats ≥0); fixed $P_{12}(0,1)=P_{12}(1,0)=4.0$ .
Set unary capacities:

C(s, w_1) = U_1(1), \quad C(w_1, t) = U_1(0)

C(s, w_2) = U_2(1), \quad C(w_2, t) = U_2(0)

Set pairwise capacities (symmetric for undirected smoothness):

C(w_1, w_2) = C(w_2, w_1) = 4.0

Output: 6 floats as listed.

Verification: Constant terms $P(0,0)=P(1,1)=0$ are absorbed (no extra edges needed).

Example (assume $U_1(0)=3, U_1(1)=1, U_2(0)=2, U_2(1)=4$ ):

$C(s,w_1)=1.0$ , $C(w_1,t)=3.0$
$C(s,w_2)=4.0$ , $C(w_2,t)=2.0$
$C(w_1,w_2)=C(w_2,w_1)=4.0$

4. Common Pitfalls

Swapping source/sink: $s$ must represent label 0, $t$ label 1 (reverse flips assignments).
Asymmetric capacities: Pairwise must be bidirectional and equal for undirected graphs; $C(w_1,w_2) = P(0,1)$ .
Non-submodular costs: If $P(0,1)+P(1,0) < P(0,0)+P(1,1)$ , Min-Cut fails (use approximations).
Ignoring constants: $P(0,0), P(1,1) \neq 0$ requires offset: add $\min(P(0,0),P(1,1))$ to unaries.
Negative costs: Unaries must be ≥0; shift if needed ( $U_n'(l) = U_n(l) - \min_l U_n(l)$ ).
Coding: Use floats; ensure max-flow handles capacities correctly (no inf-flow).

5. Time & Space Complexity

Graph Construction: $O(V)$ for $V$ pixels (add 2V unary + 2|E| pairwise edges).

Min-Cut Solve (for full image):

Nodes: $V+2$ , Edges: $2V + 2|E|$ ( $|E| \approx 4V$ for 4-neighbor grid).
Dinic's: $O(V^2 E) = O(V^3)$ .
Push-Relabel: $O(V^2$ \sqrt{E} $) = O(V^{2.5})$ .
Practical: $O(V)$ amortized for images via optimized codes.

This Problem: $O(1)$ (fixed 2 pixels, 4 nodes, 8 edges).

Scalability: Exact for binary submodular; multi-label needs expansions (e.g., $\alpha$ -expansion).