Distance Transform in Parallel Logarithmic Complexity

Abstract

Nowadays a huge amount of digital data are generated every moment in a broad spectrum of application domains such as biomedical imaging, document processing, geosciences, remote sensing, video surveillance, etc. Processing such big data requires an efficient data structure, encouraging the algorithms with lower complexity and parallel operations. In this paper, first, a new method for computing the distance transform (DT) as the fundamental operation in binary images is presented. The method computes the DT with the parallel logarithmic complexity O(log(n)) where n is the maximum diameter of the largest foreground region in the 2D binary image. Second, we define the DT in the combinatorial map (CM) structure. In the CM, by replacing each edge with two darts a smoother DT with the double resolution is derived. Moreover, we compute n different distances for the nD-map. Both methods use the hierarchical irregular pyramid structure and have the advantage of preserving topological information between regions. The operations of the proposed algorithms are totally local and lead to parallel implementations. The GPU implementation of the algorithm has high performance while the bottleneck is the bandwidth of the memory or equivalently the number of available independent processing elements. Finally, the logarithmic complexity of the algorithm speeds up the execution and suits it. particularly for large images.