Fast computation of the 3-D Euclidean distance transform on the EREW PRAM model

In a two or three-dimensional image array, the computation of Euclidean distance transform (EDT) is an important task. With the increasing application of 3D voxel images, it is useful to consider the distance transform of a 3D digital image array. Because the EDT is a global operation, it is prohibitively time consuming when performing the EDT for image generation. In order to provide the efficient transform computations, parallelism is employed. In this paper we first derive several important geometry relations and properties among parallel planes. We then develop a parallel algorithm for the three-dimensional Euclidean distance transform (3D-EDT) on the EREW PRAM computation model. The time complexity of our parallel algorithm is O(log/sup 2/ N) for an N/spl times/N/spl times/N image array.