Topological skeleton


Topological skeleton

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).

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, and skeletons by influence zones (SKIZ) (also known as Voronoi diagram).

In the technical literature, the concepts of skeleton and medial axis are used interchangeably by some authors [(R. Jain 1995), Section 2.5.10, pg. 55.] (Gonzales and Woods 2001), Section 11.1.5, pg. 650] [http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf] [(Dougherty 1992)] [(Ogniewicz 1995)] , while some other authors(A.K. Jain 1989), Section 9.9, pg. 382] [(Serra 1982)] (Sethian 1999), Section 17.5.2, pg. 234] regard them as related, but not the same. Similarly, the concepts of "skeletonization" and thinning are also regarded as identical by some, and not by others.

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 compression.

Mathematical Definitions

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.

Quench points of the fire propagation model

In his seminal paper (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 [http://en.wiktionary.org/wiki/quench 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 disc (or ball) "B" is said to "maximal" in a set "A" if

* Bsubseteq A, and
* If another disc "D" contains "B", then D otsubseteq A.

One way of defining the skeleton of a shape "A" is as the set of centers of all maximal discs in "A" [(ajain1989|A.K. Jain 1989), Section 9.9, pg. 387] .

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. 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 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, i.e., the points that are locally maximum.

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

keletonization Algorithms

There are many different algorithms for computing skeletons for shapes in digital images, as well as continuous sets.

* Using morphological operators(Gonzales and Woods 2001), Section 9.5.7, pg. 543]
* Using curve evolution
* Using level sets
* Finding ridge points on the distance function
* "Peeling" the shape, without changing the topology, until convergence [(A.K. Jain 1989), Section 9.9, pg. 389]

Notes

References

* Rafael C. Gonzales and Richard E. Woods, "Digital Image Processing", ISBN 0-201-18075-8 (2001)
* Ramesh Jain, Rangachar Kasturi and Brian G. Schunck, "Machine Vision", ISBN 0-07-032018-7 (1995)
* Anil K. Jain, "Fundamentals of Digital Image Processing", ISBN 0-13-336165-9 (1989)
* Jean Serra, "Image Analysis and Mathematical Morphology", ISBN 0126372403 (1982)
* Edward R. Dougherty, "An Introduction to Morphological Image Processing", ISBN 0-8194-0845-X (1992)
* J.A. Sethian, "Level Set Methods and Fast Marching Methods", ISBN 0-521-64557-3 (1999)
* 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)
* 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)
* "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

ee 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.]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Skeleton (disambiguation) — A skeleton is a biological system providing support in a living organism.Skeleton may also mean: *Human skeleton, human anatomy * Skeleton (category theory), in mathematics, every category has a skeleton in which no two distinct objects are… …   Wikipedia

  • N-skeleton — This article is not about the topological skeleton concept of computer graphics In mathematics, particularly in algebraic topology, the n skeleton of a topological space X presented as a simplicial complex (resp. CW complex) refers to the… …   Wikipedia

  • n-skeleton — This hypercube graph is the 1 skeleton of the tesseract. This article is not about the topological skeleton concept of computer graphics In mathematics, particularly in algebraic topology, the n skeleton of a topological space X presented as a …   Wikipedia

  • Straight skeleton — In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a… …   Wikipedia

  • List of topology topics — This is a list of topology topics, by Wikipedia page. See also: topology glossary List of general topology topics List of geometric topology topics List of algebraic topology topics List of topological invariants (topological properties)… …   Wikipedia

  • Medial axis — An ellipse (red), its evolute (blue), and its medial axis (green). The symmetry set, a super set of the medial axis is the green and yellow curves. One bi tangent circle is shown. The medial axis of an object is the set of all points having more… …   Wikipedia

  • Symmetry set — In geometry, the symmetry set is a method for representing the local symmetries of a curve, and can be used as a method for representing the shape of objects by finding the topological skeleton. The medial axis, a subset of the symmetry set is a… …   Wikipedia

  • Skeletonization — may refer to*Skeletonization (forensics), the final stage of decomposition of bony organisms. *Topological skeleton, a digital imaging method …   Wikipedia

  • CW complex — In topology, a CW complex is a type of topological space introduced by J. H. C. Whitehead to meet the needs of homotopy theory. This class of spaces is broader and has some better categorical properties than simplicial complexes, but still… …   Wikipedia

  • Obstruction theory — In mathematics, obstruction theory is a name given to two different mathematical theories, both of which yield cohomological invariants. Contents 1 In homotopy theory 2 In geometric topology 3 In surgery theory …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.