Pyramidal Connected Component Labeling by Irregular Graph Pyramid

Abstract

This paper presents a new logarithmic-time algorithm which simultaneously assigns labels to all connected components of a binary image in parallel. The irregular graph pyramid of an input binary image is constructed based on the optimized combinatorial structure. The novel small built pyramid has only three levels and is created at worst case with O(log(N 2 )) complexity for a N×N-sized (2D) binary image. To assign a label to each connected component, instead of the common linear-time raster scan techniques (with complexity O(N 2 )), only two important movements, namely bottom-up and top-down traversing, are needed. First, in the bottom-up traversing, the redundant connections are removed and the contraction kernels are contracted. This results in a simpler graph at top of the pyramid each of its vertices has a unique label identifying corresponding connected component. Such reduced graph preserves all connecting relations including inclusions. Second, in the top-down traversing, each unique label propagates down into each individual corresponding pixel at the base level. The complexity of the labeling propagation procedure in worst cases is O (log(image - size)). The GPU implementation of the algorithm has high performance and the bottleneck is the bandwidth of the memory or equivalently the number of available independent processing elements. Finally, the experimental results show the proposed algorithm outperforms the other state-of-the-art methods.