 Connected-component labeling

Connected-component labeling assigns an identifying number to each separate connected region of an image after choosing which pixels belong to the foreground and which neighboring pixels count as connected. In a binary image, interpret each foreground pixel as a vertex of a graph, with an edge for each allowed neighboring pair. Each component receives one label; background pixels receive a separate background value. The choice of pixel connectivity is part of the problem definition, not an incidental display setting.

For example, consider the binary imageIf a foreground pixel connects only to foreground pixels immediately above, below, left or right, the two ones form two regions. One valid label image is $\left(\begin{array}{cc}1& 0\\ 0& 2\end{array}\right)$. If diagonal neighbors also connect, the same input has one region, with label image $\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$. SciPy's ndimage.label treats zero as background and nonzero entries as foreground; its default two-dimensional neighborhood uses the four axial neighbors. Its neighborhood mask must be symmetric about its centre so that a connection works in both directions.^[ref]

One direct algorithm scans for an unlabelled foreground pixel, starts a flood fill there and assigns a fresh label to every reachable foreground pixel. It then resumes scanning for another unlabelled region. For a fixed-size neighborhood, every pixel and a bounded number of neighbors need be inspected, giving $O(N)$ time complexity for $N$ image pixels, with storage for labels and the pending search. Another approach records provisional labels and merges equivalent ones using a disjoint-set data structure.

The numerical labels are identifiers: swapping labels $1$ and $2$ does not change the segmentation. A single printed character can have several disconnected regions, while touching characters can share one region. Connected-component labeling therefore supplies geometric grouping for image segmentation and optical character recognition; it does not itself determine what an object means.