Title :
A simple and efficient connected components labeling algorithm
Author :
Di Stefano, Luigi ; Bulgarelli, Andrea
Author_Institution :
Dipt. di Elettronica Inf. e Sistemistica, Bologna Univ., Italy
Abstract :
We describe a two-scan algorithm for labeling connected components in binary images in raster format. Unlike the classical two-scan approach, our algorithm processes equivalences during the first scan by merging equivalence classes as soon as a new equivalence is found. We show that this significantly improves the efficiency of the labeling process with respect to the classical approach. The data structure used to support the handling of equivalences is a 1D-array. This renders the more frequent operation of finding class identifiers very fast, while the less-frequent class-merging operation has a relatively high computational cost. Nonetheless, it is possible to reduce significantly the merging cost by two slight modifications to the algorithm´s basic structure. The idea of merging equivalence classes is present also in Samet´s general labeling algorithm. However when considering the case of binary images in raster format this algorithm is much more complex than the one we describe in this paper
Keywords :
computer vision; data structures; equivalence classes; 1D-array data structure; binary images; computational cost; connected component labeling; equivalence classes; merging; raster format; two-scan algorithm; Computational efficiency; Computer vision; Costs; Data structures; Electronic switching systems; Identity-based encryption; Image analysis; Labeling; Merging;
Conference_Titel :
Image Analysis and Processing, 1999. Proceedings. International Conference on
Conference_Location :
Venice
Print_ISBN :
0-7695-0040-4
DOI :
10.1109/ICIAP.1999.797615