distancetransform

Distance transform is a foundational image processing operation that assigns to every pixel a value representing its distance to the nearest feature pixel, according to a chosen distance metric. In binary images, a common convention is to compute, for each foreground pixel, the distance to the nearest background (zero-valued) pixel. The resulting distance map is used to quantify proximity to boundaries, locate centers of shapes, and support further analysis such as segmentation and skeletonization. Some formulations also compute the distance from background pixels to the nearest foreground pixel, depending on the application.

Metrics. The Euclidean distance transform (EDT) uses straight-line distance. Alternatives include the city-block (L1) distance and the chessboard (L∞) distance. In practice, many applications use approximate distance transforms called Chamfer distances, which replace Euclidean distance with simple weighted neighborhood distances, trading accuracy for speed. There are also exact algorithms for the true Euclidean distance in 2D and 3D.

Algorithms. Simple approaches compute distances by sweeping the image multiple times; more efficient methods include Felzenszwalb and Huttenlocher's linear-time EDT, which decomposes the transform into separable passes. Other methods use dynamic programming or distance transform on distance transforms. Implementations are available in many libraries (for example, OpenCV, scikit-image) and support 2-D and 3-D arrays.

Applications. Distance transforms support shape analysis, object localization, and feature extraction. They underpin skeletonization, Voronoi diagram computation, median filtering, and path planning in robotics and computer vision. In medical imaging and material science, distance maps help quantify structures and measure proximity to boundaries.