Distance transform: Difference between revisions
imported>EvilxFish remove obviously promotional material |
imported>SchlurcherBot m Bot: http → https |
||
| Line 56: | Line 56: | ||
==External links == | ==External links == | ||
*[ | *[https://www.theoryofcomputing.org/articles/v008a019/v008a019.pdf Fast distance transform in C++] by Felzenszwalb and Huttenlocher | ||
*[ | *[https://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm Distance Transform tutorials in CVonline] | ||
*[ | *[https://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://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]]. | * [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 [ | *Morphological DistanceTransform function in [https://reference.wolfram.com/mathematica/ref/DistanceTransform.html Mathematica] | ||
*Morphological Inverse Distance Transform function in [ | *Morphological Inverse Distance Transform function in [https://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] | *A general algorithm for computing distance transforms in linear time [http://www.cs.rug.nl/~roe/publications/dt.pdf] | ||
[[Category:Image processing]] | [[Category:Image processing]] | ||
[[Category:Digital geometry]] | [[Category:Digital geometry]] | ||
Latest revision as of 18:03, 30 December 2025
Template:Short description Template:More footnotes 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.[1]
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.
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.[2]
Applications are digital image processing (e.g., blurring effects, skeletonizing), motion planning in robotics, medical-image analysis for prenatal genetic testing, and even pathfinding. [3] Uniformly-sampled signed distance fields have been used for GPU-accelerated font smoothing, for example by Valve researchers.[4]
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.[5]
See also
- Signed distance function
- Function representation
- Parallel curve
- Level sets methods for distance computation.[6]
References
<templatestyles src="Reflist/styles.css" />
- ↑ Script error: No such module "citation/CS1".
- ↑ Strutz, Tilo: The Distance Transform and its Computation. June, 2021, TECH/2021/06, arXiv:2106.03503v1, https://arxiv.org/abs/2106.03503
- ↑ Script error: No such module "Citation/CS1".
- ↑ 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. Script error: No such module "CS1 identifiers".
- ↑ Archived at GhostarchiveTemplate:Cbignore and the Wayback MachineTemplate:Cbignore: Script error: No such module "Citation/CS1".Template:Cbignore
- ↑ Kimmel, R.; Kiryati, N. and Bruckstein, A. M.: 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.
Script error: No such module "Check for unknown parameters".
External links
- Fast distance transform in C++ by Felzenszwalb and Huttenlocher
- Distance Transform tutorials in CVonline
- Survey of fast exact Euclidean distance transform algorithms
- 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 Inverse Distance Transform function in Mathematica
- A general algorithm for computing distance transforms in linear time [1]