Les images JPEG

Pour mon travail de diplôme à la Haute Ecole d’Ingénerie et de Gestion du Canton de Vaud, j’ai développé un logiciel de stéganalyse. Le but du logiciel était de détecter la présence de messages stéganographiés dans des images numériques principalement. À cette occasion, j’ai étudié plusieurs formats de fichiers dont la norme JPEG. Cet article, relativement long, explique le fonctionnement du format d’image le plus populaire.

Norme JPEG

JPEG est l’acronyme de Joint Photographic Experts Group. Il a été créé en 1986 par un comité résultant de la fusion de plusieurs groupes professionnels; d’où le mot Joint dans l’acronyme. Le but visé par ce panel d’experts était de définir une norme ouverte de compression pour les images numériques.

Par abus de langage, le terme JPEG est souvent assimilé à un format de fichier. La raison est évidement à chercher dans le choix de l’extension des fichiers qui est généralement .jpg ou .jpeg. Pourtant, JPEG ne définit qu’une norme. La distinction est importante: d’un coté, la norme JPEG définit des méthodes de compression (avec ou sans pertes) ainsi qu’une structuration des informations à l’intérieur d’un flux de données. En complément, un format spécifie les méthodes et algorithmes utilisés pour transformer une information visuelle en une suite de bits et inversement. Typiquement, un format pour une image en nuance de gris spécifiera qu’une valeur de 0 identifie un pixel noir, une valeur de 255 un pixel blanc, alors que les valeurs intermédiaires identifient les 254 nuances entre ces deux extrêmes.

Il existe actuellement une dizaine de formats s’appuyant sur la norme JPEG. Un liste exhaustive peut être trouvée sur ici. Parmi ceux-ci, le plus important est le format JFIF: l’immense majorité des fichiers images communément appelée JPEG le sont dans ce format et c’est également le seul à être compris par tous les logiciels graphiques du marché.

Compression JPEG

La norme JPEG définit deux types de compressions: avec et sans perte. La première met en oeuvre un algorithme de prédiction des pixels par rapport à ses voisins directs afin d’encoder uniquement la différence (il s’agit en général d’une valeur bien inférieure à la valeur absolue du pixel). La seconde méthode se base sur les transformations en cosinus discrètes, appelée DCT (pour Discrete Cosine Transform). Dans la pratique, seule cette dernière est réellement employée, car elle permet d’atteindre des taux de compression vraiment intéressants. Cet article ne traitera donc pas de la compression JPEG sans perte.

La figure suivante illustre le principe général appliqué lors de la compression basée sur la DCT. Celle-ci comprend trois étapes distinctes, la FDCT, la quantification et le codage entropique.

Pour la décompression, il suffit d’inverser les étapes comme illustré à la figure suivante. À noter toutefois que les tables utilisées lors des phases de quantification et d’encodage sont transmises en parallèle de l’image compressée.

DCT

La DCT dérive directement de la transformée de Fourier discrète. Elle transforme un signal discret bidimensionnel d’amplitudes en une information bidimensionnel de fréquences et inversement. L’idée sous-jacente est que l’oeil humain est nettement moins sensible aux hautes fréquences et qu’il est alors possible de supprimer purement et simplement certaines informations non visible.

Pour réaliser la DCT, il est au préalable nécessaire de découper l’image en blocs de 8×8. Deux raisons à cela: la première, est que la transformation ne peut s’effectuer que dans un matrice carrée. La seconde est que plus la matrice est grande, plus les calculs sont complexes. En contrepartie, plus la matrice est petite, plus le taux de compression pouvant être appliqué sur l’image est faible. Une taille de 8×8 est ainsi un bon compromis.

Les deux formules - FDCT (F pour forward) et IDCT (I pour inverse) - sont les suivantes:

Quantification

Jusqu’à présent - à part les erreurs d’arrondis - l’image originale n’a subi aucune perte d’information. Par contre, la quantification est une étape dite non conservatrice. Son but est de filtrer les informations issues de la transformée en cosinus pour ne garder que les données de basse fréquence. En effet, non seulement l’information effective de la plupart des images naturelles est concentrée sur les basses fréquences, mais de plus, l’oeil humain est beaucoup moins sensible aux fréquences élevées (changement de couleurs brusques) qu’aux fréquences basses (changements lents). La quantification consiste donc à diviser chaque élément de la DCT par un élément correspondant dans la table de quantification et en arrondissant à l’entier le plus proche. Si les diviseurs sont suffisamment grands, de nombreux éléments deviendront nuls ou très faibles et il sera aisé de les compresser à l’aide d’un algorithme entropique par exemple.

Le choix des valeurs de la table de quantification dépend du taux de compression désiré. Ainsi, la plupart des logiciels offre à l’utilisateur la possibilité de choisir un indice de qualité. Cette valeur influence directement la table de quantification.

Au niveau du décompresseur, l’étape inverse s’appelle la déquantification. Elle consiste à multiplier chaque élément de la DCT par l’élément correspondant de la même table de quantification. La figure suivante illustre les différentes transformations effectuées en partant d’un bloc de 8×8 issu de l’image originale jusqu’à la restauration de celui-ci.

Codage entropique

Un codage entropique exploite les propriétés statistiques des coefficients quantifiés pour diminuer le débit de transmission en utilisant des mots courts pour représenter les évènements les plus probables et des mots plus longs pour les occurrences rares.

JPEG propose deux techniques pour le codage entropique: le code de Huffman - qui fut mis au point en 1952 par David Huffman — et le codage arithmétique. Ce dernier, légèrement plus performant que le premier, semble être protégé par des brevets déposés par IBM, AT&T et Mitsubishi; raison pour laquelle il est généralement absent des codeur et décodeur JPEG.

L’idée qui préside au codage de Huffman est voisine de celle utilisée dans le code Morse : coder ce qui est fréquent sur peu de place, et coder en revanche sur des séquences plus longues ce qui revient rarement. En morse le e, lettre très fréquente, était codé par un simple point, le plus bref de tous les signes.

Le principe du codage de Huffman repose sur la création d’un arbre composé de noeuds. Supposons que la phrase à coder est “abracadabra”. La première étape consiste à déterminer le nombre d’occurrences de chaque caractère; soit 5 pour le a, 2 pour le b et le r, et 1 pour les autres lettres. Chaque caractère constitue une feuille de l’arbre, à laquelle on associe un poids valant son nombre d’occurrences. Puis l’arbre est créé suivant un principe simple: on associe à chaque fois les deux noeuds de plus faibles poids pour donner un noeud dont le poids équivaut à la somme des poids de ses fils jusqu’à n’en avoir plus qu’un, la racine. On associe ensuite à chaque branche la plus faible d’un noeud le code 0 et la plus forte le code 1, comme l’illustre la figure suivante.

Pour obtenir le code binaire de chaque lettre, il suffit de descendre l’arbre en partant de la racine en ajoutant chaque fois le code 0 ou 0 selon la branche suivie. Ici, le code pour “abracadabra” devient 0 10 110 0 1110 0 1111 0 10 110 0 (les espaces ont été ajoutés pour des questions de lisibilité), soit 23 bits.

Il existe trois variantes de l’algorithme de Huffman, chacune définissant une méthode pour la création de l’arbre:

1. statique : chaque octet a un code prédéfini par le logiciel. L’arbre n’a pas besoin d’être transmis, mais la compression ne peut s’effectuer que sur un seul type de fichier (ex: un texte en français, où les fréquences d’apparition du ‘e’ sont énormes; celui-ci aura donc un code très court);
2. semi-adaptatif : le fichier est d’abord lu, de manière à calculer les occurences de chaque octet, puis l’arbre est construit à partir des poids de chaque octet. Cet arbre restera le même jusqu’à la fin de la compression. Il sera nécessaire pour la décompression de transmettre l’arbre;
3. adaptatif : c’est la méthode qui offre a priori les meilleurs taux de compression car l’arbre est construit de manière dynamique au fur et à mesure de la compression du flux. Cette méthode représente cependant le gros désavantage de devoir reconstruire l’arbre à chaque fois, ce qui implique un temps d’exécution énorme.

La norme JPEG a choisi de n’utiliser que la deuxième variante. Cela implique que la table de codage doit être transmise en même temps que l’image afin que le décodeur puisse lire les données contenue dans l’arbre de Huffman.

Un dernier point important concerne la manière de linéariser la matrice en deux dimensions des coefficients DCT quantifiés en un vecteur en une dimension. En effet, la convention stipule que la lecture des coefficient s’effectue en zigzag comme illustré à la figure suivante. Cette séquence, décrite pour la première fois par Tescher en 1978, permet d’ordonner les coefficients en fonction de leur probabilité de contenir une valeur différente de zéro. La séquence en zigzag est d’une importance primordiale pour le codage entropique: elle améliore considérablement la construction du modèle statistique utilisé pour la construction de l’arbre de Huffman et donc permet de résuire significativement la taille des données compressées.

Modes opératoires

Outre les méthodes de compression, La norme JPEG définit également des modes de transmission et donc d’affichage des images. Pour la compression avec perte, ces modes sont au nombre de trois:

1. séquentiel: les blocs de 8×8 sont transmis à la suite en partant du haut de l’image et par balayage de gauche à droite;
2. progressif; les blocs sont transmis dans le même ordre, mais en passes multiples. À chaque passe, un partie seulement d’un bloc de 8×8 est transmis et l’image est ainsi restituée progressivement;
3. hiérarchique: plusieurs images à des résolutions de plus en plus élevées sont transmises à la suite les unes des autres.

Format JFIF

Le JPEG File Interchange Format, abrégé JFIF, est le format de fichier le plus utilisé pour les images enregistrées avec la compression JPEG. En fait, l’extension de fichier jpeg ou .jpg indique, en général, un fichier au format JFIF.

Le format JFIF utilise un modèle luminance-chrominance pour la représentation des pixels. Ce modèle sépare la luminosité (luminance) d’un pixel de sa coloration (chrominance) en affectant une valeur comprise en 0 et 255 à la première et deux, dans le même intervalle, à la seconde. Il existe plusieurs variantes du modèle luminance-chrominance: YIQ, YUV et YCbCr. C’est cette dernière qui est utilisée par JFIF. Le Y représente la luminance, le Cb, la luminance moins le bleu et le Cr, la luminance moins le rouge. À l’aide de ces trois valeurs, il est possible de recréer mathématiquement la vert. Les formules suivantes permettent d’effectuer la conversion entre une représentation RGB et YCrCb et inversement:

L’avantage du modèle luminance-chrominance, est qu’il est possible de sous-échantilloner la composante chrominance dans une image. En effet, l’oeil est nettement moins sensible aux modifications de teintes qu’à l’intensité.

Le format JFIF tire parti de cette propriété. Ainsi, l’image est découpée en 2 ou 4 blocs de 8×8 en fonction du sous-échantillonage souhaité. L’opération consiste ensuite à créer 2 ou 4 blocs contenant les informations sur la luminance et 2 blocs pour la chrominance, le premier pour la composante Cb et le second pour la composante Cr. Ces 4 ou 6 blocs, appelés unités d’image sont ensuite compressés par une des méthodes définies dans la norme JPEG.

Enfin, un autre avantage du modèle luminance-chrominance est qu’il est compatible avec les images et les récepteurs noir/blanc. Il suffit pour cela de ne pas tenir compte de la chrominance et de ne garder que la luminance. D’ailleurs la télévision marche sur ce principe. Un vieux récepteur noir/blanc est tout à fait capable de recevoir une émission couleur. Normal, il ne sait décoder que la luminance!

Cet article a été posté le Mercredi 08 février 2006 à 17:52 sous la catégorie Technologies. Vous pouvez suivre le fil de cette discussion en vous abonnant au flux RSS 2.0 . Les commentaires et "Ping" sont actuellement fermées.