Connected-component Labeling - Graphical Example of Two-pass Algorithm

Graphical Example of Two-pass Algorithm

1. The array from which connected regions are to be extracted is given below (8-connectivity based)

2. After the first pass, the following labels are generated. A total of 7 labels are generated in accordance with the conditions highlighted above.

The label equivalence relationships generated are,

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.

4. Final result in color to clearly see two different regions that have been found in the array.

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 is not Background neighbors = connected elements with the current element's value if neighbors is empty linked = set containing NextLabel labels = NextLabel NextLabel += 1 else Find the smallest label L = neighbors labels labels = min(L) for label in L linked = union(linked, L) Second pass for row in data for column in row if data is not Background labels = find(labels) return labels

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