Segmentation fast enough for video

The series so far has three ways of answering “which pixels go together”: mean shift finds bumps in a colour density, normalised cuts turns the picture into a graph and looks for its weakest seam, EM fits a mixture of Gaussians and lets the pixels vote. Post 44 ran all three on the same photograph and measured them honestly: normalised cuts’ sparse eigensolver needs its image capped at 3,000 pixels to stay usable at all, EM at its published $K=20$ took nine seconds and never converged, and mean shift’s peeling loop can run for minutes without terminating, which post 44 had to cap by wall clock rather than trust to finish. None of the three is a candidate for a camera feed. A phone camera alone gives you thirty new 8-megapixel frames a second; anything that needs seconds per frame, capped or not, is not in the running.

Felzenszwalb and Huttenlocher’s 2004 graph-based segmentation is. It has shown up twice already in this series as a component inside something else, never explained on its own, which is the gap this post fills. The idea is almost embarrassingly simple once you see it: sort every edge in the pixel graph by weight, walk the sorted list once, and join two components whenever the edge between them is cheap relative to how varied each component already is internally. No eigenproblem, no iterative mode-seeking, no EM loop to fail to converge. One sort, one pass, done.

Sorting edges, joining components

Treat every pixel as a graph node. Connect it to its four forward neighbours (right, down, down-right, down-left; each undirected edge counted once, so an $w \times h$ image gives roughly $4wh$ edges rather than $8wh$), weighted by the Euclidean distance between the two pixels’ colours after a light Gaussian blur. The paper recommends a small $\sigma$, “typically 0.8”, enough to smooth out digitisation noise without visibly softening the photograph; the widget’s slider goes well past that so you can watch real edges start to disappear once the blur gets big enough to matter.

Sort every edge by weight, ascending. Walk the sorted list. For an edge $(u, v)$ with weight $w$, let $C_u$ and $C_v$ be whatever components currently contain $u$ and $v$. A component’s threshold is

$$\tau(C) = \frac{k}{|C|}$$

and the merge rule is: join $C_u$ and $C_v$ if $w \le \tau(C_u)$ and $w \le \tau(C_v)$. $k$ is the one parameter worth sitting with. A bigger $k$ makes every component more tolerant of a costly edge before it refuses to grow further, which biases the whole image toward fewer, larger regions, but because the threshold divides by $|C|$, that bias is not a fixed pixel-count floor the way a naive “merge until $N$ pixels” rule would be: a small, genuinely uniform patch can stay small if nothing costs enough to justify merging it into its noisier neighbour, while a large uniform one keeps absorbing cheap edges long after a fixed-size rule would have stopped it.

The reason a single ascending pass is enough, and you never have to reconsider a merge you already made or track a running “internal variation” statistic separately, is that the edges arrive in weight order. When $C_u$ and $C_v$ merge on edge $(u, v, w)$, $w$ is provably the largest edge used to build the new component so far (every edge processed before it was cheaper, and every edge inside $C_u$ or $C_v$ already was, by induction). So the new component’s threshold is just

$$\tau(C_{u} \cup C_{v}) = w + \frac{k}{|C_u| + |C_v|}$$

$w$ standing in for “the internal variation this component has earned”, $k / |C|$ standing in for “and it still gets this much benefit of the doubt because it’s small.” A singleton’s threshold, before anything has merged into it, is just $k$ itself: nothing has happened yet, so the whole benefit of the doubt applies.

One more pass over the same sorted list, after the main one, folds any component still under min_size pixels into a neighbour regardless of edge weight. This is not part of the threshold rule; it is bookkeeping to stop a handful of stray pixels from surviving as their own one-pixel “regions”, which a purely colour-driven rule with no notion of “too small to be interesting” would otherwise leave behind.

Here is the whole thing, more or less verbatim from felzenszwalb.rs:

for e in edges.iter() {
    let a = uf.find(e.u);
    let b = uf.find(e.v);
    if a == b {
        continue;
    }
    if e.w <= threshold[a as usize] && e.w <= threshold[b as usize] {
        let r = uf.union(a, b);
        let sz = uf.set_size(r);
        threshold[r as usize] = e.w + k / sz as f32;
    }
}

uf is the exact same union-find post 35 wrote for mean shift’s connected-component check and post 42 also reuses: union by size, path halving, nothing new needed here. Felzenszwalb and Huttenlocher’s actual contribution, reading the paper next to this loop, is entirely in that one if: a merge predicate that is cheap to evaluate, needs no global recomputation as components grow, and falls out of a single sorted pass. That is the whole reason it is fast.

What I built with it since

The algorithm being simple enough to reimplement in an afternoon is exactly why it turned up twice more in my own work after this. Once as a pooling layer inside a graph neural network, where I kept the sorted-edges-plus-union-find core completely unchanged and replaced “Euclidean distance between two pixels’ colours” with a distance the network itself learns from feature differences, so the same merge rule decides which nodes to coarsen together instead of which pixels belong to the same region. And once over a point cloud instead of an image, where “distance between two pixels’ colours” became a statistical distance between two voxels’ running colour and geometry statistics, so the same threshold rule that decides “is this edge cheap enough to cross” runs on a completely different notion of cheap. Neither of those is this post; both are still to come. What carries over in each case is not the algorithm’s mathematics adapting to a new domain, it is that the algorithm barely notices: it only ever asks a merge predicate a yes/no question about a sorted list of edges, so anything that can be turned into “vertices, edges, a weight per edge” gets segmentation for free.

Real time

The widget runs felzenszwalb.rs on the main thread once per camera frame: grab a frame, downscale it, blur it, build the graph, sort, union-find, recolour by segment mean, paint, repeat. σ, k and the minimum size are all live sliders; drag any of them while the camera is running and the next frame reflects it immediately. There is no worker for this path: the whole pipeline for one frame, measured below, is single-digit milliseconds to a few tens of milliseconds depending on the machine, which is close enough to a frame interval that a worker’s message-passing round trip would be a real fraction of the budget rather than free overhead.

With JavaScript on, this becomes a live segmentation view: point a camera at something (or upload a photo, or use the bundled sample) and watch Felzenszwalb & Huttenlocher’s algorithm run every frame, with σ, k and minimum-size sliders and a measured frame time. A second panel below lets you freeze the current frame and run mean shift, normalised cuts and EM on it too, each reporting its own real time.

What the numbers actually say

felzenszwalb.rs gets the whole snapshot, uncapped, while mean shift, normalised cuts and EM each still need the same pixel budgets post 44 measured them at (50,000 / 3,000 / 24,000 pixels respectively) to stay responsive at all. That gap, not just the per-pixel speed, is most of the argument: the other three all need to be shrunk before they are usable; this one does not.

Three separate runs of the “compare this frame” button, same photograph, same defaults (mean shift’s are post 44’s report-matched preset; EM runs at $K=5$, the value that actually produced every figure in post 44, not the report’s published $K=20$, which post 42 found never ran):

algorithm	pixels	regions	time (3 runs)
Felzenszwalb & Huttenlocher (this post)	154,882	127	78 ms, 85 ms, 88 ms
EM, $K=5$ (post 42)	24,003	5	1.06 s, 1.16 s, 1.08 s
Normalised cuts (post 39)	3,015	16	1.43 s, 1.50 s, 1.45 s
Mean shift (post 35)	49,959	8	4.48 s, 4.41 s, 4.59 s

Run it yourself with the “compare this frame” button and you may well see mean shift lose by an even wider margin than that: post 44 found its peeling loop does not reliably terminate on this exact photograph at the report’s own default preset, and had to add a wall-clock cap rather than trust it to finish. This widget’s comparison worker carries the same cap for the same reason, described there rather than re-derived here; the “4.5 s” above is that cap doing its job, not the algorithm actually converging.

Verifying it against itself

Three of this crate’s tests exist specifically because a merge rule this simple is also easy to get subtly wrong. A uniform-colour image has every edge at weight zero, so no matter how small $k$ is, the whole (connected) grid graph collapses to one region; if that test ever failed it would mean the threshold comparison had an off-by-one that let a perfectly flat photograph fragment. A single sharply different pixel dropped into a uniform background should survive the main pass as its own component (its edges are far too expensive to clear any real threshold) and then get folded into a neighbour by the minimum-size pass, and afterward no region anywhere in the image may be smaller than min_size; that test is really checking that the second pass, which merges unconditionally, does not stop early. And segmenting the same seeded-random image twice must produce byte-identical labels both times, which sounds too obvious to bother testing until you remember that a hash map’s iteration order, or a sort that is not actually deterministic on ties, is exactly the kind of thing that breaks it silently.

#[test]
fn merge_predicate_on_a_hand_built_graph() {
    let mut edges = vec![Edge { u: 0, v: 1, w: 1.0 }, Edge { u: 1, v: 2, w: 5.0 }];
    let count = segment_graph_into(&mut edges, 3, 2.0, 0, &mut threshold, &mut map, &mut labels);
    assert_eq!(count, 2, "expected two regions, got {count}");
    assert_eq!(labels[0], labels[1], "0 and 1 should merge");
    assert_ne!(labels[1], labels[2], "1 and 2 should not merge");
}

Three nodes in a line, $0$ joined to $1$ and $1$ joined to $2$, weights $1.0$ and $5.0$, $k=2$. A singleton’s threshold is $k/1=2$, so the first edge clears it on both sides and merges $0$ and $1$; the merged component’s threshold becomes $1.0 + 2/2 = 2.0$. The second edge, at weight $5.0$, then fails against both endpoints, so $2$ never joins, even though the graph is connected and a path exists. That one hand-checked example is the entire algorithm: a low-weight edge merges, a higher-weight edge one hop away does not just ride along on the first merge’s coattails.

Where this leaves the series

Four segmentation algorithms now, and each earns its place for a different reason: mean shift for density without committing to a region count up front, normalised cuts for turning “which pixels belong together” into something you can look at as an eigenvector, EM for a principled soft assignment with an explicit generative story, and this one for being the only one of the four fast enough to point at a camera and not notice it is running. None of that makes it the “best” segmenter in the way the report’s own honest failure taxonomy for the other three makes clear none of them is uniformly best either. It just means that if the job is “keep up with the feed”, this is the one you reach for.