Editing Distance transform

{{Short description|Derived representation of a digital image}}
{{more footnotes|date=August 2014}}
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 [[Perspective (cognitive)|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.<ref>{{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
 }}</ref>

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]].

[[Image:Distance Transformation.gif|frame|right|A distance transformation]]

Usually the transform/map is qualified with the chosen [[Metric (mathematics)|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.<ref>Strutz, Tilo: The Distance Transform and its Computation. June, 2021, TECH/2021/06, arXiv:2106.03503v1, https://arxiv.org/abs/2106.03503</ref> 

Applications are [[digital image processing]] (e.g., blurring effects, [[topological skeletons|skeletonizing]]), [[motion planning]] in [[robotics]], medical-image analysis for prenatal [[genetic testing]], and even [[pathfinding]].
<ref>{{cite journal
 | 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
 }}</ref>
Uniformly-sampled signed distance fields have been used for [[GPU]]-accelerated [[font]] smoothing, for example by [[Valve Corporation|Valve]] researchers.<ref>''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}}''</ref>

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.<ref>Archived at [https://ghostarchive.org/varchive/youtube/20211211/2MzSmdC49Ns Ghostarchive]{{cbignore}} and the [https://web.archive.org/web/20140125070028/http://www.youtube.com/watch?v=2MzSmdC49Ns Wayback Machine]{{cbignore}}: {{cite AV media| url = https://www.youtube.com/watch?v=2MzSmdC49Ns| title = Advanced visual effects with DirectX 11 | website=[[YouTube]]}}{{cbignore}}</ref>

==See also==
* [[Signed distance function]] 
* [[Function representation]] 
* [[Parallel curve]]
* Level sets methods for distance computation.<ref>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.</ref>

==References==
{{reflist}}

==External links ==
*[http://www.theoryofcomputing.org/articles/v008a019/v008a019.pdf Fast distance transform in C++] by Felzenszwalb and Huttenlocher
*[http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm Distance Transform tutorials in CVonline]
*[http://distance.sourceforge.net Survey of fast exact Euclidean distance transform algorithms]
*[http://www.javaonthebrain.com/java/dungeon/ai.html Using distance mapping for AI]
* [http://demonstrations.wolfram.com/DistanceTransforms/ Distance Transforms] by Henry Kwong and [http://demonstrations.wolfram.com/DynamicStepDistanceTransforms/ Dynamic Step Distance Transforms] by Richard Scott, [[The Wolfram Demonstrations Project]].
*Morphological DistanceTransform function in [http://reference.wolfram.com/mathematica/ref/DistanceTransform.html Mathematica]
*Morphological Inverse Distance Transform function in [http://reference.wolfram.com/mathematica/ref/InverseDistanceTransform.html Mathematica]
*A general algorithm for computing distance transforms in linear time [http://www.cs.rug.nl/~roe/publications/dt.pdf]

[[Category:Image processing]]
[[Category:Digital geometry]]