Made by Gaël Jaboulay
Codage binaire et symbolique
Les données graphiques peuvent être codées sous forme binaire, comme une image TIFF par exemple. Pour comprendre une telle image un interpréteur est nécessaire. C’est, en général, le cas du codage des bitmaps. Le codage symbolique (généralement sous forme de caractères ASCII) est celui des images vectorielles. Une exception de taille : les fichiers PostScript qui utilisent des caractères ASCII pour coder des images bitmap.
Compression symétrique et dissymétrique
Un algorithme de compression symétrique utilise le même temps pour comprimer que pour décomprimer une image. Ce type d’algorithme est nécessaire pour l’acquisition et la compression en temps réel. Les algorithmes dits asymétriques prennent beaucoup plus de temps pour la compression que pour la décompression. La compression n’est pas faite en temps réel, et le temps total de capture des images, acquisition et compression, est beaucoup plus long. Par contre, comme la compression se fait sans contrainte de temps, la qualité obtenue est meilleure. Le module de compression peut prendre le temps d’analyser chaque image et déterminer les meilleurs paramètres de compression possible. Le facteur de compression est en général lui aussi plus fort. Ce principe de compression asymétrique est intéressant, car il permet de générer plus facilement des séquences pour des supports tels que le CD-ROM. De façon générale, les configurations utilisées pour la conception des séquences sont nettement plus étoffées que celles pour la simple lecture de ces mêmes séquences.
Algorithme RLE
Cette technique consiste à repérer et à éliminer la redondance des données. Une image contient souvent des surfaces de couleurs identiques, il est donc plus efficace de coder cette couleur et sa répétition que de coder unitairement chaque point. Par exemple la séquence '' 4444444 '' est remplacée par '' 4/7 ''. Ce codage appelé RLE '' Run Length Encoding '' est intéressant pour des données comportant peu de valeurs différentes et de longues séquences. Par contre il est moins interressant pour des données textuelles ou de type images photographiques.
Algorithme de Huffman
Le codage Huffman (Huffman 1952) est désormais un standard en matière de compression. Créé à la base pour des fichiers de texte, cette approche a su séduire les concepteurs et est appliquée aujourd’hui aux fichiers les plus divers.Simplement, un code binaire dont la longueur est variable est assigné à chaque valeur selon le schéma suivant : à une valeur fréquemment rencontrée on affecte un code de longueur courte. Une table de conversion recueille les valeurs et le code qui leur est ainsi affecté. Cette table sera passée comme paramètre à tout programme de décodage avant l’envoi des données elles-mêmes. Par cette méthode, le ratio de compression peut atteindre jusqu’à 8:1. La qualité de la compression dépendra de l’algorithme statistique qui établira la conversion. Dans la pratique, ce type de compression est peu efficace pour les fichiers où l’on rencontre de longues chaînes de valeurs différentes et uniques ; car ce genre de fichiers, une fois codés avec cette méthode, deviennent plus longs que les originaux ! Pour cette raison, le codage Huffman est réalisé par deux passages. Le premier passage crée l’algorithme statistique, le second code les données. Un dernier point à relever est la lenteur de cette méthode due au travail intense que le décodage impose au processeur.
Algorithme LZW
A la différence de Huffman, la compression LZW n’a aucun besoin de construire une table de conversion à l’avance. La table se construit au fur et à mesure que la compression se déroule. Dans le cas d’un texte compressé en LZW, chaque nouvelle occurrence d’un mot est remplacée par un pointeur vers la première occurrence rencontrée. Le principe est le même avec des images. Donc, ici, la règle « à fréquence élevée, code court » n’est pas respectée. Les ratios de compression obtenus avec cette méthode varient entre 1:1 et 3:1, bien que certaines images fortement sous-séquencées puissent atteindre jusqu’à 10:1. La compression LZW est utilisée par les formats GIF et TIFF.
Compression arithmétique
A la manière du codage Huffman, la compression arithmétique utilise des codes courts pour des valeurs fréquemment rencontrées. L’amélioration réside dans le codage, qui est effectué cette fois sur des séquences de valeurs, et non plus des valeurs prises individuellement. La compression arithmétique rejoint presque les limites théoriques de la compression et son efficacité est étonnante : jusqu’à 100:1 de ratio de compression. La complexité de cette méthode empêche toute explication succincte.
Algorithme JPEG
Sous cette appellation se cachent plusieurs techniques de compression dont le principe est le suivant : peu importent les données originales, on ne garde que celles dont on ne peut se passer, les autres sont perdues. Ce principe n’est évidemment pas applicable à tous les domaines, mais pour l’imagerie commerciale (dont la télévision et les applications multimédia) il fait merveille. A titre indicatif, une image couleur de 1145 Ko peut être archivée à 58 Ko, sans perte d’information remarquable !
Le fonctionnement de cette compression est le suivant :
1. Conversion de l’image RGB en une image luminance/chrominance
2. On découpe l’image en blocs de 8*8 pixels
3. On traduit le bloc de pixels en 64 coefficients d’éloignement par rapport à la moyenne
4. On élimine les redondances d’information
5. d’après un ratio déterminé, une transformation cosinusoïdale discrète (DCT en anglais : cette transformation algébrique traduit un tableau d’intensités en un tableau de fréquences) est appliquée aux données, le but est de réduire le volume d’informations par quantification (c’est cette opération qui altère et réduit les données initiales)
6. finalement, les données quantifiées sont compressées soit en Huffman, soit en arithmétique.
Cet algorithme est de type “Lossy” car il y a perte d’information : en effet, cette technique profite des imperfections de la perception de l'oeil humain. L'oeil perçoit mieux les contrastes sur les faibles que sur les fortes intensités; cette propriété a des conséquences sur le nombre de niveaux qui servent à coder l'image; celui-ci pourra être plus faible pour les faibles intensités. Ex: sur une zone de l'image fortement éclaircie, les valeurs du signal vidéo pourront être codées sur 5 bits (32 niveaux) au lieu de 8 bits (256 niveaux). L'oeil est plus sensible à l'intensité qu'à la couleur. La moins grande sensibilité à la couleur, va permettre de numériser la composante couleur de l'image (chrominance), avec moins d'échantillons sans dégradation apparente. Rapport de 1 à 2 par rapport à la luminance. L'oeil enfin, agit comme un intégrateur sur les hautes fréquences spatiales des images. Ainsi, on peut directement éliminer certaines informations correspondant aux hautes fréquences de l'image, ce qui a pour effet de créer des portions d'images plus uniformes, et donc favoriser les opérations d'élimination de redondance. Par exemple, une zone comportant une alternance très serrée de raies noires et blanches peut être représentée par un nombre unique correspondant au gris. On admet qu'un taux de compression inférieur à 25 est possible sans altération de l'image; au delà, les différences sont beaucoup plus apparentes.
Voir http://tecfa.unige.ch/guides/tecfaman/unix-68.html