Introduction

Connected component labeling assigns a unique label to each connected foreground region in a binary image. Disjoint sets, also called union-find, are useful because the first scan of the image often discovers that two temporary labels actually refer to the same component, and union-find lets you merge those equivalences efficiently.

Why Union-Find Fits Connected Components

When you scan a binary image row by row, a foreground pixel can encounter neighboring pixels that already have labels. Sometimes there is only one neighboring label, but sometimes two different labels both touch the current pixel and must later be recognized as the same component.

That is the exact job of a disjoint-set structure:

• 'find returns the representative label of a set'
• 'union merges two labels that refer to one component'

Two-Pass Labeling Strategy

The classic union-find CCL algorithm has two passes.

First Pass

For each foreground pixel:

• inspect already-visited neighbors
• assign a new label if no foreground neighbor exists
• reuse an existing label if one neighbor label exists
• assign one label and union the rest if multiple neighbor labels exist

Second Pass

Replace every temporary label with its root representative from the disjoint-set structure.

That second pass collapses equivalent provisional labels into one final component label.

A Small Python Example

This example uses 4-connectivity and labels 1 pixels in a binary image.

1class UnionFind:
2    def __init__(self):
3        self.parent = {}
4
5    def make_set(self, x):
6        self.parent[x] = x
7
8    def find(self, x):
9        if self.parent[x] != x:
10            self.parent[x] = self.find(self.parent[x])
11        return self.parent[x]
12
13    def union(self, a, b):
14        ra = self.find(a)
15        rb = self.find(b)
16        if ra != rb:
17            self.parent[rb] = ra
18
19
20def label_components(image):
21    rows = len(image)
22    cols = len(image[0])
23    labels = [[0] * cols for _ in range(rows)]
24    uf = UnionFind()
25    next_label = 1
26
27    for r in range(rows):
28        for c in range(cols):
29            if image[r][c] == 0:
30                continue
31
32            neighbors = []
33            if r > 0 and labels[r - 1][c] > 0:
34                neighbors.append(labels[r - 1][c])
35            if c > 0 and labels[r][c - 1] > 0:
36                neighbors.append(labels[r][c - 1])
37
38            if not neighbors:
39                labels[r][c] = next_label
40                uf.make_set(next_label)
41                next_label += 1
42            else:
43                smallest = min(neighbors)
44                labels[r][c] = smallest
45                for n in neighbors:
46                    uf.union(smallest, n)
47
48    for r in range(rows):
49        for c in range(cols):
50            if labels[r][c] > 0:
51                labels[r][c] = uf.find(labels[r][c])
52
53    return labels
54
55
56image = [
57    [1, 0, 1, 1],
58    [1, 1, 0, 1],
59    [0, 1, 0, 0],
60]
61
62for row in label_components(image):
63    print(row)

This example keeps the idea visible: assign temporary labels first, then resolve label equivalences through union-find.

Four-Connected Versus Eight-Connected

The neighbor rule changes the result.

• 4-connected usually checks north and west during the first pass
• 8-connected also considers north-west and north-east

The union-find structure does not change much. What changes is which previously visited neighbors you treat as connected.

Why Path Compression Helps

Without optimization, repeated find operations can become expensive as the equivalence structure grows. Path compression makes every later find flatter and faster. Combined with union heuristics, the algorithm becomes almost linear for practical image sizes.

That is why union-find is the standard textbook companion to two-pass component labeling.

Common Pitfalls

The most common mistake is forgetting to union all distinct neighboring labels when a pixel touches multiple provisional components. If you skip that, the second pass cannot collapse them correctly.

Another mistake is mixing 4-connectivity logic with 8-connectivity expectations. The neighborhood rule changes which components merge.

A third issue is trying to finalize labels during the first pass without recording equivalences. That usually produces duplicate labels for one component.

Summary

• Connected component labeling often needs temporary labels and later equivalence merging.
• Disjoint sets provide efficient find and union operations for that equivalence management.
• The standard approach is a first pass for provisional labels and a second pass for canonical labels.
• Path compression makes the union-find structure efficient in practice.
• Choose 4-connectivity or 8-connectivity deliberately because it changes the labeling result.