TPE 2003-2004

LA COMPRESSION D'IMAGES NUMERIQUES PAR LE JPEG

Classe :

Terminal 5 du Lycée Brizeux 29000 Quimper

Élèves :

Fabien Menou

Loïc Gueguen

Benjamin Trempont

Thème :

Images

Problématique :

«Comment deux images qui semblent identiques peuvent-elles prendre un espace mémoire différent?»

Professeurs :

mathématiques : Mr Bozec

physique/chimie : Mme Richard

Téléchargement du format PDF et du programme :

.PDF
Programmes

Contact :

webmaster@startjeux.com

Sommaire :

Introduction :

I/Le Système de couleurs YUV

1)Pourquoi changer le système de couleur ?

2)Détermination mathématique des coefficients de "passage"

3)Quels sont les effets visibles et les limites de cette compression?

Conclusion

II/La transformée en cosinus discrète (DCT) et la quantification

1)Le principe théorique de la DCT

2)L'application de la DCT dans la norme JPEG

3)La quantification

III/Compression non destructrice

1)La Compression RLE ou RLC

2)La Compression Huffman

Conclusion

Glossaire

Bibliographie

Introduction :

La compression est une méthode très fréquemment utilisée qui touche le domaine de l'informatique, mais pour comprendre ce concept il faut avant tout faire une petite introduction sur la mémoire de l'ordinateur, en effet quand on parle de compression des données c'est cette espace mémoire qui sera réduit via la compression. La mémoire d'un ordinateur est constituée d'une suite de bits qui se suivent les uns à la suite des autres, un bit est le plus petit élément de la mémoire d'un ordinateur qui peut prendre deux valeurs possible, soit 1 ou soit 0, ce qui correspond à un état stable ou instable.

Exemple d'une suite de bits :

010011011011110011111110

Mais dans l'ordinateur, les bits sont regroupés par groupe de huit bits, que l'on appelle octet, ainsi les données de la mémoire sont mieux hiérarchisées. De plus, l'ordinateur associe à chaque octet de la mémoire un numéro d'octet, c'est-à-dire que l'on peut demander à l'ordinateur la valeur d'un octet en donnant le numéro physique associé dans la mémoire à un octet, ces numéros varient bien évidement de 0 à la taille de l'espace mémoire de l'ordinateur et croît de un en un à chaque octet qui se suivent dans la mémoire. Si on reprend l'exemple d'au-dessus, on aura par exemple :

bits dans la mémoire : 01001101 10111100 11111110

numéro associée à chaque octet : 56002 56003 56004

Mais que représente ces 1 et ces 0 dans la mémoire? Et bien ils représentent des nombres comme nous avons l'habitude de travailler dessus mais au lieu d'être en base 10, ils sont en base 2 d'où l'appellation binaire car l'ordinateur ne peut «comprendre» que cette base. Voici un exemple de nombre en base 10, décomposé :

108 = 10² x 1 + 10¹ x 0 + 10⁰ x 8

Pour passer d'une base 10 en base 2, on effectue des divisions euclidiennes successives par 2 sur le nombre en premier puis sur les quotients de la division précédente. Les restes que l'on obtient au fur et à mesure sont les chiffres du nombre en base 2. Voici un exemple avec 108 :

En mettant bout à bout, le quotient de la dernière division puis les restes des divisions jusqu'au premier reste de la première division, on obtient 108 en binaire qui vaut 1101100. Pour revenir en base 10 à partir de ce nombre binaire, il suffit de traiter chaque chiffre binaire en le multipliant par 2 avec l'exposant du rang où ce chiffre appartient en commençant par 0 et enfin on fait la somme de l'ensemble des résultats obtenus. Voici un exemple illustrant le changement du nombre 1101100 en base 2, en base décimale :

108 en base 2 : 0 1 1 0 1 1 0 0

Valeur en base 10 de 108 : 108 = 2⁷x0 + 2⁶x1 + 2⁵x1 + 2⁴x1 + 2³x1 + 2²x1 + 2¹x1 + 2⁰x1

On pourra bien entendu étendre la valeur d'une variable à plusieurs octets si on a besoin de travailler avec des plus grands nombres mais ici on se limitera souvent à 1 octet pour une valeur. Qui pourra ainsi avoir une valeur variant de 0 à 255 ou alors de -127 à 128 (par norme) si le bit du rang 7 représente le signe du nombre.

Maintenant que nous savons comment sont représentées les données dans l'ordinateur il faut savoir comment une image est représentée. Pour mieux cerner le problème nous allons prendre l'exemple de la numérisation d'une photo via un appareil photo numérique. Il est en fait constitué de lignes et de colonnes de capteurs de lumière (capteurs photosensibles). Plus il y a de capteurs, plus l'image sera de qualité. Chaque capteur décompose la lumière qu'il reçoit en un signal électrique qui sera lui-même ensuite transformé en données numérique. Pour chaque capteur il y aura trois octets de données pour décomposer l'image en trois composantes qui sont le rouge, le vert et le bleue : ce sont les couleurs primaires d'un faisceau lumineux. On appelle ce morceau de l'image, un pixel : c'est le plus petit élément composant une image. Un capteur sur ce type d'appareil photographique est à l'échelle microscopique, ils sont donc très nombreux.

En fin de compte, pour chaque composante lumineuse on aura un tableau de valeurs qui aura n*m valeurs. La variable m représente le nombre de lignes de capteurs et n le nombre de colonnes de capteurs. En général, un appareil photo numérique possède 800*600 pixels, cette résolution peut être moins grande ou beaucoup plus grande également. Donc pour une composante on aura 800*600 octets c'est-à-dire 480 000 octets. Mais comme, on a trois composantes pour cette images, la taille de cette image sera donc de 800*600*3 = 1440000 octets ≈ 1,37 Mo. Or, la mémoire des appareils photos numériques est limitée et vaut 10 Mo environ mais cette valeur peut être beaucoup moins élevée ou au contraire beaucoup plus grande, ainsi l'appareil photo numérique ne pourrait pas prendre plus de 7 photos! Imaginez si nous avions à enregistrer une vidéo numérique à 24 images par secondes, un film de 1h30, prendrait 173,81 Go soit environ 249 CD-Rom et encore sans le son! On se rend vite compte que c'est strictement impossible et des techniques de compression d'image ont été mises en place pour contrer ce problème.

A travers cet exposé, nous allons analyser, une norme de compression qui est le JPEG (pour Joint Photographic Experts Group). Pourquoi cette norme en particulier? C'est actuellement la norme la plus utilisée pour la compression d'images numériques que ce soit pour internet, ou pour les appareils photos numériques par exemple. De plus, il permet à l'utilisateur de choisir un facteur de qualité, c'est-à-dire qu'il peut choisir une image qui sera de très bonne qualité mais qui prendra beaucoup d'espace mémoire ou alors une image de moins bonne qualité mais qui prendra également moins de mémoire mais pourtant avec certains facteurs qualités, on a deux images de qualité identique à première vue mais qui prennent des espaces mémoires différents. Ainsi on s'est posé la problématique suivante : «comment deux images qui semblent identiques peuvent-elles prendre un espace mémoire différent? ». Cet exposé va répondre à cette problématique en analysant l'ensemble des traitements que la compression JPEG fait à une image non compressée.

I) Le Système de couleurs YUV

Tout d'abord, il faut définir le terme qui semble ambigu. Une image numérique est découpée en pixels, carrés de couleurs (ou de teintes de gris allant du blanc au noir) comme nous l'avons précédemment vu dans l'introduction. Au départ, lorsque l'on ne compresse pas l'image, chaque pixel est caractérisé par 3 composantes de base (format BMP ou BITMAP), la composante R, qui défini les domaines de nuances rouges, le V qui défini les domaines de nuance vertes et en dernier lieu le B, qui s'occupe de la couleur bleue. Ce qui nous donne au final un pixel codé en RVB (ou aussi appelé RGB). Le principe de la compression YUV est tout simplement d'optimiser ce codage couleur. En effet, au lieu de décomposer le pixel en 3 couleurs, on le décompose en 3 "caractéristiques" qui sont la luminance ou luminescence (Y ou Brigthness en anglais), la chrominance bleue (Cb ou U, tons de bleu), ainsi pour finir que la chrominance rouge (Cr ou V, tons de rouge). Tout cela dans le but de compresser l'image grâce aux caractéristiques de l'oeil qui est, pour nous humain, plus sensible au variations d'intensité lumineuse qu'au variations dans l'échelle des teintes (chrominance), mais nous allons développer tout cela plus en détails dans la suite de la partie.

1) Pourquoi changer le système de couleur ?

Comme toute étape d'un format de compression, ce passage en YUV (ou YCbCr) a pour but une exploitation optimisée du format d'image et donc aussi une compression par étapes. Ici ce changement possède les deux avantages, il compresse et rend l'image exploitable pour la DCT (Discrete Cosine Transform), deuxième étape de compression qui sera développée ultérieurement dans notre TPE. Pour mieux expliquer comment fonctionne ce passage et quels en sont les gains, nous allons prendre un exemple d'image formée par un bloc de 64 pixels (8x8 pixels) au format bitmap donc codée en RGB.

Nous allons tout d'abord devoir appliquer une donnée de luminance a chaque pixel, étant donné que cette dernière est très importante dans une image, le passage en YUV va donc la garder pour chaque pixel. Ensuite, au lieu de définir une donnée pour chaque couleur (R V et B), nous allons prendre des blocs de 2x2 pixels et leur appliquer une composante Cb et une composante Cr, il ne nous reste plus que, dans ce même bloc de 4 pixels, 4 informations de luminance et 2 pour la chrominance (une Cb et une Cr), ce qui nous fait au total 6 octets pour le codage couleur sur un bloc de 4 pixels au lieu de 12 octets (4 pixels multiplié par 3 composantes). Nous avions pris une image de 64 pixels, qui pour des couleurs codées en RGB , pèse 3x64= 192 octets alors que notre image au format YUV ne pèse que (4+2)x16= 96 octets. Nous gagnons donc la moitié d'espace mémoire. Bien sur ces espaces mémoires ne sont que la partie couleur de l'image, ces 2 images auront des "poids" différents sur l'ordinateur, car après cette compression interviennent d'autres compressions.

Voici un schéma qui illustre ce que nous avons décrit ci-dessus:

( Cb = V et Cr = U)

2) Détermination mathématique des coefficients de "passage"

Bien entendu, nous sommes parvenus a fixer les composantes Y, U et V grave a différentes méthodes physiques et mathématiques. La luminance Y étant la donnée fondamentale de l'image, nous la déterminons en premier lieu en faisant une moyenne pondérée des composantes RGB, ensuite nous procédons a l’établissement des formules de passage des autres composantes, a savoir la chrominance rouge et la chrominance bleue.

Ce qui nous donnera :

Y = 0.3R + 0.59V + 0.11B.

U = - 0.1687R – 0.3313V + 0.5B + 128

V = 0.5R – 0.41874G – 0.0813B + 128

A partir de ces équations, nous pouvons également revenir de ces composantes YUV aux composantes RVB :

R = Y + 1.402 (Cr – 128)

G = Y - 0.34414 (Cb – 128) - 0.71414 (Cr – 128)

B = Y + 1.772 (Cb – 128)

La luminance est une quantité physique objective, c’est l’intensité des radiations lumineuses par unité de surface considérées (en lumen, ou lux par mètre carré).

Cette dernière va de 0 (luminance du noir) à 255 (luminance du blanc), car on admet qu’il y a 256 échelles de gris allant du noir au blanc. On mesure la luminance par des récepteurs photoélectriques : on fait les mesures pour chaque composante RVB, on divise ensuite par la somme des trois résultats. Ainsi on obtient les coefficients donnés sur la page précédente. Puis grâce a cela, on détermine les coefficients Cb (V) et Cr (U). Mais avant cela nous devons représenter nos 3 composantes dans un repère orthonormé (unités équivalentes sur les 3 axes, ainsi que des axes perpendiculaires entre eux). Voici le repère en détails que nous expliquerons plus bas.

U et V doivent être respectivement dans le plan (R,Y) et (B,Y), car elles dépendent évidemment de ces deux données qui sont leurs chrominances respectives et la luminance. Pour que ces composantes soient bien distinctes, on doit toutes les mettre dans un plan orthogonal aux deux autres, ainsi, pour se faire, on doit poser U et V de telle forme que : U = a x (R-Y) et V = b x (B-Y). On obtient donc bien une « base orthogonale » comme RVB. Dans ces 2 formules, on choisit a et b arbitrairement et on ajoute 128 pour que U et V restent bien comprises entre 0 et 255. Dans les formules, on a posé a = 0.713 et b = 0.565, ce qui permet bien, après vérification, aux 2 composantes de rester dans des valeurs comprises entre 0 et 255. En effet pour Cb et Cr, si on regarde bien pour Cb par exemple (ceci est aussi et bien sur valable pour Cr), 0.1687 + 0.3313 = 0.5, or dans la formule nous avons +0.5B, si R, V et B sont comprises entre 0 et 255 et que nous n’ajoutons pas 128, nous aurons des valeurs comprises entre -128 et +128, or des valeurs négatives n’existent pas ici en terme de « données ».

3) Quels sont les effets visibles et les limites de cette compression ?

Théoriquement et mathématiquement, cette transformation est bijective, c'est-à-dire qu’on peut l’effectuer dans un sens, comme dans l’autre en re-écrivant l’équation de façon à isoler les inconnues qui nous intéressent. Mais en pratique, une fois la compression faite, on ne peut pas revenir en arrière, car cette compression effectue une moyenne de chrominance par 4 pixels et pour 4 pixels. On ne peut donc plus retrouver les valeurs initiales de chaque pixel puisque les 3 autres pixels le bordant ont la même donnée de chrominance. Visuellement, on ne décèle la compression qu’en regardant les endroits bien précis de l’image ou en prenant une image très petite (en général, des phots numériques sont très « grandes », ou hautement définies, c'est-à-dire comportant un nombre énorme de pixels, il est donc impossible pour nos yeux de trouver un défaut sur une photo complexe). Voici quelques exemples ou la compression se « voit » :

On voit très nettement la différence… regardez la couleur de fond de l’image et les coins de plus près. Ce ci montre bien que la compression YUV, et même plus généralement JPEG n’est pas recommandée dans le cas de petites images ou de formes géométriques parfaites possédant des angles tels les carrés ci-dessus.

Conclusion :

La conversion YUV, couramment utilisée dans les algorithmes de compression d’images tel le JPEG dans ce TPE, s’avère très avantageuse des lors qu’elle est utilisée à des fins précises comme la retouche photographique ou le stockage numérique, mais garde des limites et des défauts comme toute compression.

II/La transformée en cosinus discrète (DCT) et la quantification :

1)Le principe théorique de la DCT :

La transformée en cosinus discrète est une transformation mathématique complexe qui a pour but dans la compression JPEG de transformer le domaine de représentation de nos données, c'est-à-dire de passer d'un domaine spatiale à un domaine fréquentiel, ce que fait également sa grande soeur la transformée de Fourier, en effet après les transformations de visualisations nos données restent toujours dans un domaine spatiale à trois dimensions où x et y représentent un point de l'image (ou un point sur l'écran), ou plus précisément un élément de la matrice de pixel, avec une valeur pour chaque élément de cette matrice représentant l'intensité de couleur pour une des composante Y, Cb ou Cr, c'est-à-dire l'axe z dans un repère à trois dimension(l'image en dessous montre un signal en 3 dimensions), mais comme nous l'avons vu notre oeil est moins sensible à certaines données de l'image et le but de la transformée en cosinus discrète est de passer dans un domaine fréquentiel, ce qui nous permettra de trier efficacement l'ensemble des données de l'image et ainsi supprimer certaines données de l'image où l'oeil humain ne verra que très peu de différences : les hautes fréquences de l'image tout en gardant les données majeures de l'image qui sont les représentées par les bases fréquences.

L'image dans un domaine spatial, a ses données non ordonnées et on voit bien qu'en supprimant même très peu de valeurs de l'image et bien cette perte se voit tout de suite, ainsi la DCT permettra de séparer les données majeures des données moins utiles pour mieux les manipuler par la suite. L'image en dessous montre la suppression de certaines données en remplaçant un carré de couleurs proches par une couleur uniforme, cette «perte» se voit immédiatement.

Les hautes fréquences représentent les zones à forts contrastes dans l'image, ce qui signifie lorsqu'il y a un changement brutal de couleurs dans l'image, comme par exemple, une image qui a d'un côté une couleur noire et de l'autre côté une couleur blanche. Voici cette image qui montre un très fort contraste :

En reprenant l'image d'au-dessus et en changeant le contraste de l'image en l'abaissant comme le fait n'importe quel logiciel de traitement d'image, on obtient une nouvelle image et on voit bien que les bases fréquences représentent les zones qui n'ont pas de changement brutaux de couleurs dans l'image, représentant ainsi une plage de couleurs uniformes:

Affichons un exemple d'image qui nous démontre l'importance du contraste sur les images compressées via la norme JPEG, voici une image à fort contraste non compressée :

Les discontinuités entre le disque bleu et son fond blanc, peuvent être considérées comme des zones à forts contrastes et en compressant cette image via la norme JPEG, on obtient très rapidement, même avec des facteurs de qualités petits, des dégradés qui se forment entre la couleur du disque et le fond blanc. Ce qui signifie qu'en supprimant les hautes fréquences de l'image on supprime les parties de l'image qui ont de forts contrastes, donc cette image a tendance à linéariser ses couleurs pour avoir des dégradés de couleurs comme on le voit sur l'image en-dessous, mais cette linéarisation n'est pas forcement un beau dégradé comme on aimerait avoir, cela donne souvent un rendu pas très agréable pour l'oeil et donc un résultat non cohérent par rapport à ce que représente l'image :

Cette transformation est une transformation avec le qualificatif «discrète», car on a affaire à un signal non continue, en effet, comme on l'a vu avec l'appareil photo numérique, et bien celui-ci va prendre grâce à ses capteurs une valeur pour chacun des récepteurs photosensibles, et ainsi avec ce prélèvement de valeurs, on aura affaire à un signal à trois dimensions discret car il y aura comme un «saut» entre une valeur et celles qui sont autour d'elle comme le montre l'image en dessous d'une dimension de 4*4 pixels :

Afin de mieux comprendre le fonctionnement de cette transformation on va d'abord étudier comment une variante de la DCT agit sur un signal à deux dimensions, en effet ce type de signal est plus courant et surtout beaucoup plus intuitif et donc mieux compréhensible. Ce type de signal se retrouve très fréquemment comme par exemple lorsque l'on a un repère orthonormé où l'axe des abscisses est le temps et l'axe des ordonnées représente les amplitudes comme on a souvent affaire en physique. L'enregistrement d'un signal sonore est un exemple de ce type de signal qui utilise également une compression du même genre que celle de la transformée en cosinus discrète dans le célèbre format MP3.

Dans notre exemple ici, on va considérer juste une image qui a pour dimension 8 colonnes sur une seule ligne, de plus on ne considère qu'une seule composante de l'image car la transformée en cosinus discrète s'applique séparément pour chacune des composantes de luminance et des deux chrominance. Pourquoi ne considère-t-on qu'une seule ligne? Tout simplement parce qu'on pourra considérer qu'à chaque unité d'abscisse on a un pixel avec une valeur comprise entre 0 et 255 représentant l'intensité lumineuse en ordonnée. Voici le tableau des huit valeurs que l'on considère :

Juste en dessous, on a la représentation visuelle de ces valeurs en considérant la valeur 255 comme étant le blanc, 0 le noir et toutes les autres valeurs comprises entre 0 et 255, des couleurs intermédiaires :

Enfin, on a un repère orthonormé affichant la représentation de l'ensemble des pixels avec des flèches bleues pour les amplitudes des pixels sur l'axe des ordonnées et en allant d'unité en unité d'abscisse on a les pixels de gauche à droite de l'abscisse 0 à l'abscisse 7. De plus, j'affiche une fonction (une parmi d'autres) qui passe par les points représentant les pixels :

Le but de la DCT ou de l'une des transformation de la même famille est de transformer les données que l'on a dans un domaine fréquentiel, après cette transformation on obtient un spectre de fréquences qui décrit notre signal en une comme de fonctions sinus pour cet exemple. Voici le spectre que l'on obtient après transformation :

A partir, ce ce spectre, il nous est facile de retrouver le signal que l'on avait au départ, il suffit de faire la somme des fonctions sinus en fonction de leur fréquence et de leur amplitude. Pour cette exemple, notre signal de départ a alors pour équation :

f(x) = 200*sin(2*pi*x*0.0625) + 100*sin(2*pi*x*0.125) + 50*sin(2*pi*x*0.3125)

(pour le premier terme, 200 représente l'amplitude, et de 0.0625 la fréquence, même principe pour les termes qui suivent)

En-dessous, nous avons la représentation de cette fonction qui passe bien par les points représentant nos pixels. Ainsi, on se rend compte qu'il est facile de supprimer certaines données de l'image de façon cohérente, en supprimant certaines fréquences du signal.

On va juste conserver dans le signal, les deux fréquences les plus bases qui le décrivent pour montrer un exemple de perte de données. Voici à présent, l'image que l'on obtient, avec l'image originale juste en dessous, certes il y a une différences mais qui n'est pas si énorme et ce principe est celui utilisé par la transformée en cosinus discrète :

2)L'application de la DCT dans la norme JPEG :

Après avoir vu, le principe théorique général de la DCT et donc l'objectif qu'elle devait atteindre avec pour principal exemple un signal en deux dimensions, il est temps d'expliquer son application à un signal en trois dimensions et donc à une image. En effet, ici on ne considère plus un signal en deux dimensions comme on travaille souvent dessus mais sur trois signaux en trois dimensions, un pour chacune des composante donc l'application de la transformée en cosinus discrète s'applique sur chacune des composante séparément. De plus, il faut savoir qu'on ne peut appliquer la DCT que sur une matrice carré donc l'image que l'on a doit être découpée en bloc de N*N pixels, si les dimensions de l'image ne sont pas des multiples de N, alors l'image est agrandie sur la droite et/ou sur le bas de façon a avoir des dimensions qui soient des multiples de N, avec ces nouveaux pixels qui prennent pour valeurs, les mêmes que les pixels les plus à droite ou les plus en bas de l'image. On définit DCT(i, j) comme étant l'élément à la colonne i et à la ligne j de la matrice après la DCT, avec i et j variant de 0 à 7. Img(x,y) représente l'élément de la matrice carré de pixels N*N à la colonne x et à la ligne y avec x et y variant de 0 à 7. L'application de la DCT se fait donc sur chacune des matrices N*N prisent séparément. En gardant les mêmes notations, voici la formule de la DCT, avec Img la matrice de pixel avant transformation et DCT, les données après la DCT :

N représente la taille de la matrice carré, mais elle est en général égale à 8 mais cette valeur pourrait être plus grande mais au détriment des calculs car pour chacun des N*N coefficients on a N*N additions et 2*N*N multiplications environ. Si N vaut 8, on a 64*64=4096 additions à calculer pour une matrice 8*8 et 8192 multiplications environ, ce qui est déjà énorme pour un bloc de seulement 8*8 pixels! La valeur 8 a donc été choisie car c'est un bon compromis entre la qualité de l'application de la DCT et la rapidité des calculs, de plus, au delà d'un bloc de 8*8 pixels, il n'y a en général plus beaucoup de rapport entre les pixels au niveau de leurs variations de couleurs.

On va maintenant expliquer comment marche cette transformée, mais pour mieux la comprendre on va commencer par se limiter à une image d'une ligne de huit pixels, on étendra après le principe sur huit lignes. On garde donc la valeur 8 pour la variable N. On va donc commencer par construire 8 fonctions de base nécessaire pour décrire nos pixels, qui ont des fréquences de plus en plus élevées. Voici les huit fonctions de base qui sont après l'équation de leur courbe avec i variant de 0 à 7 de la fonction :

Le but de la DCT est de calculer un coefficient pour chacune de nos fonctions en fonction des données de nos huit pixels, c'est-à-dire huit coefficients en tout. On numérote les huit pixels en leur donnant un indice de 0 à 7 de gauche à droite dans la représentation spatiale. Donc après cette transformation nous aurons toujours huit valeurs d'où aucun gain d'espaces mémoire. Pour le calcul d'un coefficient d'une fonction, on décrit la fonction considérée seulement avec huit valeurs (les ordonnées des abscisses de 0 à 7 par la fonction f_i) et pour chacune des valeurs que l'on a, on l'a multiplie par la valeur du pixel avec le même indice, puis on fait la somme de ces huit multiplications pour avoir le coefficient d'une des fonction. On réitère cette opération pour nos huit fonctions. Voici un schéma illustrant cette opération pour une des fonctions de base :

Le calcul d'un coefficient d'une des fonction de base, est calculer par rapport à la forme décrite par les valeurs de nos pixels. Plus la valeur absolue du coefficient de la fonction est élevé, plus il y a d'informations sur l'image stockées par le coefficient, à l'inverse plus elle est petite moins il y a d'informations sur l'image décrient par le coefficient de l'une des fonction de base. Par exemple, si on prend la fonction f₃ et 8 pixels représentés par les colonnes bleues sur l'image en-dessous. Plus ces colonnes sont élevées, plus la valeur du pixel est grande. Après avoir multiplié cette valeur par l'ordonnée de la fonction au-dessus, on a le signe de ce produit, et en observant, la hauteur des colonnes bleues, on voit bien que la somme de ces huit multiplications c'est-à-dire la valeur de ce coefficient est élevé et que cette fonction décrit la forme de nos pixels.

En gardant la même fonction de base mais en changeant la valeur de nos pixels tels qu'ils aient la même couleur pour une des composante, alors on s'aperçoit qu'en faisant la somme des huit multiplications on obtient une valeur nul, donc ici le coefficient de cette fonction de base ne décrit pas la forme de nos pixels, ce qui confirme ce qu'on voit en comparant la courbe du dessus et la droite d'équation y=a avec a qui vaut la valeur des pixels car tous les pixels ont la même valeur.

Ainsi, en calculant les huit coefficients de nos fonctions de base, on a la forme de notre image qui est décrite par ces valeurs qui représentent un spectre de fréquences. Ainsi pour retrouver nos données de départ, il suffit de faire comme on a fait pour le spectre que l'on avait dans le chapitre 1, c'est-à-dire que la fonction passant par la représentation de nos pixels, a pour équation la somme des multiplications de la fonction de base f_i(x) (fréquence) par le coefficient de la fonction de base i(amplitude de cette fréquence). On a ainsi la valeur du pixel i qui vaut IDCT(i). La transformée inverse est donc assez simple à retrouver et vaut :

On a ainsi vu l'explication de la transformée en cosinus discrète et sa transformée inverse sur une seule ligne de huit pixels. Pour étendre cette relation, à un bloc de 8*8 pixels, il suffit d'étendre nos formules en prenant en compte les fonctions de base horizontales et les fonctions de bases verticales. C'est ce qui a été effectué dans la première formule qui a déjà été donnée plus haut mais pour la transformée inverse non. Il faut donc ajouter, une seconde variable à DCT pour pouvoir localiser un élément de la matrice après la DCT. En ajoutant cette variable, il faut également ajouter un symbole sigma d'addition comme le premier en début de formule sauf qu'il concerne la nouvelle variable que l'on a ajouté et enfin il faut multiplier le terme de la fonction cosinus par un terme de la même forme sauf qu'il concerne y au lieu de x, c'est-à-dire le domaine spatiale vertical. Au final, on obtient la transformée inverse en cosinus discrète, qui transforme la matrice N*N représentant le spectre de fréquences en la matrice IDCT de pixels que l'on avait au départ par la formule suivante :

Ainsi, après la transformée en cosinus discrète on obtient un nouveau domaine de représentation de notre image qui est un domaine fréquentiel via un spectre de fréquences. D'après les fonctions de bases que l'on a crée, plus on va vers les éléments de droites et/ou du bas de la matrice 8*8 que l'on a maintenant, alors plus on se dirige vers les hautes fréquences de l'image, c'est-à-dire les zones de l'image à forts contrastes. C'est à l'étape qui suit que l'on considéra cette propriété et que l'on exploitera pour justement enlever ces parties de l'image car l'oeil humain, ne verra que très peu de baisse de qualité.

3)La quantification :

La transformée en cosinus discrète appliquée sur une matrice carré, dans notre cas une matrice 8*8 n'a fait que transformer nos données mais elles sont facilement retrouvable dans leur état avant transformation, donc il n'y a pas eut de pertes d'informations jusqu'à présent sauf aux erreurs de précisions et d'arrondis mais il n'y a également pas eut de gains de place mémoire car il y a toujours autant de nombres dans la matrice c'est-à-dire 64 coefficients, la quantification est justement cette étape qui va permettre de réduire le poids de nos données.

Cette étape divise chaque coefficient de la matrice 8*8 après la DCT par un coefficient d'une matrice carré de même taille que la précédente, donc ici dans notre cas, cette matrice sera de 8*8 éléments, il faut préciser que ce tableau de valeurs est spécifique pour chacune des composante de l'image, de même on a vu que la transformée en cosinus discrète s'applique sur des blocs de 8*8 pixels pour chacune des composantes prise séparément. Donc un élément de la matrice d'entrée qui est localisé par une colonne et une ligne et bien, le coefficient de la matrice de quantification qui est localisé par la même colonne et la même ligne divisera ce coefficient de la matrice d'entrée.

Si Quant(i, j) représente l'élément de la matrice de quantification située à la colonne i et à la ligne j, avec ces deux variables variant de 0 à 7, on a alors nos nouvelles valeurs dans une nouvelle matrice Nx par la formule suivante :

Nx(i, j)= DCT(i,j)/Quant(i,j)

(où Nx(i,j) représente l'élément de la matrice à la colonne i et à la ligne j de la matrice après quantification)

Mais comme arrive-t-on à réduire le poids d'un coefficient? En fait, cette étape est la seule étape destructrice de la norme JPEG, le tôt de compression d'une image va dépendre de la table de quantification que l'on aura. En effet plus un coefficient de cette matrice est grand, plus le coefficient de la matrice après la DCT, sera réduit, mais il sera également arrondi à l'entier le plus grand inférieur au nombre que l'on a après la division par le coefficient de quantification. Par exemple, si on a après la DCT un coefficient qui vaut 4 et que le coefficient de la matrice de quantification est 100, on a après quantification la valeur 0.04, mais comme cette valeur est arrondie à l'entier le plus grand inférieur à 0.04, on a la valeur 0. Comme on l'a vue précédemment le principe de la DCT est de trier nos données par fréquence, horizontales et verticales, plus on va vers les coefficients sur la droite, plus on sera dans les hautes fréquences horizontales qui sont moins importantes et plus on va vers les coefficients plus en bas, plus on ira vers les hautes fréquences verticales qui sont moins importantes. On a déduit que les données les plus importantes dans la matrice après la transformée en cosinus discrète se situent en haut à gauche de celle-ci, on peut donc attribuer dans la matrice de quantification des coefficients plus élevés plus on va vers la droite et vers le bas. Voici un schéma montrant deux flèches désignant deux sens des hautes fréquences :

La bonne manière de tirer partie des informations importantes du bloc 8*8 est de créer une équation qui prend en paramètre un facteur de qualité de 1 à 10 mais également le fait qu'il faut que les coefficients à droite et en bas aient des valeurs de plus en plus grandes lorsque l'on se dirige vers le coin en bas à droite. Voici l'exemple d'une équation qui prend en compte ces paramètres, où i et j représentent respectivement la colonne i et la ligne j avec Q(i,j) l'élément désigné dans la matrice de quantification:

Q(i,j)=1 + ( 1 + i + j )*Facteur

Ce n'est bien entendu qu'un exemple d'équation, on peut en créer une infinité et chaque logiciel utilise sa propre équation pour trouver le meilleur compromis entre qualité de l'image et sa taille. On peut également noter que chacune des diagonales doivent avoir des coefficients proches voir identiques, en effet sur cette droite, pour un coefficient donné, un autre coefficient de cette diagonale, sera plus dans les hautes fréquences horizontales mais plus dans les bases fréquences verticales, il y a donc comme un «équilibre» entre les coefficients d'une même diagonale. Sur l'image en-dessous, les lignes noires représentes ces diagonales et la flèche verte montre le sens où l'on monte de façon générale dans les hautes fréquences :

Cette caractéristique à propos des coefficients d'une même diagonale est importante car elle servira par la suite pour avoir un maximum de valeurs identiques les unes à la suite des autres mais surtout une suite de zéro plus ou moins longue.

En reprenant l'équation de la table de quantification, on a écrit un programme qui charge une matrice de pixel à partir d'un fichier de 8*8 valeurs et qui crée une matrice de quantification en fonction du facteur de qualité. Ce programme affiche les matrices de quantification et de pixels avant transformation et la matrice après les deux transformations mais également la matrice en utilisant les algorithmes inverses pour retrouver la matrice de pixel. On se rend bien compte qu'après les transformations, on obtient dans les deux cas, une matrice avec beaucoup de zéros à l'intérieur et que l'ensemble des valeurs ont tendance à être vers le haut à gauche, on se rend bien compte que les données pourront être beaucoup plus facilement réduite par rapport à la matrice de pixels du départ. De même, on se rend compte qu'en effectuant les algorithmes inverse on obtient une matrice de valeurs qui reste relativement proche de la matrice de départ, donc la perte de données est plus ou moins importante en fonction du facteur de qualité. Voici un aperçu des résultats que le logiciel donne pour les facteurs de qualité 5 et 17 :

Enfin si, on créer une table de quantification avec un facteur de qualité très élevé, par exemple 87, on obtient ce genre de résultats :

On voit ici qu'après la transformée en cosinus discrète, il ne reste plus d'un coefficient non nul dans la matrice, et la transformée inverse nous donne une matrice de pixels où chacun d'eux ont la même valeur donc la même couleur. Ce résultat signifie qu'à des taux de compression très élevés, nous aurons notre image qui commencera a avoir des blocs de N*N pixels qui auront la même couleur, on aura donc un effet de pixelisation c'est-à-dire où l'on verra de gros blocs de pixels qui auront la même couleur. Par exemple, si on a l'image originale juste en dessous, l'image compressée en JPEG un peu plus en dessous montre bien cette effet où l'on voit des blocs de couleurs uniformes ce qui donne un effet visuel pas très agréable pour l'oeil :

III/Compression non destructrice :

Nous allons donc passer à la troisième étape de ce TPE, qui consiste à compresser, cette fois-ci sans perte d’information. Il reste après la DCT, deux compressions pour la norme JPEG : La compression RLE (Run Length Encoding) ou RLC (Run Length Coding) et la compression Huffman.

1)La Compression RLE ou RLC

Cette méthode de compression est l’une des plus simples. Le principe est de remplacer une séquence de l éléments u identiques par un couple (u, l) . C’est à dire remplacer une addition par une multiplication.

Exemple : JPPPPPPPPPPEEEEEEEEEEEEEEEEEEEEEEGGGGGGGGGGGGGGGGGGGGG

On choisi un caractère spécial comme $ , après la compression nous obtenons donc :

J$10O$23A$21L Gain : 42 caractères soit 24%

Cette méthode est très utile pour la compression JPEG, car comme vu dans la partie 2 suite à la compression du type DCT nous retrouvons une très grande suite de 0. Cette suite de 0 est beaucoup plus importante par une lecture en « zigzag » : 

Utilisons maintenant cette méthode au cas général : En premier temps on définit un caractère spécial (dans l’exemple $) pour repérer le nombre de répétition du caractère, puis un seuil de répétition ( car cette méthode peut augmenter la taille des données si celles-ci comportent peu de suites de symboles identiques, d’où la mise en place du seuil de répétition) Ensuite, on commence la lecture un par un de chaque caractère de la chaîne en suivant cet algorithme :

La compression RLE voit son utilité essentiellement pour la compression des images, une image étant composée de répétitions de pixels, de couleur identique, codés chacun par un caractère.

2)La Compression Huffman

La méthode de compression Huffman consiste à diminuer au maximum le nombre de bits utilisés pour coder un fragment d’information. Prenons l’exemple d’un fichier de texte : le fragment d’information sera un caractère ou un suite de caractères. Plus le fragment sera grand, plus les possibilités seront grandes et donc la mise en œuvre complexe à exécuter. L’algorithme de Huffman se base sur la fréquence d’apparition d’un fragment pour le coder : plus un fragment est fréquent, moins on utilisera de bits pour le coder. Par exemple dans un fichier texte, si on considère que notre fragment est la taille d’un caractère, on peut remarquer que les voyelles sont beaucoup plus fréquentes que les consonnes : par exemple la lettre ‘e’ est largement plus fréquente que la lettre ‘x’ par conséquent la lettre ‘e’ sera codée sur moins de bit que la lettre ‘x’ : la lettre ’e’ peut être sur 2 bits et ‘x’ sur 10 bits.

Pour utiliser cet algorithme, prenons exemple pour un codage des caractères dans un texte :

Il faut tout d’abord créer un tableau à deux entrées : d’une part les caractères de la chaîne , d’autre part leur nombre de répétition. Ensuite il faut trier la liste par ordre croissant de fréquences. Puis construire l’arbre à partir de la liste ordonnée de nœuds, il suffit de prendre les deux nœuds les moins fréquents et de les ajouter comme fils d’un nouveau nœud qui aura pour fréquence la somme des deux.

Si nous prenons par exemple un texte qui comporte :

On prend les deux nœuds les moins fréquents (f et e) , et on crée un nouveau nœud :

Et ainsi de suite jusqu’à ne plus avoir qu’un seul nœud.

Après cela, pour avoir le codage de chacune des lettres, on complète l’arbre : descendre vers la gauche équivaut à un 0 vers la droite à un 1 :

On en déduit donc le codage suivant :

Sur cet exemple nous voyons très bien que le a, apparaissant 45 fois est codé grâce à cette compression sur un seul bit, sans cet méthode il aurait très bien pu être codé sur 4 bits et la lettre f sur 1 bit ! Voilà donc pourquoi cette compression est importante.

Il existe 3 variantes de cet algorithme :

- Non adaptive : l’arbre est élaboré à partir d’une table des fréquences fixe ce qui fait qu’il est adapté à un seul type de donnée, et dans certain cas le fichier sera plus important après la compression.

- Semi adaptive : On lit une fois le fichier à compresser pour créer la table des fréquences, puis on s’en sert pour compresser le fichier. C’est la méthode la plus efficace mais elle présente l’inconvénient de nécessiter l’arbre que l’on devra introduire dans un en-tête.

• Adaptive : La table des fréquences est élaborée au fur et à mesure de la lecture du fichier et l’arbre est reconstruit à chaque fois. On réalise l’arbre avec les premiers caractères (que l’on ne compresse pas) et on s’en sert pour compresser les caractères suivants que l’on utilise aussi pour actualiser l’arbre etc.. Elle est un peu moins efficace que la méthode semi adaptive mais le résultat final est souvent meilleur car elle ne nécessite pas le stockage de l’arbre, et de plus elle ne nécessite qu’une lecture du fichier.

Conclusion :

Nous avons décidé de choisir comme sujet : «La compression d'images numériques par le JPEG» pour répondre à une question que nous nous posions, comment deux images paraissant pratiquement identiques à nos yeux puissent prendre un espace disque totalement différent, par exemple cette image :

L'image compressé qui prend 1150 Ko contre 35 Ko pour l'image compressé en JPEG, soit 3% de la taille original! Dans une première partie nous avons vu que chaque pixel, lorsque l'image n'est pas compressée (format BMP ou BITMAP) est caractérisée par 3 composantes de base, la composante R, qui definit les domaines de nuances rouges, le V qui definit les domaines de nuance vertes et en dernier lieu le B, qui s'occupe de la couleur bleue. Ce qui nous donne au final un pixel codé en RVB (ou aussi appellé RGB). Le principe de la compression YUV est tout simplement d'optimiser ce codage couleur. En effet, au lieu de décomposer le pixel en 3 couleurs, on le décompose en 3 "caractéristiques" qui sont la luminance ou luminescence (Y ou Brigthness en anglais), la chrominance bleue (Cb ou U, tons de bleu), ainsi pour finir que la chrominance rouge (Cr ou V, tons de rouge). Tout cela dans le but de compresser l'image avec les caractéristiques de l'oeil qui est, pour nous humain, plus sensible au variations d'intensité lumineuse qu'au variations dans l'echelle des teintes (chrominance). Ensuite dans une seconde partie la transformée en cosinus discrète, le but étant de transformer le domaine de représentation de nos données, c'est à dire de passer d'un domaine spatial à un domaine fréquentiel, ce qui permet de trier efficacement l'ensemble des données de l'image et ainsi supprimer certaines données de l'image où l'oeil humain ne verra que très peu de différences : les hautes fréquences de l'image représentant les zones à forts contrastes de l'image. Et enfin dans une troisième partie les deux dernières compressions du types RLE (Run Length Encoding) et Huffman, qui sont des encodages sans pertes d'informations, permettant de tirer partie du travail que la DCT a effectué.

A travers ce TPE, nous avons analyser comment la compression d'une image Bitmap se faisait, mais pour décompresser l'image, il faut appliquer les algorithmes inverses dans le sens inverse c'est-à-dire la décompression Huffman, puis RLE au niveau de la décompression sans perte puis on applique la transformée en cosinus discrète inverse et pour finir on applique la transformation inverse de couleur de YCbCr à RGB. On retrouve ainsi notre image de départ avec une perte de donnée cependant.

Ainsi en appliquant des procédés d'optimisations et de concentration de l'essentiel des données de l'images, on a pu réduire la taille de l'image sur l'ordinateur. Mais cette compression, a quand même un coup qui est une perte de donnée qui peut être faible mais également beaucoup plus grande et très désagréable pour l'oeil ce qui signifie également que la compression JPEG est surtout optimisé pour certains type d'images qui sont des images photographiques et surtout pas des images géométriques où les discontinuités de celles-ci entraînent de très mauvais rendus. Enfin, il faut compter du temps de calcul pour la décompression et la compression de l'image. Aujourd'hui les machines informatiques deviennent de plus en plus rapide donc ce n'est plus vraiment un inconvénient mais pour des machines plus vieilles, ce temps peut-être ressenti. On peut donc conclure en disant que le JPEG est une norme de compression d'image à utiliser pour des images de types photographiques, mais les dégradations que l'image subie peuvent être importante et c'est pour ça que de nouvelles normes de compression ont été mises en place pour avoir des images de meilleurs qualités en abaissant encore la taille de l'image comme par exemple la norme JPEG2000 qui pour une qualité équivalente a des images qui peuvent être de taille dix fois moins grande, ou encore la compression par ondelettes ou par fractale.

Glossaire :

Bit :

Le plus petit élément de la mémoire d'un ordinateur qui peut prendre deux valeurs possible, soit 1 ou soit 0.

Octet :

Un paquet de huit bits qui se suivent dans la mémoire et qui possède une adresse mémoire. La mémoire d'un ordinateur est caractérisée par le nombre d'octet qu'elle contient. Les autres unités sont le Kilo-octet (Ko) où 1 Ko = 1024 octets = 2¹⁰ octets, le Méga-octet (Mo) où 1 Mo = 1024 Ko = 1048576 octet = 2²⁰ octets.

Pixel :

Cette le plus petit élément composant une image qui est décrit avec trois valeurs qui sont le rouge, le bleue et le vert avec une valeur variant de 0 à 255.

Pixelisation :

C'est un effet visuel où l'image originale perd en qualité. Elle transforme une belle image en un ensemble de gros blocs de pixels colorés avec la même couleur à l'intérieur de ce bloc.

Résolution :

C'est le nombre de colonnes et de lignes de pixels d'une image ou d'un écran d'ordinateur ou de télévision par exemple.

RBG (Red, Green, Blue pour rouge, vert et bleue):

C'est une abréviation pour désigner une couleur qui est définie par trois composantes : rouge, vert et bleue.

Bibliographie :

Internet :

-Les algorithmes de compression et d'encodage du JPEG :

http://mp01.free.fr/comp/comp.htm

http://lab.erasme.org/compress/index.html

http://donut.99.free.fr/En-vrac/tipe/dct.htm

http://inepty.free.fr/

http://crteknologies.free.fr/projets/tpe_compression_graphique

http://xavier.chassagneux.free.fr/tipe/tipe.htm

http://www.artemis.jussieu.fr/wwwos2/html/dess/memoire/promo95/muller/COMPRESS.HTM

http://developpeur.journaldunet.com/tutoriel/gra/010820gra_compression.shtml

http://iphilgood.chez.tiscali.fr/Codage/Compressionjpeg.htm

http://www.kaddour.com/chap2/chap2.htm

http://www.chez.com/nico77

-L'appareil photo numérique :

http://artic.ac-besancon.fr/technologie/Formation/Production_01/gg1/fabric05.htm

http://www.ac-versailles.fr/etabliss/herblay/audiovis/techniq/FORMAT/Ccd.htm

-Les images :

http://donut.99.free.fr/En-vrac/tipe/synthese.htm

http://www.hebus.com