Linear time algorithms for exact distance transform: elaboration on Maurer et al. algorithm

Krzysztof Chris Ciesielski; Jayaram K. Udupa; Xinjian Chen; George J. Grevera

doi:10.1117/12.811010

27 March 2009 Linear time algorithms for exact distance transform: elaboration on Maurer et al. algorithm

Krzysztof Chris Ciesielski, Jayaram K. Udupa, Xinjian Chen, George J. Grevera

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 L_p-metric for 1 ≤ p ≤ ∞, which includes Euclidean distance L₂. 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 L₁ 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 < ∞.

Citation Download Citation

Krzysztof Chris Ciesielski, Jayaram K. Udupa, Xinjian Chen, and 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); https://doi.org/10.1117/12.811010

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available