Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Dossier : La compression d'images numériques
(Article écrit par Jean-François Pillou - 2003)
|
|
Note : ce document est issu de Comment Ça Marche
et mis à disposition sous les termes de la licence
Creative Commons.
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 larges 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 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 |
Voici l'arbre correspondant :
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 compression, 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 s'ajouter à 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 occurrences
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") 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 dues à 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).
|
