|
|
|
|
La compression (code Huffman) Pour coder des informations, on considère un alphabet contenant A caractères (dans le domaine de l'informatique, l'alphabet est souvent constitué de {0, 1}; donc A = 2) et on code chaque caractère ou élément d'information (caractère semi graphique, caractère de contrôle, ...) à l'aide d'un "mot" écrit avec l'alphabet. On note le nombre de mots considérés par M. On distingue les systèmes de codage (on utilisera souvent le mot code à la place de système de codage) à longueur fixe où tous les mots ont la même longueur (par exemple: code ASCII) et les systèmes à longueur variable (alphabet morse). Le passage d'un code à longueur fixe à un code de longueur variable peut constituer une technique de compression. Un code de Huffman est un code à longueur variable construit de telle manière que:
Les techniques de compression dépendent du type d'information qui est à traiter. Il faut distinguer en première approximation les informations discrètes (suite de caractères), les informations linéaires continues (son) et les informations par plans (images). Informations discrètesCe sont les plus faciles à traiter. On utilise principalement la technique des codes de Huffman. Exemple: Un texte de 100 caractères contient les caractères suivants avec les répétitions indiquées entre parenthèses: E(35), N(10), T(8), S(11), X(2), R(7), O(27). Trouvez le code de Huffman permettant de coder ce texte de la manière la plus compacte possible. Quelle est le taux de compression par rapport à un codage ASCII sur 8 bits (on ne prend pas en compte l'en-tête du fichier compacté) ? Il est possible d'améliorer les taux de compression en prenant en compte les doublets de caractères. Le code de Huffman modifié supprime (par la technique des headers, voir ci-dessous) le codage pour les caractères dont le code est trop long (> 16). Le désavantage de cette méthode est de devoir préalablement analyser l'information à comprimer afin d'établir la table de codage. Le décompresseur doit connaître cette table. Cela ne permet pas la compression "à la volée" (par exemple dans le cas de transmission ininterrompue). La technique Lempel-Ziv-Welsh (LZW) introduit la construction de tables dynamiquement que le récepteur peut reconstruire au fur et à mesure de la réception du message. Cette technique est utilisée, par exemple, dans les utilitaires "zip" et "compress". Elle est également utilisée pour le codage d'images format GIF, format TIFF): l'image est codée sous la forme de motifs de répétition (suite de couleurs) qu'on peut y trouver que l'on l'on stocke dans une table et on ne transmet que les adresses de cette table. Une adresse occupant moins de place physique que la suite de couleurs qu'elle représente, on économise de la place mémoire. La décompression utilise la table pour retrouver les données originales. Information par plansIl faut tout d'abord rappeler la manière de coder des images. Une image peut être codée pixel par pixel. Cette méthode rend difficile certaines opérations sur les images (masque). Par ailleurs, si le nombre de couleur augmente un pixel demande beaucoup d'information et celle-ci a tendance a devenir très « irrégulière ». Dans des machines à vocation graphique une image est codée par plans de bits (bitplanes). Chaque plan correspondant à la présence ou absence d'une nuance. Par extension à d'autres technologies, on parle parfois de bitplanes à n bits par pixel ! On voit donc qu'un bitplane à des chances d'avoir de larges zones ayant la même valeur ! Compression par suppression des répétitions: (compression RLE: Run-Length Encoding) avec cette méthode, une information répétée est enregistrée une seule fois, accompagnée du facteur de répétition. Dans le format PCX, par exemple, si les deux premiers bits d'un octet sont 11 (header), les 6 autres indiquent un facteur de répétition. L'octet suivant est la valeur répétée. Sinon l'octet représente une valeur unique. C'est une méthode de compression idéale pour le fax (car on y trouve de longues suites de noirs et de blancs). Pour les images couleur, le taux de compression sera plus important si l'image est stockée sous forme de plans de bits. Des formats qui utilisent cette compression sont: le format PCX, le format TARGA, le format PHOTOSHOP Exemple: Dans un mode graphique (ancienne technologie) avec 1 bitplane à 4 bits par pixel (16 couleurs), on a une résolution de 640x480 points. On représente sur l'écran un damier de 16 sur 16 cases. Deux cases adjacentes sont supposées avoir des couleurs différentes. Compression topographique: Cette technique est utilisée lorsque une information (par exemple la valeur 0) est souvent répétée. Dans ce cas chaque octet est remplacé par 1 bit. Ce bit est 0 si le byte correspondant est 0, 1 sinon. Puis on note à la suite les valeurs des bytes non nuls. Exemple proposé par Sven Geisler:
Information linéaire à faible amplitude de variationLorsqu'une variation pas trop importante d'une donnée à l'autre existe, on ne code que la différence (delta). Cette technique peut être couplée avec d'autres (topographie). L'algorithme de Fibonacci-delta ramène toutes les différences aux nombres de Fibonacci (1 2 3 5 8 13 21 ...). Les techniques avec "approximation"Décomposition "spectrale": Pour le son et les images on peut aussi utiliser des techniques de transformation de Fourier discrète (Fast Fourier Transform: FFT) avec une certaine perte de qualité (JPEG). Pour les images animées on peut utiliser la technique delta d'une image à l'autre combinée à d'autres techniques. Compression fractale: La méthode "Iterated
Function System" (IFS) offre une technique de compression d'image
permettant des rapports de compression très élevés.
Cette technique est basée sur la production d'images fractales.
Elle se base sur un algorithme très simple. Ce document
préliminaire pourra être modifié de façon substantielle avant sa diffusion
commerciale. Il est fourni uniquement à titre d’information et Microsoft ainsi
que EROL n’apportent aucune garantie, explicite ou implicite, le concernant. Les
informations présentées dans le présent document peuvent être modifiées sans
préavis. L’utilisateur reconnaît assumer tous les risques liés à l'utilisation
ou aux résultats de l’utilisation de ce document. Les exemples de sociétés,
d’organisations, de produits, de personnes et d’événements décrits dans ce
document sont fictifs. Aucune association avec une société, une organisation, un
produit, une personne ou un événement réel n’a été voulue ou ne doit être
déduite. L’utilisateur est tenu de respecter toutes les lois applicables en
matière de droits d’auteur. Sans restriction des droits dérivés des droits
d’auteur, aucune partie de ce document ne peut être reproduite, stockée ou
introduite dans un système de récupération de données ou transmise à quelque fin
ou par quelque moyen que ce soit (électronique, mécanique, photocopie,
enregistrement ou autre) ou dans quelque but que ce soit sans la permission
expresse et écrite de Microsoft Corporation. |
|
|
