Avec mon camarade Jean-Baptiste DODANE (mail, URL), nous avons choisi d'étudier la compression des images numériques.
Nous ne nous sommes pas arrêtés à une simple étude théorique, mais nous avons également programmé les principaux algorithmes (JPEG, LZW, RLE, Huffman, codage prédictif) et créé nos propres formats les utilisant.
Plan du dossier
1. Généralités1.1. Le stockage des images informatiques
1.1.1. Le mode de stockage
1.1.2. La couleur (RGB, luminance, chrominance)
1.1.3. Le format BMP (structure, entête)
1.2. Algorithmes de compression généraux
1.2.1. évaluation de la compression
1.2.2. La compression RLE
1.2.3. Le codage de Huffman
1.2.4. Les algorithmes à dictionnaire (LZ**)
2. La compression graphique conservative
2.1. Mise en oeuvre de la RLE et démarche
2.1.1. Au commencement
2.1.2. Le traitement de l'image
2.1.3. Notre format
2.1.4. Résultats
2.2. Mise en oeuvre de la LZW
2.2.1. Fonctionnement du dictionnaire
2.2.2. Caractéristiques de notre format WTPE et démarche
2.3. Le codage prédictif et sa mise en oeuvre
2.3.1. Principe du codage prédictif
2.3.2. Caractéristiques de notre format PTPE et démarche
2.3.3. Résultats
3. La compression non conservative : la norme JPEG
3.1. Théorie et principes de la norme JPEG
3.1.1. La transformée en cosinus discrète (DCT)
3.1.2. La méthode JPEG
3.2. Mise en oeuvre du JPEG
3.2.1. Vérification expérimentale des fondements de la méthode JPEG
3.2.2. Caractéristiques de notre format JTPE et démarche
3.3. Etude des pertes dues à la compression
3.3.1. Méthode JPEG
3.3.2. Images satellites
Contenu complet du TPE en téléchargement
| Dossiers (PDF) |
|
|||||
|---|---|---|---|---|---|---|
| Soutenance (PPS) |
|
|||||
| Programme |
|
|||||
| Contacts |
|
|||||
| Liens |
|
Présentation générale de la compression
Des problèmes se sont posés très tôts pour le stockage et la transmission des données informatiques, liés au limitations technologiques. De plus les images numériques font partie des données dont le stockage nécessite le plus de place. Une technique alors employée est la compression des informations, qui consiste à réduire la taille des données sans en perdre le contenu.
Plusieurs techniques existent, répondant à certains critères : difficulté de mise en oeuvre, efficacité de la compression, vitesse d'exécution, degré de conservation de l'information. Selon l'utilisation, tel ou tel critère doit être privilégié, et l'algorithme de compression doit être choisi en conséquent. Par exemple en astronomie on privilégiera la qualité, et pour les appareils photographiques numériques la difficulté de mise en oeuvre, pour ne pas avoir à réaliser de circuits trop complexes.
Vous trouverez ici une présentation de principaux algorithmes de compression, générale ou spécifique aux images. Vous pouvez vous reporter à notre TPE pour les démonstrations, détails techniques et pratiques, exemples détaillés et mises en oeuvre.
Les algorithmes de compression généraux
La compression RLE
La méthode de compression RLE (Run Length Encoding), appelée aussi RLC (Run Length Coding), est l'une des plus simples qui soit. Le principe est de remplacer une séquence de n éléments v identiques par un couple (n, v). C'est un peu comme remplacer des additions par une multiplication.Exemple : ABBBBCAAACCC donne 1A 4B 1C 3A 3C, ainsi 10 symboles en remplacent 12
Cependant cette méthode peut augmenter la taille des données si celles-ci comportent peu de suites de symboles identiques, des améliorations de cet algorithme existent donc : n'utiliser cette méthode que lorsque trois symboles sont répétés et donc que l'opération est rentable. Pour cela il suffit de commencer par indiquer le nombre de symboles non compressables, puis appliquer l'algorithme sur la série de symboles suivante pour laquelle il faut appliquer l'algorithme etc. Il faut bien entendu utiliser des codes spéciaux qui donnent une information sur les opérations à effectuer au décodage, tout cela est détaillé dans notre TPE.
Cette méthode a le bénéfice d'être simple, rapide et peu demandeuse de ressources. Elle peut être extrêmement efficace sur certaines données, mais en général reste faible seule, c'est pourquoi elle est très souvent utilisée en complément d'une autre méthode. On la trouve ainsi dans de nombreux formats (BMP, PCX, TIFF, JPEG, PSP ...)
Le codage de Huffman
Le codage de Huffman est un codage statistique, c'est à dire qu'il se base sur la fréquence d'apparition d'un caractère pour le coder : plus le caractère apparaît souvent plus son code sera court et vice-versa. C'est pourquoi on appelle aussi ce codage un VLC (Variable Length Code, code à taille variable) préfixé. En effet chaque code n'est le préfixe d'aucun autre, d'où préfixé, ce qui permet un décodage unique.Dans la pratique, pour déterminer le code de chaque caractère on construit l'arbre de Huffman :
- On calcule la fréquence d'apparition de chaque caractère (ou poids).
- On rassemble les deux caractères de plus faible poids pour former un noeud, dont le poids est égal à la somme des poids des deux caractères qui le composent.
- On affecte la valeur 0 au caractère le plus petit et 1 au caractère le plus grand des deux.
- On recommence les deux étapes précédentes en considérant chaque noeud formé comme un caractère, jusqu' à n'avoir plus qu'un noeud, la racine.
Le code du caractère est alors formé par la suite des valeurs (0 ou 1) des branches par lesquelles on passe pour aller du symbole à la racine de l'arbre (pour des détails et exemples, voir le TPE, et la soutenance pour les animations). Ainsi si un symbole apparait souvent, il sera utilisé tardivement dans l'élaboration de l'arbre, donc sera proche de la racine et aura un code court.
Il existe trois variantes de cet algorithme :
- Non adaptative : l'arbre est élaboré à partir d'une table des fréquences fixe ce qui fait qu'il est adapté à un seul type de donnée.
- Semi adaptative : comme dans l'exemple, on lit une fois le fichier à compresser pour créer la table des fréquences, puis on s'en sert pour compresser le fichier. C'est la méthode la plus efficace mais elle présente l'inconvénient de nécessiter l'arbre que l'on devra introduire dans un en-tête.
- Adaptative : la table des fréquences est élaborée au fur et à mesure de la lecture du fichier et l'arbre est reconstruit à chaque fois. On réalise l'arbre avec les premiers caractères (que l'on ne compresse pas) et on s'en sert pour compresser les caractères suivants que l'on utilise aussi pour actualiser l'arbre etc. Elle est un peu moins efficace que la méthode semi adaptative mais le résultat final est souvent meilleur car elle ne nécessite pas le stockage de l'arbre, et de plus elle ne nécessite qu'une seule lecture du fichier.
Les algorithmes à dictionnaires LZ**
Les algorithmes à dictionnaire, aussi appelés à substitution de facteurs, consistent à remplacer des séquences (les facteurs) par un code plus court qui est l'indice de ce facteur dans un dictionnaire.LZ77
Le premier algorithme de ce type a été publié par Lempel et Zif en 1977 sous le nom de LZ77, et a relancé la recherche dans la compression par son efficacité révolutionnaire.L'algorithme utilise le principe d'une fenêtre coulissante de longueur, divisée en 2 parties, qui se déplace sur le texte de gauche à droite. La seconde partie, le tampon de lecture, rencontre le texte en premier. La première partie constitue le dictionnaire. Initialement, la fenêtre est située de façon à ce que le tampon de lecture soit positionné sur le texte, et que le dictionnaire n'y soit pas. A tout moment, l'algorithme va rechercher, dans le dictionnaire le plus long facteur qui se répète au début du tampon de lecture, que l'on code par le triplet (i, j, c) où :
- i est la distance entre le début du tampon et la position de la répétition dans le dictionnaire.
- j est la longueur de la répétition.
- c est le premier caractère du tampon différent du caractère correspondant dans le dictionnaire.
L'avantage de la méthode, outre son efficacité est qu'elle ne nécessite qu'une lecture du fichier (contrairement au codage de Huffman).
LZ78
Il s'agit simplement d'une amélioration par les mêmes auteurs. Il n'y a plus de fenêtre coulissante, mais un pointeur qui suit le texte et un dictionnaire indépendant, dans lequel on cherche les facteurs situés au niveau du pointeur. Il suffit d'encoder le couple (n, c) où :- n est l'index du facteur dans le dictionnaire
- c est le premier caractère du tampon différent du caractère correspondant dans le dictionnaire.
Il n'y a donc plus que deux informations à coder au lieu de trois dans la méthode LZ77.
LZW
En 1984 Welch publie son travail de complément de la méthode LZ. Il a réussit à n'avoir plus qu'une information à coder, en utilisant un dictionnaire dynamique, qui se construit au fur et à mesure que l'on scanne le fichier à compresser. On ne transmet pas le dictionnaire ainsi formé, mais on le reconstruit de la même façon à la décompression.Cette méthode est brevetée, et la plus utilisée aujourd'hui, notamment dans le format GIF.
Les algorithmes à dictionnaire sont les plus utilisés de nos jours, notamment dans tous les gros compresseurs et les formats ZIP ou RAR par exemple. Vous pourrez trouver le détail complet du fonctionnement de la méthode LZW, sa mise en oeuvre et les sources, ainsi que des précisions sur les algorithmes LZ77 et LZ78 dans notre TPE.
La compression conservative
La compression RLE et LZW
Ces algorithmes généraux de compression peuvent s'appliquer avec profits à la compression des images. En tant que méthodes générales elles sont bien entendu conservatives, c'est à dire que le fichier décompressé est exactement identique à l'original (indispensable pour les fichiers en général).La RLE comme nous l'avons expliqué, même si elle peut être utilisée seule dans certains formats BMP par exemple, est non seulement souvent utilisée en complément d'autres méthodes, mais ces autres méthodes l'utilisent quasi-systématiquement grâce à sa simplicité.
En revanche la LZW s'applique très bien seule, mais uniquement pour les images de faibles profondeurs (nombre de couleurs différentes) puisque les motifs différents doivent être relativement faibles pour être répétés.
C'est pourquoi une autre méthode peut s'appliquer pour les images en couleurs vraies, plus efficace que la LZW mais qui pourtant ne semble être utilisée officiellement par aucun format.
Le codage prédictif
Comme son nom l'indique, le codage prédictif effectue une prédiction. étant donné que des blocs d'une image en couleurs vraies (24 bits) ont tendance à varier d'une manière progressive, c'est à dire que deux blocs voisins ont de sérieuses chances d'être similaires, on peut essayer, à partir de quelques pixels, d'imaginer ce que pourraient être les pixels voisins. Le but est alors de stocker la différence entre la couleur du pixel et sa prédiction, qui sera généralement faible. Cette différence est donc une valeur non plus absolue, mais relative.Cependant on se rend vite compte que le principe de coder la différence entre la valeur prédite et la valeur réelle ne peut pas être utilisée seul. En effet, en considérant par exemple que chaque pixel (ou composante) est codé sur un octet (256 niveaux), si on prédit qu'une valeur sera égale à 0, et qu'en réalité elle est égale à 255, il faudra enregistrer 255, et si on prédit qu'elle sera égale à 255 et qu'en fait elle est nulle, on devra enregistrer -255. Cela fait donc une amplitude de 511 niveaux, qu'il faudrait enregistrer au minimum avec 9 bits puisqu'il faut prévoir toutes les possibilités, ce qui augmenterait la taille du fichier.
Mais les valeurs à coder seront en revanche généralement faibles, et donc plus fréquentes. En codant les données avec un codage statistique de type Huffman, celui-ci affectera un code court à ces valeurs fréquentes, d'où un gain notable de place. On peut également traiter les valeurs nulles avec une RLE (avant Huffman), puisque pour des étendues de même couleur la différence entre la valeur prédite et la valeur réelle sera nulle.
Divers paramètres doivent être étudiés pour une efficacité optimale, comme les pixels utilisés pour la prédiction, toujours détaillé dans notre TPE avec les logiciels et leurs codes sources complets.
Cette méthode est la plus efficace des méthodes conservatives, mais reste extrêmement faible face à des méthodes non conservatives tel JPEG, ce qui explique son utilisation rare.
La compression non conservative : norme JPEG
Le JPEG est simplement une méthode de compression mais n'est pas un format : le format .jpg le plus utilisé est en fait le format JFIF (Jpeg Interchange Format), mais la méthode JPEG est aussi utilisée dans d'autres formats comme le TIFF ou le TGA, et même pour stocker les images dans les appareils photographiques numériques.C'est une méthode destructive (elle perd une partie des données) qui est adaptée aux images naturelles pour lesquelles elle donne de très forts taux de compression pour une perte de qualité indécelable, car elle exploite les défaillances de notre système de vision, mais en revanche elle convient mal aux images géométriques.
La transformée en cosinus discrète
La clé du processus de compression est la DCT bidimensionnelle (Discrete Cosine Transform) ou transformée en cosinus discrète, une variante de la transformée de Fourier discrète. Comme cette dernière elle transforme un signal discret (signal composé d'éléments distincts, les pixels dans notre cas) bidimensionnel d'amplitude en une information bidimensionnelle de fréquence.La transformée de Fourier unidimensionnelle décompose un signal que l'on peut se représenter par une courbe, en une somme de sinusoïdes de différentes fréquences, amplitudes et phases. Elle se présente sous la forme de pics dont l'emplacement donne la fréquence de la composante et leur hauteur donne son amplitude. Le filtrage (élimination des hautes, moyennes ou basses fréquences) est alors très simple. La transformée en deux dimensions réalise la même chose, mais décompose le signal en une évolution verticale et horizontale.
Or une image n'est en principe pas périodique, il faut donc périodiser le signal. La transformée en cosinus, semblable à la transformée de Fourier, diffère dans la manière dont le signal est périodisé puisqu'au lieu de coller les intervalles bout à bout, ce qui crée des discontinuités et donc des hautes fréquences parasites, elle le fait en le "dépliant" (voir détail dans le TPE ). De plus elle ne conserve pas l'information de phase (le résultat est réel et non complexe), mais celle-ci n'est pas utile pour les images.
Le résultat se présente sous la forme d'une matrice, dont le coefficient en haut à gauche est la composante DC (pour Direct Component) ou coefficient continu, qui représente la valeur moyenne des éléments avant transformations. Les autres éléments sont les composantes AC (Alternative Coomponent) qui représente l'amplitude des fréquences spatiales.
Cette opération est réversible, et la transformée inverse IDCT permet de restituer exactement les données de départ (en l'absence d'erreurs d'arrondis)
Le détail du fonctionnement de ces transformées et des exemples sont disponibles dans notre TPE , ainsi que des démonstrations pratiques dans le logiciel.
Les étapes de la méthode JPEG
Préparation
On va donc commencer par traduire les informations du modèle RGB au modèle Luminance - Chrominance, et étant donné que notre oeil est plus sensible à la luminance qu'à la chrominance on va pouvoir stocker avec moins de précision la chrominance. Par exemple, l'oeil ne peut discerner de différences de chrominance au sein d'un carré de 2 x 2 points, et on va donc sous échantillonner la chrominance (regrouper les pixels par carrés de quatre et ne prendre que la moyenne de leur chrominance).DCT
On applique ensuite la transformée en cosinus. Mais le calcul ne peut se faire sur l'image entière d'une part parce que cela génèrerait trop de calculs, et d'autre part le signal de l'image doit absolument être représenté par une matrice carrée. On va donc décomposer l'image en blocs de 8 pixels de côté et on appliquera la DCT indépendamment sur chacun de ces blocs. Les plus petits blocs en bordure devront être traités par une autre méthode.Quantification
C'est la seule étape non conservative (sauf les erreurs d'arrondis dans les précédentes étapes). La transformée en cosinus nous donne des informations sur la fréquence ce qui va permettre de filtrer de l'information. En effet, non seulement l'information effective de la plupart des images naturelles est concentrée dans les basses fréquences, mais de plus notre oeil est beaucoup moins sensible aux fréquences élevées (changements de couleur brusques) qu'aux fréquences basses (changements lents). La quantification consiste donc à diminuer la précision des fréquences élevées, en divisant chaque élément DCT par l'élément correspondant dans la table de quantification, et en arrondissant à l'entier leplus proche (voir exemple plus loin). Ainsi beaucoup d'éléments deviendront nuls ou très faibles et occuperont donc moins de place.
Linéarisation
Pour écrire le bloc dans un fichier il nous faut une suite d'octets et nous avons une matrice carrée. Il faut donc la linéariser. On va pour cela employer une méthode particulière, dite de zigzag, de façon à regrouper ensemble les éléments les moins importants (voir exemple plus loin).Codage
Les composantes DC sont généralement de grands nombres mais en revanche elles varient lentement d'un bloc à l'autre, puisque ce sont les moyennes de leur bloc. On va donc coder non pas la composante DC elle-même mais sa différence avec celle du bloc précédent, ce qui donnera de plus petits nombres prenant moins de place. Cette méthode est appelée DPCM (Differential Pulse Code Modulation). On va ensuite appliquer un codage de Huffman et une RLE pour les zéros qui sont nombreux.Vous pouvez trouver tous les détails de fonctionnement, de mise en oeuvre, formules, exemples, démonstrations et codes sources dans notre TPE.
Cette méthode est aujourd'hui de loin la plus utilisée pour la compression des images en couleur vraie, puisqu'elle peut diviser la taille d'une image par 20 avec une perte de qualité quasiment imperceptible.
Conclusion
La compression graphique peut donc être considérée comme une branche à part de la compression. Si elle peut utiliser seulement des algorithmes généraux (LZW), ceux-ci montrent rapidement leurs limites, surtout pour les images en couleurs vraies. Il faut alors utiliser les propriétés des images afin de trouver de nouvelles méthodes qui y sont adaptées (codage prédictif), quitte à perdre un peu de l'information pour arriver à des taux beaucoup plus élevés (JPEG).En effet, il serait illusoire de croire que la compression devient obsolète à cause de la capacité des mémoires qui augmente sans cesse, car la quantité de données à conserver croît de la même manière, et les réseaux évoluent pour leur part beaucoup moins vite. La compression peut même apporter un gain de vitesse car par exemple il est plus rapide d'enregistrer une image sur son disque dur en JPEG qu'en BMP car on perd moins de temps à compresser l'image qu'à écrire plus de données sur le disque dur.
Enfin, si vous ne l'avez toujours pas compris, le contenu complet de notre TPE est disponible ici en téléchargement, comprenant des détails beaucoup plus poussés que dans cet article de présentation, détails de mise en oeuvre, codes sources en pascal, explications et exemples.