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

- Mathematical definitions
- Quench points of the fire propagation model
- Centers of maximal disks (or balls)
- Centers of bi-tangent circles
- Ridges of the distance function
- Other definitions
- Skeletonization algorithms
- See also
- Notes
- References
- Open source software
- External links

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] }^{ [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 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 ^{ [9] } and plant morphology on various biological scales.^{ [10] }

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^{ [11] } 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.

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*.^{ [12] }

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.^{ [13] } This definition assures that the skeleton points are equidistant from the shape boundary and is mathematically equivalent to Blum's medial axis transform.

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

- 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

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

- Using morphological operators (See Morphological skeleton
^{ [13] }) - Supplementing morphological operators with shape based pruning
^{ [14] } - Using intersections of distances from boundary sections
^{ [15] } - Using curve evolution
^{ [16] }^{ [17] } - Using level sets
^{ [8] } - Finding ridge points on the distance function
^{ [6] } - "Peeling" the shape, without changing the topology, until convergence
^{ [18] }

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

- ↑ Jain, Kasturi & Schunck (1995), Section 2.5.10, p. 55.
- 1 2 Gonzales & Woods (2001), Section 11.1.5, p. 650
- ↑ http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf
- ↑ Dougherty (1992).
- ↑ Ogniewicz (1995).
- 1 2 3 4 A. K.Jain ( 1989 ), Section 9.9, p. 382.
- ↑ Serra (1982).
- 1 2 Sethian (1999), Section 17.5.2, p. 234.
- ↑ Abeysinghe et al. (2008)
- ↑ Bucksch (2014)
- ↑ HarryBlum ( 1967 )
- ↑ A. K.Jain ( 1989 ), Section 9.9, p. 387.
- 1 2 Gonzales & Woods (2001), Section 9.5.7, p. 543.
- ↑ Abeysinghe et al. (2008).
- ↑ R. Kimmel, D. Shaked, N. Kiryati, and A. M. Bruckstein. https://www.cs.technion.ac.il/~ron/PAPERS/skeletonization_CVIU_1995.pdf Comp. Vision and Image Understanding, 62(3):382-391, 1995.
- ↑ Tannenbaum (1996)
- ↑ Bai, Longin & Wenyu (2007).
- ↑ A. K.Jain ( 1989 ), Section 9.9, p. 389.

In mathematics, a **Voronoi diagram** is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane. For each seed there is a corresponding region consisting of all points of the plane closer to that seed than to any other. These regions are called Voronoi cells. The Voronoi diagram of a set of points is dual to its Delaunay triangulation.

**Mathematical morphology** (**MM**) is a theory and technique for the analysis and processing of geometrical structures, based on set theory, lattice theory, topology, and random functions. MM is most commonly applied to digital images, but it can be employed as well on graphs, surface meshes, solids, and many other spatial structures.

In geometry, the **incenter** of a triangle is a triangle center, a point defined for any triangle in a way that is independent of the triangle's placement or scale. The incenter may be equivalently defined as the point where the internal angle bisectors of the triangle cross, as the point equidistant from the triangle's sides, as the junction point of the medial axis and innermost point of the grassfire transform of the triangle, and as the center point of the inscribed circle of the triangle.

**Digital geometry** deals with discrete sets considered to be digitized models or images of objects of the 2D or 3D Euclidean space.

In geometry, a **locus** is a set of all points, whose location satisfies or is determined by one or more specified conditions.

A **distance transform**, also known as **distance map** or **distance field**, is a derived representation of a digital image. The choice of the term depends on the point of view on the object in question: whether the initial image is transformed into another representation, or it is simply endowed with an additional map or field.

In geometry, a **simple polygon** is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If the sides intersect then the polygon is not simple. The qualifier "simple" is frequently omitted, with the above definition then being understood to define a polygon in general.

In computer vision and image processing **feature detection** includes methods for computing abstractions of image information and making local decisions at every image point whether there is an image feature of a given type at that point or not. The resulting features will be subsets of the image domain, often in the form of isolated points, continuous curves or connected regions.

A point is said to be **equidistant** from a set of objects if the distances between that point and each object in the set are equal.

**Pickover stalks** are certain kinds of details to be found empirically in the Mandelbrot set, in the study of fractal geometry. They are so named after the researcher Clifford Pickover, whose "epsilon cross" method was instrumental in their discovery. An "epsilon cross" is a cross-shaped orbit trap.

The **pruning** algorithm is a technique used in digital image processing based on mathematical morphology. It is used as a complement to the skeleton and thinning algorithms to remove unwanted parasitic components (spurs). In this case 'parasitic' components refer to branches of a line which are not key to the overall shape of the line and should be removed. These components can often be created by edge detection algorithms or digitization. Common uses for pruning include automatic recognition of hand-printed characters. Often inconsistency in letter writing creates unwanted spurs that need to be eliminated for better characterization.

The **medial axis** of an object is the set of all points having more than one closest point on the object's boundary. Originally referred to as the topological skeleton, it was introduced by Blum as a tool for biological shape recognition. In mathematics the closure of the medial axis is known as the cut locus.

**NeuronStudio** is a non-commercial program created at Icahn School of Medicine at Mount Sinai by the Computational Neurobiology and Imaging Center. This program performs automatic tracing and reconstruction of neuron structures from confocal image stacks. The resulting model can then be exported to a file using standard formats for further processing, modeling, or for statistical analyses.

**Ridge detection** is the attempt, via software, to locate ridges in an image.

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 polygon may involve parabolic curves. However, both are homotopy-equivalent to the underlying polygon.

In digital image processing, **morphological skeleton** is a skeleton representation of a shape or binary image, computed by means of morphological operators.

**Mathematical diagrams**, such as charts and graphs, are mainly designed to convey mathematical relationships—for example, comparisons over time.

In image processing, the **grassfire transform** is the computation of the distance from a pixel to the border of a region. It can be described as "setting fire" to the borders of an image region to yield descriptors such as the region's skeleton or medial axis. Harry Blum introduced the concept in 1967.

**Franz-Erich Wolter** is a German computer scientist, chaired professor at Leibniz University Hannover, with research contributions especially in computational (differential) geometry and haptic/tactile Virtual reality.

**Discrete Skeleton Evolution** (**DSE**) describes an iterative approach to reducing a morphological or topological skeleton. It is a form of pruning in that it removes noisy or redundant branches (spurs) generated by the skeletonization process, while preserving information-rich "trunk" segments. The value assigned to individual branches varies from algorithm to algorithm, with the general goal being to convey the features of interest of the original contour with a few carefully chosen lines. Usually, clarity for human vision is valued as well. DSE algorithms are distinguished by complex, recursive decision-making processes with high computational requirements. Pruning methods such as by structuring element (SE) convolution and the Hough transform are general purpose algorithms which quickly pass through an image and eliminate all branches shorter than a given threshold. DSE methods are most applicable when detail retention and contour reconstruction are valued.

- 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, ISBN 978-1-4244-2260-9 . - 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 . - 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 . - 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 . - 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 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 .

- ITK (C++)
- Skeletonize3D (Java)
- Graphics gems IV (C)
- EVG-Thin (C++)

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.