(Pripremili: Milorad Cvjetković i Miran Slade-Šilović)

U današnje vrijeme sve su veći zahtjevi za prijenosom što veće količine podataka. To se pokušava realizirati hardware-skim rješenjima, koja ipak pomalo počinju dosezati svoje realne granice (ograničenja koja nameću same tehnološke mogućnosti), pa se pribjegava software-skim rješenjima, koja nastoje sliku sažeti na što manju veličinu, da bi se moglo prenijeti više slika u jedinici vremena, preko istog ograničenog prijenosnog sustava. Kompresijom podataka (slika) mogu se postići izvrsni rezultati, npr. slika dimenzija 1024 pixela x 1024 pixela x 24 bita, bez kompresije zauzima oko 3 MB memorijskog prostora i potrebno je oko 7 minuta za njen prijenos koristeći brzu 64 Kbit/s ISDN liniju, dok je za sliku kompresiranu u omjeru 10:1 potrebno 300 KB memorijskog prostora, a za njen prijenos je potrebno oko 30 sekundi. Prijenos velikih slikovnih datoteka predstavlja usko grlo distribuiranih sustava.

Postoje dvije vrste algoritama za kompresiju slike :

- bez gubitaka

Metode sa gubicima zasnivaju se na modelima ljudske percepcije (više kompresiraju one atribute slike koji manje doprinose ukupnom izgledu slike) , one uzrokuju degradaciju slike u svakom koraku (svakim slijedećim korakom kompresije/dekompresije slika se degradira) , ali najčešće omogućuju daleko veće omjere kompresije nego metode bez gubitaka.

Karakteristike : Lako se implementira, software-ski ili hardware-ski, vrlo je brzo, lako se provjerava, ali ima ograničene kompresijske mogućnosti.

Slika 1.Run-length kod

Ovaj algoritam je razvio D.A.Huffman i temelji se na činjenici da se neki znakovi pojavljuju češće nego neki drugi. Na toj osnovi algoritam izgrađuje težinsko binarno stablo (na osnovu frekvencije pojavljivanja pojedinih znakova). Svakom elementu tog stabla pridružuje se nova kodna riječ određena pozicijom znaka u stablu. Najčešće ponavljani znak postaje korjen stabla i njemu se pridružuje najkraća kodna riječ, dok kodna riječ najrjeđe ponavljanog znaka može biti i dvostruko duža od samog znaka.

Karakteristike : Omjer kompresije iznosi oko 1 : 2 za nekorelirane slike, za tipične slike omjer kompresije iznosi oko 1 : 1.2 do 1 : 2.5.

Slika 2. Huffmanovo kodiranje

Karakteristike : Omjer kompresije iznosi do 1 : 8 za prosječne GIF slike, relativno su problematični za implementaciju budući da sadrže tablice koje rastu s izvođenjem algoritma.

Slika 3.Kodiranje kodnom tablicom

To je poboljšana verzija run-length kodiranja koja iskorištava dvodimenzionalnu karakteristiku slika. Algoritam pokušava pronaći pravokutne regije jednakih karakteristika koje se zatim kodiraju u opisnoj formi kao elementi s dvije točke i određenom strukturom. Cijela slika treba biti opisana da bi se omogućilo dekodiranje bez gubitaka. Moguće performanse temelje se na vrlo kompleksnom problemu pronalaženja najvećih područja jednakih karakteristika.

Ove metode sastoje se od tri komponente :

• modeliranje slike (definicija transformacije koja se koristi)
• kvantizacija parametara (kvantizacija podataka dobivenih transformacijom)
• kodiranje

Kodiranje optimizira reprezentaciju informacija, te se može unijeti detekcija grešaka.

Slika dimenzija NxN se dijeli u manje blokove dimenzija nxn i na svakom od njih se primijenjuje unitarna transformacija. Cilj transformacije je da dekorelira originalni signal, što najčešće rezultira raspodjelom najvećeg dijela energije u nižim koeficijentima transformacije. Na taj način mnogi koeficijenti se mogu zanemariti nakon kvantizacije.

Cijeli proces može se svesti na četiri koraka :

• podjela slike
• transformiranje slike
• kvantizacija koeficijenata
• Huffman kodiranje

Transformacijsko kodiranje vrši se u dva koraka: segmentacija (podjela slike na dvodimenzionalne vektore), te transformiranje (primjena izabrane transformacije).

Naknadno se vrši kvantizacija koja se može provesti na više načina. Klasični pristupi su primjena ‘zonalnog kodiranja’, koje se sastoji od skalarne kvantizacije koeficijenata koji pripadaju predefiniranom području i primjena ‘kodiranja pragom’ kod kojeg se odbacuju koeficijenti čija apsolutna vrijednost prelazi neku unaprijed zadanu vrijednost praga. Postoji još jedna mogućnost, tzv. vektorska kvantizacija, koja omogućuje veće omjere kompresije. JPEG i MPEG algoritmi koriste transformacijsko kodiranje.

Vektor-kvantizator se može matematički definirati kao transformacijski operator koji transformira R-K prostor u konačan podskup X u R-K prostoru predstavljen sa N vektora. Taj podskup X postaje vektorska kodna knjiga.

Linde , Buzo i Graz su generalizirali metodu optimalnog skalarnog kvantizatora koju su predložili Lloyd i Max, a koja se temelji na iteraciji slijedećih jednostavnih koraka :

• podjela područja za treniranje u N grupa
• centroidi tih grupa postaju vektori u kodnoj knjizi
• proračunavanje srednje distorzije; ako je postotno smanjenje distorzije u usporedbi sa prethodnim korakom ispod određenog praga, onda se proces zaustavlja

Jednom kad je kodna knjiga generirana, kodiranje se sastoji u primjeni operatora na vektore originalne slike. U praksi svaka grupa od n pixela bit će kodirana kao adresa u vektorskoj kodnoj knjizi , tj. broj od 1 do N.

Ovim metodama slika se modelira kao mozaik regija, od kojih je svaka karakterizirana određenim stupnjem uniformnosti svojih pixela.

Klasični primjeri ovih metoda su polinomska aproksimacija i aproksimacija teksturama. Polinomska aproksimacija zasniva se na rekonstrukciji regija na osnovi srednjih vrijednosti polinomskih funkcija, dok se aproksimacija teksturama temelji na sintezi parametriziranih tekstura baziranih na nekom modelu.

Ovaj način kodiranja zasnovan je na opisu slike pomoću fraktala (njihovih parametara), dobar je za prirodne scene. U srednjim osamdesetim se započelo s proučavanjem ovih načina kodiranja, zabilježeni su izvrsni rezultati, omjeri kompresije oko 10000 : 1 i veći, ali problem je bio izrazito velika kompleksnost, te jako dugo vrijeme izvođenja takvih algoritama (za jednu sliku bilo je potrebno oko 100 sati rada na Cray-u), pa je njihova primjena za komercijalne svrhe bila neprihvatljiva. Tijekom godina ti algoritmi su unapređivani, tako da danas postoje njihove upotrebljive verzije, a radi se i na njihovoj implementaciji u hardware-ski oblik.

Performanse algoritama za kodiranje s gubicima se najčešće izražavaju preko dva faktora :

1. faktor kompresije
2. distorzija proizvedena nakon rekonstrukcije

Prvi faktor je objektivan, dok drugi uvelike ovisi o samom izboru slike.

U nastavku navedeni su neki od primjera standardiziranih formata za kompresiju slike u kojima se upotrebljavaju navedeni principi odnosno algoritmi.

JPEG (Joint Photographic Experts Group), ime dolazi izravno iz imena vijeća koje je sastavilo taj standard, a predstavlja način kompresije koji najbolje djeluje na slike s puno boja ili slike sastavljene od nivoa sive boje, koje prikazuju scene iz stvarnog svijeta. Dobar je za fotografije, ali nije baš uspješan pri kompresiji jednostavnih crtanih slika ili linija, ima problema s oštrim rubovima. Služi isključivo za kompresiju mirnih slika.

Napravljen je tako da koristi nesavršenosti ljudskog oka, odnosno činjenicu da se okom bolje primjećuju male razlike u svjetlini nego u boji. Ova činjenica može stvarati izvjesne probleme, ako slike obrađene na ovaj način ne analizira čovjek nego stroj.

Važno svojstvo JPEG metode je u mogućnosti traženja kompromisa između veličine slike i njene kvalitete. Za dobru kvalitetu, slike se ne mogu jako kompresirati, ali ako nam nije jako bitna kvaliteta možemo postići visok stupanj kompresije. Postoji još jedna važna činjenica vezana uz kvalitetu slike. Možemo birati između kvalitete slike i brzine dekodiranja, koristiti manje točne aproksimacije, ali zato jako brze i obrnuto.

Promatrajući slike iz stvarnog života JPEG gubi puno manje informacija nego GIF, koji predstavlja također jednu metodu kompresije slika. Jedini pravi nedostatak JPEG-a sastoji se od toga da svaki put kada kompresiramo i ponovo dekompresiramo sliku gubimo sve više informacija. Vrlo je važno ograničiti broj kompresija i dekompresija između početne i završne verzije slike. Postoje neke operacije, rotacija za 90° , koje se mogu izvesti, uz neka ograničenja u veličini slike, bez dekompresije slike.

JPEG može osigurati kompresiju 20:1 sa svim bojama bez vidljivih gubitaka informacija. Ne kompresirani podaci su veličine 24 bita po pixelu. Kompresija od 30:1 do 50:1 moguća je uz manje i srednje gubitke dok je, za primjene u kojima nije jako važna kvaliteta, moguće postići kompresiju i 100:1.

Osnovni JPEG format sprema se kao jedan prijelaz preko slike od vrha do dna. PROGRESIVNI JPEG podijeljen je u nekoliko prijelaza preko slike. Prvi prijelaz daje sliku vrlo loše kvalitete, ali zauzima vrlo malo mjesta, slijedeći postupno poboljšavaju kvalitetu slike. Prednost ovog načina je u tome, što se slika može vidjeti odmah nakon prijenosa, u početku lošije kvalitete, ali s vremenom kako stižu novi podaci kvaliteta se popravlja. Ovaj način našao je svoju primjenu kroz popularnost World Wide Web-a i njegovih pretraživača, koji rade sa sporim modemskim vezama.

LOSSLESS JPEG je potpuno drugačiji princip od osnovnog JPEG-a, a najznačajnija prednost mu je garancija istovjetnosti svih bitova deompresirane i originalne slike. Može izvršiti kompresiju podataka sa svim bojama u omjeru 2:1, a upotrebljiv je isključivo na slike s kontinuiranim prijelazima boja.

Danas postoji i novi stanadard nazvan JPEG-LS koji omogućuje veći nivo kompresije, također bez gubitaka, ali je još uvijek puno lošiji, po omjeru originalne i kompresirane slike, od osnovnog JPEG-a.

MPEG je standard za kompresiju pomićnih slika odnosno videa ("motion picture compression"). Upotrebljava slične tehnike kao JPEG. Koristi se činjenicom da su slike, koje slijede jedna za drugom, a dio su nekog videa, u mnogočemu slične. Nedostaci se sastoje u prvom redu u tome što je potrebno puno proračuna za generiranje kompresirane sekvence, vrlo je teško editirati MPEG sekvencu na razini pojedine sličice.

Vrlo često pojavljuje se M-JPEG, koji je vrlo popularan za editiranje videa, ali je problem što nije definiran kao standard.

X WINDOWS odličan za gledanje JPEG, GIF i dr. , može raditi konverzije između različitih formata, te neke jednostavnije transformacije sa slikama.

QPV je vrlo brz, ali se nešto gubi na kvaliteti slike, posebno kod slika sa 256 ili manje boja. Primjenjiv kod pretraživanja velikog broja slika.

SEA je novi program za gledanje i konverziju formata JPEG, PNG, GIF i dr., brži je od prethodnog. Može čitati i progresivne JPEG-ove.

DVPEG u nekim primjenama brz jednako kao i QPV, u nekim je sporiji, ali daje slike bolje kvalitete.

WinJPEG prikazuje i vrši konverziju JPEG, GIF, TIFF, BMP. Sadrži funkcije poput podešavanja boja i " slideshow-a ".

ACDsee je brz, dobar za JPEG, GIF, PNG , i dr. Nije moguće vršiti editiranje slika niti konverzije formata.

Photo shop 5.0 ima mogućnost prikaza progresivnog JPEG-a.

PIE posebno za korisnike digitalnih kamera, može rotirati slike u JPEG formatu bez gubitaka.