7.3.1 Distance Transforms, Functions and Skeletons

Fischler, M.A., Barrett, P.,
An Iconic Transform for Sketch Completion and Shape Abstraction,
CGIP(13), No. 4, August 1980, pp. 334-360.
Elsevier DOI Introduce the labeled distance transform and apply to generation of skeletons, closest surrounding region, etc. It uses a four-pass Euclidean distance transform. BibRef 8008

Yokoi, S., Toriwaki, J.I., Fukumura, T.,
Properties of Fusion Distance Transformation and Skeleton for Processing of Gray Pictures,
IECE(61-D), September 1978, pp. 613-xx. BibRef 7809

Toriwaki, J., Saitoh, T., Okada, M.,
Distance Transformation and Skeleton for Shape Feature Analysis,
VF91(547-563). BibRef 9100

Toriwaki, J.I., Yokoi, S.,
Distance Transformations and Skeletons of Digitized Pictures with Applications,
PPR82(187-264). BibRef 8200

Meyer, F.,
Skeletons and Perceptual Graphs,
SP(16), 1989, pp. 335-363. BibRef 8900

Meyer, F.,
Digital Euclidean Skeletons,
SPIE(1360), 1990, pp. 251-262. BibRef 9000

Forsgren, P.O., Seidman, P.,
An Interobject Distance Measure Based on Medial Axes Retrieved from Discrete Distance Maps,
PAMI(12), No. 4, April 1990, pp. 390-397.
IEEE DOI Use of the MAT between 2 objects. BibRef 9004

Preteux, F.,
Watershed and Skeleton by Influence Zones: A Distance-Based Approach,
JMIV(1), 1992, pp. 239-255. BibRef 9200

Shih, F.Y.[Frank Y.], Pu, C.C.[Christopher C.],
A Skeletonization Algorithm by Maxima Tracking on Euclidean Distance Transform,
PR(28), No. 3, March 1995, pp. 331-341.
Elsevier DOI BibRef 9503
Earlier:
Medial axis transformation with single-pixel and connectivity preservation using Euclidean distance computation,
ICPR90(I: 723-725).
IEEE DOI 9006
BibRef

Wright, M.W.[Mark W.], Cipolla, R.[Roberto], Giblin, P.J.[Peter J.],
Skeletonization Using an Extended Euclidean Distance Transform,
IVC(13), No. 5, June 1995, pp. 367-375.
Elsevier DOI BibRef 9506
And: BMVC94(559-568).
PDF File.
HTML Version. 9409
BibRef

Kimmel, R., Shaked, D., Kiryati, N., and Bruckstein, A.M.,
Skeletonization via Distance Maps and Level Sets,
CVIU(62), No. 3, November 1995, pp. 382-391.
DOI Link Segment the boundary first (maximal curvature), then compute a distance map from these points. The skeleton is computed from the distance map. BibRef 9511

Kimmel, R., Bruckstein, A.M.,
Shape offsets via level sets,
CAD(25), No. 3, March 1993, pp. 154-162. BibRef 9303

Kimmel, R., Kiryati, N., Bruckstein, A.M.,
Sub-Pixel Distance Maps and Weighted Distance Transforms,
JMIV(6), No. 2-3, June 1996, pp. 223-233. 9608
BibRef
Earlier: A1 and A3 only: SPIE(2031), 1993, pp. 259-268. BibRef

Niblack, C.W.[C. Wayne], Gibbons, P.B.[Phillip B.], Capson, D.W.[David W.],
Generating Skeletons and Centerlines from the Distance Transform,
GMIP(54), No. 5, September 1992, pp. 420-437. BibRef 9209
And:
Generating Connected Skeletons for Exact and Approximate Reconstruction,
CVPR92(826-828).
IEEE DOI BibRef
Earlier: A1, A3, A2:
Generating Skeletons and Centerlines from the Medial Axis Transform,
ICPR90(I: 881-885).
IEEE DOI Different levels of representation for different quality of reconstruction. BibRef

Gibbons, P.B., Niblack, C.W.,
A Width-Independent Parallel Thinning Algorithm,
ICPR92(III:708-711).
IEEE DOI BibRef 9200

Nacken, P.F.M.,
Chamfer Metrics, the Medial Axis and Mathematical Morphology,
JMIV(6), No. 2-3, June 1996, pp. 235-248. 9608
BibRef

Nacken, P.F.M.,
Chamfer Metrics in Mathematical Morphology,
JMIV(4), 1994, pp. 233-253. BibRef 9400

Sanniti di Baja, G.[Gabriella], Thiel, E.[Edouard],
Skeletonization Algorithm Running on Path-Based Distance Maps,
IVC(14), No. 1, February 1996, pp. 47-57.
Elsevier DOI 9608
BibRef
And:
The Path-Based Distance Skeleton: A Flexible Tool to Analyse Silhouette Shape,
ICPR94(B:570-572).
IEEE DOI BibRef
And:
A multiresolution shape description algorithm,
CAIP93(208-215).
Springer DOI 9309

See also 3,4)-Weighted Skeleton Decomposition for Pattern Representation and Description. BibRef

Borgefors, G.[Gunilla], Sanniti di Baja, G.[Gabriella],
Skeletonizing the Distance Transform on the Hexagonal Grid,
ICPR88(I: 504-507).
IEEE DOI BibRef 8800

Ge, Y.R.[Yao-Rong], Fitzpatrick, J.M.[J. Michael],
On the Generation of Skeletons from Discrete Euclidean Distance Maps,
PAMI(18), No. 11, November 1996, pp. 1055-1066.
IEEE DOI 9612
BibRef
And:
Extraction of Maximal Inscribed Disks from Discrete Euclidean Distance Maps,
CVPR96(556-561).
IEEE DOI BibRef

Qian, K., Cao, S., Bhattacharya, P.,
Gray Image Skeletonization with Hollow Preprocessing Using Distance Transformation,
PRAI(13), No. 6, September 1999, pp. 881-892i. 0005
BibRef

da Fontoura Costa, L.[Luciano],
Robust Skeletonization through Exact Euclidean Distance Transform and its Application to Neuromorphometry,
RealTimeImg(6), No. 6, December 2000, pp. 415-431. 0101
BibRef

Luppe, M.[Maximiliam], da Fontoura Costa, L.[Luciano], Roda, V.O.[Valentin Obac],
Parallel implementation of exact dilations and multi-scale skeletonization,
RealTimeImg(9), No. 3, June 2003, pp. 163-169.
Elsevier DOI 0310
Hardware implementation. BibRef

da Fontoura Costa, L.[Luciano],
Enhanced multiscale skeletons,
RealTimeImg(9), No. 5, October 2003, pp. 314-318.
Elsevier DOI 0311
Enhance accuracy BibRef

Zou, J.J.[Ju Jia], Chang, H.H.[Hung-Hsin], Yan, H.[Hong],
Shape skeletonization by identifying discrete local symmetries,
PR(34), No. 10, October 2001, pp. 1895-1905.
Elsevier DOI 0108
Delaunay triangulation to isolated, end, normal and junction triangles. BibRef

Choi, S.W.[Sung Woo], Seidel, H.P.[Hans-Peter],
Hyperbolic Hausdorff Distance for Medial Axis Transform,
GM(63), No. 5, September 2001, pp. 369-384.
DOI Link 0203
BibRef

Breuß, M.[Michael], Zimmer, H.[Henning], Weickert, J.[Joachim],
Can Variational Models for Correspondence Problems Benefit from Upwind Discretisations?,
JMIV(39), No. 3, March 2011, pp. 230-244.
WWW Link. 1103
BibRef

Zimmer, H.[Henning], Breuß, M.[Michael], Weickert, J.[Joachim], Seidel, H.P.[Hans-Peter],
Hyperbolic Numerics for Variational Approaches to Correspondence Problems,
SSVM09(636-647).
Springer DOI 0906
BibRef

Choi, S.W., Lee, S.W.,
Stability Analysis of Medial Axis Transform Under Relative Hausdorff Distance,
ICPR00(Vol III: 135-138).
IEEE DOI 0009
BibRef

Choi, W.P.[Wai-Pak], Lam, K.M.[Kin-Man], Siu, W.C.[Wan-Chi],
An Efficient and Accurate Algorithm for Extracting a Skeleton,
ICPR00(Vol III: 742-745).
IEEE DOI 0009
BibRef

Pizer, S.M.[Stephen M.], Siddiqi, K.[Kaleem], Székely, G.[Gabor], Damon, J.N.[James N.], Zucker, S.W.[Steven W.],
Multiscale Medial Loci and Their Properties,
IJCV(55), No. 2-3, November-December 2003, pp. 155-179.
DOI Link 0310
BibRef

Han, Q.O.[Qi-Ong], Pizer, S.M.[Stephen M.], Damon, J.N.[James N.],
Interpolation in Discrete Single Figure Medial Objects,
MMBIA06(85).
IEEE DOI 0609
BibRef

Xu, J.N.[Jian-Ning],
A Generalized Discrete Morphological Skeleton Transform with Multiple Structuring Elements for the Extraction of Structural Shape Components,
IP(12), No. 12, December 2003, pp. 1677-1686.
IEEE DOI 0402
BibRef
Earlier:
A Generalized Morphological Skeleton Transform and Extraction of Structural Shape Components,
ICIP03(I: 325-328).
IEEE DOI 0312
BibRef
Earlier:
Morphological skeleton and shape decomposition,
ICPR90(I: 876-880).
IEEE DOI 9006

See also Morphological Decomposition of 2-D Binary Shapes into Conditionally Maximal Convex Polygons.
See also Hierarchical Representation of 2-D Shapes Using Convex Polygons: A Morphological Approach.
See also Morphological Decomposition of 2-D Binary Shapes Into Modestly Overlapped Octagonal and Disk Components. BibRef

Xu, J.N.[Jian-Ning],
A generalized morphological skeleton transform using both internal and external skeleton points,
PR(47), No. 8, 2014, pp. 2607-2620.
Elsevier DOI 1405
Mathematical morphology BibRef

Liu, X.B.[Xia-Bi], Jia, Y.D.[Yun-De],
A bottom-up algorithm for finding principal curves with applications to image skeletonization,
PR(38), No. 7, July 2005, pp. 1079-1085.
Elsevier DOI 0505
BibRef

Wang, L.W.[Li-Wei], Zhang, Y.[Yan], Feng, J.F.[Ju-Fu],
On the Euclidean Distance of Images,
PAMI(27), No. 8, August 2005, pp. 1334-1339.
IEEE Abstract. 0506
Image ED take into account spatial relations of pixels. BibRef

Baudrier, E.[Etienne], Nicolier, F.[Frederic], Millon, G.[Gilles], Ruan, S.[Su],
Binary-image comparison with local-dissimilarity quantification,
PR(41), No. 5, May 2008, pp. 1461-1478.
Elsevier DOI 0711
BibRef
Earlier: A1, A3, A2, A4:
A fast binary-image comparison method with local-dissimilarity quantification,
ICPR06(III: 216-219).
IEEE DOI 0609
BibRef
Earlier: A1, A3, A2, A4:
A new similarity measure using Hausdorff distance map,
ICIP04(I: 669-672).
IEEE DOI 0505
Binary images; Hausdorff distance; Similarity measures; Spatial dissimilarity layout; Local analysis BibRef

Shapira, L.[Lior], Shamir, A.[Ariel], Cohen-Or, D.[Daniel],
Consistent mesh partitioning and skeletonisation using the shape diameter function,
VC(24), No. 4, April 2008, pp. xx-yy.
Springer DOI 0804
BibRef

Gustavson, S.[Stefan], Strand, R.[Robin],
Anti-aliased Euclidean distance transform,
PRL(32), No. 2, 15 January 2011, pp. 252-257.
Elsevier DOI 1101
Distance transform; Vector propagation; Euclidean metric; Sub-pixel accuracy BibRef

Linnér, E.[Elisabeth], Strand, R.[Robin],
A Graph-Based Implementation of the Anti-aliased Euclidean Distance Transform,
ICPR14(1025-1030)
IEEE DOI 1412
BibRef
Earlier:
Anti-Aliased Euclidean Distance Transform on 3D Sampling Lattices,
DGCI14(88-98).
Springer DOI 1410
Algorithm design and analysis BibRef

Strand, R.[Robin],
Sparse Object Representations by Digital Distance Functions,
DGCI11(211-222).
Springer DOI 1104
BibRef

Wang, J.[Jun], Tan, Y.[Ying],
Efficient Euclidean distance transform algorithm of binary images in arbitrary dimensions,
PR(46), No. 1, January 2013, pp. 230-242.
Elsevier DOI 1209
BibRef
Earlier:
Efficient Euclidean distance transform using perpendicular bisector segmentation,
CVPR11(1625-1632).
IEEE DOI 1106
Euclidean distance transform; Arbitrary dimensions; Independent scan; Linear time algorithm; Binary image BibRef

Gavet, Y.[Yann], Pinoli, J.C.[Jean-Charles],
Human visual perception and dissimilarity,
SPIE(Newsroom), November 15, 2013.
DOI Link 1311
Mathematics classically uses distance functions to make comparisons, whereas the notion of dissimilarity is more adapted to the human visual perception system. BibRef

Sironi, A.[Amos], Türetken, E.[Engin], Lepetit, V.[Vincent], Fua, P.[Pascal],
Multiscale Centerline Detection,
PAMI(38), No. 7, July 2016, pp. 1327-1341.
IEEE DOI 1606
BibRef
Earlier: A1, A3, A4, Only:
Multiscale Centerline Detection by Learning a Scale-Space Distance Transform,
CVPR14(2697-2704)
IEEE DOI 1409
Accuracy. BibRef

Mille, J.[Julien], Leborgne, A.[Aurélie], Tougne, L.[Laure],
Euclidean Distance-Based Skeletons: A Few Notes on Average Outward Flux and Ridgeness,
JMIV(61), No. 3, March 2019, pp. 310-330.
WWW Link. 1903
BibRef

Jiang, Z.[Zheheng], Rahmani, H.[Hossein], Angelov, P.[Plamen], Vyas, R.[Ritesh], Zhou, H.Y.[Hui-Yu], Black, S.[Sue], Williams, B.[Bryan],
Deep orientated distance-transform network for geometric-aware centerline detection,
PR(146), 2024, pp. 110028.
Elsevier DOI 2311
Centerline detection, Geometric properties, Graph representation, Graph refinement BibRef

Kushnir, O.[Olesia], Seredin, O.[Oleg],
Parametric Description of Skeleton Radial Function by Legendre Polynomials for Binary Images Comparison,
ICISP14(520-530).
Springer DOI 1406
BibRef

Hulin, J.[Jérôme], Thiel, É.[Édouard],
Farey Sequences and the Planar Euclidean Medial Axis Test Mask,
IWCIA09(82-95).
Springer DOI 0911
BibRef
And:
Appearance Radii in Medial Axis Test Mask for Small Planar Chamfer Norms,
DGCI09(434-445).
Springer DOI 0909
BibRef

Bailey, D.G.[Donald G.],
An Efficient Euclidean Distance Transform,
IWCIA04(394-408).
Springer DOI 0505
BibRef

Makada, Y., Toriwaki, J.,
Anchor point thinning using a skeleton based on the Euclidean distance transformation,
ICPR02(III: 923-926).
IEEE DOI 0211
BibRef

Jang, J.H.[Jeong-Hun], Hong, K.S.[Ki-Sang],
A Pseudo-Distance Map for the Segmentation-Free Skeletonization of Gray-Scale Images,
ICCV01(II: 18-23).
IEEE DOI 0106
Skeleton directly with image data. BibRef

Li, H.[Hong], Vossepoel, A.M.[Albert M.],
Generation of the Euclidean Skeleton from the Vector Distance Map by a Bisector Decision Rule,
CVPR98(66-71).
IEEE DOI BibRef 9800

Chehadeh, Y., Coquin, D., Bolon, P.,
A Skeletonization Algorithm Using Chamfer Distance Transformation Adapted to Rectangular Grids,
ICPR96(II: 131-135).
IEEE DOI 9608
(Universite de Savoie, F) BibRef

Talbot, H., Vincent, L.,
Euclidean Skeletons and Conditional Bisectors,
SPIE(1818), Visual Comm. and Image Pricessing, 1992, pp. 862-876. BibRef 9200

Vincent, L.,
Exact Euclidean Distance Function by Chain Propagation,
CVPR91(520-525).
IEEE DOI BibRef 9100

Chapter on 2-D Feature Analysis, Extraction and Representations, Shape, Skeletons, Texture continues in
Use of Skeletons for Recognition and Representation .