{{Short description|Algorithmic application of graph theory}} '''Connected-component labeling''' ('''CCL'''), '''connected-component analysis''' ('''CCA'''), '''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 heuristic. Connected-component labeling is not to be confused with segmentation.
Connected-component labeling is used in computer vision to detect connected regions in binary digital images, although color images and data with higher dimensionality can also be processed.<ref name="Samet1988">{{cite journal|first1=H.|first2=M.|year=1988|title=Efficient Component Labeling of Images of Arbitrary Dimension Represented by Linear Bintrees|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=10|issue=4|pages=579|doi=10.1109/34.3918|last1=Samet|last2=Tamminen|s2cid=15911227 }}</ref><ref name="Michael1992">{{Cite journal|author1=Michael B. Dillencourt |author2=Hannan Samet |author3=Markku Tamminen |year=1992 |title=A general approach to connected-component labeling for arbitrary image representations |journal=Journal of the ACM |volume=39 |issue=2 |pages=253 |doi=10.1145/128749.128750 |citeseerx=10.1.1.73.8846 |s2cid=1869184 }}</ref> When integrated into an image recognition system or human-computer interaction interface, connected component labeling can operate on a variety of information.<ref name="Weijie2006">{{cite journal |author1=Weijie Chen |author2=Maryellen L. Giger |author3=Ulrich Bick |year=2006 |title=A Fuzzy C-Means (FCM)-Based Approach for Computerized Segmentation of Breast Lesions in Dynamic Contrast-Enhanced MR Images |doi=10.1016/j.acra.2005.08.035 |pmid=16399033 |volume=13 |issue=1 |pages=63–72 |journal=Academic Radiology }}</ref><ref name="Kesheng2003">{{cite web |author1=Kesheng Wu |author2=Wendy Koegler |author3=Jacqueline Chen |author4=Arie Shoshani |year=2003 |title=Using Bitmap Index for Interactive Exploration of Large part Datasets |publisher=SSDBM |url=http://csdl.computer.org/comp/proceedings/ssdbm/2003/1964/00/19640065abs.htm }}</ref> Blob extraction is generally performed on the resulting binary image from a thresholding step, but it can be applicable to gray-scale and color images as well. Blobs may be counted, filtered, and tracked.
Blob extraction is related to but distinct from blob detection.
==Overview== thumb|100px|right|4-connectivity thumb|100px|right|8-connectivity 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 neighborhood or 8-connected neighborhood.<ref name="Fisher2003">{{cite web |author1=R. Fisher |author2=S. Perkins |author3=A. Walker |author4=E. Wolfart |year=2003 |title=Connected Component Labeling |url=http://homepages.inf.ed.ac.uk/rbf/HIPR2/label.htm }}</ref>
Following the labeling stage, the graph may be partitioned into subsets, after which the original information can be recovered and processed .
== Definition == The usage of the term connected-components labeling (CCL) and its definition is quite consistent in the academic literature, whereas connected-components analysis (CCA) varies in terms of both terminology and problem definition.
Rosenfeld et al.<ref>{{Cite journal|last1=Rosenfeld|first1=Azriel|last2=Pfaltz|first2=John L.|date=October 1966|title=Sequential Operations in Digital Picture Processing|journal=J. ACM|volume=13|issue=4|pages=471–494|doi=10.1145/321356.321357|s2cid=7391071 |issn=0004-5411}}</ref> define connected components labeling as the “[c]reation of a labeled image in which the positions associated with the same connected component of the binary input image have a unique label.” Shapiro et al.<ref name=":1">{{Cite book|chapter=Connected Component Labeling and Adjacency Graph Construction|last=Shapiro|first=Linda G.|author-link=Linda Shapiro|pages=1–30|doi=10.1016/s0923-0459(96)80011-5|title = Topological Algorithms for Digital Image Processing|volume = 19|series = Machine Intelligence and Pattern Recognition|year = 1996|isbn = 9780444897541}}</ref> define CCL as an operator whose “input is a binary image and [...] output is a symbolic image in which the label assigned to each pixel is an integer uniquely identifying the connected component to which that pixel belongs.”<ref name=":0">{{Cite book|title=A Parallel and Resource-Efficient Single Lookup Connected Components Analysis Architecture for Reconfigurable Hardware|last=Klaiber|first=Michael J.|publisher=University of Stuttgart|year=2016}}</ref>
There is no consensus on the definition of CCA in the academic literature. It is often used interchangeably with CCL.<ref name=":2">{{Cite book|last1=Fu|first1=Y.|last2=Chen|first2=X.|last3=Gao|first3=H.|title=2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing |chapter=A New Connected Component Analysis Algorithm Based on Max-Tree |date=December 2009|pages=843–844|doi=10.1109/DASC.2009.150|isbn=978-1-4244-5420-4|s2cid=6805048 }}</ref><ref name=":3">{{Cite book|last1=Grana|first1=C.|last2=Borghesani|first2=D.|last3=Santinelli|first3=P.|last4=Cucchiara|first4=R.|title=2010 Workshops on Database and Expert Systems Applications |chapter=High Performance Connected Components Labeling on FPGA |date=August 2010|pages=221–225|doi=10.1109/DEXA.2010.57|isbn=978-1-4244-8049-4|s2cid=6905027 }}</ref> A more extensive definition is given by Shapiro et al.:<ref name=":1" /> “Connected component analysis consists of connected component labeling of the black pixels followed by property measurement of the component regions and decision making.” The definition for connected-component analysis presented here is more general, taking the thoughts expressed in <ref name=":1" /><ref name=":2" /><ref name=":3" /> into account.
==Algorithms== The algorithms discussed can be generalised to arbitrary dimensions, albeit with increased time and space complexity.
===One component at a time=== This is a fast and very simple method to implement and understand. It is based on graph traversal methods in graph theory. In short, once the first pixel of a connected component is found, all the connected pixels of that connected component are labelled before going onto the next pixel in the image. This algorithm is part of Vincent and Soille's watershed segmentation algorithm,<ref>{{cite journal|last1=Vincent|first1=Luc|last2=Soille|first2=Pierre|title=Watersheds in digital spaces: an efficient algorithm based on immersion simulations|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|date=June 1991|volume=13|issue=6|page=583|doi=10.1109/34.87344|s2cid=15436061 }}</ref> other implementations also exist.<ref>{{cite book|last1=Abubaker|first1=A|last2=Qahwaji|first2=R|last3=Ipson|first3=S|last4=Saleh|first4=M|title=2007 IEEE International Conference on Signal Processing and Communications|chapter=One Scan Connected Component Labeling Technique|date=2007|page=1283|doi=10.1109/ICSPC.2007.4728561|isbn=978-1-4244-1235-8|s2cid=10710012}}</ref>
In order to do that a linked list is formed that will keep the indexes of the pixels that are connected to each other, steps (2) and (3) below. The method of defining the linked list specifies the use of a depth or a breadth first search. For this particular application, there is no difference which strategy to use. The simplest kind of a last in first out queue implemented as a singly linked list will result in a depth first search strategy.
It is assumed that the input image is a binary image, with pixels being either background or foreground and that the connected components in the foreground pixels are desired. The algorithm steps can be written as:
# Start from the first pixel in the image. Set current label to 1. Go to (2). # If this pixel is a foreground pixel and it is not already labelled, give it the current label and add it as the first element in a queue, then go to (3). If it is a background pixel or it was already labelled, then repeat (2) for the next pixel in the image. # Pop out an element from the queue, and look at its neighbours (based on any type of connectivity). If a neighbour is a foreground pixel and is not already labelled, give it the current label and add it to the queue. Repeat (3) until there are no more elements in the queue. # Go to (2) for the next pixel in the image and increment current label by 1.
Note that the pixels are labelled before being put into the queue. The queue will only keep a pixel to check its neighbours and add them to the queue if necessary. This algorithm only needs to check the neighbours of each foreground pixel once and doesn't check the neighbours of background pixels.
The pseudocode is: '''algorithm''' OneComponentAtATime(data) ''input'' : imageData[xDim][yDim] ''initialization'' : label = 0, labelArray[xDim][yDim] = 0, statusArray[xDim][yDim] = false, queue1, queue2; '''for''' i = 0 '''to''' xDim '''do''' '''for''' j = 0 '''to''' yDim '''do''' '''if''' imageData[i][j] has not been processed '''do''' '''if''' imageData[i][j] is a foreground pixel '''do''' check its four neighbors(north, south, east, west) : '''if''' neighbor is not processed '''do''' '''if''' neighbor is a foreground pixel '''do''' add it to queue1 '''else''' update its status to processed '''end if''' labelArray[i][j] = label (give label) statusArray[i][j] = true (update status) '''while''' queue1 is not empty '''do''' For each pixel in the queue do : check its four neighbors '''if''' neighbor is not processed '''do''' '''if''' neighbor is a foreground pixel '''do''' add it to queue2 '''else''' update its status to processed '''end if''' give it the current label update its status to processed remove the current element from queue1 copy queue2 into queue1 '''end While''' increase the label '''end if''' '''else''' update its status to processed '''end if''' '''end if''' '''end if''' '''end for''' '''end for'''
===Two-pass=== Relatively simple to implement and understand, the two-pass algorithm,<ref name="Shapiro2002">{{cite book |author1=Shapiro, L. |author2=Stockman, G. |year=2002 |title=Computer Vision | publisher=Prentice Hall | url=http://www.cse.msu.edu/~stockman/Book/2002/Chapters/ch3.pdf | pages=69–73}}</ref> (also known as the Hoshen–Kopelman algorithm) iterates through 2-dimensional binary data. The algorithm makes two passes over the image: the first pass to assign temporary labels and record equivalences, and the second pass to replace each temporary label by the smallest label of its equivalence class.
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.
'''Connectivity checks''' are carried out by checking neighbor pixels' labels (neighbor elements whose labels are not assigned yet are ignored), or say, the north-east, the north, the north-west and the west of the current pixel (assuming 8-connectivity). 4-connectivity uses only north and west neighbors of the current pixel. The following conditions are checked to determine the value of the label to be assigned to the current pixel (4-connectivity is assumed)
Conditions to check:
#Does the pixel to the left (west) have the same value as the current pixel? ##'''Yes''' – We are in the same region. Assign the same label to the current pixel ##'''No''' – Check next condition #Do both pixels to the north and west of the current pixel have the same value as the current pixel but not the same label? ##'''Yes''' – We know that the north and west pixels belong to the same region and must be merged. Assign the current pixel the minimum of the north and west labels, and record their equivalence relationship ##'''No''' – Check next condition #Does the pixel to the left (west) have a different value and the one to the north the same value as the current pixel? ##'''Yes''' – Assign the label of the north pixel to the current pixel ##'''No''' – Check next condition #Do the pixel's north and west neighbors have different pixel values than current pixel? ##'''Yes''' – Create a new label id and assign it to the current pixel
The algorithm continues this way, and creates new region labels whenever necessary. The key to a fast algorithm, however, is how this merging is done. This algorithm uses the union-find data structure which provides excellent performance for keeping track of equivalence relationships.<ref>Introduction to Algorithms, [https://books.google.com/books?id=NLngYyWFl_YC&q=introduction+to+algorithms], pp498</ref> Union-find essentially stores labels which correspond to the same blob in a disjoint-set data structure, making it easy to remember the equivalence of two labels by the use of an interface method E.g.: findSet(l). findSet(l) returns the minimum label value that is equivalent to the function argument 'l'.
Once the initial labeling and equivalence recording is completed, the second pass merely replaces each pixel label with its equivalent disjoint-set representative element.
A faster-scanning algorithm for connected-region extraction is presented below.<ref>{{cite journal|last=Lifeng He|author2=Yuyan Chao |author3=Suzuki, K. |title=A Run-Based Two-Scan Labeling Algorithm|journal=IEEE Transactions on Image Processing|date=1 May 2008|volume=17|issue=5|pages=749–756|doi=10.1109/TIP.2008.919369|pmid=18390379|bibcode=2008ITIP...17..749H }}</ref>
On the first pass: #Iterate through each element of the data by column, then by row (Raster Scanning) #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.
== Graphical example of two-pass algorithm == {{unreferenced section|date=June 2013}} 1. The array from which connected regions are to be extracted is given below (8-connectivity based).
We first assign different binary values to elements in the graph. The values "0~1" at the center of each of the elements in the following graph are the elements' values, whereas the "1,2,...,7" values in the next two graphs are the elements' labels. The two concepts should not be confused.
800px
2. After the first pass, the following labels are generated:
800px
A total of 7 labels are generated in accordance with the conditions highlighted above.
The label equivalence relationships generated are,
{| class="wikitable" |- ! '''Set ID''' ! '''Equivalent Labels''' |- | 1 | 1,2 |- | 2 | 1,2 |- | 3 | 3,4,5,6,7 |- | 4 | 3,4,5,6,7 |- | 5 | 3,4,5,6,7 |- | 6 | 3,4,5,6,7 |- | 7 | 3,4,5,6,7 |}
3. Array generated after the merging of labels is carried out. Here, the label value that was the smallest for a given region "floods" throughout the connected region and gives two distinct labels, and hence two distinct labels.
800px
4. Final result in color to clearly see two different regions that have been found in the array.
800px
thumb|right|Sample graphical output from running the two-pass algorithm on a binary image. The first image is unprocessed, while the last one has been recolored with label information. Darker hues indicate the neighbors of the pixel being processed.
The pseudocode is:
'''algorithm''' TwoPass(data) '''is''' linked = [] labels = structure with dimensions of data, initialized with the value of Background NextLabel = 0 ''First pass'' '''for''' row '''in''' data '''do''' '''for''' column '''in''' row '''do''' '''if''' data[row][column] '''is not''' Background '''then''' neighbors = connected elements with the current element's value '''if''' neighbors '''is''' empty '''then''' linked[NextLabel] = '''''set''''' containing NextLabel labels[row][column] = NextLabel NextLabel += 1 '''else''' ''Find the smallest label'' L = neighbors labels labels[row][column] = '''''min'''''(L) '''for''' label '''in''' L '''do''' linked[label] = '''''union'''''(linked[label], L) ''Second pass'' '''for''' row '''in''' data '''do''' '''for''' column '''in''' row '''do''' '''if''' data[row][column] '''is not''' Background '''then''' labels[row][column] = '''''find'''''(labels[row][column]) '''return''' labels
The ''find'' and ''union'' algorithms are implemented as described in union find.
=== Sequential algorithm === Create a region counter
Scan the image (in the following example, it is assumed that scanning is done from left to right and from top to bottom):
* For every pixel check the ''north'' and ''west'' pixel (when considering 4-connectivity) or the ''northeast'', ''north'', ''northwest'', and ''west'' pixel for 8-connectivity for a given region criterion (i.e. intensity value of 1 in binary image, or similar intensity to connected pixels in gray-scale image). * If none of the neighbors fit the criterion then assign to region value of the region counter. Increment region counter. * If only one neighbor fits the criterion assign pixel to that region. * If multiple neighbors match and are all members of the same region, assign pixel to their region. * If multiple neighbors match and are members of different regions, assign pixel to one of the regions (it doesn't matter which one). Indicate that all of these regions are equivalent. * Scan image again, assigning all equivalent regions the same region value.
==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.<ref name="Kenji2003">{{cite journal |author1=Kenji Suzuki |author2=Isao Horiba |author3=Noboru Sugie |year=2003 |title=Linear-time connected-component labeling based on sequential local operations |doi=10.1016/S1077-3142(02)00030-9 |journal=Computer Vision and Image Understanding |volume=89 |pages=1–23 }}</ref>
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.<ref name="Yujie1990">{{cite journal|author1=Yujie Han |author2=Robert A. Wagner |year=1990 |title=An efficient and fast parallel-connected component algorithm |journal=Journal of the ACM |volume=37 |issue=3 |pages=626 |doi=10.1145/79147.214077 |s2cid=17867876 |doi-access=free }}</ref>
The interest to the algorithm arises again with an extensive use of CUDA.
===Pseudocode for the one-component-at-a-time algorithm=== {{Unreferenced section|date=June 2014}}
Algorithm: #Connected-component matrix is initialized to size of image matrix. #A mark is initialized and incremented for every detected object in the image. #A counter is initialized to count the number of objects. #A row-major scan is started for the entire image. #If an object pixel is detected, then following steps are repeated while (Index !=0) ##Set the corresponding pixel to 0 in Image. ##A vector (Index) is updated with all the neighboring pixels of the currently set pixels. ##Unique pixels are retained and repeated pixels are removed. ##Set the pixels indicated by Index to mark in the connected-component matrix. #Increment the marker for another object in the image.
'''''One-Component-at-a-Time'''''(''image'') [M, N] := size(''image'') ''connected'' := zeros(M, N) ''mark'' := value ''difference'' := increment ''offsets'' := [-1; M; 1; -M] ''index'' := [] ''no_of_objects'' := 0 '''for''' i: '''1:M''' '''do''' '''for''' j: '''1:N''' '''do''' '''if''' (''image''(i, j) == 1) '''then''' ''no_of_objects'' := ''no_of_objects'' + 1 ''index'' := [((j-1) × M + i)] ''connected''(''index'') := ''mark'' '''while''' ~isempty(''index'') '''do''' ''image''(''index'') := 0 ''neighbors'' := bsxfun(@plus, ''index'', ''offsets'') ''neighbors'' := unique(''neighbors''(:)) ''index'' := ''neighbors''(find(''image''(''neighbors''))) ''connected''(''index'') := ''mark'' '''end while''' ''mark'' := ''mark'' + ''difference'' '''end if''' '''end for''' '''end for'''
The run time of the algorithm depends on the size of the image and the amount of foreground. The time complexity is comparable to the two pass algorithm if the foreground covers a significant part of the image. Otherwise the time complexity is lower. However, memory access is less structured than for the two-pass algorithm, which tends to increase the run time in practice.
==Performance evaluation== In the last two decades many novel approaches to connected-component labeling have been proposed, but almost none of them have been subjected to a comparative performance assessment using the same data set. YACCLAB <ref name="YACCLAB">{{cite conference|url=http://imagelab.ing.unimore.it/imagelab/pubblicazioni/2016-icpr-yacclab.pdf|title=YACCLAB - Yet Another Connected Components Labeling Benchmark|last1=Grana|first1=C.|last2=Bolelli|first2=F.|last3=Baraldi|first3=L.|last4=Vezzani|first4=R.|year=2016|book-title=23rd International Conference on Pattern Recognition|location=Cancún}}</ref><ref>{{Cite web | url=https://github.com/prittt/YACCLAB | title=Yet Another Connected Components Labeling Benchmark: Prittt/YACCLAB| website=GitHub| date=2019-02-18}}</ref> (acronym for Yet Another Connected Components Labeling Benchmark) is an example of C++ open source framework which collects, runs, and tests connected-component labeling algorithms.
==Hardware architectures== The emergence of FPGAs with enough capacity to perform complex image processing tasks also led to high-performance architectures for connected-component labeling.<ref>{{Cite book|last1=Bailey|first1=D. G.|last2=Johnston|first2=C. T.|last3=Ma|first3=Ni|title=2008 International Conference on Field Programmable Logic and Applications |chapter=Connected components analysis of streamed images |date=September 2008|pages=679–682|doi=10.1109/FPL.2008.4630038|isbn=978-1-4244-1960-9|s2cid=6503327 }}</ref><ref name="Kl13">{{cite journal |author1=M. J. Klaiber |author2=D. G. Bailey |author3=Y. Baroud |author4=S. Simon |year=2015 |title=A Resource-Efficient Hardware Architecture for Connected Components Analysis|journal=IEEE Transactions on Circuits and Systems for Video Technology |volume=26 |issue=7 |pages=1334–1349 |doi=10.1109/TCSVT.2015.2450371|s2cid=10464417 }}</ref> Most of these architectures utilize the single pass variant of this algorithm, because of the limited memory resources available on an FPGA. These types of connected component labeling architectures can process several image pixels in parallel, thereby achieving high throughput and low processing latency.
== See also == * Feature extraction * Flood fill
==References== {{Reflist}}
===General=== *{{cite book | last = Horn | first = Berthold K.P. | author-link = Berthold K.P. Horn | title = Robot Vision | publisher = MIT Press | year = 1986 | pages = [https://archive.org/details/robotvision0000horn/page/69 69–71] | isbn = 978-0-262-08159-7 | url = https://archive.org/details/robotvision0000horn/page/69 }}
*{{cite book | last = Al Bovik| title = HandBook for Image and Video processing | publisher = Academic Press | year = 2000 | pages = [37–70] | isbn = 0-12-119790-5 | url = https://preetikale.files.wordpress.com/2018/07/handbook-of-image-and-video-processing-al-bovik1.pdf }}
==External links== * [http://www.codeproject.com/Articles/336915/Connected-Component-Labeling-Algorithm Implementation in C#] * [https://drive.google.com/file/d/0B8gQ5d6E54ZDd3JiMURVU05HM2s/edit?usp=sharing about Extracting objects from image and Direct Connected Component Labeling Algorithm]
{{Authority control}}
Category:Computer vision