Connected Components Labeling

hardFREEWhat is Computer Vision?Image ProcessingCV: Introduction to Computer Vision

Implement connected components labeling for binary image segmentation.

Given a binary image, identify and label distinct connected regions. Two pixels are connected if they share an edge (4-connectivity) or corner (8-connectivity).

Union-Find Algorithm (efficient approach):

First pass: Scan image, assign temporary labels
- If pixel is foreground and has labeled neighbors, use minimum label
- Track equivalences between labels using union-find
Second pass: Resolve equivalences and relabel

4-connectivity: Only horizontal/vertical neighbors 8-connectivity: Includes diagonal neighbors

Return a label map where each connected region has a unique integer label (background = 0). Labels are consecutive integers $1, 2, 3, \ldots$ assigned in raster-scan order: the region whose first pixel appears earliest (top-to-bottom, then left-to-right) gets label 1, the next gets 2, and so on.

Example

Input

image = [[1, 0, 1],
         [1, 0, 1],
         [0, 0, 0]]
connectivity = 4

Output

[[1, 0, 2], [1, 0, 2], [0, 0, 0]]

Reasoning

Input: image is a $3 \times 3$ binary grid (1 = foreground, 0 = background); connectivity $= 4$ means two foreground pixels belong together only if they share an edge.
Foreground pixels: four, at (row 0, col 0), (row 1, col 0), (row 0, col 2) and (row 1, col 2).
Grouping: (0,0) and (1,0) are vertically adjacent, so they form one region; (0,2) and (1,2) form another. The all-zero column 1 keeps them apart.
Numbering: reading the grid top-to-bottom, left-to-right, the left region appears first, at (0,0), so it is label 1; the right region, first seen at (0,2), is label 2. Each pixel takes its region's label: [[1, 0, 2], [1, 0, 2], [0, 0, 0]].
Notice: the output has the same shape as the input, background stays 0, and the largest label equals the number of regions. With connectivity $= 8$ the answer here is identical, since no diagonal pair bridges the gap; a diagonal line of 1s, though, is one region under 8-connectivity but one label per pixel under 4.

Constraints

image: Binary 2D array (0 = background, 1 = foreground)
connectivity: 4 or 8 (default 4)
Return: Label map with same shape, unique label per component
Background stays 0, components labeled 1, 2, 3, ...

More from CV: Introduction to Computer Vision

Sparse Matrix Operations for Imagesmedium Multi-Scale Feature Pyramidhard Implement Prewitt Edge Detectorhard K-Means Color Quantizationmedium Image Histogram Equalizationmedium

Concept primer

Background Knowledge

Connected Components Labeling (CCL) is a classic operation in binary image segmentation: given a binary image (background = 0, foreground = 1), you want to group all foreground pixels into regions where each pixel in a region can be reached from any other via a path of neighboring foreground pixels. The notion of “neighbor” depends on connectivity: with 4-connectivity, only up/down/left/right are neighbors; with 8-connectivity, diagonals count as neighbors too. This operation is used after thresholding or other segmentation to turn a blob of foreground pixels into discrete labeled objects.

A key idea is that multiple pixels may initially get different labels but later are discovered to be part of the same region. To manage this efficiently, CCL often uses the union-find (disjoint set) data structure. Union-find keeps track of which temporary labels are equivalent (belong to the same component) and can later compress them into final labels. The common pattern is a two-pass algorithm: first pass assigns provisional labels and records equivalences; second pass resolves those equivalences and rewrites the label map with final, compact labels.

Algorithm / General Approach

Typical pattern (two-pass, union-find):

Pass 1 (scan & assign provisional labels)
Traverse the image in raster order (row by row, left to right).
For each foreground pixel:
Look at already-processed neighbors (depending on 4- or 8-connectivity).
If no labeled neighbor: assign a new label.
If labeled neighbors exist: assign the minimum neighbor label and union all their labels in the union-find structure.
Pass 2 (resolve equivalences)
For each foreground pixel, replace its provisional label by the root (canonical representative) from union-find, often remapped to compact labels (1,2,3,…).

This separates local decisions (nearest neighbors) from global consistency (merging equivalent labels).

Step-by-Step Strategy

Assume input: 2D array image[h][w] with 0/1, and connectivity conn ∈ {4, 8}.

Initialize

Create labels[h][w] initialized to 0.
Initialize union-find with enough capacity for worst-case labels (e.g., h*w).
Set next_label = 1.

Define neighbor offsets

For 4-connectivity, when scanning top-to-bottom, left-to-right, only check:
top: (i-1, j)
left: (i, j-1)
For 8-connectivity, also check:
top-left: (i-1, j-1)
top-right: (i-1, j+1)

Only neighbors that are already scanned (above or left) matter in the first pass.

First pass: assign provisional labels & union

For i from 0 to h-1:
For j from 0 to w-1:
If image[i][j] == 0: continue (label stays 0).
Collect labels of foreground neighbors among the defined offsets.
If no neighbor label:
labels[i][j] = next_label
Make a new set in union-find for next_label
next_label += 1
Else:
labels[i][j] = min(neighbor_labels)
For every neighbor label L in neighbor_labels:
union(min_label, L) in union-find.

Optional: compress / normalize label roots

After pass 1, you may:
Run a find on each label 1..next_label-1 to get its root.
Build a mapping root -> new_compact_label (e.g., 1..num_components in order of first occurrence).

Second pass: relabel with canonical labels

For i from 0 to h-1:
For j from 0 to w-1:
If labels[i][j] != 0:
root = find(labels[i][j])
labels[i][j] = mapped_label[root] (or directly root if you don’t need compact labels).

Return

Return labels as the label map (background = 0, each component a unique positive integer).

Common Pitfalls

Incorrect neighbor set for connectivity
For 4-connectivity, do not consider diagonals; for 8-connectivity, remember both diagonals above the current pixel.
Checking neighbors outside bounds
Guard indices when accessing (i-1, j), (i, j-1), etc., especially at first row/column.
Not union-ing all neighbor labels
If multiple different neighbor labels exist, you must union them all; otherwise a single component may split into multiple labels.
Forgetting path compression / rank in union-find
Without optimization, union-find can become slow on large images.
Label map vs. union-find index mismatch
Ensure every new label gets a corresponding set in union-find and that you never call find on label 0.
Not compacting label IDs (if required by problem)
Many problems expect labels to be contiguous from 1 to num_components.

Time & Space Complexity

Let the image size be $H \times W$ , with $N = H \cdot W$ .

Time complexity:

First pass:
Visits each pixel once and checks a constant number of neighbors → $O(N)$ .
Union-find union/find operations are almost constant amortized ( $O($ \alpha $(K))$ , inverse Ackermann) where $K$ is number of labels.
Second pass:
Again visits each pixel once and does a find → $O(N)$ .

Overall: $O(N)$ time.

Space complexity:

Label map labels: $O(N)$ .
Union-find arrays: up to $O(K)$ , where $K \le N$ (worst case: every foreground pixel is its own component).
Total: $O(N)$ space.

solution.py

Python 3.13

Test results