IEEE Transactions on Parallel and Distributed Systems · 2003 · 22 citations · 27 references
ComputingComputer ScienceComputational GeometryParallel AlgorithmsParallel Computing3D Imaging3D ReconstructionData ParallelismParallel Computational GeometryParallel Geometric AlgorithmsThree-dimensional ReconstructionDigital Image AnalysisDistance TransformParallel Algorithm AnalysisParallel Algorithm ComplexityParallel Time ComplexityThree-dimensional Image Reconstruction
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.
27
Per‐Erik Danielsson · Computer Graphics and Image Processing · 1980 · 2K citations
Distance transformations in digital images
Gunilla Borgefors · Computer Vision Graphics and Image Processing · 1986 · 1.9K citations
A transformation for extracting new descriptors of shape
H.E. Blum · Medical Entomology and Zoology · 1967 · 1.7K citations
Sequential Operations in Digital Picture Processing
Azriel Rosenfeld, John L. Pfaltz · Journal of the ACM · 1966 · 1.6K citations
Distance functions on digital pictures
Amir Rosenfeld, John L. Pfaltz · Pattern Recognition · 1968 · 835 citations