Compression progressive et sans perte de structures géométriques

For a few years, meshes have been conquering a predominant status amongst the different types of computer data structure for geometric objects. More precisely, the meshes composed of simplices -- triangles for the modeling of surfaces embedded in 3D, tetrahedra for the modeling of volumes -- seem to be the most widespread at the present time. The rapid growth of applications using these geometric structures in such various fields as finite elements computing, simulation of surgery, or video games has quickly raised the problem of an efficient coding, well suited for storage or visualization. The advent of the World Wide Web, which needs a compact and progressive representation of the data in order to guarantee the user-friendliness of the exchanges and communications, increases this need. Therefore, since 1995, a large number of algorithms have been proposed for the compression of triangular meshes, using for most of them the following approach: the vertices of the mesh are coded in an order such that it contains partially the topology of the mesh. In the same time, some simple rules attempt to predict the position of the current vertex from the positions of its neighbors that have been previously coded. In this thesis, we have chosen to give the priority to the compression of the vertex positions rather than their connectivity. We describe a set of coding methods which are progressive, lossless, adapted to arbitrary meshes (non necessarily triangular nor manifold, with arbitrary genus), and generalizable to any dimension. Our results are competitive with regards to the best current progressive methods: for instance, for the particular case of triangular surface meshes, about 3.6 bits per vertex are necessary on average to code the connectivity of usual models.En quelques années, les maillages ont conquis une position prédominante parmi les différents modes de représentation informatique d'objets géométriques. Plus particulièrement, les maillages à base de simplexes -- les triangles pour la représentation de surfaces plongées en 3D, les tétraèdres pour la représentation de volumes -- semblent être actuellement les plus répandus. Le développe- ment rapide des applications manipulant ces structures géométriques dans des domaines aussi divers que le calcul par éléments finis, la simulation chirurgi- cale, ou les jeux vidéo a très vite soulevé le problème d'un codage efficace et adapté à la visualisation. L'expansion du World Wide Web, qui nécessite une représentation compacte et progressive des données pour garantir la convivial- ité de l'interface homme-machine, a fini de conférer à ce problème une place centrale dans la recherche en informatique. Ainsi, depuis 1995, de nombreux algorithmes ont été proposés pour la com- pression de maillages triangulaires, en utilisant le plus souvent l'approche suiv- ante : les sommets du maillage sont codés dans un ordre établi pour contenir par- tiellement la topologie (ou connectivité) du maillage. Parallèlement, quelques règles simples permettent de prédire la position du sommet courant à partir des positions de ses voisins qui ont déjà été codés. Dans ce mémoire, nous avons choisi de donner plutôt la priorité à la compression des positions des sommets. Nous décrivons un ensemble de méthodes de codage progressif, sans perte d'information, adaptées à une large classe de structures géométriques (non nécessairement triangulaires ni manifold, de genre quelconque), et généralisables à n'importe quelle dimension. Les taux de compression obtenus se positionnent avantageusement par rapport aux méthodes progressives actuelles les plus ef- ficaces : par exemple, pour le cas particulier des maillages triangulaires sur- faciques, des taux moyens autour de 3,6 bits par sommet sont atteints sur des modèles usuels pour le codage de la connectivité