6

5. JPEG NORMA

ENTROPIJSKO KODIRANJE

Entropijsko kodiranje

Pojam entropije detaljno je objašnjen u drugom poglavlju. Entropijsko kodiranje je dodatan postupak kompresije bez unošenja gubitaka. Ovaj postupak efikasnije kodira kvantizirane DCT koeficijente različite od nule. Analiziranjem izraza (2.4) može se vidjeti da koeficijenti veće vjerojatnosti nose manje korisnu informaciju. Za svaki koeficijent dovoljno je bitova. Za sve koeficijente u bloku u prosjeku je dovoljno bita/koeficijentu. je funkcija gustoće vjerojatnosti (pdf-probability density function), a definirana je izrazom (2.3).

Na slici 5.13 prikazan je histogram distribucije amplitude DCT koeficijenata bloka iz tipične prirodne slike [2]. Uočljivo je da je DC koeficijent uniformno distribuiran. AC koeficijenti nisu uniformno distribuirani i njihova distribucija sliči na Laplacovu distribuciju.

Slika 5.13. Distribucija DCT koeficijenata

Ukoliko kvantizirani DCT koeficijenti nemaju uniformnu distribuciju onda je njihova entropija manja od N. Stoga mora postojati kod koji koristi manje od N bitova po koeficijentu. Može se zaključiti da što su vjerojatnosti pojavljivanja vrijednosti koeficijenata veće, to je prosječno potrebno manje bitova za njihov prikaz. Na tome se temelji entropijsko kodiranje. JPEG norma rabi Huffmanovo kodiranje i aritmetičko kodiranje.

Huffmanovo kodiranje

Algoritam je razvio 1952.g. David Huffman za tekstualne datoteke, a do danas je doživio mnoge promjene. Huffmanovo kodiranje [8] koristi kodne tablice koje mora poznavati koder i dekoder. Tablice su ulazni parametar, a mogu se koristiti standardne ili se proračunavaju na slijedeći način. Za danu sliku u postupku JPEG kompresije provodi se statistička analiza slike. Računa se frekvencija odnosno vjerojatnost pojavljivanja svih kvantiziranih DCT koeficijenata. Vjerojatnosti pojavljivanja se pohranjuju u pomoćni memorijski spremnik. Zatim se Huffmanovim algoritmom računa minimalan broj bitova za svaki kvantizirani DCT koeficijent različit od nule. Koeficijenti koji se češće pojavljuju nose manje korisne informacije i kodiraju se s manje bitova, dok se oni s manjom vjerojatnošću pojavljivanja kodiraju s većim brojem bitova. Na taj način se svakom koeficijentu pridjeljuje njegov kod zapisan u kodnoj, Huffmanovoj tablici. Na prijamnoj strani odnosno u dekoderu mora postojati ista Huffmanova tablica radi ispravnog dekodiranja.

Da bi se prikazao rad Huffmanova algoritma, potrebno je objasniti strukturu koja se naziva stablo, a prikazana je na slici 5.14.

Slika 5.14. Struktura stabla

Na vrhu stabla se nalazi osnovni čvor koji se zove korijen (root). On se dijeli na makismalno dva čvora koji se nazivaju djeca. Svaki daljni čvor može imati maksimalno dvoje djece. Dubina stabla jednaka je maksimalnoj razini nekog čvora u stablu, s time da je razina korijena jednaka 1. Kod Huffmanovog kodiranja stablo se popunjava od djece. To znači da do završetka Huffmanovog algoritma nije moguće znati strukturu stabla.

Huffmanov algoritam glasi:

Vjerojatnosti pojavljivanja koeficijenata poredati po veličini od manje prema najvećoj, te ih smatrati djecom stabla.
Dok se ne dođe do korijena stabla formirati roditelja od dva čvora s najmanjim vjerojatnostima. Novonastali čvor ima vjerojatnost jednaka zbroju vjerojatnosti svoje djece. Granama koje spajaju djecu i roditelje dodijeliti proizvoljno binarni znak 0 ili 1.
Nakon formiranja stabla kod za pojedini koeficijent sastaviti od simbola 0 i 1 pridjeljenih granama, idući od korijena do krajnjeg dijeteta.

Slijedi primjer [8] na kojem će se objasniti rad Huffmanovog algoritma. Radi jedostavnosti pretpostavimo slijedeći niz podataka koji se nalazi na ulazu u Huffmanov koder:

1 1 1 1 2 3 4 5 5 5 6 6 7 7 7 8

Frekvencija pojavljivanja znakova je slijedeća: Znak 1 pojavio se 4 puta, znakovi 2, 3, 4, 8 po jednom, znakovi 5 i 7 su se pojavili po tri puta, znak 6 dva puta.

Frekvencijama pojavljivanja pojedinih znakova pridružene su slijedeće vjerojatnosti:

Algoritam kaže da se uzmu dva znaka s najmanjim vjerojatnostima koji će dati svog roditelja. U ovom primjeru uzet će se znak 2 i 3 čija je vjerojatnost jednaka i iznosi 0.0625. Vjerojatnost njihovih roditelja je jednaka zbroju vjerojatnosti znaka 2 i 3 i iznosi 0.125. Stablo do sad ima tri čvora prema slici 5.15.

Slika 5.15. Prvi korak Huffmanovog algoritma

Slijedeći znakovi s najmanjim vjerojatnostima su 4 i 8. Slučajno u ovom primjeru imaju istu vjerojatnost kao i prethodni znakovi pa se nalaze na istoj razini budućeg stabla. Do sada je formirano 6 čvorova prema slici 5.16.

Slika 5.16. Drugi korak Huffmanovog algoritma

Sličnim razmatranjem se dolazi do slijedeće razine stabla prema slici 5.17.

Slika 5.17. Treći korak u Huffmanovom algoritmu

Postupak se ponavlja dok se sve vjerojatnosti ne uzmu u obzir i formira stablo prikazano na slici 5.18. Kada je stablo formirano očitava se Huffmanov kod. Kod se sastoji od 0 i 1 pridjeljenih granama koje povezuju čvorove, s time da se očitavanje provodi od korijena do odgovarajućeg čvora koji sadrži pripadajuću vjerojatnost. Rezultati Huffmanovog algoritma za ovaj primjer prikazani su u tablici 5.8.

Slika 5.18. Konačan izgled stabla

Prednosti Huffmanovog algoritma:

Jednostavnost implementacije i brzina.
Provodi kompresiju bez gubitaka.

Nedostaci Huffmanova algoritma:

Efikasnost ovisi o statističkoj prirodi slike.
Huffmanovo kodiranje je vremenski spor proces jer se odvija u dva koraka. Prvo je potrebno napraviti statističku analizu slike, a onda se pristupa procesu kodiranja. Ovaj nedostatak ne postoji kad se koriste gotove Huffmanove tablice.
Kodovi kodiranog niza podataka su različite duljine što dekoderu otežava detekciju zadnjeg bita pojedinog koda. Ukoliko negdje dođe do pogreške, u dekoderu će nastati rekonstruirana slika koja je neuporabljiva.

Tablica 5.8. Primjer izračunatog Huffmanovog koda

Znak	Vjerojatnost znaka	Huffmanov kod
1	0.25	01
2	0.0625	1001
3	0.0625	1000
4	0.0625	1010
5	0.1875	110
6	0.125	111
7	0.1875	00
8	0.0625	1011

Aritmetičko kodiranje

Aritmetičko kodiranje [8] je također postupak entropijskog kodiranja bez unošenja gubitaka. Kao i Huffmanovo kodiranje, temelji se na statističkoj analizi slike, ali postiže bolje rezultate. Aritmetičko kodiranje određuje vjerojatnosti pojavljivanja pojedinih diskretnih vrijednosti elemenata slike. Sve izračunate vjerojatnosti prikazuju se na jediničnoj dužini. Princip kodiranja je prikazan na primjeru koji slijedi.

Radi jednostavnosti, pretpostavimo da slika ima 2500 elemenata slike i da elementi slike mogu poprimiti bilo koju vrijednost iz skupa .

Neka je statističkom analizom ustanovljena slijedeća frekvencija ponavljanja vrijednosti elemenata slike [8]:

A : 200, B : 300, C : 100, D : 300, E : 300, F : 500, G : 600, H : 200,

Vjerojatnosti pojavljivanja su slijedeće:

P(A) = 0.08, P(B) : 0.12, P(C) : 0.04, P(D) : 0.12,

P(E) : 0.12, P(F) : 0.2, P(G) : 0.24, P(H) : 0.08,

Slika. 5.19. Aritmetičko kodiranje

Svaka vjerojatnost se predstavlja jednom vrijednošću iz odgovarajućeg intervala. U primjeru na slici 5.19. vrijednost 0.30 leži u intervalu 0.24 - 0.36 koji označava vjerojatnost pojavljivanja simbola D. Dakle sve vjerojatnosti iz ovog intervala su predstavljene pomoću vrijednosti 0.30. Moguće je više vjerojatnosti prikazati nekom vrijednošću. Na slici 5.19. u raspon označen strelicom G, «utisnuti» su rasponi svih vjerojatnosti. Vrijednost D je sada prikazana s proračunatom vjerojatnošću 0.7545. Dubina dijeljenja odnosno duljina niza povećava broj potrebnih bitova za prikaz izračunate vjerojatnosti, pa je taj postupak ograničen mogućnostima programske podrške.

Prikazanim postupkom zapravo se raspon vjerojatnosti od 0 do 1, komprimira na puno manji raspon čime se provodi smanjenje broja potrebnih bitova. Vrijednosti elemenata slike koji imaju manju vjerojatnost pojavljivanja kodiraju se većom preciznošću i obrnuto.

Prednosti aritmetičkog kodiranja:

Bolja metoda od Huffmanove jer je u mogućnosti vrijednosti koje imaju veću vjerojatnost pojavljivanja kodirati s manje bitova nego što to radi Huffmanov algoritam.
Ostvaruje i do 10% veću kompresiju uz omjer kompresije i do 100:1.

Nedostatak:

Algoritam je patentiran i ukoliko se želi koristiti potrebno je otkupiti licencu. Huffmanov algoritam je besplatan.

ÛKodiranje duljine niza

MENTOR:

Prof.dr.sc.Sonja Grgić

Û prethodno poglavlje Û

Ü slijedeće poglavlje Ü

Autor:

Mihael Jančić