Algoritam je razvijen od strane Joint Photographic Expert Group posebno za kompresiju 24-bitnih i sivih slika 1991. godine. Ovaj algoritam ne komprimira slike na dva nivoa baš dobro, ali dobro radi u rukovanju slikama kontinualnih tonova u kojima bliski pikseli obično imaju slične boje. Obično oko ne može primijetiti nikakvu razliku kada se komprimira ovom metodom 10 ili 20 puta.
Algoritam se zasniva na DCT primenjenom na matricu disjunktnih blokova slike od 8x8 piksela. DCT dekomponuje ove blokove prema amplitudama određenih frekvencija. Rezultat je matrica u kojoj su mnogi koeficijenti, po pravilu, blizu nule, što se može prikazati u grubom numeričkom obliku, tj. u kvantiziranom obliku bez značajnog gubitka kvalitete restauracije.
Razmotrimo rad algoritma detaljnije. Pretpostavimo da se komprimuje 24-bitna slika u punoj boji. U ovom slučaju dobijamo sledeće faze rada.
Korak 1. Konvertujemo sliku iz RGB prostora u YCbCr prostor koristeći sljedeći izraz:
Odmah primijetimo da se inverzna transformacija lako dobija množenjem inverzna matrica u vektor, koji je u suštini YUV prostor:
.
Korak 2. Originalnu sliku podijelimo na matrice 8x8. Formiramo tri radne DCT matrice od svake - 8 bita posebno za svaku komponentu. Pri visokim omjerima kompresije, blok 8x8 se dekomponuje na YCbCr komponente u formatu 4:2:0, tj. komponente za Cb i Cr su uzete kroz tačku u redovima i kolonama.
Korak 3. Primjena DCT-a na blokove slike 8x8 piksela. Formalno, direktni DCT za blok 8x8 se može napisati kao
Gdje 
. Pošto je DCT „srce“ JPEG algoritma, poželjno je u praksi da se izračuna što je brže moguće. Jednostavan pristup ubrzavanju izračunavanja je da se unaprijed izračunaju kosinusne funkcije i da se rezultati tabele. Štoviše, s obzirom na ortogonalnost kosinusnih funkcija s različite frekvencije, gornja formula se može napisati kao
.
Ovdje je matrica od 8x8 elemenata, koja opisuje 8-dimenzionalni prostor, za predstavljanje stupaca bloka u ovom prostoru. Matrica je transponovana matrica i radi istu stvar, ali za blok redove. Rezultat je odvojiva transformacija, koja se u matričnom obliku zapisuje kao
Evo rezultata DCT-a, za čije izračunavanje su potrebne operacije množenja i skoro isto toliko sabiranja, što je znatno manje od direktnih proračuna korištenjem gornje formule. Na primjer, trebat će vam za konverziju slike veličine 512x512 piksela aritmetičke operacije. Uzimajući u obzir 3 komponente svjetline, dobijamo vrijednost od 12.582.912 aritmetičkih operacija. Broj množenja i sabiranja može se dodatno smanjiti korištenjem algoritma brze Fourierove transformacije. Kao rezultat toga, za transformaciju jednog bloka 8x8 morat ćete napraviti 54 množenja, 468 sabiranja i pomaka bitova.
Kao rezultat DCT-a dobijamo matricu u kojoj su koeficijenti lijevo gornji ugao odgovaraju niskofrekventnoj komponenti slike, au donjem desnom - visokofrekventnoj.
Korak 4. Kvantizacija. U ovom koraku neke informacije se odbacuju. Ovdje se svaki broj iz matrice dijeli posebnim brojem iz "tablice kvantizacije", a rezultat se zaokružuje na najbliži cijeli broj:
.
Štaviše, za svaku matricu Y, Cb i Cr, možete postaviti vlastite tablice kvantizacije. JPEG standard čak dozvoljava upotrebu sopstvenih tabela kvantizacije, koje će, međutim, morati da se prenesu u dekoder zajedno sa kompresovanim podacima, što će povećati ukupnu veličinu datoteke. Jasno je da je korisniku teško samostalno odabrati 64 koeficijenta, pa JPEG standard koristi dva pristupa za matrice kvantizacije. Prvi je da JPEG standard uključuje dvije preporučene tabele kvantizacije: jednu za lumu i jednu za hrominaciju. Ove tabele su predstavljene u nastavku. Drugi pristup je da se sintetizira (izračunavanje u hodu) tablice kvantizacije koja ovisi o jednom parametru koji je odredio korisnik. Sama tabela je izgrađena prema formuli
Faza kvantizacije je gdje se kontrolira omjer kompresije i gdje se javljaju najveći gubici. Jasno je da ćemo specificiranjem tablica kvantizacije sa velikim koeficijentima dobiti više nula, a samim tim i veći omjer kompresije.
Specifični efekti algoritma su takođe povezani sa kvantizacijom. Pri velikim vrijednostima koraka kvantizacije, gubici mogu biti toliki da se slika raspada na monokromatske kvadrate 8x8. Zauzvrat, gubici na visokim frekvencijama mogu se manifestirati u takozvanom "Gibbsovom efektu", kada se oko kontura s oštrim prijelazom boja formira talasast "halo".
Korak 5. Konvertujemo matricu 8x8 u vektor od 64 elementa koristeći cik-cak skeniranje (slika 2).
Rice. 2. Cik-cak skeniranje
Kao rezultat toga, koeficijenti različiti od nule će, po pravilu, biti zapisani na početku vektora, a lanci nula će se formirati na kraju.
Korak 6. Vektor transformiramo pomoću modificiranog RLE algoritma, čiji su izlazni parovi tipa (skip, broj), gdje je "skip" brojač preskočenih nula, a "broj" je vrijednost koja se mora staviti u sljedeći ćelija. Na primjer, vektor 1118 3 0 0 0 -2 0 0 0 0 1 ... bit će skupljen u parove (0, 1118) (0,3) (3,-2) (4,1) ... .
Treba napomenuti da je prvi broj pretvorene komponente u suštini jednak prosječnoj svjetlini bloka 8x8 i naziva se DC koeficijent. Isto za sve blokove slika. Ova okolnost sugerira da se DC koeficijenti mogu efikasno komprimirati ako zapamtite ne njihove apsolutne vrijednosti, već relativne u obliku razlike između DC koeficijenta trenutnog bloka i DC koeficijenta prethodnog bloka, i zapamtite prvi koeficijent kao TO JE. U ovom slučaju, poredak DC koeficijenata može se izvršiti, na primjer, ovako (slika 3). Preostali koeficijenti, koji se nazivaju AC koeficijenti, ostaju nepromijenjeni.
Korak 7 Konvolviramo rezultirajuće parove koristeći neuniformne Huffmanove kodove sa fiksnom tablicom. Štaviše, za DC i AC koeficijente, različite šifre, tj. različiti stolovi sa Huffman kodovima.
Rice. 3. Šema uređenja koeficijenta DC
Rice. 4. Blok dijagram JPEG algoritma
Proces obnavljanja slike u ovom algoritmu je potpuno simetričan. Metoda vam omogućava da komprimirate slike 10-15 puta bez vidljivih gubitaka vida.
Prilikom izrade ovog standarda vodili smo se činjenicom da ovaj algoritam morao da komprimuje slike prilično brzo - ne više od jedne minute na prosečnoj slici. Ovo je 1991! A njegova hardverska implementacija bi trebala biti relativno jednostavna i jeftina. U ovom slučaju, algoritam je morao biti simetričan u vremenu rada. Performanse najnoviji zahtjev učinio mogući izgled digitalni fotoaparati koji snimaju 24-bitne slike. Da je algoritam asimetričan, bilo bi neugodno dugo čekati da se uređaj "napuni" i komprimira sliku.
Iako je JPEG algoritam ISO standard, njegov format datoteke nije fiksiran. Koristeći ovo, proizvođači kreiraju vlastite formate koji su međusobno nekompatibilni, te stoga mogu promijeniti algoritam. Stoga su interne tabele algoritama koje preporučuje ISO zamijenjene njihovim vlastitim. Postoje i JPEG opcije za određene aplikacije.
JPEG je jedan od najnovijih i prilično moćnih algoritama. U praksi, to je “de facto” standard za slike u punoj boji. Algoritam radi na područjima 8x8 u kojima se svjetlina i boja relativno glatko mijenjaju. Kao rezultat toga, kada se matrica takvog regiona dekomponuje u dvostruki niz u kosinusima (formule ispod), značajni su samo prvi koeficijenti. Dakle, JPFG kompresija se postiže izglađivanjem promjena boja na slici.
Algoritam je razvila grupa stručnjaka za fotografiju posebno za kompresiju 24-bitnih JPEG slika - Zajednička fotografska ekspertska grupa - odjel unutar ISO - Međunarodne organizacije za standardizaciju. Generalno, algoritam se zasniva na diskretnoj kosinusnoj transformaciji (u daljem tekstu DCT) primenjenoj na matricu slike da bi se dobila nova matrica koeficijenata. Da bi se dobila originalna slika, primjenjuje se inverzna transformacija
DCT dekomponuje sliku prema amplitudama određenih frekvencija, tako da tokom transformacije dobijamo matricu u kojoj su mnogi koeficijenti ili blizu ili jednaki nuli. osim toga, ljudski sistem percepcija boja slabo prepoznaje određene frekvencije. Stoga je moguće grublje aproksimirati neke koeficijente bez primjetnog gubitka kvaliteta slike.
U tu svrhu koristi se kvantizacija koeficijenta. U samom jednostavan slučaj je aritmetički pobitni pomak udesno. Ovom konverzijom neke informacije se gube, ali se mogu postići veliki omjeri kompresije.
Algoritamski rad.
Neka 24-bitna slika bude komprimirana.
Korak I.
Konvertujemo sliku iz RGB prostora boja, sa komponentama odgovornim za crvene, zelene i plave komponente tačke boje, u YCrCb prostor boja (ponekad se naziva YUV).
U njemu je Y komponenta svjetline, a Cr, Cb su komponente odgovorne za boju (hromatska crvena i hromatska plava). Zbog činjenice da je ljudsko oko manje osjetljivo na boju nego na svjetlinu, postaje moguće arhivirati nizove za Cr i Cb komponente s velikim gubicima i, shodno tome, velikim omjerima kompresije. Ova vrsta konverzije se već dugo koristi na televiziji. Tamo je dodijeljen uži frekvencijski pojas za signale odgovorne za boju.
Pojednostavljeni prijevod iz RGB prostora boja u YCrCb prostor boja može se predstaviti na sljedeći način:
Inverzna transformacija se izvodi množenjem YUV vektora inverznom matricom:
Korak 2.
Originalnu sliku podijelimo na matrice 8x8. Formiramo tri radne DCT matrice od svake - 8 bita posebno za svaku komponentu. Pri većim omjerima kompresije, ovaj korak može biti malo teži. Slika je podijeljena Y komponentom - kao u prvom slučaju, a za Cr i Cb komponente matrice se kucaju kroz red i kroz kolonu. One. od originalne 16x16 matrice dobija se samo jedna radna DCT matrica. Iako je to lako primijetiti, gubimo 3/4 korisne informacije o komponentama u boji slike i odmah dobiti dvostruku kompresiju. To možemo učiniti radeći u YCrCb prostoru. Na rezultat RGB slika, kao što je praksa pokazala, to nema jak učinak.
Korak 3.
Mi primjenjujemo DCT na svaku radnu matricu. U ovom slučaju dobijamo matricu u kojoj koeficijenti u gornjem lijevom uglu odgovaraju niskofrekventnoj komponenti slike, au donjem desnom - visokofrekventnoj komponenti.
U pojednostavljenom obliku, ova transformacija se može predstaviti na sljedeći način:
Korak 4.
Vršimo kvantizaciju. U principu, ovo je jednostavno dijeljenje radne matrice elementom po elementu matrice kvantizacije. Za svaku komponentu (Y, U i V), u opštem slučaju, specificira se sopstvena matrica kvantizacije (u daljem tekstu MC).
Ovaj korak je gdje se kontrolira omjer kompresije i gdje se javljaju najveći gubici. Jasno je da ćemo specificiranjem MK sa velikim koeficijentima dobiti više nula i samim tim veći stepen kompresije.
Specifični efekti algoritma su takođe povezani sa kvantizacijom. Za velike vrijednosti koeficijenta gama , - gubici na nižim frekvencijama mogu biti toliki da se slika razbije na kvadrate 8x8. Gubici na visokim frekvencijama mogu se manifestirati u takozvanom "Gibbsovom efektu", kada se oko kontura s oštrim prijelazom boja formira neka vrsta "haloa".
Korak 5.
Konvertujemo matricu 8x8 u vektor od 64 elementa koristeći cik-cak skeniranje, tj. odaberite elemente s indeksima (0.0). (0,1). (1.0). (2.0)...
Dakle, na početku vektora dobijamo matrične koeficijente koji odgovaraju niske frekvencije, i na kraju - visoko.
Korak 6.
Sažimamo vektor koristeći algoritam grupnog kodiranja. U ovom slučaju dobijamo parove tipa (skip, broj), gde je „skip“ brojač preskočenih nula, a „broj“ je vrednost koja se mora staviti u sledeću ćeliju.
Dakle, vektor će se skupiti u parove (0, 42) (0, 3) (3, -2) (4, 1)
Korak 7
Sažimamo naučene parove koristeći Huffman kodiranje s fiksnom tablicom.
Proces obnavljanja slike u ovom algoritmu je potpuno simetričan. Metoda vam omogućava da komprimirate neke slike 10-15 puta bez ozbiljnih gubitaka.
Cjevovod operacija korištenih u JPEG algoritmu.
Essential pozitivni aspekti Algoritam je da:
- 1) Postavlja omjer kompresije
- 2) Slobodan dan slika u boji može imati 24 bita po tački.
Negativni aspekti algoritma su:
- 1) Kako se nivo kompresije povećava, slika se raspada na zasebne kvadrate (8x8). To je zbog činjenice da se veliki gubici javljaju na niskim frekvencijama tokom kvantizacije i postaje nemoguće vratiti originalne podatke.
- 2) Pojavljuje se Gibbsov efekat - oreoli duž granica oštrih prijelaza boja.
JPEG je standardizovan relativno nedavno - 1991. godine. Ali čak i tada su postojali algoritmi koji su se jače kompresovali sa manjim gubitkom kvaliteta. Činjenica je da su akcije standardnih programera bile ograničene snagom tehnologije koja je postojala u to vrijeme. Odnosno, čak i na personalnom računaru, algoritam je morao da radi manje od jednog minuta na prosečnoj slici, a njegova hardverska implementacija je morala biti relativno jednostavna i jeftina. Algoritam je morao biti simetričan (vrijeme raspakiranja je približno jednako vremenu arhiviranja).
Posljednji zahtjev omogućio je pojavu digitalnih kamera - uređaja veličine male video kamere koji snimaju 24-bitne fotografije na fleš kartici od 10-20 MB sa PCMCIA interfejsom. Zatim se kartica ubacuje u slot na laptopu i odgovarajući program omogućava čitanje slika. Da je algoritam asimetričan, bilo bi neugodno dugo čekati da se uređaj "napuni" i komprimira sliku.
Još jedno ne baš prijatno svojstvo JPEG-a je da je često horizontalno i vertikalne pruge potpuno su nevidljivi na displeju i mogu se pojaviti samo kada se štampaju u obliku moiré uzorka. Javlja se kada se nagnuti raster za štampanje preloži na horizontalne i vertikalne pruge slike. Zbog ovih iznenađenja, JPEG se ne preporučuje za aktivnu upotrebu u štampanju, postavljajući visoke koeficijente. Međutim, kada se arhiviraju i slike namijenjene ljudskom gledanju, jeste ovog trenutka nezamjenjiv.
Široku upotrebu JPEG-a dugo vremena ograničavala je, možda, samo činjenica da radi na 24-bitnim slikama. Stoga, kako bi se slika sa prihvatljivim kvalitetom prikazala na redovni monitor u paleti od 256 boja, zahtijevalo je korištenje odgovarajućih algoritama i, stoga, određeno vrijeme. U aplikacijama koje su namijenjene zahtjevnim korisnicima, kao što su igre, takva kašnjenja su neprihvatljiva. Pored toga, ako imate slike, recimo, u 8-bitnom GIF formatu, konvertovane u 24-bitni JPEG, a zatim nazad u GIF za gledanje, gubitak kvaliteta će se desiti dva puta tokom obe konverzije. Međutim, povećanje u veličini arhive je često tako veliko (3-20 puta!), a gubitak u kvalitetu je tako mali da je skladištenje slika u JPEG formatu veoma efikasno.
Treba reći nekoliko riječi o modifikacijama ovog algoritma. Iako je JPEG ISO standard, njegov format datoteke nije fiksiran. Koristeći ovo, proizvođači koriste vlastite formate koji su međusobno nekompatibilni, te stoga mogu promijeniti algoritam. Dakle, interne tabele algoritama koje preporučuje ISO. Oni se zamjenjuju svojim vlastitim.Osim toga, postoji mala zabuna prilikom postavljanja stepena gubitaka. Na primjer, tokom testiranja se ispostavilo da “odličan” kvalitet, “100%” i “10 bodova” daju značajno različite slike. Usput, "100%" kvaliteta ne znači kompresiju bez gubitaka. Postoje i JPEG opcije za određene aplikacije.
Kako se ISO standard JPEG sve više koristi u razmjeni slika kompjuterske mreže. JPEG algoritam je podržan u formatima Quick Time, PostScript Level 2, Tiff 6.0 i trenutno zauzima istaknuto mjesto u multimedijalnim sistemima.
Karakteristike JPFG algoritma:
Omjeri kompresije: 2-200 (korisnički definirano).
Klasa slike: 24-bitne slike u punoj boji ili slike u nijansama sive bez oštrih prelaza boja (fotografije).
simetrija: 1.
Karakteristične karakteristike: U nekim slučajevima, algoritam stvara "halo" oko oštrih horizontalnih i vertikalnih granica na slici (Gibbsov efekat). Osim toga, uz visok stepen kompresije, slika je podijeljena na blokove veličine 8x8 piksela.
- Tutorial
UPD. Bio sam primoran da uklonim monospace formatiranje. Jednog lepog dana, habraparser je prestao da prihvata formatiranje unutra tags pre i kod. Cijeli tekst se pretvorio u kašu. Uprava Habra mi nije mogla pomoći. Sada je neujednačeno, ali je barem čitljivo.
Da li ste ikada želeli da znate kako funkcioniše jpg fajl? Hajde da to sada shvatimo! Zagrijte svoj omiljeni kompajler i hex editor, mi ćemo ovo dekodirati:
Namjerno sam uzeo manji crtež. Ovo je poznat, ali jako komprimiran Google favicon:
Odmah vas upozoravam da je opis pojednostavljen i date informacije nisu potpune, ali će kasnije biti lako razumjeti specifikaciju.
Čak i bez znanja kako se kodiranje događa, već možemo izdvojiti nešto iz datoteke.
- startni marker. Uvijek je na početku svih jpg datoteka.
Slijede bajtovi
. Ovo je marker koji označava početak odjeljka za komentare. Sljedeća 2 bajta
- dužina sekcije (uključujući ova 2 bajta). Dakle u sljedeća dva
- sam komentar. To su kodovi znakova ":" i ")", tj. običan emotikon. Možete ga vidjeti u prvom redu na desnoj strani hex editora.
Malo teorije
Vrlo kratko korak po korak:
Razmislimo o redoslijedu kojim se ovi podaci mogu kodirati. Recimo da je kanal Y potpuno kodiran za cijelu sliku, zatim Cb, pa Cr. Svi se sjećaju učitavanja slika na dial-up. Da su kodirani na ovaj način, morali bismo čekati da se cijela slika učita prije nego što se pojavi na ekranu. Također će biti neugodno ako se izgubi kraj datoteke. Vjerovatno postoje i drugi dobri razlozi. Stoga se kodirani podaci slažu jedan po jedan, u malim dijelovima. 
Da vas podsjetim da je svaki blok Y ij , Cb ij , Cr ij matrica DCT koeficijenata kodiranih Huffmanovim kodovima. U datoteci su raspoređeni ovim redoslijedom: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20
Čitanje fajla
Nakon što izdvojimo komentar, biće lako razumjeti da:- Fajl je podijeljen na sektore kojima prethode markeri.
- Markeri su dugi 2 bajta, pri čemu je prvi bajt .
- Gotovo svi sektori pohranjuju svoju dužinu u sljedeća 2 bajta nakon markera.
FF D8 FF FE 00 04 3A 29 FF DB 00 43 00 A0 6E 78
FF FF FF FF FF FF FF FF FF FF FF FF FF FF DB 00
43 01 AA B4 B4 F0 D2 F0 FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01 FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02 FF C4 00 1A
10 01 00 02 03 01 00 00 00 00 00 00 00 00 00 00
00 01 00 12 02 11 31 21 FF C4 00 15 01 01 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 FF
C4 00 16 11 01 01 01 00 00 00 00 00 00 00 00 00
00 00 00 00 11 00 01 FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00 AE E7 61 F2 1B D5 22 85 5D 04 3C
82 C8 48 B1 DC BF FF D9
Marker: DQT - tabela kvantizacije.
FF DB 00 43 00 A0 6E 78
8C 78 64 A0 8C 82 8C B4 AA A0 BE F0 FF FF F0 DC
DC F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF
Zaglavlje odjeljka uvijek zauzima 3 bajta. U našem slučaju jeste. Zaglavlje se sastoji od:
Dužina: 0x43 = 67 bajtova
Dužina vrijednosti u tabeli: 0 (0 - 1 bajt, 1 - 2 bajta)
[_0]
ID tabele: 0
Preostala 64 bajta treba da popune tabelu 8x8.
Pažljivije pogledajte redoslijed kojim se popunjavaju vrijednosti u tabeli. Ovaj redosled se zove cik-cak redosled: 
Marker: SOF0 - Osnovni DCT
Ovaj marker se zove SOF0 i znači da je slika kodirana korištenjem osnovne metode. Vrlo je česta. Ali ništa manje popularna na Internetu nije poznata progresivna metoda, kada se slika prvi put učitava niske rezolucije, a zatim normalna slika. Ovo vam omogućava da shvatite šta je tamo prikazano bez čekanja puno opterećenje. Specifikacija definira još nekoliko, kako mi se čini, ne baš uobičajenih metoda.FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01
Dužina: 17 bajtova.
Preciznost: 8 bita. U osnovnoj metodi to je uvijek 8. Koliko ja razumijem, ovo je dubina bita vrijednosti kanala.
Visina slike: 0x10 = 16
Širina slike: 0x10 = 16
Broj komponenti: 3. Najčešće su to Y, Cb, Cr.
1. komponenta:
ID: 1
Horizontalno stanjivanje (H 1): 2
[_2]
Vertikalno stanjivanje (V 1): 2
ID tablice kvantizacije: 0
2. komponenta:
ID: 2
Horizontalno stanjivanje (H 2): 1
[_1]
Vertikalno stanjivanje (V 2): 1
3. komponenta:
ID: 3
Horizontalno stanjivanje (H 3): 1
[_1]
Vertikalno stanjivanje (V 3): 1
ID tablice kvantizacije: 1
Sada pogledajte kako odrediti koliko je slika tanka. Nalazimo H max =2 i V max =2. Kanal i će se istanjiti za H max /H i puta horizontalno i V max /V i puta vertikalno.
Marker: DHT (Huffmanova tablica)
Ovaj odjeljak pohranjuje kodove i vrijednosti dobivene Huffman kodiranjem.FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02
dužina: 21 bajt.
klasa: 0 (0 - tabela DC koeficijenata, 1 - tabela AC koeficijenata).
[_0]
id tabele: 0
Duljina Huffman koda: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Broj kodova:
Broj kodova znači broj kodova te dužine. Imajte na umu da odjeljak pohranjuje samo dužine kodova, a ne same kodove. Šifre moramo pronaći sami. Dakle, imamo jedan kod dužine 1 i jedan dužine 2. Ukupno 2 koda, u ovoj tabeli više nema kodova.
Svaki kod ima pridruženu vrijednost i oni su navedeni u datoteci kako slijedi. Vrijednosti su jednobajtne, tako da čitamo 2 bajta.
- vrijednost 1. koda.
- vrijednost 2. koda.
Konstrukcija Huffmanovog kodnog stabla
Moramo da napravimo binarno stablo iz tabele koju smo dobili u DHT sekciji. I iz ovog stabla prepoznajemo svaki kod. Vrijednosti dodajemo redoslijedom kojim su navedene u tabeli. Algoritam je jednostavan: bez obzira u kom se čvoru nalazimo, uvijek pokušavamo dodati vrijednost lijevoj grani. A ako je zauzeta, onda desno. A ako tamo nema mjesta, onda se vraćamo na viši nivo i pokušavamo odatle. Morate stati na nivou jednaka dužini kod. Lijeve grane odgovaraju vrijednosti 0, desne - 1.komentar:
Ne morate svaki put početi od vrha. Dodata vrijednost - vratite se na viši nivo. Postoji li prava grana? Ako jeste, idite ponovo gore. Ako ne, kreirajte desnu granu i idite tamo. Zatim, od ove tačke, počnite tražiti da dodate sljedeću vrijednost.
Stabla za sve tabele u ovom primjeru: 
UPD (hvala): Čvorovi prvog stabla (DC, id =0) moraju imati vrijednosti 0x03 i 0x02
U kružićima su značenja kodova, ispod kružića su sami kodovi (da objasnim da smo ih dobili tako što smo prošli put od vrha do svakog čvora). Ovim kodovima (ove i drugih tabela) je kodiran sam sadržaj slike.
Marker: SOS (početak skeniranja)
Bajt u markeru znači „DA! Konačno, prešli smo direktno na raščlanjivanje dijela kodirane slike!” Međutim, dio se simbolično naziva SOS. FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00
Dužina dijela zaglavlja (ne cijelog odjeljka): 12 bajtova.
Broj komponenti skeniranja. Imamo 3, po jedan za Y, Cb, Cr.
1. komponenta:
Broj komponente slike: 1 (Y)
ID Huffmanove tablice za DC koeficijente: 0
[_0]
ID Huffmanove tablice za AC koeficijente: 0
2. komponenta:
Broj komponente slike: 2 (Cb)
[_1]
3. komponenta:
Broj komponente slike: 3 (Cr)
ID Huffmanove tablice za DC koeficijente: 1
[_1]
ID Huffmanove tablice za AC koeficijente: 1
Ove komponente se ciklički izmjenjuju.
Ovdje se završava dio zaglavlja, odavde do kraja (marker) su kodirani podaci.
0
Pronalaženje DC koeficijenta.
1.
Čitanje niza bitova (ako naiđemo na 2 bajta, onda ovo nije marker, već samo bajt). Nakon svakog bita krećemo se duž Huffmanovog stabla (sa odgovarajućim identifikatorom) duž grane 0 ili 1, ovisno o pročitanom bitu. Zaustavljamo se ako se nađemo na konačnom čvoru.
10
1011101110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je jednak 0, tada je koeficijent jednak 0, upisujemo ga u tablicu i prelazimo na očitavanje ostalih koeficijenata. U našem slučaju - 02. Ova vrijednost je dužina koeficijenta u bitovima. To jest, čitamo sljedeća 2 bita, to će biti koeficijent.
10
10
11101110011101100001111100100
3. Ako je prva cifra vrijednosti u binarno predstavljanje- 1, onda ostavite kako jeste: DC_coef = vrijednost. Inače, transformiramo: DC_coef = vrijednost-2 vrijednost dužine +1. Koeficijent upisujemo u tablicu na početku cik-cak - gornjem lijevom uglu.
Pronalaženje AC koeficijenata.
1.
Slično koraku 1, pronalaženje DC koeficijenta. Nastavljamo da čitamo sekvencu:
10
10
1110
1110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je 0, to znači da preostale vrijednosti matrice treba popuniti nulama. Zatim se kodira sljedeća matrica. Prvih nekoliko koji pročitaju dovde i napišu mi o tome u ličnoj poruci dobiće plus u karmi. U našem slučaju, vrijednost čvora je 0x31.
Prvi grickanje: 0x3 - ovo je tačno koliko nula moramo dodati u matricu. Ovo su 3 nula koeficijenta.
Drugi grickanje: 0x1 - dužina koeficijenta u bitovima. Pročitajte sledeći deo.
10
10
1110
1
110011101100001111100100
3. Slično koraku 3 pronalaženja DC koeficijenta.
Kao što već razumijete, morate čitati AC koeficijente dok ne naiđemo na nultu vrijednost koda, ili dok se matrica ne popuni.
U našem slučaju dobijamo:
10
10
1110
1
1100
11
101
10
0
0
0
1
11110
0
100
i matrica:
Jeste li primijetili da su vrijednosti popunjene istim cik-cak uzorkom?
Razlog za korištenje ovog reda je jednostavan - budući da su veće vrijednosti v i u, manje je značajan koeficijent S vu u diskretnoj kosinusnoj transformaciji. Stoga, pri visokim stopama kompresije, beznačajni koeficijenti se postavljaju na nulu, čime se smanjuje veličina datoteke.
[-4 1 1 1 0 0 0 0] [ 5 -1 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0 0] [-1 -2 -1 0 0 0 0 0]
[ 0 -1 0 0 0 0 0 0] [ 0 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-1 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[-4 2 2 1 0 0 0 0]
[-1 0 -1 0 0 0 0 0]
[-1 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
Oh, zaboravio sam reći da kodirani DC koeficijenti nisu sami DC koeficijenti, već njihove razlike između koeficijenata iz prethodne tabele (isti kanal)! Potrebno je ispraviti matrice:
DC za 2.: 2 + (-4) = -2
DC za 3.: -2 + 5 = 3
DC za 4.: 3 + (-4) = -1
[-2 1 1 1 0 0 0 0] [ 3 -1 1 0 0 0 0 0] [-1 2 2 1 0 0 0 0]
………
Sada je sve u redu. Ovo pravilo važi do kraja fajla.
... i prema matrici za Cb i Cr:
[-1 0 0 0 0 0 0 0]
[ 1 1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
Pošto postoji samo jedna matrica, DC koeficijenti se mogu ostaviti netaknutim.
Računanja
Kvantizacija
Sjećate li se da matrica prolazi kroz fazu kvantizacije? Elementi matrice moraju se pomnožiti član po član sa elementima matrice kvantizacije. Ostaje samo da odaberete onu koja vam je potrebna. Prvo smo skenirali prvu komponentu, njena komponenta slike = 1. Komponenta slike sa ovim ID-om koristi matricu kvantizacije od 0 (naša je prva od dvije). Dakle, nakon množenja:
[ 0 120 280 0 0 0 0 0]
[ 0 -130 -160 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
Slično, dobijamo još 3 Y-kanalne matrice...
[-320 110 100 160 0 0 0 0] [ 480 -110 100 0 0 0 0 0]
[ 0 0 140 0 0 0 0 0] [-120 -240 -140 0 0 0 0 0]
[ 0 -130 0 0 0 0 0 0] [ 0 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-140 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[-160 220 200 160 0 0 0 0]
[-120 0 -140 0 0 0 0 0]
[-140 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
...i po matrici za Cb i Cr.
[-170 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 180 210 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
Inverzna diskretna kosinusna transformacija
Formula ne bi trebala biti teška*. S vu je naša rezultujuća matrica koeficijenata. u - stupac, v - red. s yx - direktno vrijednosti kanala.
*Uopšteno govoreći, ovo nije sasvim tačno. Kada sam uspio dekodirati i prikazati sliku veličine 16x16 na ekranu, uzeo sam sliku od 600x600 (usput rečeno, ovo je bila naslovnica omiljenog albuma Mind.In.A.Boxa - Lost Alone). Nije uspjelo odmah - pojavile su se razne greške. Uskoro sam mogao da se divim pravilno učitanoj slici. Jedina stvar koja me stvarno uznemirila je brzina preuzimanja. Još se sjećam da je trebalo 7 sekundi. Ali to nije iznenađujuće, ako nepromišljeno koristite gornju formulu, tada ćete za izračunavanje jednog kanala od jednog piksela morati pronaći 128 kosinusa, 768 množenja i neke dodatke. Razmislite samo o tome - skoro hiljadu teških operacija na samo jednom kanalu od jednog piksela! Srećom, ima prostora za optimizaciju (nakon mnogo eksperimentisanja smanjio sam vrijeme učitavanja na granicu tačnosti tajmera od 15ms, a nakon toga promijenio sliku u fotografiju sa 25 puta većom površinom. Možda ću o tome pisati u poseban članak).
Napisat ću rezultat izračunavanja samo prve matrice kanala Y (vrijednosti su zaokružene):
[ 87 72 50 36 37 55 79 95]
[-10 5 31 56 71 73 68 62]
[-87 -50 6 56 79 72 48 29]
I preostala 2:
Cb Cr
[ 60 52 38 20 0 -18 -32 -40] [ 19 27 41 60 80 99 113 120]
[ 48 41 29 13 -3 -19 -31 -37] [ 0 6 18 34 51 66 78 85]
[ 25 20 12 2 -9 -19 -27 -32] [-27 -22 -14 -4 7 17 25 30]
[ -4 -6 -9 -13 -17 -20 -23 -25] [-43 -41 -38 -34 -30 -27 -24 -22]
[ -37 -35 -33 -29 -25 -21 -18 -17] [-35 -36 -39 -43 -47 -51 -53 -55]
[ -67 -63 -55 -44 -33 -22 -14 -10] [ -5 -9 -17 -28 -39 -50 -58 -62]
[ -90 -84 -71 -56 -39 -23 -11 -4] [ 32 26 14 -1 -18 -34 -46 -53]
[-102 -95 -81 -62 -42 -23 -9 -1] [ 58 50 36 18 -2 -20 -34 -42]
- Oh, idem da jedem!
- Da, ne useljavam se uopšte, o čemu pričamo.
- Nakon što se dobiju vrijednosti boja YCbCr, ostaje samo da ih konvertujete u RGB, ovako: YCbCrToRGB(Y ij, Cb ij, Cr ij) , Y ij , Cb ij , Cr ij - naše rezultirajuće matrice.
- 4 Y matrice, i po jedna Cb i Cr, pošto smo razrijedili kanale i 4 Y piksela odgovaraju jednom Cb i Cr. Stoga izračunajte ovako: YCbCrToRGB(Y ij , Cb , Cr )
YCbCr u RGB
R = Y + 1,402 * CrG = Y - 0,34414 * Cb - 0,71414 * Cr
B = Y + 1,772 * Cb
Ne zaboravite dodati 128. Ako vrijednosti prelaze interval, dodijelite granične vrijednosti. Formula je jednostavna, ali također troši dio procesorskog vremena.
Evo rezultujućih tabela za R, G, B kanale za gornji lijevi kvadrat 8x8 našeg primjera:
255 248 194 148 169 215 255 255
255 238 172 115 130 178 255 255
255 208 127 59 64 112 208 255
255 223 143 74 77 120 211 255
237 192 133 83 85 118 184 222
177 161 146 132 145 162 201 217
56 73 101 126 144 147 147 141
0 17 76 126 153 146 127 108
231 185 117 72 67 113 171 217
229 175 95 39 28 76 139 189
254 192 100 31 15 63 131 185
255 207 115 46 28 71 134 185
255 241 175 125 112 145 193 230
226 210 187 173 172 189 209 225
149 166 191 216 229 232 225 220
72 110 166 216 238 231 206 186
255 255 249 203 178 224 255 255
255 255 226 170 140 187 224 255
255 255 192 123 91 138 184 238
255 255 208 139 103 146 188 239
255 255 202 152 128 161 194 232
255 244 215 200 188 205 210 227
108 125 148 172 182 184 172 167
31 69 122 172 191 183 153 134
Kraj
Generalno, nisam stručnjak za JPEG, tako da teško mogu odgovoriti na sva pitanja. Samo, kada sam pisao svoj dekoder, često sam morao da se nosim sa raznim stvarima neshvatljivi problemi. A kada je slika bila pogrešno prikazana, nisam znao gdje sam pogriješio. Možda je pogrešno protumačio bitove, ili je možda pogrešno koristio DCT. Stvarno mi je nedostajao korak po korak primjer, pa se nadamo da će ovaj članak pomoći pri pisanju dekodera. Mislim da pokriva opis osnovna metoda, ali ipak ne možete proći samo s njom. Nudim vam linkove koji su mi pomogli: Problemi sa algoritmima arhiviranja sa gubicimaKonvencionalni algoritmi su bili prvi koji su korišteni za arhiviranje slika. Oni koji su se koristili i koriste se u backup sistemima, pri kreiranju distribucija itd. Ovi algoritmi su arhivirali informacije nepromijenjene. Međutim, glavni trend u posljednje vrijeme bila je upotreba novih klasa slika. Stari algoritmi više ne ispunjavaju zahtjeve za arhiviranje. Mnoge slike praktički nisu bile komprimirane, iako su "na prvi pogled" imale očiglednu redundantnost. To je dovelo do stvaranja nove vrste algoritma - kompresije sa gubitkom informacija. Po pravilu se može podesiti koeficijent arhiviranja, a samim tim i stepen gubitka kvaliteta u njima. Ovo stvara kompromis između veličine slike i kvaliteta.
Jedan od ozbiljnih problema kompjuterske grafike je to što još nije pronađen adekvatan kriterijum za procenu gubitka kvaliteta slike. I stalno se gubi – tokom digitalizacije, prilikom prevođenja u ograničenu paletu boja, prilikom prevođenja u drugi sistem za prikaz boja za štampu i, što je za nas posebno važno, prilikom arhiviranja sa gubicima. Može se dati primjer jednostavnog kriterija: standardna devijacija vrijednosti piksela (L 2 mjera ili srednji kvadrat - RMS):
Prema njemu, slika će biti ozbiljno oštećena ako se svjetlina smanji za samo 5% (oko to neće primijetiti - postavka svjetline mnogo više varira na različitim monitorima). Istovremeno, slike sa "snijegom" - oštra promjena boje pojedinačnih poena, slabe pruge ili “moiré” će se smatrati “gotovo nepromijenjenim” (Objasnite zašto?). I drugi kriterijumi imaju svoje neprijatne strane.
Uzmite u obzir, na primjer, maksimalno odstupanje:
Ova mjera je, kao što možete pretpostaviti, izuzetno osjetljiva na gubitak pojedinačnih piksela. One. Na cijeloj slici može se značajno promijeniti samo vrijednost jednog piksela (što je za oko gotovo neprimjetno), međutim, prema ovoj mjeri, slika će biti jako oštećena.
Mjera koja se sada koristi u praksi naziva se omjer signala i šuma (PSNR).
Ova mjera je u suštini slična standardnoj devijaciji, ali je nešto praktičnija za korištenje zbog logaritamske skale skale. Ima iste nedostatke kao i standardna devijacija.
Naše oči su najbolji sudija o gubitku kvaliteta slike. Arhiviranje se smatra odličnim ako je nemoguće okom razlikovati originalne i nearhivirane slike. Dobra stvar je što kada možete da kažete koja je od slika arhivirana, možete uporediti samo dve susedne slike. Daljnjim povećanjem omjera kompresije, u pravilu, nuspojave karakteristične za ovaj algoritam postaju uočljive. U praksi, čak i uz odličan kvalitet očuvanja, na slici se mogu redovno vršiti određene promjene. Stoga se ne preporučuje korištenje algoritama za arhiviranje s gubicima prilikom komprimiranja slika koje će kasnije biti ili odštampane visoka kvaliteta, ili obrađene programima za prepoznavanje slika. Neprijatni efekti s takvim slikama, kao što smo već rekli, mogu se pojaviti čak i kod jednostavnog skaliranja slike. JPEG algoritam
JPEG je jedan od najnovijih i prilično moćnih algoritama. To je praktično de facto standard za slike u punoj boji. Algoritam radi na područjima 8x8 u kojima se svjetlina i boja relativno glatko mijenjaju. Kao rezultat toga, kada se matrica takve površine dekomponuje u dvostruki niz u kosinusima (pogledajte formule ispod), značajni su samo prvi koeficijenti. Dakle, JPEG kompresija se postiže glatkom promenom boja na slici.
Algoritam je razvila grupa stručnjaka za fotografiju posebno za kompresiju 24-bitnih slika. JPEG - Joint Photographic Expert Group - odjel unutar ISO - Međunarodne organizacije za standardizaciju. Ime algoritma glasi ["jei"peg]. Generalno, algoritam se zasniva na diskretnoj kosinusnoj transformaciji (u daljem tekstu DCT) primenjenoj na matricu slike da bi se dobila nova matrica koeficijenata. Za dobivanje originalne slike primjenjuje se inverzna transformacija.
DCT dekomponuje sliku prema amplitudama određenih frekvencija. Dakle, prilikom transformacije dobijamo matricu u kojoj su mnogi koeficijenti ili blizu ili jednaki nuli. Osim toga, zbog nesavršenosti ljudskog vida, moguće je grublje aproksimirati koeficijente bez primjetnog gubitka kvaliteta slike.
U tu svrhu koristi se kvantizacija koeficijenta. U najjednostavnijem slučaju, ovo je aritmetički pomak udesno. Ovom konverzijom neke informacije se gube, ali se mogu postići veliki omjeri kompresije.
Kako algoritam radi
Dakle, pogledajmo algoritam detaljnije. Hajde da komprimujemo 24-bitnu sliku.
Korak 1.
Konvertujemo sliku iz RGB prostora boja, sa komponentama odgovornim za crvene, zelene i plave komponente tačke boje, u YCrCb prostor boja (ponekad se naziva YUV).
U njemu je Y komponenta svjetline, a Cr, Cb su komponente odgovorne za boju (hromatska crvena i hromatska plava). Zbog činjenice da je ljudsko oko manje osjetljivo na boju nego na svjetlinu, postaje moguće arhivirati nizove za Cr i Cb komponente s visokim gubicima i, shodno tome, visokim omjerima kompresije. Ova vrsta konverzije se već dugo koristi na televiziji. Tamo je dodijeljen uži frekvencijski pojas za signale odgovorne za boju.
Pojednostavljeni prijevod iz RGB prostora boja u YCrCb prostor boja može se predstaviti korištenjem prijelazne matrice:
Inverzna transformacija se izvodi množenjem YUV vektora sa inverznom matricom.
Korak 2.
Originalnu sliku podijelimo na matrice 8x8. Formiramo tri radne DCT matrice od svake - 8 bita posebno za svaku komponentu. Pri većim omjerima kompresije, ovaj korak može biti malo teži. Slika je podijeljena Y komponentom - kao u prvom slučaju, a za Cr i Cb komponente matrice se kucaju kroz red i kroz kolonu. One. od originalne 16x16 matrice dobija se samo jedna radna DCT matrica. U ovom slučaju, kao što je lako vidjeti, gubimo 3/4 korisnih informacija o komponentama boje slike i odmah dobijamo dvostruko veću kompresiju. To možemo učiniti radeći u YCrCb prostoru. Kao što je praksa pokazala, ovo nema značajan uticaj na rezultujuću RGB sliku.
Korak 3.
Mi primjenjujemo DCT na svaku radnu matricu. U ovom slučaju dobijamo matricu u kojoj koeficijenti u gornjem lijevom uglu odgovaraju niskofrekventnoj komponenti slike, au donjem desnom - visokofrekventnoj komponenti.
U pojednostavljenom obliku, ova transformacija se može predstaviti na sljedeći način:
Korak 4.
Vršimo kvantizaciju. U principu, ovo je jednostavno dijeljenje radne matrice elementom po elementu matrice kvantizacije. Za svaku komponentu (Y, U i V), u opštem slučaju, specificira se sopstvena matrica kvantizacije q (u daljem tekstu MC).
Ovaj korak je gdje se kontrolira omjer kompresije i gdje se javljaju najveći gubici. Jasno je da ćemo specificiranjem MK sa velikim koeficijentima dobiti više nula i samim tim veći stepen kompresije.
Specifični efekti algoritma su takođe povezani sa kvantizacijom. Pri visokim gama vrijednostima, gubitak na niskim frekvencijama može biti toliki da se slika razbije na kvadrate 8x8. Gubici na visokim frekvencijama mogu se manifestirati u takozvanom "Gibbsovom efektu", kada se oko kontura s oštrim prijelazom boja formira neka vrsta "haloa".
Korak 5.
Konvertujemo matricu 8x8 u vektor od 64 elementa koristeći “cik-cak” skeniranje, tj. uzeti elemente sa indeksima (0,0), (0,1), (1,0), (2,0)...
Dakle, na početku vektora dobijamo matrične koeficijente koji odgovaraju niskim frekvencijama, a na kraju - visokim.
Korak 6.
Sažimamo vektor koristeći algoritam grupnog kodiranja. U ovom slučaju dobijamo parove tipa (skip, broj), gde je „skip“ brojač preskočenih nula, a „broj“ je vrednost koja se mora staviti u sledeću ćeliju. Tako će vektor 42 3 0 0 0 -2 0 0 0 0 1 ... biti presavijen u parove (0,42) (0,3) (3,-2) (4,1) ... .
Korak 7
Dobivene parove skupljamo pomoću Huffmanovog kodiranja s fiksnom tablicom.
Proces obnavljanja slike u ovom algoritmu je potpuno simetričan. Metoda vam omogućava da komprimirate neke slike 10-15 puta bez ozbiljnih gubitaka.
Cjevovod operacija korištenih u JPEG algoritmu.
Značajni pozitivni aspekti algoritma su:
- Postavlja omjer kompresije.
- Slobodan dan slika u boji može imati 24 bita po tački.
- Kako se nivo kompresije povećava, slika se raspada na pojedinačne kvadrate (8x8). To je zbog činjenice da se veliki gubici javljaju na niskim frekvencijama tokom kvantizacije, te postaje nemoguće vratiti originalne podatke.
- Pojavljuje se Gibbsov efekat - oreoli duž granica oštrih prijelaza boja.
Posljednji zahtjev omogućio je pojavu igračaka kao npr digitalni fotoaparati- uređaji veličine male video kamere koji snimaju 24-bitne fotografije na fleš kartici od 10-20 MB sa PCMCIA interfejsom. Zatim se ova kartica ubacuje u slot na vašem laptopu i odgovarajući program vam omogućava čitanje slika. Nije li istina, da je algoritam asimetričan, bilo bi neugodno dugo čekati da se uređaj "napuni" i komprimira sliku.
Još jedno ne baš prijatno svojstvo JPEG-a je da su često horizontalne i vertikalne pruge na ekranu potpuno nevidljive i mogu se pojaviti samo kada se odštampaju u obliku moiré uzorka. Javlja se kada se nagnuti raster za štampanje preloži na horizontalne i vertikalne pruge slike. Zbog ovih iznenađenja, JPEG se ne preporučuje za aktivnu upotrebu u štampanju, postavljajući visoke koeficijente. Međutim, kada se arhiviraju slike namijenjene ljudskom gledanju, ono je trenutno neizostavno.
Široku upotrebu JPEG-a dugo vremena ograničavala je, možda, samo činjenica da radi na 24-bitnim slikama. Stoga je za gledanje slike prihvatljivog kvaliteta na običnom monitoru u paleti od 256 boja bila potrebna upotreba odgovarajućih algoritama i, shodno tome, određeno vrijeme. U aplikacijama koje su namijenjene zahtjevnim korisnicima, kao što su igre, takva kašnjenja su neprihvatljiva. Pored toga, ako imate slike, recimo, u 8-bitnom GIF formatu, konvertovane u 24-bitni JPEG, a zatim nazad u GIF za gledanje, gubitak kvaliteta će se desiti dva puta tokom obe konverzije. Međutim, povećanje u veličini arhive je često tako veliko (3-20 puta!), a gubitak u kvalitetu je tako mali da je skladištenje slika u JPEG formatu veoma efikasno.
Treba reći nekoliko riječi o modifikacijama ovog algoritma. Iako je JPEG ISO standard, njegov format datoteke nije fiksiran. Koristeći ovo, proizvođači kreiraju vlastite formate koji su međusobno nekompatibilni, te stoga mogu promijeniti algoritam. Stoga su interne tabele algoritama koje preporučuje ISO zamijenjene njihovim vlastitim. Osim toga, postoji mala zabuna prilikom postavljanja stepena gubitka. Na primjer, tokom testiranja se ispostavilo da “odličan” kvalitet, “100%” i “10 bodova” daju značajno različite slike. U isto vrijeme, usput, "100%" kvaliteta ne znači kompresiju bez gubitaka. Postoje i JPEG opcije za određene aplikacije.
Kao ISO standard, JPEG se sve više koristi za razmjenu slika na računarskim mrežama. JPEG algoritam je podržan u formatima Quick Time, PostScript Level 2, Tiff 6.0 i trenutno zauzima istaknuto mjesto u multimedijalnim sistemima.
Karakteristike algoritma JPEG:
Klasa slike: 24-bitne slike u punoj boji ili slike u nijansama sive bez oštrih prelaza boja (fotografije).
simetrija: 1
karakteristike: U nekim slučajevima, algoritam stvara “halo” oko oštrih horizontalnih i vertikalnih granica na slici (Gibbsov efekat). Osim toga, uz visok stepen kompresije, slika je podijeljena na blokove veličine 8x8 piksela.
Fraktalni algoritamIdeja metode
Fraktalno arhiviranje se zasniva na činjenici da sliku predstavljamo u kompaktnijoj formi – koristeći koeficijente sistema iteriranih funkcija (u daljem tekstu IFS). Prije nego što razmotrimo sam proces arhiviranja, pogledajmo kako IFS gradi sliku, tj. proces dekompresije.
Strogo govoreći, IFS je skup trodimenzionalnih afinih transformacija, u našem slučaju pretvarajući jednu sliku u drugu. Tačke u trodimenzionalnom prostoru (x_koordinate, y_koordinate, svjetlina) prolaze kroz transformaciju.
Ovaj proces je najjasnije pokazao Barnsley u svojoj knjizi “Fractal Image Compression”. Tamo je predstavljen koncept mašine za fotokopiranje, koja se sastoji od ekrana na kojem je prikazana originalna slika i sistema sočiva koji projektuju sliku na drugi ekran:
- Objektivi mogu projektovati dio slike slobodnoj formi na bilo koju drugu lokaciju na novoj slici.
- Regioni u kojem slike se projektuju ne seku.
- Lens can promijenite svjetlinu i smanjite kontrast.
- Lens can ogledalo i rotirati vaš fragment slike.
- Objektiv mora u skali(smanjite) vaš fragment slike.
Raspoređivanjem sočiva i promenom njihovih karakteristika možemo kontrolisati rezultujuću sliku. Jedna iteracija rada Mašine je da se nova gradi od originalne slike koristeći dizajn, nakon čega se nova uzima kao početna. Tvrdi se da ćemo tokom procesa iteracije dobiti sliku koja će prestati da se mijenja. To će ovisiti samo o lokaciji i karakteristikama sočiva, a neće ovisiti o originalnoj slici. Ova slika se zove “ fiksna tačka" ili atraktor dati IFS. Odgovarajuća teorija garantuje da postoji tačno jedna fiksna tačka za svaki IFS.
Pošto je mapiranje sočiva kompresivno, svako sočivo eksplicitno specificira sebi slični područja na našoj slici. Zahvaljujući samosličnosti, dobijamo složenu strukturu slike pri bilo kom uvećanju. Dakle, intuitivno je da sistem iterativnih funkcija definira fraktal(nestrogo - samosličan matematički objekat).
Dvije najpoznatije slike dobivene korištenjem IFS-a su “trougao Sierpinskog” i “Brnslijeva paprat”. „Trougao Sierpinskog” je definisan sa tri, a „Barnslijeva paprat” sa četiri afine transformacije (ili, u našoj terminologiji, „sočiva”). Svaka transformacija je kodirana u doslovno nekoliko bajtova, dok slika napravljena pomoću njih može zauzeti nekoliko megabajta.
Vježba: Identifikujte 4 područja na slici, čiji spoj bi pokrivao cijelu sliku, a svaka bi bila slična cijeloj slici (ne zaboravite stabljiku paprati).
Iz navedenog postaje jasno kako arhivator radi i zašto je potrebno toliko vremena. U stvari, fraktalna kompresija je traženje samosličnih područja na slici i određivanje parametara afine transformacije za njih.
=>
U najgorem slučaju, ako se ne koristi algoritam optimizacije, biće potrebno nabrojati i uporediti sve moguće fragmente slike različitih veličina. Čak i za male slike, uzimajući u obzir diskretnost, dobijamo astronomski broj opcija koje treba razvrstati. Štoviše, čak i oštro sužavanje klasa transformacije, na primjer, zbog skaliranja samo određeni broj puta, ne daje primjetan dobitak u vremenu. Osim toga, gubi se kvalitet slike. Velika većina istraživanja u području fraktalne kompresije sada je usmjerena na smanjenje vremena arhiviranja potrebnog za dobivanje slike visokog kvaliteta.
Definicija.
Gdje a, b, c, d, e, f nazivaju se realni brojevi dvodimenzionalna afina transformacija.
Definicija. Transformacija, predstavljena u obliku
gdje su a, b, c, d, e, f, p, q, r, s, t, u realni brojevi i naziva se trodimenzionalna afina transformacija.
Definicija. Neka je transformacija u prostoru X. Tačka je takva da se zove fiksna tačka(atraktorska) transformacija.
Definicija. Pretvori u metrički prostor(X, d) se naziva ugovaranjem ako postoji broj s: , takav da
komentar: Formalno, možemo koristiti bilo koje mapiranje kompresije za fraktalnu kompresiju, ali u stvarnosti se koriste samo trodimenzionalne afine transformacije s prilično jakim ograničenjima na koeficijente.
Teorema. (O transformaciji kompresije)
Neka u kompletnom metričkom prostoru (X, d). Tada postoji tačno jedna fiksna tačka ove transformacije, a za bilo koju tačku niz 
konvergira na .
Općenitija formulacija ove teoreme garantuje konvergenciju.
Definicija. Slika je funkcija S definirana na jediničnom kvadratu i uzima vrijednosti od 0 do 1 ili
Neka se trodimenzionalna afina transformacija zapiše u obliku
i definiran je na kompaktnom podskupu kartezijanskog kvadrata x. Tada će prenijeti dio površine S na područje koje se nalazi sa smjenom (e,f) i rotaciju specificiranu matricom
Štaviše, ako tumačimo vrijednost S kako će se svjetlina odgovarajućih tačaka smanjiti za str puta (transformacija mora biti kompresivna) i promijenit će se u smicanje q.
Definicija.
Konačan skup W kontraktivne trodimenzionalne afine transformacije definirane na domenima kao što su 
, zvao sistem iterativnih funkcija ( IFS).
Sistem iteriranih funkcija je jedinstveno povezan sa fiksnom tačkom - slikom. Dakle, proces kompresije je da se pronađu koeficijenti sistema, a proces dekompresije je iteracija sistema dok se rezultujuća slika (fiksna tačka IFS) ne stabilizuje. U praksi je dovoljno 7-16 iteracija. Područja će se dalje nazivati rangiran, a oblasti - domena.
Konstrukcija algoritma
Kao što je već postalo očito iz gore navedenog, glavni zadatak pri kompresiji fraktalnim algoritmom je pronaći odgovarajuće afine transformacije. U najopćenitijem slučaju možemo prevesti područja slike bilo koje veličine i oblika, ali u ovom slučaju dobijamo astronomski broj iteracija različitih fragmenata, koji se trenutno ne mogu obraditi čak ni na superkompjuteru.
IN edukativna verzija algoritma , navedeno u nastavku, sljedeća ograničenja su napravljena na područjima:
- Sva područja su kvadrati sa stranicama paralelnim sa stranicama slike. Ovo ograničenje je prilično strogo. U stvari, mi ćemo aproksimirati čitav niz geometrijskih oblika samo kvadratima.
- Prilikom prijenosa područja domene u područje ranga, veličina se smanjuje tačno dva puta. Ovo uvelike pojednostavljuje i kompresor i dekompresor, jer zadatak skaliranja malih područja nije trivijalan.
- Svi blokovi domena su kvadratni i imaju fiksna veličina. Slika je podijeljena na skup blokova domena pomoću uniformne mreže.
- Područja domena su zauzeta „kroz tačku“ i u X i u Y, što odmah smanjuje pretragu za 4 puta.
- Prilikom prijenosa područja domene u područje ranga, moguća je rotacija kocke samo na 0 0, 90 0, 180 0 ili 270 0. Također dozvoljeno odraz ogledala. Ukupan broj mogućih transformacija (računajući prazne) je 8.
- Skaliranje (kompresija) se vrši vertikalno (osvjetljenje). fiksni broj puta- na 0,75.
Ova ograničenja dozvoljavaju:
- Napravite algoritam koji zahtijeva relativno mali broj operacija čak i na prilično velikim slikama.
- Veoma je kompaktan za prezentovanje podataka za pisanje u fajl. Za svaku afinu transformaciju u IFS-u zahtijevamo:
- dva broja za postavljanje pomaka bloka domene. Ako ograničimo ulazne slike na 512x512, tada će biti dovoljno 8 bita po broju.
- tri bita za specificiranje transformacije simetrije prilikom pretvaranja bloka domene u blok ranga.
- 7-9 bita za postavljanje pomaka svjetline tokom prijevoda.
Na primjer, za datoteku u sivim tonovima od 256 boja 512x512 piksela sa veličinom bloka od 8 piksela, postojaće 4096 afinskih transformacija (512/8x512/8). Svaki će zahtijevati 3,5 bajta. Stoga, ako je originalna datoteka zauzimala 262144 (512x512) bajtova (bez zaglavlja), tada će datoteka sa koeficijentima zauzimati 14336 bajtova. Faktor arhiviranja - 18 puta. Istovremeno, ne uzimamo u obzir da fajl sa koeficijentima takođe može imati redundantnost i biti arhiviran metodom arhiviranja bez gubitaka, na primer LZW.
Negativni aspekti predloženih ograničenja:
- Budući da su sva područja kvadrati, nemoguće je iskoristiti sličnost objekata koji su daleko od kvadratnog oblika (koji su prilično česti na stvarnim slikama).
- Slično tome, nećemo moći iskoristiti sličnost objekata na slici, koeficijent sličnosti između kojih se jako razlikuje od 2.
- Algoritam neće moći iskoristiti prednost sličnosti objekata na slici, ugao između kojih nije višestruki od 90 0.
Sam algoritam pakovanja se svodi na nabrajanje svih blokova domena i odabir odgovarajućeg blok ranga za svaki. Ispod je dijagram ovog algoritma.
za (sve blokove opsega) (
min_distance = Maksimalna udaljenost;
R ij= slika->CopyBlock(i,j);
za (svi blokovi domene) ( // Sa rotacijama i neg.
current=Trenutne koordinate transformacije;
D=slika->CopyBlock(trenutno);
trenutna_udaljenost = R ij.L2distance(D);
if(trenutna_udaljenost< min_distance) {
// Ako su najbolje kvote lošije:
min_distance = trenutna_udaljenost;
najbolje = trenutno;
}
) //Sljedeći raspon
Save_Coefficients_to_file(najbolje);
) //Sljedeća domena
Kao što se može vidjeti iz gornjeg algoritma, za svaki blok ranga provjeravamo ga sa svim mogućim blokovima domene (uključujući i one koji su prošli transformaciju simetrije), pronađite opciju sa najmanjom mjerom L 2 (najmanja standardna devijacija) i sačuvajte koeficijente ove konverzije u datoteku. Koeficijenti su (1) koordinate pronađenog bloka, (2) broj od 0 do 7 koji karakterizira transformaciju simetrije (rotacija, refleksija bloka) i (3) pomak svjetline za ovaj par blokova. Pomak svjetline se izračunava na sljedeći način:
,
Gdje r ij- vrijednosti piksela rangiranog bloka ( R), A d ij- vrijednosti piksela bloka domene ( D). U ovom slučaju, mjera se izračunava kao:
.
Mi ne kalkulišemo kvadratni korijen od L 2 mjere i ne dijelite ih na n, budući da su ove transformacije monotone i neće nas spriječiti da pronađemo ekstrem, međutim, moći ćemo izvesti dvije manje operacije za svaki blok.
Izračunajmo broj operacija koje su nam potrebne za komprimiranje slike u sivim tonovima od 256 boja 512x512 piksela s veličinom bloka od 8 piksela:
Tako smo uspjeli smanjiti broj operacija algoritma kompresije na prilično izračunljive (čak i nekoliko sati) vrijednosti.
Šema algoritma za dekompresiju slike
Dekompresija algoritma fraktalne kompresije je izuzetno jednostavna. Potrebno je provesti nekoliko iteracija trodimenzionalnih afinskih transformacija čiji su koeficijenti dobiveni u fazi kompresije.
Apsolutno bilo koja slika (na primjer, apsolutno crna) može se uzeti kao početna, jer nam odgovarajući matematički aparat jamči konvergenciju niza slika dobivenih tijekom IFS iteracija na nepokretnu sliku (blizu originalnoj). Obično je za to dovoljno 16 iteracija.
Očitajmo koeficijente svih blokova iz datoteke;
Kreirajmo crna slika prava veličina;
Dok (slika neće stati)(
Za(svaki raspon (R))(
D=image->CopyBlock(D_coord_for_R);
Za(svaki piksel( i,j) u bloku (
R ij = 0,75 D ij + o R ;
) //Sljedeći piksel
) //Sljedeći blok
)//Do kraja
Pošto smo zapisali koeficijente za blokove R ij(koji su, kao što smo rekli, u našem konkretnom slučaju kvadrati iste veličine) sekvencijalno, tada se ispostavlja da sekvencijalno popunjavamo sliku kvadratima particione mreže koristeći afinu transformaciju.
Kao što se može izračunati, broj operacija po pikselu slike u sivim tonovima tokom restauracije je neobično mali (N “+” operacija, 1 “*” operacija, gdje je N broj iteracija, tj. 7-16). Zahvaljujući tome, dekompresija slike za fraktalni algoritam je brža od dekompresije, na primjer, za JPEG algoritam, u kojem postoje 64 “+” i 64 “?” operacije po tački (sa optimalnom implementacijom inverznog DCT-a i operacija kvantizacije) . ” (bez uzimanja u obzir RLE koraka i Huffmanovog kodiranja!). U ovom slučaju, za fraktalni algoritam, množenje se dešava racionalnim brojem, po jedan za svaki blok. To znači da možemo, kao prvo, koristiti cjelobrojnu racionalnu aritmetiku, koja je znatno brža od aritmetike s pomičnim zarezom. Drugo, množenje vektora brojem je jednostavnija i brža operacija, često ugrađena u arhitekturu procesora (SGI procesori, Intel MMX...), nego skalarni proizvod dva vektora potreban u slučaju JPEG-a. Za sliku u punoj boji situacija se ne mijenja kvalitativno, jer oba algoritma koriste konverziju u drugi prostor boja.
Procjena gubitaka i načini njihovog regulacije
At sažetak pojednostavljena verzija algoritma je propustila mnoga važna pitanja. Na primjer, što učiniti ako algoritam ne može pronaći sličan za određeni fragment slike? Prilično očigledno rješenje je razbiti ovaj fragment na manje i pokušati ih potražiti. Istovremeno, jasno je da se ovaj postupak ne može ponavljati beskonačno, inače će broj potrebnih transformacija postati toliko velik da će algoritam prestati biti algoritam kompresije. Stoga dopuštamo gubitke u nekom dijelu slike.
Za algoritam fraktalne kompresije, kao i za druge algoritme kompresije sa gubicima, veoma su važni mehanizmi pomoću kojih se može podesiti stepen kompresije i stepen gubitka. Do danas je razvijen prilično veliki skup takvih metoda. Prvo, možete ograničiti broj afinskih transformacija, svjesno osiguravajući da stupanj kompresije nije niži od fiksne vrijednosti. Drugo, možete zahtijevati da u situaciji kada je razlika između obrađenog fragmenta i njegove najbolje aproksimacije iznad određene granične vrijednosti, ovaj fragment mora biti zdrobljen (za njega se mora instalirati nekoliko „leća“). Treće, možete zabraniti cijepanje fragmenata manjih od, recimo, četiri točke. Promjenom graničnih vrijednosti i prioriteta ovih uvjeta, moći ćemo vrlo fleksibilno kontrolirati omjer kompresije slike u rasponu od bitskog podudaranja do bilo kojeg nivoa kompresije. Imajte na umu da će ova fleksibilnost biti mnogo veća od fleksibilnosti njegovog najbližeg “konkurenta” - JPEG algoritma.
Karakteristike fraktalnog algoritma :
Omjeri kompresije: 2-2000 (korisnički definirano).
Klasa slike: 24-bitne slike u punoj boji ili slike u nijansama sive bez oštrih prelaza boja (fotografije). Poželjno je da područja većeg značaja (za percepciju) budu kontrastnija i oštrija, a područja manjeg značaja treba da budu niskog kontrasta i zamućena.
simetrija: 100-100000
karakteristike: Može slobodno skalirati sliku prilikom otkopčavanja, povećavajući je 2-4 puta bez pojave “efekta stepenica”. Kako se stepen kompresije povećava, na ivicama blokova na slici pojavljuje se efekat „blokiranja“.
Rekurzivni (talasni) algoritamEngleski naziv za rekurzivnu kompresiju je wavelet. Na ruski se prevodi kao kompresija talasa, i kao kompresija pomoću rafala. Ova vrsta arhiviranja poznata je dosta dugo i direktno proizilazi iz ideje korištenja koherentnosti područja. Algoritam je fokusiran na kolor i crno-bijele slike s glatkim prijelazima. Idealan za slike tipa rendgenskih zraka. Omjer kompresije je podešen i varira od 5-100. Kada pokušate postaviti veći koeficijent na oštrim granicama, posebno onima koje se kreću dijagonalno, pojavljuje se "efekat stepenica" - stepenice različite svjetline veličine nekoliko piksela.
Ideja algoritma je da razliku spremamo u datoteku - broj između prosječnih vrijednosti susjednih blokova na slici, koji obično uzima vrijednosti bliske 0.
Dakle, dva broja a 2i I a 2i +1 uvijek može biti predstavljen u obliku b 1 i=(a 2i +a 2i +1 )/2 i b 2 i=(a 2i -a 2i +1 )/2. Sličan niz a imogu se prevesti u parovima u niz b 1.2i.
Hajde da to sredimo konkretan primjer: Komprimirajmo niz vrijednosti svjetline od 8 piksela ( a i): (220, 211, 212, 218, 217, 214, 210, 202). Dobićemo sledeće sekvence b 1 i, And b 2 i: (215,5, 215, 215,5, 206) i (4,5, -3, 1,5, 4). Imajte na umu da vrijednosti b 2 isu prilično blizu 0. Ponovimo operaciju, uzimajući u obzir b 1 i Kako a i. Ova akcija se izvodi rekurzivno, otuda i naziv algoritma. Dobijamo iz (215,5, 215, 215,5, 206): (215,25, 210,75) (0,25, 4,75). Rezultirajuće koeficijente, zaokružene na cijele brojeve i komprimirane, na primjer, koristeći Huffman algoritam sa fiksnim tabelama, možemo staviti u datoteku.
Imajte na umu da smo našu transformaciju na lanac primijenili samo dva puta. U stvarnosti, možemo sebi priuštiti korištenje talasne transformacije 4-6 puta. Štaviše, dodatna kompresija se može postići korištenjem tablica Huffmanovog algoritma s neujednačenim razmacima (tj. morat ćemo pohraniti Huffmanov kod za najbližu vrijednost u tabeli). Ove tehnike vam omogućavaju da postignete primjetne omjere kompresije.
vježba: Vratili smo lanac (215, 211) (0, 5) (5, -3, 2, 4) iz datoteke (vidi primjer). Napravite niz od osam vrijednosti svjetline piksela koje će algoritam kompresije valova ponovo kreirati.
Algoritam za dvodimenzionalne podatke implementiran je na sličan način. Ako imamo kvadrat od 4 tačke sa svjetlinama a 2 i, 2 j,a 2 i +1 , 2 j,a 2 i, 2 j +1, And a 2 i +1 , 2 j +1, To
| Original | B 1 | B 2 | |
| slika | B 3 | B 4 |
Koristeći ove formule, za sliku veličine 512x512 piksela, nakon prve transformacije dobijamo 4 matrice veličine 256x256 elemenata:
-- 
Prvi će, kao što možete pretpostaviti, pohraniti malu kopiju slike. U drugom - prosječne razlike između parova vrijednosti piksela horizontalno. U trećem - prosječne razlike između parova vrijednosti piksela duž vertikale. U četvrtom - prosječne razlike u vrijednostima piksela duž dijagonale. Po analogiji sa dvodimenzionalnim slučajem, možemo ponoviti našu transformaciju i dobiti 4 matrice veličine 128x128 umjesto prve matrice. Ponavljajući našu transformaciju treći put, na kraju ćemo dobiti: 4 matrice 64x64, 3 matrice 128x128 i 3 matrice 256x256. U praksi, prilikom pisanja u datoteku, vrijednosti dobijene u posljednjem redu () se obično zanemaruju (odmah se dobiva povećanje od oko trećine veličine datoteke - 1- 1/4 - 1/16 - 1/64 ...).
Prednosti ovog algoritma uključuju činjenicu da vrlo lako omogućava postupno „razvijanje“ slike prilikom prijenosa slike preko mreže. Osim toga, pošto zapravo pohranjujemo manju kopiju slike na vrhu slike, to olakšava prikazivanje "zumirane" slike po naslovu.
Za razliku od JPEG-a i fraktalnog algoritma, ova metoda ne radi u blokovima, na primjer, 8x8 piksela. Tačnije, radimo sa blokovima 2x2, 4x4, 8x8 itd. Međutim, zbog činjenice da nezavisno spremamo koeficijente za ove blokove, vrlo lako možemo izbjeći cijepanje slike na „mozaične“ kvadrate.
Karakteristike talasnog algoritma:
Omjeri kompresije: 2-200 (korisnički definirano).
Klasa slike: Kao fraktal i JPEG.
simetrija: ~1.5
karakteristike: Osim toga, uz visok stepen kompresije, slika se raspada u zasebne blokove.
Zaključak
U zaključku, pogledajmo tabele koje sumiraju parametre različitih algoritama kompresije slike o kojima smo gore raspravljali.
| Algoritam | Karakteristike slike zbog kojih dolazi do kompresije |
| RLE | Uzastopne identične boje: 2 2 2 2 2 2 15 15 15 |
| LZW | Identični podlanci: 2 3 15 40 2 3 15 40 |
| Huffman | Različite frekvencije boja: 2 2 3 2 2 4 3 2 2 2 4 |
| CCITT-3 | Prevlast bijela na slici, velike površine ispunjene jednom bojom |
| Rekurzivno | Glatki prijelazi boja i bez oštrih granica |
| JPEG | Nema oštrih granica |
| Fraktal | Sličnost između elemenata slike |
| Algoritam | Kompleti za kompresiju | Vremenska simetrija | Za što orijentisan |
Gubici | Dimenzija |
| RLE | 32, 2, 0.5 | 1 | 3.4 bit | br | 1D |
| LZW | 1000, 4, 5/7 | 1.2-3 | 1-8 bit | br | 1D |
| Huffman | 8, 1.5, 1 | 1-1.5 | 8 bit | br | 1D |
| CCITT-3 | 213(3), 5, 0.25 | ~1 | 1-bit | br | 1D |
| JBIG | 2-30 puta | ~1 | 1-bit | br | 2D |
| JPEG bez gubitaka | 2 puta | ~1 | 24-bitna, siva | br | 2D |
| JPEG | 2-20 puta | ~1 | 24-bitna, siva | Da | 2D |
| Rekurzivna kompresija | 2-200 puta | 1.5 | 24-bitna, siva | Da | 2D |
| Fraktal | 2-2000 puta | 1000-10000 | 24-bitna, siva | Da | 2.5D |
JPEG i JPEG2000"
Završeno:
učenik grupe 819
Ugarov Dmitry
Principi rada JPEG i JPEG2000 algoritama
1. JPEG algoritam
JPEG (Joint Photographic Experts Group) je široko korištena metoda za kompresiju fotografskih slika. Format datoteke koji sadrži komprimirane podatke obično se naziva i JPEG; Najčešće ekstenzije za takve datoteke su .jpeg, .jfif, .jpg, .JPG ili .JPE. Međutim, od njih, .jpg je najpopularnija ekstenzija na svim platformama.
JPEG algoritam je kompresijski algoritam sa gubitkom kvaliteta.
Područje primjene
Format je format kompresije sa gubitkom, tako da je pogrešno misliti da JPEG čuva podatke kao 8 bita po kanalu (24 bita po pikselu). S druge strane, pošto su JPEG kompresovani i dekomprimovani podaci tipično predstavljeni u 8 bitova po kanalu, ova terminologija se ponekad koristi. Kompresija crno-bijelih polutonskih slika je također podržana.
Prilikom snimanja JPEG datoteke možete odrediti stepen kvaliteta, a time i stepen kompresije, koji se obično navodi u nekim konvencionalnim jedinicama, na primjer, od 1 do 100 ili od 1 do 10. Veći broj odgovara boljem kvalitetu , ali se veličina datoteke povećava. Obično se okom praktički ne percipira razlika u kvaliteti između 90 i 100. Treba imati na umu da se bit-po-bit obnovljena slika uvijek razlikuje od originala. Uobičajena zabluda je to JPEG kvaliteta identičan udjelu pohranjenih informacija.
Faze kodiranja
Proces kompresije JPEG-a uključuje nekoliko koraka:
1. Pretvorite sliku u optimalni prostor boja;
Ako se koristi prostor boja luma/hrominance (YCbCr), postiže se bolji omjer kompresije. U ovoj fazi kodiranja, koristeći odgovarajuće relacije model u boji RGB pretvoren u YCbCr:
Y = 0,299*R + 0,587*G + 0,114*B
Cb = - 0,1687*R – 0,3313*G + 0,5*B
Cr = 0,5*R – 0,4187*G – 0,0813*B.
Tokom dekodiranja možete koristiti odgovarajuću inverznu transformaciju:
R = Y + 1,402*Cr
G = Y – 0,34414*Cb – 0,71414*Cr
B = Y + 1,772*Cb.
Napomena o Y,Cb,Cr u ljudskom vizuelnom sistemu:
Oko, posebno mrežnica, ima dvije vrste ćelija kao vizualnih analizatora: ćelije noćnog vida koje percipiraju samo nijanse sive (od svijetlo bijele do tamno crne) i ćelije dnevnog vida koje percipiraju nijansu boja. Prve ćelije, koje proizvode RGB boju, detektuju nivo osvetljenosti sličan vrednosti Y. Druge ćelije, odgovorne za percepciju nijanse, određuju vrednost povezanu sa razlikom u boji.
2. Poduzorkovanje komponenti boja usrednjavanjem grupa piksela;
Većina vizuelnih informacija na koje je ljudsko oko najosjetljivije sastoji se od visokofrekventnih komponenti osvjetljenja u sivim tonovima (Y) YCbCr prostora boja. Druge dvije hromatske komponente (Cb i Cr) sadrže informacije o boji visoke frekvencije na koje je ljudsko oko manje osjetljivo. Stoga se određeni dio može odbaciti i time smanjiti broj piksela koji se uzimaju u obzir za kanale boja.
1) upišite 4:2:0 (kada je slika podijeljena na kvadrate od 2x2 piksela i u svakom od njih svi pikseli primaju iste vrijednosti Cb i Cr kanala, a svjetlina Y ostaje različita za svaki)
2) tip 4:2:2 (kombinacija po komponentama hromatičnosti se javlja samo horizontalno u grupama od dva piksela).
3) Tip 4:4:4 znači da svaki piksel u svakom redu ima svoju jedinstvenu vrijednost Y, Cb i Cr komponenti. (Slika 1 a)
4) tip 4:2:2. Poduzorkovanjem signala hrominacije sa faktorom 2 horizontalno, dobijamo od 4:4:4 YCbCr toka 4:2:2 YCbCr toka. Unos "4: 2: 2" znači da u jednom redu postoje 4 vrijednosti svjetline za 2 vrijednosti hromatike (vidi sliku 1 b). Signal 4:2:2 YCbCr je vrlo malo inferioran u kvalitetu slike u odnosu na 4:4:4 YCbCr signal, ali je potrebna širina pojasa smanjena za 33% od originala.
3. Primjena diskretnih kosinusnih transformacija za smanjenje redundantnosti slikovnih podataka;
Glavna faza algoritma je diskretna kosinusna transformacija (DCT ili DCT), koja je vrsta Fourierove transformacije. Koristi se pri radu sa slikama u različite svrhe, a ne samo u svrhu kompresije. Prijelaz na frekvencijski prikaz vrijednosti piksela omogućava nam da drugačije pogledamo sliku, obradimo je i, što je za nas zanimljivo, komprimiramo je. Štoviše, znajući koeficijente konverzije, uvijek možemo izvršiti suprotnu akciju - vratiti originalnu sliku.
DCT direktno primijenjen na blok (u našem slučaju 8x8 piksela) slike će izgledati ovako:
gdje su x, y prostorne koordinate piksela (0..7),
f(x,y) - vrijednosti piksela originalnog makrobloka (na primjer, svjetlina)
u,v - koordinate piksela u frekvencijskoj predstavi (0..7)
w(u) =1/SQRT(2) za u=0, u ostalim slučajevima w(u)=1 (SQRT - kvadratni korijen)
w(v) =1/SQRT(2) za v=0, u ostalim slučajevima w(v)=1
Ili u matričnom obliku:
4. Kvantizacija svakog bloka DCT koeficijenata korištenjem težinskih funkcija optimiziranih uzimajući u obzir ljudsku vizualnu percepciju;
Diskretna kosinusna transformacija priprema informacije za kompresiju sa gubicima i zaokruživanje. Za svaki element matrice koji se transformiše postoji odgovarajući element matrice kvantizacija. Rezultirajuća matrica se dobiva dijeljenjem svakog elementa matrice koja se transformira odgovarajućim elementom matrice kvantizacije i zatim zaokruživanjem rezultata na najbliži cijeli broj. Prilikom sastavljanja matrice kvantizacije, njeni veliki elementi se nalaze u donjem lijevom uglu, tako da se prilikom dijeljenja njima podaci u ovom kutu nakon diskretne kosinusne transformacije (upravo oni čije će zaokruživanje biti manje bolno) grublje zaokružuju. Shodno tome, izgubljene informacije su nam manje važne od preostalih informacija.
5. Sekundarni stupanj kompresije
Posljednja faza JPEG kodera je kodiranje rezultirajuće matrice.
5.1 Cik-cak permutacija 64 DCT koeficijenta
Dakle, nakon što smo izvršili DCT transformaciju na 8x8 bloku vrijednosti, imamo novi blok 8x8. Zatim se ovaj blok 8x8 prelazi u cik-cak obrascu ovako:
(Brojevi u bloku 8x8 označavaju redoslijed kojim skeniramo 2-dimenzionalnu matricu 8x8)
0, 1, 5, 6,14,15,27,28,
2, 4, 7,13,16,26,29,42,
3, 8,12,17,25,30,41,43,
9,11,18,24,31,40,44,53,
10,19,23,32,39,45,52,54,
20,22,33,38,46,51,55,60,
21,34,37,47,50,56,59,61,
35,36,48,49,57,58,62,63
Kao što vidite, prvo je gornji lijevi ugao (0,0), zatim vrijednost na (0,1), zatim (1,0), pa (2,0), (1,1), (0, 2), (0,3), (1,2), (2,1), (3,0) itd.
Nakon što prođemo cik-cak kroz matricu 8x8, sada imamo vektor sa 64 koeficijenta (0..63).Poenta ovog cik-cak vektora je da gledamo kroz 8x8 DCT koeficijente u redoslijedu povećanja prostornih frekvencija. Dakle, dobijamo vektor sortiran po kriterijumima prostorne frekvencije: prva vrednost na vektoru (indeks 0) odgovara najnižoj frekvenciji na slici - označava se terminom DC. Kako indeks na vektoru raste, dobijamo vrijednosti koje odgovaraju višim frekvencijama (vrijednost sa indeksom 63 odgovara amplitudi visoka frekvencija u bloku 8x8). Ostali DCT koeficijenti su označeni sa AC.
5.2 RunLength nulto kodiranje (RLE)
Sada imamo vektor sa dugim nizom nula. Ovo možemo koristiti kodiranjem uzastopnih nula. VAŽNO: Kasnije ćete vidjeti zašto, ali ovdje preskačemo kodiranje prvog vektorskog koeficijenta (DC koeficijenta), koji je kodiran drugačije. Zamislite originalni vektor 64 kao vektor 63 (ovo je vektor 64 bez prvog koeficijenta)
Recimo da imamo 57,45,0,0,0,0,23,0,-30,-16,0,0,1,0,0,0,0,0,0, samo 0,... .0
Evo kako se radi RLC JPEG kompresija za ovaj primjer:
(0,57); (0,45); (4,23); (1,-30); (0,-16); (2.1); EOB
Kao što možete vidjeti, za svaku vrijednost različitu od 0 kodiramo broj uzastopnih VODEĆIH nula prije vrijednosti, a zatim dodajemo vrijednost. Još jedna napomena: EOB je kratka forma za kraj bloka, to je posebna kodirana vrijednost (marker). Ako smo došli do pozicije na vektoru od koje imamo samo vektorske nule do kraja, dodijelit ćemo tu poziciju sa EOB-om i kompletnom RLC kompresijom kvantiziranog vektora.
[Imajte na umu da ako kvantizirani vektor nije nul-terminiran (ima posljednji element ne 0), nećemo imati EOB token.]
(0,57); (0,45); (4,23); (1,-30); (0,-16); (2,1); (0,0)
Još jedna OSNOVNA stvar: Recimo negdje na kvantiziranom vektoru koji imamo:
57, osamnaest nula, 3, 0,0 ,0,0 2, trideset tri nule, 895, EOB
JPG Huffman kodiranje postavlja ograničenje da broj vodećih nula mora biti kodiran kao 4-bitna vrijednost ne može premašiti 15.
Dakle, prethodni primjer bi trebao biti kodiran kao:
(0,57); (15,0) (2,3); (4,2); (15,0) (15,0) (1,895), (0,0)
(15,0) je posebna kodirana vrijednost koja označava da slijedi 16 uzastopnih nula.
5.3 Završni korak - Huffmanovo kodiranje
Prvo VAŽNA napomena: Umjesto pohranjivanja stvarne vrijednosti, JPEG standard navodi da pohranjujemo minimalnu veličinu bita na kojoj možemo zadržati ovu vrijednost (ovo se zove kategorija ove vrijednosti), a zatim bit-kodirani prikaz ove vrijednosti Volim ovo:
7,..,-4,4,..,7 3 000,001,010,011,100,101,110,111
15,..,-8,8,..,15 4 0000,..,0111,1000,..,1111
31,..,-16,16,..,31 5 00000,..,01111,10000,..,11111
63,..,-32,32,..,63 6 .
127,..,-64,64,..,127 7 .
255,..,-128,128,..,255 8 .
511,..,-256,256,..,511 9 .
1023,..,-512,512,..,1023 10 .
2047,..,-1024,1024,..,2047 11 .
4095,..,-2048,2048,..,4095 12 .
8191,..,-4096,4096,..,8191 13 .
16383,..,-8192,8192,..,16383 14 .
32767,..,-16384,16384,..,32767 15 .
Nakon toga za prethodni primjer:
(0,57); (0,45); (4,23); (1,-30); (0,-8); (2,1); (0,0)
kodirajmo samo desnu vrijednost ovih parova, osim parova koji su posebni tokeni poput (0,0) ili (ako moramo imati) (15,0)
45, na sličan način, bilo bi kodirano kao (6.101101)
30 -> (5,00001)
A sada ćemo ponovo napisati niz parova:
(0,6), 111001; (0,6), 101101; (4,5), 10111; (1,5), 00001; (0,4), 0111; (2,1), 1; (0,0)
Parovi od 2 vrijednosti zatvoreni u zagradama mogu biti predstavljeni u bajtu, jer u stvari svaka od 2 vrijednosti može biti predstavljena u 4-bitnom komadu (broj vodećih nula je uvijek manji od 15 i isti kao kategorija [brojevi kodirani u JPG fajl- u području -32767..32767]). U ovom bajtu, visoki bit predstavlja broj prethodnih nula, a niži bit predstavlja kategoriju nove vrijednosti koja nije 0.
Posljednji korak kodiranja je da Huffman kodira ovaj bajt, a zatim snimi u JPG datoteku, kao tok bitova, Huffmanov kod ovog bajta, nakon čega slijedi prikaz ovog broja u bitovima.
Na primjer, za bajt 6 (ekvivalentno (0,6)) imamo Huffman kod = 111000;
21 = (1,5) - 11111110110
4 = (0,4) - 1011
33 = (2,1) - 11011
0 = EOB= (0,0) - 1010
Konačni bitstream napisan u JPG datoteci na disk za prethodni primjer je 63 koeficijenta (zapamtite da smo preskočili prvi koeficijent) -
111000 111001 111000 101101 1111111110011001 10111 11111110110 00001
1011 0111 11011 1 1010
Prednosti i nedostaci
Nedostaci formata uključuju činjenicu da se pri visokim nivoima kompresije, struktura blok podataka osjeća sama po sebi, slika je "podijeljena na kvadrate" (svaki veličine 8x8 piksela). Ovaj efekat je posebno primetan u oblastima niske prostorne frekvencije (glatki prelazi slike, npr. čisto nebo). U područjima s visokom prostornom frekvencijom (na primjer, kontrastne ivice slike), pojavljuju se karakteristični "artefakti" - nepravilna struktura piksela s izobličenom bojom i/ili svjetlinom. Osim toga, mali detalji u boji nestaju sa slike. To takođe ne treba zaboraviti ovaj format ne podržava transparentnost.
Međutim, uprkos svojim nedostacima, JPEG je postao veoma raširen zbog svog visokog stepena kompresije u odnosu na alternative koje su postojale u vreme njegovog uvođenja.
2. JPEG2000 algoritam
Algoritam JPEG-2000 razvila je ista grupa stručnjaka za fotografiju koja je razvila JPEG. Formiranje JPEG kao međunarodni standard završena je 1992. Godine 1997. postalo je jasno da je potreban novi, fleksibilniji i moćniji standard, koji je finaliziran do zime 2000. godine.
Glavne razlike između algoritma u JPEG 2000 i algoritma u JPEG-u su sljedeće:
1) Bolji kvalitet slike sa visokim stepenom kompresije. Ili, što je ista stvar, veći omjer kompresije sa istim kvalitetom za visoke omjere kompresije. U stvari, to znači primjetno smanjenje veličine grafike "web kvaliteta" koju koristi većina web lokacija.
2) Podrška za kodiranje pojedinačnih područja sa boljim kvalitetom. Poznato je da su određena područja slike kritična za ljudsku percepciju (na primjer, oči na fotografiji), dok se kvalitet drugih može žrtvovati (na primjer, pozadina). Sa “ručnom” optimizacijom, stepen kompresije se povećava sve dok se kvalitet ne izgubi u nekom važnom dijelu slike. Sada postaje moguće postaviti kvalitet u kritična područja, jače kompresujući druga područja, tj. dobijamo još veći konačni omjer kompresije uz subjektivno jednak kvalitet slike.
3) Glavni algoritam kompresije je zamijenjen waveletom. Pored navedenog povećanja omjera kompresije, ovo je omogućilo da se riješimo blokade od 8 piksela koja se javlja kada se poveća omjer kompresije. Osim toga, glatki razvoj slike sada je u početku uključen u standard (progresivni JPEG, koji se aktivno koristi na Internetu, pojavio se mnogo kasnije od JPEG-a).
4) Za povećanje omjera kompresije, algoritam koristi aritmetičku kompresiju. U početku je JPEG standard uključivao i aritmetičku kompresiju, ali je to kasnije zamijenjeno manje efikasnom Huffman kompresijom jer je aritmetička kompresija bila zaštićena patentima. Sada je glavni patent istekao i postoji prilika za poboljšanje algoritma.
5) Podržava kompresiju bez gubitaka. Pored uobičajene kompresije sa gubicima, novi JPEG će sada podržavati kompresiju bez gubitaka. Tako to postaje moguća upotreba JPEG za kompresiju medicinskih slika, u štampanju, prilikom čuvanja teksta za prepoznavanje od strane OCR sistema itd.
6) Podržava kompresiju jednobitnih (2-bojnih) slika. Za čuvanje jednobitnih slika (crteži mastilom, skenirani tekst, itd.), GIF format je ranije bio široko preporučljiv, jer je DCT kompresija vrlo neefikasna za slike sa oštrim prelazima boja. U JPEG-u, kada se kompresuje, 1-bitna slika je konvertovana u 8-bitnu, tj. povećao za 8 puta, nakon čega je učinjen pokušaj kompresije, često manje od 8 puta. Sada možemo preporučiti JPEG 2000 kao univerzalni algoritam.
7) Transparentnost je podržana na nivou formata. Glatko blendajte pozadinu prilikom kreiranja WWW stranice sada će to biti moguće ne samo u GIF, već iu JPEG 2000. Osim toga, nije podržan samo 1 bit transparentnosti (piksel je transparentan/neproziran), već i poseban kanal, koji će vam omogućiti da postavite glatka tranzicija od neprozirne slike do prozirne pozadine.
Pored toga, nivo formata podržava uključivanje informacija o autorskim pravima u sliku, podršku za toleranciju grešaka bitova tokom prenosa i emitovanja, i može se tražiti za dekompresiju ili obradu eksterna sredstva(plug-ins), možete uključiti njegov opis, informacije o pretraživanju, itd. u sliku.
Faze kodiranja
Proces kompresije JPEG2000 uključuje nekoliko koraka:
1. Pretvorite sliku u optimalni prostor boja.
U ovoj fazi kodiranja, koristeći odgovarajuće omjere boja RGB model pretvoren u YUV:
Prilikom dekompresije primjenjuje se odgovarajuća inverzna transformacija:
2. Diskretna talasna transformacija.
Diskretno wavelet konverzija(DWT) takođe može biti dva tipa - za slučaj kompresije sa gubicima i za kompresiju bez gubitaka.
Ova transformacija u jednodimenzionalnom slučaju je skalarni proizvod odgovarajućih koeficijenata i niza vrijednosti. Ali zato mnogi koeficijenti su nula, tada se direktna i inverzna wavelet transformacija može napisati sljedećim formulama (za transformaciju ekstremnih elemenata linije koristi se njeno proširenje za 2 piksela u svakom smjeru, čije su vrijednosti simetrične s vrijednosti elemenata linije u odnosu na njene ekstremne piksele):
y(2*n + 1) = x(2*n + 1) - (int)(x(2*n) + x(2*n + 2)) / 2
y(2*n) = x(2*n) + (int)(y(2*n - 1) + y(2*n + 1) + 2) / 4
i obrnuto
x(2*n) = y(2*n) - (int)(y(2*n - 1) + y(2*n + 1) + 2) / 4
x(2*n + 1) = y(2*n + 1) + (int)(x(2*n) + x(2*n + 2)) / 2.
3. Kvantizacija koeficijenata.
Baš kao i JPEG algoritam, kvantizacija se koristi kada se slika kodira u JPEG2000 format. Diskretna talasna transformacija, kao i njen analog, sortira koeficijente po frekvenciji. Ali, za razliku od JPEG-a, u novom formatu postoji jedna matrica kvantizacije za cijelu sliku.
4. Sekundarni stupanj kompresije
. Kao i JPEG, posljednji korak u algoritmu kompresije u novom formatu je kodiranje bez gubitaka. Ali, za razliku od prethodnog formata, JPEG2000 koristi algoritam aritmetičke kompresije.
Implementacija softvera
U ovom radu implementirani su algoritmi JPEG i JPEG2000. Oba algoritma implementiraju unaprijed i obrnuto kodiranje (ne postoji završna faza sekundarna kompresija). JPEG proračun traje dosta vremena (oko 30 sekundi) zbog "direktnog" izračunavanja DCT-a. Ako trebate povećati brzinu rada, prvo bi trebali izračunati DCT matricu (promjene treba izvršiti u DCT klasi).
Pređimo na program:
Nakon pokretanja, pojavljuje se prozor gdje
a možete ga sačuvati klikom na dugme (2) i unosom željenog imena u dijalog box. Uz dovoljno veliki faktor kvalitete, slika će se uvelike promijeniti. Ako je ovo JPEG algoritam, tada će blokovi veličine 8x8 biti jasno vidljivi (u slučaju JPEG2000 algoritma, neće biti podjele blokova)
nakon:
