La compression D.C.T.





I)Le codage luminance et chrominance

Il est reconnu de puis longtemps que notre oeil est plus sensible à la luminance (intensité de la lumière) qui sont des basses fréquences qu'à la chrominance (les couleurs) qui sont des hautes fréquences. La première technique pour réduire la taille d'une image est donc de donner plus d'importance aux informations de luminance que de chrominance. C'est ce qui est notamment utilisé dans une compression destructive.


II)Compression destructive

 Ainsi, c'est dans cette dernière que 'on rentre dans le domaine de compression avec perte d'information. Le but est de perdre le minimum d'information de manière à garder un aspect visuel le plus proche. Ce type de compression n'est pas adaptable à toutes les données mais 'on peut retrouver les mêmes concepts dans la compression du son.


III)La D.C.T. ( Discrete Cosine Transform)

Elle fait parti des compressions destructives et se regroupe en 4 étapes :



A)La préparation

Les informations sur la luminance (paramètre y) et la chrominance 1 et 2(paramètres I et Q) sont des combinaisons linéaires des intensités de rouge (R), vert(G), et bleu (B).
Par ex :
Y= 0.30R + 0.59G + 0.11B
I=0.60R – 0.28G – 0.32B
Q=0.21R– 0.52G + 0.31B
Chacune des trois variables est reprise sous forme de matrice 620*480. Cependant, les matrices I et Q (info sur la chrominance) peuvent être réduites à des matrices 320*240 en prenant les moyennes des valeurs des pixels regroupés par carré de quatre (car l'oeil y est peu sensible). Puis pour des questions de précisions, 'image est centrée sur ce principe :
Comme chaque point de chaque matrice est une info codée sur 8 bits, il y a 256 niveaux possibles (0-255). En soustrayant 128 à chaque élément, on met à zéro le milieu de la gamme de valeur possible : de -128 à +127. Enfin chaque matrice est partagée en bloc de 8*8.


B)La Décomposition ou transformation

La clé du processus de compression est la D.C.T. Elle prend un ensemble de points d'un domaine spatial et les transforme sur en une représentation équivalente dans le domaine dans le domaine fréquentiel ; et cela sur le modèle de la transformation de fourrier:



Elle s'opère sur un signal en trois dimensions. En effet, le signal est une image graphique, les axes x et y étant deux dimensions de 'écran, et 'axe des z reprenant 'amplitude du signal, c'est à dire la valeur du pixel en un point particulier de 'écran.
La D.C.T. convertit donc une info spatiale en une information spectrale dont les axes x et y représentent les fréquences du signal en deux dimensions. La D.C.T. est donc effectuée sur chaque matrice 8*8 de coefficients de fréquence : 'élément (0,0) représentera la valeur moyenne du bloc, les autres indiqueront la puissance spectrale pour chaque fréquence spatiale.
Elle serait conservative si elle ne tiendrait pas compte des erreurs d'arrondis qu'elle introduit ( notamment dans le calcul de la valeur moyenne).

Voilà; ce que donne cette étape :



En bas à droite, faible voir nul car hautes fréquences à cet endroit; comme le montre ceci :




C)La Quantification

Le but de la deuxième étape de la méthode JPEG, l'étape de quantification, est de diminuer la précision du stockage des entiers de la matrice DCT pour diminuer le nombre de bits occupés par chaque entier. C'est la seule partie non-conservative de la méthode (excepté les arrondis effectués). Puisque les informations de basses fréquences sont plus pertinentes que les informations de hautes fréquences, la diminution de précision doit être plus forte dans les hautes fréquences.

La perte de précision va donc être de plus en plus grande lorsqu'on s'éloigne de la position (0,0). Pour cela on utilise une matrice de quantification contenant des entiers par lesquels seront divisées les valeurs de la matrice DCT. Ces entiers seront de plus en plus grands lorsqu'on s'éloigne de la position (0,0). Elle filtre les hautes fréquences.

La valeur d'un élément de la matrice DCT quantifiée sera égale à l'arrondi, à l'entier le plus proche, du quotient de la valeur correspondante de la matrice DCT par la valeur correspondante de la matrice de quantification. Lors de la décompression, il suffira de multiplier la valeur de la matrice DCT quantifiée par l'élément correspondant de la matrice de quantification pour obtenir une approximation de la valeur de la DCT. La matrice obtenue sera appelée matrice DCT déquantifiée.
Bien que la spécification JPEG n'impose aucune contrainte sur la matrice de quantification, l'organisme de standardisation ISO a développé un ensemble standard de valeurs de quantifications utilisables par les programmeurs de code JPEG. Les matrices de quantifications intéressantes sont celles permettant de ``choisir'' la perte de qualité acceptable. Ce choix a été rendu possible grâce aux tests intensifs des matrices.

Voici un exemple de matrice de quantification avec un facteur de qualité de 2 (qui apporte des changements importants à la matrice DCT, mais des modifications mineures à l'image) : On part de la matrice dct puis on utilise la matrice de quantification puis on obtient la matrice de dct quantifiée.

De manière générale, dans cette étape on "écrase" les hautes fréquences pour privilégier les basses fréquences auxquelles l'oeil humain est plus sensible.


D)Codage entropique ou réversible

 Avant toute chose, la matrice représentant l'image [en deux dimensions] est linéarisée afin de subir un codage réversible (ou entropique). Il est effectuée en diagonale, on parle aussi de méthode zigzag.

Par ex cette matrice dct quantifiée :



donnera alors la suite suivante : 150, 80, 92, 26, 75, 20, 4, 18, 19, 3, 1, 2, 13, 3, 1, 0, 1, 2, 2, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, etc.

Cette séquence a la propriété de parcourir les éléments en commençant par les basses fréquences (plus importantes) et de traiter les fréquences de plus en plus hautes. Puisque la matrice DCT quantifiée contient beaucoup de composantes de hautes fréquences nulles, l'ordre de la séquence zigzag va engendrer de longues suites de 0 consécutifs. D'autres mécanismes sont mis en oeuvre pour comprimer la matrice DCT quantifiée.

Les suites de valeurs nulles sont simplement codées en donnant le nombre de 0 successifs.

Ensuite, Un codage RLE est appliqué, (Run Length Encoding)
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 intéressant pour des données textuelles ou de type images photographiques. Le gros inconvénient pour cet algorithme est que s'il y a beaucoup de changement dans une image, le fichier compressé se montrera plus gros que le fichier d'origine. Pour pallier à ce problème, l'algorithme RLC a été inventé.

R.L.C. ou Run Length Coding Le R.L.C. est considérée comme l'un des plus simples algorithmes de compression. Son principe consiste à compter le nombre de caractères identiques successifs et à transformer cette succession en indiquant le nombre de répétitions de l'information à répéter ainsi qu'un caractère spécial informant de la présence d'une répétition.
Cette méthode n'a d'intérèt que pour les fichiers contenant souvent des répétitions de plus de trois caractères. Sinon elle peut augmenter la taille du fichier source si il n'y a pas de répétitions de plus de 3 caractères.

Ensuite le codage de Huffman est appliqué. Le principe de ce codage est le suivant : si on considère un fichier, celui-ci est constitué de données qui sont toutes codées avec la même quantité d'information (sur 8 bits ou 16 bits par exemple. Or, si certaines données reviennent beaucoup plus souvent que d'autres, il est plus avantageux de les coder sur un petit nombre de bit, quitte à utiliser plus de bits après pour les données qui reviennent rarement. Huffman a trouvé un algorithme qui permet d'attribuer à chaque valeur possible un code qui répond aux exigences précédentes et qui permet une lecture du fichier codé même lorsque les codes sont mis bout à bout (unicité de l'interprétation du fichier codé).

Voici une représentation de la technique de Huffman ou 'arbre est construit en mariant les deux pourcentages les plus faibles.

Probabilité valeur (en binaire) code par Huffman
12% 00 111
31% 01 110
45% 11 00
22% 10 10



Il existe d'autres algorithmes de codage réversible : Shannon Fano, LZW, codage arithmétique.


E)Avantages et inconvénients

'avantage essentiel de la DCT est le taux de compression important pour une qualité donnée. La valeur de ce taux est difficile à évaluer compte tenu du fait qu'il dépend de la nature des signaux et de leurs qualités initiales (quantification, colorimétrie). Notons quand même qu'il est possible d'obtenir des taux voisins sans que 'on puisse observer des différences à l'oeil nu avec des images de type photographique ou sur des écrans de très bonne qualité.

'inconvénient majeur de la DCT est le découpage des signaux en blocs. Leur silhouette apparaîit à partir d'un certain taux de compression qui dépend de la nature du signal. Cet effet généralement invisible apparait à l'oei nu, dans le cas des images photographiques, dès que le taux de compression atteint quelques dizaines.

Aujourd'hui de nombreux testeurs se penchent sur des techniques visant à accélérer la DCT, par traitement mathématique à virgule fixe ; chaque cycle gagné sur le temps pris pour calculer la DCT vaut son pesant d'or.


F) Ouverture sur la décompression

 Le processus JPEG de compression conduit au stockage ou au transport des informations sur 'image sous un volume mémoire réduit. La restitution de 'image nécessite ensuite que 'on fasse le chemin inverse dans un processus de décompression, grâce à un logiciel de décompression.

Les étapes de la décompression sont les suivantes :

l' ouverture du fichier de données.
-Rétablissement de la matrice DCT quantifiée, en suivant le chemin inverse de la méthode de Huffman.
-Rétablissement de la matrice DCT déquantifiée, en multipliant les éléments de la précédente par le coefficient correspondant de la matrice de quantification.
-Rétablissement de la matrice des pixels de l'image à l' aide d'une transformation DCT inverse

On peut observer que la décompression est plus rapide que la compression car il n'y a plus lieu d'arrondir ou de négliger certaines valeurs. Les différences entre la matrice de sortie de 'image d'origine et la matrice d'entrée doivent bien entendu rester acceptables pour l'oeil.

Exemple de décompression :



exemple avec une image a plusieurs taux de compressions :

Détail de l'image, non compressée (bitmap) [12342 Bytes].

1 - [5362 Bytes]

20 - [2015 Bytes]

40 - [1542 Bytes]

80 - [1065 Bytes]

90 - [895 Bytes]

Evolution (99 >>> 50)