Dans la compression sans perte, on réduit la taille sans altérer le contenu. Le principe est d’utiliser la redondance de l’information (répétitions). Elle a comme avantage la réversibilité.
Exemples : RLE,VCL,LZW (zip)…
Dans la compression avec perte, réduit fortement la taille au detriment d’une perte d’information. Le principe est d’enlever les informations les moins importantes. Inconvénient majeur est la non réversible (artefacts lors de la décompression)
Exemples : JPEG, JPEG2000, PNG…
Codage RLE
RLE ou Codage Run Length Encoding est un algorithme de compression sans perte. il est utilisé dans les formats BMP, TIFF. l’idée est de regrouper les plages de valeurs identiques.
Exemple:
AAAAARRRRRROLLLBBTTTTT : 22 caractères
5A6R1O3L2B5T : 12 caractères Taux = 45%
En pratique : format binaire, par exemple 1 octet pour le compteur puis un octet pour la valeur.
L’octet 0 peut servir de caractère spécial pour introduire par exemple une suite de données non compressées.
Codage d’Huffman
 |
 |
| Dans cet exemple, il y a 36 bloques de 2×2 bits, au total 144 bits. | On commence par le calcul des fréquences d’apparition des blocs |
On trie les boques par fréquence d’apparition :
On met les deux plus faibles éléments dans les branches et on crée ainsi le nœud parent avec une fréquence qui est la somme des deux fréquences des deux faibles éléments.
Les deux éléments sont enlevés de la liste et le nouveau nœud Parent (avec une fréquence égale à 9) est inséré dans la liste. On obtient alors la liste suivante, triée par fréquence :
Le même principe est réutilisé, en combinant les deux éléments les plus faibles. Le résultat est le suivant:
On continu avec la même procédure jusqu’à ce qu’il reste un seul élément dans la liste à gauche.
Pour générer le code d’Hoffman, on parcoure l’arbre à la valeur qu’on veut, on met un 0 à chaque fois qu’on emprunte une branche de gauche et un 1 pour une branche de droite.
 |
 |
Le resultat est le suivant:
|
|
 |
Les codes des éléments les plus probables sont plus courts que ceux des éléments les moins probables.
Algorithme JPEG
JPEG : un algorithme de compression avec perte
On veut supprimer de l’information sans perdre des informations importantes
Vision humaine :
l’oeil est plus sensible à la luminance (intensité) qu’aux nuances de couleur.
l’oeil humain est plus sensible aux basses fréquences
Conclusion :
on réduit la partie de codage consacrée aux nuances de couleur on supprime en priorité les hautes fréquences d’une image
Chaque image est décomposée en blocs de taille 8 x 8.
Chaque matrice 8 x 8 est transformée en une autre matrice par la DCT (Discrete Cosinus Transform).
On obtient une nouvelle matrice de même taille, à valeurs réelles, qui contient la même information que la matrice de départ.
Les hautes fréquences correspondent aux coefficients en bas à droite de la matrice DCT.
On divise terme à terme la matrice DCT par une matrice de quantification prédéfinie.
On conserve l’arrondi de la division, souvent nul pour une valeur de MQ élevée.
On transforme chaque matrice en vecteur :
• Lecture en Zig‐Zag
• Permet d’obtenir de longues plages de 0
• Les vecteurs sont compressés par un codage sans perte, RLE pour les plages de 0 puis Huffman
