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 de 512x512 pixeli, vor fi necesare operații 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 ale etapei de cuantificare, pierderile pot fi atât de mari încât imaginea se descompune în pătrate monocromatice de 8x8. La rândul lor, pierderile în frecvente inalte se pot manifesta în așa-numitul „efect Gibbs”, când se formează un „halo” ondulat în jurul contururilor cu o tranziție clară de culoare.
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 algoritmul RLE modificat, a cărui ieșire sunt perechi de tipul (sărire, număr), unde „sărire” este contorul de zerouri omise, iar „număr” este valoarea care trebuie pusă în următorul celulă. 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. Mai mult, se folosesc coduri diferite pentru coeficienții DC și AC, de ex. 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, 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. Îndeplinirea ultimei cerinţe făcute 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.
Deși algoritmul 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. Există, de asemenea, opțiuni JPEG pentru aplicații specifice.
Algoritmul JPEG a fost dezvoltat special pentru compresia imaginii de către Joint Photographic Expert Group (JPEG) și se bazează pe DCT.
DCT descompune o imagine într-un set de coeficienți, dintre care unii pot fi egali cu zero din cauza neutilizarii unor funcții DCT. Folosesc deja Acest lucru Se poate realiza o anumită compresie a datelor. Cu toate acestea, cel mai mare efect este obținut prin eliminarea unora dintre coeficienții nesemnificativi (echivalându-i cu zero).
De obicei, matricea externă are o caracteristică clar vizibilă. Valorile numerice ale elementelor matricei scad rapid din colțul din stânga sus în colțul din dreapta jos. Astfel, cele mai importante date sunt plasate în colțul din stânga sus, iar cele mai puțin importante sunt plasate în colțul din dreapta jos. Folosind acest fapt, puteți elimina datele cele mai puțin semnificative. Pentru a face acest lucru, datele convertite trebuie cuantificate.
Ideea din spatele cuantizării este că informațiile spectrale (de frecvență) trebuie să depășească un prag cunoscut pentru a constitui o parte importantă a informațiilor totale despre un anumit fragment de imagine. În etapa de cuantizare se pierde o anumită informație și, în consecință, se pierde calitatea.
Cuantificarea se face de obicei pe baza matrice specială, care conține divizori după care elementele DCP vor trebui împărțite. Următorul algoritm este adesea folosit:
Q(i,j) = 1 + ((1 + i + j) q);
Unde Q(i,j) este matricea divizorilor,
q - parametru de calitate.
Prin selectarea parametrului q, puteți controla valorile divizorului și puteți regla raportul de compresie. De exemplu, cu q = 2, obțineți o matrice de următoarea formă (Fig. 3.6):
Figura 3.6. Un exemplu de matrice de cuantizare.
După împărțirea celor 64 de elemente ale matricei la elementele matricei Q(i,j), rezultatul este o matrice a cărei:
Va apărea un număr mare de valori zero suplimentare,
Efectul de scădere a valorilor din stânga sus la dreapta jos va fi și mai pronunțat.
Pentru înregistrarea economică, este necesar să se schimbe ordinea de parcurgere a valorilor obținute, astfel încât secvențele de elemente zero să fie cât mai lungi posibil. Unul dintre moduri posibile schimbarea ordinii de parcurgere este metoda zig-zag (Fig. 3.7).
Figura 3.7. Conversia unei matrice bidimensionale într-o secvență unidimensională folosind metoda zigzagului.
După cum se poate observa din figură, o matrice bidimensională cu un format de 8 x 8 elemente este convertită într-o secvență unidimensională de 64 de elemente lungime. Proprietatea principală a unei astfel de secvențe va fi locația celor mai semnificativi coeficienți la început și a celor mai puțin elemente semnificative(de obicei zerouri) la sfârșit.
Implementarea algoritmului include rad actiuni consistente, care este ilustrat în Fig. 3.8.
Figura 3.8. Secvența de operații la implementarea algoritmului JPEG.
1. Imaginea, dacă este necesar, este convertită în format YUV.
2. Semnalele de diferență de culoare U și V sunt eșantionate în conformitate cu formatul 4:2:0. Împărțirea imaginii în fragmente de 8 x 8 elemente. Prelucrarea ulterioară a semnalelor de luminozitate și crominanță poate fi efectuată independent și în paralel.
3. Transformarea cosinus discretă este efectuată pe toate blocurile de 8 x 8 elemente.
4. Cuantificare în conformitate cu parametrul de calitate selectat.
5. Scanare în zig-zag pentru a obține o secvență unidimensională de 64 de elemente.
6. Algoritmul RLE se aplică unei secvențe unidimensionale.
7. Algoritmul Huffman este aplicat unei secvențe care a fost deja comprimată folosind RLE.
8. P.p. 3 – 7 se execută pentru toate blocurile cu format de 8 x 8 elemente și pentru toate planurile de culoare.
Caracteristici cheie Metoda JPEG sunt după cum urmează:
1. Raport de compresie ridicat, mai ales pentru imaginile a căror calitate este considerată bună sau excelentă.
2. Un număr mare de parametri care permit unui utilizator experimentat să experimenteze cu setările metodei și să atingă echilibrul compresie/calitate necesar.
3. Rezultate bune pentru toate tipurile de imagini cu ton continuu, indiferent de rezoluția, spațiul de culoare, dimensiunea pixelilor sau alte proprietăți.
4. O metodă de compresie destul de sofisticată, dar nu prea complicată, permițându-vă să creați dispozitive adecvate și să scrieți programe pentru a implementa metoda pentru calculatoare pe majoritatea platformelor, precum și în hardware.
5. Posibilitatea de a utiliza compresia fără pierderi de informații la un raport de compresie nu foarte mare.
Pentru a comprima eficient datele, trebuie mai întâi să evaluați natura imaginii dvs. JPEG comprimă datele grafice pe baza a ceea ce vede ochiul uman. Așadar, pentru a înțelege cum și ce face JPEG, aș dori să vă ofer ideea generala despre percepția vizuală umană.
Comprimarea JPEG are loc în mai multe etape. Scopul este de a transforma datele grafice, astfel încât informațiile vizuale irelevante să fie ușor identificate și aruncate. Această compresie „cu pierderi” diferă de majoritatea celorlalte abordări utilizate cu formatele grafice, care încearcă să păstreze intact fiecare fragment al imaginii.
Model de culoare
Primul pas în JPEG este alegerea unui mod adecvat de a reprezenta culorile. Culorile sunt de obicei specificate într-un sistem de coordonate tridimensional. Un sistem bine cunoscut de majoritatea programatorilor descrie culoarea ca o combinație de roșu, verde și albastru (RGB). Din păcate, din punct de vedere al compresiei, acest lucru nu este Cel mai bun mod descrieri de culori. Problema este că toate cele trei componente: roșu, verde și albastru sunt echivalente. Cu toate acestea, trecerea la un sistem diferit de redare a culorilor ne permite să evidențiem mai multe Informații importante.
Profesioniștii folosesc două modele de culoare: HSL (Hue-Saturation-Lightness) și HSV (Hue-Saturation-Value). Intuitiv, componenta Luminozitate a modelului HSL și Valoarea modelului HSV definesc fiecare raportul dintre lumină și umbră în felul lor. Saturația determină nivelul de culoare „pură”. Culorile nesaturate sunt adesea numite informal „murdare” (cenușii). Nuanța este ceea ce percepem ca culoarea unui obiect, cum ar fi roșu sau verde cenușiu. Este important de remarcat aici informatie uimitoare: Viziunea umană este mai sensibilă la schimbările de lumină, nu culoarea în sine!
Diferite implementări ale algoritmului de compresie JPEG folosesc diferite sisteme de culoare. Sistemul de redare a culorilor YCbCr utilizat de formatul JFIF este în multe privințe similar cu schema dezvoltată cu mulți ani în urmă pentru televiziunea color.
subțierea
Motivul principal pentru conversia unui model de culoare în altul este identificarea informațiilor care sunt mai puțin relevante pentru vizualizarea unei imagini. JPEG reduce cantitatea de informații despre culoare. În timp ce componenta luma este transmisă la rezoluție maximă, componentele de crominanță folosesc jumătate din intervalul de valori. Ca urmare un pas simplu volumul datelor este redus cu o treime.
Folosind subeșantionarea, culorile unei imagini TV color sunt ajustate. De obicei la televizor imagine alb-negruși informațiile de culoare sunt transmise separat. Mai mult, informațiile despre culoare sunt transmise într-o formă mai puțin strictă decât informațiile despre luminozitatea imaginii.
Transformarea Cosinus discretă (DCT)
Fiecare componentă de culoare este procesată separat, ca și cum nu ar fi o imagine color, ci trei imagini în tonuri de gri. Dacă priviți o imagine detaliată de la distanță, veți discerne doar tonul general al imaginii. De exemplu, „în mare parte albastru” sau „în mare parte roșu”. Cu cât te apropii de imagine, cu atât vei putea discerne mai multe detalii. Pentru a emula acest efect, JPEG folosește o tehnică matematică numită transformată cosinus discret (DCT). DCT convertește informațiile despre pixeli în informații despre schimbarea pixelilor. Primul lucru pe care DCT îl poate oferi este culoarea medie a zonei. Apoi elaborează din ce în ce mai multe detalii.
Ca si in cazul imagine de la distanță, valoarea medie a culorii reprezintă informații foarte importante despre zona imaginii. Ochiul tău este mai puțin sensibil la rata de schimbare a culorii, așa că nu este la fel de important. Conversia informațiilor de culoare Intr-un mod similar, evidențiem informații care pot fi donate.
Se crede că pierderile sunt cauzate de această etapă. Dacă codificați DCT o imagine și apoi utilizați funcția DCT inversă pentru a o reconstrui, nu veți obține exact același set de biți. Cu toate acestea, această eroare este o eroare de rotunjire. Apare la efectuarea operațiilor aritmetice și de obicei nu este foarte mare. Prin urmare, prefer să mă gândesc la etapa DCT ca la o activitate „în mare parte fără pierderi”.
Pentru imagini mari Calcularea DCT și DCT inversă este un proces care necesită foarte mult timp. Pentru a reduce timpul de calcul, JPEG împarte imaginea într-un mozaic de opt pe opt pixeli. Fiecare mozaic este procesat separat, ceea ce reduce semnificativ timpul de calcul necesar pentru DCT. Problema care apare cu această abordare este că după cuantizare (care va fi discutată în secțiunea următoare), limitele acestor pătrate pot să nu coincidă și, prin urmare, să devină vizibile atunci când se specifică valoare mica parametru de calitate.
Cuantizarea
Dezvoltatorii JPEG au fost interesați în primul rând de imagini de calitate fotografică (fotografie, ton continuu). De obicei, aceste imagini semitonuri sunt caracterizate de tranziții blânde de la o culoare la alta. Pentru astfel de imagini, componenta de frecvență joasă (se schimbă lent) a DCT este mai importantă decât componenta de frecvență înaltă (se schimbă rapid).
Termenul de cuantizare înseamnă pur și simplu „rotunjire”. JPEG elimină unele informatii grafice prin rotunjirea fiecărui termen DCT cu ponderi diferite bazate pe diferiți factori. Componenta de înaltă frecvență este rotunjită mai mult decât componenta de joasă frecvență. De exemplu, componenta de joasă frecvență care stochează valoarea medie a luminozității poate fi rotunjită la un multiplu de trei, în timp ce componenta de înaltă frecvență poate fi rotunjită la un multiplu de o sută!
Operația de cuantizare explică de ce compresia JPEG produce linii agitate atunci când marginile sunt ascuțite. Contururile sunt determinate de o componentă spațială de înaltă frecvență (în schimbare rapidă). (La prima vedere, ați putea crede că ar trebui să ajungeți cu un contur neclar, dar amintiți-vă că C din DCT înseamnă cosinus.)
De obicei, planurile de culoare sunt cuantificate mult mai grosier decât planurile de luminozitate. Aici alegerea potrivita Modelul de culoare ajută la identificarea informațiilor care pot fi aruncate.
Comprimare
Până acum, cu excepția cazului în care frecvența de eșantionare de două canale de culoare, nu a avut loc compresie. Toți pașii discutați mai sus - conversia modelului de culoare, DCT și cuantificare - au lăsat neschimbată dimensiunea datelor. Am ajuns în sfârșit la pasul final, în care tehnicile standard de compresie fără pierderi vor reduce de fapt dimensiunea datelor.
Datele descompuse în pașii anteriori pot fi comprimate mai eficient decât materia primă care este datele grafice RGB. În plus, niciunul dintre pașii întreprinși nu a fost de prisos; fiecare modificare a datelor a avut ca scop comprimarea mai eficientă a versiunii finale.
Schimbarea modelului de culoare a făcut posibilă subțirea informațiilor canalelor și apoi cuantificarea lor mai energic.
DCT a făcut posibilă izolarea componentei spațiale de înaltă frecvență. Componenta de înaltă frecvență are de obicei valori mici, ceea ce duce la ieșirea etapei DCT care conține un număr disproporționat de valori mici pentru a facilita procesul de compresie.
În timpul procesului de cuantificare, cea mai mare parte a componentei de înaltă frecvență este resetată la zero, iar restul ia valori specifice. Reducerea numărului sensuri diferite facilitează, de asemenea, procesul de comprimare a datelor.
Standardul JPEG oferă două diverse metode compresie fără pierderi care poate fi utilizată ultima etapă. Compresia Huffman este un algoritm de mult cunoscut, neproprietar, ușor de programat. În schimb, mai mult nou algoritm Codarea aritmetică face obiectul a numeroase brevete. (Deci nu este surprinzător că multe programe de compresie JPEG acceptă doar compresia Huffman.)
La decodare Imagini JPEG toți acești pași trebuie finalizați în ordine inversă. Fluxul de date este mai întâi decomprimat, apoi fiecare bloc de 8-8 este supus la DCT inversă și în final imaginea este convertită în blocul corespunzător. model de culoare(de obicei RGB). Rețineți că informațiile care au fost aruncate în mod deliberat prin decimare și cuantizare nu sunt niciodată recuperate. Cu toate acestea, dacă totul a fost făcut corect, pierderea de informații nu va provoca nicio degradare vizibilă a imaginii.
Probleme cu algoritmii de arhivare cu pierderiAlgoritmii convenționali au fost primii folosiți pentru arhivarea imaginilor. Cele care au fost și sunt folosite în sistemele de backup, la crearea distribuțiilor etc. Acești algoritmi au arhivat informațiile neschimbate. Cu toate acestea, tendința principală recent a fost utilizarea de noi clase de imagini. Algoritmii vechi nu mai îndeplinesc cerințele de arhivare. Multe imagini nu erau practic comprimate, deși „la prima vedere” aveau o redundanță evidentă. Acest lucru a dus la crearea unui nou tip de algoritm - compresie cu pierdere de informații. De regulă, se poate seta coeficientul de arhivare și, prin urmare, gradul de pierdere a calității în acestea. Acest lucru creează un compromis între dimensiunea și calitatea imaginii.
Una dintre problemele grave ale graficii pe computer este că încă nu a fost găsit un criteriu adecvat pentru evaluarea pierderilor de calitate a imaginii. Și se pierde constant - în timpul digitizării, în timpul traducerii într-o paletă de culori limitată, în timpul traducerii într-un alt sistem de reprezentare a culorilor pentru imprimare și, ceea ce este deosebit de important pentru noi, în timpul arhivării cu pierderi. Un exemplu de criteriu simplu poate fi dat: abaterea standard a valorilor pixelilor (L 2 măsură sau rădăcină pătrată medie - RMS):
Potrivit acesteia, imaginea va fi foarte deteriorată atunci când luminozitatea este redusă cu doar 5% (ochiul nu va observa acest lucru - monitoare diferite Setarea de luminozitate variază mult mai mult). În același timp, imaginile cu „zăpadă” - o schimbare bruscă a culorii punctelor individuale, dungi slabe sau „moiré” vor fi considerate „aproape neschimbate” (Explicați de ce?). Alte criterii au și laturile lor neplăcute.
Luați în considerare, de exemplu, abaterea maximă:
Această măsură, după cum ați putea ghici, este extrem de sensibilă la epuizarea pixelilor individuali. Acestea. În întreaga imagine, doar valoarea unui pixel se poate schimba semnificativ (ceea ce este aproape insesizabil pentru ochi), cu toate acestea, conform acestei măsuri, imaginea va fi foarte deteriorată.
Măsura care este utilizată acum în practică se numește raportul semnal-zgomot vârf-la-vârf (PSNR).
Această măsură este în esență similară cu abaterea standard, dar este ceva mai convenabil de utilizat datorită scării logaritmice a scalei. Are aceleași dezavantaje ca și abaterea standard.
Ochii noștri sunt cel mai bun judecător al pierderii calității imaginii. Arhivarea este considerată excelentă dacă este imposibil să se facă distincția cu ochiul între imaginile originale și cele nearhivate. Lucrul bun este că, atunci când poți spune care dintre imagini a fost arhivată, poți compara doar două imagini adiacente. Odată cu o creștere suplimentară a raportului de compresie, de regulă, efectele secundare caracteristice acestui algoritm devin vizibile. În practică, chiar și cu o calitate excelentă de conservare, se pot face modificări specifice imaginii în mod regulat. Prin urmare, nu este recomandat să utilizați algoritmi de arhivare cu pierderi atunci când comprimați imagini care ulterior vor fi fie tipărite la calitate înaltă, fie procesate cu programe de recunoaștere a imaginii. Efectele neplăcute cu astfel de imagini, așa cum am spus deja, pot apărea chiar și cu o simplă scalare a imaginii. algoritm JPEG
JPEG este unul dintre cei mai noi și destul de puternici algoritmi. Este practic standardul de facto pentru imagini color. Algoritmul operează pe zone de 8x8 în care luminozitatea și culoarea se schimbă relativ ușor. Ca urmare, la descompunerea matricei unei astfel de zone într-o serie dublă în cosinus (vezi formulele de mai jos), doar primii coeficienți sunt semnificativi. Astfel, compresia JPEG este realizată prin schimbarea lină a culorilor din imagine.
Algoritmul a fost dezvoltat de un grup de experți în fotografie special pentru comprimarea imaginilor pe 24 de biți. JPEG - Joint Photographic Expert Group - o divizie din cadrul ISO - Organizația Internațională pentru Standardizare. Numele algoritmului este ["jei"peg]. În general, algoritmul se bazează pe o transformată cosinus discretă (denumită în continuare DCT) aplicată matricei imaginii 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 chiar caz simplu este o deplasare aritmetică la dreapta pe biți. Cu această conversie, unele informații se pierd, dar se pot obține rapoarte mari de compresie.
Cum funcționează algoritmul
Deci, să ne uităm la algoritm mai detaliat. Să comprimăm o imagine pe 24 de biți.
Pasul 1.
Traducerea unei imagini din spațiu de culoare RGB, cu componente responsabile pentru componentele roșii, verzi și albastre ale culorii unui punct, în spațiul de culoare YCrCb (uneori numit YUV).
În ea, Y este componenta de luminozitate, iar Cr, 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 componentele Cr și Cb cu pierderi mari și, în consecință, cu rapoarte de compresie ridicate. Acest tip de conversie a fost folosit în televiziune de mult timp. 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:
Transformarea inversă se realizează prin înmulțirea vectorului YUV cu matricea inversă.
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 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-un rând și printr-o coloană. Acestea. 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 compresia de două 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.
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 corespunde componentei de joasă frecvență a imaginii, iar în dreapta jos - celei de înaltă frecvență.
Într-o formă simplificată, această transformare poate fi reprezentată după cum urmează:
Pasul 4.
Efectuăm cuantizarea. Î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, este specificată propria sa matrice de cuantizare q (denumită în continuare MC).
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 de 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.
Convertim matricea 8x8 într-un vector de 64 de elemente folosind scanarea „zigzag”, adică. iau elemente cu indici (0,0), (0,1), (1,0), (2,0)...
Astfel, la începutul vectorului obținem coeficienții matricei corespunzători frecvente joase, iar la final - mare.
Pasul 6.
Restrângem vectorul folosind algoritmul de codificare de grup. În acest caz, obținem perechi de tip (sărire, număr), unde „sărire” este contorul de zerouri omise, iar „număr” este valoarea care trebuie pusă în celula următoare. Astfel, vectorul 42 3 0 0 0 -2 0 0 0 0 1 ... va fi pliat în perechi (0,42) (0,3) (3,-2) (4,1) ... .
Pasul 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.
Conducta de operațiuni utilizate în algoritmul JPEG.
Esenţial aspecte pozitive Algoritmul este ca:
- Setează raportul de compresie.
- Zi libera imagine color poate avea 24 de biți pe punct.
- 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 granițelor tranzițiilor clare de culoare.
Această din urmă cerință a făcut posibilă apariția unor astfel de jucării precum camerele digitale - dispozitive de dimensiunea unei camere video mici care fac fotografii pe 24 de biți pe un card flash de 10-20 MB cu o interfață PCMCIA. Apoi acest card este introdus într-un slot de pe laptop și programul corespunzător vă permite să citiți imagini. Nu-i așa că, 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 că adesea dungile orizontale și verticale de pe afișaj sunt complet invizibile și pot apărea doar atunci când sunt imprimate 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 pentru utilizare activă în imprimare, stabilind coeficienți mari. Cu toate acestea, atunci când arhivați imagini destinate vizionarii umane, în prezent este indispensabil.
Aplicație largă a JPEG pentru o lungă perioadă de timp a fost, probabil, reținut 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 să se utilizeze algoritmi corespunzători și, prin urmare, anumit timp. În aplicațiile destinate utilizatorilor pretențioși, cum ar fi jocurile, astfel de întârzieri sunt inacceptabile. De asemenea, dacă imaginile pe care le aveți sunt, să zicem, pe 8 biți format GIF convertiți în JPEG pe 24 de biți și apoi înapoi în GIF pentru vizionare, apoi 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 (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 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. Î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 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:
Clasa de imagine: Imagini color pe 24 de biți sau imagini în tonuri de gri fără tranziții clare de culoare (fotografii).
Simetrie: 1
Caracteristici:În unele cazuri, algoritmul creează un „aureolă” în jurul limitelor orizontale și verticale clare din imagine (efectul Gibbs). În plus, cu un grad ridicat de compresie, imaginea este împărțită în blocuri de 8x8 pixeli.
Algoritm fractalIdeea metodei
Arhivarea fractale se bazează pe faptul că reprezentăm imaginea într-o formă mai compactă - utilizând coeficienții Sistemului de Funcții Iterate (denumit în continuare IFS). Înainte de a lua în considerare procesul de arhivare în sine, să ne uităm la modul în care IFS construiește o imagine, de exemplu. proces de decompresie.
Strict vorbind, IFS este un set de transformări afine tridimensionale, în cazul nostru transformând o imagine în alta. Punctele din spațiul tridimensional (coordonată x, coordonată y, luminozitate) suferă transformare.
Acest proces a fost demonstrat cel mai clar de Barnsley în cartea sa „Fractal Image Compression”. Acolo a fost introdus conceptul de mașină de fotocopiere, constând dintr-un ecran pe care este înfățișată imaginea originală și un sistem de lentile care proiectează imaginea pe alt ecran:
- Lentilele pot proiecta o parte din imagine liber de laîn orice altă locație din noua imagine.
- Regiuni in care imaginile sunt proiectate nu se intersectează.
- Lentila poate modificați luminozitatea și reduceți contrastul.
- Lentila poate oglindă și rotiți fragmentul de imagine.
- Obiectiv trebuie sa a masura(reduceți) fragmentul de imagine.
Prin aranjarea lentilelor și modificarea caracteristicilor acestora, putem controla imaginea rezultată. O iterație a lucrării Mașinii este că una nouă este construită din imaginea originală folosind design, după care cea nouă este luată ca cea inițială. Se argumentează că în timpul procesului de iterație vom obține o imagine care nu se va mai schimba. Va depinde doar de locația și caracteristicile lentilelor și nu va depinde de imaginea originală. Această imagine se numește „ punct fix" sau atractor dat IFS. Teoria corespunzătoare garantează că există exact un punct fix pentru fiecare IFS.
Deoarece maparea lentilei este compresivă, fiecare lentilă specifică în mod explicit auto-asemănătoare zone din imaginea noastră. Datorită auto-asemănării, obținem o structură complexă a imaginii la orice mărire. Astfel, este intuitiv ca un sistem de funcții iterabile să definească fractal(non-strict - un obiect matematic auto-similar).
Cele mai cunoscute două imagini obținute folosind IFS sunt „triunghiul Sierpinski” și „feriga Barnsley”. „Triunghiul Sierpinski” este definit prin trei, iar „feriga Barnsley” prin patru transformări afine (sau, în terminologia noastră, „lentile”). Fiecare transformare este codificată literalmente în câțiva octeți, în timp ce imaginea construită folosindu-le poate ocupa câțiva megaocteți.
Exercițiu: Identificați 4 zone din imagine, a căror unire ar acoperi întreaga imagine și fiecare dintre ele ar fi similară cu întreaga imagine (nu uitați de tulpina de feriga).
Din cele de mai sus, devine clar cum funcționează arhivatorul și de ce durează atât de mult timp. De fapt, compresia fractală este o căutare a zonelor auto-similare într-o imagine și determinarea parametrilor de transformare afine pentru acestea.
=>
În cel mai rău caz, dacă nu se utilizează un algoritm de optimizare, va fi necesar să se enumere și să se compare toate fragmentele posibile de imagini de diferite dimensiuni. Chiar și pentru imaginile mici, ținând cont de discreție, obținem un număr astronomic de opțiuni de rezolvat. Mai mult decât atât, chiar și o îngustare bruscă a claselor de transformare, de exemplu, datorită scalării doar de un anumit număr de ori, nu oferă un câștig vizibil în timp. În plus, calitatea imaginii se pierde. Marea majoritate a cercetărilor în domeniul compresiei fractale vizează acum reducerea timpului de arhivare necesar pentru a obține o imagine de înaltă calitate.
Definiție.
Unde a, b, c, d, e, f numerele reale sunt numite transformare afină bidimensională.
Definiție. Transformare, reprezentată în formă
unde a, b, c, d, e, f, p, q, r, s, t, u sunt numere reale și se numește o transformare afină tridimensională.
Definiție. Fie o transformare în spațiul X. Punctul este de așa natură încât se numește punct fix(atractor) transformare.
Definiție. O transformare într-un spațiu metric (X, d) se numește contractare dacă există un număr s: , astfel încât
Cometariu:În mod formal, putem folosi orice mapare de compresie pentru compresia fractală, dar în realitate sunt folosite doar transformări afine tridimensionale cu restricții destul de puternice asupra coeficienților.
Teorema. (Despre transformarea compresiei)
Lăsați spațiul metric complet (X, d). Atunci există exact un punct fix al acestei transformări și pentru orice punct șirul 
converge spre .
O formulare mai generală a acestei teoreme garantează convergența.
Definiție. Imagine este o funcție S definită pe pătratul unității și luând valori de la 0 la 1 sau
Fie ca transformarea afină tridimensională să fie scrisă sub forma
și este definită pe o submulțime compactă a pătratului cartezian x. Apoi va transfera o parte din suprafață Sîntr-o zonă situată cu tură (e,f)și rotația specificată de matrice
Mai mult, dacă interpretăm valoarea S pe măsură ce luminozitatea punctelor corespunzătoare, aceasta va scădea cu p ori (transformarea trebuie să fie compresivă) și se va schimba într-o forfecare q.
Definiție.
set finit W transformări afine tridimensionale contractive definite pe domenii precum 
, numit sistem de funcții iterabile ( IFS).
Sistemul de funcții iterate este asociat în mod unic cu un punct fix - o imagine. Astfel, procesul de compresie este de a găsi coeficienții sistemului, iar procesul de decompresie este de a itera sistemul până când imaginea rezultată (punctul fix IFS) este stabilizată. În practică, 7-16 iterații sunt suficiente. Zonele vor fi denumite în continuare clasat, iar zonele - domeniu.
Construcția algoritmului
După cum a devenit deja evident din cele de mai sus, sarcina principală la comprimarea cu un algoritm fractal este de a găsi transformările afine corespunzătoare. În cel mai general caz, putem traduce zone de imagine de orice dimensiune și formă, dar în acest caz obținem un număr astronomic de iterații ale diferitelor fragmente, care nu pot fi procesate în prezent nici măcar pe un supercomputer.
ÎN versiunea educațională a algoritmului , prezentate mai jos, se fac următoarele restricții asupra zonelor:
- Toate zonele sunt pătrate cu laturile paralele cu laturile imaginii. Această limitare este destul de strictă. De fapt, vom aproxima întreaga varietate forme geometrice doar pătrate.
- Când transferați o zonă de domeniu într-o zonă de rang, dimensiunea este redusă exact de două ori. Acest lucru simplifică foarte mult atât compresorul, cât și decompresorul, deoarece sarcina de a scala suprafețe mici nu este banală.
- Toate blocurile de domenii sunt pătrate și au marime fixa. Imaginea este împărțită într-un set de blocuri de domenii folosind o grilă uniformă.
- Zonele de domeniu sunt luate „prin un punct” atât în X, cât și în Y, care reduce imediat căutarea de 4 ori.
- Când transferați o zonă de domeniu într-o zonă de rang, este posibilă rotația cubului numai la 0 0, 90 0, 180 0 sau 270 0. De asemenea, permis reflexie în oglindă. Numărul total posibile transformări (numărând gol) - 8.
- Se realizează scalarea (compresia) pe verticală (luminozitatea). un număr fix de ori- la 0,75.
Aceste restricții permit:
- Construiți un algoritm care necesită un număr relativ mic de operații chiar și pe imagini destul de mari.
- Este foarte compact să prezinți date pentru scrierea într-un fișier. Avem nevoie pentru fiecare transformare afină în IFS:
- două numere pentru a seta decalajul blocului de domeniu. Dacă limităm imaginile de intrare la 512x512, atunci 8 biți pe număr vor fi de ajuns.
- trei biți pentru a specifica transformarea de simetrie la conversia unui bloc de domeniu într-un bloc de rang.
- 7-9 biți pentru a seta schimbarea luminozității în timpul translației.
De exemplu, pentru un fișier în tonuri de gri de 256 de culori 512x512 pixeli cu o dimensiune a blocului de 8 pixeli, vor exista 4096 transformări afine (512/8x512/8). Fiecare va necesita 3,5 octeți. Prin urmare, dacă fișierul original a ocupat 262144 (512x512) octeți (excluzând antetul), atunci fișierul cu coeficienți va ocupa 14336 octeți. Factor de arhivare - de 18 ori. Totodată, nu ținem cont că fișierul cu coeficienți poate avea și redundanță și ar putea fi arhivat folosind o metodă de arhivare fără pierderi, de exemplu LZW.
Aspecte negative ale restricțiilor propuse:
- Deoarece toate zonele sunt pătrate, este imposibil să profitați de asemănarea obiectelor care sunt departe de a fi pătrate în formă (care sunt destul de comune în imaginile reale).
- În mod similar, nu vom putea profita de asemănarea obiectelor din imagine, coeficientul de asemănare între care este foarte diferit de 2.
- Algoritmul nu va putea profita de asemănarea obiectelor din imagine, unghiul dintre care nu este un multiplu de 90 0.
Algoritmul de împachetare în sine se rezumă la enumerarea tuturor blocurilor de domenii și la selectarea unui bloc de rang corespunzător pentru fiecare. Mai jos este o diagramă a acestui algoritm.
pentru (toate blocurile de gamă) (
min_distance = MaximumDistance;
R ij= imagine->CopyBlock(i,j);
pentru (toate blocurile de domenii) ( // Cu rotații și neg.
curent=Coordonatele curente transformări;
D=imagine->CopyBlock(current);
distanta_actuala = R ij.L2distanta(D);
if(distanta_curenta< min_distance) {
// Dacă cele mai bune cote sunt mai slabe:
distanta_min = distanta_actuala;
cel mai bun = curent;
}
) //Următorul interval
Salvare_Coeficienți_în_fișier(cel mai bun);
) //Domeniul următor
După cum se poate observa din algoritmul de mai sus, pentru fiecare bloc de rang îl verificăm cu toate blocurile de domeniu posibile (inclusiv cele care au suferit transformarea de simetrie), găsim opțiunea cu cea mai mică măsură L 2 (cea mai mică abatere standard) și salvați coeficienții acestei conversii într-un fișier. Coeficienții sunt (1) coordonatele blocului găsit, (2) un număr de la 0 la 7 care caracterizează transformarea de simetrie (rotația, reflectarea blocului) și (3) deplasarea luminozității pentru această pereche de blocuri. Schimbarea luminozității se calculează astfel:
,
Unde r ij- valorile pixelilor blocului de clasare ( R), A d ij- valorile pixelilor blocului de domeniu ( D). În acest caz, măsura se calculează astfel:
.
Noi nu calculăm rădăcină pătrată de la L 2 masuri si nu o imparti la n,întrucât aceste transformări sunt monotone și nu ne vor împiedica să găsim extremul, totuși vom putea efectua două operații mai puține pentru fiecare bloc.
Să calculăm numărul de operații de care avem nevoie pentru a comprima o imagine în tonuri de gri de 256 de culori 512x512 pixeli cu o dimensiune a blocului de 8 pixeli:
Astfel, am reușit să reducem numărul de operații ale algoritmului de compresie la valori destul de calculabile (chiar dacă a durat câteva ore).
Schema algoritmului de decompresie a imaginii
Decomprimarea algoritmului de compresie fractală este extrem de simplă. Este necesar să se efectueze mai multe iterații ale transformărilor afine tridimensionale, ai căror coeficienți au fost obținuți în etapa de compresie.
Absolut orice imagine (de exemplu, absolut neagră) poate fi luată ca fiind cea inițială, deoarece aparatul matematic corespunzător ne garantează convergența secvenței de imagini obținute în timpul iterațiilor IFS la o imagine statică (aproape de cea originală). De obicei, 16 iterații sunt suficiente pentru asta.
Să citim coeficienții tuturor blocurilor din fișier;
Să creăm imagine neagră dimensiunea potrivită;
Până când (imaginea nu va deveni nemișcată)(
Pentru (fiecare interval (R))(
D=imagine->CopyBlock(D_coord_for_R);
Pentru(fiecare pixel( i,j) in bloc(
R ij = 0,75 D ij + o R;
) //Următorul pixel
) //Blocul următor
)//Până la sfârșit
Din moment ce am notat coeficienții pentru blocuri R ij(care, după cum am afirmat, în cazul nostru particular sunt pătrate de aceeași dimensiune) secvenţial, apoi se dovedește că umplem secvențial imaginea cu pătratele grilei de partiție folosind o transformare afină.
După cum se poate calcula, numărul de operații per pixel al unei imagini în tonuri de gri în timpul restaurării este neobișnuit de mic (N operațiuni „+”, operație 1 „*”, unde N este numărul de iterații, adică 7-16). Datorită acestui fapt, decompresia imaginii pentru un algoritm fractal este mai rapidă decât decompresia, de exemplu, pentru algoritmul JPEG, în care există 64 de operații „+” și 64 „?” pe punct (cu implementarea optimă a operațiilor de cuantizare inversă și DCT) . ” (fără a lua în considerare pașii RLE și codarea Huffman!). În acest caz, pentru algoritmul fractal, înmulțirea are loc cu un număr rațional, câte unul pentru fiecare bloc. Aceasta înseamnă că putem, în primul rând, să folosim aritmetica rațională cu numere întregi, care este semnificativ mai rapidă decât aritmetica în virgulă mobilă. În al doilea rând, înmulțirea unui vector cu un număr este o operație mai simplă și mai rapidă, adesea încorporată în arhitectura procesorului (procesoare SGI, Intel MMX...), decât produsul scalar a doi vectori necesar în cazul JPEG. Pentru o imagine plină color, situația nu se schimbă calitativ, deoarece ambii algoritmi folosesc conversia într-un alt spațiu de culoare.
Evaluarea pierderilor și modalitățile de reglementare a acestora
La rezumat versiunea simplificată a algoritmului a omis multe probleme importante. De exemplu, ce să faceți dacă algoritmul nu poate găsi unul similar pentru un anumit fragment de imagine? O soluție destul de evidentă este să împărțiți acest fragment în altele mai mici și să încercați să le căutați. În același timp, este clar că această procedură nu poate fi repetată la infinit, altfel numărul transformărilor necesare va deveni atât de mare încât algoritmul va înceta să mai fie un algoritm de compresie. Prin urmare, permitem pierderi într-o anumită parte a imaginii.
Pentru algoritmul de compresie fractală, ca și pentru alți algoritmi de compresie cu pierderi, mecanismele prin care se pot ajusta gradul de compresie și gradul de pierdere sunt foarte importante. Până în prezent, a fost dezvoltat un set destul de mare de astfel de metode. În primul rând, puteți limita numărul de transformări afine, asigurându-vă cu bună știință că gradul de compresie nu este mai mic decât o valoare fixă. În al doilea rând, puteți cere ca, într-o situație în care diferența dintre fragmentul procesat și cea mai bună aproximare a acestuia este peste o anumită valoare de prag, acest fragment să fie zdrobit (trebuie instalate mai multe „lentile” pentru el). În al treilea rând, puteți interzice divizarea fragmentelor mai mici de, să zicem, patru puncte. Prin modificarea valorilor de prag și a priorității acestor condiții, vom putea controla foarte flexibil raportul de compresie a imaginii în intervalul de la potrivirea bit-bit la orice nivel de compresie. Rețineți că această flexibilitate va fi mult mai mare decât cea a celui mai apropiat „concurent” al său - algoritmul JPEG.
Caracteristicile algoritmului fractal :
Raport de compresie: 2-2000 (definit de utilizator).
Clasa de imagine: Imagini color pe 24 de biți sau imagini în tonuri de gri fără tranziții clare de culoare (fotografii). Este de dorit ca zonele cu o semnificație mai mare (pentru percepție) să fie mai contrastante și mai clare, iar zonele cu semnificație mai mică să fie cu contrast redus și neclare.
Simetrie: 100-100000
Caracteristici: Poate scala în mod liber imaginea la dezarhivare, mărind-o de 2-4 ori fără apariția unui „efect de scară”. Pe măsură ce gradul de compresie crește, la granițele blocurilor din imagine apare un efect „blocat”.
Algoritm recursiv (undă).Denumirea engleză pentru compresia recursivă este wavelet. Este tradus în rusă ca compresie de undă și compresie folosind rafale. Acest tip de arhivare este cunoscut de destul de mult timp și vine direct din ideea de a folosi coerența zonelor. Algoritmul se concentrează pe imagini color și alb-negru cu tranziții netede. Ideal pentru poze ca raze X. Raportul de compresie este setat și variază de la 5 la 100. Când încercați să setați un coeficient mai mare pe granițele ascuțite, în special pe cele care rulează în diagonală, apare un „efect de scară” - pași de luminozitate diferită de câțiva pixeli.
Ideea algoritmului este că salvăm diferența într-un fișier - un număr între valorile medii ale blocurilor învecinate din imagine, care de obicei ia valori apropiate de 0.
Deci două numere A 2iȘi A 2i +1 poate fi întotdeauna reprezentat sub formă b 1 i=(A 2i +A 2i +1 )/2 și b 2 i=(A 2i -A 2i +1 )/2. Secvență similară A ipoate fi tradus perechi într-o secvență b 1.2i.
Să rezolvăm exemplu concret: Să comprimăm un șir de valori de luminozitate de 8 pixeli ( A i): (220, 211, 212, 218, 217, 214, 210, 202). Vom obține următoarele secvențe b 1 i, Și b 2 i: (215,5, 215, 215,5, 206) şi (4,5, -3, 1,5, 4). Rețineți că valorile b 2 isunt destul de apropiate de 0. Să repetăm operația, având în vedere b 1 i Cum A i. Această acțiune este efectuată recursiv, de unde și denumirea algoritmului. Obținem de la (215,5, 215, 215,5, 206): (215,25, 210,75) (0,25, 4,75). Putem pune coeficienții rezultați, rotunjiți la numere întregi și comprimați, de exemplu, folosind algoritmul Huffman cu tabele fixe, într-un fișier.
Rețineți că am aplicat transformarea noastră la lanț doar de două ori. În realitate, ne putem permite să folosim transformarea wavelet de 4-6 ori. Mai mult, o compresie suplimentară poate fi obținută prin utilizarea tabelelor de algoritmi Huffman cu spațiere neuniformă (adică, va trebui să stocăm codul Huffman pentru cea mai apropiată valoare din tabel). Aceste tehnici vă permit să obțineți rapoarte de compresie vizibile.
Exercițiu: Am restaurat lanțul (215, 211) (0, 5) (5, -3, 2, 4) din fișier (vezi exemplu). Construiți un șir de valori de luminozitate de opt pixeli pe care algoritmul de compresie a undelor le va recrea.
Algoritmul pentru datele bidimensionale este implementat în mod similar. Dacă avem un pătrat de 4 puncte cu luminozități A 2 i, 2 j,A 2 i +1, 2 j,A 2 i, 2 j +1, Și A 2 i +1, 2 j +1, Acea
| Original | B 1 | B 2 | |
| imagine | B 3 | B 4 |
Folosind aceste formule, pentru o imagine de 512x512 pixeli, dupa prima transformare obtinem 4 matrici de 256x256 elemente in dimensiune:
-- 
Primul, după cum ați putea ghici, va stoca o copie mică a imaginii. În al doilea - diferențele medii între perechile de valori de pixeli pe orizontală. În al treilea - diferențele medii între perechile de valori pixeli de-a lungul verticală. În al patrulea - diferențele medii ale valorilor pixelilor de-a lungul diagonalei. Prin analogie cu cazul bidimensional, putem repeta transformarea noastră și obținem 4 matrici de dimensiunea 128x128 în loc de prima matrice. Repetând transformarea noastră a treia oară, vom ajunge cu: 4 matrici 64x64, 3 matrici 128x128 și 3 matrici 256x256. În practică, atunci când scrieți într-un fișier, valorile obținute în ultima linie () sunt de obicei neglijate (obținând imediat un câștig de aproximativ o treime din dimensiunea fișierului - 1- 1/4 - 1/16 - 1/64 ...).
Avantajele acestui algoritm includ faptul că face foarte ușor posibilă „dezvoltarea” treptată a unei imagini atunci când se transmite o imagine printr-o rețea. În plus, deoarece stocăm de fapt o copie mai mică a imaginii în partea de sus a imaginii, este mai ușor să afișați imaginea „mărită” după titlu.
Spre deosebire de JPEG și algoritmul fractal, această metodă nu funcționează în blocuri, de exemplu, 8x8 pixeli. Mai exact, operăm cu blocuri de 2x2, 4x4, 8x8 etc. Cu toate acestea, datorită faptului că salvăm coeficienții pentru aceste blocuri în mod independent, putem evita destul de ușor împărțirea imaginii în pătrate „mozaic”.
Caracteristicile algoritmului undei:
Rapoarte de compresie: 2-200 (definite de utilizator).
Clasa de imagine: Ca fractal și JPEG.
Simetrie: ~1.5
Caracteristici:În plus, cu un grad ridicat de compresie, imaginea se descompune în blocuri separate.
Concluzie
În concluzie, să ne uităm la tabelele care rezumă parametrii diferiților algoritmi de compresie a imaginii pe care i-am discutat mai sus.
| Algoritm | Caracteristicile imaginii datorită cărora are loc compresia |
| RLE | Culori identice consecutive: 2 2 2 2 2 2 15 15 15 |
| LZW | Sublanțuri identice: 2 3 15 40 2 3 15 40 |
| Huffman | Frecvență de culoare diferită: 2 2 3 2 2 4 3 2 2 2 4 |
| CCITT-3 | Predominanţă albîntr-o imagine, zone mari umplute cu o singură culoare |
| Recursiv | Tranziții netede de culoare și fără limite clare |
| JPEG | Fără granițe clare |
| Fractal | Similaritate între elementele imaginii |
| Algoritm | Truse de compresie | Simetria timpului | Pentru ce orientat |
Pierderi | Dimensiune |
| RLE | 32, 2, 0.5 | 1 | 3,4 biți | Nu | 1D |
| LZW | 1000, 4, 5/7 | 1.2-3 | 1-8 biți | Nu | 1D |
| Huffman | 8, 1.5, 1 | 1-1.5 | 8 biți | Nu | 1D |
| CCITT-3 | 213(3), 5, 0.25 | ~1 | 1 bit | Nu | 1D |
| JBIG | de 2-30 de ori | ~1 | 1 bit | Nu | 2D |
| JPEG fără pierderi | de 2 ori | ~1 | 24 de biți, gri | Nu | 2D |
| JPEG | de 2-20 de ori | ~1 | 24 de biți, gri | da | 2D |
| Compresie recursiva | de 2-200 de ori | 1.5 | 24 de biți, gri | da | 2D |
| Fractal | de 2-2000 de ori | 1000-10000 | 24 de biți, gri | da | 2.5D |
- Tutorial
UPD. Am fost forțat să elimin formatarea monospace. Într-o bună zi, habraparser a încetat să accepte formatarea în interior etichete preși cod. Întregul text s-a transformat în zâmbet. Administrația Habr nu m-a putut ajuta. Acum este neuniform, dar cel puțin este lizibil.
Ai vrut vreodată să știi cum funcționează un fișier jpg? Să ne dăm seama acum! Încălzește-ți compilatorul și editorul hexadecimal preferat, vom decoda asta:
Am luat în mod deliberat un desen mai mic. Acesta este un favicon Google familiar, dar foarte comprimat:
Vă avertizez imediat că descrierea este simplificată și informațiile furnizate nu sunt complete, dar ulterior va fi ușor de înțeles specificația.
Chiar și fără a ști cum are loc codificarea, putem deja extrage ceva din fișier.
- marker de pornire. Este întotdeauna la începutul tuturor fișierelor jpg.
Urmează octeții
. Acesta este un marcator care indică începutul unei secțiuni 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 de caractere „:” și „)”, adică. un emoticon obișnuit. Îl puteți vedea în prima linie din partea dreaptă a editorului hexadecimal.
Puțină teorie
Foarte pe scurt pas cu pas:
Să ne gândim la ordinea în care ar putea fi codificate aceste date. Să presupunem că canalul Y este complet codificat pentru întreaga imagine, 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 întemeiate. Prin urmare, datele codificate sunt aranjate una câte una, î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 această ordine: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20
Citirea unui fișier
Odată ce am extras comentariul, va fi ușor de înțeles că:- Fișierul este împărțit în sectoare precedate de markeri.
- Markerii au o lungime de 2 octeți, primul octet fiind .
- 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 are întotdeauna 3 octeți. În cazul nostru este. Antetul este format din:
Lungime: 0x43 = 67 de octeți
Lungimea valorilor din tabel: 0 (0 - 1 octet, 1 - 2 octeți)
[_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ă folosind metoda de bază. Este foarte comun. Dar nu mai puțin populară pe Internet este metoda progresivă familiară, atunci când o imagine este încărcată pentru prima dată rezolutie scazuta, și apoi o imagine normală. Acest lucru vă permite să înțelegeți ceea ce este afișat acolo fără să așteptați sarcina completa. Specificația definește mai multe 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 imaginii: 0x10 = 16
Lățimea figurii: 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]
Subțiere verticală (V 1): 2
ID tabel de cuantizare: 0
componenta a doua:
ID: 2
Diluare orizontală (H 2): 1
[_1]
Subțiere verticală (V 2): 1
componenta a treia:
ID: 3
Diluare orizontală (H 3): 1
[_1]
Rărirea verticală (V 3): 1
ID tabel de cuantizare: 1
Acum uitați-vă la cum să determinați cât de subțire este o imagine. Găsim H max =2 și V max =2. Canalul i va fi subțiat de H max /H i ori orizontal și V max /V i ori vertical.
Marcator: DHT (tabelul Huffman)
Această secțiune stochează codurile și valorile obținute prin codificarea 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 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ă. Vă rugăm să 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. În total 2 coduri, nu mai există coduri în acest tabel.
Fiecare cod are o valoare asociată cu acesta și sunt listate în fișier după cum urmează. Valorile sunt pe un singur octet, deci citim 2 octeți.
- valoarea primului cod.
- valoarea celui de-al 2-lea cod.
Construcția unui arbore de cod Huffman
Trebuie să construim un arbore binar din tabelul primit în secțiunea DHT. Și din acest arbore recunoaștem fiecare cod. Adăugăm valorile în ordinea în care sunt indicate în tabel. Algoritmul este simplu: indiferent în ce nod 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 valorii 0, cele din dreapta - 1.Cometariu:
Nu trebuie să începi de sus de fiecare dată. A adăugat o valoare - reveniți la un nivel superior. Există ramura potrivită? Dacă da, urcă din nou. Dacă nu, creați o ramură dreaptă și mergeți acolo. Apoi, din acest punct, începeți să căutați 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ă valori 0x03 și 0x02
În cercuri sunt semnificațiile codurilor, sub cercuri sunt codurile în sine (dați-mi să vă explic că le-am obținut mergând prin calea de sus la fiecare nod). Cu aceste coduri (ale acestui și altor tabele) este codificat însuși conținutul figurii.
Marcator: SOS (Start of Scan)
Octetul din marker înseamnă „DA! În cele din urmă, am trecut direct la analizarea secțiunii de imagine codificată!” Cu toate acestea, secțiunea se numește simbolic SOS. 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, câte unul pentru Y, Cb, Cr.
Prima componenta:
Număr componentă a imaginii: 1 (Y)
ID-ul tabelului Huffman pentru coeficienții DC: 0
[_0]
ID-ul tabelului Huffman pentru coeficienții AC: 0
componenta a doua:
Numărul componentei imaginii: 2 (Cb)
[_1]
componenta a treia:
Numărul componentei imaginii: 3 (Cr)
ID tabel Huffman pentru coeficienții DC: 1
[_1]
ID-ul tabelului Huffman pentru coeficienții AC: 1
Aceste componente se alternează ciclic.
Aici se termină partea antetului, de aici până la sfârșit (marker) sunt datele 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 ramurii 0 sau 1, în funcție de bitul citit. Ne oprim dacă ne aflăm la nodul final.
10
1011101110011101100001111100100
2.
Luăm valoarea nodului. Dacă este egal cu 0, atunci coeficientul este egal cu 0, îl scriem î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 reprezentare binară- 1, apoi lăsați-l așa cum este: DC_coef = valoare. În caz contrar, transformăm: DC_coef = valoare-2 valoare lungime +1 . Scriem coeficientul în tabel la începutul zigzagului - colțul din stânga sus.
Găsirea coeficienților AC.
1.
Similar cu pasul 1, găsirea coeficientului DC. Continuăm să citim secvența:
10
10
1110
1110011101100001111100100
2.
Luăm valoarea nodului. Dacă este 0, aceasta î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 vor scrie despre asta într-un mesaj personal vor primi un plus în karma. În cazul nostru, valoarea nodului este 0x31.
Prima ciugulire: 0x3 - exact cam 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. Citiți următorul bit.
10
10
1110
1
110011101100001111100100
3. Similar cu pasul 3 de găsire a coeficientului DC.
După cum ați înțeles deja, trebuie să citiți coeficienții AC până ne întâlnim valoare nulă cod, sau până când matricea este umplută.
În cazul nostru vom obține:
10
10
1110
1
1100
11
101
10
0
0
0
1
11110
0
100
si matrice:
Ați observat că valorile sunt completate în același model în zig-zag?
Motivul utilizării acestei comenzi este simplu - pentru că ce valoare mai mare v și u, cu atât mai puțin semnificativ este coeficientul S vu în transformarea cosinus discret. Prin urmare, la rate de compresie ridicate, coeficienții nesemnificativi sunt setaț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)! Matricele trebuie corectate:
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 totul este în ordine. Această regulă se aplică până la sfârșitul fișierului.
... și conform matricei 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 există o singură matrice, coeficienții DC pot fi lăsați neatinse.
Calcule
Cuantizarea
Vă amintiți că matricea trece printr-o etapă de cuantizare? Elementele matricei trebuie înmulțite termen cu termen cu elementele matricei de cuantizare. Tot ce rămâne este să-l alegi pe cel de care ai nevoie. Am scanat prima componentă, componenta sa imagine = 1. Componenta imagine cu acest ID folosește o matrice de cuantizare de 0 (a noastră este prima dintre 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 de canal 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 trebuie să fie dificilă*. S vu este matricea noastră de coeficienți rezultată. u - coloană, v - rând. s yx - direct valorile canalului.
* Î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 imaginea de 600x600 (apropo, aceasta 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. Singurul lucru care m-a supărat cu adevărat a fost viteza de descărcare. Îmi amintesc încă că a durat 7 secunde. Dar acest lucru nu este surprinzător, dacă folosiț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. Gândește-te doar la asta - aproape o mie de operații dificile pe un singur canal de un pixel! Din fericire, este loc de optimizare (după multe experimente, am redus timpul de încărcare la limita de precizie a cronometrului de 15 ms, iar după aceea am schimbat imaginea cu o fotografie cu o suprafață de 25 de ori mai mare. Poate voi scrie despre asta în un articol separat).
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, mă duc să mănânc!
- Da, nu mă mut deloc, despre ce vorbim.
- Odată ce valorile culorii YCbCr au fost obținute, tot ce rămâne este să le convertim î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 un Cb și Cr fiecare, deoarece am subțiat canalele și 4 pixeli 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 depășesc intervalul, atunci atribuiți valori limită. Formula este simplă, dar consumă și o parte din timpul procesorului.
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
