Goal

An N-dimensional image $I: P \to \mathbb{R}$ and two disjoint user-marked seed sets $O \subset P$ (object) and $B \subset P$ (background) are the inputs. The output is a binary labelling $A: P \to \{\text{obj}, \text{bkg}\}$ that satisfies the hard constraints $\forall p \in O,\, A_p = \text{"obj"}$ and $\forall p \in B,\, A_p = \text{"bkg"}$, and is the global minimum of a combined region-and-boundary MRF energy $E(A)$. The global optimum is computed exactly via a single s-t min-cut on a pixel graph; both segments may consist of multiple disconnected components.

Algorithm

Let $P$ denote the set of all pixels (or voxels). Let $N$ denote the neighbourhood system — 8-connectivity in 2D, 26-connectivity in 3D. Let $O \subset P$ and $B \subset P$ be the disjoint object and background seed sets. Let $A_p \in \{\text{"obj"}, \text{"bkg"}\}$ be the label assigned to pixel $p$. Let $I_p$ denote the intensity at pixel $p$. Let $\sigma > 0$ be the boundary contrast scale. Let $\lambda \geq 0$ be the scalar weight trading off the region term against the boundary term. Let $K$ be the seed-enforcing capacity. Let $S$ denote the source terminal (object) and $T$ the sink terminal (background).

Procedure

Implementation

The graph-construction step in Rust:

fn build_graph<G: GraphBuilder>(
    graph: &mut G,
    pixels: &[f32],                      // intensity per pixel
    neighbors: &[(usize, usize, f32)],   // (p, q, dist_pq) for each N-link pair
    ln_pr_obj: &[f32],                   // -ln Pr(I_p | O) per pixel
    ln_pr_bkg: &[f32],                   // -ln Pr(I_p | B) per pixel
    seeds_obj: &[usize],
    seeds_bkg: &[usize],
    sigma: f32,
    lambda: f32,
) {
    let n = pixels.len();
    let nodes: Vec<G::NodeId> = (0..n).map(|_| graph.add_node()).collect();
    let s = graph.source();
    let t = graph.sink();

    let mut n_link_sum = vec![0.0_f32; n];
    let mut n_link_caps = Vec::with_capacity(neighbors.len());
    for &(p, q, dist_pq) in neighbors {
        let diff = pixels[p] - pixels[q];
        let cap = (-(diff * diff) / (2.0 * sigma * sigma)).exp() / dist_pq;
        n_link_caps.push((p, q, cap));
        n_link_sum[p] += cap;
        n_link_sum[q] += cap;
    }
    for (p, q, cap) in n_link_caps {
        graph.add_edge(nodes[p], nodes[q], cap, cap);
    }

    let k: f32 = 1.0 + n_link_sum.iter().cloned().fold(f32::NEG_INFINITY, f32::max);

    let mut is_obj = vec![false; n];
    let mut is_bkg = vec![false; n];
    for &p in seeds_obj { is_obj[p] = true; }
    for &p in seeds_bkg { is_bkg[p] = true; }

    for p in 0..n {
        if is_obj[p] {
            graph.add_edge(nodes[p], s, k, 0.0);
            graph.add_edge(nodes[p], t, 0.0, 0.0);
        } else if is_bkg[p] {
            graph.add_edge(nodes[p], s, 0.0, 0.0);
            graph.add_edge(nodes[p], t, k, 0.0);
        } else {
            graph.add_edge(nodes[p], s, lambda * ln_pr_bkg[p], 0.0);
            graph.add_edge(nodes[p], t, lambda * ln_pr_obj[p], 0.0);
        }
    }
}

Remarks

• Globality: a single min-cut yields the global minimum of $E(A)$ subject to the hard seed constraints — failures trace to the energy definition, not to a local minimiser.
• The pairwise boundary term carries a shrinking bias towards short cuts; $\lambda$ requires per-image tuning: too small produces small segments, too large fragments the result through region competition.
• Scope: the formulation is binary. Multi-region segmentation requires repeated binary cuts (sequential foreground/background passes) or different formulations such as $\alpha$-expansion.
• Common extension: GrabCut replaces dense seed strokes with a single bounding-box prior, swaps the fixed seed histograms for full-covariance RGB Gaussian mixture models re-fit at each pass, and adds a regularised 1-D $\alpha$-profile in a $\pm 6$-pixel ribbon for sub-pixel boundary transitions. See grabcut-iterative-segmentation.

References

1. Y. Boykov, M.-P. Jolly. Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images. ICCV, 2001. PDF