Le développement fulgurant de réseaux informatiques, a entraîné l'apparition de diverses applications multimédia qui emploient des données 3D dans des multiples contextes. Si la majorité des travaux de recherche sur ces données s'est appuyées sur les modèles statiques, c'est à présent vers Les modèles dynamiques de maillages qu'il faut se tourner. Cependant, le maillage triangulaire est une représentation extrinsèque, sensible face aux différentes transformations affines et isométriques. Par conséquent, il a besoin d'un descripteur structurel intrinsèque. Pour relever ces défis, nous nous concentrons sur la modélisation topologique intrinsèque basée sur les graphes de Reeb. Notre principale contribution consiste à définir une nouvelle fonction continue basée sur les propriétés de diffusion de la chaleur. Ce dernier est calculé comme la distance de diffusion d'un point de la surface aux points localisés aux extrémités du modèle 3D qui représentent l'extremum locales de l'objet . Cette approche de construction de graph de Reeb peut être extrêmement utile comme descripteur de forme locale pour la reconnaissance de forme 3D. Il peut également être introduit dans un système de compression dynamique basée sur la segmentation.Dans une deuxième partie, nous avons proposé d'exploiter la méthode de construction de graphe de Reeb dans un système de reconnaissance de formes 3D non rigides. L'objectif consiste à segmenter le graphe de Reeb en cartes de Reeb définis comme cartes de topologie contrôlée. Chaque carte de Reeb est projetée vers le domaine planaire canonique. Ce dépliage dans le domaine planaire canonique introduit des distorsions d'aire et d'angle. En se basant sur une estimation de distorsion, l'extraction de vecteur caractéristique est effectuée. Nous calculons pour chaque carte un couple de signatures, qui sera utilisé par la suite pour faire l'appariement entre les cartes de Reeb.Dans une troisième partie, nous avons proposé de concevoir une technique de segmentation, des maillages dynamiques 3D. Le processus de segmentation est effectué en fonction des valeurs de la fonction scalaire proposée dans la première partie. Le principe consiste à dériver une segmentation purement topologique qui vise à partitionner le maillage en des régions rigides tout en estimant le mouvement de chaque région au cours du temps. Pour obtenir une bonne répartition des sommets situés sur les frontières des régions, nous avons proposé d'ajouter une étape de raffinement basée sur l'information de la courbure. Chaque limite de région est associée à une valeur de la fonction qui correspond à un point critique. L'objectif visé est de trouver la valeur optimale de cette fonction qui détermine le profil des limites. La technique de segmentation développée est exploitée dans un système de compression sans perte des maillages dynamiques 3D. Il s'agit de partitionner la première trame de la séquence. Chaque région est modélisée par une transformée affine et leurs poids d'animation associés. Le vecteur partition, associant à chaque sommet l'index de la région auquel il appartient, est compressé par un codeur arithmétique. Les deux ensembles des transformées affines et des poids d'animation sont quantifiés uniformément et compressés par un codeur arithmétique. La première trame de la séquence est compressée en appliquant un codeur de maillage statique. L a quantification de l'erreur de prédiction temporelle est optimisée en minimisant l'erreur de reconstruction. Ce processus est effectué sur les données de l'erreur de prédiction, qui est divisé en 3 sous-bandes correspondant aux erreurs de prédiction des 3 coordonnées x, y et z. Le taux de distorsion introduit est déterminé en calculant le pas de quantification, pour chaque sous-bande, afin d'atteindre le débit binaire cible. / In the last decade, the technological progress in telecommunication, hardware design and multimedia, allows access to an ever finer three-dimensional (3-D) modeling of the world. While most researchers have focused on the field of 3D objects, now it is necessary to turn to 3D time domain (3D+t). 3D dynamic meshes are becoming a media of increasing importance. This 3D content is subject to various processing operations such as indexation, segmentation or compression. However, surface mesh is an extrinsic shape representation. Therefore, it suffers from important variability under different sampling strategies and canonical shape-non-altering surface transformations, such as affine or isometric transformations. Consequently it needs an intrinsic structural descriptor before being processed by one of the aforementioned processing operations. The research topic of this thesis work is the topological modeling based on Reeb graphs. Specifically, we focus on 3D shapes represented by triangulated surfaces. Our objective is to propose a new approach, of Reeb graph construction, which exploits the temporal information. The main contribution consists in defining a new continuous function based on the heat diffusion properties. The latter is computed from the discrete representation of the shape to obtain a topological structure.The restriction of the heat kernel to temporal domain makes the proposed function intrinsic and stable against transformation. Due to the presence of neighborhood information in the heat kernel, the proposed Reeb Graph construction approach can be extremely useful as local shape descriptor for non-rigid shape retrieval. It can also be introduced into a segmentation-based dynamic compression scheme in order to infer the functional parts of a 3D shape by decomposing it into parts of uniform motion. In this context, we apply the concept of Reeb graph in two widely used applications which are pattern recognition and compression.Reeb graph has been known as an interesting candidate for 3D shape intrinsic structural representation. we propose a 3D non rigid shape recognition approach. The main contribution consists in defining a new scalar function to construct the Reeb graph. This function is computed based on the diffusion distance. For matching purpose, the constructed Reeb graph is segmented into Reeb charts, which are associated with a couple of geometrical signatures. The matching between two Reeb charts is performed based on the distances between their corresponding signatures. As a result, the global similarity is estimated based on the minimum distance between Reeb chart pairs. Skeletonisation and segmentation tasks are closely related. Mesh segmentation can be formulated as graph clustering. First we propose an implicit segmentation method which consists in partitioning mesh sequences, with constant connectivity, based on the Reeb graph construction method. Regions are separated according to the values of the proposed continuous function while adding a refinement step based on curvature and boundary information.Intrinsic mesh surface segmentation has been studied in the field of computer vision, especially for compression and simplification purposes. Therefore we present a segmentation-based compression scheme for animated sequences of meshes with constant connectivity. The proposed method exploits the temporal coherence of the geometry component by using the heat diffusion properties during the segmentation process. The motion of the resulting regions is accurately described by 3D affine transforms. These transforms are computed at the first frame to match the subsequent ones. In order to improve the performance of our coding scheme, the quantization of temporal prediction errors is optimized by using a bit allocation procedure. The objective aimed at is to control the compression rate while minimizing the reconstruction error.

En ce moment même, d'énormes quantités de données sont générées, collectées et analysées. Dans de nombreux cas, ces données sont échantillonnées sur des objets à la structure géométrique particulière. De tels objets apparaissent fréquemment dans notre vie quotidienne. Utiliser ce genre de données pour inférer la structure géométrique de tels objets est souvent ardue. Cette tâche est rendue plus difficile encore si les objets sous-jacents sont abstraits ou encore de grande dimension. Dans cette thèse, nous nous intéressons à deux problèmes concernant l'analyse géométrique de données. Dans un premier temps, nous nous penchons sur l'inférence de la métrique de structures filamentaires. En supposant que ces structures sont des espaces métriques proches d'un graphe métrique nous proposons une méthode, combinant les graphes de Reeb et l'algorithme Mapper, pour approximer la structure filamentaire via un graphe de Reeb. Notre méthode peut de plus être facilement implémentée et permet de visualiser simplement le résultat. Nous nous concentrons ensuite sur le problème de la comparaison de formes. Nous étudions un ensemble de méthodes récentes et prometteuses pour la comparaison de formes qui utilisent la notion de carte fonctionnelles. Nos résultats théoriques montrent que ces approches sont stables et peuvent être utilisées dans un contexte plus général que la comparaison de formes comme la comparaison de variétés Riemanniennes de grande dimension. Enfin, en nous basant sur notre analyse théorique, nous proposons une généralisation des cartes fonctionnelles aux nuages de points. Bien que cette généralisation ne bénéficie par des garanties théoriques, elle permet d'étendre le champ d'application des méthodes basées sur les cartes fonctionnelles. / Massive amounts of data are being generated, collected and processed all the time. A considerable portion of them are sampled from objects with geometric structures. Such objects can be tangible and ubiquitous in our daily life. Inferring the geometric information from such data, however, is not always an obvious task. Moreover, it’s not a rare case that the underlying objects are abstract and of high dimension, where the data inference is more challenging. This thesis studies two problems on geometric data analysis. The first one concerns metric reconstruction for filamentary structures. We in general consider a filamentary structure as a metric space being close to an underlying metric graph, which is not necessarily embedded in some Euclidean spaces. Particularly, by combining the Reeb graph and the Mapper algorithm, we propose a variant of the Reeb graph, which not only faithfully approximates the metric of the filamentary structure but also allows for efficient implementation and convenient visualization of the result. Then we focus on the problem of shape comparison. In this part, we study the stability properties of some recent and promising approaches for shape comparison, which are based on the notion of functional maps. Our results show that these approaches are stable in theory and potential for being used in more general setting such as comparing high-dimensional Riemannian manifolds. Lastly, we propose a pipeline for implementing the functional-maps-based frameworks under our stability analysis on unorganised point cloud data. Though our pipeline is experimental, it undoubtedly extends the range of applications of these frameworks.

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.<br /><br />Nous présentons dans ce 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, 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.

Avec le développement récent des technologies 3D, les formes 3D sont devenues un type de données multimédia interactives de première importance. Leur représentation la plus courante, le maillage de polygones, souffre cependant de grande variabilité face à des transformations canoniques préservant la forme. Il est donc nécessaire de concevoir des techniques de modélisation intrinsèque de forme. Dans cette thèse, nous explorons la modélisation topologique par l'étude de structures basées sur les graphes de Reeb. En particulier, nous introduisons une nouvelle abstraction de forme, appelée squelette topologique avancé, qui permet non seulement l'étude de l'évolution topologique des lignes de niveau de fonctions de Morse mais aussi l'étude de leur évolution géométrique. Nous démontrons l'utilité de cette représentation intrinsèque de forme dans trois problèmes de recherche liés à l'Informatique Graphique et à la Vision par Ordinateur. Tout d'abord, nous introduisons la notion de calcul géométrique sur les graphes de Reeb pour le calcul automatique et stable de squelettes de con- trôle pour la manipulation interactive de forme. Ensuite, en introduisant les notions de cartes de Reeb et de motifs de Reeb, nous proposons une nouvelle méthode pour l'estimation de similarité partielle entre formes 3D. Nous montrons que cette approche dépasse les méthodes participant au concours international de reconnaissance de forme 2007 (SHREC 2007) par un gain de 14%. Enfin, nous présentons deux techniques permettant de fournir une dé- composition fonctionnelle d'une forme 3D, à la fois en considérant des heuristiques issues de la théorie de la perception humaine et des données 3D variant dans le temps. Des exemples applicatifs concrets viennent illustrer l'utilité de notre ap- proche pour chacun de ces problèmes de recherche.

Magnetic Resonance Imaging, Computed Tomography, and other image modalities are routinely used to visualize a particular structure in the patient's body. The classification of the image region corresponding to this structure is called segmentation. For applications in Neuroscience, it is important for the segmentation of a brain scan to represent the boundary of the brain as a folded surface with no holes. However the segmentation of the brain generally exhibits many erroneous holes. Consequently we have developed an algorithm for automatically correcting holes in segmented medical scans while preserving the accuracy of the segmentation. Upon concepts of Discrete Topology, we remove the holes based on the smallest modification to the image. First we detect each hole with a front propagation and a Reeb graph. Then we search for a number of loops around the hole on the isosurface of the image. Finally we correct the hole in the image using the loop that minimizes the modification to the image. At each step we limit the size of the data in memory. With these contributions our algorithm removes every hole in the image with high accuracy and low complexity even for images too large to fit into the main memory. To help doctors and scientists to obtain segmentations without holes, we have made our software publicly available at http://www.OpenTopology.org. / Les images par Résonance Magnétique, la Tomographie par Rayons X et les autres modalités d'imagerie médicale sont utilisées quotidiennement pour visualiser une structure particulière dans le corps du patient. La classification de la région de l'image qui correspond à cette structure s'appelle la segmentation. Pour des applications en Neuroscience, il est important que la segmentation d'une image du cerveau représente la surface extérieure du cerveau comme une surface pliée sans trous. Cependant la segmentation du cerveau présente généralement de nombreux trous. Par conséquent, nous avons développé un algorithme pour corriger automatiquement les trous dans les images médicales segmentées tout en préservant la précision de la segmentation. Sur des concepts de Topologie Discrète, nous enlevons les trous en fonction de la plus petite modification apportée à l'image. D'abord nous détectons chaque trou avec un certain nombre de boucles autour du trou sur l'isosurface de l'image. Finalement nous corrigeons le trou dans l'image en utilisant la boucle qui minimise la modification de l'image. A chaque étape, nous limitons la taille des données en mémoire. Grâce à ces contributions notre algorithme enlève tous les trous dans l'image avec une grande précision et une faible complexité même pour des images trop grandes pour tenir dans la mémoire de l'ordinateur. Pour aider les médecins et les chercheurs à obtenir des segmentations sans trous, nous avons rendu notre logiciel disponible publiquement à http://www.OpenTopology.org.