Connected-component labeling
[1][2] When integrated into an image recognition system or human-computer interaction interface, connected component labeling can operate on a variety of information.
An algorithm traverses the graph, labeling the vertices based on the connectivity and relative values of their neighbors.
[5] Following the labeling stage, the graph may be partitioned into subsets, after which the original information can be recovered and processed .
The algorithms discussed can be generalized to arbitrary dimensions, albeit with increased time and space complexity.
[12] 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 simplest kind of a last in first out queue implemented as a singly linked list will result in a depth first search strategy.
This algorithm uses the union-find data structure which provides excellent performance for keeping track of equivalence relationships.
Multi-pass algorithms also exist, some of which run in linear time relative to the number of image pixels.
[16] 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.
The time complexity is comparable to the two pass algorithm if the foreground covers a significant part of the image.
However, memory access is less structured than for the two-pass algorithm, which tends to increase the run time in practice.
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.
The emergence of FPGAs with enough capacity to perform complex image processing tasks also led to high-performance architectures for connected-component labeling.
[20][21] Most of these architectures utilize the single pass variant of this algorithm, because of the limited memory resources available on an FPGA.
