# Connected-component labeling Connected-component labeling (CCL) is an algorithmic application of graph theory that assigns unique labels to connected subsets of pixels in digital images, commonly used in computer vision for blob extraction and region analysis. Connected-component labeling (CCL), also known as connected-component analysis, blob extraction, region labeling, or blob discovery, is an algorithmic application of graph theory in which subsets of connected components are uniquely labeled based on a given heuristic. It is used in computer vision to detect connected regions in binary digital images, though color images and higher-dimensional data can also be processed. CCL is distinct from image segmentation, and blob extraction is related to but different from blob detection. In practice, CCL operates on a graph constructed from input data, where vertices represent pixels or elements and edges indicate connectivity between neighbors. An algorithm traverses the graph, assigning labels to vertices based on connectivity and relative values. After labeling, the graph can be partitioned into subsets, allowing the original information to be recovered and processed for tasks such as counting, filtering, and tracking blobs. ## Definition and Terminology The term connected-component labeling is used consistently in academic literature, whereas connected-component analysis (CCA) varies in both terminology and problem definition. Rosenfeld et al. define CCL as the creation of a labeled image in which positions associated with the same connected component of the binary input image have a unique label. Shapiro et al. describe CCL as an operator whose input is a binary image and output is a symbolic image where each pixel's label is an integer uniquely identifying its connected component. There is no consensus on CCA's definition; it is often used interchangeably with CCL. A more extensive definition by Shapiro et al. states that CCA consists of connected-component labeling of black pixels, followed by property measurement of component regions and decision making. This article adopts a broader interpretation that incorporates these perspectives. ## Graph Construction and Connectivity A graph is constructed from relevant input data, with vertices containing information needed for the comparison heuristic and edges indicating connected neighbors. The algorithm traverses the graph, labeling vertices based on connectivity and relative values. Connectivity is determined by the medium; for image graphs, common neighborhoods include 4-connected (north, south, east, west) and 8-connected (including diagonals). Following labeling, the graph may be partitioned into subsets, after which original information can be recovered and processed. This approach generalizes to arbitrary dimensions, though time and space complexity increase accordingly. ## One Component at a Time Algorithm The one-component-at-a-time algorithm is fast, simple to implement, and based on graph traversal methods. It is part of Vincent and Soille's watershed segmentation algorithm, with other implementations existing. The method uses a linked list to keep indexes of connected pixels, with the choice of depth-first or breadth-first search having no practical difference for this application. The algorithm assumes a binary image with foreground and background pixels, aiming to label connected components in the foreground. Steps: 1. Start from the first pixel, set current label to 1. 2. If the pixel is foreground and unlabeled, assign the current label and add it to a queue; otherwise, move to the next pixel. 3. Pop an element from the queue, examine its neighbors (based on connectivity type). If a neighbor is foreground and unlabeled, assign the current label and add it to the queue. Repeat until the queue is empty. 4. Move to the next pixel and increment the current label. Pixels are labeled before being queued, and each foreground pixel's neighbors are checked only once; background pixels' neighbors are not checked. The pseudocode uses two queues to manage pixel processing, ensuring efficient traversal. ## Applications in Computer Vision CCL is widely used in computer vision for detecting connected regions in binary images, often after a thresholding step. Blob extraction can be applied to gray-scale and color images as well. Blobs may be counted, filtered, and tracked, making CCL valuable in image recognition systems and human-computer interaction interfaces. For example, in [machine-learning](https://www.wikiprompt.org/wiki/machine-learning) pipelines, CCL can preprocess images for object detection or segmentation tasks, complementing techniques like [u-net](https://www.wikiprompt.org/wiki/u-net) architectures. It is also used in [artificial-intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence) systems for analyzing medical images, industrial inspection, and autonomous driving, where identifying connected regions is crucial. ## Related Concepts and Extensions CCL is related to but distinct from blob detection, which focuses on identifying regions of interest based on intensity variations. In contrast, CCL labels all connected components based on connectivity. The algorithm can be extended to higher-dimensional data, such as 3D volumes in medical imaging, with increased computational cost. Recent advances in [deep-learning](https://www.wikiprompt.org/wiki/deep-learning) and [neural-network](https://www.wikiprompt.org/wiki/neural-network) models have led to learned approaches for segmentation, but CCL remains a fundamental tool for post-processing and analysis. Its simplicity and efficiency make it a staple in computer vision libraries and frameworks, often used in conjunction with [data-augmentation](https://www.wikiprompt.org/wiki/data-augmentation) and [loss-functions](https://www.wikiprompt.org/wiki/loss-functions) in training pipelines. ## See Also - [computer-vision](https://www.wikiprompt.org/wiki/computer-vision) - image-segmentation - blob-detection - graph-theory ## External links - [Wikipedia: Connected-component labeling](https://en.wikipedia.org/wiki/Connected-component_labeling) --- Source: https://www.wikiprompt.org/wiki/connected-component-labeling License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/) Last updated: 2026-09-14T04:26:40.109218+00:00