Parallel O(log(n)) Computation of the Adjacency of Connected Components

Abstract

Connected Component Labeling (CCL) is a fundamental task in pattern recognition and image processing algorithms. It groups the pixels into regions, such that adjacent pixels have the same label while pixels belonging to distinct regions have different labels. The common linear-time raster scan CCL techniques have a complexity of O(image- size) in a 2D binary image. To speed up the procedure of the CCL, the paper proposes a new irregular graph pyramid. To construct this pyramid, we use a new formalism [1] that introduces an order of the pixels in the base grid to detect the redundant edges through the hierarchical structure. These redundant edges, unlike the usual methods of constructing the irregular pyramid, are removed before contracting the edges. This not only simplifies the construction processes but may decrease memory consumption by approximately half. To perform the CCL task efficiently the proposed parallel algorithm reduces the complexity to O(log(n) ) where the n is the diameter of the largest connected component in the image. In addition, using an efficient combinatorial structure the topological properties of the connected components including adjacency of CCs, multi-boundaries and inclusions are preserved. Finally, the mathematical proofs provide fully parallel implementations and lead to efficient results in comparison with the state-of-the-art.