In shape analysis, skeleton (or topological skeleton) of a shape is a thin version of that shape that is equidistant to its boundaries. The skeleton usually emphasizes geometrical and topological properties of the shape, such as its connectivity, topology, length, direction, and width. Together with the distance of its points to the shape boundary, the skeleton can also serve as a representation of the shape (they contain all the information necessary to reconstruct the shape).
A shape and its skeleton, computed with a topology-preserving thinning algorithm.
Skeletons have several different mathematical definitions in the technical literature, and there are many different algorithms for computing them. Various different variants of skeleton can also be found, including straight skeletons, morphological skeletons, etc.
In the technical literature, the concepts of skeleton and medial axis are used interchangeably by some authors,[1][2] while some other authors[3][4][5] regard them as related, but not the same. Similarly, the concepts of skeletonization and thinning are also regarded as identical by some,[2] and not by others.[3]
Skeletons have several different mathematical definitions in the technical literature; most of them lead to similar results in continuous spaces, but usually yield different results in discrete spaces.
In his seminal paper, Harry Blum[8] of the Air Force Cambridge Research Laboratories at Hanscom Air Force Base, in Bedford, Massachusetts, defined a medial axis for computing a skeleton of a shape, using an intuitive model of fire propagation on a grass field, where the field has the form of the given shape. If one "sets fire" at all points on the boundary of that grass field simultaneously, then the skeleton is the set of quench points, i.e., those points where two or more wavefronts meet. This intuitive description is the starting point for a number of more precise definitions.
Centers of maximal disks (or balls)
A disk (or ball) B is said to be maximal in a set A if
, and
If another disc D contains B, then .
One way of defining the skeleton of a shape A is as the set of centers of all maximal disks in A.[9]
Centers of bi-tangent circles
The skeleton of a shape A can also be defined as the set of centers of the discs that touch the boundary of A in two or more locations.[10] This definition assures that the skeleton points are equidistant from the shape boundary and is mathematically equivalent to Blum's medial axis transform.
Ridges of the distance function
Many definitions of skeleton make use of the concept of distance function, which is a function that returns for each point x inside a shape A its distance to the closest point on the boundary of A. Using the distance function is very attractive because its computation is relatively fast.
One of the definitions of skeleton using the distance function is as the ridges of the distance function.[3] There is a common mis-statement in the literature that the skeleton consists of points which are "locally maximum" in the distance transform. This is simply not the case, as even cursory comparison of a distance transform and the resulting skeleton will show. Ridges may have varying height, so a point on the ridge may be lower than its immediate neighbor on the ridge. It is thus not a local maximum, even though it belongs to the ridge. It is, however, less far away vertically than its ground distance would warrant. Otherwise it would be part of the slope.
Other definitions
Points with no upstream segments in the distance function. The upstream of a point x is the segment starting at x which follows the maximal gradient path.
Points where the gradient of the distance function are different from 1 (or, equivalently, not well defined)
Smallest possible set of lines that preserve the topology and are equidistant to the borders
Skeletonization algorithms
There are many different algorithms for computing skeletons for shapes in digital images, as well as continuous sets.
^Zhang, T. Y.; Suen, C. Y. (1984-03-01). "A fast parallel algorithm for thinning digital patterns". Communications of the ACM. 27 (3): 236–239. doi:10.1145/357994.358023. ISSN 0001-0782. S2CID 39713481.
References
Abeysinghe, Sasakthi; Baker, Matthew; Chiu, Wah; Ju, Tao (2008), "Segmentation-free skeletonization of grayscale volumes for shape understanding", IEEE Int. Conf. Shape Modeling and Applications (SMI 2008)(PDF), pp. 63–71, doi:10.1109/SMI.2008.4547951, ISBN978-1-4244-2260-9, S2CID 15148296.
Abeysinghe, Sasakthi; Ju, Tao; Baker, Matthew; Chiu, Wah (2008), "Shape modeling and matching in identifying 3D protein structures" (PDF), Computer-Aided Design, Elsevier, 40 (6): 708–720, doi:10.1016/j.cad.2008.01.013
Bai, Xiang; Longin, Latecki; Wenyu, Liu (2007), "Skeleton pruning by contour partitioning with discrete curve evolution" (PDF), IEEE Transactions on Pattern Analysis and Machine Intelligence, 29 (3): 449–462, doi:10.1109/TPAMI.2007.59, PMID 17224615, S2CID 14965041.
Blum, Harry (1967), "A Transformation for Extracting New Descriptors of Shape", in Wathen-Dunn, W. (ed.), Models for the Perception of Speech and Visual Form(PDF), Cambridge, Massachusetts: MIT Press, pp. 362–380.
Bucksch, Alexander (2014), "A practical introduction to skeletons for the plant sciences", Applications in Plant Sciences, 2 (8): 1400005, doi:10.3732/apps.1400005, PMC4141713, PMID 25202647.
Cychosz, Joseph (1994), Graphics gems IV, San Diego, CA, USA: Academic Press Professional, Inc., pp. 465–473, ISBN0-12-336155-9.
Dougherty, Edward R. (1992), An Introduction to Morphological Image Processing, ISBN0-8194-0845-X.
Golland, Polina; Grimson, W. Eric L. (2000), "Fixed topology skeletons" (PDF), 2000 Conference on Computer Vision and Pattern Recognition (CVPR 2000), 13-15 June 2000, Hilton Head, SC, USA, IEEE Computer Society, pp. 1010–1017, doi:10.1109/CVPR.2000.855792, S2CID 9916140
Gonzales, Rafael C.; Woods, Richard E. (2001), Digital Image Processing, ISBN0-201-18075-8.
Jain, Anil K. (1989), Fundamentals of Digital Image Processing, Bibcode:1989fdip.book.....J, ISBN0-13-336165-9.
Jain, Ramesh; Kasturi, Rangachar; Schunck, Brian G. (1995), Machine Vision, ISBN0-07-032018-7.
Kimmel, Ron; Shaked, Doron; Kiryati, Nahum; Bruckstein, Alfred M. (1995), "Skeletonization via distance maps and level sets" (PDF), Computer Vision and Image Understanding, 62 (3): 382–391, doi:10.1006/cviu.1995.1062
Ogniewicz, R. L. (1995), "Automatic Medial Axis Pruning Based on Characteristics of the Skeleton-Space", in Dori, D.; Bruckstein, A. (eds.), Shape, Structure and Pattern Recognition, ISBN981-02-2239-4.
Petrou, Maria; García Sevilla, Pedro (2006), Image Processing Dealing with Texture, ISBN978-0-470-02628-1.
Serra, Jean (1982), Image Analysis and Mathematical Morphology, ISBN0-12-637240-3.
Sethian, J. A. (1999), Level Set Methods and Fast Marching Methods, ISBN0-521-64557-3.
Tannenbaum, Allen (1996), "Three snippets of curve evolution theory in computer vision", Mathematical and Computer Modelling, 24 (5): 103–118, doi:10.1016/0895-7177(96)00117-3.
Skeletons from laser scanned point clouds (Homepage)
January 30, 2023
topological, skeleton, shape, analysis, skeleton, topological, skeleton, shape, thin, version, that, shape, that, equidistant, boundaries, skeleton, usually, emphasizes, geometrical, topological, properties, shape, such, connectivity, topology, length, directi. In shape analysis skeleton or topological skeleton of a shape is a thin version of that shape that is equidistant to its boundaries The skeleton usually emphasizes geometrical and topological properties of the shape such as its connectivity topology length direction and width Together with the distance of its points to the shape boundary the skeleton can also serve as a representation of the shape they contain all the information necessary to reconstruct the shape A shape and its skeleton computed with a topology preserving thinning algorithm Skeletons have several different mathematical definitions in the technical literature and there are many different algorithms for computing them Various different variants of skeleton can also be found including straight skeletons morphological skeletons etc In the technical literature the concepts of skeleton and medial axis are used interchangeably by some authors 1 2 while some other authors 3 4 5 regard them as related but not the same Similarly the concepts of skeletonization and thinning are also regarded as identical by some 2 and not by others 3 Skeletons are widely used in computer vision image analysis pattern recognition and digital image processing for purposes such as optical character recognition fingerprint recognition visual inspection or compression Within the life sciences skeletons found extensive use to characterize protein folding 6 and plant morphology on various biological scales 7 Contents 1 Mathematical definitions 1 1 Quench points of the fire propagation model 1 2 Centers of maximal disks or balls 1 3 Centers of bi tangent circles 1 4 Ridges of the distance function 1 5 Other definitions 2 Skeletonization algorithms 3 See also 4 Notes 5 References 6 Open source software 7 External linksMathematical definitions EditSkeletons have several different mathematical definitions in the technical literature most of them lead to similar results in continuous spaces but usually yield different results in discrete spaces Quench points of the fire propagation model Edit Main article Grassfire transform In his seminal paper Harry Blum 8 of the Air Force Cambridge Research Laboratories at Hanscom Air Force Base in Bedford Massachusetts defined a medial axis for computing a skeleton of a shape using an intuitive model of fire propagation on a grass field where the field has the form of the given shape If one sets fire at all points on the boundary of that grass field simultaneously then the skeleton is the set of quench points i e those points where two or more wavefronts meet This intuitive description is the starting point for a number of more precise definitions Centers of maximal disks or balls Edit A disk or ball B is said to be maximal in a set A if B A displaystyle B subseteq A and If another disc D contains B then D A displaystyle D not subseteq A One way of defining the skeleton of a shape A is as the set of centers of all maximal disks in A 9 Centers of bi tangent circles Edit The skeleton of a shape A can also be defined as the set of centers of the discs that touch the boundary of A in two or more locations 10 This definition assures that the skeleton points are equidistant from the shape boundary and is mathematically equivalent to Blum s medial axis transform Ridges of the distance function Edit Many definitions of skeleton make use of the concept of distance function which is a function that returns for each point x inside a shape A its distance to the closest point on the boundary of A Using the distance function is very attractive because its computation is relatively fast One of the definitions of skeleton using the distance function is as the ridges of the distance function 3 There is a common mis statement in the literature that the skeleton consists of points which are locally maximum in the distance transform This is simply not the case as even cursory comparison of a distance transform and the resulting skeleton will show Ridges may have varying height so a point on the ridge may be lower than its immediate neighbor on the ridge It is thus not a local maximum even though it belongs to the ridge It is however less far away vertically than its ground distance would warrant Otherwise it would be part of the slope Other definitions Edit Points with no upstream segments in the distance function The upstream of a point x is the segment starting at x which follows the maximal gradient path Points where the gradient of the distance function are different from 1 or equivalently not well defined Smallest possible set of lines that preserve the topology and are equidistant to the bordersSkeletonization algorithms EditThere are many different algorithms for computing skeletons for shapes in digital images as well as continuous sets Using morphological operators See Morphological skeleton 10 Supplementing morphological operators with shape based pruning 11 Using intersections of distances from boundary sections 12 Using curve evolution 13 14 Using level sets 5 Finding ridge points on the distance function 3 Peeling the shape without changing the topology until convergence 15 Zhang Suen Thinning Algorithm 16 Skeletonization algorithms can sometimes create unwanted branches on the output skeletons Pruning algorithms are often used to remove these branches See also EditMedial axis Straight skeleton b skeleton Grassfire Transform Stroke based fontsNotes Edit Jain Kasturi amp Schunck 1995 Section 2 5 10 p 55 Golland amp Grimson 2000 Dougherty 1992 Ogniewicz 1995 a b Gonzales amp Woods 2001 Section 11 1 5 p 650 a b c d A K Jain 1989 Section 9 9 p 382 Serra 1982 a b Sethian 1999 Section 17 5 2 p 234 Abeysinghe et al 2008 Bucksch 2014 Harry Blum 1967 A K Jain 1989 Section 9 9 p 387 a b Gonzales amp Woods 2001 Section 9 5 7 p 543 Abeysinghe et al 2008 Kimmel et al 1995 Tannenbaum 1996 Bai Longin amp Wenyu 2007 A K Jain 1989 Section 9 9 p 389 Zhang T Y Suen C Y 1984 03 01 A fast parallel algorithm for thinning digital patterns Communications of the ACM 27 3 236 239 doi 10 1145 357994 358023 ISSN 0001 0782 S2CID 39713481 References EditAbeysinghe Sasakthi Baker Matthew Chiu Wah Ju Tao 2008 Segmentation free skeletonization of grayscale volumes for shape understanding IEEE Int Conf Shape Modeling and Applications SMI 2008 PDF pp 63 71 doi 10 1109 SMI 2008 4547951 ISBN 978 1 4244 2260 9 S2CID 15148296 Abeysinghe Sasakthi Ju Tao Baker Matthew Chiu Wah 2008 Shape modeling and matching in identifying 3D protein structures PDF Computer Aided Design Elsevier 40 6 708 720 doi 10 1016 j cad 2008 01 013 Bai Xiang Longin Latecki Wenyu Liu 2007 Skeleton pruning by contour partitioning with discrete curve evolution PDF IEEE Transactions on Pattern Analysis and Machine Intelligence 29 3 449 462 doi 10 1109 TPAMI 2007 59 PMID 17224615 S2CID 14965041 Blum Harry 1967 A Transformation for Extracting New Descriptors of Shape in Wathen Dunn W ed Models for the Perception of Speech and Visual Form PDF Cambridge Massachusetts MIT Press pp 362 380 Bucksch Alexander 2014 A practical introduction to skeletons for the plant sciences Applications in Plant Sciences 2 8 1400005 doi 10 3732 apps 1400005 PMC 4141713 PMID 25202647 Cychosz Joseph 1994 Graphics gems IV San Diego CA USA Academic Press Professional Inc pp 465 473 ISBN 0 12 336155 9 Dougherty Edward R 1992 An Introduction to Morphological Image Processing ISBN 0 8194 0845 X Golland Polina Grimson W Eric L 2000 Fixed topology skeletons PDF 2000 Conference on Computer Vision and Pattern Recognition CVPR 2000 13 15 June 2000 Hilton Head SC USA IEEE Computer Society pp 1010 1017 doi 10 1109 CVPR 2000 855792 S2CID 9916140 Gonzales Rafael C Woods Richard E 2001 Digital Image Processing ISBN 0 201 18075 8 Jain Anil K 1989 Fundamentals of Digital Image Processing Bibcode 1989fdip book J ISBN 0 13 336165 9 Jain Ramesh Kasturi Rangachar Schunck Brian G 1995 Machine Vision ISBN 0 07 032018 7 Kimmel Ron Shaked Doron Kiryati Nahum Bruckstein Alfred M 1995 Skeletonization via distance maps and level sets PDF Computer Vision and Image Understanding 62 3 382 391 doi 10 1006 cviu 1995 1062 Ogniewicz R L 1995 Automatic Medial Axis Pruning Based on Characteristics of the Skeleton Space in Dori D Bruckstein A eds Shape Structure and Pattern Recognition ISBN 981 02 2239 4 Petrou Maria Garcia Sevilla Pedro 2006 Image Processing Dealing with Texture ISBN 978 0 470 02628 1 Serra Jean 1982 Image Analysis and Mathematical Morphology ISBN 0 12 637240 3 Sethian J A 1999 Level Set Methods and Fast Marching Methods ISBN 0 521 64557 3 Tannenbaum Allen 1996 Three snippets of curve evolution theory in computer vision Mathematical and Computer Modelling 24 5 103 118 doi 10 1016 0895 7177 96 00117 3 Open source software EditITK C Skeletonize3D Java Graphics gems IV C EVG Thin C NeuronStudioExternal links EditSkeletonization Medial Axis Transform Skeletons of a region Skeletons in Digital image processing pdf Comparison of 15 line thinning algorithms Skeletonization using Level Set Methods Curve Skeletons Skeletons from laser scanned point clouds Homepage Retrieved from https en wikipedia org w index php title Topological skeleton amp oldid 1120323609, wikipedia, wiki, book, books, library,
