Compression JPEG
| Série JPEG | |||||
| Groupe JPEG | JFIF | JPEG-LS | Compression JPEG | JPEG 2000 | Compression par ondelettes |
| Sommaire |
Introduction au JPEG
JPEG est le sigle de Joint Photografic Expert Group, qui a édifié une norme de compression applicable dans le domaine des images fixes. Cette norme est le résultat de l'évolution des travaux qui ont débuté dans les années 78-80 avec les premiers essais de laboratoire en compression d'images.
Le groupe JPEG qui a réuni une trentaine d'experts internationaux, a spécifié la norme en 1991. Mais la norme officielle et définitive n'a été adoptée qu'en 1992. Pratiquement, seule la partie concernant le codage arithmétique est brevetée, et par conséquent protégée par IBM, son concepteur.
La norme décrit principalement le format des données compressées et le schéma de codage et de décodage. Les algorithmes de compression et de décompression y sont proposés, mais ne sont pas normalisés. Ce qui fait que tout programmeur est libre d'éprouver ses propres algorithmes ou variantes, pourvus que les formats de sortie soient respectés.
JPEG définit deux classes de processus de compression : avec perte d'informations et gain substantiel, ou sans perte avec des taux de compression assez moyens. De plus, les taux de compression sont fonction de la qualité souhaitée après décompression et de la vitesse demandée aux processus de codage et de décodage.
La Compression JPEG
Nous allons maintenant nous intéresser à l'algorithme.
On peut diviser la compression et la décompression JPEG en 6 étapes donc voici l'organigramme :
CompressionJPEGorgjpeg.gif
Figure 1 Organigramme de compression
Découpage en bloc
Le Format JPEG, comme le font généralement les algorithmes de compression à perte, commence par découper l'image en blocs ou carreaux généralement carrés de 64 (8x8) ou 256 (16x16) pixels.
Transformation des couleurs
JPEG est capable de coder les couleurs sous n'importe quel format, toutefois des meilleur taux de compression avec un codage des couleurs de type luminance/chrominance tel que YUV, YcbCR car l'œil est assez sensible à la luminance mais peu à la chrominance.
Sous échantillonnage
La façon la plus simple d’exploiter la faible sensibilité de l'œil à la chrominance est simplement de sous-échantillonner les signaux de chrominance. Généralement on utilise un sous échantillonnage de type 2h1v ou 2h2v. Dans le premier cas (le plus utilisé) on a un sous échantillonnage 1:1 horizontalement et 2:1 verticalement, dans le deuxième cas on a un sous échantillonnage 2:1 horizontalement et verticalement. Ces sous échantillonnages sont utilisés pour les chrominances, pour la luminance on n'utilise jamais de sous échantillonnage.
Transformée DCT
La transformée DCT (Discrete Cosine Transform, en français : Transformée en Cosinus Discrète), est une transformation numérique qui est appliquée a chaque bloc et pour chaque « couleur ». Cette transformée est une variante de la transformée de Fourrier. Cette méthode permet de décrire chaque bloc en une carte de fréquences et en amplitudes plutôt qu'en pixels et couleurs. La valeur d'une fréquence reflète l'importance et la rapidité d’un changement, tandis que la valeur d’une amplitude correspond à l'écart associé à chaque changement de couleur.
A chaque bloc de 
pixels sont ainsi associées fréquences
La transformée DCT s'exprime mathématiquement par :
![DCT(i, j)=\frac{1}{\sqrt{2N}}C(i)C(j)\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}pixel(x, y) \cos\left[\frac{(2x+1)i\pi}{2N} \right] \cos\left[\frac{(2y+1)j\pi}{2N} \right]](/img/math/f133e456306b285379e0e76165a87c17.png)
|
|---|
| Equation 1 Transformée DCT direct |
Et la transformée DCT inverse s'exprime par :
![pixel(x, y)=\frac{1}{\sqrt{2N}}\sum_{i=0}^{N-1}\sum_{j=0}^{N-1}C(i)C(j)DCT(i, j) \cos\left[\frac{(2x+1)i\pi}{2N} \right] \cos\left[\frac{(2y+1)j\pi}{2N} \right]](/img/math/65f049c51f25a64b7887ad417c7945c5.png)
|
|---|
| Equation 2 Transformée DCT inverse |
Dans les deux cas comme constante 
vaut :
|
|---|
| Equation 3 définition de la constante |
Pour illustrer la compression, a été repris, un exemple complet provenant de « Digital Images Compression Techniques » de Majid Rabbani et Paul W. Jones.
Matrice (bloc de pixel) de base :
|
|---|
| Equation 4 Matrice d'origine |
En effectuant la transformée DCT on obtient comme matrice des fréquences suivante :
|
|---|
| Equation 5 Matrice transformée DCT |
Remarques
Le calcul d'une DCT est complexe. C'est l'étape qui coûte le plus de temps et de ressources dans la compression et la décompression JPEG, mais c’est peut-être la plus importante car elle nous a permis de séparer les basses fréquences et les hautes fréquences présentes dans l'image.
La puissance de calcul disponible aujourd'hui, alliée à des algorithmes de type FFT très efficace, permet de rendre le temps de calcul tout à fait acceptable pour l'utilisateur courant, voire imperceptible pour les machines les plus puissantes.
Quantification
La quantification consiste à réduire le nombre de valeurs correspondant aux amplitudes. Les hautes fréquences qui ont généralement de faibles amplitudes et auxquelles de plus l'œil n’est que peu sensible. Elles sont généralement éliminées. Pour cela nous avons besoin d’une matrice qui définit le niveau de quantification pour chaque fréquence spatiale que l'on ne désire que peu de détails par rapport à celle que l'on désire beaucoup de détails. C'est dans cette partie que s'effectue le principale des pertes.
Voici le calcul permettant la quantification :
 entier le plus proche 
|
|---|
Avec :  entier directement inférieur à 
|
| Equation 6 Calcul de la quantification |
Et pour la quantification inverse :
|
|---|
| Equation 7 Calcul de la quantification inverse |
Dans notre exemple nous avons pris la matrice, définissant le niveau de quantification, suivante :
|
|---|
| Equation 8 Matrice définissant le niveau de quantification |
Ce qui donne comme matrice des fréquences quantifiée :
|
|---|
| Equation 9 Matrice quantifiée |
Remarques
La division en blocs devient visible lors de taux de compression extrêmes (voir les exemples associés) car un bloc entier se trouve codé avec la même valeur. Ce phénomène s'appelle la « pixellisation ». Chaque coefficient issu de la DCT est quantifié en utilisant les valeurs d’une table de quantification Q, chaque composante possédant sa propre table.
Codage, compression RLE et Huffman
Le codage s’effectue en zigzag comme le montre la figure suivante et ce terminant par un caractère de fin :
CompressionJPEGImage13.gif
Figure 2 Ordre de codage défini par la norme JPEG
Codage de notre exemple : 
.
Ce résultat est ensuite compressé selon un algorithme RLE puis un algorithme Huffman ou arithmétique. Algorithmes défini dans la première partie du didacticiel.
Avec le schème de codage très simplifié suivant on remarque que le codage nous délivre deux (4 pour une image couleur) tables. Ces tables étant enregistrées dans le fichier final peuvent être choisie par le compresseur.
CompressionJPEGImage14.gif
Figure 3 schéma de codage simplifié
Décompression JPEG
Les étapes de la décompression s'effectue dans l'ordre inverse de la compression suivant les méthodes définies précédemment (en même temps que la compression).
Voici dans notre exemple le résultat de la décompression :
|
|---|
| Equation 10 Résultat de la décompression |
Ainsi que la matrice d’erreur :
|
|---|
| Equation 11 Matrice des erreurs réalisées par les pertes. |
Remarques
Les erreurs sont au maximum de 5 et en moyenne 1.6 sur environ 150 ce qui nous donne une erreur moyenne d'environ 1%, et tout cela pour un passage de 64 à 10 valeurs (avec le caractère de fin), à cela il faut rajouter la matrice de quantification, mais comme généralement on compresse de gros fichier elle n’influence que peut.
JPEG, codage sans pertes
Ici, la précision p des échantillons varie de 2 à 16 bits. À la place de la DCT, le codage utilise un prédicateur P à trois échantillons.
CompressionJPEGImage17.gif
Figure 4 schéma de compression JPEG sans pertes