distancetransformed

Distancetransformed, commonly referred to as the distance transform, is a family of image processing and mathematical tools that assigns to every point in a space a value representing its distance to a set of specified feature points. In a digital image, the typical use is to compute, for each pixel, the distance to the nearest foreground pixel or to a boundary, producing a distance map that encodes geometric relationships within the image.

Formally, given a domain and a subset S of feature points, the distance transform D(x) is defined as the minimum distance from x to any point in S. The distance metric can vary; the Euclidean distance yields the Euclidean distance transform (EDT), while other common metrics include the city-block (L1) and chessboard (L∞) distances. Some implementations also store the squared Euclidean distance to avoid square roots and enable faster comparisons.

Algorithms for computing distance transforms aim to be fast and accurate. Exact EDT algorithms exist that run in linear time with respect to the number of pixels, such as the separable methods that perform 1D transforms along each axis and combine the results. Classic approaches include two-pass methods and, more recently, efficient O(nm) algorithms for 2D images. Approximate methods, like chamfer distance transforms, use weighted neighborhood operations to speed up computation while providing close estimates of Euclidean distances.

Applications of distance transforms are broad. They are used in object segmentation and shape analysis, skeletonization and medial-axis computation, path planning and collision checking in robotics, and as preprocessing in feature extraction and medical imaging. Distance maps also support Voronoi diagram construction and various morphological operations.

See also: distance map, Voronoi diagram, skeletonization, morphological distance.