Connected-Component Labeling

The problem, from first principles

A segmentation mask says which pixels are foreground, but not how many separate objects there are. Connected-component labeling assigns every foreground pixel to the object it belongs to: two pixels are in the same component if a path of foreground pixels links them. Using 4-connectivity, pixels touch only if they share an edge (up, down, left, right), and a diagonal contact does not connect them. The algorithm is a graph search: scan the image, and whenever you meet an unlabeled foreground pixel, start a flood fill (breadth-first search) that labels everything reachable. Component labels give object counts, areas and bounding boxes.

From theory to code

Implement label_components.

Constraints

• binary is a 2-D array of 0 and 1. Return (labels, count) where labels has the same shape, background is 0 and components are numbered 1..count.
• Use 4-connectivity.
• Number the components in the raster-scan order (row by row, left to right) of their first pixel.
• Use an explicit queue (breadth-first search) and do not use recursion, which would overflow on large components.

Hints