Parallel computation of the Euclidean distance transform on the mesh of trees and the hypercube computer

The distance transform is an operation that converts an image consisting of black and white pixels to an image where each pixel has a value or coordinate that represents the distance or location to the nearest black pixel. It is a basic operation in image processing and computer vision fields, used for expanding, shrinking, thinning, segmentation, clustering, computing shape, object reconstruction, etc. There are many approximate Euclidean distance transform algorithms in the literature, but finding the distance transform with respect to the Euclidean metric is rather time consuming. So, it is important to increase the computing speed. The parallel algorithms discussed are for the computation of exact Euclidean distance transform for all pixels with respect to black pixels in an N x N binary image. The object of this paper is to develop the time-optimal algorithms. O(log N) time-optimal algorithms are proposed for both mesh of trees and hypercube computer. The number of processors used to solve this problem for the former is N x N x N/log N and that for the latter is N-2.5, respectively. A generalized algorithm is also proposed for a reduced three-dimensional mesh of trees and it can be computed in O(m log N) time using N x N x N/m log N processors, where m is a constant and 1 less than or equal to m less than or equal to root N/log N. Compared to the previous result, the time complexity of the generalized algorithm is inversely proportional to the number of processors used by a factor of m times. (C) 1997 Academic Press.