Squelettisation

The squelettisation is a class of algorithms used in analysis of forms. It consists in reducing a form in a whole of curves, called skeletons , centered in the form of origin. The squelettisation is a tool for analysis of form not-scalar, which preserves the topological properties of the form of origin as well as the geometrical properties, according to the method employed.

N.B.: the term squelettisation is also used in surgery and means the interruption partial or complete of the blood contribution towards a structure in order to it exciser (appendicectomy) or to move it (lowering testiculaire).

Definitions and properties

Of simple terms, the squelettisation consists with to thin down a form until obtaining a whole of centered curves. The unit obtained is then called skeleton or median axis ( medial axis , in English).

There exist various definitions of the squelettisation.

The analogy of the fire of meadow

The definition below was stated by Harry Blum and is known under the name of analogy of the fire of meadow . It offers an intuitive vision of the squelettisation.

That is to say a covered meadow in a homogeneous way by dry grass and Ω a unit of points of this meadow. At the beginning, all the points of the contour of Ω are ignited simultaneously. Fire is propagated in a homogeneous way and extends through the meadow at a constant speed. the skeleton of the whole of points Ω (noted MY (Ω)) is defined like the place of the points or the ignited faces met.

Formal definition

There exists a formal definition of the skeleton based on the concept of maximum Boule. The skeleton of a form S , noted MY ( S ), is defined by the whole of the centers of the maximum balls in S :

Balanced skeleton

The skeleton balanced or the transformed median axis ( medial axis transform , in English) of a form S , noted CHECHMATE ( S ), is the whole of the couples made up of the center of the maximum balls of S and their ray.

Exosquelette and endosquelette

The skeletons are not only objects located inside the forms. If we begin again, the analogy of the fire of meadow, the process of squelettisation transforms not only the interior of the form, but also outside. One calls then endosquelette the part of the skeleton which is located inside the form and exosquelette the part of the skeleton which is located outside the form.

It often happens that confusion is made between skeleton and endosquelette, because this part of the skeleton is that which is studied in analysis of forms. Same manner, in this article, we consider that the skeletons correspond to the endosquelettes.

Properties of the skeletons

The skeletons have various interesting properties:

the skeletons are theoretically invariant by linear transformation (translation, rotation and scaling),
the squelettisation is a homotopic transformation: it preserves the topological property of the form.

Other properties are specific to the balanced skeletons:

all the balanced skeletons are single,
in the case of the balanced skeletons, the squelettisation is a reversible transformation, in the direction where it is possible to rebuild the form of origin starting from the balanced skeleton,
a balanced skeleton provides a hierarchical description of the form: the squelettaux points far away from contour describe the total aspect of the form and the squelettaux points close to contour describe characteristics appearing in contour.

Another property of the skeletons in general is regarded as a defect: the squelettisation is a semi-continuous transformation. Indeed, the least disturbance in contour or within the form can produce the creation of an important branch in the skeleton.

Methods of squelettisation

There exists currently a large variety of methods making it possible to build skeletons starting from forms. In the majority of the scientific publications, the methods of squelettisation can be classified according to four classes.

Topological thinning

Topological thinning consists in progressively withdrawing the points of the contour of the form, while preserving its topological characteristics. The squelettaux points are added progressively when there is formation of a corner (the curve of contour becomes discontinuous) or when the points of contour meet.

Extraction of the chart of distance

The Carte of distances of a form S consists in associating with each point S its distance to the point nearest to contour. Within a continuous framework, the maximum buildings of the chart of distance correspond exactly to the points of the skeleton of S .

Simulation of the ignited face

The methods proceeding by simulation of the ignited face are based on the analogy of the fire of meadow. They study the evolution of the face ignited during time. Each formation of shock in the face is added to the skeleton.

Analytical calculation

The research of the skeleton is compared to a geometrical problem. The methods of this class use geometrical tools such as the diagrams of Voronoï or the polygonation of contour (in the case of the squelettisation in discrete spaces).

Other criteria of classification

The methods of squelettisation can be classified according to the type of space to which they apply. Certain methods of squelettisation apply to continuous spaces. These methods are in general exact and precise. Other methods of squelettisation apply to discrete spaces. These methods are not exact that in certain cases and often require a succession of operations to refine the skeleton.

Certain methods of squelettisation apply to forms to a plan or objects in three dimensions and more.

Applications

The squelettisation knows many applications like the pattern recognition, the modeling of solids for the design and the handling of forms, the organization of groups of dots, the search for ways, animations, etc It is used in medicine and biology since its creation, like in mineralogy. Applications were found in the indexing of images in the databases and in compression. There exists if not some applications in architecture and town planning, within the morphological framework of analysis.

Researchers showed that, in the process of visual perception, our unconscious sensitivity is maximum on the level of the skeleton.

Origins

The squelettisation is a method which was developed at the origin in the Sixties by Harry Blum, in order to create a new descriptor of forms. This method gained the interest of many researchers. Currently, the squelettisation is a very known method in Analyze of image. There exists a great number of algorithm proposing to transform a form into skeleton.

Random links: