Retour Accueil A2SI Points P-simples Recherche Points simples

Algorithmes de squelettisation 3D

Personnes impliquées : Zouina Aktouf, Gilles Bertrand, Christophe Lohou.


Un algorithme de squelettisation réduit un objet sans changer sa topologie. Pour cela on enlève des points de l'objet qui sont simples et qui satisfont certaines conditions dites ``géométriques''. En 3 dimensions le choix des conditions géométriques permet de réduire l'objet en des surfaces (on a alors un squelette surfacique) ou bien en des courbes (on a un squelette curviligne). Contrairement au cas 2D, il n'existe que peu d'algorithmes de squelettisation en 3D. Certains sont des algorithmes non valides [BM95] (ils changent, dans certaines configurations, la topologie de l'objet), d'autres s'appuient sur une condition suffisante mais pas nécessaire pour caractériser les points simples; il s'ensuit que le squelette obtenu contient des points inutiles.

Nous proposons plusieurs algorithmes parallèles de squelettisation 3D qui s'appuient sur les deux nombres topologiques présentés ci-dessus. Ces deux nombres permettent de détecter les points simples et de disposer de conditions géométriques conduisant à un squelette surfacique ou curviligne. Par exemple, nous avons proposé un algorithme qui utilise une décomposition en sous-mailles de la maille cubique initiale [Akt97].

Dans le cadre des ordres (voir la section ``Ordres et topologie numérique''), nous avons proposé des algorithmes de squelettisation parallèles particulièrement simples et efficaces, assurant de plus un parfait centrage du squelette par rapport à l'objet original. Des conditions caractéristiques d'extrémités de courbes ou de bords de surfaces permettent d'obtenir des squelettes curvilignes ou surfaciques (Fig. 4).

 

Figure Figure
(a) (b)

Figure Figure
(c) (d)


Figure 4: (a): Objet original, (b): squelette surfacique, (c): squelette curviligne, (d): noyau homotopique.