Connected Component Labeling

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Connected-component labeling — (alternatively connected component analysis, blob extraction, region labeling, blob discovery, or region extraction) is an algorithmic application of graph theory, where subsets of connected components are uniquely labeled based on a given… …   Wikipedia

  • Connected component — Connected components are part of topology and graph theory, two related branches of mathematics. For the graph theoretic concept, see connected component (graph theory). In topology: connected component (topology). Implementations: Connected… …   Wikipedia

  • Connected component (graph theory) — A graph with three connected components. In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example,… …   Wikipedia

  • Blob extraction — is an image segmentation technique that categorizes the pixels in an image as belonging to one of many discrete regions. Blob extraction is generally performed on the resulting binary image from a thresholding step. Blobs may be counted, filtered …   Wikipedia

  • Comparison of image processing software — The following table provides a comparison of image processing software. Functionality Matlab*[1] Mathematica[2] imageJ FIJI (software) Population Extract alpha channel No …   Wikipedia

  • Flood fill — Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi dimensional array. It is used in the bucket fill tool of paint programs to determine which parts of a bitmap to fill with color, and… …   Wikipedia

  • Minimum spanning tree-based segmentation — Contents 1 Image segmentation introduction 2 Motivation for graph based methods 3 From images to graphs 4 Minimum Spanning Tree segmentation algorithms …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Binary image — A binary image is a digital image that has only two possible values for each pixel. cite news |url=http://www.codersource.net/csharp color image to binary.aspx |title=Conversion of a Color Image to a Binary Image |publisher=CoderSource.net… …   Wikipedia

  • Feature extraction — In pattern recognition and in image processing, Feature extraction is a special form of dimensionality reduction.When the input data to an algorithm is too large to be processed and it is suspected to be notoriously redundant (much data, but not… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”