Algoritam je 1991. razvila Joint Photographic Expert Group posebno za komprimiranje 24-bitnih slika i slika u sivim tonovima. Ovaj algoritam ne sažima dobro dvorazinske slike, ali dobro radi na slikama kontinuiranog tona u kojima bliski pikseli obično imaju slične boje. Oko obično ne može primijetiti nikakvu razliku kada se komprimira ovom metodom 10 ili 20 puta.
Algoritam se temelji na DCT primijenjenom na matricu disjunktnih blokova slike od 8x8 piksela. DCT rastavlja te blokove prema amplitudama određenih frekvencija. Rezultat je matrica u kojoj su mnogi koeficijenti, u pravilu, blizu nule, što se može prikazati u grubom numeričkom obliku, tj. u kvantiziranom obliku bez značajnog gubitka kvalitete restauracije.
Razmotrimo detaljnije rad algoritma. Pretpostavimo da se komprimira 24-bitna slika u punoj boji. U ovom slučaju dobivamo sljedeće faze rada.
Korak 1. Sliku pretvaramo iz RGB prostora u YCbCr prostor koristeći sljedeći izraz:
Odmah napomenimo da se inverzna transformacija lako dobiva množenjem inverzna matrica u vektor, koji je u biti YUV prostor:
.
Korak 2. Podijelili smo izvornu sliku na matrice 8x8. Od svake formiramo tri radne DCT matrice - 8 bita zasebno za svaku komponentu. Pri visokim omjerima kompresije, blok 8x8 se rastavlja na komponente YCbCr u formatu 4:2:0, tj. komponente za Cb i Cr uzimaju se kroz točku u redovima i stupcima.
3. korak Primjena DCT-a na blokove slike veličine 8x8 piksela. Formalno, direktni DCT za blok 8x8 može se napisati kao
Gdje 
. Budući da je DCT "srce" JPEG algoritma, u praksi ga je poželjno izračunati što je brže moguće. Jednostavan pristup ubrzanju izračuna je unaprijed izračunati kosinusne funkcije i tabelirati rezultate. Š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 transponirana matrica i radi istu stvar, ali za blok retke. Rezultat je separabilna transformacija, koja se u matričnom obliku piše kao
Ovdje je rezultat DCT-a, čiji izračun zahtijeva operacije množenja i gotovo isto toliko zbrajanja, što je znatno manje od izravnih izračuna pomoću gornje formule. Na primjer, za pretvaranje slike veličine 512x512 piksela trebat će vam aritmetičke operacije. Uzimajući u obzir 3 komponente svjetline, dobivamo vrijednost od 12 582 912 aritmetičkih operacija. Broj množenja i zbrajanja 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 zbrajanja i pomaka bitova.
Kao rezultat DCT-a dobivamo matricu u kojoj su koeficijenti lijevo gornji kut odgovaraju niskofrekventnoj komponenti slike, au donjem desnom dijelu - visokofrekventnoj.
Korak 4. Kvantizacija. U ovom koraku neke informacije se odbacuju. Ovdje se svaki broj iz matrice dijeli s posebnim brojem iz "kvantizacijske tablice", a rezultat se zaokružuje na najbliži cijeli broj:
.
Štoviše, za svaku matricu Y, Cb i Cr možete postaviti vlastite tablice kvantizacije. JPEG standard čak dopušta korištenje vlastitih kvantizacijskih tablica, koje će se, međutim, morati prenijeti u dekoder zajedno s komprimiranim 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 kvantizacijske matrice. Prvi je da JPEG standard uključuje dvije preporučene kvantizacijske tablice: jednu za svjetlinu i jednu za boju. Ove tablice prikazane su u nastavku. Drugi pristup je sintetizirati (izračun u hodu) kvantizacijsku tablicu koja ovisi o jednom parametru koji je odredio korisnik. Sama tablica je izgrađena prema formuli
Faza kvantizacije je mjesto gdje se kontrolira omjer kompresije i gdje se javljaju najveći gubici. Jasno je da ćemo određivanjem kvantizacijskih tablica s velikim koeficijentima dobiti više nula, a time i veći omjer kompresije.
Specifični učinci algoritma također su povezani s kvantizacijom. Pri velikim vrijednostima koraka kvantizacije, gubici mogu biti toliko veliki da se slika raspada na monokromatske kvadrate 8x8. Zauzvrat, gubici u visokim frekvencijama mogu se manifestirati u takozvanom "Gibbsovom efektu", kada se oko kontura formira valoviti "halo" s oštrim prijelazom boja.
Korak 5. Matricu 8x8 pretvaramo u vektor od 64 elementa pomoću cik-cak skeniranja (slika 2).
Riža. 2. Cik-cak skeniranje
Kao rezultat toga, koeficijenti različiti od nule u pravilu će biti zapisani na početku vektora, a lanci nula će se formirati na kraju.
Korak 6. Vektor transformiramo pomoću modificiranog RLE algoritma, čiji izlaz su parovi tipa (preskoči, broj), gdje je “preskoči” brojač preskočenih nula, a “broj” je vrijednost koju treba staviti u sljedeći ćelija. Na primjer, vektor 1118 3 0 0 0 -2 0 0 0 0 1 ... će se sažeti u parove (0, 1118) (0,3) (3,-2) (4,1) ... .
Treba napomenuti da je prvi broj pretvorene komponente u biti jednak prosječnoj svjetlini bloka 8x8 i naziva se DC koeficijent. Isto za sve blokove slika. Ova okolnost sugerira da se DC koeficijenti mogu učinkovito komprimirati ako se ne sjećate njihovih apsolutnih vrijednosti, već relativnih 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 koeficijenata istosmjerne struje može se napraviti, na primjer, ovako (slika 3). Ostali koeficijenti, koji se nazivaju AC koeficijenti, ostaju nepromijenjeni.
Korak 7 Rezultirajuće parove konvolviramo pomoću neuniformnih Huffmanovih kodova s fiksnom tablicom. Štoviše, za DC i AC koeficijente, različite šifre, tj. različite tablice s Huffmanovim kodovima.
Riža. 3. Shema sređivanja istosmjernih koeficijenata
Riža. 4. Blok dijagram JPEG algoritma
Proces obnove slike u ovom algoritmu potpuno je simetričan. Metoda vam omogućuje komprimiranje slika 10-15 puta bez primjetnih gubitaka vida.
Pri razvoju ovog standarda vodili smo se činjenicom da ovaj algoritam morao je komprimirati slike prilično brzo - ne više od minute na prosječnoj slici. Ovo je 1991.! A njegova hardverska implementacija trebala bi biti relativno jednostavna i jeftina. U ovom slučaju, algoritam je morao biti simetričan u vremenu rada. Izvođenje 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. Iskorištavajući to, proizvođači stvaraju vlastite formate koji su međusobno nekompatibilni i stoga mogu promijeniti algoritam. Stoga su interne tablice algoritama koje preporučuje ISO zamijenjene njihovim vlastitim. Postoje i JPEG opcije za posebne aplikacije.
JPEG je jedan od najnovijih i prilično moćnih algoritama. U praksi, to je "de facto" standard za slike u boji. Algoritam radi na 8x8 područjima u kojima se svjetlina i boja relativno glatko mijenjaju. Kao rezultat toga, pri rastavljanju matrice takvog područja u dvostruki niz u kosinusima (formule u nastavku), značajni su samo prvi koeficijenti. Stoga se JPFG kompresija postiže izglađivanjem promjena boja na slici.
Algoritam je razvila skupina fotografskih stručnjaka posebno za komprimiranje 24-bitnih JPEG slika - Joint Photographic Expert Group - odjel unutar ISO-a - Međunarodne organizacije za standardizaciju. Općenito, algoritam se temelji na diskretnoj kosinusnoj transformaciji (u daljnjem tekstu DCT) primijenjenoj na matricu slike kako bi se dobila nova matrica koeficijenata. Za dobivanje izvorne slike primjenjuje se inverzna transformacija
DCT rastavlja sliku prema amplitudama određenih frekvencija, pa se tijekom transformacije dobiva matrica u kojoj su mnogi koeficijenti ili blizu nule ili jednaki nuli. Osim, ljudski sustav percepcija boja slabo prepoznaje određene frekvencije. Stoga je neke koeficijente moguće grublje aproksimirati bez primjetnog gubitka kvalitete slike.
U tu svrhu koristi se kvantizacija koeficijenata. U samom jednostavan slučaj je aritmetički bitni pomak udesno. Ovom pretvorbom gube se neke informacije, ali se mogu postići veliki omjeri kompresije.
Rad algoritma.
Neka 24-bitna slika bude komprimirana.
Korak I.
Pretvaramo sliku iz RGB prostora boja, s komponentama odgovornim za crvenu, zelenu i plavu komponentu boje točke, u YCrCb prostor boja (ponekad zvan YUV).
U njemu je Y komponenta svjetline, a Cr, Cb komponente odgovorne za boju (kromatska crvena i kromatska plava). Zbog činjenice da je ljudsko oko manje osjetljivo na boju nego na svjetlinu, postaje moguće arhivirati nizove za komponente Cr i Cb s velikim gubicima i, sukladno tome, velikim omjerima kompresije. Ova vrsta pretvorbe već se 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 provodi množenjem YUV vektora inverznom matricom:
Korak 2.
Podijelili smo izvornu sliku na matrice 8x8. Od svake formiramo tri radne DCT matrice - 8 bita zasebno za svaku komponentu. Kod viših omjera 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 upisuju kroz red i kroz stupac. Oni. od originalne 16x16 matrice, dobiva se samo jedna radna DCT matrica. Iako je lako primijetiti, gubimo 3/4 korisna informacija o komponentama boje slike i odmah dobiti dvostruku kompresiju. To možemo učiniti radom u YCrCb prostoru. Na nastaloj RGB slika, kao što je praksa pokazala, to nema jak učinak.
3. korak
DCT primjenjujemo na svaku radnu matricu. U ovom slučaju dobivamo matricu u kojoj koeficijenti u gornjem lijevom kutu odgovaraju niskofrekventnoj komponenti slike, au donjem desnom - visokofrekventnoj.
U pojednostavljenom obliku, ova se transformacija može prikazati na sljedeći način:
Korak 4.
Provodimo kvantizaciju. U principu, ovo je jednostavno dijeljenje radne matrice s kvantizacijskom matricom element po element. Za svaku komponentu (Y, U i V), u općem slučaju, određena je vlastita kvantizacijska matrica (u daljnjem tekstu MC).
U ovom koraku se kontrolira omjer kompresije i gdje se javljaju najveći gubici. Jasno je da ćemo specificiranjem MK s velikim koeficijentima dobiti više nula, a time i veći stupanj kompresije.
Specifični učinci algoritma također su povezani s kvantizacijom. Za velike vrijednosti koeficijenata gama , - gubici u nižim frekvencijama mogu biti toliko veliki da se slika raspada na 8x8 kvadrata. Gubici u visokim frekvencijama mogu se manifestirati u takozvanom "Gibbsovom učinku", kada se oko kontura formira neka vrsta "aureole" s oštrim prijelazom boja.
Korak 5.
Matricu 8x8 pretvaramo u vektor od 64 elementa pomoću cik-cak skeniranja, tj. odaberite elemente s indeksima (0.0). (0,1). (1,0). (2.0)...
Dakle, na početku vektora dobivamo koeficijente matrice koji odgovaraju niske frekvencije, a na kraju - vis.
Korak 6.
Sažimamo vektor pomoću algoritma grupnog kodiranja. U ovom slučaju dobivamo parove tipa (preskoči, broj), gdje je "preskoči" brojač preskočenih nula, a "broj" je vrijednost koju treba staviti u sljedeću ćeliju.
Dakle, vektor će biti sažet u parove (0, 42) (0, 3) (3, -2) (4, 1)
Korak 7
Sažimamo naučene parove koristeći Huffmanovo kodiranje s fiksnom tablicom.
Proces obnove slike u ovom algoritmu potpuno je simetričan. Metoda vam omogućuje komprimiranje nekih slika 10-15 puta bez ozbiljnih gubitaka.
Cjevovod operacija korišten u JPEG algoritmu.
Bitno pozitivni aspekti Algoritam je sljedeći:
- 1) Postavlja omjer kompresije
- 2) Slobodan dan slika u boji može imati 24 bita po točki.
Negativni aspekti algoritma su sljedeći:
- 1) Kako se razina kompresije povećava, slika se raspada u zasebne kvadrate (8x8). To je zbog činjenice da se tijekom kvantizacije javljaju veliki gubici na niskim frekvencijama i postaje nemoguće vratiti izvorne podatke.
- 2) Pojavljuje se Gibbsov učinak - aureole duž granica oštrih prijelaza boja.
JPEG je standardiziran relativno nedavno - 1991. Ali čak i tada su postojali algoritmi koji su jače komprimirali s manjim gubitkom kvalitete. Činjenica je da su radnje standardnih programera bile ograničene snagom tehnologije koja je postojala u to vrijeme. Odnosno, čak i na osobnom računalu, algoritam je morao raditi manje od minute na prosječnoj slici, a njegova hardverska implementacija morala je biti relativno jednostavna i jeftina. Algoritam je morao biti simetričan (vrijeme raspakiranja približno je jednako vremenu arhiviranja).
Potonji zahtjev omogućio je pojavu digitalnih kamera - uređaja veličine male video kamere koji snimaju 24-bitne fotografije na flash karticu od 10-20 MB s PCMCIA sučeljem. Zatim se kartica umetne u utor na prijenosnom računalu i odgovarajući program omogućuje čitanje slika. Da je algoritam asimetričan, bilo bi neugodno dugo čekati da se uređaj "napuni" i komprimira sliku.
Još jedno ne baš ugodno svojstvo JPEG-a je često horizontalno i okomite pruge potpuno su nevidljivi na zaslonu i mogu se pojaviti samo pri ispisu u obliku moiré uzorka. To se događa kada se kosi ispisni raster postavi na vodoravne i okomite pruge slike. Zbog ovih iznenađenja, JPEG se ne preporučuje za aktivnu upotrebu u ispisu, postavljanje visokih koeficijenata. Međutim, kod arhiviranja i slika namijenjenih ljudskom gledanju, jest ovaj trenutak nezamjenjiva.
Široka upotreba JPEG-a dugo je bila ograničena, možda, samo činjenicom da radi na 24-bitnim slikama. Stoga, kako biste vidjeli sliku prihvatljive kvalitete na redoviti monitor u paleti od 256 boja, zahtijevao korištenje odgovarajućih algoritama i, stoga, Određeno vrijeme. U aplikacijama namijenjenim zahtjevnim korisnicima, poput igara, takva su kašnjenja neprihvatljiva. Osim toga, ako imate slike, recimo, u 8-bitnom GIF formatu, pretvorene u 24-bitni JPEG, a zatim natrag u GIF za gledanje, tada će se gubitak kvalitete dogoditi dva puta tijekom obje pretvorbe. Međutim, dobitak u veličini arhive često je toliko velik (3-20 puta!), a gubitak u kvaliteti tako mali da je pohranjivanje slika u JPEG vrlo učinkovito.
Treba reći nekoliko riječi o modifikacijama ovog algoritma. Iako je JPEG ISO standard, njegov format datoteke nije popravljen. Iskorištavajući to, proizvođači koriste svoje vlastite formate koji su međusobno nekompatibilni, te stoga mogu promijeniti algoritam. Dakle, tablice internih algoritama koje preporučuje ISO. zamjenjuju oni svojima.. Osim toga, postoji mala zabuna kod postavljanja stupnja gubitaka. Na primjer, tijekom testiranja pokazalo se da "izvrsna" kvaliteta, "100%" i "10 bodova" daju značajno različite slike. Usput, "100%" kvaliteta ne znači kompresiju bez gubitaka. Postoje i JPEG opcije za posebne aplikacije.
Kako se ISO standard JPEG sve više koristi u razmjeni slika računalne mreže. JPEG algoritam je podržan u formatima Quick Time, PostScript Level 2, Tiff 6.0 i trenutno zauzima istaknuto mjesto u multimedijskim sustavima.
Karakteristike JPFG algoritma:
Omjeri kompresije: 2-200 (korisnički definirano).
Klasa slike: 24-bitne slike u boji ili slike u sivim tonovima bez oštrih prijelaza boja (fotografije).
Simetrija: 1.
Karakteristične značajke: U nekim slučajevima algoritam stvara "aureolu" oko oštrih vodoravnih i okomitih granica na slici (Gibbsov efekt). Osim toga, s visokim stupnjem kompresije, slika je podijeljena u blokove od 8x8 piksela.
- Tutorial
UPD. Bio sam prisiljen ukloniti monospace formatiranje. Jednog lijepog dana, habraparser je prestao prihvaćati formatiranje unutra oznake pre i kod. Cijeli tekst se pretvorio u kašu. Uprava Habra mi nije mogla pomoći. Sada je neravnomjerno, ali je barem čitljivo.
Jeste li ikada htjeli znati kako funkcionira jpg datoteka? Shvatimo sada! Zagrijte svoj omiljeni prevodilac i heksadecimalni uređivač, dekodirat ćemo ovo:
Namjerno sam uzeo manji crtež. Ovo je poznati, ali jako komprimirani Google favicon:
Odmah vas upozoravam da je opis pojednostavljen i da navedene informacije nisu potpune, ali kasnije će biti lako razumjeti specifikaciju.
Čak i ne znajući kako se kodiranje događa, već možemo izvući nešto iz datoteke.
- startni marker. Uvijek je na početku svih jpg datoteka.
Slijede bajtovi
. Ovo je oznaka koja označava početak odjeljka komentara. Sljedeća 2 bajta
- duljina odjeljka (uključujući ova 2 bajta). Dakle u sljedeća dva
- sam komentar. To su znakovni kodovi ":" i ")", tj. obični emotikon. Možete ga vidjeti u prvom redu na desnoj strani hex uređivača.
Malo teorije
Vrlo ukratko korak po korak:
Razmislimo o redoslijedu kojim se ti 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 pričekati da se cijela slika učita prije nego što se pojavi na ekranu. Također će biti neugodno ako se kraj datoteke izgubi. Vjerojatno postoje i drugi dobri razlozi. Stoga se kodirani podaci slažu jedan po jedan, u male dijelove. 
Dopustite 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 datoteke
Nakon što izdvojimo komentar, bit će lako razumjeti sljedeće:- Datoteka je podijeljena na sektore kojima prethode oznake.
- Markeri su dugi 2 bajta, a prvi bajt je .
- Gotovo svi sektori pohranjuju svoju duljinu u sljedeća 2 bajta nakon oznake.
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 - kvantizacijska tablica.
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 je. Zaglavlje se sastoji od:
Duljina: 0x43 = 67 bajtova
Duljina vrijednosti u tablici: 0 (0 - 1 bajt, 1 - 2 bajta)
[_0]
ID tablice: 0
Preostala 64 bajta trebaju ispuniti tablicu 8x8.
Pažljivije pogledajte redoslijed kojim se popunjavaju vrijednosti tablice. Ovaj poredak se naziva cik-cak redoslijed: 
Marker: SOF0 - osnovni DCT
Ovaj marker se zove SOF0 i znači da je slika kodirana pomoću osnovne metode. Vrlo je čest. Ali ne manje popularna na Internetu je poznata progresivna metoda, kada se slika prvo učitava iz niske rezolucije, a onda normalna slika. To vam omogućuje da bez čekanja razumijete što je tamo prikazano 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
Duljina: 17 bajtova.
Preciznost: 8 bita. U osnovnoj metodi uvijek je 8. Koliko ja razumijem, ovo je dubina bita vrijednosti kanala.
Visina slike: 0x10 = 16
Širina figure: 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 kvantizacijske tablice: 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 kvantizacijske tablice: 1
Sada pogledajte kako odrediti koliko je slika tanka. Nalazimo H max =2 i V max =2. Kanal i bit će stanjen za H max /H i puta vodoravno i V max /V i puta okomito.
Marker: DHT (Huffmanova tablica)
Ovaj odjeljak pohranjuje kodove i vrijednosti dobivene Huffmanovim kodiranjem.FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02
duljina: 21 bajt.
klasa: 0 (0 - tablica DC koeficijenata, 1 - tablica AC koeficijenata).
[_0]
ID tablice: 0
Duljina Huffmanovog koda: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Broj kodova:
Pod brojem kodova podrazumijeva se broj kodova te duljine. Imajte na umu da odjeljak pohranjuje samo duljine kodova, a ne same kodove. Sami moramo pronaći kodove. Dakle, imamo jedan kod duljine 1 i jedan duljine 2. Ukupno 2 koda, nema više kodova u ovoj tablici.
Svaki kod ima pridruženu vrijednost, a one su navedene u datoteci kako slijedi. Vrijednosti su jednobajtne, tako da čitamo 2 bajta.
- vrijednost 1. šifre.
- vrijednost 2. šifre.
Konstrukcija Huffmanovog kodnog stabla
Moramo izgraditi binarno stablo iz tablice koju smo dobili u odjeljku DHT. I iz ovog stabla prepoznajemo svaki kod. Dodajemo vrijednosti redoslijedom kojim su navedene u tablici. Algoritam je jednostavan: bez obzira u kojem 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šu razinu i pokušavamo od tamo. Trebate stati na razini jednaka duljini kodirati. Lijeve grane odgovaraju vrijednosti 0, desne - 1.Komentar:
Ne morate svaki put krenuti od vrha. Dodana vrijednost - povratak na višu razinu. Postoji li prava grana? Ako da, idite ponovno gore. Ako ne, stvorite desnu granu i idite tamo. Zatim, od ove točke, počnite tražiti kako biste dodali sljedeću vrijednost.
Stabla za sve tablice 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 prolazeći stazom od vrha do svakog čvora). Ovim kodovima (ove i drugih tablica) kodiran je sam sadržaj slike.
Oznaka: SOS (početak skeniranja)
Bajt u markeru znači „DA! Napokon smo prešli izravno na analizu odjeljka kodirane slike!” No rubrika je simbolično nazvana SOS. FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00
Dužina dijela zaglavlja (ne cijele sekcije): 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 završava dio zaglavlja, odavde do kraja (marker) su kodirani podaci.
0
Određivanje DC koeficijenta.
1.
Čitanje niza bitova (ako naiđemo na 2 bajta, onda to nije marker, već samo bajt). Nakon svakog bita, krećemo se po Huffmanovom stablu (s pripadajućim identifikatorom) duž grane 0 ili 1, ovisno o pročitanom bitu. Zaustavljamo se ako se nađemo na završnom čvoru.
10
1011101110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je jednak 0, onda je koeficijent jednak 0, upisujemo to u tablicu i prelazimo na očitavanje ostalih koeficijenata. U našem slučaju - 02. Ova vrijednost je duljina koeficijenta u bitovima. Odnosno, čitamo sljedeća 2 bita, to će biti koeficijent.
10
10
11101110011101100001111100100
3. Ako je prva znamenka vrijednosti u binarni prikaz- 1, zatim ostavite kako jest: DC_coef = vrijednost. U suprotnom transformiramo: DC_coef = value-2 value length +1 . Koeficijent upisujemo u tablicu na početku cik-cak - gornji lijevi kut.
Određivanje AC koeficijenata.
1.
Slično koraku 1, pronalaženje DC koeficijenta. Nastavljamo čitati niz:
10
10
1110
1110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je 0, to znači da preostale vrijednosti matrice moraju biti popunjene nulama. Zatim se kodira sljedeća matrica. Prvih nekoliko koji pročitaju dovde i napišu mi o tome u osobnoj poruci dobit će plus u karmi. U našem slučaju, vrijednost čvora je 0x31.
Prvi grickanje: 0x3 - to je točno koliko nula moramo dodati matrici. To su 3 nula koeficijenta.
Drugi nibble: 0x1 - duljina koeficijenta u bitovima. Pročitajte sljedeći dio.
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 ispuni.
U našem slučaju dobit ćemo:
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 se pri visokim stupnjevima kompresije beznačajni koeficijenti 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 prethodne tablice (isti kanal)! Matrice je potrebno ispraviti:
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 vrijedi do kraja datoteke.
... a 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]
Budući da postoji samo jedna matrica, DC koeficijenti se mogu ostaviti netaknuti.
Izračuni
Kvantizacija
Sjećate li se da matrica prolazi kroz fazu kvantizacije? Elementi matrice moraju se pomnožiti član po član s elementima kvantizacijske matrice. Ostaje samo odabrati onu koja vam je potrebna. Prvo smo skenirali prvu komponentu, njezina komponenta slike = 1. Komponenta slike s ovim ID-om koristi matricu kvantizacije 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 tome, dobivamo 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 matricom 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 rezultirajuća matrica koeficijenata. u - stupac, v - red. s yx - izravno vrijednosti kanala.
*Općenito govoreći, to nije sasvim točno. Kada sam uspio dekodirati i prikazati sliku 16x16 na ekranu, uzeo sam sliku 600x600 (usput, ovo je bila naslovnica omiljenog albuma Mind.In.A.Boxa - Lost Alone). Nije uspjelo odmah - pojavile su se razne greške. Uskoro sam se mogao diviti ispravno učitanoj slici. Jedina stvar koja me stvarno uznemirila je brzina preuzimanja. Još se sjećam da je trajalo 7 sekundi. Ali to nije iznenađujuće, ako nepromišljeno koristite gornju formulu, tada ćete za izračun jednog kanala od jednog piksela morati pronaći 128 kosinusa, 768 množenja i neke dodatke. Razmislite samo o tome - gotovo tisuću teških operacija na samo jednom kanalu jednog piksela! Srećom, ima prostora za optimizaciju (nakon mnogo eksperimentiranja, smanjio sam vrijeme učitavanja na granicu točnosti timera od 15ms, a nakon toga promijenio sliku u fotografiju 25 puta veće površine. Možda o tome pišem u poseban članak).
Napisat ću rezultat izračuna 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 jesti!
- Da, uopće se ne useljavam, o čemu mi pričamo.
- Nakon što se dobiju vrijednosti YCbCr boja, sve što preostaje je pretvoriti ih u RGB, ovako: YCbCrToRGB(Y ij, Cb ij, Cr ij) , Y ij, Cb ij, Cr ij - naše rezultirajuće matrice.
- 4 Y matrice, te po jedna Cb i Cr, pošto smo prorijedili 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 oduzima dio procesorskog vremena.
Ovdje su dobivene tablice 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
Općenito, nisam stručnjak za JPEG, pa teško mogu odgovoriti na sva pitanja. Samo što sam, dok sam pisao svoj dekoder, često imao posla s raznim stvarima neshvatljivi problemi. A kada je slika bila netočno prikazana, nisam znao gdje sam pogriješio. Možda je krivo protumačio bitove ili je možda krivo upotrijebio DCT. Jako mi je nedostajalo korak po korak primjer, stoga 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 s algoritmima arhiviranja s gubicimaKonvencionalni algoritmi prvi su korišteni za arhiviranje slika. Oni koji su se koristili i koriste u backup sustavima, prilikom izrade distribucija itd. Ovi su algoritmi arhivirali informacije nepromijenjene. Međutim, glavni trend u posljednje vrijeme je korištenje novih klasa slika. Stari algoritmi više ne zadovoljavaju zahtjeve arhiviranja. Mnoge slike praktički nisu komprimirane, iako su "na prvi pogled" imale očitu suvišnost. To je dovelo do stvaranja nove vrste algoritma - kompresije s gubitkom informacija. U pravilu se može postaviti koeficijent arhiviranja, a time i stupanj gubitka kvalitete u njima. Ovo stvara kompromis između veličine i kvalitete slike.
Jedan od ozbiljnih problema računalne grafike je što još nije pronađen adekvatan kriterij za procjenu gubitaka kvalitete slike. I stalno se gubi - tijekom digitalizacije, tijekom prevođenja u ograničenu paletu boja, tijekom prevođenja u drugi sustav prikaza boja za tisak i, što je za nas posebno važno, tijekom arhiviranja s gubicima. Može se dati primjer jednostavnog kriterija: standardna devijacija vrijednosti piksela (L 2 mjera, ili root mean square - 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). U isto vrijeme, slike sa "snijegom" - oštra promjena boje pojedinačne točke, slabe pruge ili "moiré" smatrat će se "gotovo nepromijenjenim" (Objasnite zašto?). I drugi kriteriji imaju svoje neugodne strane.
Uzmite u obzir, na primjer, maksimalno odstupanje:
Ova je mjera, kao što možete pretpostaviti, iznimno osjetljiva na otjecanje pojedinačnih piksela. Oni. Na cijeloj slici može se značajno promijeniti samo vrijednost jednog piksela (što je oku gotovo neprimjetno), no prema ovoj mjeri slika će biti jako oštećena.
Mjera koja se sada koristi u praksi naziva se omjer signala i šuma između vrha i vrha (PSNR).
Ova je mjera u biti slična standardnoj devijaciji, ali je nešto prikladnija za korištenje zbog logaritamske skale ljestvice. Ima iste nedostatke kao i standardna devijacija.
Naše su oči najbolji sudac gubitka kvalitete slike. Arhiviranje se smatra izvrsnim ako je okom nemoguće razlikovati izvorne od nearhiviranih slika. Dobra stvar je što kada možete reći koja je od slika arhivirana, možete usporediti samo dvije susjedne slike. Daljnjim povećanjem omjera kompresije u pravilu postaju vidljive nuspojave karakteristične za ovaj algoritam. U praksi, čak i uz izvrsno očuvanje kvalitete, na slici se mogu redovito raditi određene promjene. Stoga se ne preporučuje korištenje algoritama arhiviranja s gubitkom prilikom komprimiranja slika koje će se kasnije ili ispisati visoka kvaliteta, ili obrađeni programima za prepoznavanje slika. Neugodni efekti kod takvih slika, 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čki de facto standard za slike u boji. Algoritam radi na 8x8 područjima u kojima se svjetlina i boja relativno glatko mijenjaju. Kao rezultat toga, kada se matrica takve površine rastavlja na dvostruki niz u kosinusima (vidi formule u nastavku), značajni su samo prvi koeficijenti. Stoga se JPEG kompresija postiže glatkom promjenom boja na slici.
Algoritam je razvila skupina fotografskih stručnjaka posebno za komprimiranje 24-bitnih slika. JPEG - Joint Photographic Expert Group - odjel unutar ISO-a - Međunarodne organizacije za standardizaciju. Naziv algoritma glasi ["jei"peg]. Općenito, algoritam se temelji na diskretnoj kosinusnoj transformaciji (u daljnjem tekstu DCT) primijenjenoj na matricu slike kako bi se dobila nova matrica koeficijenata. Za dobivanje izvorne slike primjenjuje se inverzna transformacija.
DCT rastavlja sliku prema amplitudama određenih frekvencija. Tako pri transformaciji dobivamo matricu u kojoj su mnogi koeficijenti ili blizu nule ili jednaki nuli. Osim toga, zbog nesavršenosti ljudskog vida, moguće je grublje aproksimirati koeficijente bez zamjetnog gubitka kvalitete slike.
U tu svrhu koristi se kvantizacija koeficijenata. U najjednostavnijem slučaju, to je aritmetički pomak udesno. Ovom pretvorbom gube se neke informacije, ali se mogu postići veliki omjeri kompresije.
Kako algoritam radi
Dakle, pogledajmo algoritam detaljnije. Komprimirajmo 24-bitnu sliku.
Korak 1.
Pretvaramo sliku iz RGB prostora boja, s komponentama odgovornim za crvenu, zelenu i plavu komponentu boje točke, u YCrCb prostor boja (ponekad zvan YUV).
U njemu je Y komponenta svjetline, a Cr, Cb komponente odgovorne za boju (kromatska crvena i kromatska plava). Zbog činjenice da je ljudsko oko manje osjetljivo na boju nego na svjetlinu, postaje moguće arhivirati nizove za komponente Cr i Cb s velikim gubicima i, sukladno tome, visokim omjerima kompresije. Ova vrsta pretvorbe već se 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 prikazati pomoću prijelazne matrice:
Inverzna transformacija se provodi množenjem YUV vektora inverznom matricom.
Korak 2.
Podijelili smo izvornu sliku na matrice 8x8. Od svake formiramo tri radne DCT matrice - 8 bita zasebno za svaku komponentu. Kod viših omjera 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 upisuju kroz red i kroz stupac. Oni. od originalne 16x16 matrice, dobiva se samo jedna radna DCT matrica. U ovom slučaju, kao što je lako vidjeti, gubimo 3/4 korisnih informacija o komponentama boja slike i odmah dobivamo dvostruku kompresiju. To možemo učiniti radom u YCrCb prostoru. Kao što je praksa pokazala, to nema značajan učinak na rezultirajuću RGB sliku.
3. korak
DCT primjenjujemo na svaku radnu matricu. U ovom slučaju dobivamo matricu u kojoj koeficijenti u gornjem lijevom kutu odgovaraju niskofrekventnoj komponenti slike, au donjem desnom - visokofrekventnoj.
U pojednostavljenom obliku, ova se transformacija može prikazati na sljedeći način:
Korak 4.
Izvodimo kvantizaciju. U principu, ovo je jednostavno dijeljenje radne matrice s kvantizacijskom matricom element po element. Za svaku komponentu (Y, U i V), u općem slučaju, određena je vlastita kvantizacijska matrica q (u daljnjem tekstu MC).
U ovom koraku se kontrolira omjer kompresije i gdje se javljaju najveći gubici. Jasno je da ćemo specificiranjem MK s velikim koeficijentima dobiti više nula, a time i veći stupanj kompresije.
Specifični učinci algoritma također su povezani s kvantizacijom. Pri visokim gama vrijednostima gubitak u niskim frekvencijama može biti toliko velik da se slika raspada na kvadrate 8x8. Gubici u visokim frekvencijama mogu se manifestirati u takozvanom "Gibbsovom efektu", kada se oko kontura formira neka vrsta "aureole" s oštrim prijelazom boja.
Korak 5.
Matricu 8x8 pretvaramo u vektor od 64 elementa koristeći "cik-cak" skeniranje, tj. uzeti elemente s indeksima (0,0), (0,1), (1,0), (2,0)...
Dakle, na početku vektora dobivamo koeficijente matrice koji odgovaraju niskim frekvencijama, a na kraju - visokim.
Korak 6.
Sažimamo vektor pomoću algoritma grupnog kodiranja. U ovom slučaju dobivamo parove tipa (preskoči, broj), gdje je "preskoči" brojač preskočenih nula, a "broj" je vrijednost koju treba staviti u sljedeć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
Sažimamo dobivene parove koristeći Huffmanovo kodiranje s fiksnom tablicom.
Proces obnove slike u ovom algoritmu potpuno je simetričan. Metoda vam omogućuje komprimiranje nekih slika 10-15 puta bez ozbiljnih gubitaka.
Cjevovod operacija korišten u JPEG algoritmu.
Značajni pozitivni aspekti algoritma su sljedeći:
- Postavlja omjer kompresije.
- Slobodan dan slika u boji može imati 24 bita po točki.
- Kako se razina kompresije povećava, slika se raspada na pojedinačne kvadrate (8x8). To je zbog činjenice da se tijekom kvantizacije javljaju veliki gubici na niskim frekvencijama i postaje nemoguće vratiti izvorne podatke.
- Pojavljuje se Gibbsov efekt - aureole duž granica oštrih prijelaza boja.
Potonji zahtjev omogućio je pojavu igračaka kao što su digitalne kamere- uređaji veličine male video kamere koji snimaju 24-bitne fotografije na flash karticu od 10-20 MB s PCMCIA sučeljem. Zatim se ta kartica umetne u utor na vašem prijenosnom računalu i odgovarajući program vam omogućuje č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š ugodno svojstvo JPEG-a je da su vodoravne i okomite pruge na zaslonu često potpuno nevidljive i mogu se pojaviti samo kada su ispisane u obliku moiré uzorka. To se događa kada se kosi ispisni raster postavi na vodoravne i okomite pruge slike. Zbog ovih iznenađenja, JPEG se ne preporučuje za aktivnu upotrebu u ispisu, postavljanje visokih koeficijenata. No, kod arhiviranja slika namijenjenih ljudskom gledanju trenutno je neizostavan.
Široka upotreba JPEG-a dugo je bila ograničena, možda, samo činjenicom da radi na 24-bitnim slikama. Dakle, da bi se na običnom monitoru prikazala slika prihvatljive kvalitete u paleti od 256 boja, bila je potrebna upotreba odgovarajućih algoritama, a time i određeno vrijeme. U aplikacijama namijenjenim zahtjevnim korisnicima, poput igara, takva su kašnjenja neprihvatljiva. Osim toga, ako imate slike, recimo, u 8-bitnom GIF formatu, pretvorene u 24-bitni JPEG, a zatim natrag u GIF za gledanje, tada će se gubitak kvalitete dogoditi dva puta tijekom obje pretvorbe. Međutim, dobitak u veličini arhive često je toliko velik (3-20 puta!), a gubitak u kvaliteti tako mali da je pohranjivanje slika u JPEG vrlo učinkovito.
Treba reći nekoliko riječi o modifikacijama ovog algoritma. Iako je JPEG ISO standard, njegov format datoteke nije popravljen. Iskorištavajući to, proizvođači stvaraju vlastite formate koji su međusobno nekompatibilni i stoga mogu promijeniti algoritam. Stoga su interne tablice algoritama koje preporučuje ISO zamijenjene njihovim vlastitim. Osim toga, postoji mala zabuna pri postavljanju stupnja gubitka. Na primjer, tijekom testiranja pokazalo se da "izvrsna" kvaliteta, "100%" i "10 bodova" daju značajno različite slike. Istodobno, usput, "100%" kvaliteta ne znači kompresiju bez gubitaka. Postoje i JPEG opcije za posebne aplikacije.
Kao ISO standard, JPEG se sve više koristi za razmjenu slika na računalnim mrežama. JPEG algoritam je podržan u formatima Quick Time, PostScript Level 2, Tiff 6.0 i trenutno zauzima istaknuto mjesto u multimedijskim sustavima.
Karakteristike algoritma JPEG:
Klasa slike: 24-bitne slike u boji ili slike u sivim tonovima bez oštrih prijelaza boja (fotografije).
Simetrija: 1
Karakteristike: U nekim slučajevima algoritam stvara "aureolu" oko oštrih vodoravnih i okomitih granica na slici (Gibbsov efekt). Osim toga, s visokim stupnjem kompresije, slika je podijeljena u blokove od 8x8 piksela.
Fraktalni algoritamIdeja metode
Fraktalno arhiviranje temelji se na tome da sliku prikazujemo u kompaktnijem obliku - pomoću koeficijenata Iterated Function System (dalje u 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 pretvaranje jedne slike u drugu. Točke u trodimenzionalnom prostoru (x_koordinata, y_koordinata, svjetlina) prolaze kroz transformaciju.
Ovaj proces je najjasnije pokazao Barnsley u svojoj knjizi “Fractal Image Compression”. Tamo je uveden koncept fotokopirnog stroja koji se sastoji od zaslona na kojem je prikazana originalna slika i sustava leća koje projiciraju sliku na drugi zaslon:
- Objektivi mogu projicirati dio slike slobodan oblik na bilo koje drugo mjesto na novoj slici.
- regije u kojem slike se projiciraju ne sijeku se.
- Objektiv može promijeniti svjetlinu i smanjiti kontrast.
- Objektiv može zrcaliti i rotirati fragment vaše slike.
- Leće mora mjeriti(smanjite) svoj fragment slike.
Raspoređivanjem leća i mijenjanjem njihovih karakteristika možemo kontrolirati dobivenu sliku. Jedna iteracija rada Stroja je da se nova gradi iz izvorne slike pomoću dizajna, nakon čega se nova uzima kao početna. Tvrdi se da ćemo tijekom procesa iteracije dobiti sliku koja se neće mijenjati. Ovisit će samo o položaju i karakteristikama leća, a ne o izvornoj slici. Ova slika se zove " fiksna točka" ili atraktor dati IFS. Odgovarajuća teorija jamči da postoji točno jedna fiksna točka za svaki IFS.
Budući da je preslikavanje leće kompresivno, svaka leća eksplicitno specificira sebi sličan područja na našoj slici. Zahvaljujući samosličnosti dobivamo složenu strukturu slike pri svakom povećanju. Stoga je intuitivno definirati sustav funkcija koje se mogu ponoviti fraktalni(nestrogo - sebi sličan matematički objekt).
Dvije najpoznatije slike dobivene korištenjem IFS-a su “trokut Sierpinskog” i “Paprat Barnsley”. “Sierpinskijev trokut” definiraju tri, a “Barnsleyjevu paprat” četiri afine transformacije (ili, u našoj terminologiji, “leće”). Svaka transformacija kodirana je doslovno u nekoliko bajtova, dok slika konstruirana pomoću njih može zauzeti nekoliko megabajta.
Vježba: Odredite 4 područja na slici čije bi sjedinjenje pokrivalo cijelu sliku, a svako bi bilo slično cijeloj slici (ne zaboravite stabljiku paprati).
Iz gore navedenog postaje jasno kako arhiver radi i zašto oduzima toliko vremena. Zapravo, fraktalna kompresija je traženje sebi sličnih područja na slici i određivanje parametara afine transformacije za njih.
=>
U najgorem slučaju, ako se ne koristi optimizirajući algoritam, bit će potrebno nabrojati i usporediti sve moguće fragmente slike različitih veličina. Čak i za male slike, uzimajući u obzir diskretnost, dobivamo astronomski broj opcija koje treba sortirati. Štoviše, čak ni naglo sužavanje klasa transformacije, na primjer, zbog skaliranja samo određenog broja puta, ne daje zamjetan dobitak u vremenu. Osim toga, kvaliteta slike se gubi. Velika većina istraživanja u području fraktalne kompresije sada je usmjerena na smanjenje vremena arhiviranja potrebnog za dobivanje visokokvalitetne slike.
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. Točka je takva da se zove fiksna točka(atraktor) transformacija.
Definicija. Pretvoriti u metrički prostor(X, d) nazivamo kontrakcijom ako postoji broj s: , tako da
Komentar: Formalno, možemo koristiti bilo koje preslikavanje 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 cijelom metričkom prostoru (X, d). Tada postoji točno jedna fiksna točka ove transformacije, a za bilo koju točku niz 
konvergira u .
Općenitija formulacija ovog teorema jamči konvergenciju.
Definicija. Slika je funkcija S definirana na jediničnom kvadratu i uzima vrijednosti od 0 do 1 ili
Neka je trodimenzionalna afina transformacija zapisana u obliku
i definiran je na kompaktnom podskupu kartezijanskog kvadrata x. Tada će prenijeti dio površine S na područje koje se nalazi s pomakom (e,f) i rotacija određena matricom
Štoviše, ako protumačimo vrijednost S kao i svjetlina odgovarajućih točaka, smanjit će se za str puta (transformacija mora biti kompresijska) i promijenit će se u smicanje q.
Definicija.
Konačan skup W kontraktivne trodimenzionalne afine transformacije definirane na domenama kao što su 
, nazvao sustav iterabilnih funkcija ( IFS).
Sustav iteriranih funkcija jedinstveno je povezan s fiksnom točkom - slikom. Dakle, proces kompresije je pronaći koeficijente sustava, a proces dekompresije je ponavljanje sustava dok se rezultirajuća slika (IFS fiksne točke) ne stabilizira. U praksi je dovoljno 7-16 ponavljanja. Područja će se dalje nazivati rangiran, a područja - domena.
Konstrukcija algoritma
Kao što je već postalo očito iz gore navedenog, glavni zadatak pri komprimiranju s fraktalnim algoritmom je pronaći odgovarajuće afine transformacije. U najopćenitijem slučaju možemo prevesti slikovna područja bilo koje veličine i oblika, ali u ovom slučaju dobivamo astronomski broj ponavljanja različitih fragmenata, koji trenutno nije moguće obraditi niti na superračunalu.
U obrazovna verzija algoritma , navedeno u nastavku, postoje sljedeća ograničenja za područja:
- Sva područja su kvadrati sa stranicama paralelnim sa stranicama slike. Ovo je ograničenje prilično strogo. Zapravo, cijelu raznolikost geometrijskih oblika ćemo aproksimirati samo kvadratima.
- Prilikom prijenosa područja domene u područje ranga, veličina se smanjuje točno dvaput. Ovo uvelike pojednostavljuje i kompresor i dekompresor, jer zadatak skaliranja malih površina nije trivijalan.
- Svi blokovi domena su kvadratni i imaju fiksna veličina. Slika je podijeljena u skup blokova domene pomoću uniformne mreže.
- Zauzeta su područja domene “kroz toč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 dopušteno zrcalni odraz. Ukupan broj mogućih transformacija (računajući prazne) je 8.
- Provodi se vertikalno skaliranje (kompresija) (svjetlina). fiksni broj puta- po 0,75.
Ova ograničenja dopuštaju:
- Izgradite algoritam koji zahtijeva relativno mali broj operacija čak i na prilično velikim slikama.
- Vrlo je kompaktno prikazati podatke za pisanje u datoteku. Zahtijevamo za svaku afinu transformaciju u IFS-u:
- 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 određivanje transformacije simetrije prilikom pretvaranja bloka domene u blok ranga.
- 7-9 bita za postavljanje pomaka svjetline tijekom prijevoda.
Na primjer, za datoteku u sivim tonovima od 256 boja 512x512 piksela s veličinom bloka od 8 piksela, bit će 4096 afinih transformacija (512/8x512/8). Svaki će zahtijevati 3,5 bajta. Stoga, ako je izvorna datoteka zauzimala 262144 (512x512) bajtova (bez zaglavlja), tada će datoteka s koeficijentima zauzimati 14336 bajtova. Faktor arhiviranja - 18 puta. Istodobno, ne uzimamo u obzir da datoteka s koeficijentima također može imati redundanciju i biti arhivirana metodom arhiviranja bez gubitaka, na primjer 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, čiji je koeficijent sličnosti jako različit od 2.
- Algoritam neće moći iskoristiti sličnost objekata na slici, čiji kut između njih nije višekratnik 90 0.
Sam algoritam pakiranja svodi se na nabrajanje svih blokova domene i odabir odgovarajućeg bloka ranga za svaki. Ispod je dijagram ovog algoritma.
za (sve blokove raspona) (
min_udaljenost = MaksimalnaUdaljenost;
R i J= slika->KopirajBlok(i,j);
za (svi blokovi domene) ( // S rotacijama i neg.
current=Trenutne koordinate transformacije;
D=slika->Kopiraj blok(trenutno);
trenutna_udaljenost = R i J.L2udaljenost(D);
if(trenutna_udaljenost< min_distance) {
// Ako su najbolji izgledi lošiji:
min_udaljenost = trenutna_udaljenost;
najbolje = trenutno;
}
) //Sljedeći raspon
Spremi_koeficijente_u_datoteku(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 one koji su prošli transformaciju simetrije), pronalazimo opciju s najmanjom mjerom L 2 (najmanje standardno odstupanje) i spremite 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 izračunava se kao:
,
Gdje r i J- vrijednosti piksela bloka rangiranja ( R), A d i J- vrijednosti piksela bloka domene ( D). U ovom slučaju, mjera se izračunava kao:
.
Ne kalkuliramo korijen od L 2 mjere i nemojte ga dijeliti po n, budući da su ove transformacije monotone i neće nas spriječiti u pronalaženju ekstremuma, međutim, moći ćemo izvesti dvije operacije manje 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 sasvim izračunljive (čak i ako je trebalo nekoliko sati) vrijednosti.
Shema algoritma za dekompresiju slike
Dekompresija algoritma fraktalne kompresije iznimno je jednostavna. Potrebno je provesti nekoliko iteracija trodimenzionalnih afinih transformacija, čiji su koeficijenti dobiveni u fazi kompresije.
Apsolutno bilo koja slika (na primjer, apsolutno crna) može se uzeti kao početna, budući da nam odgovarajući matematički aparat jamči konvergenciju niza slika dobivenih tijekom IFS iteracija na nepokretnu sliku (blisku izvornoj). Obično je za to dovoljno 16 ponavljanja.
Očitajmo koeficijente svih blokova iz datoteke;
Kreirajmo crna slika prava veličina;
Dok (slika ne postane mirna)(
Za (svaki raspon (R))(
D=slika->Kopiraj blok(D_koord_za_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 i J(koji su, kao što smo rekli, u našem konkretnom slučaju kvadrati iste veličine) sekvencijalno, tada se ispostavlja da sekvencijalno ispunjavamo sliku kvadratima particijske mreže koristeći afinu transformaciju.
Kao što se može izračunati, broj operacija po pikselu slike u sivim tonovima tijekom restauracije neobično je mali (N operacija "+", 1 operacija "*", gdje je N broj ponavljanja, 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 točki (s optimalnom implementacijom inverznih DCT i kvantizacijskih operacija) . ” (bez uzimanja u obzir RLE koraka i Huffmanova kodiranja!). U ovom slučaju, za fraktalni algoritam, množenje se događa racionalnim brojem, jedan za svaki blok. To znači da možemo, prvo, koristiti cjelobrojnu racionalnu aritmetiku, koja je znatno brža od aritmetike s pomičnim zarezom. Drugo, množenje vektora brojem jednostavnija je i brža operacija, često ugrađena u procesorsku arhitekturu (SGI procesori, Intel MMX...), od skalarnog produkta dvaju vektora koji je potreban u slučaju JPEG-a. Za sliku u punoj boji situacija se kvalitativno ne mijenja, budući da oba algoritma koriste pretvorbu u drugi prostor boja.
Procjena gubitaka i način njihova reguliranja
Na Sažetak pojednostavljena verzija algoritma propustila je 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čito rješenje je razbiti ovaj fragment na manje i pokušati ih potražiti. Pritom je jasno da se ovaj postupak ne može ponavljati ad infinitum, inače će broj potrebnih transformacija postati toliki da algoritam prestaje biti algoritam kompresije. Stoga dopuštamo gubitke u nekom dijelu slike.
Za algoritam fraktalne kompresije, kao i za druge algoritme kompresije s gubicima, vrlo su važni mehanizmi pomoću kojih se mogu prilagoditi stupanj kompresije i stupanj gubitka. Do danas je razvijen prilično velik skup takvih metoda. Prvo, možete ograničiti broj afinih transformacija, svjesno osiguravajući da stupanj kompresije nije niži od fiksne vrijednosti. Drugo, možete zahtijevati da se u situaciji kada je razlika između obrađenog fragmenta i njegove najbolje aproksimacije iznad određene granične vrijednosti, taj fragment mora zgnječiti (za njega se mora ugraditi nekoliko "leća"). Treće, možete zabraniti cijepanje fragmenata manjih od, recimo, četiri točke. Promjenom vrijednosti praga i prioriteta ovih uvjeta, moći ćemo vrlo fleksibilno kontrolirati omjer kompresije slike u rasponu od usklađivanja po bitovima do bilo koje razine kompresije. Imajte na umu da će ova fleksibilnost biti mnogo veća od one kod njegovog najbližeg "konkurenta" - JPEG algoritma.
Karakteristike fraktalnog algoritma :
Omjeri kompresije: 2-2000 (korisnički definirano).
Klasa slike: 24-bitne slike u boji ili slike u sivim tonovima bez oštrih prijelaza 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 niskog kontrasta i mutna.
Simetrija: 100-100000
Karakteristike: Može slobodno skalirati sliku prilikom raspakivanja, povećavajući je 2-4 puta bez pojave "efekta stubišta". Kako se stupanj kompresije povećava, na granicama blokova na slici pojavljuje se efekt "blokova".
Rekurzivni (valni) algoritamEngleski naziv za rekurzivnu kompresiju je wavelet. Prevedeno je na ruski kao kompresija valova i kao kompresija pomoću praska. Ova vrsta arhiviranja poznata je već dosta dugo i izravno proizlazi iz ideje korištenja koherentnosti područja. Algoritam je fokusiran na slike u boji i crno-bijele slike s glatkim prijelazima. Idealno za rendgenske slike. Omjer kompresije je postavljen i varira od 5-100. Kada pokušate postaviti veći koeficijent na oštrim granicama, posebno onima koje idu dijagonalno, pojavljuje se "efekt stubišta" - stepenice različite svjetline veličine nekoliko piksela.
Ideja algoritma je da spremamo razliku u datoteku - broj između prosječnih vrijednosti susjednih blokova na slici, koji obično ima vrijednosti blizu 0.
Dakle dva broja a 2ja I a 2ja +1 uvijek se može prikazati u obliku b 1 i=(a 2ja +a 2ja +1 )/2 i b 2 i=(a 2ja -a 2ja +1 )/2. Sličan slijed a jamogu se prevesti u paru u niz b 1.2i.
Idemo to riješiti konkretan primjer: Komprimirajmo niz vrijednosti svjetline od 8 piksela ( a ja): (220, 211, 212, 218, 217, 214, 210, 202). Dobit ćemo sljedeće nizove b 1 i, I 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 ja. Ova radnja se izvodi rekurzivno, otuda i naziv algoritma. Dobivamo 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, korištenjem Huffmanovog algoritma s fiksnim tablicama, možemo staviti u datoteku.
Imajte na umu da smo našu transformaciju primijenili na lanac samo dva puta. U stvarnosti, možemo si priuštiti korištenje valićne transformacije 4-6 puta. Štoviše, dodatna kompresija se može postići korištenjem tablica Huffmanovog algoritma s nejednakim razmakom (tj. morat ćemo pohraniti Huffmanov kod za najbližu vrijednost u tablici). Ove tehnike vam omogućuju postizanje zamjetnih omjera kompresije.
Vježba: Vratili smo lanac (215, 211) (0, 5) (5, -3, 2, 4) iz datoteke (vidi primjer). Izgradite niz od osam vrijednosti svjetline piksela koje će algoritam kompresije vala ponovno stvoriti.
Algoritam za dvodimenzionalne podatke implementiran je na sličan način. Ako imamo kvadrat od 4 točke sa svjetlinama a 2 i, 2 j,a 2 i +1 , 2 j,a 2 i, 2 j +1, I a 2 i +1 , 2 j +1, To
| Izvornik | B 1 | B 2 | |
| slika | B 3 | B 4 |
Koristeći ove formule, za sliku od 512x512 piksela, nakon prve transformacije dobivamo 4 matrice veličine 256x256 elemenata:
-- 
Prvi će, kao što možda pretpostavljate, pohraniti malu kopiju slike. U drugom - prosječne razlike između parova vrijednosti piksela vodoravno. U trećem - prosječne razlike između parova vrijednosti piksela duž okomice. U četvrtom - prosječne razlike u vrijednostima piksela duž dijagonale. Po analogiji s dvodimenzionalnim slučajem, možemo ponoviti našu transformaciju i umjesto prve matrice dobiti 4 matrice veličine 128x128. Ponavljajući našu transformaciju treći put, dobit ćemo: 4 matrice 64x64, 3 matrice 128x128 i 3 matrice 256x256. U praksi, prilikom pisanja u datoteku, vrijednosti dobivene u zadnjem retku () obično se zanemaruju (odmah se dobiva dobitak od oko trećine veličine datoteke - 1- 1/4 - 1/16 - 1/64 ...).
Prednosti ovog algoritma uključuju činjenicu da vrlo jednostavno omogućuje postupno “razvijanje” slike prilikom prijenosa slike preko mreže. Osim toga, budući da zapravo spremamo manju kopiju slike na vrhu slike, lakše je prikazati "uvećanu" sliku prema naslovu.
Za razliku od JPEG-a i fraktalnog algoritma, ova metoda ne radi u blokovima, na primjer, 8x8 piksela. Točnije, radimo s blokovima 2x2, 4x4, 8x8 itd. Međutim, zbog činjenice da koeficijente za ove blokove spremamo neovisno, vrlo lako možemo izbjeći dijeljenje slike u kvadrate "mozaika".
Karakteristike valnog algoritma:
Omjeri kompresije: 2-200 (korisnički definirano).
Klasa slike: Poput fraktala i JPEG-a.
Simetrija: ~1.5
Karakteristike: Osim toga, s visokim stupnjem kompresije, slika se razbija u zasebne blokove.
Zaključak
Zaključno, pogledajmo tablice koje sažimaju parametre različitih algoritama za kompresiju slike o kojima smo gore govorili.
| Algoritam | Značajke 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čita frekvencija boja: 2 2 3 2 2 4 3 2 2 2 4 |
| CCITT-3 | Prevlast bijela na slici, velika područja ispunjena jednom bojom |
| Ponavljajući | Glatki prijelazi boja i bez oštrih granica |
| JPEG | Bez oštrih granica |
| Fraktal | Sličnost između elemenata slike |
| Algoritam | Kompleti za kompresiju | Vremenska simetrija | Za što orijentiran |
Gubici | Dimenzija |
| RLE | 32, 2, 0.5 | 1 | 3,4 bita | Ne | 1D |
| LZW | 1000, 4, 5/7 | 1.2-3 | 1-8 bita | Ne | 1D |
| Huffman | 8, 1.5, 1 | 1-1.5 | 8 bita | Ne | 1D |
| CCITT-3 | 213(3), 5, 0.25 | ~1 | 1-bitni | Ne | 1D |
| JBIG | 2-30 puta | ~1 | 1-bitni | Ne | 2D |
| JPEG bez gubitaka | 2 puta | ~1 | 24-bitni, sivi | Ne | 2D |
| JPEG | 2-20 puta | ~1 | 24-bitni, sivi | Da | 2D |
| Rekurzivna kompresija | 2-200 puta | 1.5 | 24-bitni, sivi | Da | 2D |
| Fraktal | 2-2000 puta | 1000-10000 | 24-bitni, sivi | Da | 2.5D |
JPEG i JPEG2000"
Završeno:
student grupe 819
Ugarov Dmitrij
Principi rada algoritama JPEG i JPEG2000
1. JPEG algoritam
JPEG (Joint Photographic Experts Group) široko je korištena metoda za komprimiranje 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 ovih, .jpg je najpopularnije proširenje na svim platformama.
JPEG algoritam je algoritam kompresije uz gubitak kvalitete.
Područje primjene
Format je format kompresije s gubitkom, pa je netočno misliti da JPEG pohranjuje podatke kao 8 bita po kanalu (24 bita po pikselu). S druge strane, budući da su JPEG komprimirani i dekomprimirani podaci obično predstavljeni u formatu od 8 bita po kanalu, ova se terminologija ponekad koristi. Podržana je i kompresija crno-bijelih polutonskih slika.
Prilikom spremanja JPEG datoteke možete odrediti stupanj kvalitete, a time i stupanj 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 boljoj kvaliteti , ali se veličina datoteke povećava. Obično se razlika u kvaliteti između 90 i 100 praktički ne opaža okom. Treba imati na umu da se obnovljena slika bit-po-bit uvijek razlikuje od originala. Uobičajena zabluda je da JPEG kvaliteta identičan udjelu pohranjenih informacija.
Faze kodiranja
Proces JPEG kompresije uključuje nekoliko koraka:
1. Pretvorite sliku u optimalni prostor boja;
Ako se koristi prostor boja svjetline/krominacije (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.
Tijekom 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 koja se odnosi na Y,Cb,Cr u ljudskom vizualnom sustavu:
Oko, posebno mrežnica, ima dvije vrste stanica kao vizualnih analizatora: stanice za noćni vid koje percipiraju samo nijanse sive (od svijetle bijele do tamnocrne) i stanice za dnevni vid koje percipiraju nijanse boja. Prve ćelije, koje proizvode RGB boju, otkrivaju razinu svjetline sličnu vrijednosti Y. Druge ćelije, odgovorne za percepciju nijanse, određuju vrijednost povezanu s razlikom u boji.
2. Poduzorkovanje komponenti boje usrednjavanjem skupina piksela;
Većina vizualnih informacija na koje je ljudsko oko najosjetljivije sastoji se od visokofrekventnih komponenata svjetline u sivim tonovima (Y) YCbCr prostora boja. Druge dvije komponente kromatičnosti (Cb i Cr) sadrže visokofrekventne informacije o boji na koje je ljudsko oko manje osjetljivo. Stoga se određeni dio može odbaciti i time smanjiti broj piksela koji se uzima u obzir za kanale boja.
1) tip 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 kromatičnosti javlja se samo horizontalno u grupama od dva piksela).
3) Vrsta 4:4:4 znači da svaki piksel u svakom redu ima svoju jedinstvenu vrijednost komponenti Y, Cb i Cr. (Sl. 1 a)
4) tip 4:2:2. Poduzorkovanjem signala boje s faktorom 2 horizontalno, dobivamo od 4:4:4 YCbCr toka 4:2:2 YCbCr tok. Unos "4: 2: 2" znači da u jednom retku postoje 4 vrijednosti svjetline za 2 vrijednosti kromatike (vidi sliku 1 b). 4:2:2 YCbCr signal vrlo je neznatno lošiji u kvaliteti slike od 4:4:4 YCbCr signala, ali je potrebna propusnost smanjena za 33% od izvorne.
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 za različite svrhe, ne samo za potrebe kompresije. Prijelaz na frekvencijski prikaz vrijednosti piksela omogućuje nam drugačiji pogled na sliku, obradu i, što nam je zanimljivo, kompresiju. Štoviše, znajući koeficijente pretvorbe, uvijek možemo izvršiti suprotnu radnju - vratiti izvornu sliku.
DCT izravno primijenjen na blok (u našem slučaju 8x8 piksela) slike izgledat će 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 frekvencijskom prikazu (0..7)
w(u) =1/SQRT(2) za u=0, u drugim slučajevima w(u)=1 (SQRT - kvadratni korijen)
w(v) =1/SQRT(2) za v=0, u drugim slučajevima w(v)=1
Ili u obliku matrice:
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 i zaokruživanje s gubitkom. Za svaki element matrice koji se transformira postoji odgovarajući element matrice kvantizacija. Rezultirajuća matrica se dobiva dijeljenjem svakog elementa matrice koji se transformira s odgovarajućim elementom matrice kvantizacije i zatim zaokruživanjem rezultata na najbliži cijeli broj. Pri sastavljanju kvantizacijske matrice njezini veliki elementi nalaze se u donjem lijevom kutu, tako da se pri dijeljenju s njima podaci u tom kutu nakon diskretne kosinusne transformacije (upravo oni čije će zaokruživanje biti manje bolno) grublje zaokružuju. Sukladno tome, izgubljene informacije su nam manje važne od preostalih informacija.
5. Sekundarni stupanj kompresije
Završna 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 bloku vrijednosti 8x8, imamo novi blok 8x8. Zatim se kroz 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, prvi je gornji lijevi kut (0,0), zatim vrijednost na (0,1), zatim (1,0), zatim (2,0), (1,1), (0, 2), (0,3), (1,2), (2,1), (3,0) itd.
Nakon što prođemo cik-cak kroz 8x8 matricu, sada imamo vektor sa 64 koeficijenta (0..63).Smisao ovog cik-cak vektora je da gledamo kroz 8x8 DCT koeficijente prema rastućim prostornim frekvencijama. Dakle, dobivamo vektor razvrstan po kriteriju prostorne frekvencije: prva vrijednost na vektoru (indeks 0) odgovara najnižoj frekvenciji na slici - označava se izrazom DC. Kako se indeks na vektoru povećava, dobivamo vrijednosti koje odgovaraju višim frekvencijama (vrijednost s indeksom 63 odgovara amplitudi visoka frekvencija u bloku 8x8). Ostali DCT koeficijenti označeni su s AC.
5.2 RunLength zero encoding (RLE)
Sada imamo vektor s dugim nizom nula. To možemo koristiti kodiranjem uzastopnih nula. VAŽNO: Kasnije ćete vidjeti zašto, ali ovdje preskačemo kodiranje prvog vektorskog koeficijenta (DC koeficijent), koji je drugačije kodiran. Razmotrite izvorni 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 RLC JPEG kompresija radi za ovaj primjer:
(0,57); (0,45); (4,23); (1,-30); (0,-16); (2.1); EOB
Kao što vidite, kodiramo za svaku vrijednost koja nije 0 broj uzastopnih VODEĆIH nula prije vrijednosti, a zatim dodajemo vrijednost. Još jedna napomena: EOB je skraćenica za End of Block, 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 s EOB-om i dovršiti RLC kompresiju kvantiziranog vektora.
[Imajte na umu da ako kvantizirani vektor nije završen nulom (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 da negdje na kvantiziranom vektoru imamo:
57, osamnaest nula, 3, 0.0 ,0.0 2, trideset tri nule, 895, EOB
JPG Huffmanovo kodiranje postavlja ograničenje da broj vodećih nula mora biti kodiran tako da 4-bitna vrijednost ne smije biti veća od 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 držati ovu vrijednost (ovo se naziva kategorija ove vrijednosti), a zatim bit-kodirani prikaz ove vrijednosti kao 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 .
Naknadno za prethodni primjer:
(0,57); (0,45); (4,23); (1,-30); (0,-8); (2,1); (0,0)
kodirajmo samo desnu vrijednost ovih parova, osim za parove koji su posebni tokeni poput (0,0) ili (ako moramo) (15,0)
45 bi na sličan način bio kodiran 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 u zagradama mogu biti predstavljeni u bajtu, budući da zapravo 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 datoteka- u području -32767..32767]). U ovom bajtu, viši bit predstavlja broj prethodnih nula, a niži bit predstavlja kategoriju nove vrijednosti koja nije 0.
Posljednji korak kodiranja je Huffmanovo kodiranje ovog bajta, a zatim snimanje u JPG datoteku, kao tok bitova, Huffmanov kod ovog bajta, nakon čega slijedi bitna reprezentacija ovog broja.
Na primjer, za bajt 6 (ekvivalent (0,6)) imamo Huffmanov kod = 111000;
21 = (1,5) - 11111110110
4 = (0,4) - 1011
33 = (2,1) - 11011
0 = EOB= (0,0) - 1010
Konačni bitstream zapisan u JPG datoteci na disk za prethodni primjer je 63 koeficijenta (sjetite se da smo preskočili prvi koeficijent) -
111000 111001 111000 101101 1111111110011001 10111 11111110110 00001
1011 0111 11011 1 1010
Prednosti i nedostatci
Nedostaci formata uključuju činjenicu da se pri visokim razinama kompresije blokovska struktura podataka osjeća, slika je "podijeljena na kvadrate" (svaki je veličine 8x8 piksela). Ovaj učinak je posebno uočljiv u područjima niske prostorne frekvencije (glatki prijelazi slike, npr. čisto nebo). U područjima s visokom prostornom frekvencijom (na primjer, kontrastni rubovi slike), pojavljuju se karakteristični "artefakti" - nepravilna struktura piksela s iskrivljenom bojom i/ili svjetlinom. Osim toga, sitni detalji u boji nestaju sa slike. To također ne treba zaboraviti ovaj format ne podržava transparentnost.
Međutim, unatoč svojim nedostacima, JPEG je postao vrlo raširen zbog svog visokog omjera kompresije u odnosu na alternative koje su postojale u vrijeme 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. Godine 1997. postalo je jasno da je potreban novi, fleksibilniji i snažniji standard, koji je finaliziran do zime 2000. godine.
Glavne razlike između algoritma u JPEG 2000 i algoritma u JPEG su sljedeće:
1) Bolja kvaliteta slike s visokim stupnjem kompresije. Ili, što je isto, veći omjer kompresije uz istu kvalitetu za visoke omjere kompresije. Zapravo, to znači primjetno smanjenje veličine grafike "web-kvalitete" koju koristi većina stranica.
2) Podrška za kodiranje pojedinih područja s boljom kvalitetom. Poznato je da su određena područja slike kritična za ljudsku percepciju (primjerice oči na fotografiji), dok kvaliteta drugih može biti žrtvovana (primjerice pozadina). S "ručnom" optimizacijom, stupanj kompresije se povećava sve dok se ne izgubi kvaliteta u nekom važnom dijelu slike. Sada je moguće postaviti kvalitetu u kritičnim područjima, jače sažimajući ostala područja, tj. dobivamo još veći konačni omjer kompresije uz subjektivno jednaku kvalitetu slike.
3) Glavni algoritam kompresije zamijenjen je valićkom. Uz navedeno povećanje omjera kompresije, ovo je omogućilo uklanjanje blokova od 8 piksela koji se javljaju kada se omjer kompresije poveća. Osim toga, glatko razvijanje slike sada je u početku uključeno 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 također uključivao aritmetičku kompresiju, ali je kasnije zamijenjena manje učinkovitom 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. Uz uobičajenu kompresiju bez gubitaka, novi JPEG sada podržava kompresiju bez gubitaka. Tako postaje moguća upotreba JPEG za komprimiranje medicinskih slika, u ispisu, prilikom spremanja teksta za prepoznavanje putem OCR sustava itd.
6) Podržava kompresiju jednobitnih (2 boje) slika. Za spremanje jednobitnih slika (crteži tintom, skenirani tekst, itd.), GIF format je ranije bio naširoko preporučen, jer je DCT kompresija vrlo neučinkovita za slike s oštrim prijelazima boja. U JPEG-u, kada je kompresirana, 1-bitna slika je pretvorena u 8-bitnu, tj. povećan za 8 puta, nakon čega se pokušalo sažimati, često manje od 8 puta. Sada možemo preporučiti JPEG 2000 kao univerzalni algoritam.
7) Transparentnost je podržana na razini formata. Glatko utapajte pozadinu prilikom izrade WWW stranice sada će to biti moguće ne samo u GIF-u, već iu JPEG 2000. Osim toga, nije podržan samo 1 bit prozirnosti (piksel je proziran/neproziran), već i zasebni kanal, koji će vam omogućiti da postavite glatki prijelaz od neprozirne slike do prozirne pozadine.
Osim toga, razina formata podržava uključivanje informacija o autorskim pravima u sliku, podršku za toleranciju bitne pogreške tijekom prijenosa i emitiranja, te se može tražiti dekompresija ili obrada vanjska 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, korištenjem odgovarajućih omjera boja RGB model pretvoreno u YUV:
Prilikom dekompresije primjenjuje se odgovarajuća inverzna transformacija:
2. Diskretna valna transformacija.
Diskretna wavelet konverzija(DWT) također može biti dvije vrste - za slučaj kompresije s gubicima i za kompresiju bez gubitaka.
Ova transformacija u jednodimenzionalnom slučaju je skalarni umnožak odgovarajućih koeficijenata i niza vrijednosti. Ali zbog mnogi koeficijenti su nula, tada se izravna i inverzna valna transformacija može napisati sljedećim formulama (za transformaciju krajnjih elemenata linije koristi se njezino proširenje za 2 piksela u svakom smjeru, čije su vrijednosti simetrične s vrijednosti elemenata linije u odnosu na krajnje 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 valićna transformacija, poput svog analoga, razvrstava koeficijente po frekvenciji. No, za razliku od JPEG-a, u novom formatu postoji jedna kvantizacijska matrica za cijelu sliku.
4. Sekundarni stupanj kompresije
. Poput JPEG-a, posljednji korak u algoritmu kompresije u novom formatu je kodiranje bez gubitaka. No, 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 naprijed i nazad kodiranje (ne postoji završna faza sekundarna kompresija). Izračun JPEG-a traje prilično dugo (oko 30 sekundi) zbog "izravnog" izračuna DCT-a. Ako trebate povećati brzinu rada, prvo morate izračunati DCT matricu (promjene treba napraviti u DCT klasi).
Prijeđimo na program:
Nakon pokretanja pojavljuje se prozor gdje
a možete ga spremiti klikom na gumb (2) i unosom željenog naziva u dijaloški okvir. S dovoljno velikim faktorom kvalitete, slika će se jako promijeniti. Ako se radi o JPEG algoritmu, tada će blokovi veličine 8x8 biti jasno vidljivi (u slučaju JPEG2000 algoritma neće biti blokovske podjele)
Nakon:
