27 March 2009 Linear time algorithms for exact distance transform: elaboration on Maurer et al. algorithm
Author Affiliations +
Proceedings Volume 7259, Medical Imaging 2009: Image Processing; 72592T (2009) https://doi.org/10.1117/12.811010
Event: SPIE Medical Imaging, 2009, Lake Buena Vista (Orlando Area), Florida, United States
Abstract
In 2003, Maurer at al. [7] published a paper describing an algorithm that computes the exact distance transform in a linear time (with respect to image size) for the rectangular binary images in the k-dimensional space Rk and distance measured with respect to Lp-metric for 1 ≤ p ≤ ∞, which includes Euclidean distance L2. In this paper we discuss this algorithm from theoretical and practical points of view. On the practical side, we concentrate on its Euclidean distance version, discuss the possible ways of implementing it as signed distance transform, and experimentally compare implemented algorithms. We also describe the parallelization of these algorithms and the computation time savings associated with such an implementation. The discussed implementations will be made available as a part of the CAVASS software system developed and maintained in our group [5]. On the theoretical side, we prove that our version of the signed distance transform algorithm, GBDT, returns, in a linear time, the exact value of the distance from the geometrically defined object boundary. We notice that, actually, the precise form of the algorithm from [7] is not well defined for L1 and L∞ metrics and point to our complete proof (not given in [7]) that all these algorithms work correctly for the Lp-metric with 1 < p < ∞.
© (2009) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Krzysztof Chris Ciesielski, Jayaram K. Udupa, Xinjian Chen, George J. Grevera, "Linear time algorithms for exact distance transform: elaboration on Maurer et al. algorithm", Proc. SPIE 7259, Medical Imaging 2009: Image Processing, 72592T (27 March 2009); doi: 10.1117/12.811010; https://doi.org/10.1117/12.811010
PROCEEDINGS
9 PAGES


SHARE
RELATED CONTENT

Making 3D binary digital images well-composed
Proceedings of SPIE (January 17 2005)
Fast approximate surface evolution in arbitrary dimension
Proceedings of SPIE (March 11 2008)
Semiautomatic 4D analysis of cardiac image sequences
Proceedings of SPIE (April 08 1996)
Perceptual Grouping Of Dot Patterns
Proceedings of SPIE (August 21 1987)
TBIdoc 3D content based CT image retrieval system for...
Proceedings of SPIE (March 09 2010)

Back to Top