Na podstawie “Embedded Image Coding Using Zerotrees of Wavelet Coefficients”,

J.M. Shapiro

Stosuje siê tu pojêcie transformaty wavelet zamiast pasmowej dekompozycji poniewa¿ ka¿dy

wspó³czynnik waveletowej transformaty jest indywidualnie i deterministycznie porównywany z tym
samym zbiorem progów, aby oceniæ jego znaczenie. St¹d ka¿dy wspó³czynnik jest traktowany jako

istotna (distinct), potencjalnie wa¿na czêœæ danych w odniesieniu do rozwa¿anej skali obrazu i ¿adne

obliczenia statystyczne dla danego pasma nie s¹ stosowane. W wyniku tego ma³a liczba
deterministycznie znacz¹cych wspó³czynników okreœlonej skali nie jest ignorowana ze wzglêdu jej

statystycznie nieistotne wartoœci.

LH1

HH1

HL1

LL3

Rys. 1. Oznaczenie pasm w drzewie transformaty wavelet obrazu.

Skrótowy opis algorytmu

Rozwa¿any jest wa¿ny aspekt kodowania pozycji tych wspó³czynników transformaty, które bêd¹

transmitowane czy zapisywane jako niezerowe. Stosuj¹c skalarn¹ kwantyzacjê i kodowanie entropijne,

w celu uzyskania du¿ej efektywnoœci kompresji prawdopodobieñstwo najczêœciej wystêpuj¹cego
symbolu alfabetu (po kwantyzacji jest to wartoœæ zero) musi byæ bardzo du¿a. W typowych

rozwi¹zaniach du¿¹ czêœæ nowej reprezentacji danych zawiera zakodowana mapa znaczeñ

(significance map) opisuj¹cych kolejne pozycje dwuwymiarowej mapy obrazu jako zerowe lub

niezerowe. Powoduje to, ¿e znacz¹ce zmniejszenie d³ugoœci kodu tej mapy pozwala na znaczne

zwiêkszenie efektywnoœci kompresji.

W wielu technikach kompresji wykorzystuj¹cych liniowe transformacje, a nastêpnie skalarn¹

kwantyzacjê i kodowanie takie

A. Kodowanie mapy znaczeñ (Significance Map Encoding)

Podstawowe okreœlenia:

Waveletowy wspó³czynnik jest nieznacz¹cy wzglêdem pewnego progu T, jeœli |x|<T. W

przeciwnym przypadku wspó³czynnik jest znacz¹cy.

Wspó³czynnik wy¿szego poziomu drzewa dekompozycji (o mniejszej skali) nazywany jest

rodzicem, a odpowiadaj¹ce mu wspó³czynniki na kolejnym poziomie o wy¿szej skali – dzieæmi,

natomiast na jeszcze wy¿szych poziomach – potomkami. Przodkami s¹ wszystkie wspó³czynniki le¿¹ce
odpowiednio na wy¿szych poziomach w stosunku do danego wspó³czynnika, powy¿ej rodzica.

Wspó³czynnik x jest nazywany elementem drzewa zer dla danego progu T, jeœli on sam i

wszystkie jego wspó³czynniki potomne s¹ nieznacz¹ce.

Element drzewa zer dla progu T jest korzeniem drzewa zer jeœli jeœli nie jest potomkiem

poprzednio poprzednio znalezionego korzenia drzewa zer, czyli nie jest przewidywalnie nieznacz¹cy z
punktu widzenia poprzednio znalezionego korzenia drzewa zer w mniejszej skali przy tym samym T.

Korzeñ drzewa zer jest kodowany przy pomocy specjalnego symbolu, wskazuj¹cego ¿e wszyscy jego

potomkowie s¹ nieznacz¹cy.

Mapa znaczeñ opisuj¹ca drzewo dekompozycji obrazu opisana jest wiêc alfabetem o czterech

symbolach:

1) korzeñ drzewa,

2) izolowane zero, czyli wspó³czynnik nieznacz¹cy posiadaj¹cy wœród potomków wspó³czynnik

znacz¹cy,

3) znacz¹cy dodatni

4) znacz¹cy ujemny

Dla wspó³czynników pasma najni¿szych czêstotliwoœci oraz najwiêkszej skali (nie maj¹cych dzieci),
rezerwuje siê alfabet jedynie trójelementowy: nieznacz¹cy, znacz¹cy dodatni i ujemny.

B. Kwantyzacja sukcesywnej aproksymacji i entropijnego kodowania

Metoda sukcesywnej aproksymacji (SAQ) kolejno u¿ywa wartoœci progów z sekwencji

1

0

,....,

−

N

T

T

aby

okreœliæ znaczenie wspó³czynników, gdzie progi s¹ dobrane nastêpuj¹co:

2

/

1

−

=

i

i

T

T

. Pocz¹tkowa

wartoϾ progu

0

T

jest dobrana nastêpuj¹co:

0

2

|

|

T

x

j

<

dla wszystkich wspó³czynników transformaty

j

x

.

Podczas kodowania (dekodowania), dwie oddzielne listy wspó³czynników musz¹ byæ

pamiêtane. W ka¿dym momencie lista dominuj¹ca (dominant) zawiera wspó³rzêdne tych

wspó³czynników, które jeszcze nie okaza³y siê znacz¹ce wed³ug ustalonej kolejnoœci przegl¹dania
(kolejne pasma od najni¿szych do najwy¿szych czêstotliwoœci oraz wspó³czynniki w pasmach jak na rys.

1). Druga lista, zwana zale¿n¹ (subordinate) zawiera wartoœci tych wspó³czynników, które okaza³y siê

znacz¹ce. Dla kolejnych wartoœci progu ka¿da z list jest przegl¹dana raz. Podczas dominuj¹cego
przegl¹du wspó³czynniki z listy dominuj¹cej s¹ porównywane z progiem

i

T

w celu okreœlenia ich

znaczenia i ewentualnie znaku. Ta lista nastêpnie jako mapa znaczeñ jest kodowana w sposób opisany

wy¿ej. Za ka¿dym razem kiedy wspó³czynnik jest okreœlony jako znacz¹cy, jego wartoœæ bezwzglêdna

jest dopisywana do listy zale¿nej, a wspó³czynnik ten w tablicy wartoœci waveletowych wspó³czynników

jest zerowany. Przegl¹d zale¿ny nastêpuje zaraz po przegl¹dzie dominuj¹cym. Polega on na

doprecyzowaniu wartoœci wspó³czynników dla dekodera o kolejny bit dok³adnoœci. Dla kolejnych
wspó³czynników to doprecyzowanie wartoœci mo¿e byæ kodowane binarnie. Poprzednia wartoœæ progu

wyznacza jednoczeœnie przedzia³ niepewnoœci wpisanych wartoœci. Zmniejszona o po³owê wartoœæ

progu powoduje dookreœlenie tych wartoœci z dwukrotnie mniejszym poziomem niepewnoœci. Czyli jeœli
rzeczywista wartoœæ wpada w górn¹ po³ówkê starego przedzia³u niepewnoœci, wówczas kodowana jest

‘1’, a gdy w doln¹ – ‘0’. Ci¹g binarnych symboli po takim przegl¹dzie jest nastêpnie entropijnie

kodowany, a doprecyzowane wartoœci na podrzêdnej liœcie s¹ sortowane w kolejnoœci malej¹cej, co jest

mo¿liwe do powtórzenia tak¿e w dekoderze.

Te dwa przegl¹dy s¹ naprzemiennie powtarzane z kolejnymi, malej¹cymi wartoœciami progów.
Dekoduj¹c wspó³czynniki podczas kolejnych przegl¹dów dominuj¹cego i zale¿nego

doprecyzowuje siê ich wartoœæ zmniejszaj¹c przedzia³ niepewnoœci, w którym rzeczywiste wartoœci

wspó³czynników mog¹ siê pojawiæ. Zrekonstruowana wartoœæ mo¿e byæ dowoln¹ w ostatnim przedziale

niepewnoœci. Stosuje siê tu ró¿ne rozwi¹zania, np. dla minimalizacji b³êdu œredniokwadratowego mo¿na

u¿yæ metodê centroidu z za³o¿onym modelem funkcji gêstoœci prawdopodobieñstwa lub te¿ optymaln¹

w sensie MINMAX metodê œrodka przedzia³y niepewnoœci (takie rozwi¹zanie zastosowa³ Shapiro).

Proces kodowania koñczy siê, gdy wyczerpuje siê za³o¿ony na skompresowan¹ reprezentacjê

limit bitów.

C. Hierarchia wa¿noœci bitów

1. Numeryczna precyzja wartoœci wspó³czynników, okreœlona przez próg (przedzia³ niepewnoœci.

2. Wartoœæ wspó³czynników okreœlona z dok³adnoœci¹ do ostatniego przedzia³u niepewnoœci.

3. Skala czyli za³o¿ona kolejnoœæ kodowania pasm wielorozdzielczej analizy obrazu – od najni¿szych

czêstotliwoœci (najmniejszej skali) do pasm wysokoczêstotliwoœciowych (najwiêkszej skali).

4. Po³o¿enie w przestrzeni okreœlone przez kolejnoœæ skalowania wspó³czynników danego pasma w

czasie przegl¹du dominuj¹cego.

Przyk³ad

Rozwa¿my prosty przyk³ad trójpoziomowej (o trzech skalach) waveletowej transformacji obrazu o

rozmiarach

8

8

×

. Uzyskane wartoœci wspó³czynników pokazane s¹ w tabeli poni¿ej

63

-34

49

10

7

13

-12

7

-31

23

14

-13

3

4

6

-1

15

14

3

-12

5

-7

3

9

-9

-7

-14

8

4

-2

3

2

-5

9

-1

47

4

6

-2

2

3

0

-3

2

3

-2

0

4

2

-3

6

-4

3

6

3

6

5

11

5

6

0

3

-4

4

Poniewa¿ najwiêksza wartoœæ wspó³czynnika wynosi 63, jako pocz¹tkow¹ wartoœæ progu mo¿emy
przyj¹æ dowoln¹ wartoœæ z przedzia³u (31.5,63]. Przyjmujemy wiêc

0

T

= 32.

Tabela poni¿ej obrazuje pierwszy przegl¹d dominuj¹cy z wartoœci¹ progu równ¹ 32. Oznaczania s¹

nastêpuj¹ce:

POZ – znacz¹cy dodatni, NEG – znacz¹cy ujemny, IZ – izolowane zero, KDR – korzeñ drzewa, Z –

zero zamiast IZ i KDR na poziomie 1.

Komentarz

Pasmo

WartoϾ

wspó³czynnika

Symbol

WartoϾ

rekonstruowana

(1)

LL3

63

POZ

48

HL3

-34

NEG

-48

(2)

LH3

-31

IZ

0

(3)

HH3

23

KDR

0

HL2

49

POZ

48

(4)

HL2

10

KDR

0

HL2

14

KDR

0

HL2

-13

KDR

0

LH2

15

KDR

0

(5)

LH2

14

IZ

0

LH2

-9

KDR

0

LH2

-7

KDR

0

(6)

HL1

7

Z

0

HL1

13

Z

0

HL1

3

Z

0

HL1

4

Z

0

LH1

-1

Z

0

(7)

LH1

47

POZ

48

LH1

-3

Z

0

LH1

-2

Z

0

Natomiast pierwszy zale¿ny przegl¹d pokazuje nastêpna tabela:

Wielkoœæ wspó³czynnika

Symbol

WielkoϾ zrekonstruowana

63

1

56

34

0

40

49

1

56

47

0

40

Na koñcu kolejnoœæ tych wielkoœci zostaje zmieniona na (63,49,34,47) wed³ug informacji

dostarczanej dla dekodera.

Nastêpny przegl¹d dominuj¹cy przeprowadzany jest z progiem 16. Teraz jedynie wspó³czynniki

dot¹d nieznacz¹ce s¹ skanowane. Ponadto wspó³czynniki ju¿ okreœlone jako znacz¹ce s¹ traktowane

jako zero przy szukaniu korzeni drzewa zer. Tak wiêc w drugim dominuj¹cym przegl¹dzie kodowane s¹:

-31 z LH3 jako NEG, 23 z pasma HH3 jako POZ, wszystkie wspó³czynniki z HL2 oraz LH2 s¹ KDR.

Przegl¹d koñczy siê w momencie, gdy pozosta³e do przejrzenia wspó³czynniki s¹ przewidywane jako
nieznacz¹ce.

Drugi przegl¹d listy zale¿nej zawieraj¹cej teraz szeœæ elementów (63,49,34,47,31,23) dotyczy

trzech przedzia³ów niepewnoœci: [48,64), [32,48) oraz [16,31), ka¿dy o szerokoœci 16. Doprecyzowanie
ka¿dej wielkoœci polega na okreœleniu dla ka¿dego z tych przedzia³ów dwóch nowych przedzia³ów

niepewnoœci. Na koñcu tego przegl¹du kolejnoœæ wielkoœci wspó³czynników jest nastêpuj¹ca

(63,49,47,34,31,23).Odpowiadaj¹ im zrekonstruowane wartoœci (60,52,44,36,28,20). Kodowanie jest

dalej kontynuowane poprzez naprzemienne przegl¹danie nadrzêdne i zale¿ne wspó³czynników i mo¿e

byæ zatrzymane w dowolnym czasie.