Connected Component Labeling

Connected component labeling assigns a distinct integer to each connected set of foreground pixels in a binary image. Two foreground pixels belong to the same component when a chain of foreground pixels joins them, each pixel next to the one before. Labelling turns a mask into objects: the output of thresholding, background subtraction or a segmentation network becomes a set of blobs that can be counted, measured and filtered. Wu, Otoo and Suzuki (2009) call it one of the most fundamental algorithms of image analysis and, in many cases, one of the most time-consuming.

This article covers the definitions that the result depends on (4- and 8-connectivity, and the pairing of foreground and background connectivity), the classical multi-pass and two-pass algorithms, the union-find structure that makes the two-pass algorithm linear in the number of pixels, and how SciPy and scikit-image implement it. The example checks a hand-written two-pass labeller against both libraries on patterns whose component counts are known.

Problem

Given a binary image, partition its foreground pixels into maximal connected sets and give each set its own label. The answer is fully determined once adjacency is fixed: unlike region growing, which decides during growth whether a pixel is similar enough to join, labelling has no criterion to tune and no order dependence in its result. The work lies in computing it in few passes over the image, because a raster scan meets the parts of one object before it knows that they are connected.

The same procedure applies to label images rather than binary ones, joining neighbouring pixels that carry the same value, and to volumes, with 6- or 26-connected voxels.

Inputs and Outputs

• Input: a binary image (or an integer image whose equal-valued regions are to be split into connected pieces), and a connectivity: 4 or 8 in 2D, 6, 18 or 26 in 3D.
• Output: an integer image of the same size, 0 for background and $1, \dots, n$ for the $n$ components, and the count $n$ (always returned by SciPy’s label, and by scikit-image’s with return_num=True).

Per-component measurements (area, bounding box, centroid, moments, Euler number) are computed afterwards from the label image, for instance by scikit-image’s regionprops, or by SciPy’s find_objects (bounding boxes) and sum_labels.

Intuition

In a raster scan, row by row from the top left, the neighbours of the current pixel that have already been visited form the scan mask: the pixel above and the pixel to the left for 4-connectivity; above-left, above, above-right and left for 8-connectivity. If none of them is foreground, the pixel starts something new and gets a fresh label. If some are, it takes one of their labels.

The difficulty is the U. Scanning a U-shaped object from the top, the two arms are met first, as separate pieces, and receive two different labels; only at the bottom, where the arms join, does the scan find a pixel whose mask contains both labels. Pixels already labelled cannot be revisited cheaply. The Region Growing article reports the same observation from Haralick and Shapiro’s survey for a V-shaped region: a single top-to-bottom pass cannot make the two arms one segment, so a second pass is needed.

There are two ways out. A multi-pass algorithm sweeps the image forwards and backwards, letting each pixel take the smallest label among its visited neighbours, until a sweep changes nothing. A two-pass algorithm instead records, during the first scan, that the two labels are equivalent, resolves all equivalences once, and replaces each provisional label by its final one in a second scan. The equivalences are sets that are merged and queried, which is exactly what a union-find (disjoint-set) structure does. Graph-based image segmentation uses the same structure to merge regions in order of edge weight; here every merge is unconditional.

Algorithm

Connectivity. Pixel $(y, x)$ has the 4-neighbours $(y \pm 1, x)$ and $(y, x \pm 1)$, and the 8-neighbours that add the four diagonals. A one-pixel-wide diagonal line is a single component under 8-connectivity and as many components as it has pixels under 4-connectivity.

Two-pass labelling with union-find, in the array form that Wu, Otoo and Suzuki (2009) describe (equation, lemma and theorem numbers in this article are those of their preprint, LBNL-59102):

1. Set a counter $l \leftarrow 1$ and an array $P$ of parent links with $P[0] = 0$ for the background.
2. Scanning phase. Visit the pixels in raster order. For a foreground pixel $e$:
   • if no pixel in its scan mask is foreground, give it the new provisional label $l$, set $P[l] \leftarrow l$ (a one-node tree), and increment $l$;
   • otherwise find the root of each labelled mask neighbour’s tree, take the smallest root $r$, make every one of those trees point at $r$ (a union), and give $e$ the label $r$.
3. Analysis phase. Flatten the trees so that each provisional label points directly to a final, consecutive label.
4. Labelling phase. Replace every pixel’s provisional label by its final label.

Wu et al. use one rule throughout: a union always makes the smaller root the root of the merged tree. Then $P[i] \le i$ for every $i$, the root of a tree is its smallest label, and a single forward loop over $P$ produces consecutive final labels: if $P[i] < i$, label $i$ inherits the already final value $P[P[i]]$; otherwise $i$ is a root and receives the next unused label. The paper calls this procedure flattenL and proves that it yields exactly the labels $0, \dots, k$ for $k$ components.

Multi-pass labelling needs no table. Start from distinct labels, then alternate a forward raster scan (mask above and left) with a backward one (mask below and right), each pixel taking the smallest label in its mask, until a scan changes nothing. The number of scans depends on the shapes in the image, as the example shows.

Decision tree. For 8-connectivity, Wu et al. observe that every pixel of the forward scan mask is a neighbour of the pixel directly above, $b$. If $b$ is foreground, $e$ simply copies its label and the other three need not be read; only when $b$ is background can the pixels above-right and on the left (or above-left) belong to different trees, which is the only case that needs a union. They organize the visits as a decision tree, prove that it gives the same final labels as visiting all four neighbours (their Lemma 4) and that it visits the minimum number of them (Theorem 1), and report in the abstract that it reduces the neighbours visited from 4 to 7/3 on average and the scanning time by a factor of about 2 in their tests. The SPIE paper by Wu, Otoo and Shoshani (2005) notes that the trick does not apply to 4-connected components in 2D.

Mathematical Formulation

Write $I$ for the binary image, $L$ for the label array and $M(e)$ for the scan mask of pixel $e$. The first scan assigns

$$L[e] \leftarrow \begin{cases} 0, & I[e] = 0,\\ l, \; P[l] \leftarrow l, \; l \leftarrow l + 1, & I[i] = 0 \;\; \forall i \in M(e),\\ \min_{i \in M(e),\, I[i] = 1} \mathrm{find}(L[i]), & \text{otherwise,} \end{cases}$$

with every tree touched in the last case attached to that minimum, which is Wu et al.’s Eq. (8) up to notation. Each provisional label starts its own tree, and each union of two different trees reduces the number of trees by one, so after the scan

$$n_{\text{components}} = n_{\text{provisional}} - n_{\text{merges}},$$

where $n_{\text{merges}}$ counts the unions that joined two different trees. The second scan applies $L[e] \leftarrow P[L[e]]$ after flattening (their Eq. 11).

Provisional labels on random images. Wu et al. derive the expected number of provisional labels for an $n \times m$ image whose pixels are foreground independently with probability $q$. A foreground pixel receives a new label when its whole scan mask is background, which for an interior pixel under 8-connectivity has probability $(1 - q)^4$; pixels in the first row, the first column and the last column have smaller masks. Summing over the five mask shapes gives their Eq. (12):

$$n_p = q\left(1 + (m - 1)(1 - q) + (n - 1)(1 - q)^2 + (n - 1)(1 - q)^3 + (m - 2)(n - 1)(1 - q)^4\right).$$

The same argument for the 4-connected mask (above and left only) gives, by our derivation,

$$n_p^{(4)} = q\left(1 + (m - 1)(1 - q) + (n - 1)(1 - q) + (m - 1)(n - 1)(1 - q)^2\right).$$

Topology and the 8/4 pair. A connectivity has to be chosen for the background as well, because holes are background components that do not reach the image border. scikit-image’s documentation of euler_number states the convention: if the object is 4-connected, the background is 8-connected, and conversely. In our reasoning, the mixed pair is needed because 8-connectivity on both sides lets a diagonal line be connected while background pixels pass through its diagonal gaps, and 4-connectivity on both sides lets a closed ring of diagonal steps be disconnected while still enclosing its inside. The Euler number of a 2D binary image is the number of components minus the number of holes; Shape Descriptors uses it as a region descriptor. With the pair fixed, it can be computed with a labeller:

$$\chi = n_{\text{fg}}(c) - \bigl(n_{\text{bg}}(\bar c) - 1\bigr),$$

where $c$ is the foreground connectivity, $\bar c$ the complementary one, and $n_{\text{bg}}$ counts background components of the image padded with one ring of background, the outside being one of them. scikit-image computes it differently, from a look-up table over the $2 \times 2$ configurations of the padded image with the coefficients of Ohser et al., as its source shows.

Parameters

• Connectivity. The only parameter that changes the answer. 8-connectivity joins objects that touch at a corner and keeps thin diagonal structures whole; 4-connectivity separates them. The defaults differ between libraries: scipy.ndimage.label uses a cross-shaped structuring element (4-connectivity in 2D) when none is given, while skimage.measure.label uses full connectivity (connectivity=ndim, so 8 in 2D), as the two source files state.
• Background value. scikit-image’s label takes a background value; SciPy treats every non-zero value as foreground.
• Output type. SciPy returns int32 labels unless the array has at least $2^{31} - 2$ elements; a caller-supplied output must be able to hold the largest label, or the function raises an error (its docstring and source).

Complexity

Every algorithm has to visit every pixel, so $O(p)$ for $p$ pixels is optimal, as Wu et al. note. For general sequences of union and find operations they report that all known union-find methods are superlinear in the worst case; the inverse-Ackermann bound for union by rank with path compression is stated in the graph-based segmentation article. Image labelling has more structure. Wu et al. report that Fiorio and Gustedt (1996) proved the two-pass algorithm with path compression linear by flattening the active trees after each row; their own Theorem 3 shows that any union-find with path compression gives $O(p)$ even without that extra flattening, because the find operations of the scan only touch the active trees, those holding the labels of the row just scanned, and a find with path compression on every node of a $t$-node tree costs at most $3t$ in total (their Theorem 2).

Memory is the label image plus the parent array, whose length is the number of provisional labels and at most the number of foreground pixels. SciPy’s merge table starts at twice the line length and doubles when needed; scikit-image’s Cython labeller allocates one parent entry per pixel, using pixel indices as provisional labels.

Running time is not determined by operation counts alone. Wu et al. point out that a two-pass algorithm makes random memory accesses into its union-find structure, while a multi-pass algorithm reads memory sequentially, which they give as a reason why a multi-pass algorithm such as Suzuki et al.’s, with a label connection table, can be faster than a two-pass algorithm in practice, as had been reported; it usually needed no more than four scans. Their array-based union-find with the decision tree (which they call SAUF) was faster than the contour-tracing algorithm of Chang et al. by 50% on average in their tests, and the SPIE paper reports that using an array instead of pointer-based trees sped up the labelling algorithms by a factor of 5 to 100 in its tests on random binary images.

Implementation

The NumPy, SciPy and scikit-image code (NumPy 2.3.5, SciPy 1.16.3, scikit-image 0.25.2) implements the two-pass labeller above, without the decision tree, and a multi-pass labeller, and checks them on synthetic images whose answers are known by construction:

• a $16 \times 16$ checkerboard, whose 128 foreground pixels touch only at corners: 128 components under 4-connectivity, 1 under 8;
• a 32-pixel diagonal line: 32 components or 1;
• a U with two 2-pixel-wide arms joined at the bottom, the case that forces a merge;
• a $64 \times 64$ square spiral with a 1-pixel wall and a 1-pixel corridor: one long path of 2,110 pixels, checked to be a simple path (two ends, no pixel with more than two 4-neighbours).

For each it compares the labels pixel for pixel with scipy.ndimage.label and with skimage.measure.label applied to an integer copy of the image, which runs scikit-image’s own Cython labeller rather than SciPy’s, prints the provisional labels and merges, and counts the multi-pass scans. It then computes Euler numbers for both connectivity pairs from the labeller and compares them with skimage.measure.euler_number and with values derived by hand (for the checkerboard under the 8/4 pair, $1 - 98 = -97$: each of the 98 background pixels away from the border has four foreground 4-neighbours and is a hole). It prints the default-connectivity difference, compares area, centroid, bounding box and Euler number of a disc, a ring, a square, an L shape and a three-pixel diagonal chain with regionprops, and finally labels 30 random $256 \times 256$ images (foreground probability $q = 0.2, 0.5, 0.8$, seeds 0–4) to compare the provisional-label counts with the formulas above. The tolerance for that comparison, three standard errors of a five-image mean, was fixed before the run from the spread of the count over 200 other seeds. It runs in about one second.

import os
for v in ("OMP_NUM_THREADS", "OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "VECLIB_MAXIMUM_THREADS"):
    os.environ[v] = "1"                       # one BLAS thread, set before NumPy is imported
import numpy as np
from scipy import ndimage as ndi
from skimage import measure

# Scan masks: the neighbours already visited in a raster scan (row by row, left to right).
MASK = {4: [(-1, 0), (0, -1)],                          # b (up), d (left)
        8: [(-1, -1), (-1, 0), (-1, 1), (0, -1)]}       # a, b, c (up-left, up, up-right), d
STRUCT = {4: ndi.generate_binary_structure(2, 1), 8: ndi.generate_binary_structure(2, 2)}


def two_pass(img, conn):
    """Two-pass labelling with an array union-find (parent array P, P[i] <= i, root = smallest label)."""
    H, W = img.shape
    L = np.zeros((H, W), np.int64)
    P = [0]                                   # P[0] = 0 is the background
    merges = 0                                # unions that joined two different trees

    def find_root(i):
        while P[i] < i:
            i = P[i]
        return i

    def set_root(i, root):                    # path compression: point the whole path at root
        while P[i] < i:
            j = P[i]; P[i] = root; i = j
        P[i] = root

    for y in range(H):                        # pass 1: provisional labels and equivalences
        for x in range(W):
            if not img[y, x]:
                continue
            nb = [L[y + dy, x + dx] for dy, dx in MASK[conn]
                  if y + dy >= 0 and 0 <= x + dx < W and L[y + dy, x + dx]]
            if not nb:                        # no labelled neighbour: new provisional label
                L[y, x] = len(P); P.append(len(P))
                continue
            roots = {find_root(n) for n in nb}
            root = min(roots)
            merges += len(roots) - 1
            for n in nb:
                set_root(n, root)
            L[y, x] = root
    provisional = len(P) - 1
    k = 1                                     # flatten: consecutive final labels in order of the roots
    for i in range(1, len(P)):
        if P[i] < i:
            P[i] = P[P[i]]
        else:
            P[i] = k; k += 1
    return np.asarray(P)[L], k - 1, provisional, merges   # pass 2: look up each pixel's final label


def multi_pass(img, conn):
    """Label propagation without an equivalence table: alternate forward and backward raster scans,
    each pixel taking the smallest label in its scan mask, until a scan changes nothing."""
    H, W = img.shape
    lab = np.where(img, np.arange(1, H * W + 1).reshape(H, W), 0)
    scans = 0
    while True:
        scans += 1
        forward = scans % 2 == 1
        offs = MASK[conn] if forward else [(-dy, -dx) for dy, dx in MASK[conn]]
        ys = range(H) if forward else range(H - 1, -1, -1)
        xs = range(W) if forward else range(W - 1, -1, -1)
        changed = False
        for y in ys:
            for x in xs:
                if lab[y, x] == 0:
                    continue
                m = lab[y, x]
                for dy, dx in offs:
                    if 0 <= y + dy < H and 0 <= x + dx < W and 0 < lab[y + dy, x + dx] < m:
                        m = lab[y + dy, x + dx]
                if m < lab[y, x]:
                    lab[y, x] = m; changed = True
        if not changed:
            break
    vals = np.unique(lab[lab > 0])           # renumber 1..n in order of the smallest label
    out = np.zeros_like(lab); out[lab > 0] = np.searchsorted(vals, lab[lab > 0]) + 1
    return out, scans


def euler(img, conn):
    """Components (conn) minus holes: background components of the complementary connectivity
    (12 - conn) in the image padded with background, less the one outside."""
    comps = two_pass(img, conn)[1]
    outside = np.pad(~img, 1, constant_values=True)
    return comps - (two_pass(outside, 12 - conn)[1] - 1)


# ---------- synthetic patterns with known component counts ----------
def checkerboard(n=16):
    i, j = np.indices((n, n)); return (i + j) % 2 == 0

def diagonal(n=32):
    return np.eye(n, dtype=bool)

def u_shape():                                 # two arms that meet only at the bottom
    u = np.zeros((20, 20), bool); u[2:18, 3:5] = True; u[2:18, 15:17] = True; u[16:18, 3:17] = True
    return u

def spiral(n=64):                              # one-pixel wall, one-pixel corridor
    s = np.zeros((n, n), bool); y, x = 0, 0; dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    lengths = [n - 1, n - 1, n - 1]; k = 3
    while lengths[-1] > 0:
        lengths += [n - k, n - k]; k += 2
    s[0, 0] = True
    for t, L in enumerate(lengths):
        if L <= 1:
            break
        dy, dx = dirs[t % 4]
        for _ in range(L):
            y += dy; x += dx; s[y, x] = True
    return s

def blobs():                                   # disc, ring, square, L shape, 3-pixel diagonal chain
    b = np.zeros((96, 96), bool); yy, xx = np.indices(b.shape)
    b |= np.hypot(yy - 20, xx - 20) <= 12
    r = np.hypot(yy - 20, xx - 64); b |= (r <= 12) & (r > 6)
    b[50:80, 10:40] = True
    b[50:90, 55:62] = True; b[83:90, 55:85] = True
    b[60, 75] = b[61, 76] = b[62, 77] = True
    return b


patterns = {"checkerboard": checkerboard(), "diagonal": diagonal(), "U": u_shape(), "spiral": spiral()}
truth = {"checkerboard": {4: 128, 8: 1}, "diagonal": {4: 32, 8: 1}, "U": {4: 1, 8: 1}, "spiral": {4: 1, 8: 1}}
truth_euler = {"checkerboard": {8: -97, 4: 128}, "diagonal": {8: 1, 4: 32}, "U": {8: 1, 4: 1}, "spiral": {8: 1, 4: 1}}

sp = patterns["spiral"]
nb4 = ndi.convolve(sp.astype(int), STRUCT[4].astype(int), mode="constant")[sp] - 1
print(f"data check: spiral {sp.sum()} pixels, {int((nb4 == 1).sum())} with one 4-neighbour, "
      f"max {nb4.max()} 4-neighbours (a simple path)")

print("\nA. patterns          n  truth  ndi  differing pixels (ndi / skimage)  provisional  merges  "
      "prov-merges  multi-pass scans  multi-pass differing")
for name, img in patterns.items():
    for c in (4, 8):
        lab, n, prov, merges = two_pass(img, c)
        ref, n_ref = ndi.label(img, STRUCT[c])
        sk = measure.label(img.astype(np.int64), connectivity=1 if c == 4 else 2)
        mlab, scans = multi_pass(img, c)
        print(f"{name:12s} {c}-conn {n:4d} {truth[name][c]:5d} {n_ref:4d}  {int((lab != ref).sum()):6d} / "
              f"{int((lab != sk).sum()):<6d}                  {prov:5d}  {merges:6d}  {prov - merges:6d}"
              f"  {scans:12d}  {int((mlab != ref).sum()):12d}")

print("\nB. Euler number      hand (components - holes)  skimage euler_number  truth")
for name, img in patterns.items():
    for c in (8, 4):
        e_sk = measure.euler_number(img, connectivity=2 if c == 8 else 1)
        print(f"{name:12s} {c}/{12 - c} pair  {euler(img, c):10d}  {e_sk:22d}  {truth_euler[name][c]:10d}")

cb = patterns["checkerboard"]
print(f"\nC. default connectivity on the checkerboard: scipy.ndimage.label {ndi.label(cb)[1]}, "
      f"skimage.measure.label {measure.label(cb, return_num=True)[1]}")

print("\nD. blob statistics against regionprops")
b = blobs()
for c in (4, 8):
    lab, n, _, _ = two_pass(b, c)
    props = measure.regionprops(ndi.label(b, STRUCT[c])[0])
    idx = np.arange(1, n + 1)
    area = ndi.sum_labels(np.ones_like(lab), lab, idx)
    ys, xs = np.indices(b.shape)
    cy, cx = ndi.sum_labels(ys, lab, idx) / area, ndi.sum_labels(xs, lab, idx) / area
    bbox = [(ys[lab == i].min(), xs[lab == i].min(), ys[lab == i].max() + 1, xs[lab == i].max() + 1) for i in idx]
    eul = [euler(np.pad(lab == i, 1), 8) for i in idx]
    d_area = max(abs(area[i] - p.area) for i, p in enumerate(props))
    d_cent = max(max(abs(cy[i] - p.centroid[0]), abs(cx[i] - p.centroid[1])) for i, p in enumerate(props))
    d_bbox = sum(tuple(bbox[i]) != tuple(p.bbox) for i, p in enumerate(props))
    d_eul = sum(eul[i] != p.euler_number for i, p in enumerate(props))
    print(f"{c}-conn: {n} regions (regionprops {len(props)}); areas {[int(a) for a in area]}; Euler {eul}")
    print(f"        max |area diff| {d_area:.0f}, max |centroid diff| {d_cent:.1e} px, "
          f"bbox mismatches {d_bbox}, Euler mismatches {d_eul}")

print("\nE. random images, 256 x 256, seeds 0-4: differing pixels against ndi.label (all seeds), "
      "provisional labels against Wu et al.'s Eq. (12) (8-conn) and the same count for the 4-conn mask")
tol = {(0.2, 4): 0.0097, (0.5, 4): 0.0113, (0.8, 4): 0.0329, (0.2, 8): 0.0117, (0.5, 8): 0.0266, (0.8, 8): 0.1040}
nr = nc = 256
for q in (0.2, 0.5, 0.8):
    for c in (4, 8):
        diff, provs, direct_ok, merge_ok = 0, [], True, True
        for seed in range(5):
            img = np.random.default_rng(seed).random((nr, nc)) < q
            lab, n, prov, merges = two_pass(img, c)
            diff += int((lab != ndi.label(img, STRUCT[c])[0]).sum())
            provs.append(prov)
            pad = np.zeros((nr + 1, nc + 2), bool); pad[1:, 1:-1] = img          # direct count of pixels
            seen = np.zeros_like(img)                                         # with an empty scan mask
            for dy, dx in MASK[c]:
                seen |= pad[1 + dy:nr + 1 + dy, 1 + dx:nc + 1 + dx]
            direct_ok &= prov == int((img & ~seen).sum())
            merge_ok &= n == prov - merges
        if c == 8:
            e = q * (1 + (nc - 1) * (1 - q) + (nr - 1) * (1 - q) ** 2 + (nr - 1) * (1 - q) ** 3
                     + (nc - 2) * (nr - 1) * (1 - q) ** 4)
        else:
            e = q * (1 + (nc - 1) * (1 - q) + (nr - 1) * (1 - q) + (nc - 1) * (nr - 1) * (1 - q) ** 2)
        rel = abs(np.mean(provs) - e) / e
        print(f"q={q} {c}-conn: differing pixels {diff}, provisional {provs} (direct count {direct_ok}, n = prov - merges {merge_ok}), "
              f"mean {np.mean(provs):.1f} vs expected {e:.1f}, rel. dev. {rel:.5f} (tol {tol[(q, c)]:.4f})")

data check: spiral 2110 pixels, 2 with one 4-neighbour, max 2 4-neighbours (a simple path)

A. patterns          n  truth  ndi  differing pixels (ndi / skimage)  provisional  merges  prov-merges  multi-pass scans  multi-pass differing
checkerboard 4-conn  128   128  128       0 / 0                         128       0     128             1             0
checkerboard 8-conn    1     1    1       0 / 0                           8       7       1             3             0
diagonal     4-conn   32    32   32       0 / 0                          32       0      32             1             0
diagonal     8-conn    1     1    1       0 / 0                           1       0       1             2             0
U            4-conn    1     1    1       0 / 0                           2       1       1             3             0
U            8-conn    1     1    1       0 / 0                           2       1       1             3             0
spiral       4-conn    1     1    1       0 / 0                          17      16       1            33             0
spiral       8-conn    1     1    1       0 / 0                          17      16       1            33             0

B. Euler number      hand (components - holes)  skimage euler_number  truth
checkerboard 8/4 pair         -97                     -97         -97
checkerboard 4/8 pair         128                     128         128
diagonal     8/4 pair           1                       1           1
diagonal     4/8 pair          32                      32          32
U            8/4 pair           1                       1           1
U            4/8 pair           1                       1           1
spiral       8/4 pair           1                       1           1
spiral       4/8 pair           1                       1           1

C. default connectivity on the checkerboard: scipy.ndimage.label 128, skimage.measure.label 1

D. blob statistics against regionprops
4-conn: 7 regions (regionprops 7); areas [441, 328, 900, 441, 1, 1, 1]; Euler [1, 0, 1, 1, 1, 1, 1]
        max |area diff| 0, max |centroid diff| 0.0e+00 px, bbox mismatches 0, Euler mismatches 0
8-conn: 5 regions (regionprops 5); areas [441, 328, 900, 441, 3]; Euler [1, 0, 1, 1, 1]
        max |area diff| 0, max |centroid diff| 0.0e+00 px, bbox mismatches 0, Euler mismatches 0

E. random images, 256 x 256, seeds 0-4: differing pixels against ndi.label (all seeds), provisional labels against Wu et al.'s Eq. (12) (8-conn) and the same count for the 4-conn mask
q=0.2 4-conn: differing pixels 0, provisional [8415, 8454, 8490, 8356, 8453] (direct count True, n = prov - merges True), mean 8433.6 vs expected 8405.0, rel. dev. 0.00340 (tol 0.0097)
q=0.2 8-conn: differing pixels 0, provisional [5395, 5407, 5370, 5363, 5396] (direct count True, n = prov - merges True), mean 5386.2 vs expected 5405.7, rel. dev. 0.00361 (tol 0.0117)
q=0.5 4-conn: differing pixels 0, provisional [8200, 8234, 8222, 8169, 8286] (direct count True, n = prov - merges True), mean 8222.2 vs expected 8256.1, rel. dev. 0.00411 (tol 0.0113)
q=0.5 8-conn: differing pixels 0, provisional [2170, 2161, 2166, 2142, 2108] (direct count True, n = prov - merges True), mean 2149.4 vs expected 2136.1, rel. dev. 0.00621 (tol 0.0266)
q=0.8 4-conn: differing pixels 0, provisional [2100, 2051, 2184, 2211, 2246] (direct count True, n = prov - merges True), mean 2158.4 vs expected 2163.2, rel. dev. 0.00222 (tol 0.0329)
q=0.8 8-conn: differing pixels 0, provisional [136, 138, 141, 135, 138] (direct count True, n = prov - merges True), mean 137.6 vs expected 134.3, rel. dev. 0.02459 (tol 0.1040)

Correctness. The planned check of exact agreement held: on every pattern, under both connectivities, the hand labeller’s output differs from both libraries’ in no pixel, and the same holds on all 30 random images against ndimage.label. The labels agree as numbers, not only as partitions, and this follows from the construction: provisional labels are created in raster order and the root of each tree is its smallest label, which is the label of the component’s first pixel in raster order. SciPy’s merge table also keeps the smaller label as root and numbers labels in the order they were created, and scikit-image’s labeller numbers roots, the lowest pixel index of each component, in index order. All three therefore number components by their first pixel in the scan. The component counts equal the counts known from construction, so that check held as well.

Connectivity. The connectivity hypothesis held for all four patterns: the checkerboard and the diagonal line are one object or a hundred and twenty-eight and thirty-two, depending only on the connectivity; the U and the spiral, built from 4-connected paths, are one component either way. Section C shows the trap this creates in practice: the same call on the same checkerboard gives 128 components in SciPy and 1 in scikit-image, because their defaults differ; the check planned from the two source files held.

Equivalences. The provisional labels and merges show what the first scan records. The U gets two provisional labels, one per arm, and one merge at the base. The spiral gets 17 provisional labels, from the pieces of the path that the scan meets before it knows they are joined, and 16 merges. The 8-connected checkerboard gets eight labels in its first row, whose pixels touch only through the row below, and seven merges. In every row of section A, and in every random image of section E, the number of components equals provisional labels minus merges, and the provisional count equals a direct count of the foreground pixels whose scan mask is empty: both planned identities held everywhere.

Multi-pass scans. The two-pass labeller always reads the image twice. The multi-pass labeller reached the same labels as SciPy in every case (no differing pixels), and the scan counts derived before the run held in all eight cases: 1 to 3 scans on the checkerboard, the line and the U, and 33 on the spiral. The spiral was built to make this happen: the smallest label starts at the outer end of the path, a forward scan carries it along the parts of the path that run rightwards or downwards and a backward scan along those that run leftwards or upwards, and the spiral’s 63 straight segments form 32 alternating groups, so the label needs 32 scans to reach the centre and a 33rd scan finds nothing to change. The number of scans depends on the shapes in the image; with an equivalence table it is always two.

Euler numbers. The labeller’s components-minus-holes agrees with scikit-image’s look-up-table computation and with the hand-derived values in all eight cases, so the Euler check held. The checkerboard is the extreme case: $-97$ under the 8/4 pair (one component with 98 holes) and 128 under the 4/8 pair (128 isolated pixels, no holes). scikit-image’s documentation suggests reading such a disagreement between connectivities as a sign that the image resolution is too low for the objects and holes in it.

Blob statistics. On the blob image the labeller and regionprops agree exactly on the number of regions, their areas, bounding boxes and Euler numbers (0 for the ring, 1 for the others), and the centroids agree to the last bit: every planned comparison held under both connectivities. The three-pixel diagonal chain is one region under 8-connectivity and three single pixels under 4-connectivity, which is the difference between 5 and 7 regions.

Random images. The mean provisional count over five images is within 0.7% of Eq. (12) at $q = 0.2$ and $0.5$ and within 2.5% at $q = 0.8$, where only about 137 pixels per image have an empty mask and the count is noisier; the 4-connected counts are within 0.5% of the corresponding formula. The hypothesis held in all six settings: every mean falls inside its tolerance. At $q = 0.2$ the 4-connected scan creates 1.6 times as many provisional labels as the 8-connected one, because a mask of two pixels is empty more often than a mask of four; at $q = 0.8$ the ratio is about sixteen.

The libraries. scipy.ndimage.label works in any number of dimensions with any centrosymmetric $3 \times \dots \times 3$ structuring element. Its Cython code labels the array one line at a time against the already labelled neighbour lines, keeps a merge table in which every entry points to a smaller label, compresses paths when it merges two labels, and compacts the table into consecutive labels at the end. skimage.measure.label passes boolean images to ndimage.label with a structuring element built from its connectivity argument; integer images, in which equal-valued neighbours are joined, go to its own Cython labeller for 1D to 3D arrays, which uses pixel indices as provisional labels and the find_root/set_root/join_trees operations that its comments credit to Wu et al., and cites Fiorio and Gustedt (1996).

Properties and Behavior

• Exact and order-independent. The partition depends only on the image and the connectivity. Only the numbering depends on the scan order; with smallest-root unions it is the order of each component’s first pixel.
• Linear time. Two-pass labelling with path compression is $O(p)$ (Wu et al., Theorem 3), with a constant that depends heavily on memory access patterns.
• Every foreground pixel is labelled, including single isolated pixels: noise produces components. In the Mathematical Morphology example, noise splits one shape into 250 components and an opening followed by a closing brings the count back to one.
• Duality. Foreground and background need complementary connectivities for holes and the Euler number to behave as expected; the checkerboard above has Euler number $-97$ or $128$ depending on the pair.

Limitations

• Touching objects merge. Labelling separates objects only where background separates them. Two touching disks become one component in the Image Segmentation example, and in the Cell Segmentation example thresholding followed by connected components leaves 161 or more of 184 nuclei inside merged objects. Splitting them needs markers and a watershed, or a different target such as a boundary class.
• Thin structures depend on the connectivity. One-pixel lines, diagonal contacts and pixel-wide gaps are decided by the connectivity rather than by the scene, so the count of objects in a binary image can change by orders of magnitude between 4 and 8, as the checkerboard shows.
• The input must already be binary. Labelling inherits every error of the threshold or classifier that produced the mask, which is why masks are usually cleaned with opening and closing and small components are dropped, as the thresholding and background subtraction articles describe.
• Labels are not identities. Label numbers come from the scan order; in our reading, the same object gets a different number when anything above it in the image changes, so tracking objects across frames needs an explicit association step.

Variants

Wu et al. (2009) group labelling algorithms into five families:

• Multi-pass algorithms repeat the scan until labels stop changing. Suzuki et al.’s scan with a label connection table, as Wu et al. describe it, propagates equivalences through a one-dimensional table during the scans and usually needed no more than four.
• Two-pass algorithms record equivalences in a union-find structure, as above. Wu et al. take Fiorio and Gustedt’s algorithm as the representative and list among others the algorithm of Lumia et al.; the Region Growing article reports that Haralick and Shapiro used Lumia et al.’s two-pass algorithm for their merging pass, and Background Subtraction that Stauffer and Grimson grouped foreground pixels with a two-pass connected-components algorithm.
• One-pass algorithms find an unlabelled foreground pixel and label everything connected to it. The contour-tracing algorithm of Chang et al., as Wu et al. describe it, follows the boundary of each component back to its starting point and then fills in the interior. A breadth-first flood fill from a seed is the same idea for a single component, and is how the flood-fill form of region growing works.
• Algorithms for hierarchical image formats, such as the quadtrees, octrees and bintrees of the works they cite, mostly built on the first two families.
• Parallel algorithms, motivated by labelling being a bottleneck in many pipelines.

Related operations use the same machinery. Binary morphological reconstruction keeps exactly the components of a mask that contain a marker. Hysteresis thresholding in the Canny edge detector keeps the weak-edge components that touch a strong edge. Labelling equal values of an integer image, as skimage.measure.label does by default for integer input, splits each class of a semantic map into connected pieces, a simple way to turn a semantic map into instances. In 3D, the 6-, 18- and 26-neighbourhoods play the role of 4 and 8. Graph-based image segmentation generalizes the idea from “foreground neighbours are joined” to “neighbours are joined when the edge between them is weak relative to the regions’ internal variation”.

Two older works in the references could not be read for this article: Rosenfeld and Pfaltz (1966), and Tarjan (1975), which Wu et al. cite for weighted union. Nothing here is attributed to them beyond that.