Compresser, pourquoi faire ?

Pour le stockage et le transfert des images numériques

• Les images numériques
  Une image numérique est représentée par une succession de points (pixels). La couleur de chaque pixel est représentée par un nombre de bits qui va de 1 (noir ou blanc) à 24 (16 millions de couleurs différentes) ou même 32 (4 milliards de couleurs !). Aujourd'hui un écran standard de PC compte 1024x768 pixels. Anciennement on se satisfaisait de 640x480 ou 800x600 qui était grosso modo la définition d'une image de télévision. Une image de la taille d'un écran 1024x768 en 16 millions de couleurs (24 bits soit 3 octets par pixel) nécessite 1024x768x3=2359296 octets soit 2,4 Mega octets (Mo). C'est plus que la taille d'une disquette ! Ce format brut est le format des fichiers avec l'extension .bmp.
  Heureusement, il y a l'ADSL et la compression !!!
  
  
• Les réseaux (dont Internet)
  les photos et les images numériques nécessitent des volumes de données très importants, souvent trop importants pour les performances des réseaux ou des machines. Il faut donc comprimer les informations. Quand on manipule des photos ou des images, la plupart des succès ou des échecs sont liés à ces techniques de compression. Le choix d'un format de fichier n'est pas suffisant. Il est indispensable de comprendre un minimum les techniques de compression pour choisir les paramètres qui vous donneront les résultats attendus. Comme les informaticiens ont beaucoup d'imagination, les méthodes de compression sont très nombreuses. On peut les grouper dans 2 catégories, la compression non destructive et la compression destructive.
  
  * La compression non destructive conserve la totalité des informations numériques. C'est celle qui est employée, par exemple, pour les fichiers programmes zippés. Il faut restituer tous les bits sans aucune perte. Les taux de compression sont généralement faibles de 1 à 4.
  
  * La compression destructive tient compte des caractéristiques des équipements et de l'oeil ou de l'oreille. On ne conserve pas les signaux qui sont peu ou pas perçus. On peut alors obtenir des taux de compressions qui s'échelonnent de 10 à 1000 ou plus. C'est le mode de compression habituel des photos et des images.
  

Les algoritmes de compression non destructive

Puisque non destructives, les compressions du même nom ne modifient en rien l'image : ils la codent. C'est à dire que tous les 0 et les 1 ou plus exactement les séquences de 0 et 1 qui décrivent l'images vont être codés, le codage devant être plus court que les données d'origine. Pour cela, chaque procédé utilise un algorithme particulier.

Ce type de compression est surtout utile pour les images contenant des zones de couleurs unies, car qui dit unité dit séquence de nombres identiques. Les taux de compression ne sont pas terribles de 20 à 1 au mieux. Pour gagner sans altérer, on peut aussi diminuer le nombre de couleurs. Ainsi, le format gif constitue une palette de 256 couleurs en regroupant les couleurs proches.

Les modes les plus employés sont le RLE, le LZW et le codage de Huffman.

ASTUCE : Les fichiers zippés utilisent un mode de compression non destructive. C'est pourquoi une image au format TIFF enregistrée avec le mode de compression LZW ne sera pas plus compressée si vous l'enregistrée dans un fichier ZIP. Cependant, l'intérêt d'utiliser le zipage est que vous pouvez enregistrer des dizaines d'images dans un même fichier et les transférer en une seule opération. Vous gagnez du temps de manipulation, mais il faut tout de même rester raisonnable et ne pas dépasser la centaine d'images par zip, pour un transfert via l'ADSL (environ 50 Mo).

Le RLE (Run Length Encoding)

Cette méthode basique consiste à repérer des répétitions de valeurs identiques (qui peuvent être des bits ou des octets). Puis il suffit d'indiquer la valeur et le nombre de répétitions consécutives.

Exemple :
Dans l'image, on trouve une séquence du type :
157-157-157-157-157-157-007-007-007-000-255-255-255-255-089-089-089-089-089-089
Ce qui donne une fois codé : 006/157-004/007-001/000-004/255-006/089

Le LZW (Lempel-Ziv-Welch) ou LZ77

La société Unisys ayant déposé la méthode LZW, il en existe une variante non brevetée, le LZ77.
Plus compliqué que le RLE, il s'agit cette fois de repérer des motifs composés de séries de bits ou d'octets. Chaque motif est copié dans une table et se voit attribué un indice (code). Puis chaque motif est remplacé dans le fichier par son indice, sachant qu'une valeur isolée n'est pas codée.

Exemple :
Dans l'image, on trouve une séquence du type :
1573157 2557255 1573157 0 070007 070007 2557255 08990899 1573157 08990899
1573157 est remplacé par code1
2557255 est remplacé par code2
070007 est remplacé par code3
08990899 est remplacé par code4
Ce qui donne une fois codé :
code1 - code2 - code1 - 0 - code3 - code3 - code2 - code4 -code1 - code4
Formats de fichier : GIF ou TIF pour LZW, PNG pour LZ77

Le codage de HUFFMAN

Le système de HUFFMAN repose sur les mêmes principes que le LZW. La différence est que la longueur du code d'identification dépend de la fréquence du motif dans la séquence considérée. Pour distinguer les codes entre eux, chaque code binaire commence par un 0 ou plusieurs 0 suivis de plusieurs 1. Le 0 est donc le signal de changement de code. Pour le reste on retrouve une table ou les motifs sont rangés à côté de leur code.

Exemple :
Dans l'image, on trouve une séquence du type :
157 255 157 157 007 001 007 255 255 089 089 157 089 157 089
157 est remplacé par 01
089 est remplacé par 001
255 est remplacé par 0011
007 est remplacé par 00011
001 est remplacé par 000111
Ce qui donne une fois codé :
01 0011 01 01 00011 000111 00011 0011 0011 001 001 01 001 01 001
Si la première séquence était écrite en binaire, le gain de place serait plus évident.

Les algorithmes de compression destructive

Si ce type de compression est tant utilisé c'est pour deux raisons :

• Il permet d'atteindre des taux très élevé, jusqu'à 100:1 pour le JPeg,
  
• Notre oeil étant assez peu performant sur la vision des détails, il est possible d'en supprimer sans que cela ne se voit.

D'autre part, notre rétine est davantage sensible aux variations de lumière que de couleurs. Dans un paysage photographique, si l'on modifie légèrement la couleur des brins d'herbe, vous ne percevrez pas la différence ; si, par contre on uniformise leur couleur, sans pour autant apporter plus de modifications que précédemment, vous verrez ressortir des zones de couleur uniformes : c'est l'effet de blocs ou pixelisation.

C'est votre oeil qui commandera le choix entre la taille du fichier et la qualité de l'image. Il est évident que pour de petites images, le gif est une bonne solution. Pour les photographie, le JPeg semble être la réponse la plus courante actuellement.

Les méthodes les plus employées sont le JPeg, l'utilisation de Fractale, le codage par ondelettes.

Le JPeg

La norme JPeg est une norme ISO/CEI.

e codage emploie en fait quatre méthodes de compression :

1. Tout d’abord l'image est traduite du RVB en YCrCb .Puis, chaque pixel conserve son information Y de luminosité, mais on attribue à tout groupe de quatre pixels (2x2) la moyenne de la chrominance(Cr et Cb).
2. L’image est ensuite découpée en blocs de 8 x 8, taille optimisée expérimentalement, sur lesquels on utilise une fonction mathématique, appelée DCT (transformée cosinus discrète), qui transforme les variations de luminosité en fréquences. Les 64 valeurs obtenues sont ensuite simplifiées en fonction de l'indice de compression choisi.
3. Avec un petit coup de RLE, on compacte les nombreuses valeurs nulles.
4. Il ne reste plus qu'à compresser encore avec Huffman.

Lorsque l'on pousse le taux de la compression, on obtient une détérioration sensible de la qualité. On voit alors apparaître des tâches qui n'existaient pas, due à l'effet de bloc décrit plus haut, et des bavures dans les zones de transition entre deux couleurs. (voir ci-dessous).
Un indice de compression de 20 est conseillé : la qualité est très bonne et le taux de compression dépasse les 20:1.

Formats de fichier : JPG-JFIF (Certains logiciels supportent la compression JPEG en format TIF ou EPS)

Fractale
 
Une fractale : quesako ? C'est une équation mathématique !
Un objet fractal est créé par la répétition infinie d'un ou de plusieurs motifs.
Pour mieux comprendre, cliquez ici

Le codage :
La compression d'images par transformation fractale fait l'objet d'un brevet de Iterated Systems Inc.
Le système de codage des images en fractales reposent sur l'idée suivante :
Une image peut être décrite à partir d'un ensemble de motifs identiques en nombre limité, transformés par translations, rotations, symétries et agrandissements ou réductions. Pour codé l'image, il suffit de décrire les motifs originaux et les transformations utilisées. Le codage d'une image devient donc indépendant de sa taille.
La compression peut être effectuée soit par logiciel, ou par carte accélérateur spécialisée. Le problème est le temps de compression très élevé (plusieurs minutes) alors qu'à l'inverse la décompression est extrêmement rapide (environ une seconde).
A la différence du JPeg, en forçant le taux de compression, l'image devient floue mais aucune pixelisation n'apparaît. D'autre part, la taille de l'image n'influençant pas celle du fichier, il est possible de zoomer dans l'image, tout en conservant une excellente définition.

Format de fichier : FIF

Ondelettes

Avant de parler de compression, il faut définir ce qu'est le codage par ondelettes.

Le codage : L'idée est de diviser la résolution de l'image en codant la perte d'information découlant de cette division.
 
Pour chaque niveau :
1. On part d'une image A.
2. On divise par 2 la définition horizontale de l'image en moyennant les pixels deux à deux suivant l'axe horizontal. On obtient B.
3. Pour chaque pixel, on calcule l'erreur entre l'image originale et l'image B. On obtient C.
4. Pour B et C, on moyenne les pixels deux à deux mais cette fois suivant l'axe vertical. On obtient D et E.
5. Pour B comme pour C, on répète l'étape 3 et on obtient F et G.
L'image D obtenue est une image dont le résolution est divisée par 2 dans les deux sens. Les images E, F et G nous donnent les erreurs entre A et D.
On peut alors répété cette transformation sur l'image D et ce jusqu'à atteindre le niveau voulu. En inversant le processus, on reconstruit l'image originale dans son intégralité.
La compression :
On effectue le codage comme décrit ci dessus mais les images "d'erreurs" inférieures à un certain niveau sont éliminées. Cette compression est destructive. Ce paramètre étant réglable, il est possible de prévoir la taille du fichier compressé, ce que ne fait pas le JPeg.
La dernière étape consiste à utiliser une compression non destructrice pour ce qui reste.
Un autre avantage de ce procédé sur le JPeg c'est que l'entête du format de fichier WI qui encapsule les images est plus compact.
Lorsque l'on pousse le taux de la compression, là encore la qualité se détériore. A la différence du JPG, pas de pixelisation mais un flou de plus en plus important. (voir ci-dessous). Un indice de compression de 20 est conseillé : très bonne qualité est et un taux de compression dépassant les 40:1.

Format de fichier : WI (ou TIF-WI)