Parallel Processing Letters · 1995 · 22 citations · 0 references
ComputingComputer ScienceComputer VisionParallel AlgorithmsParallel ComputingAlgorithm AnalysisData ParallelismDigital Image ProcessingImage ProcessingPattern RecognitionDistance TransformParallel Algorithm AnalysisParallel Algorithm Complexity
The Euclidean Distance Transform is an important computational tool for the processing of binary images, with applications in many areas such as computer vision, pattern recognition and robotics. We investigate the properties of this transform and describe an O(n 2 ) time optimal sequential algorithm. A deterministic EREW-PRAM parallel algorithm which runs in O( log n) time using O(n 2 ) processors and O(n 2 ) space is also derived. Further, a cost optimal randomized parallel algorithm which runs within the same time bounds with high probability, is given.