Binary MRF Optimization using Min-Cut Setup

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$):

1. 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$.

2. 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)$$

3. Set pairwise capacities (symmetric for undirected smoothness):

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

4. 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).