Païou veut savoir comment on peut compresser des données informatiques

Les fichiers de texte sont compressés, les images sont compressées, les données audio sont compressées, les vidéos sont compressées ...
Païou se demande un peu comment cela fonctionne, puisque cette notion de compression apparaît dans plusieurs pages du site.

Dans la théorie de l'information, l'entropie de Shannon quantifie l'information contenue dans un message.
Il suffit de retenir que, plus un message est redondant, moins il contient d'information et plus son entropie est petite.

Les algorithmes de compactage visent un même objectif : éliminer de la redondance et donc augmenter l'entropie, c'est à dire transmettre exactement la même information, mais avec moins d'octets.
Le compactage ne tient pas compte de la nature des données. Il est utilisé pour toutes sortes de fichiers binaires (texte, images, fax ...). Au décompactage, les données sont restituées sans pertes.

Une notion interviendra dans plusieurs des codages : prefix code : le code d'un élément est toujours différent du début (préfixe) du code d'un autre élément. Ainsi, il n'est pas nécessaire de prévoir un séparateur entre deux codes qui se suivent et dont on ne connait pas la longueur.

Différentes techniques sont utilisées et certains codages utilisent simultanément plusieurs techniques afin d'arriver à un résultat optimal.

Le compactage RLE (Run-length encoding) : Quand il y a une succession de n éléments identiques (octets), il faut moins d'espace pour écrire qu'il y a n éléments que d'écrire n fois le même élément.
Ici, il faut un caractère spécial qui indique que ce qui suit est d'abord le nombre de répétitions et ensuite seulement le code du symbole.
Il est utilisé par le fax et par de nombreux formats d'images (BMP, PCX, certains TIFF).

Il est également dénommé codage VLC (variable length code) car la longueur du code résultant est variable :
L'Entropy encoding consiste, habituellement, à créer un prefix code et à l'assigner à chaque nouveau symbole (octet, par exemple) qui se produit à l'entrée. Ce code est de longueur variable, les codes les plus courts étant attribués aux symboles les plus fréquents (contrairement au code ASCII qui a une longueur fixe).
Différents algorithmes correspondent à cette technique : Huffman, Adaptive Huffman, arithmétique (Shannon-Fano, Range)

• Huffman :
  C'est un compactage de type entropique qui, grâce à une méthode d'arbre, permet de coder les octets revenant le plus fréquemment avec une séquence de bits beaucoup plus courte que d'ordinaire. Ce codage nécessite deux lectures du fichier. Certains formats d'images TIFF utilisent le codage Huffman.
  • le fichier est d'abord lu, de manière à calculer les occurrences de chaque octet. L'arbre de Huffman peut être constitué pour le codage.
  • le fichier est codé dans un deuxième passage.
• Huffman adaptatif :
  L'arbre est construit de manière dynamique au fur et à mesure de la compression du flux de données. Une passe suffit donc.
  Il existe plusieurs implementations de cette méthode, les plus notables sont les algorithmes de FGK (Faller-Gallager-Knuth) et de Vitter.
• Shannon-Fano :
  C'est également un compactage de type entropique, avec un premier passage pour déterminer les occurrences de chaque octet. Le codage est construit en faisant des divisions successive du tableau des occurrences. Le fichier est codé dans un deuxième passage.
• Arithmétique :
  C'est également un compactage de type entropique, comme Huffman, mais le message sera représenté à l’aide d’un nombre à virgule flottante. La méthode est protégée par un brevet.
  • le fichier est lu une première fois pour déterminer les probabilités d’apparition de chaque symbole (caractère, par exemple).
  • lors d'une deuxième lecture, une plage comprise entre 0.0 et 1.0 est calculée selon la probabilité du 1er caractère.
    Ex. si sa probabilité est de 0.4, la plage sera [0.0 - 0.4] et il reste 0.6 (complément à 1.0) pour le restant des caractères.
    Une valeur sera calculée pour le 2ème caractère à partir de ce reste et de la probabilité du 2ème caractère. Cette valeur permet de donner une nouvelle plage, comme le montre l'exemple ci-dessous.
    Ex. si sa probabilité est de 0.5, la valeur sera 0.6 * 0.5 = 0.3. La plage correspondant à ces deux premiers caractères sera [0.4 - 0.8].
    Pour chaque nouveau caractère, une nouvelle valeur sera calculée selon la plage restante et la probabilité du nouveau caractère. Et une nouvelle plage sera déterminée.
    Ainsi de suite jusqu'à la fin du document. La valeur finale + la table des probabilités constitue le document compressé.
• Range encoding :
  Ce codage est relativement proche du codage arithmétique précédent. Il y a également détermination de plages en fonction de la probabilité de chaque caractère. Mais ici, c'est la plage correspondant au premier caractère qui est subdivisée pour chacun des caractères suivants. Le résultat est également un nombre à virgule flottante et il faut également deux passages pour l'encodage. Cet algorithme est libre.
• codage de Rice :
  Bien que développé séparément, le codage de Rice est un cas particulier du codage de Golomb, avec un paramètre réglable qui est égal à une puissance de deux. Ceci est particulièrement intéressant pour un odinateur qui travaille en puissance de deux. De même, le calcul du reste correspondant est obtenu en appliquant un simple masque binaire, ce qui est tout aussi rapide.
  Le codage Rice est utilisé comme étape de codage de l'entropie dans un certain nombre de compression d'image sans pertes et de compression de données audio.
• Golomb :
  C'est un compactage de type entropique. Un peu comme Shannon-Fano, il s'intéresse à un modèle de probabilité d'apparition des valeurs (qui sont explicitement traitées comme les nombres naturels, plutôt que de symboles abstraits). Cet encodage convient particulièrement à des suites de nombres comprenant beaucoup de nombres de faible valeur. Il fait intervenir un paramètre, le diviseur.
  Pour encoder un nombre :
  • on cherche le quotient q et le reste r d'une division de ce nombre par le diviseur.
  • Le quotient est ensuite écrit en notation unaire (suite de 1 et de 0) : un entier q sera codé par (q-1) 1 suivis d'un 0 (5 sera codé 11110). On peut aussi prendre (q-1) 0 suivis d'un 1
  • Le reste est encodé en binaire tronqué qui a la propriété de ne pas nécessiter de marqueur à la fin.
• et il y en a encore quelques uns ...

Lempel-Ziv (LZ77 LZ78), Lempel-Ziv-Welch (LZW)
Les codages par dictionnaire se basent également sur l'analyse des répétitions dans les données à traiter. Cependant, on recherche ici des occurrences de motifs de longueur plus importante que celle d'un octet.
Les motifs répétés prennent place dans un dictionnaire, et chacun d'eux est remplacé, dans les données compactées, par sa seule adresse dans le dictionnaire. L'algorithme travaille ainsi en une seule passe.

• LZ77
  L'algorithme travaille sur une fenêtre d'une certaine taille, en général inférieure à la taille du fichier. C'est le début de la fenêtre qui sert comme dictionnaire. Si, au cours de la lecture du contenu de la fenêtre un motif a déjà été trouvé, ce motif est remplacé par sa position dans la fenêtre. La fenêtre est glissante jusqu'à la fin du texte. LZ77 est à la base de pkzip, arj, gzip ...
• LZ78
  Lempel et Ziv abandonnent le concept de fenêtre glissante. Le dictionnaire se construit dynamiquement, tout au long du traitement. LZ78 est à la base de arc, compress, .gif ...
• LZW
  Terry Welch utilise un dictionnaire initial, comprenant les codes ASCII, repérés de 0 à 255. Ce dictionnaire se complète au fur et à mesure avec les motifs répétitifs. Il a fait l'objet d'un brevet déposé par Unisys
• LZO
  Lempel-Ziv-Oberhumer. LZO se focalise sur la vitesse de décompression et utilise un dictionnaire et plusieurs algorithmes.

• deflate
  combine l'algorithme LZ77 et le codage de Huffman. Il est utilisé par PKZIP v 2, Gzip et PNG
• LZMA
  Lempel-Ziv-Markov Algorithm. Il a pour but : une grande compression et une décompression rapide. Il utilise une compression avec dictionnaire assez similaire au LZ77 + Range encoding (au lieu de Huffmann). Il est notamment utilisé par 7-Zip.
• et il y en a encore des autres ...

Dans le codage par prédiction la valeur de chaque symbole est prédite à partir des symboles précédemment codés. Seul l’écart entre la valeur prédite et la valeur réelle est quantifié puis codé et transmis. L’écart étant en général faible, sa représentation nécessite moins de bits que le symbole lui même.

• Arbre de contexte CTW
  Il est surtout utiliser pour compacter des textes. Au fur et à mesure de la lecture du texte, on cherche à calculer la probabilité du prochain symbole en regardant un nombre fini de caractères (le contexte) précédant le caractère courant. L'ensemble des contextes peut être représenté par un arbre et on adjoint à chaque contexte sa liste de probabilités.
  Une fois la prédiction effectuée, à partir du modèle, le résultat est envoyé à un codeur arithmétique tel que décrit ci-dessus.
• Correspondance partielle
  PPM (Prediction by Partial Matching) Elle se base sur une modélisation de contexte pour évaluer la probabilité des différents symboles. Le contexte est un ensemble de symboles déjà rencontrés dans la source de données (fichier, flux). La longueur du contexte utilisé pour la prédiction détermine l'ordre du PPM. Les fréquences d'apparition des différents symboles sont associées à chaque contexte. La prédiction ainsi obtenue est traitée par un autre algorithme, le plus souvent un codage arithmétique
• Dynamic Markov compression
  Elle utilise une prédiction similaire à celle de PPM, à la différence que la lecture se fait bit par bit, au lieu de octet par octet..

Pour plus d'informations sur ces compactages et compressions, voyez les pages de Wikipedia (le plus souvent en anglais). Elles ont grandement servi à la confection de ce chapitre.

Il est un fait connu qu'un algorithme de compression sans pertes ne peut pas traiter tous les signaux possibles, de sorte que la plupart des compresseurs se limitent à un domaine donné et essaient de travailler aussi bien que possible dans ce domaine. La compression audio n'échappe pas à cette règle.

Le domaine de la compression audio se subdivise lui-même en plusieurs sous-domaines :

• la parole, avec un faible débit
• la musique, haute fidélité et multi-canaux, avec un débit élevé
• les webradios, dont le débit binaire doit rester assez faible
• etc

Nous verrons que les techniques de compactage vues précédemment sont utilisables pour la compression audio. Cependant, la compression audio présente quelques spécificités :

• un échantillon donné change peu par rapport au précédent,
• la présence de plusieurs canaux, présentant une certaine corrélation inter-canaux,
• la compression audio perceptuelle s’appuie sur les caractéristiques de l’oreille humaine. Son principe consiste à ne prendre en compte que les informations pertinentes pour l’oreille humaine, c’est à dire à éliminer (et donc à ne pas coder) les informations qui ne peuvent pas être perçues, soit parce qu’elles ne sont pas audibles, c’est à dire en dessous du seuil de perception du système auditif, soit parce qu’elles sont masquées par des sons plus forts (masquage psychologique). Cette compression est bien bien plus intéressante parce qu’elle permet d’atteindre des taux de compression beaucoup plus importants.

Des techniques plus spécifiques sont plus adaptées. Très souvent, les codecs (logiciels de codage et de décodage des sons) associent plusieurs de ces techniques.

Codage DPCM

Au lieu de coder la valeur de chaque échantillon, on code la valeur de la différence entre l'échantillon actuel et le précédent.
Cette différence est plus petite et on gagne ainsi en volume à stocker ou transmettre. Inconvénient : les erreurs de quantification s'ajoutent.

Codage DPCM prédictif

Pour obtenir une meilleure précision, on utilise plusieurs échantillons précédents pour prédire la valeur du nouvel échantillon.
Les échantillons précédents sont pondérés par des coefficients prédictifs. Cette technique permet de coder sur 6 bits au lieu de 12 ou 16 avec PCM.

Codage ADPCM prédictif

Le principe : faire varier le nombre de bits utilisés pour coder le résidu (faible variation = petit nombre de bits).
Cette méthode est utilisée pour les normes ITU-T G.721 et ITU-T G.722

Utilisation d'un modèle psycho-acoustique

La compression repose sur des modèles psycho-acoustiques qui décrivent le comportement subjectif de l'oreille humaine en fonction de la fréquence, du volume et du temps.

Bandes : notre oreille ne perçoit pas toutes les fréquences de la même façon. Pour l'oreille, l'échelle des fréquences n'est pas continue, mais découpée en vingt-quatre bandes critiques. Ces bandes de fréquences, liées à des zones sensibles bien précises de l'oreille interne, lui permettent d'être très sélective. Ainsi, nous différencions plus aisément les sons graves ou moyens que les aigus. Cela s'explique par le fait qu'il est beaucoup plus facile de distinguer deux sons s'ils appartiennent à des bandes différentes.

Masquage : tout son fort peut en cacher un autre plus faible; c'est ce que l'on appelle le masquage simultané. Il serait donc absurde, lors d'une compression de garder les informations qui seront masquées.
Notons que le masquage joue aussi dans le temps : bien que l'influence d'un son fort sur un plus ténu qui le précède (pré-masquage) soit très courte avec 20 ms au maximum, le même son fort peut continuer à en "écraser" un autre entre 100 ms et 200 ms après avoir été coupé (post-masquage).

Ainsi, il est possible d'éliminer des signaux qui ne sont pas perçus par l'oreille, soit parce qu'ils sont masqués par un autre son, soit parce que l'oreille est peu sensible à cette fréquence.

Corrélation inter-canaux

En stéréo, il y a une certaine similitude entre les signaux des deux canaux. C'est également le cas lorsqu'il y a encore plus de canaux (5.1 ou 7.1)

Ceci peut être exploité pour réduire le volume du signal binaire.

Codage par sous-bandes (sub-band coding)

L'oreille ne perçoit pas toutes les fréquences de la même façon.

• l'oreille a un seuil de sensibilité : en-dessous de ce seuil, les informations sont inutiles, donc supprimées.
• la sensibilité varie en fonction de la fréquence : la finesse de l'échantillonnage sera meilleure là où l'oreille est plus sensible.
• les sons de faible puissance sont masqués par un son fort : mise en place d'un masquage autour d'un son fort.
• l'oreille ne distingue pas deux sons de fréquence très voisine.

Le signal audio va être décomposé en plusieurs bandes de fréquences et chaque bande va être traitée différemment.

Pour chaque bande on va supprimer l'information inutile. Il y a donc perte d'information par rapport au signal original, mais lorsque le codage est bien fait, l'oreille ne perçoit pas de différence.
Il faut réaliser une analyse en temps réel de la distribution amplitude/fréquence. Pour ceci :

1. Filtrage : l’espace audible a été divisé en un certain nombre de bandes de fréquences (appelées sous-bandes) à l’aide de filtres numériques. Ceci permettra d'appliquer un traitement spécifique à chaque sous-bande.
2. Modèle psycho-acoustique : pour chaque sous-bande, la courbe de masquage est déterminée en temps réel à partir d'une transformée de Fourier rapide (FFT ou Fast Fourier Transform). Voir ci-dessous.
3. Quantification : la finesse de la quantification va changer en fonction de la bande de fréquence : elle sera meilleure là où l'oreille est plus sensible et plus grossière ailleurs. En présence d'un son fort, masquant les autres, le niveau plancher va être relevé dans les bandes autres que celle qui correspond au son masquant, supprimant ainsi les signaux qui ne seront pas perçus par l'oreille.
4. Codage enthropique : les valeurs binaires résultant de la quantification sont ensuite encore compressées. Il peut s'agir d'un codage de Huffman.

Le codage par synthèse est très différent du codage différentiel. L'idée n'est plus de manipuler les échantillons pour éliminer la redondance et les corrélations entre échantillons, mais au contraire de considérer des blocs d'échantillons et de construire un modèle qui produise des échantillons statistiquement identiques (ou proches) des échantillons originaux. Ce modèle donc permet de synthétiser des échantillons avec des propriétés statistiques données, d'où le nom de codage par synthèse.

Codage par prédiction linéaire ou LPC (Linear predictive coding)

Le signal est analysé et traité avant d'être codé. Ce codage est très utilisé dans le traitement des sons et également dans la synthèse vocale

Le constat

Le codage LPC admet, comme hypothèse, que le son (parole) peut être représenté par une vibration émise au bout d'un tube avec, éventuellement, un ajout de sifflements (consonnes sifflantes) ou de petits bruits secs (consonnes occlusives). Bien que cela semble un peu grossier, ce modèle est en fait une approximation de la réalité de la production de la parole.

La glotte (l'espace entre les cordes vocales) produit la vibration, caractérisée par son intensité (volume) et sa fréquence (hauteur). Le conduit vocal (la gorge et la bouche) forme le tube, qui se caractérise par ses volumes de résonance (ouverture de la bouche, position de la langue, ouverture ou fermeture du conduit vocal). Ces volumes donnent naissance aux formants (pics de résonnances) du son produit.
En première approximation, les voyelles sont caractérisées par deux formants pour chacune. Les sons sifflants ou bloquants sont générés par l'action de la langue, des lèvres et de la gorge.

Le codage

Le codage LPC (Linear Predictive Coding) consiste donc à synthétiser des échantillons à partir :

1. d'un modèle d'un système de production vocal (poumons - cordes vocales - trachée - gorge - bouche - lèvres, pour la voix)
2. d'une excitation (soit une sinusoïde, soit un bruit blanc)

En pratique, on modélise ce système par un ensemble de cylindres de diamètres différents. Le choix de la fonction d'excitation (sinusoïde ou bruit blanc) dépend des caractéristiques, voisée ou non voisée, du signal. Un signal voisé correspond à une voyelle. Un signal non voisé correspond à une consonne.

Le processus de synthèse a donc deux phases, qui sont :

1. l'identification de la fonction d'excitation
2. l'identification des diamètres des cylindres

Chaque phase est exécutée toutes les 20 ms. Les valeurs qui décrivent l'intensité et la fréquence de la vibration et le reste du signal, peuvent être stockées ou transmises ailleurs. À la réception, le signal vocal peut être restitué à partir de ces données.

Codage CELP (Code Excited Linear Predictive)

Le CELP (Code Excited Linear Predictive) est une extension du codage LPC. Il comporte toujours deux phases, correspondant aux fonctions d'excitation et de transfert. L'identification de la fonction de transfert est identique à celle faite avec LPC. Par contre, la fonction d'excitation n'est pas seulement un bruit blanc ou un sinusoïde, mais une combinaison linéaire de fonctions stochastique (c'est à dire de bruit) et périodiques.
L'identification de ces fonctions est très coûteuse en temps CPU (et d'ailleurs le codeurs CELP sont en général implémentés avec l'aide de cartes spécifiques de traitement de signal), mais la qualité obtenu est bien meilleure qu'avec le codeur LPC.

Codage GSM (Global System for Mobile Communications)

Le codage GSM utilise une variante du codeur CELP appelée RPE (Regular Pulse Excited), car la fonction d'excitation fait intervenir des impulsions périodiques couplées à une boucle de prédiction à long terme. Les détails de l'algorithme sont complexes. On obtient alors un codage de qualité très proche de PCM, mais avec un débit de seulement 13 kb/s.

Transformée de Fourier discrète (Discrete Fourier Transform ou DFT)

La transformation de Fourier est connue pour le traitement des signaux analogiques. Ceci est son adaptation aux signaux numériques.

En compression du son ou de l'image, des transformées proches de la TFD sont appliquées en général sur des portions de signal, pour réduire la complexité.

Transformée de Fourier discrète (Discrete Fourier Transform ou DFT)

La FFT (Fast Fourier Transform ou transformée de Fourier rapide) est ici utilisé après échantillonnage du signal d'entrée basses fréquences (audio). Avantage : il est capable de capturer les signaux en temps réel avec une résolution spectrale très fine

Opus - Codage CELT (Constrained-Energy Lapped Transform)

CELT (repris maintenant dans le projet Opus) est un codec open-source, vocal, utilisable pour des applications à très faible retard, telles que VoIP (voix sur IP). CELT est un transform codec, basé sur Modified Discrete Cosine Transform (MDCT). Support de la voix et de la musique, de la stéréo, Bande passante audio 44,1 kHz et 48 kHz, latence 3 à 9 ms, voix et musique, stéréo.

La transformée en cosinus discrète ou TCD (de l'anglais : DCT ou Discrete Cosine Transform) est une transformation proche de la transformée de Fourier discrète (DFT).

La compression audio se fait souvent en plusieurs phases

Exemple :

1. découpage en blocs ou trames. Le signal d'entrée est divisé en plusieurs blocs contigus. Les blocs peuvent être de taille fixe ou variable (adaptative). La taille optimale du bloc dépend de nombreux facteurs, dont le taux d'échantillonnage, les caractéristiques spectrales en fonction du temps, etc
2. Joint Stereo ou corrélation inter-canaux. En flux stéréo, il y a souvent une intéressante corrélation entre les canaux gauche et droit. Au lieu de coder les deux canaux, il est possible de n'en coder qu'un seul, par moments
3. prédiction Le bloc est passé dans une phase de prédiction où l'encodeur essaie de trouver une description mathématique (généralement approximative) du signal. Cette description est beaucoup plus petite que le signal brut lui-même. Étant donné que les méthodes de prédiction sont connues à la fois par l'encodeur et par le décodeur, seulement les paramètres du prédicteur doivent être inclus dans le flux compressé.
4. codage résiduel. Si le prédicteur ne décrit pas exactement le signal, la différence entre le signal original et le signal prédit (appelé signal d'erreur ou résiduelles) doit être codée (avec ou sans pertes).

Un autre exemple :

1. découpage en blocs ou trames. Comme ci-dessus.
2. utilisation d'un modèle psycho-acoustique. Il permet d'éliminer les fréquences qui ne sont pas audibles par l'oreille humaine.
3. élimination des fréquences masquées. Le gazouillis d'un oiseau peut être masqué par le bruit d'une voiture ou d'un avion. Il peut être éliminé.
4. Joint Stereo ou corrélation inter-canaux. Comme ci-dessus.
5. codage du signal épuré, par exemple par un codage Huffman.

Quand on parle image, il faut se souvenir qu'il y a deux sortes :

• les images matricielles
• les images vectorielles