Volume 8 (2012)
Article 19 pp. 415-428
Distance Transforms of Sampled Functions
Received: December 18, 2009
Revised: May 30, 2012
Published: September 2, 2012
Revised: May 30, 2012
Published: September 2, 2012
Keywords: distance transform, minimum convolution, image processing
Categories: short, algorithms, transform, distance transform, convolution, min-convolution, vision, image processing
ACM Classification: F.2.1, I.4
AMS Classification: 68T45, 68W40
Abstract: [Plain Text Version]
We describe linear-time algorithms for solving a class of problems that involve transforming a cost function on a grid using spatial information. These problems can be viewed as a generalization of classical distance transforms of binary images, where the binary image is replaced by an arbitrary function on a grid. Alternatively they can be viewed in terms of the minimum convolution of two functions, which is an important operation in grayscale morphology. A consequence of our techniques is a simple and fast method for computing the Euclidean distance transform of a binary image. Our algorithms are also applicable to Viterbi decoding, belief propagation, and optimal control.
Licensed under a Creative Commons Attribution License (CC-BY)