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 ...
. The choice of the term depends on the
point of view
Point of view or Points of View may refer to:
Concept and technique
* Point of view (philosophy), an attitude how one sees or thinks of something
* Point of view (literature) or narrative mode, the perspective of the narrative voice; the prono ...
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 smal ...
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. 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 na ...
transform on a
binary image.
Usually the transform/map is qualified with the chosen
metric
Metric or metrical may refer to:
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
In mathem ...
. 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 (mathematics), metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences ...
. 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, therefor ...
*
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 co ...
, also known as ''City block distance'' or ''Manhattan distance''.
*
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 na ...
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 allo ...
(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 use ...
in
robotics
Robotics is an 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 humans. Robotics integrat ...
, medical
image analysis for prenatal genetic testing, and even
pathfinding
Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the sh ...
.
Uniformly-sampled signed distance fields have been used for
GPU
A graphics processing unit (GPU) is a specialized electronic circuit designed to manipulate and alter memory to accelerate the creation of images in a frame buffer intended for output to a display device. GPUs are used in embedded systems, mobi ...
-accelerated
font
In metal typesetting, a font is a particular size, weight and style of a typeface. Each font is a matched set of type, with a piece (a "sort") for each glyph. A typeface consists of a range of such fonts that shared an overall design.
In mod ...
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 fittings ...
researchers.
Signed distance fields can also be used for (3D)
solid modelling
Solid modeling (or solid modelling) is a consistent set of principles for mathematical and computer modeling of three-dimensional shapes '' (solids)''. Solid modeling is distinguished from related areas of geometric modeling and computer graph ...
. Rendering on typical GPU hardware requires conversion to polygon meshes, e.g. by the
marching cubes
Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three-dimensional discrete scalar field (the elements of which are sometim ...
algorithm.
See also
*
Signed distance function
In mathematics and its applications, the signed distance function (or oriented distance function) is the orthogonal distance of a given point ''x'' to the boundary of a set Ω in a metric space, with the sign determined by whether or not ''x' ...
*
Function representation Function Representation (FRep or F-Rep) is used in solid modeling, volume modeling and computer graphics. FRep was introduced in "Function representation in geometric modeling: concepts, implementation and applications" as a uniform representation ...
*
Parallel curve
A parallel of a curve is the envelope of a family of congruent circles centered on the curve.
It generalises the concept of '' parallel (straight) lines''. It can also be defined as a curve whose points are at a constant '' normal distance'' f ...
* Level sets methods for distance computation.
[R. Kimmel, N. Kiryati, and A. M. Bruckstein]
Distance maps and weighted distance transforms
Journal of Mathematical Imaging and Vision, Special Issue on Topology and Geometry in Computer Vision, 6:223-233,1996.
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