Squelettisation

La squelettisation est une classe d'algorithmes utilisée en analyse de formes. Elle consiste à diminuer une forme en un ensemble de courbes, nommées squelettes, centrées dans la forme d'origine.



Catégories :

Traitement d'image

Page(s) en rapport avec ce sujet :

  • la squelettisation est idempotente : Sq (Sq (X) ) = Sq (X)... Squelette par zone d'influence (SKIZ). Soit X un ensemble constitué de sous-ensembles X... (source : ufrsciencestech.u-bourgogne)
  • Squelettes : motivations. L'objectif de la squelettisation est de représenter un ensemble avec un minimum d'information, sous une forme qui soit à la fois... (source : lita.univ-metz)
  • de comparer les objets qu'on veut analyser à une forme connue.... Propriété algébrique du squelette : La squelettisation est anti-extensive :... (source : enise)
Exemples de squelettes pour des formes simples.

La squelettisation est une classe d'algorithmes utilisée en analyse de formes. Elle consiste à diminuer une forme en un ensemble de courbes, nommées squelettes, centrées dans la forme d'origine. La squelettisation est un outil d'analyse de forme non-scalaire, qui conserve les propriétés topologiques de la forme d'origine mais aussi les propriétés géométriques, selon la méthode employée.

N. B.  : Le terme squelettisation est aussi utilisé en chirurgie et veut dire l'interruption partielle ou complète de l'apport sanguin vers une structure pour l'exciser (appendicectomie) ou de la déplacer (abaissement testiculaire).

Définitions et propriétés

En termes simples, la squelettisation consiste à amaigrir une forme jusqu'à obtenir un ensemble de courbes centrées. La totalité obtenu est alors nommé squelette ou axe médian (medial axis, en anglais).

Il existe différentes définitions de la squelettisation.

L'ressemblance du feu de prairie

La définition ci-dessous a été énoncée par Harry Blum et est connue sous le nom d'ressemblance du feu de prairie. Elle offre une vision intuitive de la squelettisation.

Évolution du front enflammé dans une forme.

Soit une prairie couverte de manière homogène par de l'herbe sèche et Ω un ensemble de points de cette prairie. Au départ, l'ensemble des points du contour de Ω sont enflammés simultanément. Le feu se propage de manière homogène et couvre à travers la prairie à une vitesse constante. le squelette de la totalité de points Ω (noté MA (Ω) ) est défini comme le lieu des points ou les fronts enflammés se sont rencontrés.

Définition formelle

Il existe une définition formelle du squelette basée sur la notion de boule maximale. Le squelette d'une forme S, noté MA (S), est défini par la totalité des centres des boules maximales dans S :

Squelette pondéré

Le squelette pondéré ou la transformée de l'axe médian (medial axis transform, en anglais) d'une forme S, noté MAT (S), est la totalité des couples composés du centre des boules maximales de S et de leur rayon.

Exosquelette et endosquelette

Les squelettes ne sont pas uniquement des objets localisés au sein des formes. Si nous reprenons, l'ressemblance du feu de prairie, le processus de squelettisation transforme non seulement l'intérieur de la forme, mais également l'extérieur. On nomme alors endosquelette la partie du squelette qui se situe au sein de la forme et exosquelette la partie du squelette qui se situe hors de la forme.

Il arrive fréquemment que la confusion soit faite entre squelette et endosquelette, car cette partie du squelette est celle qui est la plus étudiée en analyse de formes. De la même manière, dans cet article, nous considérons que les squelettes correspondent aux endosquelettes.

Propriétés des squelettes

Les squelettes possèdent différentes propriétés intéressantes :

D'autres propriétés sont spécifiques aux squelettes pondérés :

Une autre propriété des squelettes généralement est reconnue comme un défaut : la squelettisation est une transformation semi-continue. En effet, la moindre perturbation dans le contour ou au sein de la forme peut produire la création d'une branche importante dans le squelette.

Méthodes de squelettisation

Il existe aujourd'hui une grande variété de méthodes servant à construire des squelettes à partir de formes. Dans la majorité des publications scientifiques, les méthodes de squelettisation peuvent être classées selon quatre classes.

Amincissement topologique

L'amincissement topologique consiste à retirer au fur et à mesure les points du contour de la forme, tout en préservant ses caractéristiques topologiques. Les points squelettaux sont rajoutés au fur et à mesure quand il y a formation d'un coin (la courbe du contour devient discontinue) ou quand les points du contour se rejoignent.

Extraction de la carte de distance

Carte de distance pour une forme.

La carte de distances d'une forme S consiste à associer à chaque point de S sa distance au point le plus proche du contour. Dans un cadre continu, les maxima locaux de la carte de distance correspondent précisément aux points du squelette de S.

Simulation du front enflammé

Les méthodes procédant par simulation du front enflammé se basent sur l'ressemblance du feu de prairie. Elles étudient l'évolution du front enflammé au cours du temps. Chaque formation de choc dans le front est ajouté au squelette.

Calcul analytique

La recherche du squelette est assimilé à un problème géométrique. Les méthodes de cette classe utilisent des outils géométriques tels que les diagrammes de Voronoï ou la polygonisation du contour (dans le cas de la squelettisation dans les espaces discrets).

Autres critères de classement

Les méthodes de squelettisation peuvent être classées selon le type d'espace auquel elles s'appliquent. Certaines méthodes de squelettisation s'appliquent à des espaces continus. Ces méthodes sont généralement exactes et précises. D'autres méthodes de squelettisation s'appliquent aux espaces discrets. Ces méthodes ne sont exactes que occasionnellementet nécessitent fréquemment une succession d'opérations pour affiner le squelette.

Certaines méthodes de squelettisation s'appliquent à des formes sur un plan ou à des objets en trois dimensions et plus.

Applications

La squelettisation connaît énormément d'applications comme la reconnaissance de formes, la modélisation de solides pour la conception et la manipulation de formes, l'organisation de nuages de points, la recherche de chemins, les animations, etc. Elle est utilisée en médecine et en biologie depuis sa création, ainsi qu'en minéralogie. Des applications ont été trouvées dans l'indexation d'images dans les bases de données et en compression. Il existe sinon quelques applications en architecture et en urbanisme, dans le cadre d'analyse morphologique.

Des chercheurs ont montré que, dans le processus de vision visuelle, notre sensibilité inconsciente est maximale au niveau du squelette.

Origines

La squelettisation est une méthode qui a été développée à l'origine dans les années soixante par Harry Blum, en vue de créer un nouveau descripteur de formes. Cette méthode a gagné l'intérêt de nombreux chercheurs. Aujourd'hui, la squelettisation est une méthode particulièrement connue en analyse d'image. Il existe la plupart d'algorithmes proposant de transformer une forme en squelette.

Bibliographie

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Squelettisation.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu