"Segmentation d'ensembles non-organisés de points
3-D d'une surface,
Propagation anisotrope basée sur les graphes"
Contexte
Mon travail de thèse s'est effectué au sein du Laboratoire d'Informatique Graphique, Images et Modélisation (LIGIM). Ces travaux s'inscrivent dans les domaines de l'analyse et de la description de surfaces numérisées en vue de leur reconstruction 3D.
Le travail que j'ai réalisé porte sur une
approche nouvelle du problème de l'analyse surfacique et de la segmentation
des ensembles de points non organisés d'une surface. Les données
dont nous disposons initialement correspondent aux coordonnées de
points 3-D appartenant à la surface d'un objet avec une certaine
précision. La saisie de ces points peut être opérée
au moyen de capteurs de diverses technologies. Pour englober l'objet et
saisir la totalité de sa complexité, plusieurs opérations
sont cependant nécessaires, entraînant des plages de recouvrement
entre les différentes nappes. Dans ces conditions, il n'est pas
toujours possible d'exploiter une organisation même partielle des
données. Le nuage formé par l'ensemble des points est dit
non-organisé et la démarche d'analyse ne peut en aucun cas
s'appuyer sur une régularité de leur distribution. A notre
connaissance, peu de techniques permettent de traiter ce type de données.
La plupart des méthodes apparentées s'appuient sur une structuration
en grille rectangulaire de données monovaluées (images de
profondeur). A la différence de ces méthodes, l'approche
proposée dans ma thèse permet le traitement d'objets fermés,
pouvant être composés de plusieurs parties distinctes, et
pouvant comporter des trous ou des discontinuités d'ordre variable.
Dans ma thèse, le problème de la segmentation de l'ensemble des points, en parties significatives de la surface sur laquelle ils ont été échantillonnés, se ramène à un problème d'étiquetage des points, de telle sorte que ceux appartenant à une même région reçoivent une même étiquette. Pour résoudre ce problème, j'ai mis en place un modèle d'évolution discret conduisant à une auto-organisation des étiquettes affectées aux points. Ce modèle est inspiré des idées de diffusion anisotrope qui ont été développées pour résoudre le problème de la restauration des images de niveau de gris. Pour cela, j'ai repris la notion de contrainte directionnelle portée par le terme de viscosité des équations de diffusion et je l'ai transposée dans le cadre d'une formalisation markovienne de l'étiquetage des points. En effet, le caractère discret d'un étiquetage n'est pas forcément adapté au formalisme continu des équations variationnelles. Les modèles d'évolution décrits par ces équations sont plus souvent utilisés à des fins de restauration que de classification. Le choix d'un modèle markovien est motivé par son formalisme discret et local qui permet de bien distinguer les contraintes de régularisation et d'attache aux données de l'étiquetage cherché.
Afin de palier ce problème, l'idée habituellement exploitée par les techniques de segmentation existantes consiste à ne regrouper des points dans une même région que sous certaines contraintes d'homogénéité globale de l'ensemble. Ce type d'approche nécessite généralement la définition d'un ou plusieurs modèles a priori pour les régions (segmentation en plans, cylindres, quadriques,...). Ainsi, la segmentation des images d'intensité peut généralement être interprétée comme une segmentation plane : au sein d'une région, les valeurs des pixels sont proches d'une valeur moyenne caractérisant la région. L'approche que j'ai développée dans ma thèse s'attache plutôt à décrire la caractérisation locale des frontières (réelles ou implicites) entre les régions, qu'à imposer un modèle pour les régions elles-mêmes. En effet, l'évaluation d'un critère d'homogénéité globale des régions est parfois coûteuse, et elle nécessite d'être mise en oeuvre chaque fois que l'on tente de fusionner des points ou des régions. Dans notre approche, les contraintes d'homogénéité globale des régions sont satisfaites de manière sous-jacente. Pour cela, les points sont traités dans un ordre particulier qui prend en compte les non-homogénéités de la surface et permet d'éviter le contournement d'indices de bord, lors de la croissance d'une région. Cet ordre de traitement dépend directement des caractéristiques intrinsèques de l'objet.
Plus précisément, l'idée que j'ai
mise en oeuvre consiste à réduire, voire bloquer, la propagation
des régions dans les directions de grande déformation et
à favoriser leur diffusion dans les directions de plus faible déformation.
Pour cela, j'ai mis en place deux représentations particulières
de type arbre couvrant, qui modélisent les contraintes directionnelles
de propagation des étiquettes. Ces arbres couvrants sont appelés
Arbres d'Escarpement Extrémaux. Le plongement géométrique
de ces arbres dans l'ensemble des points caractérise localement
la forme de l'objet :
Sur le plan technique, ces arbres m'ont permis de
mettre en place des opérations de propagation d'étiquettes
simples et peu gourmandes en temps de calcul. En effet, les Arbres d'Escarpement
Extrémaux correspondent à la sélection préalable
de paires de points significatives et localement représentatives
des autres sur le plan géométrique. Au moment de l'étiquetage,
cette information globale permet de lever les ambiguïtés pouvant
résulter de l'anisotropie des contraintes locales d'étiquetage.
Ainsi, ma thèse défend l'idée que la segmentation
peut être résolue grâce à un double mécanisme
de propagation anisotrope des étiquettes le long des Arbres d'Escarpement
Extrémaux. Cette nouvelle approche a d'ores et déjà
été testée sur divers ensembles de points et a montré
son efficacité dans différents cas de figure.
La complexité numérique de ces opérations
peut encore être réduite grâce à un processus
de contraction hiérarchique des Arbres d'Escarpement Extrémaux
le long des régions émergentes. Le processus de contraction
que j'ai introduit préserve la structure d'arbre et permet de faire
évoluer les Arbres d'Escarpement Extrémaux vers une description
symbolique de plus haut niveau. Par ailleurs, l'état final des Arbres
d'Escarpement Extrémaux correspond à l'introduction d'un
modèle compact de la surface qui dépend des caractéristiques
intrinsèques à l'objet.
La soutenance
Président : Denis Vandorpe
Rapporteurs : Marc Berthod
Examinateurs : Saïda Bouakaz