UNIVERZITET U ZENICI



Algoritmi i formati za kompresiju slikeSulji? AldijanaRezime: Sa razvojem digitalne fotografije javila se mogu?nost pohranjivanja digitalne fotografije na vi?e razli?itih na?ina. Da bismo pohranili slike u ra?unar, sa velikim formatima, potrebno je slike kompresovati odnosno smanjiti fajl. Zato u ovom seminarskog radu cilj mi je da Vas upoznam sa pojmom kompresije slike, algoritmima za kompresiju slike, kao i vrstama formata za kompresiju slike. Klju?ne rije?i: kompresija, slika, algoritam, formati slike itd.UVODU dana?nje vrijeme sve su ve?i zahtjevi za prijenosom ?to ve?e koli?ine podataka. Kompresije podataka po?ele su ozbiljnije da se razvijaju osamdesetih godina pro?log vijeka, jer su tada memorija i disk bili strahovito skupi i mnogo se skupocjenog prostora tro?ilo na skladi?tenje podataka u razvijenom, tj. nekompresovanom obliku. Me?utim, koristi se ?injenica da podaci koje ljudi koriste sadr?e mnogo nepotrebnog vi?ka, a po teoriji informacija mo?e ta?no da se izra?una koliko taj vi?ak iznosi i da odbaci ono ?to je redundantno. Algoritmi kompresije zasnivaju se upravo na toj ?injenici. Po?etna faza kompresije istra?ivanja podataka uklju?uje 1838. godine usluge kori?tenja telegrafa, a to je ?Morse code“ prvi pristup kompresije podataka. Moderni rad kompresije podataka je po?eo u kasnim 1940. godinama sa razvojem teorije informacija. Claude E. Shannon je u svom radu iz 1948. godine ?Matemati?ka teorija komunikacije“ formulisao teroiju kompresije podataka. Originalno kompresija slike je po?ela 1970. godine gdje u osnovi dobijamo matemati?ke transformacije i kvantizacije sa tehnikama kodiranja. Zatim u 1980. godinama je razvijeno nekoliko shema kompresije. [1] Pa tako algoritmi kompresije se mogu podijeliti u dvije kategorije:-algoritmi kompresije bez gubitka podataka i -algoritmi kompresije sa gubitkom podataka.Kod kompresije bez gubitka dobija se fajl koji ?e poslije dekompresije biti identi?an originalu. Postoji jako mnogo algoritama, a dva koja se naj?e??e upotrebljavaju su Hofmanov kod i LZW (Lempel Ziv Welch) algoritam. Stepen kompresije koji se mo?e posti?i algoritmima bez gubitaka nije dovoljan za smje?tanje na disk i prenos digitalnog zvuka, slike i filma kroz komunikacione kanale. Kompresija sa gubitkom podataka je pogodna za podatke koji poti?u od digitalizovanih slika ili zvuka, jer je digitalna prezentacija ve? i sama samo aproksimacija.[1]Slika1.Kompresija-dekompresija podataka [2]KOMPRESIJA SLIKE Kompresija slike predstavlja umanjenje broja bitova grafi?ke datoteke (tj. slike) tako da se vrlo malo ili uop?te ne naru?ava kvaliteta slike. Kompresija nam omogu?ava da vi?e slika pohranimo na jednome mjestu, da ubrzamo prenos slika sa jednog medija na drugi ili smanjimo vrijeme u?itavanja slika na internetu. Postoji nekoliko razli?itih na?ina pomo?u kojih mo?emo kompromirati slike. Ovisno o namjeni biraju se i na?ini kompresije. [12] Za kori?tenje interneta uglavnom se koriste JPEG, GIF i PNG format dok se u 2010. godini poku?ava uvesti novi format WebP koji je razvila Google korporacija. JPEG se uglavnom koristi za fotografije dok se GIF koristi za crte?e, te pokretne fotografije tzv. animacije. Ukoliko postoji potreba za transparencijom tada koristimo PNG format koji ima tu mogu?nost. Postoji jo? tehnika i formata za kompresiju slika, ali gore navedene su najzastupljenije i prihva?ene kao svjetski standardi. Va?na karakteristika kompresije slika je da se mo?e izgubiti dio podataka, a da se to ne primjeti. Slika, prije svega, postoji radi ljudi te stoga kada se komprimira mo?e izgubiti dio podataka na koje ljudsko oko nije osjetljivo.Imamo dvije vrste kompresije slike i to:-kompresija sa gubitkom podataka (lossy) i - kompresija bez gubitka podataka (lossless). Bitmap grfi?ki program je ra?unarski program koji korisniku omogu?uje da slika ili ure?uje sliku (naj?e??e fotografiju) pomo?u ra?unara i monitora, te da ih snimi u neki od navedenih formata. Bitmap slika je slika koja prilikom zumiranja gubi svoj kvalitet, tj. dolazi do pixelizacije. Programi za obradu bitmap slika su mnogobrojni, a najzastupljeniji su Adobe Photoshop, Adobe Lightrom, Corel Photopaint, u krajnjem slu?aju MS Paint, i mnogi drugi. Slika veli?ine 33,4 KB bez kompresije Slika veli?ine 22,5 KB sa kompresijomSlika2.Sa kompresijom – bez kompresije [2]KOPRESIJA SA GUBITKOM PODATAKA (eng. Lossy)Kompresija sa gubitkom je na?ini komprimiranja slika ?iji algoritmi rade na principu brisanja ili zaboravljanja nepotrebnih podataka. Ovom metodom gubi se dio informacija o slici, ali s druge strane dobijemo sliku koja zauzima manje memorijskog prostora. Kompresije sa gubitkom temelje se na manama ljudskog oka. Ljudsko oko manje je osjetljivo na promjene u tonu boje nego na promjene u svjetlini. Iz navedenog razloga se boja i svjetlina razdvajaju u razli?ite kanale. Vi?e se komprimiraju dijelovi slike koji manje doprinose ukupnom izgledu. Kompresije sa gubitkom uzrokuju degradaciju slike u svakom koraku, ali naj?e??e omogu?avaju daleko ve?e omjere kompresije nego metode bez gubitaka. Tako?er svakim sljede?im korakom kompresije slika se dodatno degradira. JPEG je format koji koristi kompresiju sa gubitcima, a ujedno je i standard za kompresiju slike sa gubitkom informacija, odnosno lossy kompresiju.Neki od algoritama koji se koriste u Lossy metodama :1.Transformacijsko kodiranje ,2.Vektorska kvantizacija,3.Fraktalno kodiranje i4.Aproksimacijske metode i segmentacija.Transformacijsko kodiranjeKod transformacijskog kodiranja slike dimenzija NxN dijele se u manje blokove dimenzija nxn te se na svakom od njih primjenjuje unitarna transformacija. Cilj ove transformacije je dekodiranje orginalnog signala, a to naj?e??e rezultira raspodjelom najve?eg dijela energije u ni?im koeficijentima transformacije. Pomo?u ovog na?ina mnogi se koeficijenti mogu zanemariti nakon kvantizacije. Cijeli proces mo?e se svesti na ?etiri koraka:podjela slike,transformiranje slike,kvantizacija koeficijenata iHuffman kodiranje.Transformacijsko kodiranje vr?i se u dva koraka:segmentacija ( podjela slike na dvodimenzionalne vektore te transformiranje ( primjena izabrane transformacije ).JPEG i MPEG3 algoritmi koriste transformacijsko kodiranje. [7]Slika3.Transformacijsko kodiranje [11]Vektorska kvantizacija Vektorska kvantizacija je algoritam koji se mo?e matemati?ki definisat kao transsformacijski operator koji transformi?e R-K prostor u kona?an podskup X koji je predstavljen sa n vektora.[7] Taj podskup X je vektorska kodna knjiga.Ovaj metod defini?e se na iteraciji sljede?ih koraka:podjela podru?ja za treniranje u N grupacentroidi tih grupa postaju vektori u kodnoj knjiziprora?unavanje srednje distorzije; ako se postotno smanjenje distorzije uporedi sa prethodnim korakom ispod odre?enog praga, onda se proces zaustavlja. [7]Fraktalno kodiranjeOvaj 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 1000 : 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. Tokom godina ti algoritmi su unapre?ivani, tako da danas postoje njihove upotrebljive verzije, a radi se i na njihovoj implementaciji u hardwerski oblik.[7]Slika4.Usvakoj iteraciji objekt je transformirana verzija objekta iz pro?le iteracije [11]Aproksimacijske metode i segmentacija Ovim metodama se slika modelira kao mozaik regija, a svaka od tih regija karakterizirana je odre?enim stepenom uniformnosti svojih piksela. Kao primjere ovih metoda imamo polinomsku aproksimaciju i aproksimaciju teksturama. Aproksimacija teksturama temelji se na sintezi parametriziranih tekstura baziranih na nekom modelu dok se polinomska zasniva na rekonstrukciji regija na osnovi srednjih vrijednosti polinomskih funkcija.KOPRESIJA BEZ GUBITKA PODATAKAKompresija bez gubitka podataka je na?in sa?imanja kod kojeg ne dolazi do gubitka podataka i kvalitete informacija. Drugi naziv za ovu vrstu kompresije je nezaboravna kompresija. Prilikom kompresije slike ovom metodom svi podaci slike ostaju sadr?ani, te se isto tako prilikom dekompresije mogu vratiti u izvorno stanje. Nakon dekompresije slika se vra?a u izvorni oblik u apsolutno identi?noj formi. Svi slikovni elementi nakon dekompresije poprimaju iste vrijednosti koje su imali prije kompresije. Vrlo ?esto programi za obradu slika koriste ovu vrstu algoritama za kompresiju. Najzastupljeniji formati koji koriste kompresiju bez gubitaka su: GIF, PNG, TIFF i BMP. Slika5.Kompresija bez gubitka podataka [2]Algoritmi koji se koriste kod ove kompresije su:Run – length kodiranje,Huffmanovo kodiranje ,Entropijsko kodiranje i Kodiranje podru?ja.Run-length kodiranjeRun-length je jednostavan oblik kodiranja koji iskori?tava ?injenicu da ve?ina datoteka sadr?i nizove istih vrijednosti. Run-length algoritam prolazi kroz datoteku, te kada prona?e niz od dva ili vi?e istih znakova koji se ponavljaju ubacuje specijalne znakove. U binarnom sistemu za crnu i bijelu sliku vrijednost piksela je 0 ili 1. Ovdje je vrijednost 0 za piksel crne boje, a vrijednost 1 za piksel bijele boje.[1] Neka je na pr. kod slike:WWWWWBBBWWWWWWWWBBWWWWWWWWBBBWWBBWBWWWBBBBNakon primjene Run-length kodiranja, kodirana slika je:5W3B8W2B8W3B2W2B1W1B3W4B [1]Dakle ovom metodom smo 42 znaka prikazali pomo?u 24 znaka.Slika6.Run-length kodiranje [2]Huffmanovo kodiranjeAlgoritam je dobio ime po svome izumitelju D.A.Huffman. Temelji se na ?injenici da se neki znakovi pojavljuju ?e??e nego drugi. Na temelju navedene ?injenice tj. frekvencije ponavljanja pojedinih znakova algoritam izgra?uje te?insko binarno stablo. Svaki element napravljenog stabla dobiva novu kodnu rije? koja odre?uje poziciju znaka u stablu. Znak sa najve?om frekvencijom ponavljanja postaje korijen stabla, te mu se pridru?uje najkra?a kodna rije?, dok kodna rije? najrje?e ponavljanog znaka mo?e biti i dvostruko du?a od samog znaka.[7]Slika7.Huffmanovo kodiranje [2]Entropijsko kodiranjeNja?e??e se koristi pristup J.Ziv/Lempel(tzv.Lempel/Ziv ili LZ) koji se zasniva na tome da koder i dekoder sadr?e jednak rije?nik metasimbola od kojih svaki predstavlja cijelu sekvenciju ulaznih znakova. Ako se sekvencija ponovi nakon ?to je prona?en simbol za nju, onda se ona zamjenjuje tim simbolom.. Kodovani podaci ne trebaju sadr?avati rije?nik (nizovi znakova=simbol) budu?i da je rije?nik sadr?an u koderu i dekoderu. Karakteristike:odnos kompresije iznosi do 1:8 za prosje?ne tablice koje rastu s izvo?enjem algoritma.[7]Slika8.Kodiranje kodnom tablicom [2]Kodiranje podru?jaTo je pobolj?ana verzija run-length kodiranja koja iskori?tava dvodimenzionalnu karakteristiku slika. Algoritam poku?ava prona?i pravougle regije jednakih karakteristika koje se zatim koduju u opisnoj formi kao elementi s dvije ta?ke i odre?enom strukturom. Cijela slika treba biti opisana da bi se omogu?ilo dekodovanje bez gubitaka. Mogu?e performanse temelje se na vrlo kompleksnom problemu pronala?enja najve?ih podru?ja jednakih karakteristika. Vrlo je efikasan na?in kodovanja, ali zbog svoje nelinearnosti onemogu?uje hardwarsku implementaciju, te je relativno spor.[7]FORMATISvi podaci u ra?unalu spremaju se i obra?uju u binarnom obliku. Na?in na koji se neki podatak pretvori u binarni oblik naziva se format podataka. Na?in na koji ?e se boje i oblici sa slike pretvoriti u binarne brojeve zove se format za pohranu slika. Za pohranu slika na ra?unaru koristi se mnogo razli?itih na?ina pretvorbe slike u binarne brojeve, pa se ka?e da postoji mnogo formata za zapis slika. Razli?iti formati mogu koristiti ili ne koristiti sa?imanje (kompresiju) podataka i mogu biti sa gubitkom ili bez gubitka podataka. [7]GIF formatSkra?enica GIF je skra?enica od engl.Graphics Interchange Format. GIF format koristi sa?imanje podataka bez gubitka kvalitete slike.[10] To zna?i da se zapisuju svi podaci slike i da pri tome slika ne gubi ni?ta od izvorne kvalitete. Sa?imanjem se zapis pretvara u oblik koji zauzima ?to manje memorije, ali ne na ra?un kvalitete slike. Broj boja u GIF formatu ograni?en je na 256 boja (ili nijanse sive boje). Koristi se za pohranu crte?a i jednostavnijih slika koje ne sadr?e puno prelaza boja. GIF format se ne koristi za pohranu slika koje su fotografije ili imaju u sebi puno boja (ili nijansi sive boje) odnosno prelaza boja. GIF format ima neke mogu?nossti koje drugi formati nemaju, a to su prozirnost (engl.transparency) i animacija (engl.animation). Kada se sprema slika u GIF formatu mo?e se izabrati jedna(i samo jedna) boja koja ?e biti prozirna. Ako se takva slika kasnije upotrijebi ispod prozirnih dijelova ?e se vidjeti pozadina slike. Ako se koristi animacija, tada se dobiva privid pokretne slike. Ta pokretna slika je predvi?ena samo za vrlo jednostavne pokrete i nije usporediva s npr. televizijskom slikom. Animacija u GIF fomratu se posti?e tako da su u jednom polju pohranjene sve slike(engl.frames) od kojih se sastoji animacija. Ako se npr. animacija sastoji od 10 razli?itih slika koje povezano zajedno daju dojam animacije onda su sve te slike pohranjene u istom polju u GIF formatu. Ako se GIF koristi za fotografije, onda se nedostaci ubla?avaju postupkom Dithering-a, a kojim se uz upotrebu raspolo?ive palete boja i primjenom razli?itih algoritama za rasteriranje, posti?u efekti bli?i izvornoj slici. [3] Izvorna slika GIF bez ditheringa GIF sa ditheringomSlika9.[9]BMP formatSkra?enica BMP je od engl.Bitmap. Koristi se naj?e??e nesa?eti (iako postoji i sa?eti) zapis podataka bez gubitaka kvalitete slike. Mo?e sadr?avati slike koje imaju od 2 do 16777216 boja (ili nijansi sive boje). Koristi se za sve namjene od pohrane crte?a i jednostavnijih slika do pohrane fotografija. Svi programi za obradu slike na ra?unarima s Windows operacijskim sistemom podr?avaju ovaj format. BMP format upotrebljava se vrlo rijetko jer koristi nesa?eti zapis koji kod ve?ih razlu?ivosti i broja boja zauzima mnogo memorije. Ne podr?ava prozirnost i animaciju.[4] Slika9. prikazuje Logotip Wikipedije veli?ine 1058x1058 piksela uz 24-bitnu (3 bajta) dubinu boje zauzima 3,20MB u formatu BMP, dok u formatu PNG zauzima 270kB.[6]Slika10.[6]TIFF formatSkra?enica TIFF je od engl. Tag-based Image File Format. Format podr?ava sa?imanje podatak bez gubitaka ali mo?e pohranjivati i nesa?ete podatke.[10] Mo?e sadr?avati slike koje imaju pd 2 do 16777216 boja (ili nijansi sive boje). Koristi se za sve namjene od pohrane crte?a i jednostavnijih slika do fotografija. Prednosti formata u odnosu na BMP format je manje zauze?e memorije, a u odnosu na JPEG format kvaliteta slika.Slika11.TIFF bez kompresije (lijevo), a TIFF sa LZW kompresijom (desno)[8]JPEG(JPG) formatSkra?enica JPEG(JPG) je od engl.Joint Photographic Experts Group, ?o je naziv udruge koja je donijela normu za taj format zapisa. Format koristi sa?imanje podataka sa gubitkom kvalitete slike.[10] Mo?e sadr?avati slike koje imaju od 2 do 16777216 boja (ili nijansi sive boje). Prvenstveno se koristi za pohranjivanje fotografija, a ne za pohranjivanje crte?a ili slika s relativno malo boja. Gubitak kvalitete slike odre?uje se stupnjem sa?imanja podataka. ?to je stupanj sa?imanja ve?i to je vidljiviji gubitak kvalitete slike i obratno. Najve?a prednost formata u odnosu na do sada nevedene formate je u bitno manjem zauze?u memorije. Polja su najmanja od svih gore navedenih pa ?ak i uz najve?u kvalitetu slike (najmanje sa?imanje). Koristi se i na drugim operacijskim sistemima. Ne podr?ava prozirnost i animaciju.3162300762000lefttop00 JPEG sa 100% originalnog kvaliteta Zadr?imo 80% originalnog kvaliteta, razlikasmanjuje veli?inu datoteke na 84% [5] u odnosu na original je te?ko uo?lljiva [5]304800-19050 60% originalnog kvaliteta, datoteka 40% gubitka ( gubitak neproporcionalan manja za 95.2% [5]u?tedi ) [5] 20% originalnog kvaliteta[5] 0% originalnog kvalitete( o?iti blokovi piksela ) [5]ZAKLJU?AKUkoliko treba pohraniti crte? ili sliku s relativno malo boja najbolje je koristiti GIFF format jer daje najbolji omjer ime?u kvalitete i zauze?a prostora na disku. Za fotografije i slike s mnogo boja (ili nijansi sive boje) odnosno prelaza boja koje trebaju biti ?to kvalitetnije preporu?uje se upotreba TIFF formata. Za istu namjenu, ali ako nije toliko kriti?na kvaliteta slike ve? je bitno zauze?e memorije preporu?uje se JPEG format. Formati koji su pogodni i najvi?e se koriste na internetu su JPEG i GIF.[12]Literatura [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download