EFFICIENT ALGORITHMS FOR THE EUCLIDEAN DISTANCE TRANSFORM

1 June 1995

journal article
Published by World Scientific Pub Co Pte Ltd in Parallel Processing Letters

Vol. 5 (2) , 205-212
https://doi.org/10.1142/s0129626495000187

Abstract

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²) time optimal sequential algorithm. A deterministic EREW-PRAM parallel algorithm which runs in O( log n) time using O(n²) processors and O(n²) space is also derived. Further, a cost optimal randomized parallel algorithm which runs within the same time bounds with high probability, is given.

Keywords

ALGORITHM
ROBOTICS
OPTIMAL
EUCLIDEAN DISTANCE
DETERMINISTIC
PROCESSORS
DISTANCE TRANSFORM
EREW

This publication has 0 references indexed in Scilit: