La compression de données (Généralités)

Introduction

La compression des données est un vaste sujet qui a fait l’objet de nombreux ouvrages et articles; elle donne lieu aujourd’hui à de nombreuses recherches en raison des enjeux économiques sous-jacents. Elle est utile en PAO mais elle est une des conditions d’existence du multimédia.

Les domaines mathématiques et informatiques dont la connaissance est nécessaire pour comprendre ces problèmes sont nombreux et complexes : calcul intégral, algèbre linéaire, géométrie fractale, théorie de l’information, théorie des ondelettes, théorie des probabilités,…

On comprendra facilement également que la compression des données a quelque chose à voir avec le fonctionnement de notre système visuel et avec la construction des algorithmes.

On se contentera donc dans ce bref exposé, d’ouvrir un champ de réflexion en indiquant souvent sommairement quelles sont les méthodes utilisées aujourd’hui pour compresser les données et quelles sont celles qui ont des chances de s’imposer demain.

Ce petit exposé est composé de deux parties :

• Les méthodes réversibles (sans perte).
Je traiterai d’abord un exemple très simple mais qui peut être entièrement expliqué et appliqué ici. J’aborderai ensuite les méthodes de codage statistique (algorithmes de Huffman et de Shanon-Fano) pour terminer par les méthodes dites « à dictionnaire » (algorithme LZW)

• Les méthodes irréversibles (avec pertes).
J’exposerai relativement précisément la compression JPEG en raison de son importance dans nos métiers et je donnerai quelques vues sur l’utilisation des fractales et des ondelettes dans la compression de données.

Avant d’aller plus loin définissons d’abord la compression. Nous dirons que nous avons compressé un fichier si nous parvenons à réduire le nombre de digits binaires nécessaires pour l’enregistrer.

On mesure l’efficacité de la compression par le taux de compression :

Sigma est toujours plus grand que 1 et nous souhaitons qu’il soit le plus grand possible.

Il est plus difficile de mesurer la qualité de la compression.

Essayons. Supposons que nous compressions un fichier composé des données n1, n2, n3… Quans on décompresse le fichier on récupère des données ñ1, ñ2, ñ3,…
Si ñ1 = n1, ñ2 = n2, ñ3 = n3… la compression est sans pertes. Si certaines valeurs ont été modifiées, il y a perte et il faut essayer de mesurer l’écart entre l’image originale et celle que l’on récupère après compression.
Pour chaque valeur on va faire la différence ñi - ni qui peur être positive ou négative. Pour que les différences ne s’annulent pas, on va prendre le carré de chaque différence et on va en faire la moyenne pour l’ensemble des données, par exemple pour tous les pixels d’une image. Nous venons de définir l’erreur quadratique moyenne (EQM).
(pour les matheux, on a :