La comprsession d'image

-La concatιnation de points


La concatιnation de point est une mιthode permettant de stocker les points d'une maniθre optimale: pour une image monochrome il n'y a, par dιfinition, que deux couleurs, un point de l'image peut donc κtre codι sur un seul bit pour gagner de l'espace mιmoire.


-La compression RLE


La mιthode de compression RLE (Run Length Encoding, parfois notιe RLC pour Run Length Coding) est utilisιe par de nombreux formats d'images (BMP, PCX, TIFF). Elle est basιe sur la rιpιtition d'ιlιments consιcutifs.

Le principe de base consiste ΰ coder un premier ιlιment donnant le nombre de rιpιtitions d'une valeur puis le complιter par la valeur ΰ rιpιter. Ainsi selon ce principe la chaξne "AAAAAHHHHHHHHHHHHHH" compressιe donne "5A14H". Le gain de compression est ainsi de (19-5)/19 soit environ 73,7%. En contrepartie pour la chaξne "REELLEMENT", dans lequel la redondance des caractθres est faible, le rιsultat de la compression donne "1R2E2L1E1M1E1N1T"; la compression s'avθre ici trθs coϋteuse, avec un gain nιgatif valant (10-16)/10 soit -60%!

En rιalitι la compression RLE est rιgie par des rθgles particuliθres permettant de compresser lorsque cela est nιcessaire et de laisser la chaξne telle quelle lorsque la compression induit un gaspillage. Ces rθgles sont les suivantes :

Lorsque trois ιlιments ou plus se rιpθtent consιcutivement alors la mιthode de compression RLE est utilisιe
Sinon un caractθre de contrτle (00) est insιrι, suivi du nombre d'ιlιments de la chaξne non compressιe puis de cette derniθre
Si le nombre d'ιlιments de la chaξne est impair, le caractθre de contrτle (00) est ajoutι ΰ la fin
Enfin des caractθres de contrτles spιcifiques ont ιtι dιfinis afin de coder :
une fin de ligne (00 01)
la fin de l'image (00 00)
un dιplacement du pointeur dans l'image de XX colonnes et de YY lignes dans le sens de la lecture (00 02 XX YY).
Ainsi la compression RLE n'a du sens que pour les donnιes possιdant de nombreux ιlιments consιcutifs redondants, notamment les images possιdant de large parties uniformes. Cette mιthode a toutefois l'avantage d'κtre peu difficile ΰ mettre en oeuvre. Il existe des variantes dans lesquelles l'image est encodιe par pavιs de points, selon des lignes, ou bien mκme en zigzag.

-Le codage de Huffman

David Huffman a proposι en 1952 une mιthode statistique qui permet d'attribuer un mot de code binaire aux diffιrents symboles ΰ compresser (pixels ou caractθres par exemple). La longueur de chaque mot de code n'est pas identique pour tous les symboles: les symboles les plus frιquents (qui apparaissent le plus souvent) sont codιs avec de petits mots de code, tandis que les symboles les plus rares reηoivent de plus longs codes binaires. On parle de codage ΰ longueur variable (en anglais VLC pour variable code length) prιfixι pour dιsigner ce type de codage car aucun code n'est le prιfixe d'un autre. Ainsi la suite finale de mots codιs ΰ longueurs variables sera en moyenne plus petite qu'avec un codage de taille constante.

Le codeur de Huffman crιe un arbre ordonnι ΰ partir de tous les symboles et de leur frιquence d'apparition. Les branches sont construites rιcursivement en partant des symboles les moins frιquents. La construction de l'arbre se fait en ordonnant dans un premier temps les symboles par frιquence d'apparition. successivement les deux symboles de plus faible frιquence d'apparition sont retirιs de la liste et rattachιs ΰ un noeud dont le poids vaut la somme des frιquences des deux symboles. Le symbole de plus faible poids est affectι ΰ la branche 1, l'autre ΰ la branche 0 et ainsi de suite en considιrant chaque noeud formι comme un nouveau symbole, jusqu'ΰ obtenir un seul noeud parent appelι racine.
Le code de chaque chaque symbole correspond ΰ la suite des codes le long du chemin allant de ce caractθre ΰ la racine. Ainsi, plus le symbole est "profond" dans l'arbre, plus le mot de code sera long.

Soit la phrase suivante : "COMMENT_CA_MARCHE". Voici les frιquences d'apparitions des lettres

M A C E _ H O N T R
3 2 2 2 2 1 1 1 1 1




Les codes correspondants ΰ chaque caractθre sont tels que les codes des caractθres les plus frιquents sont courts et ceux correspondant aux symboles les moins frιquents sont longs :

M A C E _ H O N T R
00 100 110 010 011 1110 1111 1010 10110 10111


Les compressions basιes sur ce type de codage donnent de bons taux de compressions, en particulier pour les images monochromes (les fax par exemple). Il est notamment utilisι dans les recommandations T4 et T5 de l'ITU-T


-La compression LZW


Abraham Lempel et Jakob Ziv sont les crιateurs du compresseur LZ77, inventι en 1977 (d'oω son nom). Ce compresseur ιtait alors utilisι pour l'archivage (les formats ZIP, ARJ et LHA l'utilisent).

En 1978 ils crιent le compresseur LZ78 spιcialisι dans la compression d'images (ou tout type de fichier de type binaire).

En 1984, Terry Welch de la sociιtι Unisys le modifia pour l'utiliser dans des contrτleurs de disques durs, son initiale vint donc se rajouter ΰ l'abrιviation LZ pour donner LZW.
LZW est un algorithme trθs rapide aussi bien en compression qu'en dιcompression, basι sur la multiplicitι des occurences de sιquences de caractθres dans la chaξne ΰ encoder. Son principe consiste ΰ substituer des motifs par un code d'affectation (indice) en construisant au fur et ΰ mesure un dictionnaire. De plus, il travaille sur des bits et non sur des octets, il ne dιpend donc pas de la maniθre de laquelle le processeur code les informations. C'est un des algorithmes les plus populaires, il est notamment utilisι dans les formats TIFF et GIF. La mιthode de compression LZW ayant ιtι brevetιe par la sociιtι Unisys, c'est l'algorithme LZ77, libre de droit, qui est utilisι dans les images PNG.


-Construction du dictionnaire


Le dictionnaire est initialisι avec les 256 valeurs de la table ASCII. Le fichier ΰ compresser est dιcoupι en chaξnes d'octets (ainsi pour des images monochromes - codιes sur 1 bit - cette compression est peu efficace), chacune de ces chaξnes est comparιe au dictionnaire et est ajoutιe si jamais elle n'y est pas prιsente.

-La compression


L'algorithme parcourt le flot d'informations en le codant; si jamais une chaξne est plus petite que le plus grand mot du dictionnaire alors elle est transmise.

-La dιcompression


Lors de la dιcompression, l'algorithme reconstruit le dictionnaire dans le sens inverse, ce dernier n'a donc pas besoin d'κtre stockι.

-La compression JPEG


L'acronyme JPEG (Joint Photographic Expert Group prononcez jipθgue ou en anglais djaypθgue) provient de la rιunion en 1982 d'un groupe d'experts de la photographie, dont le principal souci ιtait de travailler sur les faηons de transmettre des informations (images fixes ou animιes). En 1986, l'ITU-T mit au point des mιthodes de compression destinιes ΰ l'envoi de fax. Ces deux groupes se rassemblθrent pour crιer un comitι conjoint d'experts de la photographie (JPEG).

Contrairement ΰ la compression LZW, la compression JPEG est une compression avec pertes, ce qui lui permet, en dιpit d'une perte de qualitι, un des meilleurs taux de compression (20:1 ΰ 25:1 sans perte notable de qualitι).
Cette mιthode de compression est beaucoup plus efficace sur les images photographiques (comportant de nombreux pixels de couleurs diffιrentes) et non sur des images gιomιtriques (ΰ la diffιrence de la compression LZW) car sur ces derniθres les diffιrences de nuances dϋes ΰ la compression sont trθs visibles.

Les ιtapes de la compression JPEG sont les suivantes :

Rιιchantillonnage de la chrominance, car l'oeil ne peut discerner de diffιrences de chrominance au sein d'un carrι de 2x2 points
Dιcoupage de l'image en blocs de 8x8 points, puis l'application de la fonction DCT (Discrete Cosinus Transform, transformation discrθte en cosinus) qui dιcompose l'image en somme de frιquences
Quantification de chaque bloc, c'est-ΰ-dire qu'il applique un coefficient de perte (qui permet de dιterminer le ratio taille/qualitι) "annulera" ou diminuera des valeurs de hautes frιquences, afin d'attιnuer les dιtails en parcourant le bloc intelligemment avec un codage RLE (en zig-zag pour enlever un maximum de valeurs nulles).
Encodage de l'image puis compression avec la mιthode d'Huffman
Le format de fichier embarquant un flux codι en JPEG est en rιalitι appelιs JFIF (JPEG File Interchange Format, soit en franηais Format d'ιchange de fichiers JPEG), mais par dιformation le terme de "fichier JPEG" est couramment utilisι.

Il est ΰ noter qu'il existe une forme de codage JPEG sans perte (appelι lossless). Bien que peu utilisι par la communautι informatique en gιnιral, il sert surtout pour la transmission d'images mιdicales pour ιviter de confondre des artefacts (purement liιs ΰ l'image et ΰ sa numιrisation) avec de rιels signes pathologiques. La compression est alors beaucoup moins efficace (facteur 2 seulement).



--------------------------------------------------------------------------------