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 octet pour gagner de l'espace mémoire.
C'est une méthode utilisée par de nombreux formats d'images (BMP, PCX, TIF).
Elle est basée sur la répétition de bits consécutifs. Une première valeur (codée
sur un octet) donne le nombre de répétitions, une seconde la valeur à répéter
(codée elle aussi sur un octet.
la phrase suivante "aaaaahhhhhhhhhhhhhh" donnerait "5a14h", elle est trés utile
dans ce cas là.
Par contre dans "salut" cela donne "1s1a1l1u1t", elle s'avère ici très coûteuse...
Malgré tout cette méthode est peu difficile à mettre en oeuvre. Il exsite des
variantes dans lesquelles on encodera l'image par pavés de points, selon des
lignes, ou bien même en zigzag.
Ses créateurs sont Abraham Lempel et Jakob Ziv, ils ont créé le compresseur
LZ77 en 1977 (d'où son nom). Il é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 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,
il substitue des motifs 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 utilisé pour les formats
TIFF et GIF.
Construction du dictionnaire:
Le dictionnaire est initialisé avec les 256 valeurs de la table ASCII. Le fichier
est découpé en chaîne d'octets (ainsi pour des images monochromes - codées sur
2 bits - 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. Pour la
décompression l'algorithme reconstruit le dictionnaire dans le sens inverse,
il n'a donc pas besoin d'être stocké.
Compression
L'algorithme parcourt le flot d'information en le codant, si jamais une chaîne
est plus petite que le plus grand mot du dictionnaire elle est transmise.
C'est David Huffman qui l'a mis au point en 1952. Ce type de compression donne
de bons taux de compressions, notamment pour les images monochromes (les faxs
par exemple).
Son nom (Joint Photographie Expert Group) 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'IUT-T mis au point des méthodes de compression destinées à l'envoi de
fax. Ces deux groupes se rassemlè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 beacoup plus efficace sur les images photographiques
(comportant plein de pixels de couleur différente) et non sur des images géométriques
(à la différence de la compression LZW).
Les ruses:
Il rééchantillonne la chrominance car l'oeil ne peut discerner de différences
de chrominance au sein d'un carré de 2x2 points
Il découpe l'image en blocs de 8x8 points, puis lui applique la fonction
DCT(Discrete Cosinus Transform, transformation discrète en cosinus)
qui décompose l'image en somme de fréquences
Chaque bloc est quantifié, c'est-à-dire qu'il applique un coefficient de
perte (qui permet de déterminer le ratio taille/qualité) qui divisera chaque
fonction DCT
L'image est encodé puis compressée avec la méthode d'Huffman
