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.