For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Parallel Algorithms for Higher-Dimensional Euclidean Distance Transforms with Applications
Yuh-Rau WANG Shi-Jinn HORNG Yu-Hua LEE Pei-Zong LEE
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/09/01
Print ISSN: 0916-8532
Type of Manuscript: INVITED PAPER (Special Issue on Parallel and Distributed Computing, Applications and Technologies)
Category: Algorithms and Applications
Euclidean distance transform, parallel algorithm, Voronoi diagram, proximate point, EREW PRAM, CRCW PRAM, medial axis transform,
Full Text: PDF>>
Based on the dimensionality reduction technique and the solution for proximate points problem, we achieve the optimality of the three-dimensional Euclidean distance transform (3D_EDT) computation. For an N N N binary image, our algorithms for both 3D_EDT and its applications can be performed in O (log log N) time using CRCW processors or in O (log N) time using EREW processors. To the best of our knowledge, all results described above are the best known. As for the n-dimensional Euclidean distance transform (nD_EDT) and its applications of a binary image of size Nn, all of them can be computed in O (nlog log N) time using CRCW processors or in O (nlog N) time using EREW processors.