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 computation is a global operation, it is prohibitively time consuming when performing the EDT for image processing. In order to provide the efficient transform computations, parallelism is employed. 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 and this is currently the best known result. A generalized parallel algorithm for the 3D-EDT is also proposed. We implement the proposed algorithms sequentially, the performance of which exceeds the existing algorithms (proposed by Yamada, 1984). Finally, we develop the corresponding parallel programs on both the emulated EREW PRAM model computer and the IBM SP2 to verify the speed-up properties of the proposed algorithms.

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.

In this paper, based on the diagonal propagation approach, we first provide an O(N/sup 2/) time sequential algorithm to compute the chessboard distance transform (CDT) of an N/spl times/N image, which is a DT using the chessboard distance metrics. Based on the proposed sequential algorithm, the CDT of a 2-D binary image array of size N/spl times/N can be computed in O (log N) time on the EREW PRAM model using O(N/sup 2//log N) processors, O(log N/log log N) time on the CRCW PRAM model using O(N/sup 2/log log N/log N) processors and O(log N) time on the hypercube computer using O(N/sup 2/) processors. Following the mapping as proposed by Y.H. Lee and S.J. Horng (1995), the algorithm for the MAT is also efficiently derived. The medial axis transform of a 2-D binary image array of size N/spl times/N can be computed in O(log N) time on the EREW PRAM model using O(N/sup 2//log N) processors, O(log N/log log N) time on the CRCW PRAM model using O(N/sup 2/log log N/log N) processors, and O(log N) time on the hypercube computer using O(N/sup 2/) processors. Our algorithms are faster than the best previous results as proposed by J.F. Jenq and S. Sahni (1992).