Distance transform

Quality 0.50 · 1 view · Updated 2 months ago

Derived representation of a digital image

title: "Distance transform" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["image-processing", "digital-geometry"] description: "Derived representation of a digital image" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Distance_transform" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Derived representation of a digital image ::

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.

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.{{cite conference | last1 = Gibson | first1 = Sarah F. Frisken | last2 = Perry | first2 = Ronald N. | last3 = Rockwood | first3 = Alyn P. | last4 = Jones | first4 = Thouis R. | editor1-last = Brown | editor1-first = Judith R. | editor2-last = Akeley | editor2-first = Kurt | contribution = Adaptively sampled distance fields: a general representation of shape for computer graphics | contribution-url = https://www.merl.com/publications/docs/TR2000-15.pdf | doi = 10.1145/344779.344899 | pages = 249–254 | publisher = Association for Computing Machinery | title = Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 2000, New Orleans, LA, USA, July 23-28, 2000 | year = 2000| doi-access = free

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 Chebyshev distance transform on a binary image.

::figure[src="https://upload.wikimedia.org/wikipedia/commons/f/f7/Distance_Transformation.gif" caption="A distance transformation"] ::

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:

Euclidean distance
Taxicab geometry, also known as City block distance or Manhattan distance.
Chebyshev 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 (e.g., blurring effects, skeletonizing), motion planning in robotics, medical-image analysis for prenatal genetic testing, and even pathfinding. | last1 = Felzenszwalb | first1 = Pedro F. | last2 = Huttenlocher | first2 = Daniel P. | author2-link = Daniel P. Huttenlocher | doi = 10.4086/toc.2012.v008a019 | journal = Theory of Computing | mr = 2967180 | pages = 415–428 | title = Distance transforms of sampled functions | volume = 8 | year = 2012| doi-access = free Uniformly-sampled signed distance fields have been used for GPU-accelerated font smoothing, for example by Valve 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

Strutz, Tilo: The Distance Transform and its Computation. June, 2021, TECH/2021/06, arXiv:2106.03503v1, https://arxiv.org/abs/2106.03503
''Chris Green. 2007. Improved alpha-tested magnification for vector textures and special effects. In ACM SIGGRAPH 2007 courses (SIGGRAPH '07). Association for Computing Machinery, New York, NY, USA, 9–18. {{doi. 10.1145/1281500.1281665''
"Advanced visual effects with DirectX 11".
Kimmel, R.; Kiryati, N. and Bruckstein, A. M.: [https://www.cs.technion.ac.il/~ron/PAPERS/KimKirBru_JMIV1996.pdf 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.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::