Guez Lionel - Algorithmes de compression d'images et quadtree

De Ensiwiki
Aller à : navigation, rechercher


Algorithmes de compression d'images et quadtree

Labo Laboratoire LJK
Equipe MGMI
Encadrants sylvain.meignen@imag.fr

Etudiant

GUEZ, Lionel, MMIS-MCS


Introduction

Le but du TER, était de faire un état de l'art de deux algorithmes modernes de compression d'image : EZW et EBCOT(ce dernier étant utilisé par JPEG2000), de comprendre leur force, leur faiblesse, et leur différence.Cet état de l'art passant par l'implémentation (de préférence en MATLAB) des deux algorithmes.

Par rapport aux méthodes "classiques", tels JPEG, les algorithmes modernes utilisés dans la compression d'image sont conçus non seulement pour donner un meilleur taux de compression, mais pas seulement. En effet, le format engendré par l'algorithme doit assurer des fonctionnalités supplémentaires. La plus importante étant la scalabilité : Pour comprendre ce qu'est la la scalabilté (qui est un angliscisme venant de scalability), voyons comment sont stockées les données d'une image dans un format "classique"(JPEG,PNG,...) : les données sont stockées dans un certain ordre (ex de gauche à droite puis de haut en bas), si bien que si on décode la moitié du fichier, on aura la moitié de l'image. A l'inverse, les format modernes (JPEG2000) stockent d'abord les données nécessaires au décodage de l'image complete mais de trés faible qualité, puis ajoute, à la suite, les details grossiers, puis les détails fins, etc.... C'est cette propriété qu'on appelle scalabilité. Une autre propriété interessante est la mise en place de Région d'Intêret, c'est-à-dire que le format doit permettre de moins compresser certaines zones de l'image afin d'assurer une meilleure qualité pour cette zone. D'autres propriétés peuvent être utiles : Résistances aux erreurs, Navigabilité(possibilité de trouver facilement une zone),etc.... Les deux algorithmes étudiés sont scalables, par contre seul EBCOT dispose des autres fonctionalités.

Les deux algorithmes ont pour point commun de ne pas utiliser la transformée de Fourier, comme les algorithmes classiques, tels JPEG, mais préfèrent utiliser une transformée en ondelettes, qui a de biens meilleures propriétés au niveau de la scalabilité et au niveau de la compression. Nous allons ainsi commencer par expliquer en quoi consiste cette transformée, puis nous verrons les algorithmes. Puis j'expliquerai mes apports personnels.

Eléments de prérequis

Transformée en Ondelettes

Alors que la transformée de Fourier donne le contenu fréquentiel d'un signal, une transformée en ondelettes, elle , donne le contenu fréquentiel mais ajoute une information sur quand une fréquence donnée apparait dans le signal. A titre indicatif, on donne la formule de la transformée en ondelettes dans le domaine continu :



Wf\left( a , b \right) = \frac{1}{\sqrt{a}} \int_{-\infty}^{\infty} f\left( x \right)  \overline{\psi\left( \frac{x-b}{a} \right) } 
 \psi est une fonction qui vérifie certaines propriétés et qui se nomme l'"ondelette mère".


Mais, puisque la compression d'image s'appuie sur des données intrinsèquement discrètes (l'image est exprimé en pixels), EZW et EBCOT, s'appuie sur une transformée en ondelettes discrète : Cette transformée s'appuie, dans le cas d'une transformée en ondelettes de Haar(il y a plusieurs types de transformées), sur une base spéciale de l'espace, nommée base de Haar. Dans le cas 2D (qui est le cas basique pour une image) les premiers éléments(non-normalisés) de la base de Haar s'écrivent :



\phi=\begin{pmatrix} 
 1 &  1 &  1 &  1 \\
 1 &  1 &  1 & 1 \\
  1 & 1  &1 & 1 \\ 
 1&  1 & 1 & 1  
\end{pmatrix}  ;
\psi^1=\begin{pmatrix}
  1 & 1 &-1 & -1 \\ 1 & 1 & -1  &-1 \\  1 &  1 & -1 & -1 \\  1 & 1  &-1 & -1  
\end{pmatrix} ;
\psi^2=\begin{pmatrix}
  1 & 1 & 1 & 1 \\ 1 &  1 &  1 & 1 \\  -1  & -1  & -1 & -1 \\  -1 & -1 & -1 & -1 
\end{pmatrix}  ;



\psi^3=\begin{pmatrix}
  1  & 1  & -1 & -1 \\ 1 & 1  & -1 & -1 \\  -1 & -1 &  1 & 1 \\  -1 & -1 & 1 & 1  
\end{pmatrix}  ; 

\psi^1_{1,(0,0)}=\begin{pmatrix}
  1 & -1  & 0 & 0 \\ 1 & -1  & 0 & 0 \\  0 & 0 &  0 & 0 \\  0 & 0 & 0 & 0 
\end{pmatrix}  ; 
\psi^2_{1,(0,0)}=\begin{pmatrix}
  1 & 1  & 0 & 0 \\ -1 & -1  & 0 & 0 \\  0 & 0 &  0 & 0 \\  0 & 0 & 0 & 0  
\end{pmatrix} ,etc..


On projette alors les coefficients de l'image(c'est-à-dire les "points" de l'image) dans la base de Haar, on obtient alors de nouveaux coefficients.

Enfin, on place les coefficients d'une certaine manière qui permettent de mettre les basses fréquences plutôt en haut à gauche, et les hautes fréquences dans les 3 autres coins. Les différences horizontales sont placées en bas à gauche, les différences verticales sont placées en haut à droite , et les différences "diagonales" sont placées en bas à droite. Pour voir,comment sont placés ses coefficients, voici une transformée en ondelettes incomplète (une variante de la transformée en ondelettes) de l'image "lenna" :


Transformée en ondelettes incomplètes


Remarquons que les faibles fréquences correspondent à l'image originale mais de taille et de résolution plus faible. La sous-image encadrée en rouge correspond à une version de "plus haute fréquence" de la sous-image encadré en vert. Mais ces deux image sont de mêmes natures(elles représentent les différences horizontales).

EZW

Le principe d'EZW se base une structure de données spéciale nommé quadtree. Pour comprendre ce qu'est un quadtree, observons l'image précédente, on remarque qu'elle est composé de plusieurs sous-images, et que la sous-image encadrée en rouge est 4 fois plus grande que la sous-image encadrée en vert. Cela indique qu'à un point de la deuxième sous-image correspond, dans la première sous-image, à une zone composée de quatres points. Ainsi en considérant que quatre points d'une zone d'une sous-image de haute fréquence sont les fils du point de la même zone mais dans l'image de fréquence immediatement plus faible, on obtient des arbres où chaque noeud a quatres fils(excepté les racines qui en ont 3). L'arbre ainsi créé se nomme un quadtree. Ensuite, le principe de l'algorithme se base sur la considération suivante : si un noeud est insignifiant, ie est inférieur à un certain seuil, alors ses fils(et donc ses petits-fils, et donc toute sa descendance) ont une grande chance d'être insignifiant(on appelle ce type de noeud un zerotree). Ainsi, le principe de l'algorithme est de choisir un seuil, de construire l'arbre puis d'élaguer les zerotrees, on obtient ainsi un arbre relativement petit qui contient les éléments de l'arbre, on code ensuite cet arbre dans le fichier. Puis on choisit un seuil plus petit, et on recommence pour coder les details manquants, et ainsi de suite. On obtient ainsi un codage scalable et efficace.


EBCOT

Le principe d'EBCOT est de diviser l'image transformée en "codeblock"(carré de taille fixe 32x32 ou 64x64) puis de compresser indépendament, et de manière scalable, chacun de ces codeblocks. On obtient ainsi N flux binaires (ou N est le nombre de codeblocks) : un pour chaque codeblock. Le codage étant scalable, chaque flux binaire est décomposable en morceaux : plus on décode de morceaux(en commencant par les premiers), plus le décodage donne une image fidèle du codeblock. Ainsi, l'algorithme choisit quelles morceaux garder afin d'optimiser la qualité de l'image pour un taux de compression donné. Toutefois la façon de choisir et d'organiser(dans le fichier) les morceaux est trés paramètrable et peut donc viser plusieurs objectifs : avoir le meilleur taux de compression, avoir une codage scalable, choisir une zone d'intêret, etc...

Travail réalisé

EZW

J'ai implémenté un programme en CAML, qui effectue ces algorithme que j'ai comparé à un programme MATLAB fait par des chercheurs. J'ai alors testé quelques variantes :


Premiere variante

J'ai éssayé de changer la manière de coder les coefficients signifiants. L'algorithme, quand il parcout l'arbre distingue 4 types de points : les coefficients signifiants positifs notés POS, les coefficients signifiant négatifs notés NEG, les coefficients insignifiant mais dont un fils (ou un autre membre de sa descendance) est signifiant notés IZ(Izolated Zero), et les coefficients insignifiant et dont toute la descendance est insignifiante notés ZTR(ZeroTRee). J'ai choisi un codage équilibré : POS -> 00 , NEG -> 01 , IZ -> 10 ZTR -> 11. Alors qu'eux ont choisit un codage plus "entropique" qui suppose qu'il y a plus de noeuds ZTR que d'autres noeuds, et que parmi les noeuds restants, il y a plus de noeuds IZ que d'autres noeuds. Ce codage est : POS -> 0111 NEG -> 011, IZ -> 01 ZTR -> 0.


Deuxième variante

J'ai changé, dans l'algorithme initial des chercheurs, la normalisation des vecteurs de la base de Haar lors de la transformation en ondelettes. (Il y a deux types de normalisations qui ont un sens dans la base de Haar : j'ai donc choisi celle qu'il n'avait pas choisie..)

Résultat

Dans les deux cas, la version des chercheurs s'est montré bien plus performante.

EBCOT

J'ai implémenté une version approximative de MATLAB, mais je n'ai malheureusement pas pu aller plus loin(je n'ai pas fait de test poussés ni testé de variantes) car l'algorithme est d'une grande complexité, et j'ai donc eu juste le temps de le finir avant la soutenance


Conclusion

Les buts du TER ont été partiellement remplis, car si les algorithmes ont été compris, l'implémentation de l'algorithme EBCOT était trop approximative et n'a pas pu être bien testé, mais je prévois de l'améliorer dans les mois qui viennent, car il n'existe pas, à l'heure actuelle, sur INTERNET, de programmes MATLAB qui implémente EBCOT (c'est dû à l'extreme complexité de l'algorithme).


Documents additionnels