Il y a une décennie, le contenu numérique virtuel était limité à quelques applications - majoritairementles jeux vidéos, les films en 3D et la simulation numérique. Aujourd'hui, grâce à l'apparition de cartes graphiques performantes et bon marché, les objets 3D sont utilisés dans de nombreuses applications. A peu près tous les terminaux possédant des capacités d'affichage - des clusters de visualisation haute performance jusqu'aux smart phones - intègrent maintenant une puce graphique qui leur permet de faire du rendu 3D. Ainsi, les applications 3D sont bien plus variées qu'il y a quelques années. On citera par exemple la réalité virtuelle et augmentée en temps réel ou les mondes virtuels 3D. Dans ce contexte, le besoin de méthodes efficaces pour la transmission et la visualisation des données 3D est toujours plus pressant. De plus, la taille des maillages 3D ne cesse de s'accroître avec la précision de la représentation. Par exemple, les scanners 3D actuels sont capables de numériser des objets du monde réel avec une précision de seulement quelques micromètres, et génèrent des maillages contenant plusieurs centaines de millions d''el'ements. D'un autre côté, une précision accrue en simulation numérique requiert des maillages plus fins, et les méthodes massivement parallèles actuelles sont capables de travailler avec des milliards de mailles. Dans ce contexte, la compression de ces données - en particulier la compression de maillages - est un enjeu important. Durant la décennie passée, de nombreuses méthodes ont été développées pour coder les maillages polygonaux. Néanmoins, ces techniques ne sont plus adaptées au contexte actuel, car elles supposentque la compression et la d'ecompression sont des processus sym'etriques qui ont lieu sur un mat'erielsimilaire. Dans le cadre actuel, au contraire, le contenu 3D se trouve cr'e'e, compressé et distribué par des machines de hautes performances, tandis que l'exploitation des données - par exemple, la visualisation - est effectuée à distance sur des périphériques de capacité plus modeste - éventuellement mobiles - qui ne peuvent traiter les maillages de grande taille dans leur int'egralité. Ceci fait de lacompression de maillage un processus intrinsèquement asymétrique.Dans cette thèse, notre objectif est d'étudier et de proposer des méthodes pour la compression de maillages de grande taille. Nous nous intéressons plus particulièrement aux méthodes d'accès aléatoire, qui voient la compression comme un problème intrinsèquement asymétrique. Dans ce modèle, le codeur a accès à des ressources informatiques importantes, tandis que la décompression estun processus temps réel (souple) qui se fait avec du matériel de plus faible puissance. Nous décrivons un algorithme de ce type et l'appliquons au cas de la visualisation interactive. Nous proposons aussi un algorithme streaming pour compresser des maillages hexaèdriques de très grande taille utilisés dans le contexte de la simulation numérique. Nous sommes ainsi capables decompresser des maillages comportant de l'ordre de 50 millions de mailles en moins de deux minutes, et en n'utilisant que quelques mégaoctets de mémoire vive. Enfin, nous proposons, indépendamment de ces deux algorithmes, un cadre théorique général pour améliorer la compression de géométrie. Cet algorithme peut être utilisé pour développer des méthodes de prédiction pour n'importe quel algorithme basé sur un paradigme prédictif - ce qui est la cas dela majorité des méthodes existantes. Nous dérivons ainsi des schémas de prédictions compatibles avec plusieurs méthodes de la littérature. Ces schémas augmentent les taux de compression de 9% enmoyenne. Sous des hypothèses usuelles, nous utilisons aussi ces résultats pour prouver l'optimalité de certains algorithmes existants.

Il y a une décennie, le contenu numérique virtuel était limité à quelques applications – majoritairementles jeux vidéos, les films en 3D et la simulation numérique. Aujourd’hui, grâce à l’apparition de cartes graphiques performantes et bon marché, les objets 3D sont utilisés dans de nombreuses applications. A peu près tous les terminaux possédant des capacités d’affichage – des clusters de visualisation haute performance jusqu’aux smart phones – intègrent maintenant une puce graphique qui leur permet de faire du rendu 3D. Ainsi, les applications 3D sont bien plus variées qu’il y a quelques années. On citera par exemple la réalité virtuelle et augmentée en temps réel ou les mondes virtuels 3D. Dans ce contexte, le besoin de méthodes efficaces pour la transmission et la visualisation des données 3D est toujours plus pressant. De plus, la taille des maillages 3D ne cesse de s’accroître avec la précision de la représentation. Par exemple, les scanners 3D actuels sont capables de numériser des objets du monde réel avec une précision de seulement quelques micromètres, et génèrent des maillages contenant plusieurs centaines de millions d’´el´ements. D’un autre côté, une précision accrue en simulation numérique requiert des maillages plus fins, et les méthodes massivement parallèles actuelles sont capables de travailler avec des milliards de mailles. Dans ce contexte, la compression de ces données – en particulier la compression de maillages – est un enjeu important. Durant la décennie passée, de nombreuses méthodes ont été développées pour coder les maillages polygonaux. Néanmoins, ces techniques ne sont plus adaptées au contexte actuel, car elles supposentque la compression et la d´ecompression sont des processus sym´etriques qui ont lieu sur un mat´erielsimilaire. Dans le cadre actuel, au contraire, le contenu 3D se trouve cr´e´e, compressé et distribué par des machines de hautes performances, tandis que l’exploitation des données – par exemple, la visualisation – est effectuée à distance sur des périphériques de capacité plus modeste – éventuellement mobiles – qui ne peuvent traiter les maillages de grande taille dans leur int´egralité. Ceci fait de lacompression de maillage un processus intrinsèquement asymétrique.Dans cette thèse, notre objectif est d’étudier et de proposer des méthodes pour la compression de maillages de grande taille. Nous nous intéressons plus particulièrement aux méthodes d’accès aléatoire, qui voient la compression comme un problème intrinsèquement asymétrique. Dans ce modèle, le codeur a accès à des ressources informatiques importantes, tandis que la décompression estun processus temps réel (souple) qui se fait avec du matériel de plus faible puissance. Nous décrivons un algorithme de ce type et l’appliquons au cas de la visualisation interactive. Nous proposons aussi un algorithme streaming pour compresser des maillages hexaèdriques de très grande taille utilisés dans le contexte de la simulation numérique. Nous sommes ainsi capables decompresser des maillages comportant de l’ordre de 50 millions de mailles en moins de deux minutes, et en n’utilisant que quelques mégaoctets de mémoire vive. Enfin, nous proposons, indépendamment de ces deux algorithmes, un cadre théorique général pour améliorer la compression de géométrie. Cet algorithme peut être utilisé pour développer des méthodes de prédiction pour n’importe quel algorithme basé sur un paradigme prédictif – ce qui est la cas dela majorité des méthodes existantes. Nous dérivons ainsi des schémas de prédictions compatibles avec plusieurs méthodes de la littérature. Ces schémas augmentent les taux de compression de 9% enmoyenne. Sous des hypothèses usuelles, nous utilisons aussi ces résultats pour prouver l’optimalité de certains algorithmes existants. / A decade ago, 3D content was restricted to a few applications – mainly games, 3D graphics andscientific simulations. Nowadays, thanks to the development cheap and efficient specialized renderingdevices, 3D objects are ubiquitous. Virtually all devices with a display – from a large visualizationclusters to smart phones – now integrate 3D rendering capabilities. Therefore, 3D applications arenow far more diverse than a few years ago, and include for example real-time virtual and augmentedreality, as well as 3D virtual worlds. In this context, there is an ever increasing need for efficient toolsto transmit and visualize 3D content.In addition, the size of 3D meshes always increases with accuracy of representation. On one hand,recent 3D scanners are able to digitalize real-world objects with a precision of a few micrometers, andgenerate meshes with several hundred million elements. On the other hand, numerical simulationsalways require finer meshes for better accuracy, and massively parallel simulation methods now generatemeshes with billions of elements. In this context, 3D data compression – in particular 3D meshcompression – services are of strategic importance.The previous decade has seen the development of many efficient methods for encoding polygonalmeshes. However, these techniques are no longer adapted to the current context, because they supposethat encoding and decoding are symmetric processes that take place on the same kind of hardware.In contrast, remote 3D content will typically be created, compressed and served by high-performancemachines, while exploitation (e.g. visualization) will be carried out remotely on smaller – possiblyhand held – devices that cannot handle large meshes as a whole. This makes mesh compression anintrinsically asymmetric process.Our objective in this dissertation is to address the compression of these large meshes. In particularwe study random-accessible compression schemes, that consider mesh compression as an asymmetricproblem where the compressor is an off-line process and has access to a large amount of resources,while decompression is a time-critical process with limited resources. We design such a compressionscheme and apply it to interactive visualization.In addition, we propose a streaming compression algorithm that targets the very large hexahedralmeshes that are common in the context of scientific numerical simulation. Using this scheme, we areable to compress meshes of 50 million hexahedra in less than two minutes using a few megabytes ofmemory.Independently from these two specific algorithms, we develop a generic theoretical framework toaddress mesh geometry compression. This framework can be used to derive geometry compressionschemes for any mesh compression algorithm based on a predictive paradigm – which is the case of thelarge majority of compression schemes. Using this framework, we derive new geometry compressionschemes that are compatible with existing mesh compression algorithms but improve compressionratios – by approximately 9% on average. We also prove the optimality of some other schemes underusual smoothness assumptions.

Le désir d’atteindre une haute résolution spatiale en imagerie médicale pour petits animaux conduit au développement d’appareils composés de détecteurs de plus en plus petits. Des appareils s’approchant de la résolution théorique maximale en tomographie d’émission par positrons (TEP) sont à nos portes. Pour retirer le maximum d’information de ces appareils, il importe d’utiliser des méthodes de traitement évoluées qui prennent en considération l’ensemble des phénomènes physiques entourant la prise de mesure en TEP. Le problème est d’autant plus complexe à résoudre du fait que ces caméras sont composées de milliers de détecteurs qui donnent lieu à des millions de lignes de réponses mesurées pouvant alors être traitées par un algorithme de reconstruction d’images. Cette situation mène à des problèmes de reconstruction d’images en 3 dimensions (3D) qui sont difficiles à résoudre principalement à cause des limites en ressources mémoires et de calcul des ordinateurs modernes. Les travaux réalisés dans le cadre de cette thèse répondent à deux grands besoins relatifs au domaine de la reconstruction d’images en TEP, soit l'atteinte d'une meilleure qualité d'image et l'accélération des calculs menant à l'obtention de celle-ci. Le premier volet des travaux repose sur le l'élaboration de méthodes de modélisation 3D précises du processus d’acquisition en TEP permettant d'atteindre une meilleure qualité d’image. Ces modèles 3D s'expriment sous forme de matrices systèmes qui sont utilisées par un algorithme de reconstruction d'images. Pour générer ces modèles 3D pour la TEP, des méthodes de calculs analytiques et basées sur des simulations Monte Carlo (MC) ont été développées. Des méthodes hybrides, basé sur des stratégies analytiques et Monte Carlo, ont également été mises en œuvre afin de combiner les avantages des deux approches. Les méthodes proposées se distinguent de l'art antérieur en ce qu'elles tirent profit des symétries du système afin de réduire considérablement le temps de calcul requis pour l'obtention de matrices 3D précises. Pour l’approche analytique, le calcul de la matrice est divisé en diverses étapes qui favorisent la réutilisation de modèles pré-calculés entre les lignes de réponses symétriques de l’appareil. Pour l’approche par simulations MC, la réutilisation des événements MC collectés entre les lignes de réponse symétriques de l’appareil permet d’augmenter la statistique utilisée pour générer la matrice MC et du même coup de réduire le temps de simulation. La méthode hybride proposée permet de réduire encore davantage le temps de simulation MC et cela, sans faire de compromis sur la qualité de la matrice système. Le second volet des travaux repose sur le développement de nouvelles méthodes de reconstruction d’images basées sur un référentiel en coordonnées cylindriques permettant de réduire les contraintes d’espace mémoire et d'accélérer les calculs menant à l’image. Ces méthodes se divisent en deux catégories distinctes. Les premières sont des méthodes dites itératives qui permettent de résoudre le problème de reconstruction d’images par un processus itératif qui réalise une nouvelle estimation de l’image à chaque itération de façon à maximiser le degré de vraisemblance entre l’image et la mesure de l’appareil. Les secondes sont des méthodes dites directes qui permettent de résoudre le problème en inversant la matrice système qui relie l’image à la mesure de projections par une décomposition en valeurs singulières (DVS) de la matrice. La matrice inverse ainsi obtenue peut alors être multipliée directement avec la mesure pour obtenir l’image reconstruite. L’utilisation d’une image en coordonnées cylindriques entraîne une redondance au niveau des coefficients de la matrice système obtenue. En exploitant ces redondances, il est possible d’obtenir une matrice système avec une structure dite bloc circulante qui peut alors être transformée dans le domaine de Fourier afin d’accélérer les calculs lors du processus de reconstruction d’images itératif ou par DVS. De plus, pour la méthode par DVS, l’utilisation d’une matrice bloc circulante factorisée facilite grandement la procédure d'inversion de la matrice par DVS, ce qui rend l’application de la méthode possible pour des problèmes de reconstruction d’images en 3D. Or, la résolution de problèmes aussi complexes n’était jusqu’ici pas possible avec les méthodes par DVS de l’art antérieur dû aux contraintes d’espace mémoire et à la charge excessive de calcul. En somme, les travaux combinés ont pour objectif ultime de réunir à la fois la vitesse de calcul et une qualité d'image optimale en un même algorithme afin de créer un outil de reconstruction 3D idéal pour l'utilisation dans un contexte clinique.