Distance Transforms of Sampled Functions

By Pedro F. Felzenszwalb, Dan Huttenlocher. 2012

869 citations recorded by the source corpus.

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.

Subfields: Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

Deformable part models are convolutional neural networks (2014, background): “Here we show that distance transforms of sampled functions [9] generalize max pooling.”
Do Convnets Learn Correspondence? (2014, methodology): “Message passing is performed efficiently using the squared Euclidean distance transform [30].”
Automatic salient object segmentation based on context and shape prior (2011, methodology): “where d(p) is the spatial distance between pixel p and optimal closed contour C∗, computed by using a distance transform [10], as shown in Fig.”
EGO-Planner: An ESDF-Free Gradient-Based Local Planner for Quadrotors (2020, neutral): “As detailed in Section II, methods can be categorized as the incremental global updating [3] ones, and the batch local calculation [4] ones.”
NASA: Neural Articulated Shape Approximation (2019, background): “The time complexity of computing SDF from an occupancy O that is discretized on a grid is linear in the number of voxels [16].”
Fast directional chamfer matching (2010, methodology): “The distance transform can be computed in two passes over the image [6] and using which the cost function (1) can be evaluated in linear time O(n) via dCM (U, V ) = 1 n ∑ ui∈U DTV (ui).”
Beat the MTurkers: Automatic Image Labeling from Weak 3D Supervision (2014, methodology): “We perform the signed distance transform [7] on the contour (the sign is negative within the car contour), and normalize it to be between−1 and 1 for every example in order to not bias large cars.”
RAPTOR: Robust and Perception-Aware Trajectory Replanning for Quadrotor Fast Flight (2020, methodology): “An ESDF is derived from the occupancy grid map using an efﬁcient distance transform algorithm [47] to support the gradient-based optimization (Sect.”
Reducing the Hausdorff Distance in Medical Image Segmentation With Convolutional Neural Networks (2019, methodology): “In this work, we used the algorithm proposed in [37] for computing DT in 2D and the algorithm in [38] for experiments with 3D images.”
Robust and Efficient Quadrotor Trajectory Generation for Fast Autonomous Flight (2019, methodology): “We maintain an EDF of the voxel grid map for our optimization, which is computed by an efﬁcient O ( n ) algorithm [21], where n = N 3 is the number of updated voxel grids.”
Capturing Hands in Action Using Discriminative Salient Points and Physics Simulation (2015, background): “Correspondences are again established by searching for the closest points, but now in the depth image using a 2D distance transform (Felzenszwalb and Huttenlocher 2004).”
Deep learning to achieve clinically applicable segmentation of head and neck anatomy for radiotherapy (2018, methodology): “d and background neighbours. These surface images are created for the masks M 1 and M 2. Additionally we create a distance map from each of these surface images using the distance transform algorithm [53]. Iterating over the non-zero elements in the ﬁrst surface image and looking up the distance fro”
Access to Unlabeled Data can Speed up Prediction Time (2011, background): “The second hypothesis class, denoted H , is a kernelbased linear predictor with the kernel function being a Chamfer distance between images (Barrow et al., 1977; Felzenszwalb & Huttenlocher, 2004; Gavrila, 2007).”
Scene recognition and weakly supervised object localization with deformable part-based models (2011, background): “To do this efficiently, the code of [6] relies on dynamic programming and generalized distance transforms [7, 8].”
DART: Dense Articulated Real-Time Tracking (2014, neutral): “The extension to multiple objects is straightforward.”
Learning person-object interactions for action recognition in still images (2011, methodology): “We do this efficiently in linear time with respect to p using distance transform [18].”