Introduction

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)O(n) time, where nn is the number of pixels — by algorithms invented in the 1960s and still at the heart of modern computer vision pipelines.

Count the Islands

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.

<!-- interactive connected-components labeling demo -->
<p class="hint">Click or drag to toggle cells. Each connected island of colored cells gets its own color. Watch two islands merge when you bridge them with a single pixel.</p>
<div class="controls">
  <button id="btn-clear" type="button" class="ghost">Clear</button>
  <button id="btn-random" type="button" class="ghost">Random</button>
  <span class="count-badge" id="count-badge">Islands: <strong id="island-count">0</strong></span>
</div>
<div id="grid" class="grid" role="grid" aria-label="Pixel grid — click cells to toggle foreground"></div>
<div class="legend" id="legend"></div>

/* layout and color for the CCL demo */
* { 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; }

/* Connected-components labeling demo — union-find on a pixel grid */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* grid dimensions and color palette (up to 15 distinct component colors) */
const ROWS = 10, COLS = 14;
const PALETTE = [
  '#e63946','#2a9d8f','#e9c46a','#264653','#a8dadc',
  '#f4a261','#457b9d','#6a994e','#bc6c25','#9b5de5',
  '#0077b6','#f15bb5','#00b4d8','#8338ec','#fb5607'
];

/* pixel state: 1 = foreground, 0 = background */
const grid = Array.from({ length: ROWS }, () => new Array(COLS).fill(0));
let dragging = false;
let dragValue = 1; /* 1=paint, 0=erase */

/* Union-Find (disjoint-set forest) with path splitting and union-by-rank */
function makeUF(n) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = new Array(n).fill(0);
  function find(x) {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
  }
  function union(a, b) {
    a = find(a); b = find(b);
    if (a === b) return;
    if (rank[a] < rank[b]) { const t = a; a = b; b = t; }
    parent[b] = a;
    if (rank[a] === rank[b]) rank[a]++;
  }
  return { find, union };
}

/* Run one-pass CCL: sweep left-right/top-bottom, union with left and top neighbors */
function labelGrid() {
  const n = ROWS * COLS;
  const uf = makeUF(n);
  const idx = (r, c) => r * COLS + c;
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      if (!grid[r][c]) continue;
      /* merge with left neighbor */
      if (c > 0 && grid[r][c - 1]) uf.union(idx(r, c), idx(r, c - 1));
      /* merge with top neighbor */
      if (r > 0 && grid[r - 1][c]) uf.union(idx(r, c), idx(r - 1, c));
    }
  }
  /* assign compact labels: root -> sequential integer */
  const rootToLabel = new Map();
  let nextLabel = 0;
  const labels = new Array(n).fill(-1);
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      if (!grid[r][c]) continue;
      const root = uf.find(idx(r, c));
      if (!rootToLabel.has(root)) { rootToLabel.set(root, nextLabel++); }
      labels[idx(r, c)] = rootToLabel.get(root);
    }
  }
  return { labels, count: nextLabel };
}

/* re-render every cell with its component color */
function render() {
  const { labels, count } = labelGrid();
  const cells = document.querySelectorAll('.cell');
  cells.forEach((cell, i) => {
    const lbl = labels[i];
    if (lbl === -1) {
      cell.style.background = '';
      cell.classList.remove('fg');
    } else {
      cell.style.background = PALETTE[lbl % PALETTE.length];
      cell.classList.add('fg');
    }
  });
  document.getElementById('island-count').textContent = count;
  renderLegend(count);
}

/* build a color legend below the grid */
function renderLegend(count) {
  const el = document.getElementById('legend');
  if (count === 0) { el.innerHTML = ''; return; }
  el.innerHTML = Array.from({ length: count }, (_, i) => {
    const color = PALETTE[i % PALETTE.length];
    return `<span class="legend-item"><span class="legend-swatch" style="background:${color}"></span>${i18nFmt('Component %n%', { n: i + 1 })}</span>`;
  }).join('');
}

/* build the DOM grid once */
function buildGrid() {
  const g = document.getElementById('grid');
  g.style.gridTemplateColumns = `repeat(${COLS}, 28px)`;
  g.innerHTML = '';
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      const cell = document.createElement('div');
      cell.className = 'cell';
      cell.dataset.r = r;
      cell.dataset.c = c;
      cell.setAttribute('role', 'gridcell');
      cell.setAttribute('aria-label', i18nFmt('Cell row %r% column %c%', { r: r + 1, c: c + 1 }));
      g.appendChild(cell);
    }
  }
}

/* set one pixel and re-render */
function toggleCell(r, c, value) {
  grid[r][c] = value;
  render();
}

/* mouse events: click to toggle, drag to paint/erase */
document.getElementById('grid').addEventListener('mousedown', (e) => {
  const cell = e.target.closest('.cell');
  if (!cell) return;
  const r = +cell.dataset.r, c = +cell.dataset.c;
  dragValue = grid[r][c] ? 0 : 1; /* first cell decides paint vs erase for the whole drag */
  dragging = true;
  toggleCell(r, c, dragValue);
});
document.getElementById('grid').addEventListener('mouseover', (e) => {
  if (!dragging) return;
  const cell = e.target.closest('.cell');
  if (!cell) return;
  toggleCell(+cell.dataset.r, +cell.dataset.c, dragValue);
});
document.addEventListener('mouseup', () => { dragging = false; });

document.getElementById('btn-clear').addEventListener('click', () => {
  for (let r = 0; r < ROWS; r++) grid[r].fill(0);
  render();
});

document.getElementById('btn-random').addEventListener('click', () => {
  /* fill at ~42% density for interesting connectivity */
  for (let r = 0; r < ROWS; r++)
    for (let c = 0; c < COLS; c++)
      grid[r][c] = Math.random() < 0.42 ? 1 : 0;
  render();
});

/* initial render */
buildGrid();
/* pre-load a few islands so the grid is not empty on load */
const SEED = [[1,1],[1,2],[2,1],[4,3],[4,4],[5,4],[7,1],[7,2],[7,3],[2,8],[3,8],[3,9],[5,10],[6,10],[6,11]];
SEED.forEach(([r, c]) => { grid[r][c] = 1; });
render();
Result
Console

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.

The Real Complexity

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(α(n))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, α(n)≤4\alpha(n) \leq 4. So the total cost of labeling nn pixels is O(n⋅α(n))O(n \cdot \alpha(n)), which is so close to linear that the difference is invisible in practice.

  • Space: O(n)O(n) for the label array plus O(L)O(L) for the union-find structure, where LL is the number of provisional labels (at most n/2n/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)O(\log n) depth.
  • Streaming: some variants process a single row at a time, keeping only O(width)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)O(n) per component and O(n)O(n) total (each pixel is visited once), but the union-find formulation unifies the two-pass framework neatly and generalizes to parallel settings.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/connected-components-labeling/Content licensed under CC BY-NC 4.0.