ScientiaLux
strataquest Glossary › Connected Component Labeling
BOM Operation

Connected Component Labeling

Assigning unique IDs to contiguous foreground regions

View
Definition
The foundational connected-component labeling algorithm that scans a binary image, identifies contiguous groups of foreground pixels, and assigns each group a unique integer ID — creating the coded images that enable all per-object tracking, measurement, and classification in StrataQuest.
Two-Pass Algorithm
Scan → assign → resolve equivalences
Connectivity Choice
4-connected vs. 8-connected defines object boundaries
Creates Coded Images
Transforms binary masks into trackable objects
Morphological Alternative
Iterative dilation constrained to foreground

How It Works

Connected-component labeling assigns unique IDs to contiguous foreground regions in a binary image using a classical two-pass algorithm:

  1. First pass — Scan rows top to bottom, left to right. At each foreground pixel, examine already-visited neighbors (left, above, upper-left, upper-right for 8-connectivity). If no foreground neighbors exist, assign a new label. If one neighbor has a label, copy it. If multiple neighbors have different labels, assign one and record the equivalence.
  2. Second pass — Resolve all recorded equivalences using a union-find data structure, replacing temporary labels with their canonical representatives. The output has contiguous label numbers with no duplicates.

An alternative morphological approach (Solomon & Breckon): iteratively dilate from a seed pixel within one component, constrained to the original binary foreground, until convergence identifies the entire connected component. Clear from the working image, increment label, repeat until all components are labeled.

Simplified

After thresholding creates a black-and-white image, the Label operation figures out which white pixels belong together. It scans across the image — when neighboring white pixels touch, they get the same number. When two groups that were previously numbered separately turn out to be connected, their numbers are merged. The result: every separate object has a unique ID.

Image Processing Foundation

Connected-component labeling is one of the most fundamental algorithms in image processing, appearing in Gonzalez & Woods (Chapter 9) and Solomon & Breckon as a core building block for object analysis.

Connectivity

The definition of "connected" critically affects results:

  • 4-connectivity — Only N, S, E, W neighbors. Diagonal pixels are separate objects. Tends to produce more, smaller objects.
  • 8-connectivity — Includes all eight neighbors (diagonals). Diagonal pixels belong to the same object. Tends to merge objects that barely touch at corners.

Solomon & Breckon note that the choice "is more than just a matter of preference" — it fundamentally changes the topology of detected objects.

Union-Find Data Structure

The equivalence resolution in the second pass uses a union-find (disjoint-set) data structure with path compression and union by rank. This ensures that the second pass runs in near-linear time, making the overall algorithm efficient even for images with thousands of objects.

Flood-Fill Variant

A related algorithm, flood-fill, uses constrained dilation from a seed point to find connected components. Solomon & Breckon describe this as: "x_k = (x_{k-1} dilated by B) AND A" — iterative dilation intersected with the original image. The structuring element B "must not be larger than the boundary thickness" to prevent leaking through thin walls.

Simplified

Connected-component labeling is how the computer goes from 'these pixels are bright' to 'this is object #1, this is object #2, etc.' Without this step, you can see structures in an image but can't count them, measure them individually, or track them through analysis. It's the bridge between pixel data and object data.

Parameters & Settings

ParameterTypeDescription
InputBinary imageA thresholded image where foreground (non-zero) pixels represent objects to be labeled.
Connectivity4 or 8Neighborhood connectivity. 4-connectivity: orthogonal neighbors only (produces more separate objects). 8-connectivity: includes diagonals (merges diagonally-touching pixels into one object).
Simplified

The main setting is Connectivity: use 4-connected if you want diagonally-touching objects to be counted separately, 8-connected if diagonal touching means they're the same object. For most tissue analysis, 8-connectivity is standard.

Connected Terms

Share This Term
Term Connections