Connected-Components Labeling

Look at a satellite photograph, a handwritten digit, or an X-ray: underneath all the color lies a binary decision — foreground or background. Threshold the image and you get a grid of 1s (object pixels) and 0s (empty space).

Now the natural question is: how many separate objects are there? The blob of pixels in the top-left corner is clearly different from the one in the bottom-right — but a computer sees only a flat array of bits. Connected-components labeling (CCL) is the classical answer: scan the grid and stamp every distinct group of foreground pixels with a unique integer label.

Two pixels belong to the same component if you can walk from one to the other through a chain of touching foreground pixels. "Touching" most commonly means the 4 orthogonal neighbors (up, down, left, right), though 8-connectivity (diagonals included) is also used. The task is solved — and solved in $O(n)$ time, where $n$ is the number of pixels — by algorithms invented in the 1960s and still at the heart of modern computer vision pipelines.

Click any cell to toggle it between foreground (colored) and background (white). The algorithm runs instantly after every click, assigning a different color to each connected island.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls">
  <button id="btn-clear" type="button" class="ghost">{{btn_clear}}</button>
  <button id="btn-random" type="button" class="ghost">{{btn_random}}</button>
  <span class="count-badge" id="count-badge">{{label_islands}} <strong id="island-count">0</strong></span>
</div>
<div id="grid" class="grid" role="grid" aria-label="{{grid_aria}}"></div>
<div class="legend" id="legend"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.count-badge { font: 600 14px system-ui; color: #1d3557; margin-left: auto; }
.grid { display: grid; gap: 2px; width: fit-content; user-select: none; margin-bottom: .5rem; }
.cell { width: 28px; height: 28px; border-radius: 4px; cursor: pointer;
        background: #e8eef3; border: 1px solid #cdd9e3; transition: background .08s; }
.cell.fg { border-color: transparent; }
.cell:hover { opacity: .82; }
.legend { display: flex; flex-wrap: wrap; gap: .35rem .6rem; font-size: .8rem; color: #555; }
.legend-item { display: flex; align-items: center; gap: .3rem; }
.legend-swatch { width: 14px; height: 14px; border-radius: 3px; flex-shrink: 0; }

// Code not found

Notice what happens when two previously separate blobs become connected by a single bridge pixel: they instantly merge into one component. That merge is the heart of the union-find data structure — or, in the two-pass approach, the moment a second-pass equivalence table collapses two labels into one. Either way, the total work stays proportional to the number of pixels.

Connected-components labeling is one of the fortunate problems that admit an essentially linear-time solution — and the story of how close to linear we can get is beautiful.

The two-pass algorithm (Rosenfeld & Pfaltz, 1966) scans the image left-to-right, top-to-bottom:

1. First pass — assign a provisional label to each foreground pixel; if two labeled neighbors exist, record that their labels are equivalent.
2. Second pass — replace each provisional label with the smallest label in its equivalence class.

The equivalence table is managed with union-find (disjoint-set forest), which supports each union and find in amortized $O(\alpha(n))$ time, where $\alpha$ is the inverse Ackermann function — the slowest-growing function that appears in practical algorithms. For any grid you will ever process, $\alpha(n) \leq 4$. So the total cost of labeling $n$ pixels is $O(n \cdot \alpha(n))$, which is so close to linear that the difference is invisible in practice.

• Space: $O(n)$ for the label array plus $O(L)$ for the union-find structure, where $L$ is the number of provisional labels (at most $n/2$ in the worst case).
• Parallelism: modern GPUs and multi-core CPUs exploit the data-parallel structure of the first pass; specialized parallel CCL algorithms achieve $O(\log n)$ depth.
• Streaming: some variants process a single row at a time, keeping only $O(\text{width})$ state — critical for satellite imagery that doesn't fit in RAM.

Compare this to a naive approach: for each foreground pixel, do a full BFS/DFS to find its component. That is still $O(n)$ per component and $O(n)$ total (each pixel is visited once), but the union-find formulation unifies the two-pass framework neatly and generalizes to parallel settings.

Counting and isolating distinct objects is the first step in an enormous range of systems:

• Medical imaging: a radiologist's software circles individual nodules in a CT scan by labeling foreground blobs in a thresholded slice — each blob is a candidate lesion.
• Document analysis and OCR: every character on a scanned page is a connected component. Label them, extract their bounding boxes, and feed them to a classifier.
• Industrial inspection: surface-defect detectors on factory lines find scratches or pits by labeling anomalous regions in a binary difference image.
• Satellite and aerial imagery: counting buildings, delineating crop fields, or tracking ice-sheet extent are all blob-counting problems at planetary scale.
• Network science: the same union-find logic identifies connected components in graphs — which cities are reachable from which, which proteins interact in a pathway, which accounts belong to the same fraudulent ring.

The algorithm is also a teaching touchstone: it is one of the cleanest demonstrations of how the right data structure (union-find) turns a problem that looks like it might require repeated global scans into a single linear sweep. That lesson generalizes to max-flow, minimum spanning trees, and dozens of other graph primitives.

Connected-components labeling is a quiet workhorse. You won't find it in complexity-theory textbooks under "hard problems" — it runs in near-linear time with a tiny constant. But it sits at the entry point of almost every vision pipeline, from a phone camera detecting faces to a satellite counting glaciers.

What makes it instructive is the interplay between algorithm and data structure. The problem itself is straightforward; the elegance comes from union-find, which makes the equivalence bookkeeping invisible. Master that pattern — lazy merging, path compression, rank-based union — and you have a tool that reappears in spanning trees, network connectivity, and beyond.

The next time you see a bounding box drawn around an object on screen, there is a good chance that a two-pass CCL algorithm ran on a binary mask a millisecond earlier. Simple, linear, and everywhere.