Abstract
In this paper we prove an equivalence relation between the distance transform of a binary image, where the underlying distance is based on a positive definite quadratic form, and the erosion of its characteristic function by an elliptic poweroid structuring element. The algorithms devised by Shih and Mitchell [18] and Huang and Mitchell [7], for calculating the exact Euclidean distance transform (EDT) of a binary digital image manifested on a square grid, are particular cases of this result. The former algorithm uses erosion by a circular cone to calculate the EDT whilst the latter uses erosion by an elliptic paraboloid (which allows for pixel aspect ratio correction) to calculate the square of the EDT. Huang and Mitchell's algorithm [7] is arguably the better of the two because: (i) the structuring element can be decomposed into a sequence of dilations by 3 × 3 structuring elements (a similar decomposition is not possible for the circular cone) thus reducing the complexity of the erosion, and (ii) the algorithm only requires integer arithmetic (it produces squared distance). The algorithm is amenable to both hardware implementation using a pipeline architecture and efficient implementation on serial machines. Unfortunately the algorithm does not directly transpose to, nor has a corresponding analogue on, the hexagonal grid (the same is also true for Shih and Mitchell's algorithm [7]). In this paper, however, we show that if the hexagonal grid image is embedded in a rectangular grid then Huang and Mitchell's algorithm [7] can be applied, with aspect ratio correction, to obtain the exact EDT on the hexagonal grid.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G. Borgefors, “Distance transformations in digital images,” Computer Vision, Graphics, and Image Processing, Vol. 34, pp. 344–371, 1986.
Heinz Breu, Joseph Gil, David Kirkpatrick, and Michael Werman, “Linear time Euclidean distance transform algorithms,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, No. 5, pp. 529–533, 1995.
L. Chen and H.Y.H. Chuang, “A fast algorithm for Euclidean distance maps of a 2-d binary image,” Information Processing Letters, Vol. 51, pp. 25–29, 1994.
John D. DePree and Charles W. Swartz, Introduction to Real Analysis, John Wiley & Sons: New York, 1988.
Henk J.A.M. Heijmans, “Morphological image operators,” Advances in Electronics and Electron Physics, Academic Press: London, 1994.
Tomio Hirata, “A unified linear-time algorithm for computing distance maps,” Information Processing Letters, Vol. 58, pp. 129–133, 1996.
C. Tony Huang and O. Robert Mitchell, “A Euclidean distance transform using grayscale morphology decomposition,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 16, No. 4, pp. 443–448, 1994.
Richard A. Johnson and Dean W. Wichern, Applied Multivariate Statistical Analysis, 2nd edition, Prentice Hall International: London, 1988.
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.
Sandy Pavel and Selim G. Akl, “Efficient algorithms for the Euclidean distance transform,” Parallel Processing Letters, Vol. 5, No. 2, pp. 205–212, 1995.
F. Preteux and N. Merlet, “New concepts in mathematical morphology: the topographical and differential distance functions,” in Proceedings of the SPIE—The International Society for Optical Engineering, 1991, Vol. 1568, pp. 66–77.
A. Rosenfeld and J.L. Pfaltz, “Sequential operations in digital picture processing,” Journal of the ACM,Vol. 13, No. 4, pp. 471–494, 1966.
A. Rosenfeld and Avinash C. Kak, “Digital picture processing,” Computer Science and Applied Mathematics,Vol. 2, 2nd edition, Academic Press: New York, 1981.
J. Serra and B. Läy, “Square to hexagonal lattices conversion,” Signal Processing, Vol. 9, pp. 1–13, 1985.
J. Serra, Image Analysis and Mathematical Morphology, Academic Press: London, 1982.
J. Serra (Ed.), Image Analysis and Mathematical Morphology. Volume 2: Theoretical Advances, Academic Press: London, 1988.
Frank Yeong-Chyang Shih and Owen Robert Mitchell, “Decomposition of gray-scale morphological structuring elements,” Pattern Recognition, Vol. 24, No. 3, pp. 195–203, 1991.
Frank Yeong-Chyang Shih and Owen Robert Mitchell, “A mathematical morphology approach to Euclidean distance transformation,” IEEE Transactions on Image Processing, Vol. 1, No. 2, pp. 197–204, 1992.
Luc Vincent, “Exact Euclidean distance function by chain propagations,” in Proceedings 1991 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1991, pp. 520–525.
Luc Vincent, “New trends in morphological algorithms,” in Proceedings of the SPIE—The International Society for Optical Engineering, 1991, Vol. 1451, pp. 158–170.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mehnert, A.J., Jackway, P.T. On Computing the Exact Euclidean Distance Transform on Rectangular and Hexagonal Grids. Journal of Mathematical Imaging and Vision 11, 223–230 (1999). https://doi.org/10.1023/A:1008352402867
Issue Date:
DOI: https://doi.org/10.1023/A:1008352402867