La compression est un incontournable lorsque des modèles triangulaires 3D massifs doivent être transmis via un réseau de communication. La compression se doit d'être sans perte lorsque les modèles sont utilisés à des fins métrologiques. Cependant, les modèles capturés par scanneurs 3D contiennent généralement des artefacts de numérisation tels que la présence de trous dans le maillage, de petits regroupements distincts de triangles sous forme de surfaces ou de volumes ainsi que de singularités non-manifold (c.-à-d. un sommet appartenant à deux regroupement de triangles distincts). Ces aberrations rendent les techniques de compression standards inaptes à compresser sans échec le modèle. Ce mémoire propose une extension à une technique de compression et décompression sans perte des données topologiques nommée Edgebreaker. Le remplissage des trous par l'addition d'un sommet, l'insertion de faces triangulaires afin de lier les îlots ainsi que la duplication des sommets non-manifold sont proposées comme étapes de prétraitement afin de rendre le modèle compatible avec l'approche standard d'Edgebreaker. Les résultats obtenus démontrent que la solution proposée permet la compression sans perte de modèles hautement bruités à de hauts taux de compression. Les taux de compression résultants obtenus par notre approche se comparent également avec les taux observables pour des modèles sans imperfections compressés par Edgebreaker.

Une conséquence du lemme de Céa permet de déterminer l’ordre de convergence optimal d’une solution estimée par la méthode des éléments finis. L’hypothèse importante qui est faite pour obtenir cette convergence est que la solution doit être suffisamment régulière. Dans ce mémoire, nous montrerons l’impact de l’adaptation sur la convergence de problèmes de diffusion ayant une singularité dans leur gradient. Afin de retrouver l’ordre optimal de la méthode sur des problèmes où cette hypothèse est fausse, nous développerons une méthode d’adaptation de maillage faite a posteriori, c’est-à-dire que l’on doit déjà avoir une approximation initiale de la solution pour l’utiliser. L’adaptation est dite hiérarchique et utilise le fait qu’une meilleure approximation peut être trouvée à partir de l’approximation initiale. Cette méthode est en développement depuis quelques années et a été étudiée en détail dans la thèse de Bois [2].

L’adaptation de maillages anisotrope permet d’améliorer grandement la précision de méthodes numériques telles que la méthode des éléments finis. L’adaptation peut être très coûteuse en temps de calcul, mais montre un grand potentiel de parallélisation. Ce projet consiste à développer une implémentation parallèle de l’adaptation de maillages anisotrope basée sur des estimateurs métrique et hiérarchique. On introduit les notions de base de l’adaptation et de la programmation parallèle. On développe une stratégie de parallélisation applicable à la fois en deux dimensions et en trois dimensions. Enfin, on applique cette stratégie dans le cadre de la méthode des éléments finis dans le but d’en évaluer l’efficacité et la rapidité.

Ce mémoire porte sur l'adaptation de maillage par métrique. Plus précisément, on s'intéresse à développer la métrique discutée dans l'article [10] de Pagnutti & Ollivier-Gooch puis à voir l'amélioration d'une telle méthode d'adaptation de maillage sur la résolution numérique d'une équation aux dérivées partielles par éléments finis. On présente d'abord l'intuition derrière l'adaptation de maillage par métrique, d'où on introduit une approximation de l'erreur d'interpolation. On parle de la convergence d'une solution numérique. Pour se mettre en situation de maillage par métrique classique et l'adaptation hiérachique. Puis, au vif du sujet, on explique l'approche de l'adaptation de maillage de Pagnutti & Ollivier-Gooch. On parle aussi des actions permettant d'adapter nos maillages. Enfin, on résout numériquement des équations aux dérivées partielles avec opérateur laplacien par la méthode des élments finis sur des maillages uniformes et adaptés par nos 3 méthodes d'adaptation. On y considère des cas 1D, 2D et 3D.

L'objectif de ce mémoire est de présenter une méthode d'adaptation de maillage pour la méthode des éléments finis plus efficace que les méthodes dont on dispose actuellement. C'est d'autant plus important en dimension 3 puisque les problèmes rencontrés sont naturellement plus complexes et demandent de grandes ressources computationnelles. On présentera d'abord quelques notions essentielles et on étudiera plus particulièrement les méthodes d'adaptation existantes avant d'approfondir notre méthode. Celle-ci se base sur un estimateur d'erreur hiérarchique et montre des différences marquées avec les méthodes classiques. On fera donc la construction de l'estimateur en 2D avant de généraliser l'idée en 3D et d'expliquer le cadre dans lequel cet estimateur guide l'adaptation. Après avoir abordé certains aspects spécifiques de notre méthode, on fournira enfin des résultats numériques permettant entre autres de la comparer avec l'adaptation avec métrique.

Les méthodes de tatouage actuelles pour les maillages surfaciques 3D<br />sont essentiellement le fait de la communauté CAO, et sont assez peu<br />adaptées à une étude en termes de tatouage. Dans un premier temps, nous<br />avons abordé dans ce travail le tatouage par invariants géométriques,<br />dédié aux applications de tatouage fragile. Dans un deuxième temps, nous<br />avons utilisé l'espace de la décomposition spectrale de la géométrie<br />afin d'y enfouir une marque que nous voulons robuste face à la<br />quantification des coefficients spectraux. <br />En tatouage fragile, nous proposons notamment une approche flexible et<br />modulaire permettant l'analyse fine, d'un point de vue du tatouage, des<br />performances de notre méthode (classe de robustesse, probabilité de<br />fausse alarme, etc.) Les applications visées par cette approche<br />concernent tant la stéganographie que l'intégrité ou l'authentification<br />des maillages. Nous décrivons une méthode de tatouage fragile pour<br />l'authentification construite avec les modules que nous présentons. <br />Le tatouage dans l'espace de la décomposition spectrale de la géométrie,<br />à travers son étude face à la compression, implique le développement<br />d'un codeur de source géométrique spectral. Nous étudions les<br />difficultés liées à l'implantation d'une telle décomposition, tant pour<br />le codage de source que pour le tatouage. Nous terminons en montrant que<br />notre schéma de tatouage se révèle robuste face à la compression<br />géométrique spectrale.

L'évolution de l'infographie et des techniques de numérisation a récemment ouvert la voie à une modélisation tridimensionnelle du monde qui nous entoure. Afin de s'adapter à l'hétérogénéité des ressources et médias manipulant ces objets 3D, des techniques basées sur l'analyse multirésolution sont généralement utilisées car elles fournissent une représentation "scalable" de ces modèles géométriques. C'est dans ce cadre de compression et de transmission progressive d'objets 3D (modélisées sous forme de maillages surfaciques) que se situe ce travail de thèse, réalisé dans le cadre du projet "CoSurf" (collaboration entre le laboratoire LIRIS et France Télécom R&D Rennes). Nous proposons ainsi une nouvelle méthode de compression hiérarchique s'appuyant sur une décomposition en ondelettes, outil d'analyse performant et robuste qui a fait ses preuves en termes de compression d'images et de vidéos. Notre méthode se démarque des techniques existantes, puisqu'elle s'appuie sur une segmentation préalable de la surface en régions d'amplitudes fréquentielles variables. Les partitions résultantes peuvent ainsi être traitées indépendamment durant les phases d'analyse multirésolution, de quantification et d'allocation binaire, de façon à s'adapter aux caractéristiques surfaciques locales des maillages et ainsi réduire les informations à coder. La contribution visuelle de chacune des partitions à l'ensemble de la surface est également un point important à considérer dans la phase d'optimisation des bits alloués à celles-ci, notamment pour des applications comme la transmission et la visualisation sélectives. D'autres applications telles que le tatouage, le filtrage ou le débruitage adaptatifs, l'indexation ou enfin la correction d'erreurs après transmission sur un canal bruité, pourraient bénéficier de ce concept générique que nous avons proposé.

L'utilisation des modèles 3D, représentés sous forme de maillage, est sans cesse croissante dans de nombreuses applications. Pour une transmission efficace et pour une adaptation à l'hétérogénéité des ressources de ces modèles, des techniques de compression progressive sont généralement utilisées. Afin de protéger le droit d'auteur de ces modèles pendant la transmission, des techniques de tatouage sont également employées. Dans ces travaux de thèse, nous proposons premièrement deux méthodes de compression progressive pour des maillages avec ou sans information de couleurs et nous présentons finalement un système conjoint de compression progressive et de tatouage. Dans une première partie, nous proposons une méthode d'optimisation du compromis débit-distorsion pour des maillages sans attribut de couleur. Pendant le processus de l'encodage, nous adoptons la précision de quantification au nombre d'éléments et à la complexité géométrique pour chaque niveau de détail. Cette adaptation peut s'effectuer de manière optimale en mesurant la distance par rapport au maillage original, ou de façon quasi-optimale en utilisant un modèle théorique pour une optimisation rapide. Les résultats montrent que notre méthode donne des résultats compétitifs par rapport aux méthodes de l'état de l'art. Dans une deuxième partie, nous nous focalisons sur l'optimisation du compromis débit-distorsion pour des maillages possédant l'information de couleur attachée aux sommets. Après avoir proposé deux méthodes de compression pour ce type de maillage, nous présentons une méthode d'optimisation du débit-distorsion qui repose sur l'adaptation de la précision de quantification de la géométrie et de la couleur pour chaque maillage intermédiaire. Cette adaptation peut être effectuée rapidement selon un modèle théorique qui permet d'évaluer le nombre de bits de quantification nécessaire pour chaque maillage intermédiaire. Une métrique est également proposée pour préserver les éléments caractéristiques durant la phase de simplification. Finalement, nous proposons un schéma conjoint de compression progressive et de tatouage. Afin de protéger tous les niveaux de détails, nous insérons le tatouage dans chaque étape du processus d'encodage. Pour cela, à chaque itération de la simplification, nous séparons les sommets du maillage en deux ensembles et nous calculons un histogramme de distribution de normes pour chacun d'entre eux. Ensuite, nous divisons ces histogrammes en plusieurs classes et nous modifions ces histogrammes en décalant les classes pour insérer un bit. Cette technique de tatouage est réversible et permet de restaurer de manière exacte le maillage original en éliminant la déformation induite par l'insertion du tatouage. Nous proposons également une nouvelle méthode de prédiction de la géométrie afin de réduire le surcoût provoqué par l'insertion du tatouage. Les résultats expérimentaux montrent que notre méthode est robuste à diverses attaques géométriques tout en maintenant un bon taux de compression

Cette thèse est consacrée à la définition d'une surface géométriquement lisse interpolant un ensemble triangulé de points de R^3. Une telle triangulation, que nous appelons "réseau surfacique", doit définir une sous-variété de dimension 2, et peut représenter des surfaces de n'importe quel genre topologique. Il fournit l'information topologique, par l'intermédiaire d'une structure de données contenant les informations d'adjacence entre les sommets, les arêtes et les faces. Nous avons développé deux méthodes pour l'interpolation des sommets du réseau surfacique. Elles sont strictement locales et produisent des surfaces polynomiales par morceaux de degré 5 et de continuité G^1. De nombreux paramètres libres sont disponibles et ajustés soit interactivement soit automatiquement afin de lisser la surface. Dans le contexte interactif, plusieurs outils de design sont développés, basés sur l'interprétation géométrique des paramètres libres. La forme voulue peut être obtenue par une modélisation temps réel, grâce à la localité des algorithmes. Dans le cas du design automatique, de nombreux algorithmes ont été developpés satisfaisant un certain nombre de caractéristiques de forme. Un grand nombre de règles heuristiques et d'optimisations locales sont utilisées pour définir les valeurs des paramètres de forme dans le but d'obtenir des formes satisfaisantes ainsi qu'un contrôle optimal de la surface.

L’utilisation des modèles 3D, représentés sous forme de maillage, est sans cesse croissante dans de nombreuses applications. Pour une transmission efficace et pour une adaptation à l’hétérogénéité des ressources de ces modèles, des techniques de compression progressive sont généralement utilisées. Afin de protéger le droit d’auteur de ces modèles pendant la transmission, des techniques de tatouage sont également employées. Dans ces travaux de thèse, nous proposons premièrement deux méthodes de compression progressive pour des maillages avec ou sans information de couleurs et nous présentons finalement un système conjoint de compression progressive et de tatouage. Dans une première partie, nous proposons une méthode d’optimisation du compromis débit-distorsion pour des maillages sans attribut de couleur. Pendant le processus de l’encodage, nous adoptons la précision de quantification au nombre d’éléments et à la complexité géométrique pour chaque niveau de détail. Cette adaptation peut s’effectuer de manière optimale en mesurant la distance par rapport au maillage original, ou de façon quasi-optimale en utilisant un modèle théorique pour une optimisation rapide. Les résultats montrent que notre méthode donne des résultats compétitifs par rapport aux méthodes de l’état de l’art. Dans une deuxième partie, nous nous focalisons sur l’optimisation du compromis débit-distorsion pour des maillages possédant l’information de couleur attachée aux sommets. Après avoir proposé deux méthodes de compression pour ce type de maillage, nous présentons une méthode d’optimisation du débit-distorsion qui repose sur l’adaptation de la précision de quantification de la géométrie et de la couleur pour chaque maillage intermédiaire. Cette adaptation peut être effectuée rapidement selon un modèle théorique qui permet d’évaluer le nombre de bits de quantification nécessaire pour chaque maillage intermédiaire. Une métrique est également proposée pour préserver les éléments caractéristiques durant la phase de simplification. Finalement, nous proposons un schéma conjoint de compression progressive et de tatouage. Afin de protéger tous les niveaux de détails, nous insérons le tatouage dans chaque étape du processus d’encodage. Pour cela, à chaque itération de la simplification, nous séparons les sommets du maillage en deux ensembles et nous calculons un histogramme de distribution de normes pour chacun d’entre eux. Ensuite, nous divisons ces histogrammes en plusieurs classes et nous modifions ces histogrammes en décalant les classes pour insérer un bit. Cette technique de tatouage est réversible et permet de restaurer de manière exacte le maillage original en éliminant la déformation induite par l’insertion du tatouage. Nous proposons également une nouvelle méthode de prédiction de la géométrie afin de réduire le surcoût provoqué par l’insertion du tatouage. Les résultats expérimentaux montrent que notre méthode est robuste à diverses attaques géométriques tout en maintenant un bon taux de compression / The use of 3D models, represented as a mesh, is growing in many applications. For efficient transmission and adaptation of these models to the heterogeneity of client devices, progressive compression techniques are generally used. To protect the copyright during the transmission, watermarking techniques are also used. In this thesis, we first propose two progressive compression methods for meshes with or without color information, and we present a joint system of compression and watermarking. In the first part, we propose a method for optimizing the rate-distortion trade-off for meshes without color attribute. During the encoding process, we adopt the quantization precision to the number of elements and geometric complexity. This adaptation can be performed optimally by measuring the distance regarding the original mesh, or can be carried out using a theoretical model for fast optimization. The results show that our method yields competitive results with the state-of-the-art methods. In the second part, we focus on optimizing the rate-distortion performance for meshes with color information attached to mesh vertices. We propose firstly two methods of compression for this type of mesh and then we present a method for optimizing the rate-distortion trade-off based on the adaptation of the quantification precision of both geometry and color for each intermediate mesh. This adaptation can be performed rapidly by a theoretical model that evaluates the required number of quantization bits for each intermediate mesh. A metric is also proposed in order to preserve the feature elements throughout simplification. Finally, we propose a joint scheme of progressive compression and watermarking. To protect all levels of detail, we insert the watermark within each step of the encoding process. More precisely, at each iteration of simplification, we separate vertices into two sets and compute a histogram of distribution of vertex norms for each set. Then, we divide these histograms into several bins and we modify these histograms by shifting bins to insert a bit. This watermarking technique is reversible and can restore exactly the original mesh by eliminating the distortion caused by the insertion of the watermark. We also propose a new prediction method for geometry encoding to reduce the overhead caused by the insertion of the watermark. Experimental results show that our method is robust to various geometric attacks while maintaining a good compression ratio