TWO ALGORITHMS FOR COMPUTING THE EUCLIDEAN DISTANCE TRANSFORM
Marina L. Gavrilova, Muhammad H. Alsuwaiyel · International Journal of Image and Graphics · 2001
Given an n × n binary image of white and black pixels, we present two optimal algorithms for computing the distance transform and the nearest feature transform using the Euclidean metric. The first algorithm is a fast sequential algorithm that runs in linear time in the input size. The second is a parallel algorithm that runs in O(n2/p) time on a linear array of p processors, p, 1 ≤ p ≤ n.