gdje je xi pojedini događaj, a P(xi) vjerojatnost tog događaja.
To znači da bi u idealnom slučaju srednja duljina lsr dobivenog koda
gdje je di duljina koda dobivena za pojedini događaj, trebala biti jednaka entropiji H(x).
U PNG formatu postoji mogućnost izbora metode sažimanja, no sadašnjom specifikacijom definirana je samo metoda 0. Autori navode da neće definirati slijedeću metodu dok se ne postigne poboljšanje od barem 50%.
PNG metoda kompresije 0 vrši negubitno sažimanje, uzastopnom primjenom tri metode koje se primjenjuju slijedećim redom: filtriranje, LZ77 te Huffmanovo (optimalno) kodiranje.
Već LZ77 kombiniran sa Huffmanom daje deklariranih 5% - 20% poboljšanja u odnosu na patentiranu LZW metodu koja se koristi u GIFu, a kada je slika 'pogodna', filtriranje je jednostavno 'pojede': true color slika sa otprilike 64000 boja (iz alpha channel primjera) u PNG zapisu ima 3564 By, dok u GIF zapisu sa smanjenim brojem boja (GIF ne podržava 24-bitnu paletu), dakle sa gubicima, ima 35 KB. U ovom radikalnom primjeru PNG je bolji i od gubitnog JPEGa koji daje 24KB s primjetnim gubicima !
Dakle ova metoda sažimanja daje odlične rezultate s obzirom na postavljeni cilj (zamjena i proširenje GIF formata zapisa) a pored toga je i nepatentirana.
U usporedbi s danas aktualnim matematičkim metodama (BTPC, BWT, wawelets, aritmetičko kodiranje ...), dakle metodama koje su se 'dokazale' u 5 godina nakon definicije metode 0, PNG metoda kompresije lošija je prosjeku za 30%. No kako se u iščekivanju JPEG2000 formata nijedna nova metoda nije 'etablirala' kao novi format, tako je PNG trenutno ponajbolji izbor za negubitno sažimanje.
Huffmanovo kodiranje spada u statističke metode sažimanja podataka (poznate i kao metode nejednolikog kodiranja), gdje se događaji, tj. informacije kodiraju nizovima bitova različitih duljina u skladu s frekvencijom odnosno vjerojatnošću njihova pojavljivanja. Ono je uvijek završni način sažimanja s kojim se podaci dobiveni nekom drugom metodom zapišu na najkraći mogući način.
Shannon je dokazao da je najmanja moguća prosječna duljina bitova potrebna da se pokaže neka informacija jednaka entropiji tog sustava informacija:
gdje je xi pojedini događaj, a P(xi) vjerojatnost tog događaja.
To znači da bi u idealnom slučaju srednja duljina lsr dobivenog koda
gdje je di duljina koda dobivena za pojedini događaj, trebala biti jednaka entropiji H(x).
D. A. Huffman je ovaj jednostavan algoritam stvorio 1952 g. !! Algoritam daje rezultate koji se približavaju vrijednosti entropije, to više što je broj događaja veći a vjerojatnost pojedinih događaja različitija.
Postavimo primjer s 5 događaja.
1. Korak
Događaje poredamo po padajućoj vjerojatnosti:
|
|
2. Korak
Sada odaberemo dva događaja najmanje vjerojatnosti i spojimo ih u jedan događaj čija je vjerojatnost jednaka zbroju pojedinih vjerojatnosti. Svakom pojedinom događaju od upravo grupiranih, dodajemo jedan bit koda, s lijeve strane, s time da događaju koji ima veću vjerojatnost ili je na višem položaju (ako su vjerojatnosti iste) dodjeljujemo uvijek istu vrijednost (bilo 0 ili 1, u primjeru 1).
|
|
3. Korak
Ponavljamo 2. korak dok ne ostane samo jedna vrijednost:
|
|
|
|
|
|
Za zadani primjer prirodnim kodiranjem dobili bi srednju duljinu koda od 3 bita. Huffmanovom metodom dobili smo kod srednje duljine 1,7 bita, samo 5% lošije od entropije (1,617 bita), najboljeg teoretski mogućeg rezultata.
Ovo je osnovni, izvorni Huffmanov algoritam. Vrlo sličan mu je Shannon-Fano algoritam. Danas se koriste razrađeniji algoritmi koji osim što poboljšavaju stupanja sažimanja (rekurzivna metoda) omogućavaju i izradu optimalnih tablica u jednom prolazu (adaptivna metoda), dakle bez poznavanja statističkih vrijednosti vjerojatnosti samih informacija prije početka kodiranja. Vrhunac novih metoda je aritmetičko kodiranje koje daje praktički entropijske vrijednosti (no ne može se dekodirati Huffmanovim dekoderom specificiranim PNG standardom). Osim navedenih postoji još niz drugih statističkih metoda, sa svojim prednostima i manama.
Na piscu programa za sažimanje je da upotrebi optimalan algoritam.
Bla bla bla bla bla !uočavamo prvo ponavljanje
Bla bla bla bla bla !
^^^^
Sada bi početak niza mogli kodirati kao
Bla b[D=4,L=4]uz minimalnu uštedu. No ako malo detaljnije pogledamo uočićemo da se niz u stvari stalno ponavlja i uz malo umjetničke slobode (dozvolićemo da se niz kodira kao ponavljanje iako u izlaznom kodu (još) nije definiran) uočavamo pravu snagu ovakvog kodiranja:
Bla b[D=4, L=15]!Sada je očito da se na ovaj način može efikasno kodirati ponavljanje kako jednog znaka (događaja, informacije) tako i uzorka (niza) znakova. Naravno, da bi se postiglo optimalno sažimanje potrebno je još upotrijebiti bolji način kodiranja referenci na podatke nego što je npr. '[D=4, L=15]'. Jedan od optimalnijih mogućih načina definiran je u LZSS metodi.
Filtriranje je prvi korak u PNG metodi 0. Ono prikazuje podatke u najredundantnijem obliku koji omogućava bolje sažimanje u LZ77 i Huffman metodama. Pretpostavimo da imamo niz podataka
123,124,125,126,127,128,129,130,131,132U ovom obliku to je niz od 10 različitih podataka koji naizgled ne omogućava nikakvo sažimanje. No ako podatke prikazujemo kao razliku vrijednosti podatka i njegovog prethodnika taj isti niz možemo prikazati kao
123,1,1,1,1,1,1,1,1,1i sada mogućnost sažimanja postaje očita. Ova metoda naziva se filtriranje.
U PNG formatu postoji mogućnost izbora metode filtriranja, a trenutno je definirana samo metoda 0 koja se sastoji od 5 osnovnih tipova filtara:
| Tip | Ime |
| 0 | None |
| 1 | Sub |
| 2 | Up |
| 3 | Average |
| 4 | Paeth |
Enkoder (program za sažimanje) odlučuje koji će filtar upotrijebiti za koji red u slici zavisno od toga koji će omogućiti najbolje sažimanje. Za svaki red u slici pojedinačno definira se koji se filtar koristi. Nažalost, filtri imaju različite učinkovitosti na različitim tipovima podataka, tako da je čest slučaj da filter ne može pomoći u sažimanju.
Tip filtra 0: None
Označava da se filtar ne koristi, jer ne pridonosi optimizaciji sažimanja
Tip filtra 1: Sub
Filtar prenosi razliku između susjednih podataka u istom redu. Može se primijeniti formula:
podatak(x) = red_u_kojem_jesmo(x) - red_u_kojem_jesmo(x-1)
Tip filtra 2: Up
Slično kao i u prethodnom filtru, prenosi se razlika između susjednih podataka ali između redova, a ne slijeda podataka:
podatak(x) = red_u_kojem_jesmo(x) - red_iznad(x)
Tip filtra 3: Average
Ovaj filtar koristi aritmetičku sredinu susjednih točaka (gornje i lijeve) da predvidi vrijednost točke:
podatak(x) = red_u_kojem_jesmo(x) - (red_iznad(x) + red_u_kojem_jesmo(x-1))/2
Tip filtra 4: Paeth
Ovu metodu izmislio je Alan W. Paeth. Računa se jednostavna linearna funkcija tri susjedne točke (lijeve, gornje lijeve i gornje) i zatim se kao prethodnik u odnosu na koji će se računati vrijednost bira ona točka čija je vrijednost najbliža vrijednosti funkcije:
podatak(x) = red_u_kojem_jesmo(x) - PaethIzbor(red_iznad(x), red_iznad(x-1), red_u_kojem_jesmo(x-1))
Funkciju možemo prikazati slijedećim pseudokodom:
int PaethPredictor (a, b, c)
{ p = a + b + c;
if ( (abs(p - a) > abs(p - b)) && (abs(p - a) > abs(p - c)) )
return a;
if (abs(p - b) > abs(p - b))
return b;
else
return c;
}
Paeth filtar davati će u prosjeku najbolje rezultate.
Linkovi na stranice koje se bave metodama sažimanja:
Sadržaj |
Što je to PNG ? |
Mogućnosti i karakteristike |
Specifikacija zapisa |
Algoritam za sažimanje |
Komentar |
Linkovi
