A distance transform, also known as distance map or distance field, is a derived representation of a

digital image A digital image is an image composed of picture elements, also known as ''pixels'', each with '' finite'', '' discrete quantities'' of numeric representation for its intensity or gray level that is an output from its two-dimensional functions f ...

. The choice of the term depends on the point of view on the object in question: whether the initial image is transformed into another representation, or it is simply endowed with an additional map or field. Distance fields can also be signed, in the case where it is important to distinguish whether the point is inside or outside of the shape. The map labels each

pixel In digital imaging, a pixel (abbreviated px), pel, or picture element is the smallest addressable element in a raster image, or the smallest point in an all points addressable display device. In most digital display devices, pixels are the s ...

of the image with the distance to the nearest ''obstacle pixel''. A most common type of obstacle pixel is a ''boundary pixel'' in a

binary image A binary image is one that consists of pixels that can have one of exactly two colors, usually black and white. Binary images are also called ''bi-level'' or ''two-level'', Pixelart made of two colours is often referred to as ''1-Bit'' or ''1b ...

. See the image for an example of a

Chebyshev distance In mathematics, Chebyshev distance (or Tchebychev distance), maximum metric, or L∞ metric is a metric defined on a vector space where the distance between two vectors is the greatest of their differences along any coordinate dimension. It is ...

transform on a

. Usually the transform/map is qualified with the chosen metric. For example, one may speak of Manhattan distance transform, if the underlying metric is

Manhattan distance A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian co ...

. Common metrics are: *

Euclidean distance In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore o ...

Taxicab geometry A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian ...

, also known as ''City block distance'' or ''Manhattan distance''. *

There are several algorithms to compute the distance transform for these different distance metrics, however the computation of the exact Euclidean distance transform (EEDT) needs special treatment if it is computed on the image grid. Applications are

digital image processing Digital image processing is the use of a digital computer to process digital images through an algorithm. As a subcategory or field of digital signal processing, digital image processing has many advantages over analog image processing. It allow ...

(e.g., blurring effects, skeletonizing),

motion planning Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used ...

robotics Robotics is an interdisciplinarity, interdisciplinary branch of computer science and engineering. Robotics involves design, construction, operation, and use of robots. The goal of robotics is to design machines that can help and assist human ...

, medical image analysis for prenatal genetic testing, and even pathfinding. Uniformly-sampled signed distance fields have been used for GPU-accelerated

font In movable type, metal typesetting, a font is a particular #Characteristics, size, weight and style of a typeface. Each font is a matched set of type, with a piece (a "Sort (typesetting), sort") for each glyph. A typeface consists of a range of ...

smoothing, for example by

Valve A valve is a device or natural object that regulates, directs or controls the flow of a fluid (gases, liquids, fluidized solids, or slurries) by opening, closing, or partially obstructing various passageways. Valves are technically fitting ...

researchers. Signed distance fields can also be used for (3D) solid modelling. Rendering on typical GPU hardware requires conversion to polygon meshes, e.g. by the marching cubes algorithm.

References

{{reflist

External links

Fast distance transform in C++
by Felzenszwalb and Huttenlocher
Survey of fast exact Euclidean distance transform algorithms

Distance Transforms
by Henry Kwong an
Dynamic Step Distance Transforms
by Richard Scott,

The Wolfram Demonstrations Project The Wolfram Demonstrations Project is an organized, open-source collection of small (or medium-size) interactive programs called Demonstrations, which are meant to visually and interactively represent ideas from a range of fields. It is hos ...

. *Morphological DistanceTransform function i
Mathematica
*Morphological InverseDistanceTransform function i

*A general algorithm for computing distance transforms in linear tim

Image processing Digital geometry

See also

References

External links