Connected-component labeling
Find and number separate blobs in a binary image with a flood fill, and measure their sizes.
from collections import deque
GRID = [
"11000",
"11001",
"00001",
"10100",
"11100",
]
def label_components(grid):
rows, cols = len(grid), len(grid[0])
labels = [[0] * cols for _ in range(rows)]
count = 0
sizes = []
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and labels[r][c] == 0:
count += 1
size = 0
queue = deque([(r, c)])
labels[r][c] = count
while queue:
y, x = queue.popleft()
size += 1
for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == "1" and labels[ny][nx] == 0:
labels[ny][nx] = count
queue.append((ny, nx))
sizes.append(size)
return count, sizes, labels
count, sizes, labels = label_components(GRID)
print(count, sizes)
for row in labels:
print(*row)3 [4, 2, 5] 1 1 0 0 0 1 1 0 0 2 0 0 0 0 2 3 0 3 0 0 3 3 3 0 0
Explanation
After thresholding, a binary image contains groups of foreground pixels. Connected-component labeling gives each separate group, or blob, its own number. It is how a program counts cells in a microscope image, finds the characters in a scanned line of text, or separates objects before measuring them.
Two foreground pixels belong to the same component if there is a path of foreground pixels between them, where each step moves to a neighbour. The neighbourhood definition matters. With 4-connectivity a pixel's neighbours are the pixels directly above, below, left, and right. With 8-connectivity the diagonals count too, so two pixels touching only at a corner join the same blob. The program uses 4-connectivity.
The method here scans the image in reading order. Whenever it finds an unlabelled foreground pixel it starts a breadth-first flood fill from it, labelling every reachable foreground pixel with the next number and counting its size. The 5 × 6 test image contains three components of sizes 4, 2, and 5. The two pixels in the lower left, (3, 0) and (3, 2), are only connected through the row below them, which the fill follows. Production libraries use a two-pass algorithm with union-find, which is faster, but gives the same labelling.
Explore the dry run
from collections import deque GRID = [ "11000", "11001", "00001", "10100", "11100",] def label_components(grid): rows, cols = len(grid), len(grid[0]) labels = [[0] * cols for _ in range(rows)] count = 0 sizes = [] for r in range(rows): for c in range(cols): if grid[r][c] == "1" and labels[r][c] == 0: count += 1 size = 0 queue = deque([(r, c)]) labels[r][c] = count while queue: y, x = queue.popleft() size += 1 for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)): if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == "1" and labels[ny][nx] == 0: labels[ny][nx] = count queue.append((ny, nx)) sizes.append(size) return count, sizes, labels count, sizes, labels = label_components(GRID)print(count, sizes)for row in labels: print(*row)Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| An unlabelled foreground pixel starts a new component. | found (0, 0): label 1 | — | |
| 4-connectivity: look at the pixels above, below, left, and right. | found (0, 0): label 1 | — | |
| Every reachable foreground pixel receives the same label. Marking it also records that it has been visited. | found (0, 0): label 1 | — | |
| Three blobs, with 4, 2, and 5 pixels. | found (0, 0): label 1 | 3 [4, 2, 5] | |
| The label map: the three components are numbered 1, 2, and 3 in reading order, and the background stays 0. | found (0, 0): label 1 | 3 [4, 2, 5] 1 1 0 0 0 1 1 0 0 2 0 0 0 0 2 3 0 3 0 0 3 3 3 0 0 |
Cost and common mistakes
O(H·W) time and O(H·W) memory for the label map and queue.
- 4- and 8-connectivity give different counts when blobs touch only at corners. Choose the one that matches your problem.
- Marking pixels as visited when they are queued, not when they are dequeued, prevents adding a pixel to the queue twice.
- Recursive flood fill overflows the call stack on large blobs. Use an explicit queue or stack.
Try it yourself
How many components would 8-connectivity find in this image?
Reveal answer and reasoning
Three. No two blobs touch diagonally here, so the labelling is the same as with 4-connectivity.