Segmentation de maillages 3D par l’exemple

Grâce au développement de dispositifs d’acquisition de formes 3D et aux avancées dans les outils de modélisation interactive, le nombre et la diversité des bases de modèles 3D disponibles sur internet, comme la 3D Warehouse de SketchUp, sont en augmentation. L’analyse de haut niveau des formes 3D constitue une tâche primordiale dans de nombreuses applications. En effet, la modélisation de nouvelles formes par composition, l’édition de maillages ou la recherche par le contenu d’objets 3D, requièrent la compréhension de l’information sémantique associée à ces formes 3D. Cependant, la plupart des bases de modèles 3D accessibles en ligne ne contiennent pas ce genre d’information et ne permettent pas de déduire les relations entre les maillages des différents objets. Elles contiennent généralement peu d’information sémantique et ne disposent pas des décompositions cohérentes des modèles en leurs parties significatives. Or ceci peut s’avérer très utile si l’on veut créer de nouvelles formes par assemblage de parties de modèles existants.

En effet, ce type d’application requiert de segmenter les modèles en parties significatives (fonctionnelles), et de trouver quelles parties peuvent être mises en correspondance à travers la base de données. Cette application peut utiliser notamment une indexation de formes par parties et des algorithmes conçus pour extraire automatiquement les relations sémantiques et structurelles des modèles appartenant à ces grandes bases.

De tels algorithmes sont habituellement basés sur l’analyse des formes 3D. Cette analyse peut s’effectuer localement ou globalement. L’analyse locale est axée sur les propriétés locales de la surface de l’objet, comme l’estimation des tenseurs de courbure locale. Toutefois, cette approche locale peut s’avérer insuffisante pour décrire correctement la sémantique de l’objet. Les propriétés locales peuvent par contre être utiles dans une approche globale.

En effet, l’analyse globale d’une forme prend en compte la géométrie de l’objet en entier afin d’en extraire les propriétés globales inhérentes. Elle est utilisée pour calculer la segmentation de formes en parties significatives [AKM+06, Sha08], la segmentation de séquences de maillages [Arc11, ACH+13], la détection de symétrie [MPWC12] et la mise en correspondance de formes [vKZHCO11]. Ces méthodes peuvent servir à leur tour pour la reconnaissance de formes [TV08, QJQ08], l’indexation par parties [BMSF06] ou encore l’annotation sémantique [ARSF09]. Nous nous intéressons dans cette thèse à la segmentation de formes 3D, qui est un domaine de recherche très actif.

Les techniques de segmentation trouvent leur utilité dans de nombreuses applications : outre les application citées ci-dessus, elles sont aussi très efficaces dans les processus de modélisation et d’animation de modèles 3D. La tendance actuelle entraînée par la mise en place de grandes bases généralistes de modèles 3D, est de considérer un ensemble composé de plusieurs modèles similaires dans le processus de segmentation, au lieu de considérer chaque modèle séparément. Un tel procédé permet d’aboutir à des segmentations sémantiques cohérentes, plus robustes et moins biaisées par rapport à d’éventuelles irrégularités de la surface de l’objet.

L’objectif principal de la thèse est de concevoir et développer une méthode de segmentation d’un objet 3D en parties sémantiquement significatives. Celle-ci doit produire des résultats convenables dans un temps raisonnable. Comme les méthodes de segmentation individuelle ne peuvent pas satisfaire de telles exigences dans le cas général, nous avons choisi d’utiliser la connaissance de l’utilisateur pour remédier à ce problème. L’idée est de calculer une segmentation de chaque objet à partir de la donnée d’un modèle exemple appartenant à la même classe d’objets, celui-ci étant déjà segmenté en des parties sémantiques. L’approche reposera donc sur les propriétés caractéristiques des objets (symétries, courbures, distance géodésique, etc.) et sur l’information sémantique supplémentaire incorporée par l’utilisateur.

Une stratégie appropriée doit être mise en place pour déterminer les correspondances entre les parties fonctionnelles des objets à l’intérieur d’une même classe sémantique (chaise, table, humain, etc.). Pour aboutir à des résultats satisfaisants pour tous les types de modèles 3D, nous avons adopté deux démarches différentes selon que l’objet soit rigide (chaises, tables, vases, etc..) ou articulé (humains, quadrupèdes, pieuvres, etc..). Nous cherchons à obtenir :
– des segmentations cohérentes des modèles issus d’une même classe : la même étiquette sémantique doit être associée aux parties ayant la même fonctionnalité dans les différents modèles de la classe.
– un temps de réponse assez court pour que la méthode soit adaptée aux applications interactives.

Hormis la segmentation par l’exemple, les contributions de cette thèse sont les suivantes :
– Une extension de la méthode de segmentation par les marches aléatoires permettant une initialisation de la segmentation avec plusieurs germes par segment.
– Une méthode simple pour aligner deux objets 3D rigides appartenant à une même classe de modèles rigides. La méthode associe les parties fonctionnelles des deux modèles 3D entre elles.
– Un algorithme pour associer les parties du modèle exemple pré-segmenté à leurs homologues dans le modèle cible articulé . Comme les parties fonctionnelles des modèles articulés présentent généralement des variations de poses importantes, cet algorithme est basée sur la mise en correspondance des squelettes grossiers des objets.
– Un algorithme robuste et automatique localisant les germes sur le modèle cible. Ces germes utilisés comme entrée de l’algorithme des marches aléatoires conduisent à la segmentation significative du modèle cible et à la mise en correspondance des segments calculés et des segments du modèle exemple.
– Un processus original visant à améliorer les frontières des segments calculés pour les modèles rigides. Ce processus lisse les frontières et rétablit les adjacences des segments de chaque modèle cible en tenant compte des adjacences des segments du modèle exemple.

L’efficacité croissante des moyens d’acquisition de formes 3D et des logiciels de CAO est, pour une part, due à la bonne représentation numérique des objets tridimensionnels. Différentes structures de données ont été conçues pour être adaptées aux contextes d’acquisition et de création de ces objets ainsi qu’à leurs traitements. 0n distingue trois grands types de représentations :
– Les représentations volumiques, comme les voxels. Elles sont souvent utilisées dans des contextes de modélisation physique (imagerie médicale, analyse de données scientifiques, etc.).
– Les représentations surfaciques implicites. La surface S de l’objet 3D est définie comme l’isosurface de niveau zéro d’une fonction scalaire F : R³ → R, c.à.d, S = {(x, y, z) ∈ R³ | F(x, y, z) = 0}. Cette fonction F permet, en outre, de déterminer si un point de R³ est à l’intérieur du modèle et de calculer sa distance à la surface.
– Les représentations surfaciques explicites. Parmi ces représentations, on retrouve les maillages polygonaux et les surfaces paramétriques (NURBS, surfaces de subdivision, etc..). Par rapport aux NURBS et aux surfaces de subdivision, les maillages polygonaux n’ont pas de contraintes géométriques ou topologiques imposées et peuvent ainsi être considérés comme les plus flexibles des représentations surfaciques. Les triangles sont les primitives élémentaires les plus simples pour représenter les faces polygonales. En outre, tout maillage polygonal peut être ramené à un maillage triangulaire par une triangulation de chacune de ses faces, sans modifier la surface (cf. le tutoriel de Botsch et al. [BPR+06] pour une étude détaillée des maillages triangulaires et de leurs traitements géométriques).