Jump to content

Topological skeleton

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 71.146.74.108 (talk) at 15:53, 20 April 2010 (→‎Mathematical Definitions). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 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,[1][2][3][4][5] while some other authors[6][7][8] 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.[6]

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, binary image compression, and protein folding.[9]

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, Harry Blum (1967) of the Air Force Cambridge Research Laboratories in Cambridge, 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 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.[10]

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[11]. 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[6]. 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.

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.

  • Using morphological operators[11]
  • Supplementing morphological operators with shape based pruning [12]
  • Using curve evolution [13]
  • Using level sets[8]
  • Finding ridge points on the distance function[6]
  • "Peeling" the shape, without changing the topology, until convergence[14]

Notes

  1. ^ Jain, Kasturi & Schunck (1995), Section 2.5.10, p. 55.
  2. ^ a b Gonzales & Woods (2001), Section 11.1.5, p. 650
  3. ^ http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf
  4. ^ Dougherty (1992).
  5. ^ Ogniewicz (1995).
  6. ^ a b c d A. K. Jain (1989), Section 9.9, p. 382.
  7. ^ Serra (1982).
  8. ^ a b Sethian (1999), Section 17.5.2, p. 234.
  9. ^ Abeysinghe et al. (2008b).
  10. ^ A. K. Jain (1989), Section 9.9, p. 387.
  11. ^ a b Gonzales & Woods (2001), Section 9.5.7, p. 543.
  12. ^ Abeysinghe et al. (2008a).
  13. ^ Bai, Longin & Wenyu (2007).
  14. ^ A. K. Jain (1989), Section 9.9, p. 389.

References

  • Abeysinghe, Sasakthi; Baker, Matthew; Chiu, Wah; Ju, Tao (2008a), "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.
  • Abeysinghe, Sasakthi; Ju, Tao; Baker, Matthew; Chiu, Wah (2008b), "Shape modeling and matching in identifying 3D protein structures" (PDF), Computer-Aided Design, 40 (6), Elsevier: 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 Intellingence, 29 (3): 449–462, doi:10.1109/TPAMI.2007.59.
  • Blum, H., "A Transformation for Extracting New Descriptors of Shape", in Wathen-Dunn, W. (ed.), Models for the Perception of Speech and Visual Form, Cambridge, MA: MIT Press, pp. 362–380.
  • 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.
  • Gonzales, Rafael C.; Woods, Richard E. (2001), Digital Image Processing, ISBN 0-201-18075-8.
  • Jain, Anil K. (1989), Fundamentals of Digital Image Processing, ISBN 0-13-336165-9.
  • Jain, Ramesh; Kasturi, Rangachar; Schunck, Brian G. (1995), Machine Vision, ISBN 0-07-032018-7.
  • 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; García Sevilla, Pedro (2006), Image Processing Dealing with Texture, ISBN 978-0-470-02628-1.
  • Serra, Jean (1982), Image Analysis and Mathematical Morphology, ISBN 0126372403.
  • Sethian, J. A. (1999), Level Set Methods and Fast Marching Methods, ISBN 0-521-64557-3.

Open source software

See also

Retrieved from "https://en.wikipedia.org/w/index.php?title=Topological_skeleton&oldid=357222444"