Sve algoritme kompresije podataka mozemo svrstati u dve kategorije: kompresija bez gubitaka i kompresija sa gubicima. Kod kompresije bez gubitaka dobija se fajl koji će posle dekompresije biti identičan originalu. Kompresija sa gubicima zrtvuje neke podatke u fajlu, tako da se po dekompresiji dobija fajl koji nije jednak originalu. Razlike, međutim, obično nisu vidljive za ljudsko oko.
Tehnike kompresije sa gubicima daleko moćnije komprimuju podatke - komprimovani fajlovi su obično, u odnosu fajlove komprimovane nekom tehnikom kompresije bez gubitaka, i po nekoliko puta manji. Najpoznatija tehnika kompresije slika sa gubicima je JPEG.
JPEG grafički format je standardizovan krajem osamdesetih i ubrzo je postao popularan za distribuciju rasterskih slika. Osnovni problem sa digitalnim slikama jeste njihova veličina: npr. ako su dimenzije slike u pixelima 640*480, a dubina 16 ili 24 bita po pikselu (fotorealističan kvalitet) => za jednu sliku je potrebno 900 KB.
Ali, kod rasterske grafike, digitalne slike smeštene u matrici piksela su zapravo struktura pogodna za kompresiju, pošto su susedni pikseli često identični ili se razlikuju za male vrednosti. Većina standardnih formata za rastersku grafiku (npr. GIF, PNG) podrzava metode kompresije bez gubitaka, koji su najčešće neka varijacija run-lenght kodiranja. Prednost ovakvih metoda je što su kompresija i dekompresija jednostavne i brze, ali se njima ne postize puni nivo kompresije, koji je inače moguć. Na primee, run-lenght kodiranjem koristi samo sličnost piksela po horizontali (horizontalna koherencija), a ne i po vertikali.
Kod JPEG kompresije je primenjena aproksimacija originalne rasterske slike koja će posmatraču izgledati istovetno, ali koja će moći da se komprimuje mnogo efikasnije od uobičajene LZW kompresije, na primer za red veličine. Pošto je svaka rasterska slika zapravo niz piksela ili (u krajnjoj instanci) niz brojeva, moze se posmatrati kao digitalni signal i na nju primeniti metod za obradu digitalnih signala.
Furijeova transformacija je osnovni alat za obradu analognih signala.
Francuski matematičar Zozef Furije (Joseph Fourier) je 1807. godine otkrio da se, sasvim pojednostavljeno, svaka periodična funkcija moze predstaviti superponiranjem sinusne i kosinusne funkcije. Na neperiodične funkcije mozemo u određenom intervalu takođe primeniti Furijeovu transformaciju.
Signali u realnom svetu najčešće nisu periodični, ali u većini slučajeva nas zanima samo određeni vremenski interval, pa onda mozemo reći da je upravo taj interval jednak trajanju jedne periode signala, a da je izvan njega signal koga posmatramo periodičan. Dakle, Furijeovom transformacijom se signal prebacuje iz vremenskog u frekventni domen i Furijeovi koeficijenti određuju amplitude pojedinih frekvencija signala. Postoji i inverzna Furijeova transformacija, koja određuje amplitude signala u vremenskom domenu, na osnovu vrednosti koeficijenata signala u frekventnom domenu.
Digitalni signal se dobija semplovanjem ("odabiranjem") analognog signala sa određenom učestanošću semplovanja. Ovo znači da se kontinualni signal predstavlja nizom vrednosti (semplova odnosno odbiraka), koje je imao u određenim trenucima, gde broj semplova u jedinici vremena predstavlja učestanost semplovanja. Pandan Furijeovoj transformaciji analognog signala je diskretna Furijeova transformacija (DFT) digitalnog signala. DFT daje vrednosti amplituda signala na tačno određenim, dakle diskretnim, učestanostima u frekventnom domenu.
Slično vazi i za diskretne vrednosti digitalnih signala na koje primenjujemo diskretnu Furijeovu ili diskretnu kosinusnu transformaciju. Matematički model rasterske slike pruza osnovu za njenu obradu na računarima.
Osnovni koraci JPEG algoritma su
direktna diskretna kosinusna transformacija (FDCT)
kvantizacija
kodiranje entropije
JPEG algoritam posmatra sliku kao niz blokova od 8*8 piksela. Intenzitet u svakom pikselu je prostorna funkcija od dve promenljive - x i y. Ako je svaki piksel slike predstavljen sa P bitova, onda će se numerička vrednost intenziteta kretati u rasponu od 0 do 2P-1. JPEG algoritam ove vrednosti ne posmatra kao neoznačene, već kao označene (signed) brojeve (u opsegu od -2P-1 do 2P-1-1). Tako se štedi bit po DCT koeficijentu.
1. korak FDCT
Jednačina koja daje vrednosti koeficijenata direktne diskretne kosinusne transformacije (FDCT) za polje 8*8 semplova ima oblik
gde je C(u)=C(v)=1/sqrt(2) za u,v=0 i C(u)=C(v)=1 u suprotnom. Jednačina inverzne DCT (IDCT, f(x,y)) daje vrednosti signala u funkciji prostornih koordinata x i y, ako su poznati koeficijenti njegove diskretne kosinusne transformacije.
Dakle, direktna diskretna kosinusna transformacija na ulazu prima diskretni signal intenziteta u 64 tačke, da bi na izlazu dala niz od 64 koeficijenta, koji odgovaraju dvodimenzionim prostornim frekvencijama. Prvi koeficijent odgovara srednjoj vrednosti intenziteta u bloku 8*8 semplova i označava se kao DC koeficijent, dok se 63 preostala zovu AC koeficijentima. Kako se intenzitet prostorno sporo menja, većina AC koeficijenata ima vrednosti bliske 0. Vidimo po formuli za f(x,y) da diskretna kosinusna transformacija je reverzibilna: na osnovu vrednosti 64 koeficijenta mogu se pomoću IDCT tačno rekonstruisati polazne vrednosti intenziteta u 64 tačke (do na tačnost kosinusa, jer se kosinus, kao i druge trigonometrijske funkcije, moze odrediti samo sa konačnom preciznošću ). Dakle, DCT nije izvor gubitaka informacija prilikom kompresije.
korak KVANTIZACIJA
Kvantizacija predstavlja osnovni uzrok gubitaka pri kompresiji.
Nakon obavljene FDCT transformacije, pristupa se kvantizaciji koeficijenata. Oni bi, zbog mnozenja sa kosinusima, trebalo da budu predstavljeni float brojevima, ali ljudsko oko nije u stanju da razlikuje male promene, pa se za svaki od DCT koeficijenata određuje korak kvantizacije, koji mora biti u opsegu od 1 do 255, potom se vrednosti koeficijenata podele sa odgovarajućim korakom kvantizacije, a onda zaokruze na ceo broj. Na ovaj način se dobija niz koeficijenata DCT u kome figurišu mali celi brojevi i u kome ima veliki broj koeficijenata jednak 0, što je sve povoljno za treći korak kompresije - kodiranje entropije, jer osnovna ideja JPEG algoritma je: slika se predstavlja u frekventnom domenu, gde će imati malo komponenti različitih od 0 i onda će se bolje komprimovati - kodiranje je efikasnije ako treba komprimovati nizove sa uzastopnim identičnim elementima.
Što se tiče izbora koraka kvantizacije, on je za svaki od 64 koeficijenta prilozen kao predlog uz JPEG standard. Zato što u toku izrade standarda izvršen je veliki broj testova za svaki od DCT koeficijenata. Testovi su se odvijali tako što se na jednoj slici vrednost datog koeficijenta inkrementirala u koracima po 1, a polazna i novodobijena slika su stalno vizuelno upoređivane. Onog trenutka kada bi razlika postala uočljiva, vrednost koraka kvantizacije za dati koeficijent bi se definisala kao prethodni inkrement, dakle kao najveći inkrement za koji vizuelna razlika još uvek nije uočljiva. Prilikom testiranja su korišćene slike raznolikog sadrzaja, koje su, opet, posmatrane sa različitih distanci. Prilikom implementacije JPEG algoritma se mogu koristiti ove vrednosti ili se, ako je u pitanju neka specifična aplikacija, mogu sprovesti sopstveni testovi i koristiti njima dobijene vrednosti koraka kvantizacije.
Kvantizacija predstvlja osnovni uzrok gubitaka pri kompresiji, jer ako uzmemo veće korake kvantizacije, koeficijenti će biti predstavljeni nizim vrednostima, a takođe će biti veći broj koeficijenata jednakih 0. Ovo daje veći stepen kompresije pri kodiranju entropije, ali će zato razlike između originalne i dekomprimovane slike biti uočljivije.
Treći i poslednji deo kompresije je kodiranje entropije i pri ovom postupku DC koeficijenti se tretiraju odvojeno od AC koeficijenata: DC koeficijent predstavlja srednju vrednost intenziteta u polju od 8*8 semplova i prirodno je da se DC koeficijenti susednih blokova ne razlikuju mnogo. Da bi se i ova činjenica iskoristila za što veću kompresiju, DC koeficijenti se ne beleze po apsolutnoj vrednosti, već kao razlika u odnosu na DC koeficijent prethodnog 8*8 bloka. AC koeficijenti se potom preuređuju u niz po rastućim prostornim frekvencijama. Ovaj niz, prema tome, ima oblik F(0,1), F(1,0), F(2,0), F(1,1), F(0,2), i tako dalje, i često se naziva "cik-cak" sekvencom.
U prvoj fazi se, "cik-cak" sekvenca koeficijenata se prevodi u jednu međusekvencu u kojoj se nulti AC koeficijenti kodiraju duzinom niza uzastopnih nultih koeficijenata.Međusekvenca za DC koeficijente se formira na sličan način.
Na ovako pripremljenu međusekvencu primenjuje se već poznato Hafmanovo kodiranje.
Svaku sliku komprimovanu JPEG algoritmom mora, dakle, da prati i look-up tabela sa Hafmanovim kodovima, koji se mogu proračunati za svaku sliku prilikom kompresije ili se moze koristiti opšti skup Hafmanovih tabela, dobijen statističkom analizom velikog broja slika, tipičnih za datu aplikaciju.
Prilikom dekompresije postupak je obrnut: raspakivanje podataka, te primena inverzne diskretne kosinusne transformacije na blokove piksela, objedinjavanje tri kanala boja i konverzija ovog kolornog prostora u RGB. Poslednja operacija čini JPEG neprikladnim za CMYK i Hexachrome separacije, kao i slike sa alfa kanalima. Firme koje proizvode grafički softver su, nezavisno od JPEG komiteta, izabrale najnuznije opcije iz specifikacije i napravile de facto JPEG standard, kao podskup oficijelnog standarda. Proširenje je obuhvatilo podršku za CMYK.
JPEG 2000
Tokom devedesetih Wavelet funkcije su napredovale, pa je Wavelet kompresija izbila u prvi plan, pošto se mogu efikasno oblikovati da bi opisali sliku. Ono što ih čini uspešnijim u odnosu na metod primenjen u JPEG kompresiji jeste njihova sposobnost da se prilagode dimenzijama i lokaciji područja na rasterskoj slici. Dok DCT funkcioniše u blokovima od 8×8 piksela, Wavelet-i opisuju područja različite veličine, oblika i lokacije. Čitav postupak se naziva diskretna Wavelet transformacija (DWT). U prvoj fazi JPEG2000 kompresije kolorni kanali se „rasparčavaju” u blokove, koji nemaju veze sa blokovima od 8×8 piksela koje koristi standardni JPEG i mogu da budu proizvoljne veličine, tako da pokrivaju čitav kolorni kanal ili samo neke njegove delove.
Svaki blok se potom dekomponuje uzastopnom primenom Wavelet transformacija. Bez obzira na to koja se Wavelet funkcija koristi, proces dekompozicije je identičan. U prvom prolazu Wavelet se skalira na veličinu celog bloka, a transformacijom se dobija broj koji opisuje koliko je podataka slike predstavljeno Wavelet-om. U uzastopnim prolazima, Wavelet i ostatak slike dele se na četvrtine, analiziraju i ponovo se dobijaju odgovarajući koeficijenti i ostatak detalja, ali je ovoga puta preciznost veća. Proces se moze ponavljati sve dok ostatak ne bude nula ili prekinuti u trenutku postizanja određenog kvaliteta.Koeficijenti se potom organizuju u pravougaone matrice koje se posmatraju kao nizovi bit-ravni. Svaka bit-ravan se zasebno komprimuje primenom algoritma entropijskog kodiranja (Elias kodiranje).
JPEG modifikacije
Prva verzija standarda je propustila da definiše format datoteka za komprimovane podatke. Nakon kratkog i konfuznog perioda, previd je ublazen nastankom JPEG File Interchange Format-a (JFIF). Današnja „JPEG datoteka” je skup bajtova definisanih JPEG metodom kompresije i upakovanih u JFIF format. JPEG standardom definisano je nekoliko modela kompresije u koje spadaju baseline, losless, progressive i hierarchical; jedini široko rasprostranjeni rezim je baseline, koji spada u algoritme sa gubicima (lossy). Kompresija bez gubitaka u okviru JPEG standarda koristi sasvim drugačiji pristup (predictive coding) i ona je uglavnom izostala iz praktične primene JPEG-a.
JPEG koristi nekoliko uspešnih trikova kako bi obezbedio visok stepen kompresije. Tehnika je zasnovana na zanimljivom aspektu vizuelne percepcije čoveka: male promene osvetljenja (luminanse) dozivljavamo mnogo jače nego male promene boje (hrominanse). JPEG kompresija ima tri osnovne faze: transformacija, kvantizacija i kodiranje. U prvoj fazi kolorni model slike se menja tako da se pikseli opisuju pomoću hrominanse i luminanse – 24-bitni RGB podaci se transformišu u YCrCb prostor. Y kanal sadrzi informacije o luminansi, a C kanali beleze boju duz osa crveno-zeleno i plavo-zuto. U sledećim koracima svaki od kanala se tretira zasebno, jer nije neophodno da se kanali kodiraju istom preciznošću. Zbog toga JPEG i jeste kompresija koja degradira sliku, pošto se ublazavaju kolorne varijacije originala. To je ujedno i najvazniji aspekt funkcionisanja JPEG tehnike.
JPEG svojstva
Naziv JPEG je skraćenica od Joint Photographics Experts Group (zajednička grupa fotografskih stručnjaka), što je naziv grupe koja je stvorila ovaj format.
Istini za volju, JPEG nije format, nego jedna vrlo moćna tehnika kompresije grafičkih podataka. U vreme nastajanja ove tehnike, iz nekih razloga nije standardizovan format koji je koristi. Tokom godina koje su sledile, pojavilo se više različitih formata koji su koristili JPEG
kompresiju. Posebno mesto među njima imaju JFIF i SPIFF.
JFIF (Ekstenzija: JPG; Kompresija: JPEG; Odrzava: C-Cube Microsystems)
SPIFF (Ekstenzija: JPG, SPF; Kompresija: bez kompresije, JPEG, JBIG, Modified Huffman, MR, MMR; Odrzava: ITU i ISO)
U nedostatku pravog standarda, kao de facto JPEG standard pojavio se JFIF (JPEG File Interchange Format), stvoren u C-Cube Microsystems. Nekoliko godina kasnije, u ISO komitetu je došlo do dogovora o standardu, i kao rezultat toga se pojavio SPIFF (Still Picture Interchange File Format). Očekivalo se da će, zahvaljujući mnogim poboljšanjima, uspeti da zameni JFIF format. Za sada u tome još nije uspeo. Tako i danas, kada govorimo o JPEG formatu, obično mislimo na JFIF fajl format (sa JPEG kompresijom).
JPEG kompresija je vrlo moćna kompresiona tehnika sa gubicima. U stanju je da bez (za ljudsko oko) vidljivih gubitaka u kvalitetu slike, smanji veličinu fajla na njen, recimo, dvadeseti deo. Ovo je, u odnosu na tehnike kompresije bez gubitaka, ogromna ušteda, jer se pri kompresiji slike bez gubitaka moze postići ušteda memorijskog prostora od jedva 50%. JPEG kompresija se bazira na diskretnoj kosinusnoj transformaciji (DCT). DCT kao metoda, sama po sebi ne pravi gubitke u podacima. Ustvari, tehnika kompresije podataka koja počiva na DCT aproksimira neke od koeficijenata da bi se postigla značajna ušteda.
JPEG koristi osobinu ljudskog oka da slabije uočava razlike u nijansama boje nego u intenzitetu svetlosti. Zato najbolje komprimuje fotografije u punoj boji. Slabije, ali ipak dosta dobro, pokazuje se kod slika u nijansama sive boje (nijanse sive su ustvari nijanse svetlosti!)
Najslabiji je kod jednostavnih crteza sa oštrim ivicama i kod teksta, gde se i pri manjem intenzitetu kompresije pojavljuju vidljivi defekti – artefakti.
Korisnik moze da se, u skladu sa namenom slike, opredeli za nivo kompresije. Što se za viši nivo kompresije opredelimo, fajlovi će biti manji, ali će i oštećenja slike biti veća. Osnovni problem u korišćenju JPEG kompresije lezi u činjenici da su oštećenja nastala pri kompresiji trajna, i da se pri višestrukim editovanja slike, gubici akumuliraju. Posle većeg broja sesija editovanja (dekompresija, editovanje, kompresija pri snimanju izmenjenog fajla), slika više neće dobro izgledati.
Nema editovanja bez gubitaka (čak ni rotacija za 90 ili 180 stepeni, flip horizontal i vertical i crop nisu operacije bez gubitaka). Zato nikada ne treba editovati JPEG slike. Edituje se original, koji se čuva u sirovom (nekomprimovanom) obliku, ili u formatu koji komprimuje bez gubitaka (kao što su TIFF ili BMP), a JPEG kopija se pravi od originala tek u poslednjem trenutku, kada hoćemo da napravimo mali fajl koji ćemo poslati preko mreze. JPEG slike se koriste kod velikih arhiva slika (u punoj boji ili u nijansama sive) i za prikaz na Web stranama. Zbog svoje male veličine (malog zauzeća memorijskog prostora), koriste se i u svrhu prethodnog prikaza.
Progresivni JPEG. Slično prepletenom GIF-u, progresivni JPEG se koristi da stvori utisak brzeg prikazivanja slike. Pomoću progresivnog JPEG-a, prvo će se prikazati slika niskog kvaliteta; u toku nekoliko koraka, ta slika postaje sve jasnija. Za razliku od GIF-ovog preplitanja, koje se realizuje red po red, progresivni prikaz JPEG je dvodimenzion.
JPEG format ne podrzava transparentnost, a verovatno je da to svojstvo JPEG slike ni u budućnosti neće imati. Ponekad se, ako zelimo da imitiramo
transparentnost, pristupa rešenju da se deo slike koji zelimo da izgleda transparentan, oboji bojom pozadine na kojoj će se slika nalaziti kada se bude prikazivala. Ako unapred ne znamo boju pozadine, ili ako pozadina nije jednobojna, moraćemo odustati ili od transparentnosti ili od JPEG-a (u ovom drugom slučaju, moraćemo koristiti format koji podrzava transparentnost – GIF ili PNG).
|
|
