Connected-component labeling
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.
Python
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)