Computing the Component-Labeling and the Adjacency Tree of a Binary Digital Image in Near Logarithmic-Time

Abstract

Connected component labeling (CCL) of binary images is one of the fundamental operations in real time applications. The adjacency tree (AdjT) of the connected components offers a region-based representation where each node represents a region which is surrounded by another region of the opposite color. In this paper, a fully parallel algorithm for computing the CCL and AdjT of a binary digital image is described and implemented, without the need of using any geometric information. The time complexity order for an image of m × n pixels under the assumption that a processing element exists for each pixel is near O(log(m+ n)). Results for a multicore processor show a very good scalability until the so-called memory bandwidth bottleneck is reached. The inherent parallelism of our approach points to the direction that even better results will be obtained in other less classical computing architectures.