FAST BLOCK-BASED ALGORITHMS FOR CONNECTED COMPONENTS LABELING

Block-based algorithms are considered the fastest approach to label connected components in binary images. However, the existing algorithms are not able to find a specific connected component without scanning the entire labeled image. For this purpose, a one-and-half-scan algorithm performs better. Here, we proposed a new mask that enables the design of a block-based one-and-a-half-scan algorithm. Furthermore, three new efficient algorithms for connected components labeling are presented: a block-based two-scan, a pixel-based and a block-based one-and-a-half-scan. We conducted experiments using synthetic and realistic images to evaluate the performance of the proposed methods compared to the existing methods. The proposed block-based one-and-a-half-scan algorithm presents the best performance in the realistic images dataset composed of 1290 documents. Our block-based two-scan algorithm proved to be the fastest in the synthetic dataset, especially in low density images.