Connected Components Labeling

1. 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.

---

2. 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).

---

3. Step-by-Step Strategy

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

1. 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.

2. 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.

3. 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.

4. 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).

5. 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).

6. Return

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

---

4. 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.

---

5. 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.