AN EFFICIENT ALGORITHM FOR THE EUCLIDEAN DISTANCE TRANSFORMATION

Distance maps of binary images contain, for each pixel, the distance b etween that pixel and the pixel of value 0 closest to it. They are use ful for a variety of machine-vision applications. This paper presents a simple and efficient algorithm for computing the Euclidean distance maps. The algorithm runs in O(N-2) time for an N x N binary image, and it also works for other distances that appear in machine-vision appli cations, such as city black and chessboard. Its parallel version runs in O(N-2/p) time with p(1 less than or equal to p less than or equal t o N) processors.