Algoritmul a fost dezvoltat de un grup de experți în domeniul fotografiei (Joint Photographic Expert Group) special pentru comprimarea imaginilor pe 24 de biți și în tonuri de gri în 1991. Acest algoritm nu este foarte bun la comprimarea imaginilor pe două niveluri, dar gestionează excelent imaginile cu tonuri continue, în care pixelii din apropiere tind să aibă culori similare. De obicei, ochiul nu poate observa nicio diferență atunci când este comprimat prin această metodă de 10 sau 20 de ori.
Algoritmul se bazează pe DCT aplicat unei matrice de 8x8 pixeli de blocuri de imagini disjunse. DCT descompune aceste blocuri în funcție de amplitudinile anumitor frecvențe. Ca urmare, se obține o matrice în care mulți coeficienți, de regulă, sunt aproape de zero, care pot fi reprezentați în formă numerică aproximativă, adică. într-o formă cuantificată fără pierderi semnificative în calitatea restaurării.
Să luăm în considerare funcționarea algoritmului mai detaliat. Să presupunem că comprimați o imagine color pe 24 de biți. În acest caz, obținem următoarele etape de lucru.
Pasul 1. Traducem imaginea din spațiul RGB în spațiul YCbCr folosind următoarea expresie:
Observăm imediat că transformarea inversă se obține ușor prin înmulțirea matricei inverse cu un vector, care este în esență spațiul YUV:
.
Pasul 2.Împărțiți imaginea originală în matrici de 8x8. Formăm trei matrice DCT de lucru din fiecare - 8 biți separat pentru fiecare componentă. La rapoarte de compresie ridicate, blocul 8x8 este descompus în componente YCbCr în format 4: 2: 0, adică. componentele pentru Cb și Cr sunt luate printr-un punct de-a lungul rândurilor și coloanelor.
Pasul 3. Aplicarea DCT la blocuri de imagini de 8x8 pixeli. Formal, DCT direct pentru blocul 8x8 poate fi scris ca
Unde 
... Deoarece DCT este „inima” algoritmului JPEG, este de dorit în practică să îl calculăm cât mai repede posibil. O abordare simplă pentru a accelera calculele este de a calcula funcțiile cosinus din timp și de a tabulare rezultatele. Mai mult, având în vedere ortogonalitatea funcțiilor cosinus cu frecvențe diferite, formula de mai sus poate fi scrisă ca
.
Iată o matrice de 8x8 care descrie un spațiu cu 8 dimensiuni pentru a reprezenta coloanele unui bloc din acel spațiu. Matrix este o matrice transpusă și face același lucru, dar pentru rândurile de bloc. Rezultatul este o transformare separabilă, care sub formă de matrice este scrisă ca
Iată rezultatul DCT, al cărui calcul necesită operații de înmulțire și aproape aceeași cantitate de adunări, care este semnificativ mai mică decât calculele directe folosind formula de mai sus. De exemplu, convertirea unei imagini de 512x512 pixeli va necesita operații aritmetice. Luând în considerare 3 componente de luminanță, obținem valoarea a 12 582 912 operații aritmetice. Numărul de înmulțiri și adunări poate fi redus și mai mult prin utilizarea algoritmului Fast Fourier Transform. Ca rezultat, pentru a transforma un bloc de 8x8, va trebui să faceți 54 de înmulțiri, 468 de adunări și deplasări de biți.
Ca urmare a DCT, obținem o matrice în care coeficienții din colțul din stânga sus corespunde componentei de joasă frecvență a imaginii, iar în dreapta jos - celei de înaltă frecvență.
Pasul 4. Cuantizarea. La acest pas, unele informații sunt eliminate. Aici, fiecare număr din matrice este împărțit la un număr special din „tabelul de cuantizare”, iar rezultatul este rotunjit la cel mai apropiat număr întreg:
.
Mai mult, pentru fiecare matrice Y, Cb și Cr, puteți seta propriile tabele de cuantizare. Standardul JPEG permite chiar și utilizarea propriilor tabele de cuantizare, care, totuși, vor trebui transmise la decodor împreună cu datele comprimate, ceea ce va crește dimensiunea totală a fișierului. Este clar că este dificil pentru un utilizator să selecteze singur 64 de coeficienți, prin urmare standardul JPEG folosește două abordări pentru matricele de cuantizare. Primul este că standardul JPEG include două tabele de cuantizare recomandate: unul pentru lumina și unul pentru croma. Aceste tabele sunt prezentate mai jos. A doua abordare este de a sintetiza (calcula din mers) un tabel de cuantizare care depinde de un parametru care este specificat de utilizator. Tabelul în sine este construit folosind formula
În etapa de cuantizare, raportul de compresie este controlat și are loc cea mai mare pierdere. Este clar că prin stabilirea tabelelor de cuantizare cu coeficienți mari, vom obține mai multe zerouri și, prin urmare, un raport de compresie mai mare.
Cuantizarea este, de asemenea, asociată cu efecte specifice ale algoritmului. La valori mari ale etapei de cuantificare, pierderile pot fi atât de mari încât imaginea se descompune în pătrate de o singură culoare de 8x8. La rândul lor, pierderile de frecvențe înalte se pot manifesta în așa-numitul „efect Gibbs”, când se formează un „halo” ondulat în jurul contururilor cu o tranziție de culoare ascuțită.
Pasul 5. Traducem matricea 8x8 într-un vector de 64 de elemente folosind scanarea „zigzag” (Fig. 2).
Orez. 2. „Zigzag” -scanare
Ca urmare, la începutul vectorului, de regulă, se vor scrie coeficienți nenuli, iar la sfârșit se vor forma lanțuri de zerouri.
Pasul 6. Transformăm vectorul folosind algoritmul RLE modificat, la ieșirea căruia obținem perechi de tipul (skip, number), unde „skip” este contorul de zerouri omise, iar „number” este valoarea care trebuie pusă în celula următoare. De exemplu, vectorul 1118 3 0 0 0 -2 0 0 0 0 1… va fi pliat în perechi (0, 1118) (0,3) (3, -2) (4,1)….
Trebuie remarcat faptul că primul număr al componentei transformate este în mod substanțial egal cu luminanța medie a blocului 8x8 și este denumit coeficient DC. La fel pentru toate blocurile de imagini. Această împrejurare sugerează că coeficienții DC pot fi comprimați în mod eficient dacă memorați nu valorile lor absolute, ci valorile relative sub forma diferenței dintre coeficientul DC al blocului curent și coeficientul DC al blocului anterior și vă amintiți primul coeficient așa cum este. În acest caz, ordonarea coeficienților DC se poate face, de exemplu, după cum urmează (Fig. 3). Restul coeficienților, care se numesc coeficienți AC, rămân neschimbați.
Pasul 7. Convoluți perechile rezultate folosind coduri Huffman neuniforme cu tabel fix. Mai mult, se folosesc diferite coduri pentru coeficienții DC și AC, de exemplu. diferite tabele cu coduri Huffman.
Orez. 3. Schema de ordonare a coeficienților DC
Orez. 4. Diagrama bloc a algoritmului JPEG
Procesul de restaurare a imaginii în acest algoritm este complet simetric. Metoda vă permite să comprimați imaginile de 10-15 ori fără pierderi vizuale vizibile.
La dezvoltarea acestui standard, am fost ghidați de faptul că acest algoritm a trebuit să comprime imaginile destul de repede - nu mai mult de un minut la o imagine medie. Asta în 1991! Iar implementarea sa hardware ar trebui să fie relativ simplă și ieftină. În acest caz, algoritmul trebuia să fie simetric în ceea ce privește timpul de funcționare. Îndeplinirea acestei din urmă cerințe a făcut posibilă apariția camerelor digitale care înregistrează imagini pe 24 de biți. Dacă algoritmul ar fi asimetric, ar fi neplăcut să așteptați mult timp până când dispozitivul se „reîncărcă” - va comprima imaginea.
Deși JPEG este un standard ISO, formatul său de fișier nu a fost remediat. Profitând de acest lucru, producătorii își creează propriile formate incompatibile și, prin urmare, pot schimba algoritmul. Astfel, tabelele interne ale algoritmului recomandat de ISO sunt înlocuite de acestea cu propriile lor. Există, de asemenea, opțiuni JPEG pentru aplicații specifice.
- Tutorial
UPD. A fost forțat să elimine formatarea monospațiu. Într-o bună zi, habraparserul a încetat să mai perceapă formatarea din interiorul etichetelor pre și cod. Întregul text s-a transformat într-o mizerie. Administrația Habr nu m-a putut ajuta. Acum neuniform, dar cel puțin lizibil.
Te-ai întrebat vreodată cum funcționează un fișier jpg? Să ne dăm seama acum! Încălzește-ți compilatorul și editorul hexadecimal preferat, hai să decodificăm asta:
Am luat special un desen mai mic. Aceasta este favicon-ul Google familiar, dar puternic comprimat:
Vă avertizez imediat că descrierea este simplificată, iar informațiile furnizate nu sunt complete, dar ulterior va fi ușor de înțeles specificația.
Fără să știm măcar cum are loc codificarea, putem deja extrage ceva din fișier.
- marker de pornire. Se găsește întotdeauna la începutul tuturor fișierelor jpg.
Urmat de octeți
... Acesta este un marcator care marchează începutul secțiunii de comentarii. Următorii 2 octeți
- lungimea secțiunii (inclusiv acești 2 octeți). Deci în următoarele două
- comentariul în sine. Acestea sunt codurile pentru caracterele „:” și „)”, adică. emoticon obișnuit. Îl puteți vedea pe prima linie din partea dreaptă a editorului hexadecimal.
Un pic de teorie
Foarte pe scurt, în pași:
Să ne gândim la ordinea în care aceste date pot fi codificate. Să presupunem, mai întâi, complet, pentru întreaga imagine, canalul Y este codificat, apoi Cb, apoi Cr. Toată lumea își amintește că a încărcat imagini pe dial-up. Dacă ar fi codificate în acest fel, ar trebui să așteptăm ca întreaga imagine să se încarce înainte de a apărea pe ecran. De asemenea, va fi neplăcut dacă se pierde sfârșitul fișierului. Probabil că există și alte motive bune. Prin urmare, datele codificate sunt dispuse alternativ, în părți mici. 
Permiteți-mi să vă reamintesc că fiecare bloc Y ij, Cb ij, Cr ij este o matrice de coeficienți DCT codificati cu coduri Huffman. În dosar sunt dispuse în următoarea ordine: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20
Citirea unui fișier
După ce am extras comentariul, ar trebui să fie ușor de înțeles că:- Fișierul este împărțit în sectoare precedate de markeri.
- Markerii au lungimea de 2 octeți, cu primul octet.
- Aproape toate sectoarele își stochează lungimea în următorii 2 octeți după marcator.
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 - tabel de cuantizare.
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
Antetul secțiunii este întotdeauna de 3 octeți. În cazul nostru, așa este. Antetul este format din:
Lungime: 0x43 = 67 de octeți
Lungimea valorilor din tabel: 0 (0 - 1 octet, 1 - 2 octet)
[_0]
ID tabel: 0
Restul de 64 de octeți trebuie să umple tabelul 8x8.
Aruncă o privire mai atentă la ordinea în care sunt completate valorile tabelului. Această ordine se numește ordine în zig-zag: 
Marker: SOF0 - Baseline DCT
Acest marker se numește SOF0 și înseamnă că imaginea este codificată prin metoda de bază. Este foarte comun. Dar pe internet, metoda progresivă care vă este cunoscută nu este mai puțin populară, atunci când mai întâi este încărcată o imagine cu rezoluție scăzută, apoi o imagine normală. Acest lucru vă permite să înțelegeți ce este afișat acolo fără a aștepta o descărcare completă. Caietul de sarcini mai definește câteva metode, după cum mi se pare, nu foarte comune.FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01
Lungime: 17 octeți.
Precizie: 8 biți. În metoda de bază, este întotdeauna 8. După cum am înțeles, aceasta este adâncimea de biți a valorilor canalului.
Înălțimea modelului: 0x10 = 16
Lățimea modelului: 0x10 = 16
Număr de componente: 3. Cel mai adesea acestea sunt Y, Cb, Cr.
Prima componenta:
ID: 1
Diluare orizontală (H 1): 2
[_2]
Decimarea verticală (V 1): 2
ID tabel de cuantizare: 0
componenta a doua:
ID: 2
Diluare orizontală (H 2): 1
[_1]
Rărirea verticală (V 2): 1
a treia componenta:
ID: 3
Diluare orizontală (H 3): 1
[_1]
Rărirea verticală (V 3): 1
ID tabel de cuantizare: 1
Acum vedeți cum să determinați cât de subțire este imaginea. Aflați H max = 2 și V max = 2. Canalul i va fi tăiat în H max / H i ori orizontal și V max / V i ori vertical.
Marcator: DHT (tabelul Huffman)
Această secțiune stochează coduri și valori obținute prin codarea Huffman.FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02
lungime: 21 de octeți.
clasa: 0 (0 - tabelul coeficienților DC, 1 - tabelul coeficienților AC).
[_0]
ID tabel: 0
Lungimea codului Huffman: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Numar de coduri:
Numărul de coduri înseamnă numărul de coduri de lungimea respectivă. Rețineți că secțiunea stochează doar lungimile codurilor, nu codurile în sine. Trebuie să găsim codurile noi înșine. Deci, avem un cod de lungime 1 și unul - de lungime 2. Sunt 2 coduri în total, nu mai există coduri în acest tabel.
Fiecărui cod este asociată o valoare și acestea sunt listate în continuare în fișier. Valorile sunt pe un singur octet, deci citim 2 octeți.
- valoarea primului cod.
- valoarea celui de-al 2-lea cod.
Construirea unui arbore de cod Huffman
Trebuie să construim un arbore binar din tabelul pe care l-am primit în secțiunea DHT. Și deja după acest arbore recunoaștem fiecare cod. Adăugăm valorile în ordinea în care sunt indicate în tabel. Algoritmul este simplu: indiferent unde ne aflăm, încercăm întotdeauna să adăugăm o valoare ramurii din stânga. Și dacă e ocupată, atunci la dreapta. Iar dacă nu este loc acolo, atunci ne întoarcem la un nivel superior și încercăm de acolo. Trebuie să vă opriți la un nivel egal cu lungimea codului. Ramurile din stânga corespund cu 0, ramurile din dreapta - 1.Cometariu:
Nu trebuie să începi de fiecare dată de sus. Valoare adăugată - reveniți cu un nivel în sus. Există ramura potrivită? Dacă da, urcă din nou. Dacă nu, creați ramura potrivită și navigați acolo. Apoi, de acolo, începeți căutarea pentru a adăuga următoarea valoare.
Arbori pentru toate tabelele din acest exemplu: 
UPD (mulțumesc): Nodurile primului arbore (DC, id = 0) trebuie să aibă valorile 0x03 și 0x02
În cercuri - valorile codurilor, sub cercuri - codurile în sine (voi explica că le-am primit, mergând de sus la fiecare nod). Cu astfel de coduri (din acesta și alte tabele) este codificat conținutul figurii în sine.
Marcator: SOS (Start of Scan)
Octetul din marker înseamnă „DA! În cele din urmă, am trecut direct la analizarea secțiunii de imagini codificate! ". Cu toate acestea, secțiunea se numește simbolic SOS.& nbsp FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00
Lungimea părții antet (nu a întregii secțiuni): 12 octeți.
Numărul de componente de scanare. Avem 3, unul pentru Y, Cb, Cr.
Prima componenta:
Număr piesă imagine: 1 (Y)
ID tabel Huffman pentru coeficienții DC: 0
[_0]
ID tabel Huffman pentru coeficienții AC: 0
componenta a doua:
Număr piesă imagine: 2 (Cb)
[_1]
a treia componenta:
Număr componentă a imaginii: 3 (Cr)
ID tabel Huffman pentru coeficienții DC: 1
[_1]
ID tabel Huffman pentru coeficienții AC: 1
Aceste componente se alternează ciclic.
Aici se termină partea antetului, de aici până la sfârșitul (markerul) datelor codificate.
0
Aflarea coeficientului DC.
1.
Citirea unei secvențe de biți (dacă întâlnim 2 octeți, atunci acesta nu este un marker, ci doar un octet)... După fiecare bit, ne deplasăm de-a lungul arborelui Huffman (cu identificatorul corespunzător) de-a lungul ramurilor 0 sau 1, în funcție de bitul citit. Ne oprim dacă suntem în nodul final.
10
1011101110011101100001111100100
2.
Luăm valoarea nodului. Dacă este 0, atunci coeficientul este 0, îl notăm în tabel și trecem la citirea altor coeficienți. În cazul nostru - 02. Această valoare este lungimea coeficientului în biți. Adică citim următorii 2 biți, acesta va fi coeficientul.
10
10
11101110011101100001111100100
3. Dacă prima cifră a valorii în binar este 1, atunci o lăsăm așa cum este: DC_coef = valoare. În caz contrar, transformăm: DC_coef = valoare-2 lungimea valorii +1. Scriem coeficientul în tabel la începutul zigzagului - colțul din stânga sus.
Găsirea coeficienților AC.
1.
Similar cu articolul 1, găsirea coeficientului DC. Continuăm să citim secvența:
10
10
1110
1110011101100001111100100
2.
Luăm valoarea nodului. Dacă este egal cu 0, înseamnă că valorile rămase ale matricei trebuie să fie umplute cu zerouri. Apoi următoarea matrice este codificată. Primii care au citit până aici și mi-au scris despre asta într-un personal, vor primi un plus în karma. În cazul nostru, valoarea nodului este 0x31.
Prima ciugulire: 0x3 - iată câte zerouri trebuie să adăugăm la matrice. Aceștia sunt 3 coeficienți zero.
Al doilea nibble: 0x1 - lungimea coeficientului în biți. Citim următorul fragment.
10
10
1110
1
110011101100001111100100
3. Similar cu articolul 3 al găsirii coeficientului DC.
După cum ați înțeles deja, trebuie să citiți coeficienții AC până când găsim o valoare de cod zero sau până când matricea este umplută.
În cazul nostru, obținem:
10
10
1110
1
1100
11
101
10
0
0
0
1
11110
0
100
si matricea:
Ați observat că valorile sunt completate în aceeași ordine în zig-zag?
Motivul utilizării acestei ordine este simplu - cu cât valorile lui v și u sunt mai mari, cu atât coeficientul S vu în transformarea cosinus discretă este mai puțin semnificativ. Prin urmare, la rapoarte de compresie ridicate, coeficienții nesemnificativi sunt reduși la zero, reducând astfel dimensiunea fișierului.
[-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, am uitat să spun că coeficienții DC codificați nu sunt coeficienții DC în sine, ci diferențele lor între coeficienții din tabelul anterior (același canal)! Este necesar să corectați matricele:
DC pentru al doilea: 2 + (-4) = -2
DC pentru a treia: -2 + 5 = 3
DC pentru al patrulea: 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]
………
Acum e ordine. Această regulă durează până la sfârșitul fișierului.
... și prin matrice pentru 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]
Deoarece aici există o singură matrice, coeficienții DC pot fi lăsați în pace.
Calcule
Cuantizarea
Vă amintiți că matricea trece prin etapa de cuantizare? Elementele matricei trebuie înmulțite termen cu termen cu elementele matricei de cuantizare. Rămâne să-l alegi pe cel de care ai nevoie. În primul rând, am scanat prima componentă, componenta sa imagine = 1. Componenta imagine cu acest identificator folosește matricea de cuantizare 0 (o avem prima dintre cele două). Deci, după înmulțire:
[ 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]
În mod similar, obținem încă 3 matrice ale canalului Y...
[-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 prin matrice pentru 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]
Transformată cosinus discretă inversă
Formula nu ar trebui să fie dificilă *. S vu este matricea noastră de coeficienți rezultată. u este o coloană, v este un rând. s yx - valorile canalului direct.
* În general, acest lucru nu este în întregime adevărat. Când am reușit să decodez și să afișez pe ecran imaginea de 16x16, am luat o imagine de 600x600 (apropo, era coperta albumului preferat al lui Mind.In.A.Box, Lost Alone). Nu a funcționat imediat - au apărut diverse bug-uri. În curând am putut admira poza încărcată corect. Doar viteza de descărcare a fost foarte supărătoare. Încă îmi amintesc că a durat 7 secunde. Dar acest lucru nu este surprinzător, dacă utilizați fără gânduri formula de mai sus, atunci pentru a calcula un canal de un pixel, va trebui să găsiți 128 cosinus, 768 înmulțiri și unele adunări acolo. Gândește-te doar la asta - aproape o mie de operații dificile pe un singur canal de un pixel! Din fericire, există loc de optimizare (după o mulțime de experimente, am redus timpul de încărcare până la limita de 15 ms acuratețe a cronometrului, iar după aceea am schimbat imaginea într-o fotografie de 25 de ori mai mare. Poate voi scrie despre asta într-o altă formă separată). articol).
Voi scrie rezultatul calculării numai a primei matrice a canalului Y (valorile sunt rotunjite):
[ 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 restul de 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, hai să mâncăm!
- Da, nu intru deloc, despre ce este vorba.
- Odată ce valorile culorii YCbCr sunt primite, rămâne să convertiți în RGB, astfel: YCbCrToRGB (Y ij, Cb ij, Cr ij), Y ij, Cb ij, Cr ij - matricele noastre rezultate.
- 4 matrice Y și câte una Cb și Cr, deoarece am subțiat canalele și 4 pixeli din Y corespund unui Cb și Cr. Prin urmare, calculați astfel: YCbCrToRGB (Y ij, Cb, Cr)
YCbCr la RGB
R = Y + 1,402 * CrG = Y - 0,34414 * Cb - 0,71414 * Cr
B = Y + 1,772 * Cb
Nu uitați să adăugați 128. Dacă valorile sunt în afara intervalului, atunci atribuiți valorile limită. Formula este simplă, dar consumă și o fracțiune din timpul CPU.
Iată tabelele rezultate pentru canalele R, G, B pentru pătratul 8x8 din stânga sus al exemplului nostru:
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
Sfârșit
În general, nu sunt un specialist JPEG, așa că cu greu pot răspunde la toate întrebările. Doar că atunci când îmi scriam decodorul, trebuia adesea să mă confrunt cu diverse probleme de neînțeles. Și când imaginea a fost afișată incorect, nu știam unde am făcut o greșeală. Poate că a interpretat greșit părțile, sau poate că a folosit greșit DCT. Am ratat un exemplu pas cu pas, așa că sper că acest articol vă va ajuta când scrieți un decodor. Cred că acoperă descrierea metodei de bază, dar totuși nu o poți face doar. Iată câteva link-uri care m-au ajutat:JPEG este unul dintre cei mai noi și mai puternici algoritmi. În practică, este standardul de facto pentru imagini color. Algoritmul operează cu zone de 8x8, unde luminozitatea și culoarea se schimbă relativ ușor. Ca urmare, atunci când matricea unei astfel de regiuni este extinsă într-o serie dublă în cosinus (formulele de mai jos), doar primii coeficienți sunt semnificativi. Astfel, compresia în JPFG se realizează în detrimentul modificărilor netede ale culorilor din imagine.
Algoritmul a fost dezvoltat de un grup de experți în fotografie special pentru comprimarea imaginilor JPEG pe 24 de biți - Joint Photographic Expert Group - o divizie din cadrul ISO - Organizația Internațională pentru Standardizare. În general, algoritmul se bazează pe o transformată discretă cosinus (denumită în continuare DCT), aplicată matricei imaginii pentru a obține o nouă matrice de coeficienți. Pentru a obține imaginea originală se aplică transformarea inversă
DCT descompune imaginea în amplitudinile unor frecvențe, astfel, în timpul transformării, obținem o matrice în care mulți coeficienți sunt fie apropiați, fie egali cu zero. În plus, sistemul uman de percepție a culorii este slab la recunoașterea anumitor frecvențe. Prin urmare, este posibil să se aproximeze unii coeficienți mai aproximativ fără o pierdere vizibilă a calității imaginii.
Pentru aceasta se folosește cuantizarea. În cel mai simplu caz, este o deplasare aritmetică pe biți la dreapta. Cu această transformare, unele informații se pierd, dar se pot obține rapoarte mari de compresie.
Operarea algoritmului.
Să comprimăm o imagine pe 24 de biți.
Pasul I.
Traducem imaginea din spațiul de culoare RGB, cu componentele responsabile pentru componentele roșie (roșu), verde (verde) și albastru (albastru) ale culorii punctului, în spațiul de culoare YCrCb (numit uneori YUV).
În ea, Y este componenta luminozității, iar Cg, Cb sunt componentele responsabile pentru culoare (roșu cromatic și albastru cromatic). Datorită faptului că ochiul uman este mai puțin sensibil la culoare decât la luminozitate, devine posibilă arhivarea matricelor pentru componente Cg și Cb cu pierderi mari și, în consecință, cu rapoarte de compresie ridicate. Această transformare a fost folosită de mult în televiziune. O bandă de frecvență mai îngustă este alocată semnalelor responsabile de culoare.
Translația simplificată din spațiul de culoare RGB în spațiul de culoare YCrCb poate fi reprezentată după cum urmează:
Transformarea inversă se realizează prin înmulțirea vectorului YUV cu matricea inversă:
Pasul 2.
Împărțiți imaginea originală în matrici de 8x8. Formăm trei matrice DCT de lucru din fiecare - 8 biți separat pentru fiecare componentă. La rapoarte de compresie mai mari, acest pas poate fi puțin mai dificil. Imaginea este împărțită la componenta Y - ca în primul caz, iar pentru componentele Cr și Cb matricele sunt tastate printr-o linie și printr-o coloană. Acestea. din matricea originală 16x16, se obține o singură matrice DCT funcțională. Mai mult, așa cum este ușor de observat, pierdem 3/4 din informațiile utile despre componentele de culoare ale imaginii și obținem imediat o compresie de două ori. Putem face acest lucru lucrând în spațiul YCrCb. După cum a arătat practica, acest lucru nu afectează semnificativ imaginea RGB rezultată.
Pasul 3.
Aplicam DCT la fiecare matrice de lucru. În acest caz, obținem o matrice în care coeficienții din colțul din stânga sus corespund componentei de joasă frecvență a imaginii, iar în dreapta jos - celei de înaltă frecvență.
Într-o formă simplificată, acea transformare poate fi reprezentată după cum urmează:
Pasul 4.
Efectuăm cuantificare. În principiu, aceasta este pur și simplu împărțirea matricei de lucru la elementul cu element al matricei de cuantizare. Pentru fiecare componentă (Y, U și V), în cazul general, se specifică propria matrice de cuantizare (denumită în continuare MK).
În acest pas, raportul de compresie este controlat și are loc cea mai mare pierdere. Este clar că prin specificarea MK cu coeficienți mari, vom obține mai multe zerouri și, prin urmare, un raport de compresie mai mare.
Cuantizarea este, de asemenea, asociată cu efecte specifice ale algoritmului. La valori mari ale coeficientului gamma , - pierderea în frecvențe joase poate fi atât de mare încât imaginea se împarte în pătrate de 8x8. Pierderile la frecvențe înalte se pot manifesta în așa-numitul „efect Gibbs”, când se formează un fel de „aureolă” în jurul contururilor cu o tranziție de culoare ascuțită.
Pasul 5.
Traducem matricea 8x8 într-un vector de 64 de elemente folosind o scanare în zig-zag, de exemplu. selectați elemente cu indici (0,0). (0,1). (1,0). (2.0) ...
Astfel, la începutul vectorului, obținem coeficienții matricei corespunzători frecvențelor joase, iar la sfârșit - frecvențe înalte.
Pasul 6.
Convoluția vectorului folosind algoritmul de codare de grup. În acest caz, obținem perechi de tipul (sărire, număr), unde „sărire” este contorul de zerouri ignorate, iar „număr” este valoarea care trebuie pusă în celula următoare.
Deci, vectorul va fi pliat în perechi (0, 42) (0, 3) (3, -2) (4, 1)
Pasul 7.
Reducem perechile învățate prin codificarea Huffman cu un tabel fix.
Procesul de restaurare a imaginii în acest algoritm este complet simetric. Metoda vă permite să comprimați unele imagini de 10-15 ori fără pierderi serioase.
Conducta de operare utilizată în algoritmul JPEG.
Aspectele pozitive semnificative ale algoritmului sunt următoarele:
- 1) Raportul de compresie este setat
- 2) Imaginea color de ieșire poate fi de 24 de biți pe punct.
Dezavantajele algoritmului sunt următoarele:
- 1) Când raportul de compresie este crescut, imaginea se împarte în pătrate separate (8x8). Acest lucru se datorează faptului că pierderile mari apar la frecvențe joase în timpul cuantizării și devine imposibilă restabilirea datelor originale.
- 2) Apare efectul Gibbs - halouri de-a lungul limitelor tranzițiilor clare de culoare.
JPEG a fost standardizat relativ recent - în 1991. Dar chiar și atunci au existat algoritmi care se comprimă mai puternic cu mai puțină pierdere de calitate. Cert este că acțiunile dezvoltatorilor standardului au fost limitate de puterea tehnologiei care exista în acel moment. Adică, chiar și pe un computer personal, algoritmul trebuia să funcționeze mai puțin de un minut pe o imagine medie, iar implementarea sa hardware trebuia să fie relativ simplă și ieftină. Algoritmul trebuia să fie simetric (timpul de decompresie este aproximativ egal cu timpul de arhivare).
Această ultimă cerință a făcut posibilă apariția camerelor digitale - dispozitive de dimensiunea unei camere video mici care captează fotografii pe 24 de biți pe un card flash de 10-20 MB cu interfață PCMCIA. Apoi cardul este introdus în slotul de pe laptop și programul corespunzător vă permite să citiți imaginile. Dacă algoritmul ar fi asimetric, ar fi neplăcut să așteptați mult timp până când dispozitivul se „reîncărcă” - va comprima imaginea.
O caracteristică nu foarte plăcută a JPEG este și faptul că adesea dungile orizontale și verticale de pe afișaj sunt complet invizibile și pot apărea numai atunci când sunt imprimate sub forma unui model moire. Apare atunci când un ecran de imprimare oblic este suprapus pe dungile orizontale și verticale ale imaginii. Din cauza acestor surprize, JPEG nu este recomandat să fie utilizat activ în tipărire, stabilind coeficienți mari. Cu toate acestea, atunci când arhivează și imaginile destinate vizionării umane, este în prezent de neînlocuit.
Utilizarea pe scară largă a JPEG a fost constrânsă de mult timp, poate doar de faptul că funcționează cu imagini pe 24 de biți. Prin urmare, pentru a vizualiza o imagine cu o calitate acceptabilă pe un monitor obișnuit într-o paletă de 256 de culori, a fost necesar să se folosească algoritmii corespunzători și, prin urmare, o anumită perioadă de timp. În aplicațiile destinate unui utilizator pretențios, cum ar fi jocurile, astfel de întârzieri sunt inacceptabile. În plus, dacă imaginile pe care le aveți, de exemplu, sunt convertite în format GIF de 8 biți în JPEG de 24 de biți și apoi înapoi în GIF pentru vizualizare, atunci pierderea calității va avea loc de două ori cu ambele conversii. Cu toate acestea, câștigul în dimensiunea arhivelor este adesea atât de mare (de 3-20 de ori!), Iar pierderea de calitate este atât de mică încât stocarea imaginilor în JPEG este foarte eficientă.
Câteva cuvinte ar trebui spuse despre modificările acestui algoritm. Deși JPEG este un standard ISO, formatul său de fișier nu a fost remediat. Profitând de acest lucru, producătorii folosesc propriile formate incompatibile și, prin urmare, pot schimba algoritmul. Deci, tabelele interne ale algoritmului, recomandate de ISO. sunt înlocuite de ei cu propriile lor Krone, în plus, există o ușoară confuzie la stabilirea gradului de pierderi. De exemplu, la testare, se dovedește că calitatea „excelentă”, „100%” și „10 puncte” oferă imagini semnificativ diferite. Mai mult, apropo, calitatea „100%” nu înseamnă compresie fără pierderi. Există, de asemenea, opțiuni JPEG pentru aplicații specifice.
Ca standard ISO, JPEG devine din ce în ce mai utilizat în schimbul de imagini prin rețelele de computere. Algoritmul JPEG este suportat în formatele Quick Time, PostScript Level 2, Tiff 6.0 și, în acest moment, ocupă un loc proeminent în sistemele multimedia.
Caracteristicile algoritmului JPFG:
Raport de compresie: 2-200 (definit de utilizator).
Clasa de imagine: Imagini color pe 24 de biți sau imagini în tonuri de gri fără tranziții abrupte de culoare (fotografii).
Simetrie: 1.
Caracteristici speciale: În unele cazuri, algoritmul creează un „aureolă” în jurul marginilor orizontale și verticale tăiate din imagine (efectul Gibbs). În plus, când raportul de compresie este mare, imaginea este împărțită în blocuri de 8x8 pixeli.
(pronunțat „japeg” Joint Photographic Experts Group, după numele organizației dezvoltatorului) este unul dintre formatele grafice populare utilizate pentru stocarea imaginilor fotografice și a imaginilor similare. Fișierele care conțin date JPEG au de obicei extensiile .jpeg, .jfif, .jpg, .JPG sau .JPE. Dintre acestea, totuși, .jpg este cea mai populară extensie pe toate platformele.
1. Grupul mixt de experți fotografici;
2. O metodă de comprimare a imaginii dezvoltată de acest grup și un format grafic corespunzător folosit adesea pe WWW. Se caracterizează prin compactitatea fișierelor și, în consecință, prin transfer rapid, precum și prin „pierderea” calității imaginii. Folosit în principal pentru fotografii, deoarece pierderea calității este mai puțin critică pentru acestea. Păstrează setările de culoare în spațiul de culoare RGB.
Jpeg(pronunțat „ japeg", ing. Grupul mixt de experți fotografici, după numele dezvoltatorului) este unul dintre formatele grafice populare folosite pentru a stoca imagini fotografice și imagini similare. Fișierele care conțin date JPEG au de obicei extensiile .jpeg, .jfif, .jpg, .JPG, sau .JP E... Cu toate acestea, printre ei .jpg cea mai populară extensie pe toate platformele. Tipul MIME este image/jpeg.
JPEG este un algoritm de compresie a datelor cu pierderi.
Zona de aplicare
Algoritmul JPEG este cel mai potrivit pentru comprimarea fotografiilor și picturilor care conțin scene realiste cu tranziții fine în luminozitate și culoare. JPEG este utilizat pe scară largă în fotografia digitală și pentru stocarea și transmiterea imaginilor folosind Internetul.
Pe de altă parte, JPEG este de puțin folos pentru comprimarea desenelor, a textului și a caracterelor grafice, unde un contrast puternic între pixelii adiacenți duce la artefacte vizibile. Este recomandabil să salvați astfel de imagini în formate fără pierderi, cum ar fi TIFF, GIF, PNG sau RAW.
JPEG (ca și alte metode de compresie cu distorsiuni) nu este potrivit pentru comprimarea imaginilor cu procesare în mai multe etape, deoarece distorsiunile vor fi introduse în imagini de fiecare dată când rezultatele procesării intermediare sunt salvate.
De asemenea, JPEG nu ar trebui utilizat în cazurile în care chiar și pierderea minimă este inacceptabilă, de exemplu, la comprimarea imaginilor astronomice sau medicale. În astfel de cazuri, poate fi recomandat modul de compresie Lossless JPEG furnizat de standardul JPEG (care, din păcate, nu este acceptat de majoritatea codecurilor populare) sau standardul de compresie JPEG-LS.
Comprimare
Când este comprimată, imaginea este convertită din RGB în YCbCr (YUV). Trebuie remarcat faptul că standardul JPEG (ISO / IEC 10918-1) nu reglementează în niciun fel alegerea YCbCr, permițând alte tipuri de conversie (de exemplu, cu un număr de componente altele decât trei) și compresia fără conversie. (direct la RGB), totuși, specificația JFIF (JPEG File Interchange Format, propusă în 1991 de C-Cube Microsystems, și acum standardul de facto) presupune utilizarea conversiei RGB-> YCbCr.
După conversia RGB-> YCbCr pentru canalele de imagine Cb și Cr responsabile de culoare, se poate efectua „subsampling”, ceea ce înseamnă că fiecărui bloc de 4 pixeli (2x2) din canalul de luminanță Y i se atribuie valori medii Cb și Cr ( schema de decimare „4: 2: 0”). În același timp, pentru fiecare bloc 2x2, în loc de 12 valori (4 Y, 4 Cb și 4 Cr), se folosesc doar 6 (4 Y și un Cb și Cr mediu). Dacă se impun cerințe sporite asupra calității imaginii recuperate după compresie, decimarea poate fi efectuată doar într-o singură direcție - vertical (schema „4: 4: 0”) sau orizontal („4: 2: 2”) sau nu. deloc ("4: 4: 4").
Standardul permite, de asemenea, decimarea cu media Cb și Cr nu pentru un bloc 2x2, ci pentru patru pixeli consecutivi (vertical sau orizontal), adică pentru blocuri 1x4, 4x1 (schema 4: 1: 1), precum și 2x4 și 4x2 . De asemenea, este permisă utilizarea diferitelor tipuri de decimare pentru Cb și Cr, dar în practică astfel de scheme sunt rareori utilizate.
În plus, componenta luma Y și componentele Cb și Cr responsabile pentru culoare sunt împărțite în blocuri de 8x8 pixeli. Fiecare astfel de bloc suferă o transformare cosinus discretă (DCT). Coeficienții DCT obținuți sunt cuantificați (pentru Y, Cb și Cr, în cazul general, sunt utilizate diferite matrice de cuantizare) și împachetați folosind coduri Huffman. Standardul JPEG permite, de asemenea, utilizarea unei codări aritmetice mult mai eficiente, însă, din cauza restricțiilor de brevet (brevetul pentru codificatorul aritmetic QM descris în standardul JPEG aparține IBM), acesta nu este utilizat în practică.
Matricele utilizate pentru cuantificarea coeficienților DCT sunt stocate în porțiunea antet a fișierului JPEG. Ele sunt de obicei construite astfel încât coeficienții de înaltă frecvență să fie cuantificați mai puternic decât cei de joasă frecvență. Acest lucru duce la grosierul detaliilor fine din imagine. Cu cât raportul de compresie este mai mare, cu atât toți coeficienții sunt cuantificați mai puternic.
Când salvați o imagine într-un fișier JPEG, este specificat parametrul de calitate, specificat în unele unități arbitrare, de exemplu, de la 1 la 100 sau de la 1 la 10. Un număr mai mare corespunde de obicei unei calități mai bune (și unei dimensiuni mai mari a fișierului comprimat). ). Totuși, chiar și atunci când se folosește cea mai înaltă calitate (corespunzând unei matrice de cuantizare formată numai din unele), imaginea reconstruită nu va coincide exact cu cea inițială, care este asociată atât cu acuratețea finală a execuției DCT, cât și cu necesitatea rotunjirii valorile Y, Cb, Cr și coeficienții DCT la cel mai apropiat întreg. Modul de compresie Lossless JPEG, care nu folosește DCT, oferă o potrivire exactă a imaginilor reconstruite și originale, cu toate acestea, eficiența sa scăzută (raportul de compresie depășește rar 2) și lipsa suportului din partea dezvoltatorilor de software nu au contribuit la popularitatea JPEG fără pierderi. .
Varietăți de scheme de compresie JPEG
Standardul JPEG oferă două moduri principale de reprezentare a datelor codificate.
Cea mai comună, acceptată de majoritatea codec-urilor disponibile, este reprezentarea secvențială JPEG a datelor, care implică parcurgerea secvențială a imaginii codificate bloc cu bloc de la stânga la dreapta, de sus în jos. Operațiile descrise mai sus sunt efectuate pe fiecare bloc de imagine codificat, iar rezultatele codificării sunt plasate în fluxul de ieșire sub forma unei singure „scanări”, adică. matrice de date codificate corespunzătoare imaginii parcurse secvenţial ("scanat"). Linia de bază sau modul de codificare „linia de bază” permite doar această reprezentare. Modul extins (extins), împreună cu cel secvenţial, permite, de asemenea, prezentarea progresivă (JPEG progresivă) a datelor.
În cazul JPEG progresiv, datele comprimate sunt scrise în fluxul de ieșire ca un set de scanări, fiecare dintre acestea descriind imaginea în întregime, cu un grad crescând de detaliu. Acest lucru se realizează fie prin înregistrarea în fiecare scanare nu a unui set complet de coeficienți DCT, ci doar a unora dintre ei: mai întâi - joasă frecvență, în următoarele scanări - înaltă frecvență (metoda „selectării spectrale”, adică eșantionarea spectrală) , sau prin secvențial, de la scanare la scanare, rafinarea coeficienților DCT (metoda „aproximație succesivă”, adică aproximări succesive). Această reprezentare progresivă a datelor este utilă în special atunci când transferați imagini comprimate folosind canale de comunicare cu viteză redusă, deoarece vă permite să vă faceți o idee despre întreaga imagine după ce a fost transferată doar o mică parte din fișierul JPEG.
Ambele scheme descrise (atât JPEG secvențial, cât și progresiv) se bazează pe DCT și, în principiu, nu permit obținerea unei imagini reconstruite care să fie absolut identică cu cea originală. Cu toate acestea, standardul permite și compresia care nu folosește DCT, ci este construită pe baza unui predictor liniar (lossless, adică „fără pierderi”, JPEG), care garantează coincidența completă, bit-cu-bit, a originalului și reconstruit. imagini. În același timp, raportul de compresie pentru imaginile fotografice ajunge rareori la 2, dar absența garantată a distorsiunii în unele cazuri se dovedește a fi solicitată. Rate de compresie considerabil mai mari pot fi obținute folosind metoda de compresie JPEG-LS descrisă de ISO / IEC 14495-1, care, în ciuda asemănării denumirilor, nu este direct legată de standardul JPEG ISO / IEC 10918-1 (ITU T.81). Recomandare) (Recomandarea ITU T.87).
Sintaxa și structura JPEG
Fișierul JPEG conține o secvență markere, fiecare dintre care începe cu octetul 0xFF, indicând începutul markerului și byte - identificator. Unii markeri constau numai din această pereche de octeți, în timp ce alții conțin date suplimentare constând dintr-un câmp de doi octeți cu lungimea părții informaționale a marcatorului (inclusiv lungimea acestui câmp, dar minus cei doi octeți ai începutului marker, adică 0xFF și identificatorul) și datele în sine.
| Marker | octeți | Lungime | Programare |
|---|
JPEG este unul dintre algoritmii noi și suficient de puternici. În practică, este standardul de facto pentru imagini color. Algoritmul operează cu zone de 8x8, unde luminozitatea și culoarea se schimbă relativ ușor. Ca urmare, la descompunerea unei astfel de matrice, aria dintr-un rând dublu în cosinus (a se vedea formulele de mai jos) este considerată semnificativă numai de primii coeficienți.Astfel, compresia în JPEG se realizează datorită netedei modificărilor de culoare în imagine.
Un algoritm dezvoltat de un grup de experți în fotografie special pentru comprimarea imaginilor pe 24 de biți. JPEG - Joint Photographic Expert Group este o divizie din cadrul ISO - Organizația Internațională pentru Standardizare. Numele algoritmului este [„jei” peg]. În general, algoritmul se bazează pe o transformare cosinus discretă (denumită în continuare DCT), care este aplicată matricei imaginii pentru a obține o nouă matrice de coeficienți. Pentru a obține imaginea originală se aplică o transformare inversă.
DCT descompune imaginea în amplitudinile anumitor frecvențe. Astfel, la transformare, obținem o matrice în care mulți coeficienți sunt fie apropiați, fie egali cu zero. În plus, din cauza imperfecțiunii vederii umane, coeficienții pot fi aproximați mai aproximativ fără pierderea vizibilă a calității imaginii.
Pentru aceasta se folosește cuantizarea. În cel mai simplu caz, este o deplasare aritmetică pe biți la dreapta. Cu această transformare, unele informații se pierd, dar se poate obține un raport de compresie mare.
Cum funcționează algoritmul
Deci, să luăm în considerare algoritmul mai detaliat (Fig. 2.1). Să presupunem că comprimăm o imagine pe 24 de biți.
Pasul 1. Traducem imaginea din spațiul de culoare RGB, cu componentele responsabile pentru componentele roșie (roșu), verde (verde) și albastru (albastru) ale culorii punctului, în spațiul de culoare YCrCb (numit uneori YUV).
În ea, Y este componenta luminozității, iar Cr, Co sunt componentele responsabile pentru culoare (roșu cromatic și albastru cromatic). Datorită faptului că ochiul uman este mai puțin sensibil la culoare decât la luminozitate, devine posibilă arhivarea matricelor pentru componentele Cr și Co cu pierderi mari și, în consecință, cu rapoarte mari de compresie.O astfel de transformare a fost folosită de mult timp în televiziune. O bandă de frecvență mai îngustă este alocată semnalelor responsabile de culoare. Translația simplificată din spațiul de culoare RGB în spațiul de culoare YCrCb poate fi reprezentată folosind o matrice de tranziție:
Pasul 2.Împărțiți imaginea originală în matrici de 8x8. Formăm 3 matrice DCT de lucru din fiecare - 8 biți separat pentru fiecare componentă. La rapoarte de compresie mai mari, acest pas poate fi puțin mai dificil. Imaginea este împărțită la componenta Y, ca în primul caz, iar pentru componentele Cr și Cb, matricele sunt tastate printr-o linie și printr-o coloană. Adică, din matricea originală 16x16, se obține o singură matrice DCT funcțională. În același timp, așa cum este ușor de observat, pierdem 3/4 din informațiile utile despre componentele de culoare ale imaginii și obținem imediat o compresie de 2 ori. Putem face acest lucru lucrând în spațiul YCrCb. După cum a arătat practica, acest lucru are un efect redus asupra imaginii RGB rezultate.
Pasul 3.Într-o formă simplificată, DCT pentru n = 8 poate fi reprezentat după cum urmează:
nu, v] = ^ Hc (i, u) xC (j, v) y r Y) Yq= IntegerRound În acest pas, raportul de compresie este controlat și are loc cea mai mare pierdere. Este clar că prin specificarea MK cu coeficienți mari, vom obține mai multe zerouri și, prin urmare, un raport de compresie mai mare. Cuantizarea este, de asemenea, asociată cu efecte specifice ale algoritmului. La valori gamma ridicate, pierderea la frecvențe joase poate fi atât de mare încât imaginea se împarte în pătrate de 8x8. Pierderile în frecvențe înalte se pot manifesta în așa-numitele efectul Gibbs, când se formează un fel de „aureolă” în jurul contururilor cu o tranziție de culoare ascuțită. Etapa 5. Traducem matricea 8x8 într-un vector de 64 de elemente folosind scanarea „zig-zag”, adică luăm elementele cu indici (0,0), (0,1), (1,0), ( 2,0)... Astfel, la începutul vectorului, obținem coeficienții matricei corespunzători frecvențelor joase, iar la sfârșit - frecvențe înalte. Pasul 6. Convoluția vectorului folosind algoritmul de codare de grup. În acest caz, obținem perechi de tip<пропустить, число>unde „săriți” este numărul de zerouri de ignorat și „număr” este valoarea de pus în celula următoare. Deci, vectorul 42 3000-2 00001 ... va fi pliat în perechi (0,42) (0,3) (3, -2) (4,1) .... Etapa 7. Convoluți perechile rezultate prin codificarea Huffman cu un tabel fix. Procesul de restaurare a imaginii în acest algoritm este complet simetric. Metoda vă permite să comprimați unele imagini de 10-15 ori fără pierderi serioase. Aspectele pozitive semnificative ale algoritmului sunt următoarele: ■ se stabileşte gradul de compresie; ■ imaginea color de ieșire poate fi de 24 de biți per punct. Dezavantajele algoritmului sunt următoarele: ■ Mărirea raportului de compresie împarte imaginea în pătrate separate (8x8). Acest lucru se datorează faptului că pierderile mari apar la frecvențe joase în timpul cuantizării și devine imposibilă restabilirea datelor originale. ■ Apare efectul Gibbs - halouri de-a lungul marginilor tranzițiilor clare de culoare. După cum am menționat deja, JPEG a fost standardizat relativ recent - în 1991. Dar chiar și atunci au existat algoritmi care se comprimă mai puternic cu o pierdere mai mică de calitate. Cert este că acțiunile dezvoltatorilor standardului au fost limitate de puterea tehnologiei care exista în acel moment. Adică, chiar și pe un PC, algoritmul trebuia să funcționeze mai puțin de un minut pe o imagine medie, iar implementarea sa hardware trebuia să fie relativ simplă și ieftină. Algoritmul trebuia să fie simetric (timpul de decompresie este aproximativ egal cu timpul de arhivare). Îndeplinirea acestei din urmă cerințe a făcut posibilă apariția unor dispozitive precum camerele digitale care realizează fotografii pe 24 de biți pe un card flash de 8-256 MB. „Acest card este introdus într-un slot de pe laptop și programul corespunzător vă permite să citiți imagini.Nu este adevărat. Nya, dacă algoritmul ar fi asimetric, ar fi neplăcut să așteptați mult timp până când dispozitivul se „reîncărcă” - va comprima imaginea. O caracteristică nu foarte frumoasă a JPEG este, de asemenea atunci, că adesea dungile orizontale și verticale de pe afișaj sunt complet invizibile și pot apărea doar atunci când se imprimă sub forma unui model moire. Apare atunci când un ecran de imprimare oblic este suprapus pe dungile orizontale și verticale ale imaginii. Din cauza acestor surprize, JPEG-urile nu sunt recomandat în mod activ utilizare în tipărire, stabilirea coeficienților înalți ai matricei de cuantizare. Cu toate acestea, atunci când se arhivează imagini destinate vizionării umane, în prezent este de neînlocuit. Lat Utilizarea JPEG a fost constrânsă de mult timp, poate doar de faptul că funcționează cu imagini pe 24 de biți. Prin urmare, pentru a vizualiza o imagine cu o calitate acceptabilă pe un monitor obișnuit într-o paletă de 256 de culori, a fost necesar să se folosească algoritmii corespunzători și, prin urmare, o anumită perioadă de timp. În aplicațiile destinate unui utilizator pretențios, cum ar fi jocurile, astfel de întârzieri sunt inacceptabile. În plus, dacă imaginile pe care le aveți, de exemplu, sunt convertite în format GIF de 8 biți în JPEG de 24 de biți și apoi înapoi în GIF pentru vizionare, atunci pierderea calității va avea loc de două ori cu ambele conversii. Cu toate acestea, câștigul în dimensiunea arhivelor este adesea atât de mare (3-20 de ori), iar pierderea calității este atât de mică încât stocarea imaginilor în JPEG se dovedește a fi foarte eficientă. Câteva cuvinte ar trebui spuse despre modificările acestui algoritm. Deși JPEG este un standard ISO, formatul său de fișier nu a fost remediat. Folosind aceasta, producătorii își creează propriile formate incompatibile și, prin urmare, pot schimba algoritmul. Astfel, tabelele interne ale algoritmului recomandat de ISO sunt înlocuite de acestea cu propriile lor. În plus, există un pic de confuzie atunci când specificați o rată de pierdere. De exemplu, la testare, se dovedește că calitatea „excelentă”, „100%” și „10 puncte” oferă imagini semnificativ diferite. În același timp, apropo, calitatea „100%” nu înseamnă compresie fără pierderi. Există, de asemenea, opțiuni JPEG pentru aplicații specifice. Ca standard ISO, JPEG devine din ce în ce mai utilizat în schimbul de imagini prin rețelele de computere. Algoritmul JPEG este acceptat în Quick Time, PostScript Level 2, Tiff 6.0 și ocupă în prezent un loc proeminent în sistemele multimedia. Caracteristicile algoritmului JPEG: o! NS. ,. Rata compresiei: 2-200 (definit de utilizator). , c,: _ ,. ... Clasa de imagine: imagini pline de culoare 2jj.bit sau izo- | imagini în tonuri de gri fără tranziții abrupte de culoare (fotografii). Simetrie: 1. Caracteristici:în unele cazuri, algoritmul creează! „aureola” în jurul marginilor ascuțite orizontale și verticale din imagine (efectul Gibbs). În plus, cu un raport de compresie ridicat, iso-! Reflexia este împărțită în blocuri de 8x8 pixeli.
