INF4710: Introduction aux technologies multimédia TP1

École Polytechnique de Montréal

Département de génie informatique

Travail pratique No 1
La compression d’images fixes par DCT

Objectif général :
L’objectif principal de ce travail pratique est d’utiliser la transformée en DCT pour coder des
images numériques afin de permettre une compression des images en tenant compte du modèle
psycho visuel humain qui se comporte comme un filtre passe bas.

Théorie :
La compression d’images est une procédure indispensable dans les applications de transmission
de données à travers un réseau de communication. La norme JPEG constitue une des méthodes de
compression les plus fréquemment utilisées pour les images fixes. Elle consiste à transformer
l'
image en un code, dont l' espace de stockage est plus faible que celui de l'
image de départ. Pour
retrouver l'
image de départ, ou techniquement l' image de départ dégradée, il s'
agit de décoder le
code stocké en mémoire. Les étapes de codage et de décodage sont illustrées à la Figure 1, et sont
expliquées plus spécifiquement dans ce qui suit.

Figure 1 - Organigramme de la compression JPEG

• Le découpage en blocs de pixels :

Cette étape consiste à subdiviser l'
image de départ en sous-blocs carrés, de taille 8x8 pixels, ou
16x16 pixels.

1/5
INF4710: Introduction aux technologies multimédia TP1

• La transformation en cosinus discrète (DCT) :

Cette transformation est appliquée à chaque bloc, et permet d' exprimer son contenu en termes de
fréquences horizontale et verticale, notées u et v, et d' amplitude C(u,v), selon l' équation suivante :
n −1 n −1
π (2 x + 1)u π (2 y + 1)v
C (u , v) = c(u ) × c(v) × F ( x, y ) × cos( ) × cos( ) Eq.1
x = 0 y =0 2n 2n
La transformée inverse est donnée par :
n −1 n −1
π (2 x + 1)u π (2 y + 1)v
F ( x, y ) = c(u ) × c(v) × C (u , v) × cos( ) × cos( ) Eq.2
u =0 v = 0 2n 2n

1
si w = 0
Dans les deux cas, c( w) = n
2
si w = 1...n − 1
n
Avec n, la taille du bloc, et F(x,y), la couleur au pixel (x,y) de l’image de départ.

• La quantification :
Cette étape consiste à atténuer les hautes fréquences du bloc, représentant les détails fins de
l'
image, auxquels l' œil humain est peu sensible. Techniquement, il s' agit de diviser termes à
termes les valeurs C(u,v) du bloc transformé par DCT, par les valeurs d' une matrice de même
taille, dite table de quantification. Cette dernière peut être construite de plusieurs manières,
comme :
- la table vue en cours. Pour obtenir les différents niveaux de compression, il s' agit de
multiplier cette table par un paramètre k ∈ ℜ .
- ou, en affectant à chaque élément une valeur proportionnelle à sa position dans la table,
suivant l'équation suivante :
Q (i, j ) = 10 + k × (i + j + 1) Eq. 3
avec k ∈ ℜ étant le facteur de qualité, relié au niveau de compression souhaité.
Le résultat de la quantification n'étant pas toujours entier, il s'
agit d'
arrondir les valeurs obtenues,
vers les valeurs entières les plus proches.
La quantification inverse consiste à multiplier les valeurs obtenues après le décodage de
Huffman, par la même matrice de quantification, utilisée lors du codage.

• Le codage de Huffman :
Suite à la quantification, de nombreux zéros apparaissent dans chaque bloc, essentiellement dans
les hautes fréquences. Il s'agit alors, avant le codage de Huffman, de réorganiser les valeurs du
bloc dans un vecteur. Cette étape représente la lecture en zigzag du bloc (Figure 2).

2/5
INF4710: Introduction aux technologies multimédia TP1

Figure 2 - Lecture en zigzag

Elle permet de trier les valeurs par ordre croissant de fréquences. La plupart des zéros
apparaissent alors à la fin du vecteur obtenu. Cela étant réalisé, il est possible de tronquer le
vecteur de sorte à éliminer le dernier regroupement de zéros successifs. Finalement, avant de
réaliser le codage de Huffman, il s'agit de regrouper les vecteurs obtenus pour chaque bloc de
l'
image, dans un même vecteur, en faisant attention à séparer les vecteurs de blocs par une valeur
qui ne peut exister parmi les valeurs, par exemple le nombre 257. Nous obtenons ainsi un long
code. Pour réduire la taille de ce dernier, un codage de Huffman est effectué sur le vecteur
résultant. Lors du décodage JPEG, il s'agit d'exécuter les étapes inverses : décodage de Huffman,
puis, regroupement par vecteurs de blocs, et, passage de vecteurs à matrices de bloc.

Manipulations :
Dans ce travail pratique, vous utiliserez Matlab ou le langage que vous maîtrisez le plus pour lire
les trois images numériques fournies sur le site web du cours (Lion.bmp, Car.bmp,
Champs.bmp) et implémenter les différentes phases de la compression JPEG basée sur la
transformation DCT. Plus spécifiquement…

1. Téléchargez dipum_toolbox au lien suivant :

http://www.imageprocessingplace.com/DIPUM_Toolbox_1/dipum_toolbox_main_page.htm

Pour utiliser cette toolbox dans Matlab :

- décompresser le contenu du fichier dans un répertoire,
- Sélectionnez dans Matlab : File -> Set Path...
- Add Folder,
- Sélectionner le répertoire contenant les fichiers du toolbox,
- Sélectionner Save et ensuite Close.

3/5
INF4710: Introduction aux technologies multimédia TP1

Parmi les fonctions de ce toolbox, vous utiliserez les fonctions mat2huff, huff2mat, qui
permettent respectivement le codage et le décodage de Huffman, ainsi que la fonction
imratio qui calcule le taux de compression. Voici quelques informations sur les
entrées/sorties des fonctions :

y=mat2huff(x)
x : matrice à encoder
y : structure contenant les valeurs encodées, avec y.code : vecteur des valeurs encodées
avec Huffman

y=huff2mat(x)
x : structure contenant les valeurs encodées
y : matrice des valeurs décodées

cr=imratio(f1,f2)

f1,f2 = image originale et image compressée, respectivement

cr = ratio de compression

2. Pour chacune des images, effectuer une compression selon un niveau donné (par exemple
k = 1), en effectuant les opérations suivantes :
a. Effectuer un découpage préalable de l’image en blocs de 8*8 pixels;
b. Effectuer une transformation par DCT de chacun des blocs; pour vérifier si la DCT
est correcte, comparer avec la fonction DCT de Matlab.
c. Utiliser la table de quantification présentée en classe pour quantifier les
coefficients DCT obtenus pour chaque bloc;
d. Réordonner les valeurs quantifiées obtenues en zigzag;
e. Utiliser la fonction mat2huff pour générer le code de Huffman d’une matrice ainsi
que la fonction huff2mat pour effectuer l’opération inverse;
f. Utiliser la fonction imratio pour évaluer le taux de compression;

3. Reconstruire l’image originale en effectuant une opération de décompression et évaluer

l’erreur de distorsion inhérente au processus de compression et de reconstruction par
transformée inverse en utilisant la métrique présentée en cours (erreur quadratique
moyenne ou MSE).

4. Refaire les manipulations décrites dans 2 et 3 pour effectuer une compression selon quatre
autres niveaux. Pour obtenir les différents niveaux de compression, multiplier la table de
quantification par un nombre entier k = 1, 4, 8, 12, 20.

4/5
INF4710: Introduction aux technologies multimédia TP1

5. Refaire les manipulations décrites dans 2 et 3 mais en définissant des tables de

quantification selon la formule de l’équation Eq. 3. Pour obtenir les différents niveaux de
compression, faire varier k = 1, 4, 8, 12, 20.

6. Refaire les manipulations décrites dans 2 et 3 en effectuant l’opération de compression sur

l’image avec découpage préalable en blocs de 16x16 pixels. Utilisez la table de
quantification de votre choix.

Analyse des résultats

1. Pour chaque image, tracer une courbe illustrant le taux de compression en fonction de
l’erreur quadratique moyenne obtenus pour chaque niveau de compression.

2. Comparer les résultats obtenus pour les trois différentes images puis discuter et expliquer
ces résultats en considérant les courbes tracées précédemment ainsi que les différentes
images obtenues.

3. Comparer les résultats obtenus pour une compression basée sur un découpage préalable de
l’image en blocs de 8x8 et une compression basée sur un découpage préalable de l’image
en blocs de 16x16. Discuter les résultats et les différences observées. Discuter les
avantages et les inconvénients de l’augmentation de la taille des blocs.

4. Quels avantages de la compression par bloc ressortez-vous de vos résultats ? Quels sont
les intérêts de la compression par bloc comparée à une compression sur l’image entière ?

5. Quels changements dans l'

algorithme devraient être envisagés dans le cas d'
images
couleurs ?

Travail à remettre

Le travail demandé consiste à effectuer toutes les manipulations demandées et à rédiger un

rapport permettant de répondre aux questions de la section analyse des résultats. Le code
couvrant les manipulations devra être remis en annexe de votre rapport. De plus, vous devrez
zipper l'
ensemble des fichiers scripts, et l'
envoyer à l'
adresse suivante : [email protected]

La date de remise du rapport est le mercredi 25 février 2009. Une évaluation du code sera
effectuée à la fin de la séance du mercredi 18 février 2009.

5/5