Felzenszwalb and Huttenlocher’s #PDF #paper DOI:10.4086/toc.2012.v008a019 on simple #algorithms for calculating the Euclidean #distance-transform of a pixmap: “Distance Transforms of Sampled Functions.”
Abstract: 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.
on 02026-01-12Steven #Wittens’s #SDF #fonts page where he implemented the Euclidean #Distance-Transform to avoid the #Mapbox #TinySDF wobbliness and pixelation problems. Apparently there’s a separable approach to this: “Like a Fourier Transform, you can apply it to 2D images by applying it horizontally on each row X, then vertically on each column Y (or vice versa).” ...really? Holy shit, you just count up with squared distances and everything works, that’s fucking insane. Then he figures out how to make it work with subpixel #antialiasing: “Here’s how I assembled a “true” Euclidean Subpixel Distance Transform.” #algorithms #toread
on 02026-01-12#video on Euclidean #distance-transform #algorithms #toread
on 02026-01-09