Chapitre 4 - Compression Avec Pertes - 2021 [PDF]

Zitiervorschau

Codage et Compression

Chapitre 4:

Compression avec Pertes

Université de Bordj-Bou-Arreridj S2/ 2019-2020

!1

1. Notions générales et définition. 2. Sch é ma g é n é ral des m é thodes de compression bas é es sur les transformations 3. Compression sans perte 4. Critères d’évaluation (MSE, PSNR, CR, SSIM ..etc) 5. Description des différentes parties (Transformation, Quantification et codage entropique) 6. Run-length encoding 8. Effets de la transformation sur la méthode de compression 9. Description de l'algorithme LZ77 10.Codage Correcteur 11.La transformée de Burrows-Wheeler

Compression de données La compression de données ou codage de source est l'opération informatique consistant à transformer une suite de bits A en une suite de bits B plus courte pouvant restituer les mêmes informations, ou des informations voisines, en utilisant un algorithme de d é compression. C'est une opération de codage qui raccourcit la taille (de transmission, de stockage) des donn é es au prix d'un travail de compression. Celle-ci est l'op é ration inverse de la décompression. Un algorithme de compression sans perte restitue après décompression une suite de bits strictement identique à l'originale. Les algorithmes de compression sans perte sont utilisés pour les archives, les fichiers exécutables ou les textes.

Compression de données Pour la compression de données sans pertes, on distingue principalement le codage entropique et le codage algorithmique. Le codage entropique est fondé sur des a priori quant à la source. On doit, par exemple, pour le codage de Huffman, transmettre une table de probabilités des symboles de la source. D'autres exemples sont les codages par dictionnaire comme LZ77, LZ78 et LZW. Le codage algorithmique, lui, ne n é cessite de transmettre d'autres informations que le résultat du codage (et la méthode de compression utilisée). Avec un algorithme de compression avec perte, la suite de bits obtenue après décompression est plus ou moins voisine de l'original selon la qualité désirée. Les algorithmes de compression avec perte sont utiles pour les images, le son et la vidéo. Les formats de données tels que Zip, RAR, gzip, ADPCM, MP3 et JPEG utilisent des algorithmes de compression de données. Gagner 5 % en efficacité de compression par rapport aux grands algorithmes courants peut typiquement multiplier par 100 le temps nécessaire à la compression1. La théorie de la compression de données utilise des concepts issus de la théorie de l'information : celle d'entropie au sens de Shannon.

Compression sans perte La compression est dite sans perte lorsqu'il n'y a aucune perte de données sur l'information d'origine. Il y a autant d'information après la compression qu'avant, elle est seulement réécrite d'une manière plus concise (c'est par exemple le cas de la compression gzip pour n'importe quel type de données ou du format PNG pour des images synthétiques destinées au Web2). La compression sans perte est dite aussi compactage. L'information à compresser est vue comme la sortie d'une source de symboles qui produit des textes finis selon certaines règles. Le but est de réduire la taille moyenne des textes obtenus après la compression tout en ayant la possibilité de retrouver exactement le message d'origine (on trouve aussi la dénomination codage de source en opposition au codage de canal qui désigne le codage correcteur d'erreurs). Il n'existe pas de technique de compression de données sans perte universelle, qui pourrait compresser n'importe quel fichier : si une technique sans perte compresse au moins un fichier, alors elle en « grossit » également au moins un autre.

Compression sans perte La compression avec pertes ne s'applique qu'aux donn é es « perceptibles », en général sonores ou visuelles, qui peuvent subir une modification, parfois importante, sans que cela soit perceptible par un humain. La perte d'information est irréversible, il est impossible de retrouver les données d'origine après une telle compression. La compression avec perte est pour cela parfois appelée compression irréversible ou non conservative. Cette technique est fondée sur une idée simple : seul un sousensemble très faible de toutes les images possibles (à savoir celles que l'on obtiendrait par exemple en tirant les valeurs de chaque pixel par un générateur aléatoire) possède un caractère exploitable et informatif pour l'œil. Ce sont donc ces images-là qu'on va s'attacher à coder de façon courte. Dans la pratique, l'œil a besoin pour identifier des zones qu'il existe des corrélations entre pixels voisins, c'est-à-dire qu'il existe des zones contiguës de couleurs voisines. Les programmes de compression s'attachent à découvrir ces zones et à les coder de la façon aussi compacte que possible. La norme JPEG 2000, par exemple, arrive généralement à coder des images photographiques sur 1 bit par pixel sans perte visible de qualité sur un écran, soit une compression d'un facteur 24 à 1.

Comparaison des tailles d'un fichier audio non compressé (en PCM dans un conteneur WAV) et compressé (en MP3).

Compression sans perte Puisque l'œil ne perçoit pas nécessairement tous les détails d'une image, il est possible de réduire la quantité de données de telle sorte que le résultat soit très ressemblant à l'original, voire identique, pour l'œil humain. L'enjeu de la compression avec pertes est de réduire la quantité de données d'un fichier tout en préservant la qualité perceptible et en évitant l'apparition d'artefacts. De même, seul un sous-ensemble très faible de sons possibles est exploitable par l'oreille, qui a besoin de régularités engendrant ellesmêmes une redondance (coder avec fidélité un bruit de souffle n'aurait pas grand intérêt). Un codage éliminant cette redondance et la restituant à l'arrivée reste donc acceptable, même si le son restitué n'est pas en tout point identique au son d'origine. On peut distinguer trois grandes familles de compression avec perte : • par prédiction, par exemple l'ADPCM ; • par transformation. Ce sont les méthodes les plus efficaces et les plus utilisées. (JPEG, JPEG 2000, l'ensemble des normes MPEG…) ; • compression bas é e sur la r é currence fractale de motifs (Compression fractale).

Run-length encoding Le run-encoding, appelé en français le codage par plages, est un algorithme de compression de données sans perte en informatique. Le système s'applique essentiellement à des documents scannés en noir et blanc : au lieu de coder un bit par point, on dispose d'un compteur — en général sur un octet — indiquant combien de points blancs ou noirs se suivent. Comme il est fréquent d'avoir au moins 8 pixels noirs ou 8 pixels blancs de suite, et que 256 ne sont pas rares sur les endroits vierges ou les à-plats noirs, le système a bien pour effet une compression. S'il y a plus de 256 bits de la même couleur, on peut placer ensuite un octet spécifiant 0 bit de la couleur opposée, puis coder le nombre de bits qui restent. Par exemple, considérons un écran de texte noir sur fond blanc. Il sera constitué de longues séquences de pixels blancs pour le fond, et de courtes séquences de pixels noirs pour le texte. Représentons une ligne d'un tel écran, avec B (comme black) pour les pixels noirs et W (comme white) pour les pixels blancs : WWWWWWWWWWWWBWWWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWW Un encodage Run Length Encoding consiste à indiquer pour chaque suite de pixels d'une même couleur le nombre de pixels de cette séquence. Le résultat comporte en général moins de caractères, bien que ça ne soit pas toujours le cas. On obtient, par exemple, pour la ligne précédente :

12W1B14W3B23W1B11W

Compression CCITT C'est une compression d'images utilisée par les télécopieurs (ou fax), standardisée par des recommandations de l'Union internationale des télécommunications (anciennement appelée CCITT). Elle est de type RLE (on code les suites horizontales de pixels blancs et de pixels noirs) et peut-être bidirectionnelle (on déduit une ligne de la précédente). Il existe plusieurs types de compressions (« groupes ») suivant l'algorithme utilisé et le nombre de couleurs du document (monochrome, niveau de gris, couleur). Deux compressions existent, celle du Groupe 3 (recommandation ITU T.4) et celle du Groupe 4 (recommandation ITU T.6), utilisées pour les fax : • Le Groupe 3 utilise comme indiqué une compression RLE, mais les symboles représentant les longueurs sont définis par le CCITT en fonction de leur fréquence probable et ceci pour diminuer la taille des messages à transmettre par les fax. • La compression du Groupe 4, elle, représente une ligne par les différences avec la ligne précédente. Ainsi un carré noir sur une page blanche n'aura que la première ligne du carré à transmettre, les suivantes étant simplement la « différence », c'est-à-dire rien. Et la page complète revient à envoyer 3 lignes et un symbole de « répéter la précédente » pour toutes les autres. Ceci est théorique : en pratique, il faudra transmettre plus de symboles, mais envoyer une page blanche est tout de même beaucoup plus rapide avec le Groupe 4 qu'avec le Groupe 3.

LZ77 et LZ78 LZ77 et LZ78 sont deux algorithmes de compression de données sans perte proposés par Abraham Lempel et Jacob Ziv en 1977 et 1978 (d'où leurs noms). Ces deux algorithmes posent les bases de la plupart des algorithmes de compression par dictionnaire, à tel point qu'on parle couramment d'algorithme LZ pour désigner un algorithme de compression par dictionnaire. Ces algorithmes reposent de manière essentielle sur une mesure de complexité pour les suites de longueur finie, la complexité de Lempel-Ziv.

LZ77 LZ77 est un algorithme de compression par dictionnaire utilisant une fenêtre glissante ; les motifs déjà rencontrés dans la fenêtre sont remplacés par une référence à leur première apparition (typiquement, par une paire (distance, longueur)). Par extension, LZ77 est aussi utilisé pour désigner la famille des algorithmes de compression par dictionnaire utilisant une fen ê tre glissante, comme LZSS et LZMA.

Description de l'algorithme LZ77 La Compression

Etant donnée une séquence S à compresser, on l'écrit d'abord sous forme de plusieurs composantes Si juxtaposées. Pour ce faire, on choisit un entier LS qui sera la longueur maximale d'un Si et un entier n > LS qui sera la taille du buffer. On initialise les n-Ls caractères du buffer par des zéros et on complète le buffer par les LS premiers caractères de S. L'entier n-Ls est la taille de la fenêtre glissante (initialisée avec des zéros comme indiqué précédemment). Pour trouver les Si, on réalise à chaque itération une production exhaustive de la sous-séquence de S la plus longue possible en prenant le contenu de la fenêtre glissante comme préfixe, avec ici la contrainte que la longueur de la séquence produite ne peut dépasser Ls. Après initialisation de la fenêtre à zéro et en appliquant ce processus de production on obtient donc la séquence S1 de longueur L1