A simple and efficient connected components labeling algorithm

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.