Connected Components

Botie's mask contains several bright patches. Counting its ones gives an area, but he wanted to count seeds. We need to group pixels that belong together before counting the groups.

A first rule is to put neighbouring foreground pixels in the same region. That sounds straightforward until two pixels touch only at a corner. Let's decide what counts as a neighbour, then follow one region through the mask.

Two bright pixels touching at a corner may be connected under one neighbour rule and separate under another. Compare the supplied masks and inspect the labels before trusting the region count.

3

Four-connectivity uses the four edge-sharing neighbours. Eight-connectivity includes the four diagonal neighbours as well. Two foreground pixels belong to the same component if a path of allowed foreground steps joins them.

The choice depends on what adjacency means for the task. Neither convention can tell us that two touching seeds are physically separate objects.

Four-neighbour offsets (row, column):
(-1, 0), (1, 0), (0, -1), (0, 1)

A path may turn and may be long. Connected does not mean every pixel directly touches every other pixel.

Scan the grid until you find an unlabelled foreground pixel. Give it a new positive label and put its address in a queue. A queue holds positions waiting to be explored.

Remove one address, inspect its allowed neighbours, and add any unlabelled foreground neighbours. Label a position when you add it, so several paths cannot add it repeatedly. When the queue is empty, that connected region is complete.

Start a region
→ label and queue its first pixel
→ visit queued pixels and add eligible neighbours
→ stop when no queued positions remain

In Python, a tuple can store a row and column. A deque provides efficient removal from the front when implementing this traversal.

Now resume scanning the mask. A labelled foreground pixel already belongs to a region. An unlabelled foreground pixel begins the search for another region. We leave background at zero.

Our workshop scans each row from left to right, then moves down, assigning consecutive labels as it discovers regions. Those numbers let us refer to the groups. A different scan order could give the same groups different numbers without changing the segmentation.

Labelled mask:
1 1 0 2
0 1 0 2
0 0 0 0
Region count = 2

For our consecutive numbering, the maximum label equals the region count. That shortcut does not apply to arbitrary externally supplied label IDs.

Once pixels carry region labels, count how many positions have each positive label. That gives areas in pixels. Taking the minimum and maximum row and column positions of one label also gives a surrounding rectangle.

Do not include label zero when reporting foreground regions. An area cutoff may remove small regions, but it encodes an assumption about object size and should be checked against real examples.

A region's area and its enclosing rectangle describe different things. A hollow or irregular region does not fill every position inside its rectangle.

import numpy as np
labels = np.array([[1,1,0,2], [0,1,0,2], [0,0,0,0]])
areas = np.bincount(labels.ravel())
print(areas[1:].tolist())

[3, 2]

Two touching seeds can form one component. One damaged mask can split a single seed into several components. Labelling answers a question about connectivity in the supplied mask, not the true number of physical objects.

Inspect uncertain cases and revisit segmentation when that distinction matters. In Botie's workshop, switch the neighbour rule and check a diagonal example before trusting the count.

The full pipeline now has distinct responsibilities: intensities describe pixels, thresholding selects them, morphology changes mask geometry, and labelling groups reachable foreground positions.

Once one region has a label, its row and column positions supply a centroid and an enclosing rectangle. The centroid averages pixel coordinates; it is not necessarily a foreground pixel, especially for a curved or hollow region.

The rectangle needs exclusive lower and right boundaries to match array slicing. Adding one to the largest included pixel index performs that conversion. This is different from adding one to already continuous box coordinates.

import numpy as np
labels = np.array([[0,1,1,0],[0,1,0,0],[0,0,0,0]])
rows, cols = np.nonzero(labels == 1)
print([round(float(rows.mean()), 3), round(float(cols.mean()), 3)])
print([int(rows.min()), int(cols.min()), int(rows.max()+1), int(cols.max()+1)])

[0.333, 1.333]
[0, 1, 2, 3]

One traversal may call a seed region one while another calls it three. Compare membership rather than the raw label numbers: pixels grouped together by one result should be grouped together by the other, with background handled consistently.

Test diagonal contact, thin bridges, holes, an empty mask and an object touching the boundary. These reveal the connectivity and border conventions. A component count alone can conceal an incorrect partition whose number of groups happens to match.