loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
A List-Processing Approach to Compute Voronoi Diagrams and the Euclidean Distance Transform
July 1998 (vol. 20 no. 7)
pp. 757-761
ASCII Text
x 
 
Weiguang Guan, Songde Ma, "A List-Processing Approach to Compute Voronoi Diagrams and the Euclidean Distance Transform," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, no. 7, pp. 757-761, July, 1998.
 
 
BibTex
x
 
@article{ 10.1109/34.689306,
author = {Weiguang Guan and Songde Ma},
title = {A List-Processing Approach to Compute Voronoi Diagrams and the Euclidean Distance Transform},
journal ={IEEE Transactions on Pattern Analysis and Machine Intelligence},
volume = {20},
number = {7},
issn = {0162-8828},
year = {1998},
pages = {757-761},
doi = {http://doi.ieeecomputersociety.org/10.1109/34.689306},
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 - A List-Processing Approach to Compute Voronoi Diagrams and the Euclidean Distance Transform
IS - 7
SN - 0162-8828
SP757
EP761
EPD - 757-761
A1 - Weiguang Guan,
A1 - Songde Ma,
PY - 1998
KW - Voronoi transformation
KW - Voronoi diagram
KW - Euclidean distance
KW - distance transformation
KW - coherence.
VL - 20
JA - IEEE Transactions on Pattern Analysis and Machine Intelligence
ER -
 

Abstract—In this paper, we propose an efficient Voronoi transform algorithm for constructing Voronoi diagrams using segment lists of rows. A significant feature of the algorithm is that it takes segments rather than pixels as the basic units to represent and propagate the nearest neighbor information. The segment lists are dynamically updated as they are scanned. A distance map can then be easily computed from the segment list representation of the Voronoi diagram. Experimental results have demonstrated its high efficiency. Extension of the algorithm to higher dimensions is also discussed.

[1] A. Rosenfeld and J. Pfaltz, "Sequential Operations in Digital Picture Processing," J. ACM, vol. 13, no. 4, pp. 471-494, 1966.
[2] A. Rosenfeld and A. C. Kak, Digital Picture Processing, second ed. New York: Academic Press, 1978.
[3] U. Montanari, "A Method for Obtaining Skeletons Using a Quasi-Euclidean Distance," J. ACM, vol. 15, no. 4, pp. 600-624, 1968.
[4] I. Ragnemalm, "The Euclidean Distance Transform," Ph.D. Thesis, Linkoping University, Linkoping, Sweden, 1993, p. 276.
[5] L. Ji and J. Piper, "Fast Homotopy-Preserving Skeletons Using Mathematical Morphology," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, no. 6, pp. 653-664, June 1992.
[6] G. Borgefors, "Distance Transformations in Arbitrary Dimensions," Computer Vision, Graphics, and Image Processing, vol. 27, pp. 321-345, 1984.
[7] G. Borgefors, "Distance Transformations in Digital Images," Computer Vision, Graphics, and Image Processing, vol. 34, pp. 344-371, 1986.
[8] A.M. Vossepoel, "A Note on 'Distance Transformations in Digital Images,'" Computer Vision, Graphics, and Image Processing, vol. 43, pp. 88-97, 1988.
[9] P.E. Danielsson, "Euclidean Distance Mapping," Computer Graphics and Image Processing, vol. 14, pp. 227-248, 1980.
[10] F. Leymarie and M.D. Levine, "Fast Raster Scan Distance Propagation on the Discrete Rectangular Lattice," CVGIP: Image Understanding, vol. 55, no. 1, pp. 84-94, 1992.
[11] H. Yamada, "Complete Euclidean Distance Transformation by Parallel Operation," Proc. Seventh Int'l Conf. Pattern Recognition, pp. 69-71,Montreal, 1984.
[12] D.W. Paglieroni, "Distance Transforms," Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing, vol. 54, pp. 56-74, 1992.
[13] D.W. Paglieroni, "A Unified Distance Transform Algorithm and Architecture," Machine Vision and Applications, vol. 5. pp. 47-55, 1992.
[14] W. Guan and S. Ma, "A Fast Unified Distance Transform Approach," Chinese J. Computers, vol. 18, no. 8, pp. 626-635, 1995. (in Chinese)
[15] B.J.H. Verwer and P.W. Verbeek, S.T. Dekker, “An Efficient Uniform Cost Algorithm Applied to Distance Transforms,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, pp. 425-429, 1989.
[16] F.Y.-C. Shih and O.R. Mitchell, "A Mathematical Morphology Approach to Euclidean Distance Transformation," IEEE Trans. Image Processing, vol. 1, no. 2, pp. 197-204, 1992.
[17] M.N. Kolountzakis and K.N. Kutulakos, "Fast Computation of the Euclidean Distance Maps for Binary Images," Information Processing Letters, vol. 43, no. 4, pp. 181-184, 1992.
[18] H. Breu, J. Gil, D. Kirkpatrick, and M. Werman, “Linear time Euclidean Distance Transform Algorithms,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, pp. 529-533, 1995.
[19] C.L. Orbert, "Algorithms in 2D for Detection of Object Orientation Using Distance Transformations," doctoral thesis, Uppsala University, 1993.
[20] G.T. Herman, J. Zheng, C.A. Bucholtz, "Shape-Based Interpolation," IEEE Computer Graphics&Applications, May, 1992.

Index Terms:
Voronoi transformation, Voronoi diagram, Euclidean distance, distance transformation, coherence.
Citation:
Weiguang Guan, Songde Ma, "A List-Processing Approach to Compute Voronoi Diagrams and the Euclidean Distance Transform," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, no. 7, pp. 757-761, July 1998, doi:10.1109/34.689306
Usage of this product signifies your acceptance of the Terms of Use.