C H A P I T R E 3
Codage EZW
3.1 Introduction
3.2 Présentation du codage EZW
3.3 Algorithme
3.6 Conclusion
3.1 Introduction
La transformée en ondelette permet, comme décrit
dans le chapitre précédent, de représenter les images sous
forme de coefficients ordonnes en bandes de fréquences. Pour la
compression d'images, la transformée représente le premier
maillon de la chaîne, afin de compresser l'information, il faut
compléter le cycle par la quantification et le codage.
Afin de garder le coté progressif de la transformée
en ondelettes, une méthode d'organisation et de quantification des
coefficients s'impose : c'est le EZW.
La méthode de codage progressif connue sous le nom de
Embedded Zerotree Wavelet coding (EZW), proposée par Shapiro [17], est
une méthode simple et très efficace de compression d'image par
ondelettes. Elle a démontré sa puissance dans les deux formes de
compression (avec et sans perte d'informations) depuis son élaboration
en 1993. Plusieurs variantes de ce type de codage ont été
proposé par différents chercheurs dans le domaine, ce qui fait sa
force .On peut citer par exemple le SPIHT (Set Partitionning in Hierarehical
Tree) réalisé par A. SAID et W.PEARLMAN [18] qui est la variante
la plus populaire de I'EZW. L'intérêt de consacrer ce chapitre
à cette méthode est de la mettre en évidence vu qu'elle
sera à la base des algorithmes proposés dans notre travail.
3.2 Présentation du codage EZW
En général, dans une représentation d'image
par coefficients d'ondelettes, l'image obtenue est organisée de
façon à représenter les principaux traits de l'image dans
les bandes
37 -
Compression d'images animée par codage EZW 3D
Chapitre 3 Codage EZW
de basse fréquence, puis les détails dans les
bandes de haute fréquence. Le principe de 1'EZW s'appuie sur cette
représentation, pour coder les coefficients d'une manière
progressive. Ainsi, on commence par les basses fréquences L, ensuite on
code les détails (hautes fréquences), l'avantage de cet
algorithme, est que l'on a en tout temps un niveau de compression et que l'on
peut arrêter en tout moment le codage.
Le codage EZW est basé sur deux principales observations
:
· Quand une image est transformée par ondelettes,
l'énergie dans les sous-bandes diminue pendant que l'échelle
diminue (la basse échelle signifie la haute résolution). Ainsi
les coefficients d'ondelette seront plus petits en moyenne dans les sous-bandes
plus hautes que dans les sous-bandes inférieures. Ceci prouve que le
codage progressif est un choix très normal pour des images
transformées par ondelettes, puisque les sous-bandes plus hautes
ajoutent seulement les détails fins.
· Les grands coefficients d'ondelette sont plus
importants que les plus petits.
Ces deux observations sont exploitées en codant les
coefficients d'ondelettes par ordre décroissant, dans plusieurs
passages. Pour chaque passage on choisit un seuil par rapport auquel tous les
coefficients d'ondelettes sont comparés. Si un coefficient d'ondelette
est supérieur au seuil, il est codé et retiré de l'image,
sinon, il est laissé pour le prochain passage. Quand tous les
coefficients d'ondelettes ont été examinés, le seuil est
abaissé et l'image est rebalayée pour ajouter plus de
détails à l'image déjà codée. Ce processus
est répété jusqu'à ce que tous les coefficients
d'ondelettes soient encodés complètement ou qu'un autre
critère soit satisfait (PSNR choisit est atteint) selon le mode de
compression utilisé.
L'algorithme emploie la dépendance entre les
coefficients d'ondelettes à travers différentes échelles
pour coder efficacement les grandes parties de l'image qui sont au dessous du
seuil actuel, c'est ici qu'intervient le zerotree.
Dans la représentation de « l'image ondelettes
», chaque coefficient peut être considéré en tant
qu'ayant quatre descendants dans la prochaine plus haute sous-bande figure
3.1). Ainsi que pour les quatre descendants, chacun à également
quatre fils dans la prochaine
38 -
Compression d'images animée par codage EZW 3D
Chapitre 3 Codage EZW
plus haute sous-bande et nous voyons un arbre à quatre
descendants émerger ; chaque racine a quatre branches, ce processus se
poursuit jusqu'aux fréquences les plus hautes.
Figure 3.1 : Représentation de
l'organisation en arbre des coefficients d'ondelettes
Nous pouvons maintenant donner une définition du
zerotree. Un zerotree est un quadruple-arbre dont tous les noeuds enfants sont
égaux ou plus petits que les noeuds parents. L'arbre est codé
avec un symbole unique et reconstruit par le décodeur comme
quadruple-arbre rempli de zéros. Nous devons insister sur le fait que la
racine doit être plus petite que le seuil par rapport auquel les
coefficients d'ondelettes sont comparés, sinon, ce coefficient ne serait
pas considéré comme base de zerotree.
Le codeur d'EZW exploite le fait qu'il y 'a une
probabilité très élevée que tous
les
coefficients dans un arbre quadruple soient plus petits qu'un certain
seuil si la racine de cet
arbre est plus petite que ce seuil. Ceci
entraîne alors un seul code zerotree pour tout l'arbre.
39 -
Compression d'images animée par codage EZW 3D
Chapitre 3 Codage EZW
Ceci dit, en balayant toute la représentation des
coefficients d'ondelettes, des basses aux hautes fréquences, on aura
automatiquement beaucoup de zerotree ce qui constituera un gain
considérable au niveau de la compression.
Une bonne approche est d'utiliser un seuil et seulement un
signal au décodeur si les valeurs sont plus grandes ou plus petites que
le seuil. Si nous transmettons également le seuil au décodeur, il
peut reconstruire une bonne partie de l'image. Pour arriver à une
reconstruction parfaite, on doit cependant répéter le processus
après abaissement du seuil, jusqu'à ce que le seuil devienne
inférieur au plus petit coefficient que nous avons voulu transmettre.
Nous pouvons rendre ce processus beaucoup plus efficace par la soustraction du
seuil du coefficient d'ondelette qui lui était supérieur. Le
choix des seuils peut être optimisé en considérant un lien
entre eux, si l'ordre prédéterminé est un ordre des
puissances de deux, le codage est appelé codage « bitplane »,
puisque les seuils correspondent dans ce cas-ci aux bits dans la
représentation binaire des coefficients. Le codage d'EZW tel que
décrit dans [17] utilise ce type de seuils.
L'information additionnelle minimale exigée par le
décodeur, outre le code des coefficients signifiants, est le nombre de
niveaux de transformées d'ondelettes utilisés et le seuil
initial. Si on retranche le coefficient après son codage, il est
nécessaire d'envoyer aussi la valeur moyenne de l'image, ça
permet une meilleure reconstruction et l'obtention d'un meilleur PSNR.
| 
