loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Linear Time Euclidean Distance Algorithms
May 1995 (vol. 17 no. 5)
pp. 529-533
ASCII Text
x 
 
Heinz Breu, Joseph Gil, David Kirkpatrick, Michael Werman, "Linear Time Euclidean Distance Algorithms," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no. 5, pp. 529-533, May, 1995.
 
 
BibTex
x
 
@article{ 10.1109/34.391389,
author = {Heinz Breu and Joseph Gil and David Kirkpatrick and Michael Werman},
title = {Linear Time Euclidean Distance Algorithms},
journal ={IEEE Transactions on Pattern Analysis and Machine Intelligence},
volume = {17},
number = {5},
issn = {0162-8828},
year = {1995},
pages = {529-533},
doi = {http://doi.ieeecomputersociety.org/10.1109/34.391389},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Pattern Analysis and Machine Intelligence
TI - Linear Time Euclidean Distance Algorithms
IS - 5
SN - 0162-8828
SP529
EP533
EPD - 529-533
A1 - Heinz Breu,
A1 - Joseph Gil,
A1 - David Kirkpatrick,
A1 - Michael Werman,
PY - 1995
KW - Distance transform
KW - Voronoi diagram
KW - algorithm
KW - Euclidean distance.
VL - 17
JA - IEEE Transactions on Pattern Analysis and Machine Intelligence
ER -
 

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.

[1] N. Ahuja,“Dot pattern processing using Voronoi polygons as neighborhoods,” Proc. Fifth Int’l Conf. Pattern Recogition, pp. 1122-1127,Miami Beach, 1980.[2] C. Arcelli and G. Sanniti de Baja,“Computing Voronoi diagrams in digital pictures,” Pattern Recognition Letters, pp. 383-389, 1986.[3] G. Borgefors,“Distance transformations in arbitrary dimensions,” Computer Vision, Graphics, and Image Processing, vol. 27, pp. 321-345, 1984.[4] G. Borgefors, “Distance Transforms in Digital Images,” Computer Vision, Graphics, and Image Processing, vol. 34, pp. 344-371, 1986.[5] G. Borgefors,“A new distance transformation approximating the Euclidean distance,” Proc. Int’l Joint Conf. Pattern Recognition, pp. 336-338, 1986.[6] K.L. Clarkson,“Approximation algorithms for shortest path motion planning.” Proc. 19th Ann. ACM Symp. Theory Computers, pp. 56-65, 1987.[7] P.E. Danielsson,“Euclidian distance mapping,” Computer Graphics and Image Processor, vol. 14, pp. 227-248, 1980.[8] P.P. Das and P.P. Chakrabarti,“Distance functions in digital geometry,” Information Sciences, vol. 42, pp. 113-136, 1987.[9] G.L. Dirichlet,“Über die Reduktion der positiven quadratischen Formen mitdrei unbestimmten ganzen Zahlen,” J. Reine Angew. Math., vol. 40, pp. 209-227, 1850.[10] J. Fairfield,“Segmenting dot patterns by Voronoi diagram concavity,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 32, pp. 104-110, 1983.[11] F. Klein and O. Kübler,“Euclidean distance transformation and model-guided image interpretation,” Pattern Recognition Letters, vol. 5, pp. 19-29, 1987.[12] M.N. Kolountzakis and K.N. Kutulakos,“Fast computationion of the Euclidean distance map for binary images,” Information Processing Letters, vol. 43, pp. 181-184, 1992.[13] D.W. Pagliero,“Distance transforms,” Computer Vision, Graphics, and Image Processing: Graphical models and Image Processing, vol. 54, pp. 56-74, 1992.[14] D.W. Paglieroni,“A unified distance transform algorithm and architecture,” Machine Vision and Applications, vol. 5, pp. 47-55, 1992.[15] F.P. Preparata and M.I. Shamos, Computational Geometry. Springer-Verlag, 1985.[16] I. Ragnemalm,“Neighborhoods for distance transformations using ordered propagation,” Computer Vision, Graphics, and Image Processing: Image Understanding, vol. 56, pp. 399-409, 1992.[17] A. Rosenfeld and A.C. Kak,Digital Picture Processing. Academic Press, 2nd ed., 1982[18] A. Rosenfeld and J. Pfaltz,“Sequential operations in digital picture processing,” J. ACM, vol. 13, pp. 471-494, 1966.[19] A. Rosenfeld and J. Pfaltz,“Distance functions on digital pictures,” Pattern Recognition, vol. 1, pp. 33-61, 1968.[20] M.G. Voronoi,“Nouvelles applications des parametres continusála theorie des formes quadratiques,” J. Reine Angew. Math., vol. 134, pp. 198-287, 1908.[21] H. Yamada,“Complete Euclidean distance transformation by parallel operation.” Proc. Seventh Int’l Conf. Pattern Recognition, pp. 69-71,Montreal, 1984.[22] M. Yamashita and T. Ibaraki,“Distances defined by neighborhood sequences,” Pattern Recognition, vol. 19, pp. 237-246, 1986.

Index Terms:
Distance transform, Voronoi diagram, algorithm, Euclidean distance.
Citation:
Heinz Breu, Joseph Gil, David Kirkpatrick, Michael Werman, "Linear Time Euclidean Distance Algorithms," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no. 5, pp. 529-533, May 1995, doi:10.1109/34.391389
Usage of this product signifies your acceptance of the Terms of Use.