Accueil

Généralités

Pourquoi compresser ?

L'algorithme JPEG

La DCT

Codage statistique

Synthèse des algoritmes

D'autres méthodes

Notre programme

Le pathfinding(TIPE 2003/2004 de Math sup)

 Livre d'or 

Quelques liens

Delain

les vidcast

L'algorithme JPEG :

Le sigle JPEG vient du nom du groupe d'experts internationaux (Joint Photographic Expert Group) qui a établi, en 1991, la norme que nous utilisons encore aujourd'hui. Cette norme est, en fait, basée sur la DCT (Discret Cosin Transform), méthode proposée en 1974 par le professeur Rao de l'université du Texas.

Le principe de l'algorithme JPEG est le suivant :

Pour mieux comprendre ce principe, prenons comme exemple la matrice suivante représentant la composante rouge d'une image codée en 16 millions de couleurs (soit 256 nuances de rouge).

La première étape consiste à soustraire 128 (ce qui correspond au nombre de couleurs rouge divisé par 2) à chaque valeur puis à appliquer la DCT. Nous obtenons le résultat suivant.

On remarquera que les coefficients possédant les valeurs absolues les plus fortes se trouvent en haut à gauche de la matrice.

L'étape suivante est celle de la quantification. Elle consiste à donner les valeurs approximatives de la matrice précédente. Pour cela, on remplace chaque valeur par le quotient de la division euclidienne de cette valeur par le pas de quantification. Ainsi, si l'on choisit un pas de quantification de 4, on remplacera les valeurs 0, 1, 2 et 3 par 0 ; les valeurs 4, 5, 6 et 7 par 1 et ainsi de suite. C'est ici que nous allons perdre des données, mais d'une manière astucieuse. En effet, on va choisir un petit pas pour les valeurs en haut à gauche et un pas de plus en plus grand au fur et à mesure que l'on descend en bas à droite de la matrice. La matrice de quantification Q nous est donnée par la relation suivante :

Q(i,j) = 1 + F(1 + µ (in + jn)) , où F est le facteur de qualité.

Dans notre exemple, nous prendrons µ = n = 1 et F = 5. Ce qui nous donne, après simplification :

Q(i,j) = 1 + 5(1 + i + j)

Nous obtenons la matrice de quantification suivante :

Divisons maintenant les valeurs de la matrice de données par notre matrice de quantification. Le résultat est le suivant :

Vous serez sans doute étonné par le nombre de zéros.

La dernière étape consiste à compresser (sans perte) la matrice obtenue. La norme JPEG traite les 0, en raison de leur nombre important, d'une manière particulière. On va d'abord balayer la matrice de la façon suivante pour obtenir les suites de 0 les plus importantes possibles :

On utilise ensuite une méthode de compression statistique tel que celle de Huffman.

La compression est terminée.

Voyons maintenant comment réaliser la décompression de la matrice précédemment compressée.

La méthode est la suivante :

Après décodage statistique, nous retrouvons notre matrice compressée :

Il faut maintenant déquantifier en multipliant chaque valeur par son coefficient de quantification. Nous obtenons ceci :

Appliquons ensuite la DCT inverse, enfin ajoutons 128 à chaque valeur. Voici la matrice décompressée :

Remarque : les valeurs négatives seront remplacées par des 0 et les valeurs supérieures à 255 par 255.

Voyons maintenant, l'évolution du taux de compression et de la taille de l'image compressée en fonction de la qualité :

Le premier nombre est le nombre de bits de l'image compressée, le second est le taux de compression optenu et le dernier indique la qualité choisie.

On peut remarquer que la qualité se dégrade rapidement alors que l'augmentation du gain de place est de moins en important.

Retour à l'accueil.