Travaux Pratiques 5

的 Joseph Razik, last modified 在 2018-12-03

Approche de la compression JPEG

Objectif

L'objectif de ce TP est d'analyser le fonctionnement d'un algorithme standard de compression d'image, le JPEG (Joint Photographic Experts Group). L'idée au coeur de cet algorithme est la suppression d'information non perceptible. Pour cela, il utilise la notion de transformée de Fourier et de quantification.

Préambule

Pour effectuer les quelques exercices de ce TP, vous allez travailler dans l'environnement notebook d'IPython/Jupyter. Pour cela, créez un répertoire pour cette matière, déplacez-vous dans celui-ci et exécutez les commandes suivantes :

$> module load python/3.6.5
$> jupyter-notebook

Ceci va ouvrir votre navigateur sur un explorateur de fichier du répertoire dans lequel vous avez lancé la commande.

Si vous obtenez un message d'erreur comme quoi la commande module n'existe pas, exécutez la commande suivante :

$> source /usr/local/Modules/init/profile.sh

Créez un nouveau projet Python3, que vous nommerez tp5.

Au début, dans la première cellule, pour activer le remplissage de l'espace de nommage avec les modules Numpy et Matplotlib (et math), écrivez la commande suivante et exécutez la cellule avec la séquence de touche Ctrl-Enter ou Shift-Enter

%pylab inline

Le découpage par blocs

Globalement, le principe de l'algorithme JPEG est de découper l'image à compresser en blocs carrés, puis d'appliquer sur ces blocs une transformée de Fourier. La deuxième étape importante est de quantifier les coefficients de Fourier avec principalement la mise à zéro des valeurs faibles, celles des hautes fréquences (les détails). Ensuite sera appliqué un algorithme de codage/compression sur ces ensembles de valeurs.

Ainsi la première étape consiste à découper l'image source en blocs carrés de taille égales.

  1. Écrivez la fonction decoupe_blocs() qui prend comme paramètre un tableau représentant l'image en niveau de gris, ainsi que la taille du bloc (largeur en pixels du carré).
  2. En utilisant l'image retournée par la fonction ascent() du module scipy.misc, vérifier qu'en affichant le premier bloc retourné par votre fonction avec comme paramètre la taille de l'image, vous obtenez l'image originale. N'oubliez pas de forcer le passage de la représentation en niveau de gris.
  3. JPEG utilise des blocs de 8x8 pixels. Affichez les 4x4 blocs de 8x8 (16 sous-figures) correspondant au coin supérieur gauche de l'image.

La transformée en cosinus discret

La seconde étape consiste à calculer la transformée de Fourier sur chaque bloc. Cette transformée est définie cette fois sur un espace à deux dimensions. Pour rappel dans un espace à une dimension, les vecteurs de la base orthogonale de Fourier sont :

\begin{equation*} w_k[n] = e^{2i\pi kn/N} \end{equation*}

Or, en dimension 2, on peut montrer que les vecteurs \(w_{k,j}\) suivants forment une base orthogonale :

\begin{equation*} w_{k,j}[n, m] = w_k(n)\times w_j(m) = e^{2i\pi kn/N} \times e^{2i\pi jm/N} \end{equation*}
  1. À l'aide de la fonction fft2 de numpy.fft, calculez et affichez la transformée de l'image originale, puis des 4x4 blocs de 8x8 correspondant au coin supérieur gauche.

En fait, dans l'algorithme JPEG, une autre forme de transformée est utilisée : la transformée en cosinus. La différence avec la transformée de Fourier classique est le choix de la base orthogonale. Dans le cas de la DCT, les vecteurs de la base sont purement réels (pas d'harmoniques exponentielles complexes). La raison de ce choix vient du fait que cette transformation en cosinus, par ses conditions aux bords, permet de mieux gérer les discontinuités et de grouper l'énergie de la décomposition sur un faible nombre de coefficients ainsi obtenir une compression plus efficace.

  1. Refaire la question précédente mais en utilisant cette fois la transformée en cosinus discrète dct() du module scipy.fftpack et en spécifiant le paramètre norm='ortho'.

La quantification

La troisième étape consiste à appliquer une quantification des valeurs de la transformée obtenue afin de principalement mettre à zéro les valeurs proches de zéro. Habituellement, ces valeurs sont celles correspondant aux hautes fréquences.

  1. Écrivez la fonction quantification qui prendra en paramètres une liste de blocs de valeurs et quantifiera chacun N valeurs entières.
  2. JPEG utilise une quantification sur 32 valeurs. Calculez cette quantification sur les la transformée de l'image originale, puis des 4x4 blocs de 8x8 correspondant au coin supérieur gauche, et les afficher.

Le codage

Une fois l'étape de quantification effectuée, l'algorithme JPEG applique une technique compression par codage des informations résultantes. Nous n'allons pas détailler celle-ci. À la suite de cet ensemble d'étapes nous obtenons un fichier image au format standard JPEG

La reconstruction de l'image

Une autre phase importante dans l'utilisation de l'algorithme de compression JPEG est de pouvoir retrouver et visualiser l'image. Comme nous avons appliqué une quantification, cet algorithme est destructif et la reconstruction ne redonnera pas exactement l'image d'origine. Le jeu sur les paramètres tels que la taille des blocs et la résolution de la quantification vont permettre de moduler l'équilibre perte d'information / poids en octets.

Pour retrouver une image, il y a tout d'abord une étape de décodage, mais que nous n'avons pas traité.

Ensuite, nous devons inverser la transformée en cosinus afin de revenir de l'espace fréquentielle à l'espace image.

  1. En utilisant la fonction idct() du module scipy.fftpack pour inverser la transformée en cosinus, reconstruisez et affichez le résultat d'une compression JPEG classique: blocs de 8x8 et quantification sur 32 niveaux.
  2. Faites de même en faisant varier ces paramètres:
    • blocs 8x8 et 16 niveaux
    • blocs 8x8 et 4 niveaux
    • blocs 32x32 et 32 niveaux
    • blocs 32x32 et 16 niveaux
    • blocs 32x32 et 4 niveaux