Topological skeleton 1924604 225831864 2008-07-15T16:34:16Z Renatokeshet 7089667 Correcting a couple of links. [[Image:Skel.png|thumb|right|A shape and its skeleton, computed with a topology-preserving thinning algorithm.]] In [[shape analysis]], '''skeleton''' (or '''topological skeleton''') of a [[shape]] is a thin version of that shape that is [[equidistant]] to its [[boundary (topology)|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 [[image representation|representation]] of the shape (they contain all the information necessary to reconstruct the shape). 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 skeleton]]s, [[morphological skeleton]]s, and [[SKIZ|skeletons by influence zones (SKIZ)]] (also known as [[Voronoi diagram]]). In the technical literature, the concepts of skeleton and [[medial axis|medial axis]] are used interchangeably by some authors<ref>([[#rjain1995|R. Jain 1995]]), Section 2.5.10, pg. 55.</ref><ref name="gonzales">([[#gonzales2001|Gonzales and Woods 2001]]), Section 11.1.5, pg. 650</ref><ref>http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf</ref><ref>([[#dougherty1992|Dougherty 1992]])</ref><ref>([[#ogniewicz1995|Ogniewicz 1995]])</ref>, while some other authors<ref name="jain">([[#ajain1989|A.K. Jain 1989]]), Section 9.9, pg. 382</ref><ref>([[#serra1982|Serra 1982]])</ref><ref name="sethian">([[#sethian1999|Sethian 1999]]), Section 17.5.2, pg. 234</ref> regard them as related, but not the same. Similarly, the concepts of ''skeletonization'' and [[thinning]] are also regarded as identical by some<ref name="gonzales"/>, and not by others<ref name="jain"/>. Skeletons have been used in several applications in [[computer vision]], [[image analysis]], and [[digital image processing]], including [[optical character recognition]], [[fingerprint recognition]], [[visual inspection]], [[pattern recognition]], and [[binary image]] [[image compression|compression]]. ==Mathematical Definitions== Skeletons have several different mathematical definitions in the technical literature; most of them lead to similar results in [[Continuum (mathematics)#Topology|continuous space]]s, but usually yield different results in [[discrete space]]s. ===Quench points of the fire propagation model=== In his seminal paper ([[#blum67|Blum 1967]]), H. Blum defines 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 discs (or balls)=== A [[disk (mathematics)|disc]] (or [[ball (mathematics)|ball]]) ''B'' is said to ''maximal'' in a set ''A'' if * <math>B\subseteq A</math>, and * If another disc ''D'' contains ''B'', then <math>D\not\subseteq A</math>. One way of defining the skeleton of a shape ''A'' is as the set of centers of all maximal discs in ''A''<ref>([[#ajain1989|ajain1989|A.K. Jain 1989]]), Section 9.9, pg. 387</ref>. ===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<ref name="gonzales543"/>. This assures that the skeleton points are equidistant from the shape boundary. ===Ridges of the distance function=== Many definitions of skeleton make use of the concept of [[distance function]], which is a function that map each point ''x'' inside a shape ''A'' to the distance of ''x'' 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 [[ridge]]s of the distance function, i.e., the points that are locally maximum<ref name="jain"/>. ===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]] [[set]]s. * Using morphological operators<ref name="gonzales543">([[#gonzales2001|Gonzales and Woods 2001]]), Section 9.5.7, pg. 543</ref> * Using curve evolution * Using level sets<ref name="sethian"/> * Finding ridge points on the distance function<ref name="jain"/> * "Peeling" the shape, without changing the topology, until convergence<ref>([[#ajain1989|A.K. Jain 1989]]), Section 9.9, pg. 389</ref> ==Notes== {{Reflist}} ==References== * <cite id=gonzles2001>Rafael C. Gonzales and Richard E. Woods, ''Digital Image Processing'', ISBN 0-201-18075-8 (2001)</cite> * <cite id=rjain1995>Ramesh Jain, Rangachar Kasturi and Brian G. Schunck, ''Machine Vision'', ISBN 0-07-032018-7 (1995)</cite> * <cite id=ajain1989>Anil K. Jain, ''Fundamentals of Digital Image Processing'', ISBN 0-13-336165-9 (1989)</cite> * <cite id=serra1982>Jean Serra, ''Image Analysis and Mathematical Morphology'', ISBN 0126372403 (1982)</cite> * <cite id=dougherty1992>Edward R. Dougherty, ''An Introduction to Morphological Image Processing'', ISBN 0-8194-0845-X (1992)</cite> * <cite id=sethian1999>J.A. Sethian, ''Level Set Methods and Fast Marching Methods'', ISBN 0-521-64557-3 (1999)</cite> * <cite id=petrou2006>Maria Petrou and Pedro García Sevilla''Image Processing Dealing with Texture'', ISBN-13: 978-0-470-02628-1, ISBN-10: 0-470-02628-6 (2006)</cite> * <cite id=ogniewicz1995>R.L. Ogniewicz, "Automatic Medial Axis Pruning Based on Characteristics of the Skeleton-Space", in ''Shape, Structure and Pattern Recognition'' (D. Dori and A. Bruckstein editors), ISBN 981-02-2239-4 (1995)</cite> * <cite id=blum67>"A Transformation for Extracting New Descriptors of Shape" by H. Blum, in ''Models for the Perception of Speech and Visual Form'', W. Whaten-Dunn (Ed.). MIT Press: Cambridge, MA, pp. 362–380</cite> ==See also== *[[Medial axis]] *[[Straight skeleton]] ==External links == *[http://www.cee.hw.ac.uk/hipr/html/skeleton.html Skeletonization/Medial Axis Transform] *[http://www.cs.ru.nl/~ths/rt2/col/h9/9gebiedENG.html#9.2.4 Skeletons of a region] *[http://www.citr.auckland.ac.nz/techreports/2002/CITR-TR-112.pdf Skeletons in Digital image processing (pdf)] *[http://www-igm.univ-mlv.fr/LabInfo/rapportsInternes/2006/01.pdf Comparision of 15 line thinning algorithms] *[http://mecca.louisville.edu/~msabry/projects/cskel.htm Skeletonization using Level Set Methods] *[http://www.cvip.uofl.edu/~msabry/home/Publications/Hassouna_Farag_ICCV_2007.pdf Curve Skeletons] *[http://mecca.louisville.edu/~msabry/projects/vcomparative.htm Comparative Study of Curve Skeleton Extraction Techniques.] [[Category:Image processing]] [[Category:Digital geometry]] [[fr:Squelettisation]]