Connected-component labeling is the image analysis operation that assigns a unique integer label to every group of connected foreground pixels in a binary or discrete-valued image. In computer vision, it turns a thresholded mask into a set of distinct regions, often called blobs, that can be counted, measured and filtered individually.
The operation sits between low-level pixel processing and object-level reasoning. Typical inputs come from image thresholding, background subtraction or a segmentation mask, and typical outputs feed object counting, defect inspection, document layout analysis and region statistics such as area, centroid and bounding box.
How connected-component labeling works
Connected-component labeling works by scanning the image and grouping foreground pixels that touch each other according to a chosen neighborhood rule. Two pixels belong to the same component when a path of foreground pixels links them, so the result partitions the foreground into disjoint sets.
The classic approach is the two-pass algorithm. The first pass scans row by row, gives each foreground pixel a provisional label taken from already visited neighbors, and records label equivalences whenever two different provisional labels meet. Between passes, the equivalences are resolved, usually with a union-find data structure. The second pass replaces every provisional label with its final representative.
An alternative is flood fill, also called seed filling or region growing. The algorithm finds an unlabeled foreground pixel, assigns a new label and spreads it to all connected pixels with a stack or queue. Flood fill is simple to implement but accesses memory less predictably, which usually makes it slower on large images.
Connectivity rules and their effect
The connectivity rule defines which neighboring pixels count as touching, and it directly changes the number and shape of components. The table below compares the standard choices for two-dimensional and three-dimensional data.
| Connectivity | Neighbors considered | Typical effect |
|---|---|---|
| 4-connectivity | Up, down, left, right | Diagonal contacts split objects |
| 8-connectivity | All eight surrounding pixels | Diagonal contacts merge objects |
| 6-connectivity | Face neighbors in a 3D volume | Most conservative 3D grouping |
| 18-connectivity | Face and edge neighbors in 3D | Intermediate 3D grouping |
| 26-connectivity | Face, edge and corner neighbors in 3D | Most permissive 3D grouping |
Digital topology adds an important subtlety. Using the same rule for foreground and background can create topological paradoxes, such as a diagonal line that neither separates nor connects regions. A common convention is therefore 8-connectivity for the foreground and 4-connectivity for the background, or the reverse, which keeps holes and boundaries consistent.
Algorithm families and performance
Modern implementations differ mainly in how efficiently they resolve equivalences and how many neighbor checks they perform per pixel. Optimized algorithms can label megapixel images in a few milliseconds on a single CPU core, depending on image content and memory bandwidth.
| Algorithm family | Core idea | Strengths | Weaknesses |
|---|---|---|---|
| Two-pass with union-find | Provisional labels, then resolve equivalences | Predictable, cache-friendly | Needs an equivalence table |
| Flood fill | Grow each region from a seed | Easy to implement | Irregular memory access |
| Block-based scanning | Process 2×2 pixel blocks with decision trees | Fewer comparisons per pixel | More complex code |
| Run-length based | Label horizontal runs instead of pixels | Fast on sparse images | Extra encoding step |
| Parallel GPU labeling | Iterative or union-find on many threads | High throughput on large images | Synchronization overhead |
Most image processing libraries expose labeling with component statistics in one call, returning the label image plus area, bounding box and centroid for each region. This combined output avoids a second scan and is the usual entry point in production code.
How it relates to segmentation tasks
Connected-component labeling is a deterministic grouping step, not a learned recognition method, and it is often confused with segmentation tasks that use neural networks. The table clarifies how it differs from neighboring computer vision concepts.
| Concept | Input | Output | Learns from data |
|---|---|---|---|
| Connected-component labeling | Binary or label image | One ID per connected region | No |
| Semantic segmentation | Color or grayscale image | Class per pixel | Yes |
| Instance segmentation | Color or grayscale image | Mask per object instance | Yes |
| Image thresholding | Grayscale image | Binary mask | Usually no |
| Object detection | Color or grayscale image | Bounding boxes with classes | Yes |
The two worlds frequently combine. A semantic segmentation network may output a per-pixel class mask, and connected-component labeling then splits that mask into separate instances when objects do not touch. This lightweight post-processing is common in medical imaging, satellite analysis and industrial inspection.
Practical pipeline and common pitfalls
A reliable labeling pipeline depends on clean binary input, because the algorithm faithfully reproduces every flaw in the mask. Typical preprocessing includes noise filtering, thresholding and morphological operations such as opening and closing.
- Convert the image to a binary mask with thresholding or a segmentation model.
- Apply morphological opening to remove specks and closing to bridge small gaps.
- Run labeling with an explicit connectivity choice that matches the object geometry.
- Compute statistics and filter components by area or shape to discard noise.
- Pass the surviving regions to measurement, counting or classification.
Most failures come from the mask rather than the labeling algorithm itself. The following table maps common symptoms to their causes and fixes.
| Symptom | Likely cause | Fix |
|---|---|---|
| Too many tiny components | Sensor noise or speckle in the mask | Opening plus a minimum area filter |
| Touching objects merged | Objects share boundary pixels | Watershed or distance transform splitting |
| One object split in two | Thin gaps or 4-connectivity | Closing or 8-connectivity |
| Label count overflow | Too many regions for the label type | Use a 32-bit label image |
Explained without jargon
Connected-component labeling is a way for a computer to find separate objects in a black-and-white picture. Imagine a sheet of paper with several ink blots. The computer looks at every dark dot and asks which other dark dots it touches. All dots that touch, directly or through a chain, belong to the same blot.
Each blot then gets its own number, like a name tag. Once every blot has a tag, the computer can count them, measure their size and locate them, which is the first step toward understanding what is in the picture.
A typical use case
A quality control engineer at an electronics factory inspects printed circuit boards for solder splashes. A camera captures each board at 12 megapixels, and an adaptive threshold produces a binary mask in which reflective solder appears white.
After a morphological opening with a 3×3 kernel, the inspection software runs connected-component labeling with 8-connectivity and computes the area and position of every region. Regions that match the expected pad layout are ignored, and any extra component larger than about 40 pixels outside a pad is reported as a defect.
The whole step takes under 15 milliseconds per board on a standard industrial PC. The result is automatic defect detection at full line speed, with each faulty board flagged together with the exact coordinates of the splash for manual rework.