Algoritmul a fost dezvoltat de Joint Photographic Expert Group special pentru comprimarea imaginilor pe 24 de biți și în tonuri de gri în 1991. Acest algoritm nu comprimă foarte bine imaginile cu două niveluri, dar face o treabă bună în manipularea imaginilor cu tonuri continue în care pixelii apropiați 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 blocuri de imagini disjunse de 8x8 pixeli. DCT descompune aceste blocuri în funcție de amplitudinile anumitor frecvențe. Rezultatul este o matrice în care mulți coeficienți, de regulă, sunt aproape de zero, care pot fi reprezentați în formă numerică aproximativă, i.e. în formă cuantificată fără pierderi semnificative în calitatea restaurării.
Să luăm în considerare funcționarea algoritmului mai detaliat. Să presupunem că o imagine colorată pe 24 de biți este comprimată. În acest caz, obținem următoarele etape de lucru.
Pasul 1. Convertim imaginea din spațiul RGB în spațiul YCbCr folosind următoarea expresie:
Să observăm imediat că transformarea inversă se obține ușor prin înmulțire matrice inversăîntr-un vector, care este în esență spațiu YUV:
.
Pasul 2.Împărțim 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 formatul 4:2:0, adică. componentele pentru Cb și Cr sunt luate prin punct în rânduri și coloane.
Pasul 3. Aplicarea DCT la blocuri de imagini de 8x8 pixeli. În mod formal, DCT direct pentru un bloc 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 în avans funcțiile cosinus și de a tabulare rezultatele. Mai mult, dată fiind ortogonalitatea funcțiilor cosinus cu frecvente diferite, formula de mai sus poate fi scrisă ca
.
Iată o matrice de 8x8 elemente, care descrie un spațiu cu 8 dimensiuni, pentru a reprezenta coloanele unui bloc din acest spațiu. Matricea 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 tot atâtea adunări, ceea ce este semnificativ mai mic decât calculele directe folosind formula de mai sus. De exemplu, pentru a converti o imagine care măsoară 512x512 pixeli, veți avea nevoie operatii aritmetice. Ținând cont de 3 componente de luminozitate, obținem o valoare de 12.582.912 operații aritmetice. Numărul de înmulțiri și adunări poate fi redus și mai mult prin utilizarea algoritmului rapid de transformare Fourier. 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 rezultat al DCT obținem o matrice în care coeficienții din stânga colțul de sus corespunde componentei de joasă frecvență a imaginii, iar în dreapta jos - 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 utilizator să selecteze în mod independent 64 de coeficienți, astfel încât standardul JPEG utilizează două abordări pentru matricele de cuantizare. Primul este că standardul JPEG include două tabele de cuantizare recomandate: unul pentru luma și unul pentru crominanță. Aceste tabele sunt prezentate mai jos. A doua abordare este de a sintetiza (calcul din mers) un tabel de cuantizare care depinde de un parametru care este specificat de utilizator. Masa în sine este construită conform formulei
Etapa de cuantizare este cea în care raportul de compresie este controlat și unde apar cele mai mari pierderi. Este clar că prin specificarea tabelelor de cuantizare cu coeficienți mari, vom obține mai multe zerouri și, prin urmare, un raport de compresie mai mare.
Efectele specifice ale algoritmului sunt de asemenea asociate cu cuantizarea. La valori mari etapa de cuantizare, pierderile pot fi atât de mari încât imaginea se sparge în pătrate monocromatice de 8x8. La rândul lor, pierderile de frecvențe înalte se pot manifesta în așa-numitul „efect Gibbs”, atunci când se formează un „halo” sub formă de undă în jurul contururilor cu o tranziție de culoare ascuțită.
Pasul 5. Convertim matricea 8x8 într-un vector de 64 de elemente utilizând scanarea în zig-zag (Fig. 2).
Orez. 2. Scanare în zig-zag
Ca rezultat, coeficienții nenuli vor fi, de regulă, scriși la începutul vectorului, iar la sfârșit se vor forma lanțuri de zerouri.
Pasul 6. Transformăm vectorul folosind modificat Algoritmul RLE, la ieșirea cărora 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 restrâns în perechi (0, 1118) (0,3) (3,-2) (4,1) ... .
Trebuie remarcat faptul că primul număr al componentei convertite este în esență egal cu luminozitatea medie a blocului 8x8 și se numește coeficient DC. Același lucru pentru toate blocurile de imagini. Această circumstanță sugerează că coeficienții DC pot fi comprimați în mod eficient dacă vă amintiți nu valorile lor absolute, ci pe cele relative sub forma diferenței dintre coeficientul DC al blocului curent și coeficientul DC al blocului anterior și amintiți-vă primul coeficient ca este. În acest caz, ordonarea coeficienților DC se poate face, de exemplu, astfel (Fig. 3). Coeficienții rămași, care se numesc coeficienți AC, rămân neschimbați.
Pasul 7 Convolum perechile rezultate folosind coduri Huffman neuniforme cu un tabel fix. În plus, pentru coeficienții DC și AC, coduri diferite, adică mese diferite 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, ne-am ghidat de faptul că acest algoritm a trebuit să comprima imaginile destul de repede - nu mai mult de un minut pe imaginea 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 timpul de operare. Performanţă ultima cerință făcut posibila aparitie camere digitale care înregistrează imagini pe 24 de biți. Dacă algoritmul ar fi asimetric, ar fi neplăcut să așteptați mult timp ca dispozitivul să se „reîncarce” și să comprima imaginea.
Cu toate că algoritm JPEGși 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 care sunt incompatibile între ele și, prin urmare, pot schimba algoritmul. Astfel, tabelele interne de algoritmi recomandate de ISO sunt înlocuite cu propriile lor. Există, de asemenea, opțiuni JPEG pentru aplicații specifice.
Este ușor de calculat că o imagine color necomprimată cu o dimensiune de 2000 * 1000 pixeli va avea o dimensiune de aproximativ 6 megaocteți. Dacă vorbim de imagini obținute de la camere sau scanere profesionale Rezoluție înaltă, atunci dimensiunea lor poate fi și mai mare. În ciuda creșterii rapide a capacității dispozitivelor de stocare, diverși algoritmi de compresie a imaginii sunt încă foarte relevanți.
Toți algoritmii existenți pot fi împărțiți în două clase mari:
- Algoritmi de compresie fără pierderi;
- Algoritmi de compresie cu pierderi.
Algoritmi de compresie fără pierderi
Algoritmul RLE
Toți algoritmii Seria RLE se bazează pe o idee foarte simplă: grupurile repetate de elemente sunt înlocuite cu o pereche (număr de repetări, element repetat). Să luăm în considerare acest algoritm folosind exemplul unei secvențe de biți. Această secvență va alterna grupuri de zerouri și unu. În plus, grupurile vor avea adesea mai mult de un element. Apoi, secvența 11111 000000 11111111 00 va corespunde următorului set de numere 5 6 8 2. Aceste numere indică numărul de repetări (numărarea începe de la unii), dar și aceste numere trebuie să fie codificate. Vom presupune că numărul de repetări se află în intervalul de la 0 la 7 (adică 3 biți sunt suficienți pentru a codifica numărul de repetări). Apoi, secvența considerată mai sus este codificată de următoarea secvență de numere 5 6 7 0 1 2. Este ușor de calculat că sunt necesari 21 de biți pentru a codifica secvența originală, iar în cel comprimat metoda RLEÎn formă, această secvență are 18 biți.Deși acest algoritm este foarte simplu, eficiența sa este relativ scăzută. Mai mult, în unele cazuri, utilizarea acestui algoritm nu duce la o scădere, ci la o creștere a lungimii secvenței. De exemplu, luați în considerare următoarea secvență 111 0000 11111111 00. Secvența RL corespunzătoare arată astfel: 3 4 7 0 1 2. Lungimea secvenței originale este de 17 biți, lungimea secvenței comprimate este de 18 biți.
Acest algoritm este cel mai eficient pentru imaginile alb-negru. De asemenea, este adesea folosit ca una dintre etapele intermediare de compresie a algoritmilor mai complexi.
Dicţionar algorithms
Ideea din spatele algoritmilor de dicționar este că lanțurile de elemente ale secvenței originale sunt codificate. Această codificare folosește un dicționar special, care este obținut pe baza secvenței originale.Există o întreagă familie de algoritmi de dicționar, dar ne vom uita la cei mai obișnuiți Algoritmul LZW, numit după dezvoltatorii săi Lepel, Ziv și Welch.
Dicționarul din acest algoritm este un tabel care este umplut cu lanțuri de codare pe măsură ce algoritmul rulează. Când codul comprimat este decodat, dicționarul este restaurat automat, astfel încât nu este nevoie să transmiteți dicționarul împreună cu codul comprimat.
Dicționarul este inițializat cu toate șirurile singleton, adică. primele rânduri ale dicționarului reprezintă alfabetul în care codificăm. În timpul compresiei, se face o căutare pentru cel mai lung lanț deja înregistrat în dicționar. De fiecare dată când se întâlnește un lanț care nu a fost încă scris în dicționar, acesta este adăugat acolo și iese un cod comprimat corespunzător lanțului deja scris în dicționar. În teorie, nu sunt impuse restricții cu privire la dimensiunea dicționarului, dar în practică are sens să se limiteze această dimensiune, deoarece în timp încep să apară lanțuri care nu se mai regăsesc în text. În plus, atunci când dublem dimensiunea tabelului, trebuie să alocăm un bit în plus pentru a stoca coduri comprimate. Pentru a preveni astfel de situații, se introduce cod special, simbolizând inițializarea tabelului cu toate lanțurile singleton.
Să ne uităm la un exemplu de algoritm de compresie. Vom comprima linia cuccuckoocuckoohood. Să presupunem că dicționarul va conține 32 de poziții, ceea ce înseamnă că fiecare dintre codurile sale va ocupa 5 biți. Inițial, dicționarul este completat după cum urmează:
Acest tabel există atât de partea celui care comprimă informația, cât și de partea celui care o decomprimă. Acum ne vom uita la procesul de compresie. 
Tabelul arată procesul de completare a dicționarului. Este ușor de calculat că codul comprimat rezultat durează 105 biți și text original(presupunând că cheltuim 4 biți pentru codificarea unui caracter) durează 116 biți.
În esență, procesul de decodare se reduce la decodarea directă a codurilor și este important ca tabelul să fie inițializat în același mod ca în timpul codificării. Acum să ne uităm la algoritmul de decodare. 
Putem defini complet șirul adăugat în dicționar la pasul i-a doar la i+1. Evident, linia i-a trebuie să se termine cu primul caracter al liniei i+1. Acea. Tocmai ne-am dat seama cum să restabilim un dicționar. Un oarecare interes este situația când este codificată o secvență de forma cScSc, unde c este un caracter și S este un șir, iar cuvântul cS este deja în dicționar. La prima vedere poate părea că decodorul nu va putea rezolva această situație, dar de fapt toate liniile de acest tip trebuie să se termine întotdeauna cu același caracter cu care încep.
Algoritmi de codare statistică
Algoritmii din această serie atribuie cel mai scurt cod comprimat celor mai frecvente elemente ale secvențelor. Acestea. secvențele de aceeași lungime sunt codificate cu coduri comprimate de lungimi diferite. Mai mult, cu cât apare mai des o secvență, cu atât codul comprimat corespunzător este mai scurt.Algoritmul Huffman
Algoritmul Huffman vă permite să construiți coduri de prefix. Vă puteți gândi la codurile de prefix ca fiind căi către arbore binar: un pasaj de la un nod la fiul său din stânga corespunde cu 0 în cod, iar fiului său din dreapta corespunde cu 1. Dacă etichetăm frunzele arborelui cu caracterele de codat, obținem reprezentarea cod prefix sub forma unui arbore binar.Să descriem algoritmul pentru construirea unui arbore Huffman și obținerea codurilor Huffman.
- Caracterele alfabetului de intrare formează o listă de noduri libere. Fiecare frunză are o greutate care egală cu frecvența aspectul simbolului
- Sunt selectate două noduri de arbore libere cu cele mai mici greutăți
- Părintele lor este creat cu o greutate egală cu greutatea lor totală
- Părintele este adăugat la lista de noduri libere, iar cei doi copii ai săi sunt eliminați din această listă
- Un arc care părăsește părintele i se atribuie bitul 1, celuilalt i se atribuie bitul 0
- Pașii începând cu al doilea se repetă până când un singur nod liber rămâne în lista nodurilor libere. Aceasta va fi considerată rădăcina copacului.
Codare aritmetică
Algoritmii de codare aritmetică codifică șiruri de elemente într-o fracție. În acest caz, se ia în considerare distribuția de frecvență a elementelor. Pe acest moment Algoritmii de codare aritmetică sunt protejați de brevete, așa că ne vom uita doar la ideea de bază.Să fie alfabetul nostru format din N simboluri a1,...,aN și, respectiv, frecvențele lor de apariție p1,...,pN. Să împărțim jumătatea de interval. În general, algoritmul se bazează pe o transformare cosinus discretă (denumită în continuare DCT) aplicată matricei de imagine pentru a obține o nouă matrice de coeficienți. Se aplică o transformare inversă pentru a obține imaginea originală.
DCT descompune imaginea în funcție de 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țiunilor vederii umane, este posibil să se aproximeze coeficienții mai grosier fără pierderea vizibilă a calității imaginii.
În acest scop, se utilizează cuantizarea coeficienților. În cel mai simplu caz, aceasta este o schimbare aritmetică pe biți la dreapta. Cu această conversie, unele informații se pierd, dar se poate obține un grad mai mare de compresie.
Cum funcționează algoritmul
Deci, să ne uităm la algoritm mai detaliat (Fig. 2.1). Să comprimăm o imagine pe 24 de biți.
Pasul 1. Convertim imaginea din spațiul de culoare RGB, cu componente responsabile pentru componentele roșu (roșu), verde (verde) și albastru (albastru) ale culorii punctului, în spațiu de culoare YCrCb (uneori numit 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 conversie similară a fost folosită de mult timp în televiziune. O bandă de frecvență mai îngustă este alocată acolo pentru semnalele responsabile de culoare. O traducere 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țim 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ă de componenta Y, ca în primul caz, iar pentru componentele Cr și Cb matricele sunt tastate printr-un rând și printr-o coloană. Adică, din matricea originală 16x16, se obține o singură matrice DCT funcțională. În acest caz, după cum se vede ușor, pierdem 3/4 Informatii utile despre componentele de culoare ale imaginii și obțineți imediat compresie de 2 ori. Putem face acest lucru lucrând în spațiul YCrCb. După cum a arătat practica, acest lucru nu are un efect semnificativ 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 rY) Yq= IntegerRound Acest pas este locul în care raportul de compresie este controlat și unde apar cele mai mari pierderi. Este clar că prin specificarea MK cu coeficienți mari, vom obține mai multe zerouri și, prin urmare, un grad mai mare de compresie. Efectele specifice ale algoritmului sunt de asemenea asociate cu cuantizarea. La valori gamma ridicate, pierderea în frecvențe joase poate fi atât de mare încât imaginea se sparge în pătrate de 8x8. Pierderile la 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 clară de culoare. Etapa 5. Convertim matricea 8x8 într-un vector de 64 de elemente folosind scanarea în zig-zag, adică luăm elemente cu indici (0,0), (0,1), (1,0), (2,0 ).. . Astfel, la începutul vectorului obținem coeficienți de matrice corespunzătoare frecvențelor joase, iar la final - celor înalte. Pasul 6. Restrângem vectorul folosind algoritmul de codificare de grup. În acest caz obținem perechi de tipul<пропустить, число>, unde „săriți” este numărul de zerouri ignorate, iar „număr” este valoarea de pus în celula următoare. Astfel, vectorul 42 3000-2 00001 ... va fi pliat în perechi (0,42) (0,3) (3,-2) (4,1).... Etapa 7. Restrângem perechile rezultate folosind codarea 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 grave. Aspectele pozitive semnificative ale algoritmului sunt următoarele: ■ este setat nivelul de compresie; ■ Imaginea color de ieșire poate fi de 24 de biți pe punct. Aspectele negative ale algoritmului sunt următoarele: ■ Pe măsură ce nivelul de compresie crește, imaginea se împarte în pătrate individuale (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 limitelor 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 s-au comprimat mai puternic, cu mai puține pierderi de calitate. Cert este că acțiunile dezvoltatorilor standard au fost limitate de puterea tehnologiei care exista în acel moment. Adică, chiar și pe un PC, algoritmul trebuia să ruleze mai puțin de un minut pe imaginea medie, iar implementarea sa hardware trebuia să fie relativ simplă și ieftină. Algoritmul trebuia să fie simetric (timpul de dezarhivare este aproximativ egal cu timpul de arhivare). Îndeplinirea acestei din urmă cerințe a făcut posibilă apariția dispozitivelor precum camerele digitale care fac fotografii pe 24 de biți pe un card flash de 8-256 MB." Apoi, acest card este introdus într-un slot al laptopului și programul corespunzător vă permite pentru a citi imaginile.Nu este adevărat Nya, dacă algoritmul ar fi asimetric, ar fi neplăcut să așteptați mult timp ca dispozitivul să se „reîncarce” și să comprima imaginea. O altă proprietate nu foarte plăcută a JPEG este Acea, că adesea dungile orizontale și verticale de pe afișaj sunt complet invizibile și pot apărea numai atunci când se imprimă sub forma unui model moiré. Apare atunci când un raster de imprimare înclinat este suprapus pe dungi orizontale și verticale ale imaginii. Din cauza acestor surprize, JPEG nu este recomandat în mod activ utilizat în tipărire, stabilind coeficienți mari de matrice de cuantizare. Cu toate acestea, atunci când arhivați imagini destinate vizionarii umane, în prezent este indispensabil. Lat Utilizarea JPEG pentru o lungă perioadă de timp a fost restrânsă, poate, doar de faptul că funcționează pe 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ă utilizarea unor algoritmi adecvați și, în consecință, o anumită perioadă de timp. În aplicațiile destinate utilizatorilor pretențioși, cum ar fi jocurile, astfel de întârzieri sunt inacceptabile. În plus, dacă aveți imagini, de exemplu, în format GIF de 8 biți, convertite în JPEG de 24 de biți și apoi înapoi în GIF pentru vizionare, atunci pierderea calității va avea loc de două ori în timpul ambelor conversii. Cu toate acestea, câștigul în dimensiunea arhivei este adesea atât de mare (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 trebuie 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 își creează propriile formate care sunt incompatibile între ele și, prin urmare, pot schimba algoritmul. Astfel, tabelele interne de algoritmi recomandate de ISO sunt înlocuite cu propriile lor. În plus, există o ușoară confuzie la stabilirea gradului de pierdere. De exemplu, în timpul testării, se dovedește că calitatea „excelentă”, „100%” și „10 puncte” oferă imagini semnificativ diferite. Cu toate acestea, 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 pentru schimbul de imagini în rețelele de computere. Algoritmul JPEG este acceptat în formatele Quick Time, PostScript Level 2, Tiff 6.0 și ocupă în prezent un loc proeminent în sistemele multimedia. Caracteristicile algoritmului JPEG: o ! w. ,. Rata compresiei: 2-200 (setat de utilizator). ,ts, :_,. . Clasa de imagine: imagini color 2jj.bit sau izo-| reflexii în tonuri de gri fără tranziții clare de culoare (fotografii). Simetrie: 1. Caracteristici:în unele cazuri algoritmul creează! „aureola” în jurul limitelor orizontale și verticale clare dintr-o imagine (efectul Gibbs). În plus, la un raport de compresie ridicat, iso-! Imaginea este împărțită în blocuri de 8x8 pixeli. Cunoașterea algoritmului JPEG este foarte utilă nu numai pentru compresia imaginii. Folosește teoria din procesarea semnalului digital, analiză matematică, algebră liniară, teoria informației, în special, transformată Fourier, codificare fără pierderi etc. Prin urmare, cunoștințele acumulate pot fi utile oriunde. Dacă doriți, vă sugerez să parcurgeți și dumneavoastră aceiași pași în paralel cu articolul. Verificați cât de adecvat este raționamentul de mai sus pentru diferite imagini, încercați să faceți propriile modificări ale algoritmului. Este foarte interesant. Ca instrument, pot recomanda minunata combinație de Python + NumPy + Matplotlib + PIL(Pillow). Aproape toată munca mea (inclusiv grafica și animația) a fost făcută folosindu-le. Atentie, trafic! O mulțime de ilustrații, grafice și animații (~ 10Mb). În mod ironic, în articolul despre JPEG sunt doar 2 imagini cu acest format din cincizeci. Ne vom antrena pe pisici raton. Imaginea gri de mai sus este luată ca exemplu. Combină bine atât zonele omogene, cât și cele contrastante. Și dacă învățăm să comprimăm gri, atunci nu vor fi probleme cu culoarea. Vă puteți gândi mental la modul în care un semnal ale cărui valori scad treptat de la o valoare maximă la început la o valoare minimă la sfârșit ar putea fi descompus. O aproximare mai mult sau mai puțin adecvată ar putea fi făcută doar de armonici spre final, ceea ce nu este foarte grozav pentru noi. Figura din stânga este o aproximare a unui semnal cu un singur capăt. În dreapta - simetric: Așadar, ți-a venit ideea să vii cu propria ta transformare. Tine minte asta: Blocurile mari nu sunt afișate, deoarece sunt aproape imposibil de distins vizual de 32x32. Acum să ne uităm la diferența absolută cu imaginea originală (amplificată de 2 ori, altfel nimic nu este cu adevărat vizibil): 8x8 oferă rezultate mai bune decât 4x4. O creștere suplimentară a dimensiunii nu mai oferă un avantaj clar vizibil. Deși aș lua în considerare serios 16x16 în loc de 8x8: creșterea complexității cu 33% (mai multe despre complexitate în paragraful următor) oferă o îmbunătățire mică, dar încă vizibilă pentru același număr de coeficienți. Cu toate acestea, alegerea 8x8 pare destul de rezonabilă și poate fi mijlocul de aur. JPEG a fost publicat în 1991. Cred că o astfel de compresie era foarte dificilă pentru procesoarele de atunci. Al doilea argument. Un lucru de reținut este că creșterea dimensiunii blocului va necesita mai multe calcule. Să estimăm cât. Complexitatea conversiei, așa cum știm deja destul de bine: O(N 2), deoarece fiecare coeficient este format din N termeni. Dar, în practică, se folosește un algoritm eficient de transformare rapidă Fourier (FFT). Descrierea sa depășește scopul acestui articol. Complexitatea sa: O(N*logN). Pentru o expansiune bidimensională trebuie să o utilizați de două ori de N ori. Deci complexitatea DCT 2D este O(N 2 logN). Acum să comparăm complexitatea calculării unei imagini cu un singur bloc și mai multe mici: Al treilea argument. Dacă avem o margine ascuțită de culori în imagine, atunci acest lucru va afecta întregul bloc. Poate că ar fi mai bine ca acest bloc să fie suficient de mic, pentru că în multe blocuri învecinate probabil nu va mai exista o asemenea graniță. Cu toate acestea, departe de granițe, atenuarea are loc destul de repede. În plus, granița în sine va arăta mai bine. Să o verificăm folosind un exemplu cu un număr mare de tranziții de contrast, din nou, cu doar un sfert din coeficienți: Iar pentru desert, luați în considerare 5% calitate (când codați în Fast Stone). Apropo, cam 100% calitate. După cum ați putea ghici, în acest caz matricea de cuantizare constă în întregime din unități, adică nu are loc nicio cuantizare. Cu toate acestea, din cauza rotunjirii coeficienților la cel mai apropiat număr întreg, nu putem restabili cu acuratețe imaginea originală. De exemplu, ratonul a păstrat exact 96% din pixeli, dar 4% au fost reduse cu 1/256. Desigur, astfel de „distorsiuni” nu pot fi observate vizual. Exemplul 0(pentru incalzire) Vom desemna cuvinte precum A, B, C... și le vom numi simboluri. Mai mult, orice poate fi ascuns sub simbol: o literă a alfabetului, un cuvânt sau un hipopotam în grădina zoologică. Principalul lucru este că simbolurile identice corespund unor concepte identice, iar altele diferite corespund unora diferite. Deoarece sarcina noastră este o codificare (compresie) eficientă, vom lucra cu biți, deoarece acestea sunt cele mai mici unități de reprezentare a informațiilor. Prin urmare, să scriem lista ca ABBAAABA. În loc de „primul cuvânt” și „al doilea cuvânt”, pot fi folosiți biții 0 și 1. Apoi ABBAAABA este codificat ca 01100010 (8 biți = 1 octet). Exemplul 1 Exemplul 2 Exemplul 3 Exemplul 4 Acum totul este în ordine. Ne-am dat seama cum sunt stocate DC-urile: Să ne uităm la AC: Construim o histogramă a dependenței de cantitate pentru aceste perechi și un arbore Huffman. Caracteristici de implementare în JPEG: Am aflat că fiecare bloc este codificat și stocat într-un fișier ca acesta: Sper că acum înțelegeți algoritmul JPEG intuitiv. Multumesc pentru lectura! UPD Etichete: Adăugați etichete Algoritmul de conversie a unei imagini grafice JPEG constă din mai multe etape efectuate pe imagine secvențial, una după alta: – conversii spațiu de culoare, – subeșantionare, – transformată cosinus discretă (DCT), - cuantificare, – codificare. În etapa de conversie a spațiului de culoare, imaginea este convertită din spațiul de culoare RGB în YCbCr (unde Y este luminozitatea, iar Cb și Cr sunt componentele diferenței de culoare ale punctului imaginii): Aplicarea spațiului YCbCrîn loc de cele obișnuite RGB se explică prin caracteristicile fiziologice ale vederii umane, și anume faptul că sistemul nervos uman are o sensibilitate semnificativ mai mare la luminozitate ( Y) decât la componentele diferențelor de culoare (în acest caz CbȘi Cr). Conversie inversă a spațiului de culoare (de la YCrCb V RGB) are forma: Algoritmul de compresie JPEG vă permite să comprimați imagini cu dimensiuni diferite ale planului de culoare. Să notăm prin x iȘi y eu latime si inaltime i al-lea plan de culoare al imaginii. Lăsa X= max(x i), Y= max(y eu), definim pentru fiecare plan coeficientii Bună= X/ x iȘi V i= Y/ y eu. Cea mai mare valoare pentru XȘi Y conform algoritmului JPEG este 2 16, iar pentru BunăȘi V i– 2 2 . Astfel, lățimea și înălțimea planurilor de culoare pot fi de la 1 la 4 ori mai mici decât dimensiunile celui mai mare plan. Pentru obișnuit RGB imagini, dimensiunile tuturor planurilor de culoare sunt egale. Subeșantionarea constă în reducerea dimensiunii avioanelor CrȘi Cb. Cea mai frecventă reducere este de 2 ori în lățime și de 2 ori în înălțime (vezi Figura 1). Pentru aceasta CrȘi Cb Planurile imaginii sunt împărțite în blocuri cu dimensiunea de 2 pe 2 pixeli, iar blocul este înlocuit cu un eșantion de componente de diferență de culoare (în locul celor 4 eșantioane existente, se pune media lor aritmetică pentru fiecare bloc, ceea ce face ca posibilă reducerea dimensiunii imaginii originale de 2 ori). Figura 1 – Tipuri comune de eșantionare Apoi, separat pentru fiecare componentă a spațiului de culoare Y, CbȘi Cr, se realizează o transformare cosinus discretă directă. Pentru a face acest lucru, imaginea este împărțită în blocuri cu o dimensiune de 8 pe 8 pixeli și fiecare bloc este transformat conform formulei: Utilizarea transformării cosinusului discret vă permite să treceți de la reprezentarea spațială a imaginii la cea spectrală. Transformarea cosinus discretă inversă are forma: După aceasta, puteți trece la cuantificarea informațiilor primite. Ideea cuantizării este de a arunca o anumită cantitate de informații. Se știe că ochiul uman este mai puțin sensibil la frecvențele înalte (în special la frecvențele înalte ale componentelor de diferență de culoare); majoritatea imaginilor fotografice conțin puține componente de înaltă frecvență. În plus, apariția frecvențelor înalte este o consecință a procesului de digitalizare, adică. datorită apariţiei zgomotului de eşantionare şi cuantizare însoţitor. În această etapă, așa-numitul tabele de cuantizare- matrici formate din numere întregi pozitive cu dimensiunea de 8 cu 8, în care sunt împărțite frecvențele corespunzătoare ale blocurilor de imagine, rezultatul este rotunjit la un număr întreg: Procesul de decuantizare folosește aceleași tabele ca și cuantizarea. Decuantizarea constă în înmulțirea frecvențelor cuantificate cu elementele corespunzătoare ale tabelului de cuantizare: Astfel, pe măsură ce factorul de cuantizare crește, cantitatea de informații aruncate crește. Să ne uităm la asta mai detaliat folosind un exemplu. Blocați înainte de cuantizare: 3862, –22, –162, –111, –414, 12, 717, 490, 383, 902, 913, 234, –555, 18, –189, 236, 229, 707, –708, 775, 423, –411, –66, –685, 231, 34, –928, 34, –1221, 647, 98, –824, –394, 128, –307, 757, 10, –21, 431, 427, 324, –874, –367, –103, –308, 74, –1017, 1502, 208, –90, 114, –363, 478, 330, 52, 558, 577, 1094, 62, 19, –810, –157, –979, –98 Tabel de cuantizare (calitate 90): 24, 16, 16, 24, 40, 64, 80, 96, 16, 16, 24, 32, 40, 96, 96, 88, 24, 24, 24, 40, 64, 88, 112, 88, 24, 24, 32, 48, 80, 136, 128, 96, 32, 32, 56, 88, 112, 176, 168, 120, 40, 56, 88, 104, 128, 168, 184, 144, 80, 104, 128, 136, 168, 192, 192, 160, 112, 144, 152, 160, 176, 160, 168, 160 Blocare după cuantizare: 161, –1, –10, –5, –10, 0, 9, 5, 24, 56, 38, 7, –14, 0, –2, 3, 10, 29, –30, 19, 7, –5, –1, –8, 10, 1, –29, 1, –15, 5, 1, –9, –12, 4, –5, 9, 0, 0, 3, 4, 8, –16, –4, –1, –2, 0, –6, 10, 3, –1, 1, –3, 3, 2, 0, 3, 5, 8, 0, 0, –5, –1, –6, –1 3864, –16, –160, –120, –400, 0, 720, 480, 384, 896, 912, 224, –560, 0, –192, 264, 240, 696, –720, 760, 448, –440, –112, –704, 240, 24, –928, 48,–1200, 680, 128, –864, –384, 128, –280, 792, 0, 0, 504, 480, 320, –896, –352, –104, –256, 0,–1104, 1440, 240, –104, 128, –408, 504, 384, 0, 480, 560, 1152, 0, 0, –880, –160,–1008, –160 Tabel de cuantizare (calitate 45): 144, 96, 88, 144, 216, 352, 456, 544, 104, 104, 128, 168, 232, 512, 536, 488, 128, 112, 144, 216, 352, 504, 616, 496, 128, 152, 192, 256, 456, 776, 712, 552, 160, 192, 328, 496, 600, 968, 912, 680, 216, 312, 488, 568, 720, 920, 1000, 816, 432, 568, 696, 776, 912, 1072, 1064, 896, 640, 816, 840, 872, 992, 888, 912, 880 Blocare după cuantizare: 27, 0, –2, –1, –2, 0, 2, 1, 4, 9, 7, 1, –2, 0, 0, 0, 2, 6, –5, 4, 1, –1, 0, –1, 2, 0, –5, 0, –3, 1, 0, –1, –2, 1, –1, 2, 0, 0, 0, 1, 2, –3, –1, 0, 0, 0, –1, 2, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, –1, 0, –1, 0 Blocare după conversie inversă: 3888, 0, –176, –144, –432, 0, 912, 544, 416, 936, 896, 168, –464, 0, 0, 0, 256, 672, –720, 864, 352, –504, 0, –496, 256, 0, –960, 0,–1368, 776, 0, –552, –320, 192, –328, 992, 0, 0, 0, 680, 432, –936, –488, 0, 0, 0,–1000, 1632, 0, 0, 0, 0, 912, 0, 0, 896, 640, 816, 0, 0, –992, 0, –912, 0 După cum se vede, în primul caz schimbarea DC coeficientul ca urmare a compresiei este 2, iar în al doilea 26, în timp ce este cuantificat DC coeficientul în al doilea caz este de 6 ori mai mic decât în primul. Codarea este etapa finală a compresiei; în timpul acesteia, blocurile de imagine sunt convertite în formă vectorială conform regulii specificate de blocurile de forma: 0, 1, 5, 6, 14, 15, 27, 28, 2, 4, 7, 13, 16, 26, 29, 42, 3, 8, 12, 17, 25, 30, 41, 43, 9, 11, 18, 24, 31, 40, 44, 53, 10, 19, 23, 32, 39, 45, 52, 54, 20, 22, 33, 38, 46, 51, 55, 60, 21, 34, 37, 47, 50, 56, 59, 61, 35, 36, 48, 49, 57, 58, 62, 63 unde indicii vectoriali ai componentelor matricei corespunzătoare sunt indicați ca elemente de bloc. În acest caz, elementul zero este codificat ca diferență cu elementul zero al blocului anterior. Zero elemente indică DC, ele conțin componenta constantă a blocului (toate celelalte elemente AC sunt de obicei notate A.C.). Datele rezultate sunt apoi comprimate folosind codificarea aritmetică sau o modificare a algoritmului Huffman. Această etapă nu prezintă un mare interes din punctul de vedere al steganografiei în imaginile grafice, deci depășește sfera examinării noastre.
Ați înțeles corect din titlu că aceasta nu este o descriere foarte obișnuită a algoritmului JPEG (am descris formatul fișierului în detaliu în articolul „Decodare JPEG pentru nenorociri”). În primul rând, metoda aleasă de prezentare a materialului presupune că nu știm nimic nu numai despre JPEG, ci și despre transformata Fourier și codarea Huffman. În general, ne amintim puțin din prelegeri. Tocmai au făcut poza și au început să se gândească la cum ar putea fi comprimată. Prin urmare, am încercat să exprim clar doar esența, dar în care cititorul va dezvolta o înțelegere destul de profundă și, cel mai important, intuitivă a algoritmului. Formule și calcule matematice - cel puțin, doar cele care sunt importante pentru înțelegerea a ceea ce se întâmplă.
Indiferent de algoritmul de compresie a informațiilor, principiul său va fi întotdeauna același - găsirea și descrierea modelelor. Cu cât mai multe modele, cu atât mai multă redundanță, cu atât mai puține informații. Arhivatorii și codificatorii sunt de obicei „adaptați” unui anumit tip de informații și știu unde să le găsească. În unele cazuri, un model este imediat vizibil, cum ar fi o imagine a unui cer albastru. Fiecare rând al reprezentării sale digitale poate fi descris destul de precis printr-o linie dreaptă.Reprezentare vectorială
Mai întâi, să verificăm cât de dependenți sunt doi pixeli vecini. Este logic să presupunem că cel mai probabil vor fi foarte asemănătoare. Să verificăm acest lucru pentru toate perechile de imagini. Să le marchem pe planul de coordonate cu puncte, astfel încât valoarea punctului de-a lungul axei X să fie valoarea primului pixel, iar de-a lungul axei Y - al doilea. Pentru imaginea noastră care măsoară 256 x 256, obținem 256*256/2 pixeli: 
În mod previzibil, majoritatea punctelor sunt situate pe sau în apropierea liniei y=x (și sunt chiar mai multe decât se poate vedea în figură, deoarece se suprapun de multe ori și, în plus, sunt translucide). Dacă da, ar fi mai ușor să lucrați rotindu-le cu 45°. Pentru a face acest lucru, trebuie să le exprimați într-un sistem de coordonate diferit. 
Vectorii de bază ai noului sistem sunt evident: . Suntem forțați să împărțim la rădăcina a doi pentru a obține un sistem ortonormal (lungimile vectorilor de bază sunt egale cu unu). Se arată aici că un anumit punct p = (x, y) în noul sistem va fi reprezentat ca un punct (a 0 , a 1). Cunoscând noii coeficienți, îi putem obține cu ușurință pe cei vechi, întorcându-i. În mod evident, prima (nouă) coordonată este media, iar a doua este diferența dintre x și y (dar împărțită la rădăcina 2). Imaginați-vă că vi se cere să lăsați doar una dintre valori: fie 0, fie 1 (adică echivalați cealaltă cu zero). Este mai bine să alegeți un 0, deoarece valoarea unui 1 va fi cel mai probabil în jurul valorii de zero. Iată ce se întâmplă dacă restaurăm imaginea doar de la 0: 
mărire 4x: 
Această compresie nu este foarte impresionantă, să fiu sincer. Este mai bine să împărțiți în mod similar imaginea în tripleți de pixeli și să le prezentați în spațiu tridimensional. 
Acesta este același grafic, dar din puncte de vedere diferite. Liniile roșii sunt axele care s-au sugerat. Ele corespund vectorilor: . Permiteți-mi să vă reamintesc că trebuie să împărțiți la niște constante, astfel încât lungimile vectorilor să devină egale cu unu. Astfel, extinzându-ne pe această bază, obținem 3 valori a 0, a 1, a 2, iar un 0 este mai important decât un 1, iar un 1 este mai important decât un 2. Dacă aruncăm un 2, atunci graficul se va „aplatiza” în direcția vectorului e 2. Această foaie tridimensională deja destul de subțire va deveni plată. Nu va pierde atât de mult, dar vom scăpa de o treime din valori. Să comparăm imagini reconstruite din triple: (a 0 , 0, 0), (a 1 , a 2 , 0) și (a 0 , a 1 , a 2). În ultima versiune nu am aruncat nimic, așa că vom obține originalul. 
mărire 4x: 
Al doilea desen este deja bun. Zonele ascuțite au fost ușor netezite, dar în general imaginea s-a păstrat foarte bine. Și acum, să împărțim la patru în același mod și să determinăm vizual baza în spațiul cu patru dimensiuni... Ei bine, da. Dar puteți ghici care va fi unul dintre vectorii de bază: (1,1,1,1)/2. Prin urmare, se poate privi proiecția spațiului cu patru dimensiuni pe spațiul perpendicular pe vectorul (1,1,1,1) pentru a identifica altele. Dar acesta nu este cel mai bun mod.
Scopul nostru este să învățăm cum să transformăm (x 0 , x 1 , ..., x n-1) în (a 0 , a 1 , ..., a n-1) astfel încât fiecare valoare a lui a i să fie mai puțin importantă decât cele precedente. Dacă putem face acest lucru, atunci poate că ultimele valori ale secvenței pot fi aruncate cu totul. Experimentele de mai sus sugerează că este posibil. Dar nu te poți descurca fără un aparat matematic.
Deci, trebuie să transformăm punctele la o nouă bază. Dar mai întâi trebuie să găsiți o bază potrivită. Să revenim la primul experiment de împerechere. Să o luăm în considerare în general. Am definit vectorii de bază: 
Am exprimat vectorul prin ele p:
sau in coordonate: 
Pentru a găsi un 0 și un 1 trebuie să proiectați p pe e 0 și e 1 respectiv. Și pentru aceasta trebuie să găsiți produsul scalar
similar:
În coordonate: 
Este adesea mai convenabil să se efectueze transformarea sub formă de matrice. 
Apoi A = EX și X = E T A. Aceasta este o formă frumoasă și convenabilă. Matricea E se numește matrice de transformare și este ortogonală, ne vom întâlni cu ea mai târziu. Tranziția de la vectori la funcții.
Este convenabil să lucrați cu vectori de dimensiuni mici. Cu toate acestea, dorim să găsim modele în blocuri mai mari, astfel încât în loc de vectori N-dimensionali este mai convenabil să operați cu secvențele care reprezintă imaginea. Voi numi astfel de secvențe funcții discrete, deoarece următorul raționament se aplică și funcțiilor continue.
Revenind la exemplul nostru, imaginați-vă o funcție f(i), care este definită în doar două puncte: f(0)=x și f(1)=y. În mod similar, definim funcțiile de bază e 0 (i) și e 1 (i) pe baza bazelor e 0 și e 1 . Primim: 
Aceasta este o concluzie foarte importantă. Acum, în expresia „extinderea unui vector în vectori ortonormali” putem înlocui cuvântul „vector” cu „funcție” și obținem expresia complet corectă „extinderea unei funcții în funcții ortonormale”. Nu contează că avem o funcție atât de scurtă, deoarece același raționament funcționează pentru un vector N-dimensional, care poate fi reprezentat ca o funcție discretă cu N valori. Și lucrul cu funcții este mai clar decât cu vectori N-dimensionali. În schimb, puteți reprezenta o astfel de funcție ca un vector. Mai mult, o funcție continuă obișnuită poate fi reprezentată printr-un vector infinit-dimensional, deși nu în spațiul euclidian, ci în spațiul Hilbert. Dar nu vom merge acolo; ne vor interesa doar funcțiile discrete.
Iar problema noastră de a găsi o bază se transformă în problema de a găsi un sistem adecvat de funcții ortonormale. În raționamentul următor, se presupune că am determinat deja cumva un set de funcții de bază, în funcție de care vom descompune.
Să presupunem că avem o funcție (reprezentată, de exemplu, prin valori) pe care vrem să o reprezentăm ca sumă a altora. Puteți reprezenta acest proces în formă vectorială. Pentru a descompune o funcție, trebuie să o „proiectați” pe funcțiile de bază una câte una. În sens vectorial, calcularea proiecției oferă o apropiere minimă a vectorului inițial de altul în ceea ce privește distanța. Reținând că distanța este calculată folosind teorema lui Pitagora, o reprezentare similară sub formă de funcții oferă cea mai bună aproximare pătratică medie a unei funcții față de alta. Astfel, fiecare coeficient (k) determină „apropierea” funcției. Mai formal, k*e(x) este cea mai bună aproximare pătratică medie a f(x) dintre l*e(x).
Următorul exemplu arată procesul de aproximare a unei funcții folosind doar două puncte. În dreapta este o reprezentare vectorială. 
În legătură cu experimentul nostru de împărțire în perechi, putem spune că aceste două puncte (0 și 1 de-a lungul abscisei) sunt o pereche de pixeli vecini (x, y).
Același lucru, dar cu animație: 
Dacă luăm 3 puncte, atunci trebuie să luăm în considerare vectorii tridimensionali, dar aproximarea va fi mai precisă. Și pentru o funcție discretă cu N valori, trebuie să luați în considerare vectorii N-dimensionali.
Având un set de coeficienți obținuți, puteți obține cu ușurință funcția originală prin însumarea funcțiilor de bază luate cu coeficienții corespunzători. Analiza acestor coeficienți poate oferi o mulțime de informații utile (în funcție de bază). Un caz special al acestor considerații este principiul expansiunii seriei Fourier. La urma urmei, raționamentul nostru este aplicabil oricărei baze, iar atunci când ne extindem într-o serie Fourier, este luată una complet specifică. Transformate Fourier discrete (DFT)
În partea anterioară, am ajuns la concluzia că ar fi bine să descompunem o funcție în componentele sale. La începutul secolului al XIX-lea, Fourier s-a gândit și el la acest lucru. Adevărat, nu avea o imagine a unui raton, așa că a trebuit să studieze distribuția căldurii de-a lungul inelului metalic. Apoi a aflat că este foarte convenabil să exprime temperatura (și modificarea acesteia) în fiecare punct al inelului ca o sumă de sinusoide cu perioade diferite. „Fourier a descoperit (recomand să citești, este interesant) că a doua armonică se dezintegra de 4 ori mai repede decât prima, iar armonicile de ordin superior se diminuează cu o viteză și mai rapidă.”
În general, s-a dovedit curând că funcțiile periodice pot fi descompuse perfect în suma sinusoidelor. Și deoarece în natură există multe obiecte și procese descrise de funcții periodice, a apărut un instrument puternic pentru analiza lor.
Poate că unul dintre cele mai vizuale procese periodice este sunetul. 
Dacă mi-ar fi dat valorile ultimei funcții în acel moment în care nu știam despre seria Fourier și mi-ar fi cerut să le analizez, atunci cu siguranță aș fi fost confuz și nu aș fi putut spune nimic util. Ei bine, da, un fel de funcție, dar de unde înțelegeți că există ceva ordonat acolo? Dar dacă aș fi ghicit să ascult ultima funcție, urechea mea ar fi prins un ton pur printre zgomot. Deși nu foarte bine, deoarece în timpul generării am selectat special astfel de parametri, astfel încât pe graficul rezumat semnalul să se dizolve vizual în zgomot. După cum am înțeles, încă nu este clar cum face acest lucru un aparat auditiv. Cu toate acestea, recent a devenit clar că nu descompune sunetul în unde sinusoidale. Poate că într-o zi vom înțelege cum se întâmplă acest lucru și vor apărea algoritmi mai avansați. Ei bine, deocamdată o facem la modă veche.
De ce să nu încerci să folosești sinusoide ca bază? De fapt, am făcut deja asta. Să ne amintim descompunerea noastră în 3 vectori de bază și să-i prezentăm pe grafic: 
Da, da, știu, pare o ajustare, dar cu trei vectori este greu de așteptat la mai mult. Dar acum este clar cum să obțineți, de exemplu, 8 vectori de bază: 
O verificare nu foarte complicată arată că acești vectori sunt perpendiculari în perechi, adică ortogonali. Aceasta înseamnă că pot fi folosite ca bază. Transformarea pe o astfel de bază este cunoscută pe scară largă și se numește transformată cosinus discretă (DCT). Cred că din graficele de mai sus este clar cum se obține formula de transformare DCT:
Aceasta este încă aceeași formulă: A = EX cu o bază substituită. Vectorii de bază ai DCT specificat (sunt, de asemenea, vectori rând ai matricei E) sunt ortogonali, dar nu ortonormali. Acest lucru ar trebui reținut în timpul transformării inverse (nu mă voi opri asupra acestui lucru, dar pentru cei interesați, DCT inversă are un termen 0,5*a 0 , deoarece vectorul de bază zero este mai mare decât celelalte).
Următorul exemplu arată procesul de aproximare a subtotalurilor la valorile originale. La fiecare iterație, următoarea bază este înmulțită cu următorul coeficient și adăugată la suma intermediară (adică la fel ca în experimentele timpurii pe raton - o treime din valori, două treimi). 
Dar, cu toate acestea, în ciuda unor argumente despre oportunitatea alegerii unei astfel de baze, nu există încă argumente reale. Într-adevăr, spre deosebire de sunet, fezabilitatea descompunerii unei imagini în funcții periodice este mult mai puțin evidentă. Cu toate acestea, imaginea poate fi într-adevăr prea imprevizibilă chiar și într-o zonă mică. Prin urmare, imaginea este împărțită în bucăți suficient de mici, dar nu absolut mici, pentru ca descompunerea să aibă sens. În JPEG, imaginea este „tăiată” în pătrate de 8x8. În cadrul unei astfel de piese, fotografiile sunt de obicei foarte uniforme: fundalul plus mici fluctuații. Astfel de zone sunt frumos abordate de sinusoide.
Ei bine, să spunem că acest fapt este mai mult sau mai puțin intuitiv. Dar există un sentiment rău despre tranzițiile bruște de culoare, deoarece funcțiile care se schimbă încet nu ne vor salva. Trebuie să adăugăm diverse funcții de înaltă frecvență care își fac treaba, dar apar lateral pe un fundal omogen. Să luăm o imagine de 256x256 cu două zone contrastante: 
Să descompunăm fiecare rând folosind DCT, obținând astfel 256 de coeficienți pe rând.
Apoi lăsăm doar primii n coeficienți și setăm restul la zero și, prin urmare, imaginea va fi prezentată ca o sumă a primelor armonice: 
Numărul din imagine este numărul de cote rămase. În prima imagine rămâne doar valoarea medie. Pe cel de-al doilea, a fost deja adăugat un sinusoid de joasă frecvență etc. Apropo, acordați atenție marginii - în ciuda tuturor celor mai bune aproximări, 2 dungi sunt vizibile clar lângă diagonală, una mai deschisă, cealaltă mai întunecată. O parte din ultima imagine a fost mărită de 4 ori:
Și, în general, dacă departe de graniță vedem un fundal uniform inițial, atunci când ne apropiem de el, amplitudinea începe să crească, atinge în cele din urmă o valoare minimă și apoi devine brusc maximă. Acest fenomen este cunoscut sub numele de efectul Gibbs. 
Înălțimea acestor cocoașe, care apar în apropierea discontinuităților funcției, nu va scădea pe măsură ce crește numărul de sume ale funcțiilor. Într-o transformare discretă dispare doar atunci când aproape toți coeficienții sunt păstrați. Mai exact, devine invizibil.
Următorul exemplu este complet similar cu descompunerea triunghiurilor de mai sus, dar pe un raton real: 
Când studiem DCT, se poate avea impresia falsă că doar primii câțiva coeficienți (frecvență joasă) sunt întotdeauna suficienti. Acest lucru este valabil pentru multe bucăți de fotografii, cele ale căror semnificații nu se schimbă dramatic. Cu toate acestea, la granița zonelor contrastante, valorile vor „sări” rapid și chiar ultimii coeficienți vor fi mari. Prin urmare, atunci când auziți despre proprietatea de conservare a energiei a DCT, luați în considerare faptul că se aplică multor tipuri de semnale întâlnite, dar nu tuturor. De exemplu, gândiți-vă la cum ar arăta o funcție discretă, ai cărei coeficienți de expansiune sunt egali cu zero, cu excepția ultimei. Sugestie: Gândiți-vă la descompunerea sub formă vectorială.
În ciuda deficiențelor, baza aleasă este una dintre cele mai bune din fotografiile reale. Vom vedea o mică comparație cu altele puțin mai târziu. DCT vs orice altceva
Când am studiat problema transformărilor ortogonale, să fiu sinceră, nu am fost foarte convins de argumentele că totul în jur este suma oscilațiilor armonice, așa că este necesar să descompun imaginile în sinusoide. Sau poate ar fi mai bune unele funcții pas? Prin urmare, am căutat rezultatele cercetării privind optimitatea DCT pe imagini reale. Faptul că „DCT este cel mai des întâlnit în aplicațiile practice datorită proprietății „compacției energetice”” este scris peste tot. Această proprietate înseamnă că cantitatea maximă de informații este conținută în primii coeficienți. Și de ce? Nu este dificil să facem cercetări: ne înarmam cu o grămadă de imagini diferite, baze cunoscute diferite și începem să calculăm abaterea standard de la imaginea reală pentru un număr diferit de coeficienți. Am gasit un mic studiu intr-un articol (imagini folosite) despre aceasta tehnica. Prezintă grafice ale dependenței energiei stocate de numărul de primii coeficienți de expansiune pentru diferite baze. Dacă te uitai la topuri, erai convins că DCT ocupă în mod constant un onorabil... um... locul 3. Cum așa? Ce fel de conversie KLT este aceasta? Lăudam DCT și apoi... KLT
Toate transformările, cu excepția KLT, sunt transformări cu o bază constantă. Și în KLT (transformata Karhunen-Loeve) se calculează cea mai optimă bază pentru mai mulți vectori. Se calculează în așa fel încât primii coeficienți să dea cea mai mică eroare pătratică medie în total pentru toți vectorii. Am efectuat anterior lucrări similare manual, determinând vizual baza. La început pare o idee bună. Am putea, de exemplu, să împărțim imaginea în secțiuni mici și să calculăm propria bază pentru fiecare. Dar nu numai că există preocuparea de a stoca această bază, ci și operațiunea de calculare a acesteia este destul de intensivă în muncă. Dar DCT pierde doar puțin și, în plus, DCT are algoritmi de conversie rapidă. DFT
DFT (Discrete Fourier Transform) - transformată Fourier discretă. Sub acest nume, nu se face referire uneori doar la o anumită transformare, ci și la întreaga clasă de transformări discrete (DCT, DST...). Să ne uităm la formula DFT: 
După cum ați putea ghici, aceasta este o transformare ortogonală cu un fel de bază complexă. Deoarece o formă atât de complexă apare puțin mai des decât de obicei, este logic să studiem derivarea ei.
Poate părea că orice semnal armonic pur (cu o frecvență întreagă) cu descompunere DCT va da un singur coeficient diferit de zero corespunzător acestei armonice. Acest lucru nu este adevărat, deoarece, pe lângă frecvență, este importantă și faza acestui semnal. De exemplu, extinderea sinusului în cosinus (în mod similar în expansiunea discretă) va fi astfel:
Atât despre armonici pure. Ea a născut o grămadă de alții. Animația arată coeficienții DCT ai unei unde sinusoidale în diferite faze. 
Dacă ți s-a părut că coloanele se rotesc în jurul unei axe, atunci nu ți s-a părut.
Aceasta înseamnă că acum vom extinde funcția în suma de sinusoide nu doar de frecvențe diferite, ci și de cele deplasate de-a lungul unei faze. Va fi mai convenabil să luați în considerare defazajul folosind exemplul cosinus:
O identitate trigonometrică simplă dă un rezultat important: defazajul este înlocuit cu suma sinusului și cosinusului, luate cu coeficienții cos(b) și sin(b). Aceasta înseamnă că funcțiile pot fi extinse în suma sinusurilor și cosinusurilor (fără faze). Aceasta este o formă trigonometrică comună. Cu toate acestea, complexul este folosit mult mai des. Pentru a-l obține trebuie să utilizați formula lui Euler. Pur și simplu înlocuind formulele derivate pentru sinus și cosinus, obținem: 
Acum pentru o mică schimbare. Sublinierea este numărul conjugat.
Obținem egalitatea finală:
c este un coeficient complex, a cărui parte reală este egală cu coeficientul cosinus, iar partea imaginară este egală cu coeficientul sinus. Și mulțimea de puncte (cos(b), sin(b)) este un cerc. Într-o astfel de înregistrare, fiecare armonică intră în expansiune atât cu o frecvență pozitivă, cât și cu una negativă. Prin urmare, în diferite formule de analiză Fourier, însumarea sau integrarea are loc de obicei de la minus la plus infinit. Este adesea mai convenabil să efectuați calcule în această formă complexă.
Transformarea descompune semnalul în armonici cu frecvențe de la unu la N oscilații în regiunea semnalului. Dar rata de eșantionare este N pe zonă de semnal. Și conform teoremei Kotelnikov (alias teorema Nyquist-Shannon), frecvența de eșantionare trebuie să fie de cel puțin două ori frecvența semnalului. Dacă nu este cazul, atunci efectul este apariția unui semnal cu o frecvență falsă: 
Linia punctată arată semnalul reconstruit incorect. Te-ai confruntat adesea cu acest fenomen în viață. De exemplu, mișcarea amuzantă a roților mașinii într-un videoclip sau efectul moire.
Acest lucru duce la faptul că a doua jumătate a amplitudinilor complexului N pare să fie formată din alte frecvențe. Aceste armonice false din a doua jumătate sunt o imagine în oglindă a primei și nu poartă informații suplimentare. Astfel, rămânem cu N/2 cosinus și N/2 sinusuri (formând o bază ortogonală).
Bine, există o bază. Componentele sale sunt armonici cu un număr întreg de oscilații în regiunea semnalului, ceea ce înseamnă că valorile extreme ale armonicilor sunt egale. Mai precis, ele sunt aproape egale, deoarece ultima valoare nu este luată în întregime de la margine. Mai mult, fiecare armonică este aproape simetrică în oglindă față de centrul său. Toate aceste fenomene sunt deosebit de puternice la frecvențe joase, care sunt importante pentru noi atunci când codificăm. Acest lucru este, de asemenea, rău, deoarece limitele blocurilor vor fi vizibile în imaginea comprimată. Permiteți-mi să ilustrez baza DFT cu N=8. Primele 2 rânduri sunt componente cosinus, ultimele sunt sinus: 
Acordați atenție aspectului componentelor duplicate pe măsură ce frecvența crește. 
Lucrurile sunt extrem de proaste cu primul.
Deci, poate o putem face ca în DCT - reduceți frecvențele de 2 sau de un alt număr de ori, astfel încât numărul unor oscilații să fie fracționat și limitele să fie în faze diferite? Atunci componentele vor fi non-ortogonale. Și nu e nimic de făcut în privința asta.Ora de oră
Ce se întâmplă dacă folosim sinusuri în loc de cosinus în DCT? Vom obține Transformarea Sinusoială Discretă (DST). Dar pentru sarcina noastră, toate sunt neinteresante, deoarece ambele perioade întregi și jumătate ale sinusurilor sunt aproape de zero la granițe. Adică vom obține aproximativ aceeași descompunere inadecvată ca cea a DFT. Revenind la DCT
Ce mai face la granițe? Amenda. Există antifaze și nu zerouri. Toate celelalte
Transformări non-Fourier. Nu o voi descrie.
WHT - matricea constă numai din componente de pas cu valorile -1 și 1.
Haar este, de asemenea, o transformare wavelet ortogonală.
Sunt inferioare DCT, dar sunt mai ușor de calculat.
Nu va fi ușor, nu? Cu toate acestea, pentru unele tipuri de imagini este posibil să se selecteze o bază mai bună decât cea a DCT. Transformări 2D
Acum să încercăm să facem un astfel de experiment. Să luăm, de exemplu, o bucată dintr-o imagine. 
Graficul lui 3D: 
Să trecem prin DCT(N=32) prin fiecare linie: 
Acum vreau să-ți treci ochii prin fiecare coloană a coeficienților rezultați, adică de sus în jos. Amintiți-vă că scopul nostru este să lăsăm cât mai puține valori, eliminându-le pe cele care nu sunt semnificative. Probabil ați ghicit că valorile fiecărei coloane ale coeficienților rezultați pot fi extinse exact în același mod ca și valorile imaginii originale. Nimeni nu ne limitează în alegerea unei matrice de transformare ortogonală, dar o vom face din nou folosind DCT(N=8): 
Coeficientul (0,0) sa dovedit a fi prea mare, deci este redus de 4 ori în grafic.
Deci ce s-a întâmplat?
Colțul din stânga sus reprezintă cei mai semnificativi coeficienți de expansiune a celor mai semnificativi coeficienți.
Colțul din stânga jos este cei mai nesemnificativi coeficienți de expansiune a celor mai semnificativi coeficienți.
Colțul din dreapta sus este cei mai semnificativi coeficienți de expansiune a celor mai nesemnificativi coeficienți.
Colțul din dreapta jos este cei mai nesemnificativi coeficienți de expansiune a celor mai nesemnificativi coeficienți.
Este clar că semnificația coeficienților scade dacă te deplasezi în diagonală din stânga sus la dreapta jos. Care este mai important: (0, 7) sau (7, 0)? Ce înseamnă ele?
Mai întâi, pe rânduri: A 0 = (EX T) T = XE T (transpus, întrucât formula este A=EX pentru coloane), apoi pe coloane: A=EA 0 = EXE T . Dacă calculezi cu atenție, obții formula:
Astfel, dacă un vector este descompus în sinusoide, atunci matricea este descompusă în funcții de forma cos(ax)*cos(by). Fiecare bloc 8x8 din JPEG este reprezentat ca o sumă a 64 de funcții de forma: 
În Wikipedia și în alte surse, astfel de funcții sunt prezentate într-o formă mai convenabilă: 
Prin urmare, coeficienții (0, 7) sau (7, 0) sunt la fel de utili.
Cu toate acestea, de fapt, aceasta este o descompunere unidimensională obișnuită în 64 de baze cu 64 de dimensiuni. Toate cele de mai sus se aplică nu numai pentru DCT, ci și pentru orice descompunere ortogonală. Procedând prin analogie, în cazul general obținem o transformare ortogonală N-dimensională.
Și iată o transformare 2D a unui raton (DCT 256x256). Din nou, cu valorile resetate la zero. Numere - numărul de coeficienți nezeroiți din toate (s-au reținut cele mai semnificative valori, situate în zona triunghiulară din colțul din stânga sus). 
Amintiți-vă că coeficientul (0, 0) se numește DC, restul de 63 se numește AC. Alegerea unei dimensiuni de bloc
Un prieten întreabă de ce JPEG folosește partiționarea 8x8. Din răspunsul votat negativ: DCT tratează blocul ca și cum ar fi periodic și trebuie să reconstruiască saltul rezultat la granițe. Dacă luați blocuri de 64x64, cel mai probabil veți avea un salt uriaș la granițe și veți avea nevoie de o mulțime de componente de înaltă frecvență pentru a le reconstrui cu o precizie satisfăcătoare.
De exemplu, DCT funcționează bine doar pe funcțiile periodice și, dacă mergeți mare, probabil veți obține un salt uriaș la granițele blocurilor și veți avea nevoie de o mulțime de componente de înaltă frecvență pentru a-l acoperi. Nu este adevarat! Această explicație este foarte asemănătoare cu DFT, dar nu și cu DCT, deoarece acoperă perfect astfel de salturi cu primele componente.
Pe aceeași pagină este un răspuns de la MPEG FAQ, cu principalele argumente împotriva blocurilor mari:
Îți sugerez să cercetezi asta singur. Sa incepem cu primul.
Axa orizontală arată ponderea primilor coeficienți nezeroiți. Verticală - abaterea standard a pixelilor față de original. Abaterea maximă posibilă este luată ca una. Desigur, o imagine nu este suficientă pentru un verdict. În plus, nu acționez în întregime corect, pur și simplu resetând la zero. Într-un JPEG real, în funcție de matricea de cuantizare, doar valorile mici ale componentelor de înaltă frecvență sunt zero. Prin urmare, următoarele experimente și concluzii sunt menite să scoată la suprafață principiile și modelele.
Puteți compara împărțirea în blocuri diferite cu 25% din coeficienți la stânga (de la stânga la dreapta, apoi de la dreapta la stânga): 
Aceasta înseamnă că, de exemplu, calculul pentru o partiție 64x64 este de două ori mai complex decât o partiție 8x8. 
Deși distorsiunea blocurilor 16x16 se extinde mai mult decât cea a 8x8, inscripția este mai netedă. Prin urmare, doar primele două argumente m-au convins. Dar cumva îmi place mai mult divizia 16x16.Cuantizarea
În acest moment avem o grămadă de matrice 8x8 cu coeficienți de transformare cosinus. Este timpul să scăpăm de coeficienți nesemnificativi. Există o soluție mai elegantă decât simpla resetare a ultimilor coeficienți la zero, așa cum am făcut mai sus. Nu suntem mulțumiți de această metodă, deoarece valorile fără zero sunt stocate cu o precizie excesivă, iar printre cei care au avut ghinion ar putea fi și unele destul de importante. Soluția este utilizarea unei matrice de cuantizare. Pierderile apar tocmai în această etapă. Fiecare coeficient Fourier este împărțit la numărul corespunzător din matricea de cuantizare. Să ne uităm la un exemplu. Să luăm primul bloc de la ratonul nostru și să realizăm cuantizarea. Specificația JPEG oferă o matrice standard: 
Matricea standard corespunde unei calități de 50% în FastStone și IrfanView. Acest tabel a fost ales din punct de vedere al echilibrului între calitate și raportul de compresie. Cred că valoarea coeficientului DC este mai mare decât vecinii săi datorită faptului că DCT nu este normalizat și prima valoare este mai mare decât ar trebui. Coeficienții de înaltă frecvență sunt amplificați mai puternic datorită importanței lor mai mici. Cred că astfel de matrici sunt rar folosite acum, deoarece deteriorarea calității este clar vizibilă. Nimeni nu interzice utilizarea tabelului dvs. (cu valori de la 1 la 255)
În timpul decodării, are loc procesul invers - coeficienții cuantificați sunt înmulțiți termen cu termen cu valorile matricei de cuantizare. Dar, din moment ce am rotunjit valorile, nu vom putea restabili cu acuratețe coeficienții Fourier originali. Cu cât numărul de cuantizare este mai mare, cu atât eroarea este mai mare. Astfel, coeficientul reconstruit este doar cel mai apropiat multiplu.
Alt exemplu: 
Când restabilim acest bloc, vom obține doar valoarea medie plus gradientul vertical (datorită valorii păstrate de -1). Dar doar două valori sunt stocate pentru acesta: 7 și -1. Situația nu este mai bună cu alte blocuri, iată imaginea restaurată: 
Sau puteți privi matricele de cuantizare ale diferitelor camere.Codificare
Înainte de a trece mai departe, trebuie să folosim exemple mai simple pentru a înțelege cum putem comprima valorile rezultate.
Imaginează-ți o astfel de situație în care prietenul tău a uitat o foaie de hârtie cu o listă la tine acasă și acum îți cere să o dictezi la telefon (nu există alte metode de comunicare).
Listă:
Cum ți-ai face sarcina mai ușoară? Nu aveți nicio dorință specială să dictați dureros toate aceste cuvinte. Dar sunt doar două și se repetă. Prin urmare, pur și simplu dictați cumva primele două cuvinte și sunteți de acord că de acum înainte veți numi „d9rg3” primul cuvânt și „wfr43gt” al doilea. Atunci va fi suficient să dictați: 1, 2, 2, 1, 1, 1, 2, 1. 
Codificați ABC.
Este imposibil să asociezi 3 caractere diferite (A, B, C) cu 2 valori posibile de biți (0 și 1). Și dacă da, atunci puteți folosi 2 biți per simbol. De exemplu:
Secvența de biți asociată unui simbol va fi numită cod. ABC va fi codificat astfel: 000110. 
Codificați AAAAAABC.
Utilizarea a 2 biți pe caracterul A pare puțin irosită. Ce se întâmplă dacă încerci asta:
Secvență codificată: 000000100.
Evident, această opțiune nu este potrivită, deoarece nu este clar cum să decodați primii doi biți ai acestei secvențe: ca AA sau ca C? Este foarte risipitor să folosim orice separator între coduri, ne vom gândi cum să ocolim acest obstacol într-un mod diferit. Deci, eșecul se datorează faptului că codul lui C începe cu codul lui A. Dar suntem hotărâți să codificăm A cu un bit, chiar dacă B și C au câte doi. Pe baza acestei dorințe, îi dăm lui A codul 0. Apoi codurile B și C nu pot începe cu 0. Dar pot începe cu 1: 
Secvența este codificată astfel: 0000001011. Încercați să o decodați mental. Poți face asta doar într-un singur fel.
Am dezvoltat două cerințe de codare:
Evident, ordinea personajelor nu este importantă, ne interesează doar frecvența apariției lor. Prin urmare, fiecare simbol este asociat cu un număr numit greutate. Greutatea unui simbol poate fi fie o valoare relativă, care reflectă proporția de apariție a acestuia, fie o valoare absolută, egală cu numărul de caractere. Principalul lucru este că ponderile sunt proporționale cu apariția simbolurilor.
Să luăm în considerare cazul general pentru 4 simboluri cu orice pondere.
Fără pierderea generalității, să punem pa ≥ pb ≥ pc ≥ pd. Există doar două opțiuni care diferă fundamental în lungimea codului: 
Care este de preferat? Pentru a face acest lucru, trebuie să calculați lungimile rezultate ale mesajelor codificate:
W1 = 2*pa + 2*pb + 2*buc + 2*pd
W2 = pa + 2*pb + 3*buc + 3*pd
Dacă W1 este mai mic decât W2 (W1-W2<0), то лучше использовать первый вариант:
W1-W2 = pa - (buc+pd)< 0 =>pa< pc+pd.
Dacă C și D apar împreună mai des decât altele, atunci vârful lor comun primește cel mai scurt cod de un bit. În caz contrar, un bit merge la caracterul A. Aceasta înseamnă că uniunea de caractere se comportă ca un caracter independent și are o pondere egală cu suma caracterelor introduse.
În general, dacă p este greutatea unui caracter reprezentată de fracția de apariție a acestuia (de la 0 la 1), atunci cea mai bună lungime a codului este s=-log 2 p.
Să luăm în considerare acest lucru într-un caz simplu (poate fi reprezentat cu ușurință ca un copac). Deci, trebuie să codificăm caractere de 2 s cu greutăți egale (1/2 s). Datorită egalității greutăților, lungimile codului vor fi aceleași. Fiecare personaj va necesita biți. Aceasta înseamnă că dacă greutatea unui simbol este 1/2 s, atunci lungimea acestuia este s. Dacă înlocuim greutatea cu p, obținem lungimea codului s=-log 2 p . Aceasta înseamnă că, dacă un caracter apare de două ori mai des decât altul, atunci lungimea codului său va fi cu un pic mai mare. Cu toate acestea, această concluzie este ușor de tras dacă vă amintiți că adăugarea unui bit vă permite să dublați numărul de opțiuni posibile.
Și încă o observație - cele două simboluri cu cele mai mici greutăți au întotdeauna lungimile de cod mai mari, dar egale. Mai mult, bițurile lor, cu excepția ultimului, sunt aceleași. Dacă acest lucru nu ar fi adevărat, atunci cel puțin un cod ar putea fi scurtat cu 1 bit fără a rupe prefixul. Aceasta înseamnă că cele două simboluri cu cele mai mici ponderi din arborele de cod au un părinte comun la un nivel superior. Puteți vedea acest lucru în exemplele C și D de mai sus.
Să încercăm să rezolvăm următorul exemplu, pe baza concluziilor obținute în exemplul anterior.
Pașii se repetă până când rămâne un singur grup. În cadrul fiecărui grup, unui caracter (sau subgrup) i se atribuie bitul 0 și un alt caracter bitul 1.
Acest algoritm se numește codare Huffman.
Ilustrația prezintă un exemplu cu 5 caractere (A: 8, B: 6, C: 5, D: 4, E: 3). În dreapta este greutatea simbolului (sau grupului). 
Codificăm coeficienții
Să ne întoarcem. Acum avem multe blocuri cu 64 de coeficienți în fiecare, care trebuie salvate cumva. Cea mai simplă soluție este utilizarea unui număr fix de biți pe coeficient - evident fără succes. Să construim o histogramă a tuturor valorilor obținute (adică, dependența numărului de coeficienți de valoarea lor): 
Vă rugăm să rețineți - scara este logaritmică! Puteți explica motivul apariției unui grup de valori care depășește 200? Aceștia sunt coeficienți DC. Deoarece sunt foarte diferite de celelalte, nu este de mirare că sunt codificate separat. Iată doar DC: 
Rețineți că forma graficului amintește de graficele din primele experimente de asociere și triplare a pixelilor.
În general, valorile coeficientului DC pot varia de la 0 la 2047 (mai precis de la -1024 la 1023, deoarece JPEG scade 128 din toate valorile originale, ceea ce corespunde cu scăderea 1024 din DC) și este distribuit destul de uniform cu vârfuri mici. Deci codarea Huffman nu va ajuta prea mult aici. Și imaginați-vă cât de mare va fi arborele de codare! Și în timpul decodării va trebui să cauți semnificații în ea. E foarte scump. Ne gândim mai departe.
Coeficientul DC este valoarea medie a unui bloc de 8x8. Să ne imaginăm o tranziție de gradient (deși nu ideală), care se găsește adesea în fotografii. Valorile DC în sine vor fi diferite, dar vor reprezenta o progresie aritmetică. Aceasta înseamnă că diferența lor va fi mai mult sau mai puțin constantă. Să construim o histogramă a diferențelor: 
Acest lucru este mai bine, deoarece valorile sunt în general concentrate în jurul zero (dar algoritmul Huffman va da din nou un copac prea mare). Valorile mici (în valoare absolută) sunt comune, valorile mari sunt rare. Și deoarece valorile mici ocupă câțiva biți (dacă sunt eliminate zerourile de început), una dintre regulile de compresie este bine respectată: simbolurilor cu greutăți mari li se atribuie coduri scurte (și invers). În prezent suntem limitați de nerespectarea unei alte reguli: imposibilitatea decodării fără ambiguitate. În general, această problemă poate fi rezolvată în următoarele moduri: deranjează codul delimitator, indica lungimea codului, folosește coduri de prefix (le știi deja - acesta este cazul când niciun cod nu începe cu altul). Să mergem cu a doua variantă simplă, adică fiecare coeficient (mai precis, diferența dintre cei vecini) se va scrie astfel: (lungime)(valoare), după acest semn: 
Adică, valorile pozitive sunt codificate direct prin reprezentarea lor binară, iar valorile negative sunt codificate în același mod, dar cu primul 1 înlocuit cu 0. Rămâne să decideți cum să codificați lungimile. Deoarece există 12 valori posibile, se pot folosi 4 biți pentru a stoca lungimea. Dar aici este mai bine să folosiți codarea Huffman. 
Există cele mai multe valori cu lungimile 4 și 6, așa că au primit cele mai scurte coduri (00 și 01).
Poate apărea întrebarea: de ce, în exemplu, valoarea 9 are codul 1111110 și nu 1111111? La urma urmei, poți ridica în siguranță „9” la un nivel superior, lângă „0”? Cert este că în JPEG nu poți folosi un cod format doar din unele - un astfel de cod este rezervat.
Mai există o caracteristică. Codurile obținute de algoritmul Huffman descris pot să nu coincidă în biți cu codurile în JPEG, deși lungimile lor vor fi aceleași. Folosind algoritmul Huffman, se obțin lungimile codurilor și se generează codurile în sine (algoritmul este simplu - începeți cu coduri scurte și adăugați-le unul câte unul în arbore cât mai la stânga posibil, păstrând proprietatea prefixului ). De exemplu, pentru arborele de deasupra lista este stocată: 0,2,3,1,1,1,1,1. Și, desigur, este stocată o listă de valori: 4,6,3,5,7,2,8,1,0,9. În timpul decodării, codurile sunt generate în același mod.
[Cod Huffman pentru lungimea diferențelor DC (în biți)]
unde DC diff = curent DC - DC anterior
Deoarece graficul este foarte asemănător cu graficul pentru diferențele DC, principiul este același: [Cod Huffman pentru lungimea AC (în biți)]. Dar nu chiar! Deoarece scara de pe grafic este logaritmică, nu se observă imediat că există de aproximativ 10 ori mai multe valori zero decât valorile 2, următoarea cea mai frecventă. Acest lucru este de înțeles - nu toată lumea a supraviețuit cuantizării. Să revenim la matricea valorilor obținute în timpul etapei de cuantizare (folosind matricea de cuantizare FastStone, 90%). 
Deoarece există multe grupuri de zerouri consecutive, apare o idee - să scrieți doar numărul de zerouri din grup. Acest algoritm de compresie se numește RLE (Run-length encoding). Rămâne să aflăm direcția de ocolire a celor „consecutivi” - cine este în spatele cui? Scrierea de la stânga la dreapta și de sus în jos nu este foarte eficientă, deoarece coeficienții non-zero sunt concentrați în colțul din stânga sus, iar cu cât mai aproape de dreapta jos, cu atât mai multe zerouri. 
Prin urmare, JPEG folosește o ordine numită „Zig-zag”, care este prezentată în figura din stânga. Această metodă distinge bine grupurile de zerouri. În imaginea din dreapta există o metodă alternativă de bypass, care nu are legătură cu JPEG, dar cu un nume (dovadă) curios. Poate fi folosit în MPEG pentru compresia video întrețesată. Alegerea algoritmului de traversare nu afectează calitatea imaginii, dar poate crește numărul de grupuri codificate de zerouri, ceea ce poate afecta în cele din urmă dimensiunea fișierului.
Să ne modificăm intrarea. Pentru fiecare coeficient AC diferit de zero:
[Numărul de zerouri înainte de AC][Cod Huffman pentru lungimea AC (în biți)]
Cred că vă puteți da seama imediat că și numărul de zerouri este perfect codificat de Huffman! Acesta este un răspuns foarte apropiat și bun. Dar se poate optimiza puțin. Imaginați-vă că avem un coeficient AC, înaintea căruia erau 7 zerouri (desigur, dacă sunt scrise în ordine în zig-zag). Aceste zerouri sunt spiritul valorilor care nu au supraviețuit cuantizării. Cel mai probabil, coeficientul nostru a fost și el grav deteriorat și a devenit mic, ceea ce înseamnă că lungimea lui este mică. Aceasta înseamnă că numărul de zerouri în fața AC și lungimea AC sunt mărimi dependente. Prin urmare, scriem astfel:
[Cod Huffman pentru (Numărul de zerouri înainte de AC, lungimea AC (în biți)]
Algoritmul de codificare rămâne același: acele perechi (număr de zerouri înainte de AC, lungimea AC) care apar frecvent vor primi coduri scurte și invers. 
„Creasta montană” lungă confirmă presupunerea noastră.
O astfel de pereche ocupă 1 octet: 4 biți pentru numărul de zerouri și 4 biți pentru lungimea AC. 4 biți sunt valori de la 0 la 15. Pentru lungimea AC acest lucru este mai mult decât suficient, dar pot fi mai mult de 15 zerouri? Apoi se folosesc mai multe perechi. De exemplu, pentru 20 de zerouri: (15, 0)(5, AC). Adică, al 16-lea zero este codificat ca un coeficient diferit de zero. Deoarece există întotdeauna o mulțime de zerouri aproape de sfârșitul blocului, perechea (0,0) este utilizată după ultimul coeficient diferit de zero. Dacă este întâlnit în timpul decodării, atunci valorile rămase sunt 0.
[Cod Huffman pentru lungimea diferențelor DC]
[Cod Huffman pentru (număr de zerouri înainte de AC 1, lungimea AC 1]
…
[Cod Huffman pentru (numărul de zerouri înainte de AC n, lungimea AC n]
Unde AC i sunt coeficienți AC diferiti de zero.Imagine color
Modul în care este prezentată o imagine color depinde de cea selectată model de culoare. O soluție simplă este să utilizați RGB și să codificați fiecare canal de culoare al imaginii separat. Atunci codarea nu va fi diferită de codificarea unei imagini gri, doar de 3 ori mai mult lucru. Dar compresia imaginii poate fi crescută dacă ne amintim că ochiul este mai sensibil la schimbările de luminozitate decât culorile. Aceasta înseamnă că culoarea poate fi stocată cu pierderi mai mari decât luminozitatea. RGB nu are un canal de luminozitate separat. Depinde de suma valorilor fiecărui canal. Prin urmare, cubul RGB (aceasta este o reprezentare a tuturor valorilor posibile) este pur și simplu „plasat” pe diagonală - cu cât mai sus, cu atât mai luminos. Dar nu se opresc aici - cubul este apăsat puțin din lateral și se dovedește mai mult ca un paralelipiped, dar acest lucru este doar pentru a ține cont de trăsăturile ochiului. De exemplu, este mai sensibil la verde decât la albastru. Așa a apărut modelul YCbCr. 
(Imagine de la Intel.com)
Y este componenta de luminanță, Cb și Cr sunt componentele diferențelor de culoare albastru și roșu. Prin urmare, dacă doresc să comprima mai mult imaginea, atunci RGB este convertit în YCbCr, iar canalele Cb și Cr sunt subțiate. Adică, ele sunt împărțite în blocuri mici, de exemplu 2x2, 4x2, 1x2, iar toate valorile unui bloc sunt mediate. Sau, cu alte cuvinte, reduc dimensiunea imaginii pentru acest canal de 2 sau 4 ori vertical și/sau orizontal. 
Fiecare bloc 8x8 este codificat (DCT + Huffman), iar secvențele codificate sunt scrise în această ordine:
Este curios că specificația JPEG nu limitează alegerea modelului, adică implementarea codificatorului poate împărți imaginea în componente de culoare (canale) în orice mod și fiecare va fi salvată separat. Sunt conștient de utilizarea în tonuri de gri (1 canal), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4). Primele trei sunt susținute de aproape toată lumea, dar sunt probleme cu ultimele cu 4 canale. FastStone, GIMP le suportă corect, iar programele standard Windows, paint.net extrag corect toate informațiile, dar apoi aruncă al 4-lea canal negru, prin urmare (Antelle a spus că nu-l aruncă, citește-i comentariile) arată o brichetă. imagine. În stânga este un JPEG clasic YCbCr, în dreapta este un JPEG CMYK: 
Dacă diferă în culoare, sau este vizibilă o singură imagine, atunci cel mai probabil aveți IE (orice versiune) (UPD. în comentarii spun „sau Safari”). Puteți încerca să deschideți articolul în diferite browsere. Și încă ceva
Pe scurt despre caracteristici suplimentare. Modul progresiv
Să descompunăm tabelele rezultate ale coeficienților DCT în suma tabelelor (aproximativ astfel (DC, -19, -22, 2, 1) = (DC, 0, 0, 0, 0) + (0, -20) , -20, 0, 0) + (0, 1, -2, 2, 1)). În primul rând, codificăm toți primii termeni (după cum am învățat deja: Huffman și traversarea în zigzag), apoi pe al doilea etc. Acest truc este util atunci când Internetul este lent, deoarece mai întâi se încarcă doar coeficienții DC, care sunt folosiți pentru construiți o imagine brută cu 8x8 „pixeli”. Apoi coeficienți AC rotunjiți pentru a rafina cifra. Apoi corecții brute la ele, apoi unele mai precise. Și așa mai departe. Coeficienții sunt rotunjiți, deoarece în etapele incipiente ale încărcării acuratețea nu este atât de importantă, dar rotunjirea are un efect pozitiv asupra lungimii codurilor, deoarece fiecare etapă folosește propriul tabel Huffman. Modul fără pierderi
Compresie fără pierderi. Fără DCT. Se folosește predicția punctului 4 pe baza a trei învecinate. Erorile de predicție sunt codificate Huffman. După părerea mea, este folosit puțin mai des decât niciodată. Modul ierarhic
Din imagine sunt create mai multe straturi cu rezoluții diferite. Primul strat grosier este codificat ca de obicei, iar apoi numai diferența (rafinamentul imaginii) dintre straturi (pretins a fi o wavelet Haar). Pentru codificare se utilizează DCT sau Lossless. După părerea mea, este folosit puțin mai rar decât niciodată. Codare aritmetică
Algoritmul Huffman produce coduri optime bazate pe greutatea caracterelor, dar acest lucru este valabil doar pentru o mapare fixă caracter-cod. Aritmetica nu are o legare atât de rigidă, care să permită utilizarea codurilor parcă cu un număr fracționar de biți. Pretinde că reduce dimensiunea fișierului cu o medie de 10% în comparație cu Huffman. Nu este răspândit din cauza problemelor legate de brevete, nu este susținut de toată lumea.
vanwin a sugerat să indice software-ul folosit. Sunt încântat să vă anunț că totul este disponibil și gratuit:
.
