In 2003 Mauer at al. 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 k-dimensional space, where distance is measured with respect to a metric from some class of metrics including Euclidean distance and, in general, Lp-metric distance for 1 ≤ p ≤ ∞ However, that algorithm contains an error which was transformed to its Euclidean metric ITK implementation of Tustison at al. In this paper we describe a corrected version of the algorithm for 1 < p < ∞ and prove that it indeed has the desired properties. We also discuss in details the error of the algorithm from the paper of Mauer at al. The revised version of the algorithm will be made available at ITK and as a part of CAVASS software system developed and maintained at MIPG.
Work in progress. See MIPG Technical Report #337.
Last modified April 9, 2007.