Ph.D. in Signal and Image Processing

3D indexing of Object Databases using Enhanced Reeb Graphs

Indexation 3D de Bases de Données d'Objets par Graphes de Reeb Améliorés

Thèse de l'ENST Paris

Département Traitement du Signal et des Images

Soutenue le 10 juin 2005 - Mention très honorable

Jury

Pr. Françoise Prêteux, INT Evry - Présidente

Pr. Atilla Baskurt, CNRS/INSA Lyon - Rapporteur

Pr. Mohamed Daoudi, CNRS/Télécom Lille 1 - Rapporteur

Pr. Frédéric Jurie, CNRS/INRIA Grenoble - Examinateur

Pr. Francis Schmitt, CNRS/ENST Paris - Directeur de thèse

Télécharger la thèse : [pdf 26 M]

Résumé (--> See Ph.D. abstract in English)

La rapide avancée de la technologique numérique a permis d'améliorer les méthodes d'acquisition et de rendu de modèles 3D. On peut constater qu'aujourd'hui les bases de données d'objets 3D sont présentes dans beaucoup de domaines, qu'ils soient ludiques (jeux, multimédia) ou scientifiques (applications médicales, industrielles, héritage culturel, etc.). La facilité d'acquisition et de reconstruction des modèles 3D, ainsi que leur modélisation permettent de créer de grandes bases de données, et il devient difficile de naviguer dans ces bases pour retrouver des informations. L'indexation des objets 3D apparaît donc comme une solution nécessaire et prometteuse pour gérer ce nouveau type de données. Notre étude s'insérant dans le cadre du projet européen SCULPTEUR IST-2001-35372 dont des partenaires étaient des musées, nous avons donc travaillé avec des bases de données de modèles 3D muséologiques. L'indexation des éléments d'une base de données consiste à définir une méthode permettant d'effectuer des comparaisons parmi les composants de cette base. Actuellement, une des principales applications consiste à effectuer des requêtes de similarité : étant donné une "clé'' de recherche, on extrait de la base de données les éléments ayant la clé la plus similaire.

Nous présentons dans le mémoire une méthode d'indexation de modèles 3D appliquée aux recherches par similarité de forme et d'aspect dans des bases de données d'objets 3D. L'approche repose sur la méthode d'appariement de graphes de Reeb multirésolution proposée par [Hilaga et al, SIGGRAPH'01]. Dans le cadre de notre étude, nous travaillons avec des maillages de modèles 3D de géométrie plus ou moins complexes, à différents niveaux de résolution, et parfois texturés. L'approche originale, basée sur la topologie des objets 3D, s'est avérée insuffisante pour obtenir des appariements satisfaisants. C'est pourquoi nous proposons d'étendre les critères de cohérence topologique pour les appariements et de fusionner au graphe des informations géométriques et visuelles pour améliorer leur mise en correspondance et l'estimation de la similarité entre modèles. Ces attributs sont librement pondérables afin de s'adapter au mieux aux requêtes d'un utilisateur. Nous obtenons une représentation souple, multicritère et multirésolution que nous nommons graphe de Reeb multirésolution augmenté (aMRG). Nous comparons cette approche à un ensemble varié de méthodes d'indexation. Elle se révèle être très performante pour retrouver les objets de formes similaires et discerner les différentes classes de formes 3D.

Mot-clés

3D, indexation, descripteurs de forme, graphe de Reeb multirésolution, base de données

Directeur de la thèse

Pr. Francis SCHMITT

Publications

Code

Graphes de Reeb améliorés

Construction du graphe de Reeb multirésolution augmenté du modèle déesse à la résolution 5: a) modèle déesse; b) calcul d'une fonction sur la surface du modèles; c) construction des graphes de Reeb à différents niveaux de résolution; d) calcul d'attributs topologiques, géométriques et colorimétriques.

Nous nous sommes intéressés à une approche consistant à évaluer la similarité de graphes extraits d'objets 3D proposée par [Hilaga et al., SIGGRAPH'01]. Elle consiste à calculer des graphes de Reeb multirésolution (ou MRG) à partir des maillages des modèles 3D, et à appliquer un processus d'appariement topologique des graphes, puis à évaluer la similarité des formes des modèles en utilisant une fonction de coût. La méthode, robuste et sophistiquée, nous a séduit par la richesse des informations capturées par la représentation multirésolution des MRG. En effet les graphes MRG capturent des informations liées à la topologie des objets et décrivent bien la forme des objets de manière intuitive. Leur construction repose sur la théorie mathématique de Morse, et donc sur une fonction Mu calculée sur la surface des objets. Un choix adéquat de la fonction Mu permet d'obtenir des propriétés d'invariance géométrique de la représentation par graphe vis-à-vis de l'orientation des modèles et des propriétés de robustesse en cas de bruit sur la représentation utilisée pour les modèles.

L'étude des différentes méthodes d'indexation 3D et des travaux originaux de [Hilaga et al., SIGGRAPH'01] nous a permis de connaître les avantages et limites des MRG et nous a conduit vers les solutions que nous proposons pour améliorer certains aspects de la méthode. Ainsi, nous avons renforcé la robustesse de la procédure d'appariement des graphes MRG et introduit des informations (ou attributs) topologiques dans les noeuds des graphes. Nous avons également ajouté des attributs géométriques globaux et locaux ainsi que des attributs colorimétriques, tout en profitant des aspects multirésolutions des MRG, pour améliorer la discrimination des formes 3D similaires. Chaque attribut apporte un type d'information lié à la forme ou à l'aspect d'une partie de l'objet. Notre idée principale a été d'utiliser les graphes de Reeb multirésolution comme support et de fusionner un ensemble de données, choisies par la pertinence de leur pouvoir descriptif, afin d'obtenir une caractérisation complète et précise des objets. Ces graphes ainsi enrichis sont appelés graphes de Reeb multirésolution augmentés (ou aMRG).

Afin d'évaluer l'efficacité des aMRG nous avons développé un banc de tests comprenant des bases de données d'objets 3D de complexités différentes et mis en oeuvre divers outils visuels et qualitatifs. Plusieurs autres méthodes d'indexation 3D ont été implémentés à titre informatif et comparatif. De plus nous avons étudié les résultats des calculs de similarité avec différentes mesures de distance.

Les résultats expérimentaux obtenus s'avèrent favorables à la méthode des aMRG que nous proposons et sont très prometteurs. Les aMRG possèdent un fort pouvoir discriminant et selon nos tests, permettent de retrouver efficacement les objets et classes d'objets similaires. De plus, nous proposons trois applications exploitant l'habileté des aMRG: la recherche basée sur la forme et la couleur, la recherche de parties d'objets, et la recherche 2D/3D.

Courbes de précision-rappel des méthodes d'indexation 3D sur des bases de données de 116 et 266 objets classés en 16 et 27 classes respectivement. La méthode aMRG donne les meilleurs résultats (courbes les plus hautes) comparé aux autres méthodes implémentées.

Exemples de requêtes sur une base de données comprenant 567 objets (266 objets classés et 301 d'aucune classe).