Connected-component labeling
Find and number separate blobs in a binary image with a flood fill, and measure their sizes.
On this page
Queues and binary images.
- Find and number separate blobs in a binary image with a flood fill, and measure their sizes.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
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.
Code example
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
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
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 |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
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.