Autant pour moins : la compression

Aujourd’hui nous allons parler de mettre beaucoup de données sur peu d’espace par le principe de la compression. 

Rassurez-vous, pas de compression dynamique d’un signal sonore ou de décompression comme la dernière fois avec le dolby NR, non je parle bien ici de prendre un truc et le transformer en truc plus petit.

Comme j’aime bien le faire, on va d’abord s’attarder sur les bases de la compression et sur des façons que nous avons, nous humains de compresser les données qui nous entourent. Elles ne sont pas directement transposables dans l’informatique, mais ça nous réchauffera le cerveau. De même, je ne vais pas vous dire quel format de fichier utilise quoi en terme de technique de compression car les principes peuvent être combinés, et des algorithmes plus complexes encore peuvent être utilisés.

Et on va commencer par les chiffres, vous vous souvenez de ces microtablettes d’argiles dont je parlais dans le premier épisode et sur lesquelles on notait le nombre de bêtes d’un troupeau, on peut assimiler ça à de la compression. Au lieu de transporter le troupeau, on a stocké l’information d’une façon plus simple, certes on manque d’information comme l’âge des bestioles et leur état de santé…. Sans compter qu’on ne sait toujours pas si c’est des moutons ou des vaches ou des chèvres. C’est donc une forme de compression avec perte. Beaucoup de perte.

Après les chiffres, on a les mots. Sur le même principe qu’avec les chiffres, on peut plus facilement, d’un point de vue logistique, communiquer le concept d’un éléphant avec le mot éléphant qu’en transportant le gros poutoupoutou avec vous à chaque fois (hein, mais oui mon poutoupoutou… oui pour cette chronique du coup j’ai dû en louer un, faut que je finisse vite ma chronique, il est garé en double file devant chez-moi...) Encore une fois, des informations viennent à manquer mais on a pas besoin d’autant d’espace pour la communiquer.

Si on combine les deux principes on atteint le summum de la technologie: la liste de course où la douzaine de pastèques peut tenir sur un post-it.

Le concept auquel je veux vous familiariser est celui de “faire appel à” qqchose. Faire appel à une table de correspondance entre un symbole et une valeur, un symbole à un concept, un objet. 

Car ce principe est, lui, transposable en informatique. Par exemple pour les couleurs, on leur attribue un chiffre allant de 1 à X. Plus ce chiffre est grand, plus les couleurs sont nombreuses et la fidélité des tons de l’image est grande. Mais plus le chiffre est grand, plus il prend de la place et plus l’image pèse lourd. D’où des images qui pullulaient au début du web, dites “clipart”, volontairement simplistes car prévues pour être en 256 couleurs.

Mais là on ne parle pas vraiment de compression, juste d’optimisation pour pas que ça pèse trop. Alors comment faire qu’une magnifique photo, disons d’une plage vide, reste classe sans être lourde?

L’une des techniques est justement de limiter le nombre de couleurs, mais de manière intelligente: Notre photo de bord de mer contient principalement du sable et de l’eau. 

J’ai choisi cet exemple car il est simple à comprendre: 2 couleurs dominantes, avec bien entendu des variations autour de ces deux couleurs. On va du bleu emeraude foncé au blanc pour l’eau et l’écume et on est dans les tons de sable foncé à blanc pour le sable et ses cristaux brillants.

Ici, pas besoin de rose, de mauve ou autres. On peut passer de 16 millions de couleurs à seulement quelques dizaines de miliers bien choisies sans que cela soit perceptible pour l’oeil humain. Cela peut faire passer l’image de 32bits à 16bits réduisant sa taille environ par deux.

Mais ce n’est pas tout: on peut aussi, de la même manière que sur une liste de course, éviter de répéter une information pour rien. 

Si quelqu’un vous demande de quelle couleur est le ciel, vous n’allez pas pointer du doigt tous les endroits du ciel et dire: là c’est bleu, là c’est bleu, là c’est bleu. Vous allez dire “le ciel est bleu et franchement si à 30 ans tu le sais pas c’est que t’es con ou daltonien ou les deux”

Et bien pour compresser une image, on peut faire de même: au lieu de donner le couleur de chacun des pixels, on peut, pour chaque couleur utilisée, noter les pixels de la même couleur. C’est un peu complexe dit comme ça mais en réalité c’est simple: lorsque vous prenez le pixel en haut à gauche, vous avez une couleur, vous la notez et ensuite, vous cherchez les autres pixels d’exactement cette couleur et notez leur placement. et vous continuez jusqu’à ce que vous ayez noté tous les pixels de l’image.

Vous voyez que c’est un poil plus complexe que de noter bêtement la valeur de ce qui est détecté par le capteur, non? Et vous savez que les ordinateurs sont EXTRÊMEMENT bons en opérations bêtes mais moins quand il s’agit de réfléchir. Et on arrive ici à un point épineux de la compression: le ratio taille/puissance. 

Parfois on pourrait compresser bien plus un document, une image, une vidéo, mais la compression prendrait un temps fou et la décompression de même. Et parfois ce n’est pas souhaitable. 

Un exemple? Je pouvais parfaitement lire des films en AVI découpés en 2 voir 3 CD sur mon pentium 1 100MHz mais les DIVX qui eux, tenaient sur un seul CD, c’était impossible de décoder la vidéo en temps réel et donc de regarder le film correctement… 

Voilà qui vous explique le choix que vous avez sur certains logiciels de zippage qui vous proposent des options de compression plus ou moins rapides. Elles seront plus ou moins efficaces.

Puisqu’on parle de vidéo, vous pouvez imaginer que compresser de la vidéo, c’est assez simple, on compresse les 24 images par secondes et on obtient un film tout petit. Et bien oui… et non. 

Oui car la technique qui évite la répétition d’information de couleur en notant le pixels de même couleur peut être facilement utilisée… mais non car le principe de palette réduite fixe fonctionne assez mal sur un film qui peut passer de la mer à la montagne, de la campagne à la ville. Je ne dit pas que ce n’est pas utilisé, mais ce n’est pas ça qui compresse un film suffisamment pour qu’il rentre sur un DVD ou un CD.

La vraie technique est d’utiliser ce que nous n’avions pas tout à l’heure: le temps, l'enchaînement des images. De cet enchaînement on peut tirer de l’optimisation.

De la même manière que lorsque vous décrivez des travaux chez vous à quelqu’un qui connaît votre maison, vous ne citez pas l’ensemble de ce qui n’a PAS changé dans votre domicile mais juste les nouveautés, la compression vidéo fonctionne de la même manière :

Imaginez un court métrage d’auteur avec un plan fixe: une pièce vide. Rien ne bouge pendant la majorité du film quand soudain un poulet traverse la pièce et hop, générique.

Ce film peut être compressé de plusieurs manières:

Le plan fixe n’a pas besoin d’être 24 fois la même image réitérée chaque seconde: on la définit une fois et ensuite on donne juste l’information comme quoi rien n’a changé jusqu’à l’arrivée du poulet. 

Et ensuite, quand le poulet passe, tous les pixels hors de la zone du poulet ne changent pas. On peut donc juste donner l’information “rien ne change” à tous ces pixels. 

Le poulet ou plutot les pixels du poulet, eux, devront être animés mais ils représentent une partie seulement de l’image.

Et même le générique, avec ses textes qui défilent de bas en haut, peut être compressé en disant simplement que “ce bloc de pixels blancs, là, ben ils de déplacent vers le haut”. On peut d’ailleurs utiliser cette technique pour les pixels du poulet quand il traverse. C’est très compliqué mais étonnamment, c’est utilisé.

On a fait les images, mais que serait un film sans le son. (oui un film muet, je sais).

Comme j’expliquais la dernière fois, on numérique du son de la façon suivante : on encode la “vague” de son sous une forme numérique.

Un peu comme en maths où lorsque l’on veut tracer une courbe, on note quelques points et on les relies pour tracer une jolie parabole.

Concrètement, sur un CD pour chacune des pistes stéréo, 44.100x par seconde, on note la hauteur de la vague sur une valeur allant de 0 à 65 536 (sur 16 bit, donc de 16x0 à 16x1). 

Le lecteur (que ce soit une platine ou un logiciel) va lire ces 0 et 1 pour reconstituer ces valeurs en 16bit en faire des points pour reconstruire la courbe et la transmettre en analogique à l’ampli. 

Comment compresser cela? Là on a plusieurs techniques: on peut utiliser les méthodes vues précédemment: si un fichier audio ne contient que du silence, ou que la même note, on va pouvoir compresser facilement. Si c’est juste des fréquences qui se répètent, de même on va pouvoir faire appel à ces fréquences plusieurs fois en ne les définissant qu’une fois et en disant qu’elles sont répétés à des moments précis.

Mais dans le cas précis du MP3, la vraie révolution c’est de tricher vis à vis de la perception. Pour cela, on va décomposer chaque son en fréquences distinctes. les fréquences les mieux perçues seront encodées plus finement, avec plus de points sur la courbe et les fréquences moins bien perçues seront encodées plus grossièrement.

De même, on va pouvoir aussi se débarrasser de certains sons car, masqués par d’autres, nous ne les aurions de toute façon pas entendus.

On peut d’ailleurs vous faire écouter ce qui est supprimé d’un MP3 lors de l’encodage:

Voilà qui conclue notre voyage au sein de la compression. Nous avons vu les principaux principes pour réduire le poids d’un fichier :

• Eviter la répétition des données en faisant appel plusieurs fois à un élément répété, voir même noter simplement une transformation de cet élément.
• Éviter les données superflues comme par exemple ne pas avoir une palette de couleurs non utilisée
• Jouer avec les sens humains pour cacher la dégradation.
• Tout en n’oubliant pas que cette compression a un coût: celui de la puissance de calcul nécessaire à la compression et la restitution.

Selon ce que nous souhaitons, nous pouvons donc compresser avec ou sans perte, rapidement ou puissamment, nous utiliserons dans un algorithme une ou plusieurs de ces techniques.