Distance transform
Encyclopedia
A distance transform, also known as distance map or distance field, is a derived representation of a digital image
. 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.
The map labels each pixel
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 chessboard distance transform on a binary image
.
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. Common metrics are:
Applications are digital image processing
(e.g., blurring effects, skeletonizing), motion planning
in robotics
, and even pathfinding
.
Digital image
A digital image is a numeric representation of a two-dimensional image. Depending on whether or not the image resolution is fixed, it may be of vector or raster type...
. The choice of the term depends on the point of view
Perspective (cognitive)
Perspective in theory of cognition is the choice of a context or a reference from which to sense, categorize, measure or codify experience, cohesively forming a coherent belief, typically for comparing with another...
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.
The map labels each pixel
Pixel
In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....
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
Binary image
A binary image is a digital image that has only two possible values for each pixel. Typically the two colors used for a binary image are black and white though any two colors can be used. The color used for the object in the image is the foreground color while the rest of the image is the...
. See the image for an example of a chessboard distance transform on a binary image
Binary image
A binary image is a digital image that has only two possible values for each pixel. Typically the two colors used for a binary image are black and white though any two colors can be used. The color used for the object in the image is the foreground color while the rest of the image is the...
.
Metric (mathematics)
In mathematics, a metric or distance function is a function which defines a distance between elements of a set. A set with a metric is called a metric space. A metric induces a topology on a set but not all topologies can be generated by a metric...
. For example, one may speak of Manhattan distance transform, if the underlying metric is Manhattan distance. Common metrics are:
- Euclidean distanceEuclidean distanceIn mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula. By using this formula as distance, Euclidean space becomes a metric space...
- Taxicab geometryTaxicab geometryTaxicab geometry, considered by Hermann Minkowski in the 19th century, is a form of geometry in which the 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 coordinates...
, also known as City block distance or Manhattan distance. - Chessboard distance
Applications are digital image processing
Digital image processing
Digital image processing is the use of computer algorithms to perform image processing on digital images. As a subcategory or field of digital signal processing, digital image processing has many advantages over analog image processing...
(e.g., blurring effects, skeletonizing), motion planning
Motion planning
Motion planning is a term used in robotics for the process of detailing a task into discrete motions....
in robotics
Robotics
Robotics is the branch of technology that deals with the design, construction, operation, structural disposition, manufacture and application of robots...
, and even pathfinding
Pathfinding
Pathfinding generally refers to the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes...
.
External links
- Distance Transform tutorials in CVonline
- Survey of fast exact Euclidean distance transform algorithms
- Lecture notes on Euclidean distance transform
- Using distance mapping for AI
- Distance Transforms by Henry Kwong and Dynamic Step Distance Transforms by Richard Scott, The Wolfram Demonstrations Project.
- Morphological DistanceTransform function in Mathematica
- Morphological InverseDistanceTransform function in Mathematica