6

6. JPEG2000 NORMA

EBCOT KODIRANJE

EBCOT i entropijsko kodiranje

EBCOT (Embedded Block Coding with Optimal Truncation) kodiranje [20] daje umetnuti tok podataka čime se omogućuje sukcesivno izoštravanje rekonstruirane slike sve dok se ne postigne puna kvaliteta s time da je moguće u svakom trenutku prekinuti prijam bitova, a da se slika još može rekonstruirati. Takav način kodiranja omogućuje progresivan prijenos i PSNR skalabilnost. EBCOT algoritam je vrlo sličan EZW (Embedded Zerotree Wavelet) i SPIHT (Set Partitioning in Hierarchical Trees) kodiranju. No EZW i SPIHT kodiranje imaju veliki nedostatak što vrše kodiranje potpojasa ovisno o korelaciji s drugim potpojasom. Time je povećana efikasnost kodiranja, ali ne postoji otpornost na pogreške u prijenosnom kanalu te fleksibilnost kodera u stvaranju kodiranog toka podataka. EBCOT vrši neovisno kodiranje potpojasa, a samo kodiranje se provodi u nekoliko koraka.

Prvo se svaki potpojas podijeli na pravokutne blokove koji se zovu kodirajući blokovi (eng. codeblock). Svaki takav kodirajući blok se neovisno kodira. Dimenzije kodirajućih blokova se određuju u koderu po želji. Jedino se mora ispuniti da visina svakog kodirajućeg bloka ne bude manja od 4 i da broj koeficijenata u kodirajućem bloku ne prijeđe 4096. Neovisno kodiranje kodirajućih blokova omogućuje slučajan pristup bilo kojem dijelu slike, paralelno kodiranje, otpornost na pogreške u prijenosnom kanalu, bolje upravljanje tokom podataka te maksimalnu fleksibilnost u kreiranju toka podataka.

Nakon što se svaki potpojas podijelio u kodirajuće blokove slijedi postupak njihova analiziranja, formiranja bitovnih ravnina koje se potom entropijski kodiraju. Zatim se svi kodirajući blokovi slažu u pakete, paketi u slojeve kvalitete, te se formira izlazni tok podataka. U narednom tekstu su objašnjeni ovi koraci.

Formiranje bitovnih ravnina

Svaki kodirajući blok u svakom potpojasu se promatra neovisno. Kvantizirani koeficijenti u pojedinom kodirajući bloku prikazani su bitovnim riječima koje se sastoje od bitova najveće važnosti MSB (Most Significant Bit) do bita najmanje važnosti (LSB- Least Significant Bit). Svaki koeficijent možemo zamisliti kao da je opisan jednodimenzijskim nizom bitova počevši od MSB-a do LSB-a. EBCOT algoritam omogućuje stvaranje umetnutog toka podataka formiranjem tzv. bitovnih ravnina (bitplanes). Bitovne ravnine se mogu promatrati kao jednodimenzijski nizovi različite važnosti od MSBP-a do LSBP-a. Prva bitovna ravnina sadrži po jedan najznačajniji bit od svakog koeficijenata u kodirajućem bloku. Slijedeća bitovna ravnina sadrži drugi najznačajniji bit. Posljednja ravnina sadrži samo najmanje značajne bitove svih koeficijenata u kodirajućem bloku. Svaka bitovna ravnina ima broj elemenata jednak broju koeficijenata u kodirajućem bloku, a broj bitovnih ravnina je jednak broju bitova potrebnih za prikaz pojedinog koeficijenta.

Na taj način se postigne umetnuti tok podataka jer se prvo kodira MSB ravnina, zatim prva manje značajna ravnina, a zadnja se kodira LSB ravnina. Kod progresivnog prijenosa dekoder prima prvo najznačajnije bitovne ravnine i on u «hodu» može rekonstruirati sliku. Pristizanjem manje značajnih bitovnih ravnina rekonstruirana slika je sve kvalitetnija. Ako se u koderu odluči odbaciti p bitovnih ravnina od ukupno B ravnina počevši od LSB ravnine, dekoder će rekonstruirati sliku manje kvalitete, ali ipak upotrebljivu za neke primjene.

Odbacivanje ravnina se može zamisliti kao da se radi umetnuta (embedded) kvantizacija s korakom kvantizacije , za , gdje je p cijeli broj. Neka je kvantizirani wavelet koeficijent prikazan s bitova gdje je . Ukoliko odbacimo najmanje značajnih bitova tada je broj bitova , pa se može pisati izraz za kvantizirani wavelet koeficijent:

(6.30)

gdje je uniformna skalarna kvantizacija s korakom kvantizacije . Dakle dekoder neće primiti LSB bitova, ali je rekonstrukcija slike moguća uz slabiju kvalitetu. Inverzna umetnuta kvantizacija prikazana je slijedećim izrazom:

(6.31)

Može se zaključiti da se za svaki rabi uniformna skalarna kvantizacija s korakom kvantizacije (slika 6.18) [19]. Širina mrtve zone je uvijek dvostruko veća od koraka kvantizacije. Ukoliko je p=0 tada se prenose svi bitovi potrebni za prikaz kvantiziranih wavelet koeficijenata.

Slika 6.18. Umetnuta (embedded) kvantizacija

Slično razmatranje se može provesti za uniformnu skalarnu kvantizaciju s promjenjivom širinom mrtve zone čime se dobije slijedeći izraz za rekonstruirani wavelet koeficijent:

(6.32)

No kod ove skalarne kvantizacije s promjenjivom širinom mrtve zone postoji ovisnost širine mrtve zone o broju odbačenih bitova prema izrazu:

(6.33)

Širina mrtve zone će biti različita za svaki , stoga je potrebno paziti na izbor koraka kvantizacije. Slijedi primjer na kojem će se vidjeti kako promjena broja odbačenih bitova utječe na korak kvantizacije u okviru umetnute kvantizacije.

Primjer 3 [12]:

Neka wavelet koeficijent ima vrijednost 83 i neka je korak kvantizacije . Tada je prema (6.24) kvantizirani wavelet koeficijent 27. Neka je 27 prikazan slijedećom 8 bitovnom riječju: 00011011.
Ako dekoder prima svih 8 bitovnih ravnina, tada rekonstruirana vrijednost prema (6.20), uz i iznosi 82.5.
Ako dekoder prima samo 6 bitovnih ravnina, dakle odbačena su zadnja 2 najmanje značajna bita, tada rekonstruirani koeficijent, uz , iznosi 78.
Ako se odbaci 4 najmanje značajne bita, tada je rekonstruirana vrijednost, uz, jednaka 72.

Promjenom vrijednosti dobila se skalabilnost PSNR-a odnosno progresivan prijenos po vršnom odnosu signal/šum. Dekoder vrši sukscesivno izoštravanje rekonstruirane slike.

Kodiranje bitovnih ravnina

Nakon kreiranja svih bitovnih ravnina u pojedinom kodirajućem bloku slijedi njihovo entropijsko kodiranje [9]. Entropijsko kodiranje se provodi kontekstualnim binarnim aritmetičkim koderom. Radi se o tzv. MQ koderu koji je jedna od modifikacija prvotnog Q kodera kojeg je razvio IBM. MQ koder se koristi u JBIG2 standardu. MQ koder je povoljan jer radi s bitovima, a ne byte-ima kao QM koder koji se koristi u JBIG standardu. Koder radi na načelu određivanja vjerojatnosti odnosno važnosti pojedinih koeficijenta. Vjerojatnost svakog koeficijenta je procjenjena iz konteksta susjednih 8 uzoraka. Svaka bitovna ravnina se kodira sa po tri prolaza (prenošenje važnosti - Significance Propagation, izoštravanje - Refinement, pročišćavanje - Cleanup), a taj postupak kodiranja se naziva kodiranje potbitovnih ravnina (Sub-bitplanes).

Iza svakog od tri prolaza moguće je prekinuti daljnje kodiranje umetanjem točke prekida (eng. truncation point) čime se postiže finija PSNR skalabilnost. Slika 6.19. pokazuje način očitavanja kvantiziranih koeficijenata u kodirajućem bloku. Uzimaju se u obzir četiri koeficijenta jedan ispod drugog, a onda se kreće na susjedni isti takav niz uzoraka. Visina kodirajućeg bloka mora biti najmanje četiri uzorka.

Slika 6.19. Očitavanje koeficijenata unutar kodirajućeg bloka

Ovakav način očitavanja se koristi za svaku bitovnu ravninu, za svaki potpojas, za svaku razinu dekompozicije. Kodiranje bitovnih ravnina uvijek počinje od MSB ravnine, koja se uvijek kodira trećim prolazom (pročišćavanjem) jer nema prethodne ravnine. Aritmetički koder proračunava važnost svakog koeficijenta pamteći njegovu lokaciju unutar kodirajućeg bloka. Svaka lokacija ima neku važnost ,na temelju koje koder provodi odabir u kojem će se od tri moguća koraka kodirati bitovna ravnina. Aritmetički koder u praktičnim primjenama daje 6% veću dužinu kodne riječi od pripadne idealne kodne riječi. MQ koder rabi tzv. kontekstualno određivanje važnosti lokacije pojedinog koeficijenta. Da bi odredio važnost nekog koeficijenta, koder uzima u obzir važnost lokacija susjednih osam koeficijenata.

ÛKvantizacija

Formiranje toka podatakaÜ

MENTOR:

Prof.dr.sc.Sonja Grgić

Û prethodno poglavlje Û

Ü slijedeće poglavlje Ü

Autor:

Mihael Jančić