A cost optimal parallel algorithm for weighted distance transforms

The distance transform and the nearest feature transform are useful operati ons in image processing. These transforms are based on various kinds of dis tance functions because the distance functions have different efficiency or usefulness. In this paper, we consider these transforms based on the weigh ted distance, which is a generalization of many distances, such as city blo ck, chessboard and chamfer distances. This paper presents a parallel algori thm for these transforms of an n x n binary image. The algorithm runs in O( log n) time using n(2)/log n processors on the EREW PRAM and in O(log log n ) time using n(2)/log log n processors on the common CRCW PRAM. The algorit hm also runs in O(n(2)/p(2) + n) time on a p x p mesh and in O(n(2)/p(2) (n log p)/p) time on a p(2) processor hypercube (for 1 less than or equal t o p less than or equal to n). From these complexities, the algorithm is cos t optimal on all models. Also we obtained an Omega(log n) lower bound for t he transform on the CREW PRAM. This implies that the algorithm is time opti mal on the EREW PRAM. (C) 1999 Elsevier Science B.V. All rights reserved.