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.
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:
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] Recently, distance transform computation has also been proposed using a static Schrodinger's equation.[3] This particular approach has the benefit of obtaining an analytical closed-form solution to distance transforms, and of computing the average distance transform over a set of distance transforms, owing to the linearity of the Schrödinger equation. Further, this approach has also been leveraged to extend distance transforms to line-segments and curves.[3]
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.[6]
^Gibson, Sarah F. Frisken; Perry, Ronald N.; Rockwood, Alyn P.; Jones, Thouis R. (2000). "Adaptively sampled distance fields: a general representation of shape for computer graphics" (PDF). In Brown, Judith R.; Akeley, Kurt (eds.). Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 2000, New Orleans, LA, USA, July 23-28, 2000. Association for Computing Machinery. pp. 249–254. doi:10.1145/344779.344899.
^Strutz, Tilo: The Distance Transform and its Computation. June, 2021, TECH/2021/06, arXiv:2106.03503v1, https://arxiv.org/abs/2106.03503
^ abM. Sethi, A. Rangarajan and K. Gurumoorthy, "The Schrödinger distance transform (SDT) for point-sets and curves," 2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, 2012, pp. 198-205, doi:10.1109/CVPR.2012.6247676
^Felzenszwalb, Pedro F.; Huttenlocher, Daniel P. (2012). "Distance transforms of sampled functions". Theory of Computing. 8: 415–428. doi:10.4086/toc.2012.v008a019. MR 2967180.
^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
^Archived at Ghostarchive and the : Advanced visual effects with DirectX 11. YouTube.
^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.
External linksedit
Fast distance transform in C++ by Felzenszwalb and Huttenlocher
Distance Transform tutorials in CVonline
Survey of fast exact Euclidean distance transform algorithms
Morphological DistanceTransform function in Mathematica
Morphological Inverse Distance Transform function in Mathematica
A general algorithm for computing distance transforms in linear time [1]
January 01, 1970
distance, transform, this, article, includes, list, general, references, lacks, sufficient, corresponding, inline, citations, please, help, improve, this, article, introducing, more, precise, citations, august, 2014, learn, when, remove, this, message, distanc. This article includes a list of general references but it lacks sufficient corresponding inline citations Please help to improve this article by introducing more precise citations August 2014 Learn how and when to remove this message 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 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 2 Recently distance transform computation has also been proposed using a static Schrodinger s equation 3 This particular approach has the benefit of obtaining an analytical closed form solution to distance transforms and of computing the average distance transform over a set of distance transforms owing to the linearity of the Schrodinger equation Further this approach has also been leveraged to extend distance transforms to line segments and curves 3 Applications are digital image processing e g blurring effects skeletonizing motion planning in robotics medical image analysis for prenatal genetic testing and even pathfinding 4 Uniformly sampled signed distance fields have been used for GPU accelerated font smoothing for example by Valve researchers 5 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 6 See also editSigned distance function Function representation Parallel curve Level sets methods for distance computation 7 References edit Gibson Sarah F Frisken Perry Ronald N Rockwood Alyn P Jones Thouis R 2000 Adaptively sampled distance fields a general representation of shape for computer graphics PDF In Brown Judith R Akeley Kurt eds Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques SIGGRAPH 2000 New Orleans LA USA July 23 28 2000 Association for Computing Machinery pp 249 254 doi 10 1145 344779 344899 Strutz Tilo The Distance Transform and its Computation June 2021 TECH 2021 06 arXiv 2106 03503v1 https arxiv org abs 2106 03503 a b M Sethi A Rangarajan and K Gurumoorthy The Schrodinger distance transform SDT for point sets and curves 2012 IEEE Conference on Computer Vision and Pattern Recognition Providence RI USA 2012 pp 198 205 doi 10 1109 CVPR 2012 6247676 Felzenszwalb Pedro F Huttenlocher Daniel P 2012 Distance transforms of sampled functions Theory of Computing 8 415 428 doi 10 4086 toc 2012 v008a019 MR 2967180 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 Archived at Ghostarchive and the Wayback Machine Advanced visual effects with DirectX 11 YouTube 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 External links editFast 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 Retrieved from https en wikipedia org w index php title Distance transform amp oldid 1206171981, wikipedia, wiki, book, books, library,
