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 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, etc.

In the technical literature, the concepts of skeleton and medial axis are used interchangeably by some authors, while some other authors regard them as related, but not the same. Similarly, the concepts of skeletonization and thinning are also regarded as identical by some, and plant morphology on various biological scales.

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

  • <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 disks in A.

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

  • Supplementing morphological operators with shape based pruning
  • Using intersections of distances from boundary sections
  • Using curve evolution
  • Using level sets
  • Zhang-Suen Thinning Algorithm

Skeletonization algorithms can sometimes create unwanted branches on the output skeletons. Pruning algorithms are often used to remove these branches.

See also

  • Medial axis
  • Straight skeleton
  • β-skeleton
  • Grassfire Transform
  • Stroke-based fonts

Notes

References

  • .
  • .
  • .
  • .
  • .
  • .
  • .
  • .
  • .
  • .
  • .
  • .
  • .
  • .

Open source software

  • ITK (C++)
  • Skeletonize3D (Java)
  • Graphics gems IV (C)
  • EVG-Thin (C++)
  • NeuronStudio
  • Skeletonization/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)