Algoritam je razvila grupa stručnjaka iz oblasti fotografije (Joint Photographic Expert Group) posebno za kompresiju 24-bitnih i sivih slika 1991. godine. Ovaj algoritam nije baš dobar u kompresovanju slika na dva nivoa, ali odlično obrađuje slike sa neprekidnim tonovima, u kojima obližnji 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 je baziran na DCT primijenjenoj na matricu 8x8 piksela disjunktnih blokova slike. DCT razlaže ove blokove prema amplitudama određenih frekvencija. Kao rezultat, dobija se 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 u kvaliteti restauracije.
Razmotrimo rad algoritma detaljnije. Pretpostavimo da komprimirate 24-bitnu sliku u punoj boji. U ovom slučaju dobijamo sledeće faze rada.
Korak 1. Prevodimo sliku iz RGB prostora u YCbCr prostor koristeći sljedeći izraz:
Odmah napominjemo da se inverzna transformacija lako dobija množenjem inverzne matrice vektorom, koji je u suštini YUV prostor:
.
Korak 2. Podijelite originalnu sliku na 8x8 matrice. Formiramo tri radne DCT matrice od svake - 8 bitova posebno za svaku komponentu. Pri visokim omjerima kompresije, blok 8x8 se razlaže na YCbCr komponente u formatu 4:2:0, tj. komponente za Cb i Cr su uzete kroz tačku duž redova i kolona.
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. Štaviše, s obzirom na ortogonalnost kosinusnih funkcija s različitim frekvencijama, gornja formula se može napisati kao
.
Ovdje je 8x8 matrica koja opisuje 8-dimenzionalni prostor za predstavljanje stupaca bloka u tom prostoru. Matrica je transponovana matrica i radi isto, 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 gotovo isti iznos sabiranja, što je znatno manje od direktnih proračuna korištenjem gornje formule. Na primjer, pretvaranje slike veličine 512x512 piksela zahtijeva aritmetičke operacije. Uzimajući u obzir 3 komponente osvetljenja, dobijamo vrednost 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, da biste transformirali jedan blok 8x8, morat ćete napraviti 54 množenja, 468 sabiranja i pomaka bitova.
Kao rezultat DCT-a, dobijamo matricu u kojoj koeficijenti u gornjem lijevom kutu odgovaraju niskofrekventnoj komponenti slike, au donjem desnom - visokofrekventnoj komponenti.
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 korištenje vlastitih tablica kvantizacije, koje će, međutim, morati biti poslane u dekoder zajedno sa komprimiranim podacima, što će povećati ukupnu veličinu datoteke. Jasno je da je korisniku teško da sam odabere 64 koeficijenta, stoga JPEG standard koristi dva pristupa za matrice kvantizacije. Prvi je da JPEG standard uključuje dvije preporučene tabele kvantizacije: jednu za luma i jednu za hromazu. Ove tabele su predstavljene u nastavku. Drugi pristup je sintetizacija (računanje u hodu) tabele kvantizacije koja zavisi od jednog parametra koji je odredio korisnik. Sama tabela je napravljena pomoću formule
U koraku kvantizacije, omjer kompresije se kontrolira i dolazi do najvećeg gubitka. Jasno je da ćemo postavljanjem tablica kvantizacije sa velikim koeficijentima dobiti više nula, a samim tim i veći omjer kompresije.
Kvantizacija je takođe povezana sa specifičnim efektima algoritma. Pri velikim vrijednostima koraka kvantizacije, gubici mogu biti toliki da se slika razbije na jednobojne kvadrate 8x8. Zauzvrat, gubici na visokim frekvencijama mogu se manifestirati u takozvanom "Gibbsovom efektu", kada se oko kontura formira valoviti "halo" s oštrim prijelazom boja.
Korak 5. Prevodimo matricu 8x8 u vektor od 64 elementa koristeći "cik-cak" skeniranje (slika 2).
Rice. 2. "Cik-cak" - skeniranje
Kao rezultat toga, na početku vektora, po pravilu, biće ispisani koeficijenti različiti od nule, a na kraju će se formirati lanci nula.
Korak 6. Vektor transformišemo modifikovanim RLE algoritmom, na čijem izlazu dobijamo parove tipa (skip, broj), gde je "skip" brojač preskočenih nula, a "broj" je vrednost koja se mora uneti sledeća ćelija. Na primjer, vektor 1118 3 0 0 0 -2 0 0 0 0 1… bit će presavijen u parove (0, 1118) (0,3) (3, -2) (4,1)….
Treba napomenuti da je prvi broj transformisane komponente suštinski jednak prosečnoj osvetljenosti bloka 8x8 i naziva se DC koeficijent. Isto tako za sve blokove slika. Ova okolnost sugerira da se DC koeficijenti mogu učinkovito komprimirati ako zapamtite ne njihove apsolutne vrijednosti, već relativne vrijednosti u obliku razlike između DC koeficijenta trenutnog bloka i DC koeficijenta prethodnog bloka, i zapamtite prvi koeficijent kakav jeste. U ovom slučaju, poredak DC koeficijenata može se izvršiti, na primjer, na sljedeći način (slika 3). Ostali koeficijenti, koji se nazivaju AC-koeficijenti, ostaju nepromijenjeni.
Korak 7. Konvolvirajte rezultirajuće parove koristeći neuniformne fiksne tablice Huffmanovih kodova. Osim toga, koriste se različiti kodovi za DC i AC koeficijente, tj. različite tabele sa Huffmanovim 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 vidljivog gubitka vida.
Prilikom razvoja ovog standarda vodili smo se činjenicom da je ovaj algoritam morao da komprimuje slike prilično brzo – ne više od jedne minute na prosječnu sliku. 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 smislu vremena rada. Ispunjavanje posljednjeg zahtjeva omogućilo je pojavu digitalnih fotoaparata koji snimaju 24-bitne slike. Da je algoritam asimetričan, bilo bi neugodno čekati dugo dok se uređaj ne "napuni" - komprimovaće sliku.
Iako je JPEG ISO standard, njegov format datoteke nije fiksiran. Koristeći ovo, proizvođači kreiraju svoje nekompatibilne formate i stoga mogu promijeniti algoritam. Tako se interne tabele algoritma koje preporučuje ISO zamenjuju njima sopstvenim. Postoje i JPEG opcije za određene aplikacije.
- Tutorial
UPD. Bio je prisiljen ukloniti monospace formatiranje. Jednog lijepog dana, habraparser je prestao da opaža formatiranje unutar oznaka pre i code. Cijeli tekst se pretvorio u haos. Uprava Habra mi nije mogla pomoći. Sada neujednačen, ali barem čitljiv.
Jeste li se ikada zapitali kako funkcionira jpg datoteka? Hajde da to sada shvatimo! Zagrijte svoj omiljeni kompajler i heksadecimalni uređivač, dekodirajte ovo:
Posebno sam uzeo manji crtež. Ovo je poznati, ali jako komprimirani Google favicon:
Odmah vas upozoravam da je opis pojednostavljen, a date informacije nisu potpune, ali kasnije će biti lako razumjeti specifikaciju.
Čak i ne znajući kako se kodiranje odvija, već možemo izdvojiti nešto iz datoteke.
- startni marker. Uvijek se nalazi 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. Ovo su kodovi za znakove ":" i ")", tj. običan emotikon. Možete ga vidjeti na prvom redu desne strane hex editora.
Malo teorije
Vrlo kratko u koracima:
Razmislimo o redoslijedu kojim se ovi podaci mogu kodirati. Pretpostavimo, prvo, potpuno, za cijelu sliku, Y kanal je kodiran, zatim Cb, zatim Cr. Svi se sjećaju učitavanja slika na dial-up. Da su tako kodirani, 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 su kodirani podaci raspoređeni naizmjenično, 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 sljedećim redoslijedom: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20
Čitanje fajla
Nakon što smo izdvojili komentar, trebalo bi biti lako razumjeti da:- Fajl je podijeljen na sektore kojima prethode markeri.
- Markeri su dugi 2 bajta, sa prvim bajtom.
- 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 je uvijek 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 popunjavanja vrijednosti tablice. Ovaj redosled se naziva cik-cak redosled: 
Marker: SOF0 - Osnovni DCT
Ovaj marker se zove SOF0, a to znači da je slika kodirana osnovnom metodom. Vrlo je česta. Ali na Internetu, progresivna metoda koja vam je poznata nije ništa manje popularna, kada se prvo učita slika niske rezolucije, a zatim normalna slika. Ovo vam omogućava da shvatite šta je tamo prikazano bez čekanja na potpuno preuzimanje. 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 uzorka: 0x10 = 16
Širina uzorka: 0x10 = 16
Broj komponenti: 3. Najčešće su to Y, Cb, Cr.
1. komponenta:
ID: 1
Horizontalno stanjivanje (H 1): 2
[_2]
Vertikalna decimacija (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 istanjena slika. Pronađite H max = 2 i V max = 2. Kanal i će se rezati u H max / H i puta horizontalno i V max / V i puta vertikalno.
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
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 su 2 koda, u ovoj tabeli više nema kodova.
Svakom kodu je pridružena vrijednost, a ona su navedena u datoteci. Vrijednosti su jednobajtne, tako da čitamo 2 bajta.
- vrijednost 1. koda.
- vrijednost 2. koda.
Izgradnja Huffmanovog kodnog stabla
Moramo da napravimo binarno stablo iz tabele koju smo dobili u DHT sekciji. I već po ovom stablu prepoznajemo svaki kod. Vrijednosti dodajemo redoslijedom kojim su navedene u tabeli. Algoritam je jednostavan: bez obzira gdje se 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 se zaustaviti na nivou koji je jednak dužini koda. Lijeve grane odgovaraju 0, desne grane - 1.komentar:
Ne morate svaki put početi od vrha. Dodata vrijednost - vratite se jedan nivo više. Postoji li prava grana? Ako jeste, idite ponovo gore. Ako ne, kreirajte desnu granu i idite tamo. Zatim, odatle, započnite pretragu 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 krugovima - vrijednosti kodova, ispod krugova - sami kodovi (objasnit ću da smo ih dobili, idući od vrha do svakog čvora). Upravo takvim kodovima (ove i drugih tabela) je kodiran sadržaj same figure.
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 zove SOS.& nbsp 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, jedan za Y, Cb, Cr.
1. komponenta:
Broj dijela slike: 1 (Y)
ID Huffmanove tablice za DC koeficijente: 0
[_0]
ID Huffmanove tablice za AC koeficijente: 0
2. komponenta:
Broj dijela 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 (markera) kodiranih podataka.
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ž grana 0 ili 1, ovisno o pročitanom bitu. Zaustavljamo se ako smo u konačnom čvoru.
10
1011101110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je 0, tada je koeficijent 0, zapisujemo ga u tabelu 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, ovo će biti koeficijent.
10
10
11101110011101100001111100100
3. Ako je prva znamenka binarne vrijednosti 1, onda je ostavljamo onakvu kakva jeste: DC_coef = vrijednost. Inače, transformiramo: DC_coef = vrijednost-2 dužina vrijednosti +1. Koeficijent upisujemo u tabelu na početku cik-cak - gornjem lijevom uglu.
Pronalaženje AC-koeficijenata.
1.
Slično kao kod tačke 1, pronalaženje DC koeficijenta. Nastavljamo da čitamo sekvencu:
10
10
1110
1110011101100001111100100
2.
Uzimamo vrijednost čvora. Ako je jednako 0, to znači da preostale vrijednosti matrice treba popuniti nulama. Zatim se kodira sljedeća matrica. Prvih nekoliko koji su pročitali ovo daleko i pisali mi o tome u lično, dobiće plus u karmi. U našem slučaju, vrijednost čvora je 0x31.
Prvi grickanje: 0x3 - ovo je koliko nula moramo dodati u matricu. Ovo su 3 nula koeficijenta.
Drugi grickanje: 0x1 - dužina koeficijenta u bitovima. Čitamo sljedeći dio.
10
10
1110
1
110011101100001111100100
3. Slično kao kod tačke 3 određivanja DC-koeficijenta.
Kao što ste već shvatili, 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 redoslijedom?
Razlog za korištenje ovog reda je jednostavan - što su veće vrijednosti v i u, to je manje značajan koeficijent S vu u diskretnoj kosinus transformaciji. Stoga, pri visokim omjerima kompresije, beznačajni koeficijenti se nule, č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 red. Ovo pravilo traje do kraja fajla.
... i po 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 ovdje postoji samo jedna matrica, DC koeficijenti se mogu ostaviti na miru.
Izračuni
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 da odaberete onu koja vam je potrebna. Prvo smo skenirali prvu komponentu, njena komponenta slike = 1. Komponenta slike sa ovim identifikatorom koristi matricu kvantizacije 0 (imamo je prvu 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 matrice Y-kanala ...
[-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 je stupac, v je red. s yx - direktne vrijednosti kanala.
* Uopšteno govoreći, ovo nije sasvim tačno. Kada sam uspio dekodirati i prikazati sliku veličine 16x16 na ekranu, napravio sam sliku veličine 600x600 (usput rečeno, to je bila naslovnica omiljenog albuma Mind.In.A.Boxa, Lost Alone). Nije uspjelo odmah - isplivale su razne greške. Uskoro sam mogao da se divim pravilno učitanoj slici. Samo je brzina preuzimanja bila veoma uznemirujuća. 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 dosta eksperimenata, smanjio sam vrijeme učitavanja na granicu od 15ms tačnosti tajmera, a nakon toga promijenio sliku u fotografiju 25 puta veću. Možda ću o tome pisati u posebnom članak).
Napisat ću rezultat izračunavanja samo prve matrice Y kanala (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, idemo jesti!
- Da ne ulazim uopšte, o čemu se radi.
- Nakon što su primljene YCbCr vrijednosti boja, ostaje da se konvertuju u RGB, ovako: YCbCrToRGB (Y ij, Cb ij, Cr ij), Y ij, Cb ij, Cr ij - naše rezultirajuće matrice.
- 4 matrice Y, i jedna Cb i Cr, pošto smo razrijedili kanale i 4 piksela Y 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 su vrijednosti izvan raspona, dodijelite granične vrijednosti. Formula je jednostavna, ali također troši djelić CPU 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 se morao suočavati sa raznim neshvatljivim problemima. A kada je slika prikazana pogrešno, nisam znao gdje sam pogriješio. Možda je pogrešno protumačio bitove, ili je možda zloupotrijebio DCT. Propustio sam primjer korak po korak, pa se nadam da će ovaj članak pomoći pri pisanju dekodera. Mislim da pokriva opis osnovne metode, ali ipak ne možete učiniti samo to. Evo nekoliko linkova koji su mi pomogli:JPEG je jedan od najnovijih i najmoćnijih algoritama. U praksi, to je de facto standard za slike u punoj boji. Algoritam radi sa 8x8 oblastima, gde se osvetljenost i boja menjaju relativno glatko. Kao rezultat toga, kada se matrica takve regije proširi u dvostruki niz u kosinusima (formule ispod), samo su prvi koeficijenti značajni. Dakle, kompresija u JPFG se vrši na račun glatkih promjena boja na slici.
Algoritam je razvila grupa stručnjaka za fotografiju posebno za kompresiju 24-bitnih JPEG slika - Zajednička fotografska ekspertska grupa - odeljenje unutar ISO - Međunarodne organizacije za standardizaciju. Općenito, algoritam se zasniva na diskretnoj kosinusnoj transformaciji (u daljem tekstu DCT) primijenjenoj na matricu slike da bi se dobila neka nova matrica koeficijenata. Da bi se dobila originalna slika, primjenjuje se inverzna transformacija
DCT dekomponuje sliku na amplitude nekih frekvencija, tako da tokom transformacije dobijamo matricu u kojoj su mnogi koeficijenti ili blizu ili jednaki nuli. Osim toga, ljudski sistem percepcije boja je loš u prepoznavanju određenih frekvencija. Stoga je moguće grublje aproksimirati neke koeficijente bez primjetnog gubitka kvaliteta slike.
Za to se koristi kvantizacija. U najjednostavnijem slučaju, to je aritmetički pomak po bitu udesno. Ovom transformacijom neke informacije se gube, ali se mogu postići veliki omjeri kompresije.
Algoritamski rad.
Hajde da komprimujemo 24-bitnu sliku.
Korak I.
Prevodimo sliku iz RGB prostora boja, sa komponentama odgovornim za crvene (crvene), zelene (zelene) i plave (plave) komponente boje tačke, u YCrCb prostor boja (ponekad se naziva YUV).
U njemu je Y komponenta svjetline, a Cg, Cb 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 Cg i Cb komponente s visokim gubicima i, shodno tome, visokim omjerima kompresije. Ova transformacija se dugo koristila na televiziji. Signalima odgovornim za boju dodjeljuje se uži frekvencijski pojas.
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.
Podijelite originalnu sliku na 8x8 matrice. Formiramo tri radne DCT matrice od svake - 8 bitova 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. Štaviše, kao što je lako vidjeti, gubimo 3/4 korisnih informacija o komponentama boje slike i odmah dobijamo dvostruku kompresiju. To možemo učiniti radeći u YCrCb prostoru. Kao što je praksa pokazala, to ne utiče značajno 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, ta 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 MK).
U ovom koraku se kontrolira omjer kompresije i dolazi do najvećeg gubitka. Jasno je da ćemo specificiranjem MK sa velikim koeficijentima dobiti više nula, a samim tim i veći omjer kompresije.
Kvantizacija je takođe povezana sa specifičnim efektima algoritma. Pri velikim vrijednostima koeficijenta gama , - gubitak na niskim frekvencijama može biti toliki da se slika podijeli na kvadrate 8x8. Gubici na visokim frekvencijama mogu se manifestirati u takozvanom "Gibbsovom efektu", kada se oko kontura formira svojevrsni "halo" s oštrim prijelazom boja
Korak 5.
Prevodimo matricu 8x8 u vektor od 64 elementa koristeći cik-cak skeniranje, tj. odaberite elemente sa indeksima (0.0). (0,1). (1.0). (2.0) ...
Tako na početku vektora dobijamo matrične koeficijente koji odgovaraju niskim frekvencijama, a na kraju visokim frekvencijama.
Korak 6.
Konvoltiranje vektora korištenjem algoritma 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 biti presavijeni u parove (0, 42) (0, 3) (3, -2) (4, 1)
Korak 7.
Sažimamo naučene parove Huffmanovim kodiranjem sa fiksnom tablicom.
Proces obnavljanja slike u ovom algoritmu je potpuno simetričan. Metoda vam omogućava da komprimirate neke slike 10-15 puta bez ozbiljnog gubitka.
Operativni cjevovod koji se koristi u JPEG algoritmu.
Značajni pozitivni aspekti algoritma su:
- 1) Omjer kompresije je podešen
- 2) Izlazna slika u boji može biti 24 bita po tački.
Nedostaci algoritma su:
- 1) Kada se poveća omjer kompresije, slika se dijeli 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 se jače kompresuju uz manji gubitak kvaliteta. Činjenica je da su akcije programera standarda 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 dekompresije je približno jednako vremenu arhiviranja).
Posljednji zahtjev omogućio je pojavu digitalnih fotoaparata - uređaja veličine male kamkordera 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 čekati dugo dok se uređaj ne "napuni" - komprimovaće sliku.
Ne baš prijatna karakteristika JPEG-a je i činjenica da su često horizontalne i vertikalne pruge na ekranu potpuno nevidljive, a mogu se pojaviti samo kada se štampaju u obliku moire uzorka. Javlja se kada se kosi ekran za štampanje postavi na horizontalne i vertikalne pruge slike. Zbog ovih iznenađenja, JPEG se ne preporučuje da se aktivno koristi u štampanju, postavljajući visoke koeficijente. Međutim, kod arhiviranja i slika namijenjenih ljudskom gledanju, trenutno je nezamjenjiv.
Široko rasprostranjena upotreba JPEG-a je dugo bila ograničena, možda samo činjenicom da radi sa 24-bitnim slikama. Stoga, da bi se na običnom monitoru prikazala slika prihvatljivog kvaliteta u paleti od 256 boja, bilo je potrebno koristiti odgovarajuće algoritme, a time i određeno vrijeme. U aplikacijama namenjenim izbirljivim korisnicima, kao što su igre, takva kašnjenja su neprihvatljiva. Osim toga, ako se slike koje imate, recimo, konvertuju u 8-bitni GIF format u 24-bitni JPEG, a zatim se vrate u GIF za gledanje, tada će se gubitak kvaliteta dogoditi dva puta s obje konverzije. Ipak, povećanje u veličini arhiva 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 nekompatibilne formate, te stoga mogu promijeniti algoritam. Dakle, interne tabele algoritma, preporučene od strane ISO. zamjenjuju se s vlastitim kronama, osim toga, postoji mala zabuna prilikom postavljanja stepena gubitaka. Na primjer, pri testiranju se ispostavi da "odličan" kvalitet, "100%" i "10 bodova" daju značajno različite slike. Štoviše, 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 u razmjeni slika preko računarskih mreža. 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 naglih prelaza boja (fotografije).
simetrija: 1.
Posebne karakteristike: U nekim slučajevima, algoritam stvara "halo" oko isečenih horizontalnih i vertikalnih ivica na slici (Gibbsov efekat). Osim toga, kada je omjer kompresije visok, slika se dijeli na blokove veličine 8x8 piksela.
(izgovara se "japeg" Joint Photographic Experts Group, prema nazivu razvojne organizacije) jedan je od popularnih grafičkih formata koji se koriste za pohranjivanje fotografskih slika i sličnih slika. Datoteke koje sadrže JPEG podatke obično imaju ekstenzije .jpeg, .jfif, .jpg, .JPG ili .JPE. Od njih je, međutim, .jpg najpopularnija ekstenzija na svim platformama.
1. Zajednička grupa fotografskih eksperata;
2. Metoda kompresije slike koju je razvila ova grupa i odgovarajući grafički format koji se često koristi na WWW-u. Odlikuje se kompaktnošću datoteka i, shodno tome, brzim prijenosom, kao i "gubitak" kvaliteta slike. Koristi se prvenstveno za fotografije, jer je gubitak kvaliteta manje kritičan za njih. Zadržava postavke boja u RGB prostoru boja.
Jpeg(izgovara se " japeg“, inž. Zajednička grupa fotografskih eksperata, prema nazivu programera) jedan je od popularnih grafičkih formata koji se koristi za pohranjivanje fotografskih slika i sličnih slika. Datoteke koje sadrže JPEG podatke obično imaju ekstenzije .jpeg, .jfif, .jpg, .JPG, ili .JPE... Međutim, među njima .jpg najpopularnije proširenje na svim platformama. MIME tip je slika / jpeg.
JPEG je algoritam za kompresiju podataka sa gubitkom.
Područje primjene
JPEG algoritam je najprikladniji za kompresiju fotografija i slika koje sadrže realistične scene s glatkim prijelazima u svjetlini i boji. JPEG se najčešće koristi u digitalnoj fotografiji i za pohranjivanje i prijenos slika putem interneta.
S druge strane, JPEG je od male koristi za kompresiju crteža, teksta i grafike znakova, gdje oštar kontrast između susjednih piksela dovodi do uočljivih artefakata. Preporučljivo je da takve slike sačuvate u formatima bez gubitaka kao što su TIFF, GIF, PNG ili RAW.
JPEG (kao i druge metode kompresije distorzije) nije prikladan za kompresiju slika sa višestepenom obradom, budući da će izobličenja biti unesena u slike svaki put kada se pohranjuju rezultati srednje obrade.
JPEG se također ne bi trebao koristiti u slučajevima kada je čak i minimalni gubitak neprihvatljiv, na primjer, kada se kompresuju astronomske ili medicinske slike. U takvim slučajevima može se preporučiti način kompresije JPEG bez gubitaka koji obezbjeđuje JPEG standard (koji, nažalost, ne podržava većina popularnih kodeka) ili JPEG-LS standard kompresije.
Kompresija
Kada se kompresuje, slika se konvertuje iz RGB u YCbCr (YUV). Treba napomenuti da JPEG standard (ISO / IEC 10918-1) ni na koji način ne reguliše izbor YCbCr, dozvoljavajući druge vrste konverzije (na primjer, s više komponenti osim tri), i kompresiju bez konverzije (direktno u RGB), međutim, specifikacija JFIF (JPEG File Interchange Format, predložena 1991. od strane C-Cube Microsystems, a sada de facto standard) pretpostavlja upotrebu RGB->YCbCr konverzije.
Nakon RGB-> YCbCr konverzije za Cb i Cr kanale slike odgovorne za boju, može se izvršiti "poduzorkovanje", što znači da se svakom bloku od 4 piksela (2x2) Y kanala osvjetljenja dodijeljuju prosječne vrijednosti Cb i Cr (šema decimacije "4:2:0"). Istovremeno, za svaki blok 2x2, umjesto 12 vrijednosti (4 Y, 4 Cb i 4 Cr), koristi se samo 6 (4 Y i jedna prosječna Cb i Cr). Ako se postavljaju povećani zahtjevi za kvalitetu slike koja se obnavlja nakon kompresije, decimacija se može izvesti samo u jednom smjeru - okomito (šema „4: 4: 0”) ili horizontalno („4: 2: 2”), ili ne. uopšte ("4:4:4").
Standard takođe dozvoljava decimaciju sa usrednjavanjem Cb i Cr ne za blok 2x2, već za četiri uzastopna (vertikalno ili horizontalno) piksela, odnosno za blokove 1x4, 4x1 (šema 4:1:1), kao i za 2x4 i 4x2 . Također je dozvoljeno koristiti različite vrste decimacije za Cb i Cr, ali se u praksi takve sheme rijetko koriste.
Nadalje, komponenta svjetlosti Y i komponente Cb i Cr odgovorne za boju podijeljene su u blokove veličine 8x8 piksela. Svaki takav blok prolazi kroz diskretnu kosinusnu transformaciju (DCT). Dobijeni DCT koeficijenti se kvantiziraju (za Y, Cb i Cr, u općem slučaju koriste se različite matrice kvantizacije) i pakuju pomoću Huffmanovih kodova. JPEG standard također omogućava korištenje mnogo efikasnijeg aritmetičkog kodiranja, međutim, zbog patentnih ograničenja (patent za aritmetički QM enkoder opisan u JPEG standardu pripada IBM-u), ne koristi se u praksi.
Matrice koje se koriste za kvantiziranje DCT koeficijenata pohranjene su u dijelu zaglavlja JPEG datoteke. Obično su konstruisani tako da se koeficijenti visoke frekvencije kvantiziraju jače od niskofrekventnih. To dovodi do grubosti finih detalja na slici. Što je veći omjer kompresije, to su svi koeficijenti jače kvantizirani.
Prilikom pohranjivanja slike u JPEG datoteku, specificira se parametar kvalitete, specificiran u nekim proizvoljnim jedinicama, na primjer, od 1 do 100 ili od 1 do 10. Veći broj obično odgovara boljem kvalitetu (i većoj veličini komprimirane datoteke ). Međutim, čak i kada se koristi najviši kvalitet (koji odgovara matrici kvantizacije koja se sastoji od samo jedinica), rekonstruirana slika se neće potpuno poklapati s originalnom, što je povezano i s konačnom preciznošću izvršenja DCT-a i s potrebom zaokruživanja vrijednosti Y, Cb, Cr i koeficijenata DCT do najbliže cjeline. Režim kompresije JPEG bez gubitaka, koji ne koristi DCT, pruža tačnu podudarnost rekonstruisanih i originalnih slika, međutim, njegova niska efikasnost (omjer kompresije rijetko prelazi 2) i nedostatak podrške programera softvera nisu doprinijeli popularnosti Lossless JPEG-a. .
Različite šeme kompresije JPEG
JPEG standard pruža dva glavna načina predstavljanja kodiranih podataka.
Najčešći, podržan od strane većine dostupnih kodeka, je sekvencijalni JPEG prikaz podataka, koji uključuje sekvencijalno obilaženje kodirane slike blok po blok s lijeva na desno, odozgo prema dolje. Gore opisane operacije se izvode na svakom bloku kodirane slike, a rezultati kodiranja se stavljaju u izlazni tok u obliku jednog "skeniranja", tj. niz kodiranih podataka koji odgovaraju sekvencijalno pređenoj ("skeniranoj") slici. Osnovni ili "osnovni" način kodiranja dozvoljava samo ovu reprezentaciju. Prošireni (prošireni) način rada, zajedno sa sekvencijalnim, također omogućava progresivnu (progresivnu JPEG) prezentaciju podataka.
U slučaju progresivnog JPEG-a, kompresovani podaci se upisuju u izlazni tok kao skup skeniranja, od kojih svaki opisuje sliku u potpunosti sa sve većim stepenom detalja. To se postiže ili snimanjem u svakom skeniranju ne kompletnog skupa DCT koeficijenata, već samo nekih od njih: prvi - niskofrekventni, u sljedećim skeniranjima - visokofrekventni (metoda "spektralne selekcije", tj. spektralnog uzorkovanja) , ili sekvencijalnim, od skeniranja do skeniranja, preciziranje DCT koeficijenata (metoda "sukcesivne aproksimacije", tj. uzastopne aproksimacije). Ova progresivna reprezentacija podataka je posebno korisna pri prijenosu komprimiranih slika korištenjem komunikacijskih kanala male brzine, jer vam omogućava da dobijete predstavu o cijeloj slici nakon što se samo mali dio JPEG datoteke prenese.
Obje opisane šeme (i sekvencijalni i progresivni JPEG) su zasnovane na DCT-u i u osnovi ne dozvoljavaju dobijanje restaurirane slike apsolutno identične originalnoj. Međutim, standard dozvoljava i kompresiju koja ne koristi DCT, već je izgrađena na bazi linearnog prediktora (lossless, tj. "lossless", JPEG), što garantuje punu, bit-za-bit, podudarnost originalnog i rekonstruisanog slike. Istovremeno, omjer kompresije za fotografske slike rijetko dostiže 2, ali zajamčeno odsustvo izobličenja u nekim slučajevima se ispostavlja da je traženo. Primetno veći omjeri kompresije mogu se postići upotrebom JPEG-LS metode kompresije opisane u ISO / IEC 14495-1, koja, uprkos sličnosti u nazivima, nije direktno povezana sa JPEG standardom ISO / IEC 10918-1 (ITU T.81 Preporuka) (ITU T.87 Preporuka).
JPEG sintaksa i struktura
JPEG datoteka sadrži sekvencu markeri, od kojih svaki počinje bajtom 0xFF, što označava početak markera, i bajtom - identifikatorom. Neki markeri se sastoje samo od ovog para bajtova, dok drugi sadrže dodatne podatke koji se sastoje od dvobajtnog polja s dužinom informacijskog dijela markera (uključujući dužinu ovog polja, ali minus dva bajta početka marker, odnosno 0xFF i identifikator) i same podatke.
| Marker | Bytes | Dužina | Imenovanje |
|---|
JPEG je jedan od novih i dovoljno moćnih algoritama. U praksi, to je de facto standard za slike u punoj boji. Algoritam radi sa 8x8 oblastima, gde se osvetljenost i boja menjaju relativno glatko. Kao rezultat toga, prilikom dekompozicije takve matrice, površina u dvostrukom redu u kosinusima (pogledajte formule ispod) se smatra značajnom samo po prvim koeficijentima.Tako se kompresija u JPEG-u vrši zbog glatkoće promjene boje u slika.
Algoritam koji je razvila grupa stručnjaka za fotografiju posebno za kompresiju 24-bitnih slika. JPEG - Joint Photographic Expert Group je odjel unutar ISO - Međunarodne organizacije za standardizaciju. Naziv algoritma glasi ["jei" peg]. Općenito, algoritam se zasniva na diskretnoj kosinusnoj transformaciji (u daljem tekstu DCT), koja se primjenjuje na matricu slike kako bi se dobila neka nova matrica koeficijenata. Da bi se dobila originalna slika, primjenjuje se inverzna transformacija.
DCT razlaže sliku na amplitude određenih frekvencija. Tako, prilikom transformacije, dobijamo matricu u kojoj su mnogi koeficijenti ili blizu ili jednaki nuli. Osim toga, zbog nesavršenosti ljudskog vida, koeficijenti se mogu grublje aproksimirati bez primjetnog gubitka kvaliteta slike.
Za to se koristi kvantizacija. U najjednostavnijem slučaju, to je aritmetički pomak po bitu udesno. Ovom transformacijom neke informacije se gube, ali se može postići veliki omjer kompresije.
Kako algoritam radi
Dakle, razmotrimo algoritam detaljnije (slika 2.1). Recimo da komprimujemo 24-bitnu sliku.
Korak 1. Prevodimo sliku iz RGB prostora boja, sa komponentama odgovornim za crvene (crvene), zelene (zelene) i plave (plave) komponente boje tačke, u YCrCb prostor boja (ponekad se naziva YUV).
U njemu je Y komponenta svjetline, a Cr, Co 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 Co komponente s velikim gubicima i, shodno tome, velikim omjerima kompresije.Takva transformacija se dugo koristi u televiziji. Signalima odgovornim za boju dodjeljuje se uži frekvencijski pojas. Pojednostavljeni prijevod iz RGB prostora boja u YCrCb prostor boja može se predstaviti korištenjem prijelazne matrice:
Korak 2. Podijelite originalnu sliku na 8x8 matrice. Formiramo 3 radne DCT matrice od svake - 8 bitova 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 liniju i kroz kolonu. Odnosno, iz originalne matrice 16x16 dobija se samo jedna radna DCT matrica. U isto vrijeme, kao što je lako vidjeti, gubimo 3/4 korisnih informacija o komponentama boje slike i odmah dobijamo 2-struku kompresiju. To možemo učiniti radeći u YCrCb prostoru. Kao što je praksa pokazala, ovo ima mali uticaj na rezultujuću RGB sliku.
Korak 3. U pojednostavljenom obliku, DCT za n = 8 može se predstaviti na sljedeći način:
nu, v] = ^ Hc (i, u) xC (j, v) y r Y) Yq= IntegerRound U ovom koraku se kontrolira omjer kompresije i dolazi do najvećeg gubitka. Jasno je da ćemo specificiranjem MK sa velikim koeficijentima dobiti više nula, a samim tim i veći omjer kompresije. Kvantizacija je takođe povezana sa specifičnim efektima algoritma. Pri visokim gama vrijednostima, gubitak na niskim frekvencijama može biti toliki da se slika podijeli na kvadrate 8x8. Gubici na visokim frekvencijama mogu se manifestovati u tzv Gibbsov efekat, kada se oko kontura formira neka vrsta "halo" sa oštrim prijelazom boja. Korak 5. Prevodimo matricu 8x8 u vektor od 64 elementa koristeći "cik-cak" skeniranje, odnosno uzimamo elemente sa indeksima (0,0), (0,1), (1,0), ( 2,0 ) ... Tako na početku vektora dobijamo matrične koeficijente koji odgovaraju niskim frekvencijama, a na kraju visokim frekvencijama. Korak 6. Konvoltiranje vektora korištenjem algoritma grupnog kodiranja. U ovom slučaju dobijamo parove tipa<пропустить, число>gdje je "skip" broj nula koje treba preskočiti, a "number" je vrijednost koju treba staviti u sljedeću ćeliju. Dakle, vektor 42 3000-2 00001 ... bit će presavijeni u parove (0,42) (0,3) (3, -2) (4,1) .... Korak 7. Konvolvirajte rezultirajuće parove Huffmanovim kodiranjem sa fiksnom tablicom. Proces obnavljanja slike u ovom algoritmu je potpuno simetričan. Metoda vam omogućava da komprimirate neke slike 10-15 puta bez ozbiljnog gubitka. Značajni pozitivni aspekti algoritma su: ■ stepen kompresije je podešen; ■ izlazna slika u boji može biti 24 bita po tački. Nedostaci algoritma su: ■ Povećanje omjera kompresije dijeli sliku 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. ■ Pojavljuje se Gibbsov efekat - oreoli duž ivica oštrih prelaza boja. Kao što je već pomenuto, JPEG je standardizovan relativno nedavno - 1991. Ali čak i tada su postojali algoritmi koji su jače kompresovali sa manjim gubitkom kvaliteta. Činjenica je da su akcije programera standarda bile ograničene snagom tehnologije koja je postojala u to vrijeme. Odnosno, čak i na PC-u, algoritam je morao raditi manje od jednog minuta na prosječnoj slici, a njegova hardverska implementacija je morala biti relativno jednostavna i jeftina. Algoritam je morao biti simetričan (vrijeme dekompresije je približno jednako vremenu arhiviranja). Ispunjavanje posljednjeg zahtjeva omogućilo je pojavu uređaja kao što su digitalni fotoaparati koji snimaju 24-bitne fotografije na fleš karticu od 8-256 MB." Ova kartica se ubacuje u slot na vašem laptopu i odgovarajući program vam omogućava da čitate slike Nije istina. Nya, da je algoritam asimetričan, bilo bi neugodno čekati dugo dok se uređaj ne "napuni" - komprimovaće sliku. Ne baš zgodna karakteristika JPEG-a je takođe onda, da su često horizontalne i okomite pruge na displeju potpuno nevidljive i mogu se pojaviti samo pri štampanju u obliku moire uzorka. Javlja se kada se kosi ekran za štampanje postavi na horizontalne i vertikalne pruge slike. Zbog ovih iznenađenja, JPEG-ovi nisu preporučuje se aktivno upotreba u štampi, postavljanje visokih koeficijenata matrice kvantizacije. Međutim, kada se arhiviraju slike namijenjene ljudskom gledanju, trenutno je nezamjenjiv. Široko Upotreba JPEG-a je dugo bila ograničena, možda samo činjenicom da radi sa 24-bitnim slikama. Stoga, da bi se na običnom monitoru prikazala slika prihvatljivog kvaliteta u paleti od 256 boja, bilo je potrebno koristiti odgovarajuće algoritme, a time i određeno vrijeme. U aplikacijama namenjenim izbirljivim korisnicima, kao što su igre, takva kašnjenja su neprihvatljiva. Osim toga, ako se slike koje imate, na primjer, pretvore u 8-bitni GIF format u 24-bitni JPEG, a zatim se vrate u GIF za gledanje, gubitak kvaliteta će se dogoditi dva puta s obje konverzije. Ipak, dobitak u veličini arhiva je često tako velik (3-20 puta), a gubitak kvaliteta tako mali da se pohranjivanje slika u JPEG ispostavlja vrlo efikasnim. 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 nekompatibilne formate i stoga mogu promijeniti algoritam. Tako se interne tabele algoritma koje preporučuje ISO zamenjuju njima sopstvenim. Osim toga, postoji malo zabune pri određivanju stope gubitka. Na primjer, pri testiranju se ispostavi 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 u razmjeni slika preko računarskih mreža. JPEG algoritam je podržan u Quick Time, PostScript Level 2, Tiff 6.0 i trenutno zauzima istaknuto mjesto u multimedijalnim sistemima. Karakteristike JPEG algoritma: o! sh. ,. Omjer kompresije: 2-200 (korisnički definirano). , c,: _ ,. ... Klasa slike: pune boje 2jj.bitne slike ili iso- | slike u nijansama sive bez naglih prelaza boja (fotografije). simetrija: 1. karakteristike: u nekim slučajevima algoritam stvara! "halo" oko oštrih horizontalnih i vertikalnih ivica na slici (Gibbsov efekat). Osim toga, sa visokim omjerom kompresije, iso-! Refleksija je podijeljena na blokove veličine 8x8 piksela.
