BENOIT Christophe
DUSSON Alexandre
MPSI


TIPE sur la compression de données informatiques

 

I- Problèmes concrets et utilisation de la compression de données

La compression de données informatiques consiste à réduire la taille de l'information pour le stockage de cette information et son transport.

Exemples d置tilisation de la compression pour le stockage :

Le coût et les limites technologiques nécessitent d置tiliser la compression de données pour le stockage d段mportants volumes d段nformation.

Exemples d置tilisation de la compression pour le transport :

Pour une durée donnée, la compression permet de faire circuler plus d段nformations, le débit est donc plus grand.

On distingue pour cela deux types de compression suivant leur usage :

Les différents algorithmes de compression sont choisis en fonction de :

 

II- Compression sans perte

1. RLE (Run Length Encoding)

- Recherche des caractères répétés plus de n fois (n fixé par l'utilisateur)

- Remplacement de l'itération de caractères par:

  1. un caractère spécial identifiant une compression
  2. le nombre de fois où le caractère est répété
  3. le caractère répété

Durant la lecture du fichier compressé, lorsque le caractère spécial est reconnu, on effectue l弛pération inverse de la compression tout en supprimant ce caractère spécial.

ex: AAAAARRRRRROLLLLBBBBBUUTTTTTT

On choisit comme caractère spécial : @ et comme seuil de répétition : 3

Après compression : @5A@6RO@4L@5BUU@6T gain : 11 caractères soit 38%

 

  1. LZW (Lempel Ziv Welch)

Cet algorithme utilise une bibliothèque c弾st-à-dire une table de données contenant des chaînes de caractères.
Au cours du traitement de l段nformation, les chaînes de caractères sont placées une par une dans la bibliothèque. Lorsqu置ne chaîne est déjà présente dans la bibliothèque, son code de fréquence d置tilisation est incrémenté. Les chaînes de caractères ayant des codes de fréquence élevés sont remplacées par un " mot " ayant un nombre de caractères le plus petit possible et le code de correspondance est inscrit dans la bibliothèque.
On obtient ainsi une information encodée et sa bibliothèque.

Lors de la lecture de l段nformation encodée, les " mots " codés sont remplacés dans le fichier par leur correspondance lue dans la bibliothèque et le fichier d弛rigine est ainsi reconstitué.

Cette méthode est peu efficace pour les images mais donne de bons résultats pour les textes et les données informatiques en général (plus de 50%).

 

  1. Huffman
  1. on cherche la fréquence des caractères
  2. on trie les caractères par ordre décroissant de fréquence
  3. on construit un arbre pour donner le code binaire de chaque caractère

Construction de l誕rbre : on relie deux à deux les caractères de fréquence les plus basses et on affecte à ce n忖d la somme des fréquences des caractères. Puis on répète ceci jusqu'à ce que l誕rbre relie toutes les lettres. L誕rbre étant construit, on met un 1 sur la branche à droite du n忖d et un 0 sur celle de gauche.

Exemple d弾ncodage de Huffman :

Le fichier compressé se compose d置ne suite de codes sans séparateur, bien que les codes comportent un nombre variable de bits, car chaque code a la propriété d置nicité de son préfixe.

On transmet la bibliothèque de codage, puis on associe les caractères à leur code.

Cet algorithme permet de compresser aussi bien des images que des textes, on parle de compression statistique ou codage entropique (probabilités d誕pparition d置n caractère). On obtient une compression satisfaisante (50% en moyenne) et un temps de compression assez rapide. En revanche il faut transmettre la bibliothèque en même temps, et il arrive que la taille du fichier soit plus grande que celle du fichier non compressé. De plus il est très sensible à la perte d置n bit, toutes les valeurs qui suivront ce bit seront fausses lors de la décompression.

 

III- Compression avec pertes

Pour les images :

Une dégradation de l段mage décompressée indiscernable à l凋il ou suffisamment faible pour être acceptable est acceptée en contrepartie d置n taux de compression très élevé.

  1. JPEG (Joint Photographic Expert Group)

La norme J.P.E.G. définie en 1991 par un groupe d弾xperts du monde de la photographie est actuellement la méthode de compression d段mages fixes avec pertes la plus utilisée.

Schéma de principe :

 

L段mage d弛rigine est décomposée en blocs de 8´8 pixels (on obtient pour chaque bloc 64 coordonnées d置ne matrice 8´8 correspondant chacune à une couleur). On applique à chaque matrice la transformation DCT (Transformée en Cosinus Discrète). Cette technique réversible est similaire à la transformée de Fourier qui transforme une image en une somme de fonctions sinus et cosinus de différentes fréquences et amplitudes, mais la DCT se contente des cosinus. Chaque carré est représenté par une somme de 64 fonctions cosinus de fréquences et d誕mplitude appropriées à chacune desquelles on associe une matrice, on obtient ainsi une matrice tridimensionnelle 8´8´64. On observe que l誕mplitude des composantes des basses fréquences (BF, c弾st-à-dire ce qui correspond à une plage de couleur uniforme) est plus élevée que celle des composantes des hautes fréquences (HF, c弾st-à-dire ce qui correspond à des variations brusques de couleur d置n pixel à l誕utre). Les matrices sont ordonnées par leur fréquence (ou amplitude) et, pour schématiser, la compression consiste à retirer des détails pour diminuer le volume du fichier image en supprimant les hautes fréquences (HF), ce qui correspond à un filtre passe-bas. Le taux de compression va dépendre du seuil de lécrêtage : plus on conserve des composantes à amplitude faible, meilleure sera la qualité (car plus il y aura de détails fins), mais plus faible sera le taux de compression.

Matrice tridimensionnelle :

Pour simplifier létude, nous étudierons la somme de ces 64 matrices sous la forme d置ne matrice à deux dimensions de type 8´8. Prenons pour exemple le bloc de 64 pixels extrait d置ne image représenté dans la matrice 1, dont chaque coordonnée correspond à une couleur :


matrice 1


matrice 2

On applique ensuite la transformation DCT à la matrice 1 et on obtient la matrice 2.

Cette opération est totalement réversible et aucune information n誕 été perdue à cette étape.

L段ntérêt d置n telle transformation est que les coefficients de forte valeur absolue sont situés en haut et à gauche, l段mportance des coefficients pour la reconstitution de l段mage diminue quand on se déplace en diagonale vers le bas à droite.

Létape suivante est la quantification qui donne des valeurs approximatives de la matrice 2 en tenant compte d置n pas de quantification prédéfini. Pour un pas de quantification Q, la valeur quantifiée est le quotient de la division euclidienne de la valeur par Q. (ex : pour un pas de quantification de 3, on remplace 0, 1et 2 par 0 ; 3, 4 et 5 par 1 ). C弾st à cette étape que des pertes d段nformation apparaissent et la précision de l段mage restituée est déterminée par le pas de quantification. Le pas de quantification est pris relativement petit pour les valeurs importantes (en haut à gauche) et il est de plus en plus grand au fur et à mesure que l弛n descend vers le bas et la droite. L弾nsemble des pas utilisés constituent ce que l弛n appelle une matrice de quantification. Une matrice de quantification est construite en fonction de critères psycho-visuels, suivant la formule suivante : Q(i,j) = 1 + (1 + i + j) ´ Fq avec Fq facteur de qualité et Q le pas de quantification. Par exemple, pour Fq = 5 on obtient la matrice 3 (le facteur de qualité sera à indiquer au décodeur). Finalement, on prend la partie entière de la division de chaque valeur de la matrice 2 par la valeur de la matrice 3 ayant la même position et on obtient la matrice 4.


matrice 3


matrice 4

La matrice finale (matrice 4), possède beaucoup de 0 donc cette récurrence de valeurs sera compressée par un codage statistique tel que le codage de Huffman.

Le fichier est décompressé par la méthode de décodage statistique, puis la matrice obtenue est multipliée par la matrice de quantification que l弛n reconstitue grâce au facteur de qualité et enfin on applique la DCT inverse pour retrouver une image plus ou moins dégradée par rapport à l段mage initiale.

Cet algorithme fonctionne très bien avec des images à tons continus, son utilisation est moins agréable pour des images ayant de forts contrastes. Le taux de compression est très élevé : 90% avec une très bonne qualité et une vitesse de compression/décompression raisonnable. Lorsque le taux de compression est trop élevé, on a un effet mosaïque car l段mage est divisée en petits carrés qui sont traités séparément ce qui fait apparaître les bords des différents carrés restitués.

 

  1. Ondelettes

Une image est formée de carrés de 256 pixels par 256 et chaque pixel est constitué de couleurs différentes. On peut donc modéliser cette image en une matrice carrée de 256 lignes et 256 colonnes où chaque coefficient représente le code d'une couleur.

On multiplie maintenant cette matrice par une matrice creuse (contenant beaucoup de zéros), du type :

A=

Ex :

Soit   M=

Þ P=M´A=

Dans la première moitié de la matrice on a léchantillon principal, et dans la deuxième on a les détails. On veut maintenant effectuer cette opération sur les colonnes, pour ce fait on calcule N = tA ´ M ´ A. On applique maintenant le coefficient de précision à la matrice, c弾st à dire que l弛n supprime tous les coefficients inférieurs à e . On obtient maintenant une nouvelle matrice N et pour retrouver la matrice originale on calcule M = tA-1 ´ N ´ A-1.

Mais ces calculs sont longs et on peut les réduire considérablement en remarquant que ´A est une matrice rectangulaire ( tA = A-1).

Pour augmenter le taux de compression, on utilise plusieurs fois l誕lgorithme, mais on remarque que c弾st toujours le quart de la matrice en haut à gauche qui comporte des coefficients nécessitant dêtre réduits. L誕lgorithme est donc appliqué à cette partie.

Exemple : Nous allons compresser et décompresser la matrice suivante :

M =


Soient A1, A2, A3 les matrices creuses :

A1 =


A2=

A3=


A = A1´ A2´ A3 =


on calcule N = tA ´ M ´ A =


on supprime tous les coefficients inférieurs à e :


Pour décompresser,

on calcule M = tA-1´ N´ A-1 =

On constate une faible différence entre la matrice originale et la matrice finale.

La compression par ondelette est une technique récente qui donne de très bons résultats, même avec des taux de compression élevés (plus de 90%). Cette méthode reste encore marginale par rapport à l'utilisation de JPEG, malgré ses avantages.

 

  1. Fractales

Les images fractales sont générées à partir d置ne équation et de quelques paramètres. Si l弛n veut compresser une telle image, il suffit de transmettre la formule qui l誕 générée. Etant donnée une image quelconque, il est démontré à l誕ide du théorème du point fixe l弾xistence et l置nicité d置ne formule qui permette de reconstruire cette image, or il s誕vère que la démonstration nous apporte une majoration permettant de trouver cette formule, nous avons ainsi une approximation de cette formule.

L段mage est découpée en blocs de 16 pixels de côté qui sont à leur tour découpés en 4 blocs de 8 pixels de côté. Pour chaque bloc B, on détermine de manière approximative un couple de fonctions qui, lorsqu弛n les applique une succession de fois, permettent à un bloc quelconque de converger vers ce bloc B, on parle alors d誕ttracteur.

On obtient un très fort taux de compression, encore plus important que celui de JPEG, mais son principal défaut est sa lenteur dans la phase de compression. Cette méthode fait encore l弛bjet de nombreuses recherches et, dans les années à venir, cette méthode remplacera le standard actuel JPEG.

 

Pour les vidéos :

  1. MPEG (Motion Picture Expert Group)

Les vidéos sont constituées d置ne succession d段mages et, pour obtenir une animation, la différence entre deux images successives est minime. Le codage MPEG consiste à ne conserver que l段mage de départ d置ne animation, puis les modifications apportées à cette image. Lors d置n changement de plan, la première image de ce plan est conservée puis ses modifications. Les images sont également toutes compressées par la méthode JPEG.

 

Il existe également d誕utres méthodes de compression pour les vidéos, ainsi que pour la compression de sons (codage MP3, PASC, ) mais leur étude n誕 pas été traitée.

 

IV- Conclusion

La compression de données est appelée à prendre un rôle encore plus important en raison du développement des réseaux et du multimédia. Son importance est surtout due au décalage qui existe entre les possibilités matérielles des dispositifs que nous utilisons (débits sur Internet et sur les divers câbles, capacités des mémoires de masse, ) et les besoins qu弾xpriment les utilisateurs (visiophonie, vidéo plein écran, transfert de quantités d段nformation toujours plus importantes dans des délais toujours plus brefs). Quand ce décalage n弾xiste pas, ce qui est rare, la compression permet de toutes façons de faire des économies.

Les méthodes déjà utilisées couramment sont efficaces et sophistiquées (Huffman, LZW, JPEG) et utilisent des théories assez complexes. Les méthodes émergentes sont prometteuses (fractales, ondelettes) mais nous sommes loin d誕voir épuisé toutes les pistes de recherche. Les méthodes du futur sauront sans doute s誕dapter à la nature des données à compresser et utiliseront l段ntelligence artificielle.