IEEE Transactions on Parallel and Distributed Systems · 2003 · 16 citations · 24 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismGeometry ProcessingParallel Computational GeometryParallel Geometric AlgorithmsParallel Performance AnalysisVoronoi DiagramsDistance TransformParallel Algorithm AnalysisParallel Algorithm ComplexityParallel Voronoi Diagram ConstructionVoronoi Diagram ComplexityVoronoi Diagram Construction AlgorithmsVoronoi Diagrams On Polyhedral SurfacesVoronoi Polygons
We develop a parallel algorithm for the 2D Euclidean distance transform (2D/spl I.bar/EDT, for short) of a binary image of size N /spl times/ N in O(1) time using N/sup 2+/spl delta/+/spl epsi// CRCW processors and a parallel algorithm for the 3D Euclidean distance transform (3D/spl I.bar/EDT, for short) of a binary image of size N /spl times/ N /spl times/ N in O(1) time using N/sup 3+/spl delta/+/spl epsi// CRCW processors, where /spl delta/=1/, /spl epsi/=1/(2/sup c+1/-1), h, and are constants and positive integers. Our 2D/spl I.bar/EDT (3D/spl I.bar/EDT) parallel algorithm can be used to build up Voronoi diagram and Voronoi polygons (polyhedra) in a 2D (3D) binary image also. All of these parallel algorithms can be performed in O(1) time using N/sup 2+/spl delta/+/spl epsi// (N/sup 3+/spl delta/+/spl epsi//) CRCW processors. To the best of our knowledge, all results derived above are the best O(1) time algorithms known.
24
Per‐Erik Danielsson · Computer Graphics and Image Processing · 1980 · 2K 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