W1518641734
Pedro F. Felzenszwalb, Daniel P. Huttenlocher · Theory of Computing · 2012
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.
Cited by 800 works. doi:10.4086/toc.2012.v008a019 Open-access PDF
Authors
References
- Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
- A tutorial on hidden Markov models and selected applications in speech recognition
- Sequential Operations in Digital Picture Processing
- Dynamic Programming and Optimal Control
- Pictorial Structures for Object Recognition
- Comparing images using the Hausdorff distance
- Distance transformations in digital images
- Biological shape and visual science (part I)
- Hierarchical chamfer matching: a parametric edge matching algorithm
- Advances in Neural Information Processing Systems 27 (NIPS 2014)