Compression des images hyperspectrales
These en pdf
Annexe B
Exemples pour EZW et SPIHT
LES algorithmes EZW et SPIHT sont populaires et utilisés dans beaucoup de travaux, néanmoins, pour en comprendre les subtilités il est utile d’appliquer à la main ces algorithmes sur des données simples. Pour permettre de mieux comprendre ces deux algorithmes (décrits dans le chapitre 3 ainsi que dans [Sha93] et [Sai96]) et mettre en évidence leurs différences, on applique ici la première passe de ces deux algorithmes sur un exemple concret.
L’exemple original de l’article [Sha93] est appliqué également à SPIHT [Sai99]. Ces deux exemples sont repris ici sur les mêmes données (Fig. B.1) pour faciliter la compréhension des algorithmes. Rappelons que le codage est fait par plans de bits successifs.
B.1 Déroulement sur EZW
Pour EZW, rappelons également qu’un coefficient est déclaré significatif (symbole POS ou NEG suivant son signe) si sa valeur absolue est supérieure au seuil Tk du plan de bits. Sinon, soit il s’agit d’un zéro isolé (IZ) si au moins un de ses descendants est significatif, soit d’un arbre de zéros (ZTR) si aucun de ses descendants n’est significatif.
Le déroulement de l’algorithme EZW sur les données de la figure B.1 est décrit dans le tableau B.1. Quelques précisions sont données pour certaines étapes, les numéros correspondants sont données dans la dernière colonne du tableau B.1 :
- Le premier coefficient a la valeur 63, il est supérieur au seuil courant (32), le symbole POS est émis.
- -31 est non significatif, mais il possède un descendant qui est significatif (47) c’est un zéro isolé, IZ est émis.
- 23 est non significatif et tous ses descendants sont non significatifs, il s’agit donc d’un arbre de zéros, ZTR est émis.
- 7 est non significatif et comme la sous-bande HL1 n’a pas de descendant, les symboles IZ et ZTR peuvent être regroupés en un seul symbole Z.
- 47 est significatif, le symbole POS est émis. Comme ce symbole sera traité pendant la passe de raffinement, il pourra être considéré comme étant 0 pour les passes suivantes (le symbole 14 de la LH2 sera alors une racine d’un arbre de zéros).
|
En supposant que EZW utilise 2 bits pour coder les symboles POS, NEG, ZTR et IZ et 1 bit pour coder le symbole Z, on obtient un débit de 26+7=33 bits.
B.2 Déroulement sur SPIHT
L’algorithme SPIHT maintient trois listes de coefficients : la liste des coefficients
significatifs (List of Significant Pixels ou LSP), la liste des coefficients non
significatifs (List of Insignificant Pixels ou LIP) et la liste des ensembles non
significatifs (List of Insignificant Sets ou LIS). 
(x,y,λ) est l’ensemble des
enfants de (x,y,λ) (un seul niveau de descendance), 
(x,y,λ) est l’ensemble de
tous les descendants et 
(x,y,λ) = (x,y,λ) -(x,y,λ) est l’ensemble
des descendants à l’exception des enfants. La fonction Sk(x,y,λ) est
égale à 0 si tous les descendants de (x,y,λ) sont en dessous du seuil
Tk (arbre de zéros) et 1 dans le cas contraire. SPIHT considère deux
types d’arbres de zéros : le type A où tous les descendants ne sont pas
significatifs (arbre de degré 1) et le type B où tous les descendants, à
l’exception d’au moins un des enfants, ne sont pas significatifs (arbre de degré
2).
Le déroulement de l’algorithme SPIHT sur les données de la figure B.1 est décrit dans le tableau B.2. Quelques précisions sont données pour certaines étapes :
- Initialisation des listes : la LSP est vide, la LIP contient les 4 coefficients de plus basse fréquence et la LIS contient la même chose que la LIP à part le coefficient (0,0) (valeur 63) qui n’a pas de descendants.
- (0,0) qui a la valeur 63 est significatif, il est mis dans la LSP. Le signe de cette valeur est également émis, et noté +.
- Un des descendants de (1,0) est significatif (49) on teste donc les 4 enfants de (1,0).
- Comme un des enfants de (1,0) était significatif, il est changé de type (B) et mis à la fin de la LIS.
- Tous les descendants de (1,1) sont en dessous du seuil, on ne fait donc rien de particulier, on passe à l’élément suivant dans la LIS.
- (1,0) est de type B, on regarde donc (1,0) qui n’est pas significatif
- (0,1) est de type B, on regarde donc (0,1) qui est significatif (présence
de la valeur 47), on partage donc l’ensemble et on ajoute (0,2), (1,2),
(0,3), (1,3) à la fin de la LIS comme élément de type A et on enlève
(0,1) de la LIS.
- Comme (1,2) n’a pas de petits-enfants, au lieu de le passer en élément de type B comme on aurait du le faire, on le retire de la LIS.
- Ces listes constituent les listes d’entrées pour le passage suivant où le seuil sera de 16.
|
La taille de la sortie de cette première passe est de 29 bits.