Introduction
A mask says which pixels are foreground, but not how many objects there are or where each one is. To count coins on a table, read the characters on a licence plate or reject a part with a missing hole, a program must group foreground pixels into separate objects and measure each one. This step is called connected component labelling, and it turns a picture into data: a list of objects with sizes and positions.
How it works
Connectivity. Two foreground pixels belong to the same object if you can walk from one to the other through foreground neighbours. Which pixels count as neighbours is a choice:
- 4-connectivity: only the four pixels that share a side.
- 8-connectivity: also the four diagonal pixels.
A diagonal line of pixels is one object with 8-connectivity but many separate pixels with 4-connectivity. Libraries differ: OpenCV defaults to 8, while SciPy's ndimage.label defaults to 4, so always pass the connectivity you mean.
Flood fill. Scan the image row by row. When you find a foreground pixel with no label yet, start a new label and flood it: put the pixel on a stack; repeatedly pop a pixel and push each foreground neighbour that has no label yet, labelling it as you push. When the stack is empty, the whole component has that label. Continue the scan. Every pixel is pushed at most once, so the work grows in proportion to the image size. (Libraries often use a faster two-pass algorithm with union-find, which gives the same components.)
Measuring objects. With each object's pixels collected:
- Area: the number of pixels.
- Bounding box: the smallest and largest row and column.
- Centroid: the mean row and mean column, the object's balance point.
- Fill ratio (extent): area ÷ bounding-box area. A solid rectangle gives 1; a thin diagonal line gives much less.
Filtering by area is the usual way to throw away noise that survived morphology.
Boundaries and contours. A boundary pixel is a foreground pixel with at least one background (or outside) neighbour on a side; the others are interior pixels. The boundary pixels form the object's outline. Contour tracing walks around that outline in order, giving a list of points that can be simplified, measured (perimeter, area) or compared with shapes. Counting boundary pixels gives a rough perimeter; a compact shape has a small perimeter for its area.
Example
grid = [
"##..#",
"#..#.",
"..#..",
]
FOUR = [(-1, 0), (1, 0), (0, -1), (0, 1)]
EIGHT = FOUR + [(-1, -1), (-1, 1), (1, -1), (1, 1)]
def label(grid, steps):
h, w = len(grid), len(grid[0])
labels = [[0] * w for _ in range(h)]
areas = []
for r in range(h):
for c in range(w):
if grid[r][c] == "#" and labels[r][c] == 0:
areas.append(0)
labels[r][c] = len(areas)
stack = [(r, c)]
while stack:
y, x = stack.pop()
areas[-1] += 1
# neighbours that are inside the grid, set, and not labelled yet
new = [(y + dy, x + dx) for dy, dx in steps if 0 <= y + dy < h and 0 <= x + dx < w and grid[y + dy][x + dx] == "#" and labels[y + dy][x + dx] == 0]
for ny, nx in new:
labels[ny][nx] = len(areas)
stack += new
return ["".join([str(v) if v else "." for v in row]) for row in labels], areas
map4, areas4 = label(grid, FOUR)
map8, areas8 = label(grid, EIGHT)
print("4-connectivity:", len(areas4), "objects, areas", areas4)
print("8-connectivity:", len(areas8), "objects, areas", areas8)
for a, b, c in zip(grid, map4, map8):
print(" ", a, " ", b, " ", c)Line by line
- The 3 × 5 grid has an L-shaped group of three pixels at the top-left and a diagonal line of three pixels running down to the left from the top-right.
labelscans in reading order and floods each new object, counting its area.- The flood pops a pixel and collects its neighbours that are inside the grid, set and not yet labelled, labelling them before pushing, so no pixel is pushed twice.
- With 4-connectivity, the diagonal pixels do not touch, so there are 4 objects with areas 3, 1, 1 and 1.
- With 8-connectivity, the diagonal line is one object, so there are 2 objects of 3 pixels each.
- The three columns show the grid, the 4-connected labels and the 8-connected labels.
Expected result
4-connectivity: 4 objects, areas [3, 1, 1, 1]
8-connectivity: 2 objects, areas [3, 3]
##..# 11..2 11..2
#..#. 1..3. 1..2.
..#.. ..4.. ..2..
In the real world
Cell counters label and measure every cell in a microscope image, optical character recognition separates characters before reading them, and quality checks count holes and measure parts. In OpenCV (shown as text; it does not run on this site):
import cv2
n, labels, stats, centroids = cv2.connectedComponentsWithStats(mask, connectivity=8)
for i in range(1, n): # label 0 is the background
x, y, w, h, area = stats[i]
print(i, area, (x, y, w, h), centroids[i])
contours, hierarchy = cv2.findContours(mask, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
for c in contours:
print(cv2.contourArea(c), cv2.boundingRect(c)) # boundingRect gives x, y, w, h
Note that OpenCV reports boxes as x, y, width, height, with x the column.
Common mistakes
- Not saying which connectivity you use, so counts differ between programs.
- Using recursion for flood fill on large objects, which hits Python's recursion limit. Use an explicit stack.
- Labelling a pixel only when it is popped, so the same pixel is pushed many times.
- Forgetting that label 0 is the background in library output.
- Mixing up (x, y, width, height) and (row, column) when reading boxes.
Best practices
- Clean the mask with morphology before labelling.
- Filter objects by area (and maybe fill ratio) to drop noise and keep real objects.
- Store measurements in a list of records, one per object, so later steps can sort and filter them.
- Draw labels or boxes back onto the image to check the result visually.
Summary
Connected component labelling groups foreground pixels into objects, using 4- or 8-connectivity and a flood fill with an explicit stack. Each object's pixels give its area, bounding box, centroid and fill ratio. Boundary pixels, those with a background neighbour on a side, form the outline that contour tracing follows.
Quick check
Key takeaways
- Labelling turns one mask into a list of objects you can count, measure and filter.
- Whether diagonal pixels connect changes the count: always say which connectivity you use.
- Area, bounding box and centroid are simple sums over each object's pixels; boundary pixels are those with a background neighbour.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.