Compactage et compression
1 janv. 1994 - par cbraut
De toutes les disciplines informatiques, le multimédia, du fait qu'elle numérise son et image, est sans conteste la plus grosse consommatrice de données. Malgré la vitesse fulgurante à laquelle progressent les mémoires de masse, ces dernières sont encore incapables de faire face... si ce n'est avec l'aide d'algorithmes de compactage et de compression. Au tout début - qu'il s'agisse de lignes de programmes, du contenu de bases de données, de courriers saisis à partir de traitements de textes... -, les ordinateurs étaient essentiellement confrontés à des informations de type alphanumérique. Rien de bien méchant, quand on sait qu'une simple disquette double face double densité (720 Ko), permet de stocker cinq à six numéros de cette inégalable revue qu'est Keyboards Home Studio Recording...
Quelques années plus tard, dès qu'il fut question de numériser des informations plus conséquentes - documents scannerisés , audio et vidéo - les mégaoctets, suivis de près des gigaoctets, se moquèrent bruyamment des kilooctets, et pour cause : une page au format A4, passée à travers un scanner 600 DPI à 256 niveaux de gris consomme 60 Ko, une minute d'audio stéréo, 10 Mo, et une seconde de vidéo, diffusée sur un écran 16 millions de couleurs, d'une (haute) définition de 1024 x 768 points, près de 60 Mo. A peine plus de dix secondes d'images sur un CD-ROM ! De toute façon, ni ce dernier, ni aucune autre mémoire de masse, n'est aujourd'hui à même de relire à vitesse normale une telle séquence vidéo, compte tenu du temps d'accès et du débit de transfert que cela implique.
Fort heureusement, compactage et compression se font un plaisir de réduire considérablement l'espace nécessaire au stockage des données. La différence entre ces deux méthodes ? Le compactage préserve le contenu initial (aucune information n'est perdue), tandis que la compression supprime sciemment une partie du message, sous prétexte que l'être humain n'est pas en mesure, physiologiquement parlant, de la percevoir.
| Compactage | |
 | |
-
Qui, dans ses bacs à disquettes, n'a pas un logiciel d'archivage (ARC, PKZIP...), ou un programme censé augmenter la capacité d'un disque dur (Disk Doubler...) ? Bon an mal an, ce style d'utilitaire parvient à réaliser des économies de l'ordre de 50%, c'est-à-dire à caser les fichiers dans deux fois moins d'espace. A titre indicatif, et sans trop se perdre en subtilités algorithmiques, nous allons décrire l'un des procédés parmi les plus triviaux. Particulièrement adapté aux dessins bitmap , celui-ci repère les suites de données identiques. Ainsi, en supposant que chaque point d'une image soit codé sur un bit (0 pour blanc, 1 pour noir), une ligne composée de 400 points blancs, plutôt que d'occuper les 50 octets théoriquement requis (50 x 8 = 400), pourrait être représentée par deux octets, sous la forme valeur de l'octet nombre de répétitions . Dans ce cas précis, nous nous retrouverions avec les chiffres 0 (8 bits à blanc ) et 50 (50 fois 8 bits à blanc ). Le S1100, pour transmettre ou recevoir en MIDI le contenu de son écran, par l'intermédiaire de messages exclusifs, procède de la sorte... Pour les fondus du compactage, et de ses théories ô combien séduisantes, signalons qu'il existe des ouvrages de plusieurs centaines de pages sur le sujet.
| Compression | |
| |
-
En dépit du degré de complexité de certains algorithmes de compactage, leur efficacité ne satisfait pas aux exigences du multimédia, qui par sa gourmandise, pose des problèmes de stockage (lecture simultanée d'image et de son à partir d'une mémoire de masse), et de communication (transfert d'informations le long de câbles ou de lignes téléphoniques). La solution : recourir aux méthodes de compression, qui par définition, suppriment purement et simplement une partie des données, jugées inutiles, car non perçues.
En matière d'audionumérique, le MiniDisc et la cassette DCC, exploitent des procédés de compression, respectivement nommés ATRAC (Adaptive TRansform Acoustic Coding) et PASC (Precision Adaptive Sub-band Coding). L'un comme l'autre suppriment entre 75 et 80% des données, en jouant d'une part sur le seuil d'audibilité (on considère, d'après une courbe reflétant le comportement de l'oreille, que les fréquences d'amplitude inférieure à ladite courbe ne sont pas perçues), et d'autre part, sur l'effet de masquage (on considère qu'un signal relativement fort, d'une certaine fréquence, peut en masquer un autre, plus faible, d'une fréquence inférieure ou égale, toujours selon une courbe fondée sur nos capacités auditives). Les deux figures ci-contre, issues d'une documentation ayant trait au système PASC, illustrent les phénomènes de seuil d'audibilité et d'effet de masquage. Si tous les algorithmes de compression audio fonctionnent de façon similaire, il est à noter qu'ils sont responsables, entre autres, d'une dégradation de l'image stéréo et de la profondeur, toutes deux liées à d'infimes détails irrémédiablement gommés par la compression.
Pour en revenir au multimédia, rien n'empêche parallèlement, histoire de gagner encore un peu plus de place, de s'éloigner des normes dites professionnelles (16 bits et bientôt 20, 44.1 ou 48 kHz), c'est-à-dire d'exploiter une résolution et une fréquence d'échantillonnage moindres.
| JPEG et MPEG | |
| |
-
Après le plaisir des pavillons auditifs, c'est au tour de celui des yeux, pour lesquels deux standards de compression se sont imposés, l'un pour l'image fixe (JPEG, ou Joint Photographic Expert Group), l'autre pour l'image animée (MPEG, ou Moving Pictures Expert Group). L'algorithme JPEG opère tout d'abord une transformation mathématique du nom de DCT (Discrete Cosine Transform), appartenant à la même famille que la FFT (Fast Fourier Transformation). Dans ce cas précis, cette transformation analyse des blocs de 8 x 8 pixels, pour les représenter sous forme de fréquences. A ce stade des opérations, rien ne se perd : au contraire, cette représentation dans le domaine fréquentiel occupe plus de place que son homologue pixelisée . Par contre, elle permet d'effectuer une réduction drastique du nombre de bits, sans trop nuire à la qualité de l'image. Il serait soi-disant possible de pousser le taux de compression jusqu'à 25 (l'oeil, pauvre garçon, est encore plus mal loti que l'oreille). A la suite de cette décimation, un algorithme de compactage réduit encore l'espace occupé. Dans le sens inverse, on décompactera, avant de décompresser, via la fonction IDCT (Inverse DCT).
Avec l'image animée, le processus repose sur des principes totalement différents. On s'emploie ici à analyser les différences, ou plutôt les similitudes, rencontrées d'une image à l'autre. En effet, a priori, les redondances sont nombreuses (fond identique pendant plusieurs secondes, tandis qu'un personnage se déplace, etc.). Ainsi, il n'est pas rare que les taux atteignent un facteur de 50.
D'une façon générale, la compression et la décompression d'images (cette dernière devant impérativement avoir lieu en temps réel), sont des avides de calculs : le vulgaire micro-ordinateur devra le plus souvent se faire épauler par une carte spécialisée. Par ailleurs, la compression, beaucoup plus lente que la décompression (car transitant par une phase d'analyse), requiert encore plus de puissance, au point d'être parfois réservée à de très grosses machines.
En dehors des standards JPEG et MPEG, d'autres termes reviennent fréquemment dans les salons où l'on cause compression, comme DVI (Digital Video Interactive), développé par Intel et IBM, ou ATM, censé faire passer son et image au travers d'une ligne téléphonique. Quoiqu'il en soit, si la place nous manque pour aborder tous les concepts existants, espérons que ces quelques lignes vous auront fait prendre conscience de l'importance du compactage, mais aussi et surtout de la compression, grâce à laquelle, insidieusement, les acteurs du multimédia procèdent à un joyeux nivellement par le bas. Merci messieurs, et encore bravo !
| L'arbre d'huffman | |
| |
-
L'algorithme de compactage d'Huffman - nous conseillons vivement aux plus défavorisés intellectuellement de passer leur chemin -, consiste à calculer l'occurrence de chaque octet d'un fichier : le nombre de fois qu'il apparaît. Ainsi, en admettant que nous désirions compresser le texte ASCII suivant c'est en forgeant qu'on devient forgeron , il faudra commencer, comme nous venons de le dire, par calculer le nombre d'apparitions de chaque lettre : e (6), espace et n (5), o et t (4), r, f, g et apostrophe (2) c, s, a, q, u, d, v et i (1).
Sachant qu'en ASCII, un caractère est représenté par une valeur numérique comprise entre 0 et 255, à savoir par un octet, nous ferons en sorte, grâce à une méthode de codage à longueur variable dont la mise en oeuvre dépasse très largement le cadre de cet article (dite construction de l'arbre d'Huffman), de coder sur le moins de bits possibles les lettres revenant le plus souvent. Ainsi, si la lettre e apparaît plus fréquemment que la lettre x, pourquoi, plutôt que de s'en tenir à l'ASCII (les représenter toutes deux sur huit bits), ne pas coder par exemple le e sur 1 bit et le x sur 9 bits ?
Lors du décompactage, à partir de la table de codage, inscrite au début du fichier compacté (composée de la liste des différents codes, accompagnés des lettres qu'ils représentent), l'algorithme n'aura plus qu'à reconstruire le texte. Attention : pour éviter toute ambigüité, du fait que chaque lettre soit codée par un nombre variable de bits, il est impératif qu'aucun code à n bits ne corresponde au début d'un code à n + 1 bits. En bon français, en imaginant que l'on remplace les bits par des lettres, cela reviendrait à faire en sorte qu'aucun mot de n lettres ne corresponde au début d'un mot de n + 1 lettres. En effet, si nous nous retrouvions par exemple avec à la fois joue et joueur (chacun de ces deux mot codant deux entités quelconques), le programme de décompactage, en tombant sur joue, ne saurait pas si ce mot représente le code de la première entité, ou le début du code de la seconde. Aucun d'entre-vous n'a décroché ? C'est parfait.
Pour revenir à nos moutons, nous pourrions par exemple coder c, s, a et q sur sept bits (1111111, 1111110, 1111101, 1111100), u, d, v et i sur six bits (111101, 111100, 111001, 111000), r, f, g et l'apostrophe sur cinq bits (11011, 11010, 11001, 11000), l'espace, n, o et t sur quatre bits (1011, 1010, 1001, 1000), et e, sur 1 bit (0). Au total, notre phrase n'occuperait plus que 170 bits (6 x 1 + 2 x 5 x 4 + 2 x 4 x 4 + 4 , 4 x 6 + 4 x 7), au lieu de 320 (40 x 8).
© Christian Braut
A propos de l'auteur: cbraut
| Soyez le premier à donner votre Avis | |
| |
Vous devez être identifié comme membre pour pouvoir utiliser cette fonctionnalité!
