Linear time Euclidean distance transform algorithms
Heinz Breu, J. Gil, David G. Kirkpatrick et al. · IEEE Transactions on Pattern Analysis and Machine Intelligence · 1995
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.>
Cited by 454 works. doi:10.1109/34.391389
Authors
References
- Sequential Operations in Digital Picture Processing
- Computational geometry. an introduction
- Distance functions on digital pictures
- Distance transformations in digital images
- Euclidean distance mapping
- Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs.
- Distance transformations in arbitrary dimensions
- Sequencing-by-hybridization revisited: the analog-spectrum proposal
- Distance transforms: Properties and machine vision applications
- Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen.