📘

Connected Components Labeling

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

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:

4-connectivity analysis: Top-left and bottom-left 1s are connected vertically → Component 1 Top-right and bottom-right 1s are connected vertically → Component 2

Scan row by row:

(0,0)=1: No labeled neighbors → label 1
(0,2)=1: No labeled neighbors → label 2
(1,0)=1: Neighbor above is 1 → label 1
(1,2)=1: Neighbor above is 2 → label 2

Result: Two separate components labeled 1 and 2.

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

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.