An optimal parallel algorithm for the Euclidean distance maps of binary images

The Euclidean distance map (EDM) of a black and white n×n binary image is the n×n map where each element has the Euclidean distance between the corresponding pixel and the nearest black pixel. The EDM plays an important role in machine vision, pattern recognition and robotics. Many algorithms have been proposed for computing the EDM. In recent years, O(n²) time sequential algorithms were presented for computing the EDM. Hirata and Kato (1994) showed that their algorithm can be parallelized to run in O(n²/p) time using p processors (1⩽p⩽n) on the EREW PRAM. We present a parallel algorithm for computing the EDM. The algorithm runs in O(log n) time using n²/log n processors on the EREW PRAM and in O(log n/log log n) time using n² log log n/log n processors on the common CRCW PRAM, respectively. The algorithm is optimal in the sense that the product of the time and the number of processors is equal to the lower bound of the sequential time for computing the EDM