Connected Component Labeling

Connected component labeling (alternatively connected component analysis) is an algorithmic application of graph theory, where subsets of " connected components" are uniquely "labeled" based on a given heuristic. Connected component labeling is not to be confused with segmentation.

Connected component labeling is used in computer vision to detect unconnected regions in binary digital images, although color images and data with higher-dimensionality can also be processed. [cite web |author=H. Samet and M. Tamminen |date=1988 |title=Efficient Component Labeling of Images of Arbitrary Dimension Represented by Linear Bintrees |publisher=TIEEE Trans. Pattern Anal. Mach. Intell. |url=http://dx.doi.org/10.1109/34.3918 ] [cite web |author=Michael B. Dillencourt and Hannan Samet and Markku Tamminen |date=1992 |title=A general approach to connected-component labeling for arbitrary image representations} |publisher=J. ACM |url=http://doi.acm.org/10.1145/128749.128750 ] When integrated into an image recognition system or human-computer interaction interface, connected component labeling can operate on a variety of information. [cite web |author=Weijie Chen, Maryellen L. Giger and Ulrich Bick |date=2006 |title=A Fuzzy C-Means (FCM)-Based Approach for Computerized Segmentation of Breast Lesions in Dynamic Contrast-Enhanced MR Images |publisher=Academic Radiology |url=http://dx.doi.org/10.1016/j.acra.2005.08.035 ] [cite web |author=Kesheng Wu, Wendy Koegler, Jacqueline Chen and Arie Shoshani |date=2003 |title=Using Bitmap Index for Interactive Exploration of Large Datasets |publisher=SSDBM |url=http://csdl.computer.org/comp/proceedings/ssdbm/2003/1964/00/19640065abs.htm ]

Overview

A graph, containing vertices and connecting edges, is constructed from relevant input data. The vertices contain information required by the comparison heuristic, while the edges indicate connected 'neighbors'. An algorithm traverses the graph, labeling the vertices based on the connectivity and relative values of their neighbors. Connectivity is determined by the medium; image graphs, for example, can be 4-connected or 8-connected. [cite web |author=R. Fisher, S. Perkins, A. Walker and E. Wolfart |date=2003 |title=Connected Component Labeling |publisher= |url=http://homepages.inf.ed.ac.uk/rbf/HIPR2/label.htm ]

Following the labeling stage, the graph may be partitioned into subsets, after which the original information can be recovered and processed.

Algorithms

The algorithms discussed can be generalized to arbitrary dimensions, albeit with increased time and space complexity.

Two-pass

Relatively simple to implement and understand, the two-pass algorithm [cite book |author=Shapiro, L., and Stockman, G. |date=2002 |title=Computer Vision | publisher=Prentice Hall | page=69-73 | url=http://www.cse.msu.edu/~stockman/Book/2002/Chapters/ch3.pdf] iterates through 2-dimensional, binary data. The first pass uniquely labels non-background regions, and a second pass merges labels on any regions that are spatially connected.

The input data can be modified "in situ" (which carries the risk of data corruption), or labeling information can be maintained in an additional data structure.

On the first pass:

#Iterate through each element of the data by column, then by row
#If the element is not the background
## Get the neighboring elements of the current element
## If there are no neighbors, uniquely label the current element and continue
## Otherwise, find the neighbor with the smallest label and assign it to the current element
## Store the equivalence between neighboring labels

On the second pass:

#Iterate through each element of the data by column, then by row
#If the element is not the background
## Relabel the element with the lowest equivalent label

Here, the background is a classification, specific to the data, used to distinguish salient elements from the foreground. If the background variable is omitted, then the two-pass algorithm will treat the background as another region.

The pseudocode is as follows:

algorithm "TwoPass"(data) linked = [] labels = structure with dimensions of data, initialized with the value of Background "First pass" for row in data: for column in row: if data [row] [col] is not Background neighbours = connected elements with the current element's label if neighbours is empty linked [NextLabel] = set containing NextLabel labels [row] [column] = NextLabel NextLabel += 1 else "Find the smallest label" L = neighbours' labels labels [row] [column] = "min"(L) for label in L linked [label] = "union"(linked [label] , L) "Second pass" for row in data for column in row if labels [row] [column] is not Background labels [row] [col] = "find"(labels [row] [col] ) return labels

The "find" and "union" algorithms are implemented as described in union find.

Others

Some of the steps present in the two-pass algorithm can be merged for efficiency, allowing for a single sweep through the image. Multi-pass algorithms also exist, some of which run in linear time relative to the number of image pixels. [cite web |author=Kenji Suzuki and Isao Horiba and Noboru Sugie |date=2003 |title=Linear-time connected-component labeling based on sequential local operations |publisher=Comput. Vis. Image Underst. |url=http://dx.doi.org/10.1016/S1077-3142(02)00030-9 ]

In the early 1990s, there was considerable interest in parallelizing connected component algorithms in image analysis applications, due to the bottleneck of sequentially processing each pixel. [cite web |author=Yujie Han and Robert A. Wagner |date=1990 |title=An efficient and fast parallel-connected component algorithm |publisher=J. ACM |url=http://doi.acm.org/10.1145/79147.214077 ] .

See also

*Image analysis
*Computer vision
*Feature extraction
*Blob extraction
*Connected component (graph theory)
*union find
*flood fill

References