Compression de structures géométriques

La compression de structures géométriques est un domaine de recherche relativement nouveau, situé entre la géométrie algorithmique et la compression de données standard.

L'essor rapide des applications de la synthèse d'image rend nécessaires la manipulation et l'échange de données géométriques de manière rapide et économique. En particulier, les nombreuses possibilités offertes par le World Wide Web en matière de réalité virtuelle sont conditionnées par un accès rapide aux données. Cela implique (spécialement lorsque la bande passante est faible) d'organiser et de comprimer les données géométriques de manière optimale.

Depuis 1995, plusieurs travaux de recherche ont traité le problème du codage de maillages (scènes géométriques en 2 ou 3 dimensions composées de polygones) de la façon suivante: les sommets du maillage sont transmis dans un ordre établi pour contenir partiellement la topologie du maillage (c'est-à-dire les arètes des polygones). Parallèlement, un ensemble de règles simples permet de prédire la position d'un sommet à transmettre à partir des positions de ses voisins déjà transmis.

Nos travaux consistent à développer de nouvelles méthodes de compression géométrique. En particulier, nous avons mis au point un algorithme dont le principe général est le suivant: l'ordre des sommets du maillage est exploité pour comprimer leurs coordonnées, et la topologie du maillage est ensuite reconstruite à partir des sommets. Cet algorithme atteint des facteurs de compression légèrement supérieurs à ceux obtenus par les algorithmes actuellement disponibles pour la compression géométrique, et il permet en outre une transmission progressive et interactive des données.


Application aux modèles de terrain

Les images suivantes montrent comment se fait la transmission progressive d'un modèle de terrain à travers notre algorithme. Pour chaque étape de la transmission, nous indiquons le nombre de bits de précision sur les coordonnées des sommets du maillage et le facteur de compression atteint, ie la taille des données brutes originales divisée par la taille des données transmises. La derniere étape de l'algorithme restitue le modèle original (compression sans perte). Ce modèle est disponible à GIS-VIS.
Précision: 4 bits, Facteur de compression: 41.8
Précision: 5 bits, Facteur de compression: 17.5
Précision: 6 bits, Facteur de compression: 9.0
Précision: 7 bits, Facteur de compression: 5.6
Précision: 8 bits, Facteur de compression: 4.0
Précision: 9 bits, Facteur de compression: 3.0
Précision: 14 bits (compression sans perte), Facteur de compression: 1.6

Last modified: Thu Nov 4 16:01:28 MET 1999 P.-M. Gandoin Thèmes Accueil PRISME same page in english