Linear time Euclidean distance transform algorithms
- 1 May 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 17 (5) , 529-533
- https://doi.org/10.1109/34.391389
Abstract
Two linear time (and hence asymptotically optimal) algorithms for computing the Euclidean distance transform of a two-dimensional binary image are presented. The algorithms are based on the construction and regular sampling of the Voronoi diagram whose sites consist of the unit (feature) pixels in the image. The first algorithm, which is of primarily theoretical interest, constructs the complete Voronoi diagram. The second, more practical, algorithm constructs the Voronoi diagram where it intersects the horizontal lines passing through the image pixel centers. Extensions to higher dimensional images and to other distance functions are also discussed.Keywords
This publication has 17 references indexed in Scilit:
- Distance transformations in digital imagesPublished by Elsevier ,2006
- Sequencing-by-hybridization revisited: the analog-spectrum proposalIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004
- A unified distance transform algorithm and architectureMachine Vision and Applications, 1992
- Distance functions in digital geometryInformation Sciences, 1987
- Computing Voronoi diagrams in digital picturesPattern Recognition Letters, 1986
- Distances defined by neighborhood sequencesPattern Recognition, 1986
- Distance transformations in arbitrary dimensionsComputer Vision, Graphics, and Image Processing, 1984
- Sequential Operations in Digital Picture ProcessingJournal of the ACM, 1966
- Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs.Journal für die reine und angewandte Mathematik (Crelles Journal), 1908
- Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen.Journal für die reine und angewandte Mathematik (Crelles Journal), 1850