Fast and exact signed Euclidean distance transformation with linear complexity
- 1 January 1999
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 6 (15206149) , 3293-3296 vol.6
- https://doi.org/10.1109/icassp.1999.757545
Abstract
We propose a new signed or unsigned Euclidean distance transformation algorithm, based on the local corrections of the well-known 4SED algorithm of Danielsson (1980). Those corrections are only applied to a small neighborhood of a small subset of pixels from the image, which keeps the cost of the operation low. In contrast with all fast algorithms previously published, our algorithm produces perfect Euclidean distance maps in a time linearly proportional to the number of pixels in the image. The computational cost is close to the cost of the 4SSED approximation.Keywords
This publication has 20 references indexed in Scilit:
- Applications of the region growing Euclidean distance transform: anisotropy and skeletonsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Two Fast Euclidean Distance Transformations in Z2Based on Sufficient PropagationComputer Vision and Image Understanding, 1998
- Linear time Euclidean distance transform algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1995
- New algorithms for euclidean distance transformation of an n-dimensional digitized picture with applicationsPattern Recognition, 1994
- A Euclidean distance transform using grayscale morphology decompositionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1994
- The vector distance transform in two and three dimensionsCVGIP: Graphical Models and Image Processing, 1992
- Neighborhoods for distance transformations using ordered propagationCVGIP: Image Understanding, 1992
- A mathematical morphology approach to Euclidean distance transformationIEEE Transactions on Image Processing, 1992
- Fast erosion and dilation by contour processing and thresholding of distance mapsPattern Recognition Letters, 1992
- Distance transforms: Properties and machine vision applicationsCVGIP: Graphical Models and Image Processing, 1992