= 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 (graph theory)> 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 image>
$$
B=\begin{pmatrix}1&0\\0&1\end{pmatrix}.
$$
If 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{smallmatrix}1&0\\0&2\end{smallmatrix}\right)$. If diagonal neighbors also connect, the same input has one region, with label image $\left(\begin{smallmatrix}1&0\\0&1\end{smallmatrix}\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.<label in the SciPy documentation>[Parameters, input and structure; Notes, requirement for two-way connections]{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.
Back to article page
