3.3 Algorithme
L'algorithme peut être divisé en deux parties :
une tache principale (aussi passage dominant) qui constitue le fond de tache du
codeur, et une partie secondaire ou subalterne qui est plus pour le raffinement
de la reconstruction de l'image pendant le décodage.
3.3.1 Traitement principal
Comme initialisation de l'algorithme, on choisit le seuil de
départ, pour le « bitplane coding », le seuil de départ
est défini par [17] :
t log max ,
[ ( im ( x y ) ) ]
= 2 3.1
2
0
40
Compression d'images animée par codage EZW 3D
Chapitre 3 Codage EZW
Où im(x, y) désigne
les coefficients d'ondelettes, x et y étant leur position dans
l'espace.
Le symbole « Max » correspond à la valeur
maximale de tous les coefficients de la représentation en ondelettes de
l'image. Ce seuil, comme le montre la définition, est un multiple de
deux, en fait c'est la puissance de deux la plus proche (inférieur ou
égale) du maximum des coefficients de l'image Cette puissance fera
partie par la suite du paquet d'informations transmis pour initialiser le
décodage, cette partie sera développée plus en
détail dans la description du protocole du codec EZW.
La matrice de coefficients est parcourue par l'une des
méthodes suivantes :
« Raster scan » ou «
Morton scan » (figure 3.2). Ces méthodes
de parcours ont été choisies de manière a préserver
l'ordre d'importance des coefficients traités, ainsi, pour les deux
types, on commence par parcourir les coefficients de basse fréquence, et
on avance graduellement vers les détails (hautes fréquences ), la
différence entre elles est la façon avec laquelle est parcourue
une même sous bande .La figure 3.2 illustre l'ordre de
parcours des coefficients pour les deux méthodes sur une matrice issue
de transformée en ondelette à trois niveaux de
décomposition .
41 -
Compression d'images animée par codage EZW 3D
Chapitre 3 Codage EZW
Chacun des coefficients parcourus est comparé (en valeur
absolue) au seuil t0, si le
coefficient est supérieur au seuil il est codé
' Positif ' ou ' Négatif ', sinon il est soit ' Zéro isole ' ou
bien ' Zerotree', on se ramène ainsi de X (selon niveaux de gris,
résolution de l'image...) symboles à coder a un dictionnaire de
quatre symboles :
· Positif (P) : indique que la valeur
absolue du coefficient traité est supérieure au seuil et que son
signe est positif.
· Négatif (N) : indique que la
valeur absolue du coefficient traité est supérieure au seuil et
que son signe est négatif.
42 -
.
Figure 3.2 : Méthodes de parcours des
coefficients
Morton scan
Raster scan
Compression d'images animée par codage EZW 3D
Chapitre 3 Codage EZW
· Zéro isolé (Z) :
indique que la valeur absolue du coefficient traité est
inférieure au seuil et qu'il existe parmi ses descendants (selon
l'arborescence présentée dans la Figure 3.1)
ceux qui sont signifiant (c'est à dire supérieurs au seuil).
· Zerotree (ZTR) : indique que la
valeur absolue du coefficient traité est insignifiante par rapport au
seuil considéré ainsi que tous les coefficients qui lui
succèdent dans l'arbre de descendance.
Après le parcours de tous les coefficients, le seuil
est divisé par deux, et l'opération est refaite selon le nouveau
seuil, cette méthode est appelée 'quantification par
approximations
successives' et peut être refaite tant que le seuil t
n , est supérieur ou égal à 1 , sachant
que :
t n = tn-1 /2 3.2
3.3.2 Traitement secondaire
Le traitement secondaire (passage subalterne) sert à
faire du raffinement sur les valeurs des coefficients, ainsi, après
chaque passage dominant, chaque coefficient codé ' Positif ou
Négatif ' subit une autre comparaison sur un autre seuil t
qui est proportionnel au seuil du passage dominant n
t = 2 . [17]
= +
2 n
t n
|
2 2
n 1 n
+-
|
3.3
|
|
|
Ceci peut être ramené à :
tn 3.4
= n
3 * 2 - 1
Où n est la puissance du seuil du passage dominant.
Ce passage secondaire permet au décodeur dans le cas
d'une compression avec pertes d'informations, d'avoir plus de précision
sur la valeur du coefficient codé, certes, la reconstruction ne sera pas
parfaite, mais, elle sera de loin meilleure que si on ne code qu'avec le
passage dominant.
43 -
Compression d'images animée par codage EZW 3D
Chapitre 3 Codage EZW
Dans le cas où l'on veut effectuer une compression sans
pertes d'informations, le passage subalterne devient inutile.
3.3.3 Protocole de codage
Pour que le codage soit parfait, un protocole entre codeur et
décodeur est établi, ainsi, le décodeur doit
connaître le dictionnaire de codage (dans ce cas les 4 symboles
utilisés au codage), et le type de parcours des coefficients
effectués (Raster ou Morton scan). Pour sa part, le codeur doit
transmettre au moins le seuil de départ, de préférence la
puissance associée à ce seuil (une puissance de deux puisque le
codage est bitplane), et le nombre de niveaux de décomposition par
ondelettes. On peut aussi trouver dans certains cas une condition d'arrêt
si l'on effectue une compression sans pertes d'informations.
3.3.4 Décodage
En premier lieu, le décodeur crée une matrice
de dimension égale à l'image traitée à partir du
nombre de niveaux de décomposition, ensuite, comme le codeur, il calcule
le premier seuil dont la puissance lui a été transmise. Le
parcours de la matrice 'image' commence alors et selon les symboles lus par le
décodeur un traitement est effectué :
· Si le symbole est 'Positif ' (P), la valeur du seuil est
additionné au contenu de la case en cours.
· Si le symbole est 'Négatif (N), Le seuil est
retranché du coefficient parcouru.
· Si le symbole est 'Zerotree' (ZTR), tout l'arbre
associé à ce coefficient sera ignoré par rapport au seuil
courant.
· Si le symbole est 'Zero isolé' (Z) : cela veut
dire qu'il existe au moins un coefficient appartenant à l'arborescence
du coefficient étudié qui est signifiant par rapport au seuil
courant d'où, aucun coefficient ne sera ignore dans cette
arborescence.
A la fin du parcours, le seuil est divisé par deux et
l'algorithme reprend. Si le seuil atteint la valeur 1, la reconstruction ne
sera parfaite sans aucune perte, mais au cas où l'on désire
arrêter avant le décodage idéal, on peut avoir recours au
traitement secondaire qui permettra plus de précision au niveau de la
compression avec pertes d'informations.
Le principe général de la méthode est
illustré par l'organigramme suivant :
44 -
Compression d'images animée par codage EZW 3D
Chapitre 3 Codage EZW
Coefficients de l'image
Figure 3.3 : Test de signifiance des
coefficients
Oui
Pas de sortie
Non
Oui
Pas de sortie
Non
Non
Oui
+
-
Sortie « Zi »
Ajoutez à la liste
Subordonnées
Quel
signe ?
Oui Non
Précédemment
Significatif
Significatif ?
A des
descendants
significatifs
Descend de
la racine de
zerotree
Sortie « P »
|
|
Sortie « N »
|
|
Sortie « Zt »
|
|
|
|
|
|
|
|
|
|
|
|
|
45 -
Compression d'images animée par codage EZW 3D
Chapitre 3 Codage EZW
| 
