Au fost dezvoltate multe metode de compresie lossy; totuși, o familie de tehnici numită compresia transformatei s-a dovedit a fi cea mai valoroasă. Cel mai bun exemplu de compresie a transformatei este încorporat în popularul standard JPEG al codării imaginii. JPEG este denumit după originea sa, Joint Photographers Experts Group. Vom descrie funcționarea JPEG pentru a ilustra cum lucrează compresia lossy.

Am discutat deja o metodă simplă de compresie lossy a datelor, eșantionare mai grosieră și/sau cuantizare (CS&Q în Tabelul 27-1). Aceasta implică reducerea numărului de biți per eșantion sau eliminarea integrală a unora dintre eșantioane. Ambele proceduri au efectul dorit: fișierul de date devine mai mic în detrimentul calității semnalului. Așa cum vă puteți aștepta, aceste metode simple nu funcționează foarte bine.

Figura 27-9 Divizarea imaginii JPEG.

Compresia transformatei JPEG pornește prin împărțirea imaginii în grupe 8x8, fiecare conținând 64 de pixeli. Trei din aceste grupe 8x8 sunt lărgite în această figură, arătând valorile pixelilor individuali, o singură valoare de octet între 0 și 255.

Compresia transformatei se bazează pe o premisă simplă: atunci când semnalul este trecut prin transformata Fourier (sau alta), valorile de date rezultate nu vor mai fi egale în rolurile lor de trasport al informației. În particular, componentele de joasă frecvență ale unui semnal sunt mai importante decât componentele de înaltă frecvență. Eliminarea a 50% din biții de la componentele de înaltă frecvență ar putea elimina, de exemplu, doar 5% din informațiile codificate.

După cum se arată în Fig. 27-9, compresia JPEG începe prin ruperea imaginii în grupuri de 8x8 pixeli. Algoritmul complet JPEG poate accepta o gamă largă de biți per pixel, inclusiv utilizarea informațiilor de culoare. În acest exemplu, fiecare pixel este un singur octet, o valoare a tonului de gri în intervalul 0 și 255. Aceste grupuri de 8×8 pixeli sunt tratate independent în timpul compresiei. Adică, fiecare grup este inițial reprezentat de 64 octeți. După transformarea și eliminarea datelor, fiecare grup este reprezentat, de exemplu, de 2 până la 20 de octeți. În timpul decompresiei, transformata inversă este luată de la 2 la 20 de octeți pentru a crea o aproximare a grupului inițial de 8×8. Aceste grupuri aproximate sunt apoi montate împreună pentru a forma imaginea necompresată. De ce utilizați grupuri de 8×8 pixeli în loc de, de exemplu, 16×16? Gruparea de 8×8 s-a bazat pe dimensiunea maximă pe care tehnologia cu circuite integrate o putea gestiona la momentul elaborării standardului. În orice caz, dimensiunea de 8×8 funcționează bine și poate sau poate nu fi modificată în viitor.

Au fost investigate multe transformate diferite pentru compresia datelor, unele dintre ele inventate în mod special. De exemplu, transformata Karhunen-Loeve oferă cel mai bun raport posibil de compresie, dar este dificil de implementat. Transformata Fourier este ușor de utilizat, dar nu oferă compresie adecvată. După multă concurență, câștigătorul este o rudă a transformatei Fourier, Transformata discretă cosinus (DCT).

La fel cum transformata Fourier utilizează unde sinus și cosinus pentru a reprezenta un semnal, DCT utilizează numai unde cosinus. Există mai multe versiuni ale DCT, cu mici diferențe în matematică. Ca un exemplu de o versiune, imaginați-vă un semnal de 129 de puncte, care rulează de la eșantionul 0 la eșantionul 128. Acum, faceți acesta un semnal de 256 puncte duplicând eșantioanele 1 până la 127 și adăugându-le ca eșantioane 255 la 130. Acela este: 0, 1 , 2, ..., 127, 128, 127, ..., 2, 1. Luând transformata Fourier a acestui semnal de 256 puncte rezultă un spectru de frecvență de 129 de puncte, împrăștiat între 0 și 128. Deoarece semnalul din domeniul timp a fost forțat să fie simetric, partea imaginară a spectrului va fi compusă toată din zerouri. Cu alte cuvinte, am început cu un semnal din domeniu timp de 129 de puncte și am terminat cu un spectru de frecvență de 129 de puncte, fiecare amplitudinea unei unde cosinus. Acesta este DCT!

Atunci când DCT este luat dintr-un grup de 8×8, rezultă un spectru de 8×8. Cu alte cuvinte, 64 numere sunt schimbate în 64 de alte numere. Toate aceste valori sunt reale; nu există matematică complexă aici. La fel ca în analiza Fourier, fiecare valoare din spectru este amplitudinea unei funcții de bază. Figura 27-10 arată 6 din cele 64 de funcții de bază utilizate într-un DCT de 8×8, în funcție de locul unde stă amplitudinea în spectru. Funcțiile de bază 8×8 DCT sunt date de:

Frecvențele joase se află în colțul din stânga sus al spectrului, în timp ce frecvențele înalte se află în partea dreaptă inferioară. Componenta DC este la [0,0], cea mai mare valoare din stânga-sus. Funcția de bază pentru [0,1] este o jumătate de ciclu de undă cosinus într-o direcție și o valoare constantă în cealaltă. Funcția de bază pentru [1,0] este similară, doar rotită cu 90°.

Figura 27-10 Funcțiile de bază DCT.

Spectrul DCT constă dintr-o matrice 8x8, cu fiecare element în matrice fiind o amplitudine a uneia din cele 64 de funcții de bază. Șase din aceste funcții de bază sunt arătate aici, raportate la unde aparține amplitudinea corespunzătoare.

DCT calculează spectrul prin corelarea grupului de pixeli de 8×8 cu fiecare dintre funcțiile de bază. Adică, fiecare valoare spectrală se găsește prin înmulțirea funcției de bază adecvate cu grupul de pixeli de 8×8 și apoi prin însumarea produselor. Două ajustări sunt necesare pentru finalizarea calculului DCT (la fel ca în cazul transformatei Fourier). Mai întâi, împărțiți cele 15 valori spectrale în rândul 0 și coloana 0 cu doi. În al doilea rând, împărțiți toate cele 64 de valori din spectru cu 16. DCT inversă se calculează prin atribuirea fiecăreia dintre amplitudinile spectrului la funcția de bază adecvată și însumare pentru a recrea domeniul spațial. Nu sunt necesari pași suplimentari. Acestea sunt exact aceleași concepte ca și în analiza Fourier, doar cu funcții de bază diferite.

Figura 27-11 ilustrează codificarea JPEG pentru cele trei grupuri de 8×8 identificate în Fig. 27-9. Coloana din stânga, Fig. a, b & c, arată valorile originale ale pixelilor. Coloana centrală, Fig. d, e & f, arată spectrul DCT al acestor grupuri.

Figura 27-11 Exemplu de codificare JPEG.

Coloana din stânga arată trei grupuri de 8x8 pixeli, aceleași arătate în fig. 27-9. Coloana centrală arată spectrele DCT ale acestor trei grupuri. A treia coloană arată eroarea din valorile pixelilor necomprimați rezultând din utilizarea unui număr finit de biți pentru a reprezenta spectrul.

Coloana din dreapta, Fig. g, h & i, arată efectul reducerii numărului de biți folosiți pentru a reprezenta fiecare componentă în spectrul de frecvență. De exemplu, (g) se formează prin trunchierea fiecăreia dintre eșantioane în (d) la zece biți, luând DCT inversă și apoi scăzând imaginea reconstruită din original. De asemenea, (h) și (i) sunt formate prin trunchierea fiecărui eșantion în spectru la opt și respectiv cinci biți. Așa cum era de așteptat, eroarea în reconstrucție crește deoarece mai puțini biți sunt utilizați pentru a reprezenta datele. Ca un exemplu de trunchiere a bitului, spectrele arătate în coloana centrală sunt reprezentate cu 8 biți pe valoare spectrală, aranjate ca 0 la 255 pentru componenta DC și -127 până la 127 pentru alte valori.

A doua metodă de compresie a domeniului de frecvență este eliminarea unora dintre cele 64 de valori spectrale. Așa cum se arată în spectrele din Fig. 27-11, aproape întregul semnal este conținut în componentele de frecvență joasă. Aceasta înseamnă că componentele de frecvențe cele mai înalte pot fi eliminate, în timp ce semnalul este degradat doar o cantitate mică. Fig. 27-12 arată un exemplu de distorsiune a imaginii care apare când sunt șterse numere diferite ale componentelor de înaltă frecvență. Grupul de 8×8 utilizat în acest exemplu este imaginea ochi din Fig. 27-10. Figura (d) prezintă reconstrucția corectă utilizând toate cele 64 de valori spectrale. Figurile rămase arată reconstrucția utilizând numărul indicat de coeficienți de frecvență cea mai scăzută. Așa cum este ilustrat în (c), chiar și eliminarea a trei sferturi din componentele cu frecvență cea mai mare produce o mică eroare în reconstrucție. Chiar mai bine, eroarea care apare seamănă foarte mult cu zgomotul aleatoriu.

Figura 27-13 Tabele de cuantizare JPEG.

Acestea sunt două exemple de tabele de cuantizare care ar putea fi utilizate pe durata comprimării. Fiecare valoare din spectrul DCT este divizată prin valoarea corespunzătoare din tabelul de cuantizare, iar rezultatul este rotunjit la cel mai apropiat întreg.

JPEG este un bun exemplu pentru modul în care mai multe scheme de compresie a datelor pot fi combinate pentru o mai mare eficiență. Întreaga procedură JPEG este prezentată în următorii pași. Mai întâi, imaginea este împărțită în grupurile de 8×8. În al doilea rând, se ia DCT pentru fiecare grup. În al treilea rând, fiecare spectru 8×8 este comprimat prin metodele de mai sus: reducerea numărului de biți și eliminarea unor componente. Aceasta are loc într-o singură etapă, controlată de un tabel de cuantizare. Două exemple de tabele de cuantizare sunt prezentate în Fig. 27-13. Fiecare valoare din spectru este împărțită de valoarea de potrivire din tabelul de cuantizare, iar rezultatul rotunjit la cel mai apropiat număr întreg. De exemplu, valoarea stânga-sus a tabelului de cuantizare este unu, ducând la menținerea neschimbată a valorii DC. În comparație, intrarea din partea inferioară-dreapta în (a) este 16, ceea ce înseamnă că intervalul inițial de -127 până la 127 este redus la doar -7 la 7. Cu alte cuvinte, valoarea a fost redusă în precizie de la opt biți la patru biți. Într-un caz mai extreme, intrarea din partea inferioară-dreapta din (b) este 256, eliminând complet valoarea spectrală.

În cea de-a patra etapă a codării JPEG, spectrul modificat este convertit dintr-o matrice de 8×8 într-o secvență liniară. Modelul serpentină prezentat în Fig. 27-14 este utilizat pentru această etapă, plasând toate componentele de înaltă frecvență împreună la sfârșitul secvenței liniare. Aceasta grupează zerourile din componentele eliminate în rulaje lungi. Cea de-a cincea etapă comprimă aceste rulaje de zerouri prin codarea lungimii de rulare. În etapa a șasea, secvența este codificată fie prin codificare Huffman, fie aritmetică, pentru a forma fișierul final comprimat.

Cantitatea de compresie și pierderea de calitate a imaginii pot fi selectate când se execută programul de compresie JPEG. Fig. 27-15 prezintă tipul de distorsiune a imaginii care rezultă din rapoartele de compresie ridicate. Cu raportul de compresie 45:1 prezentat, fiecare dintre grupurile 8x8 este reprezentat de doar aproximativ 12 biți. O inspecție apropiată a acestei imagini arată că șase dintre funcțiile de bază cu cele mai scăzute frecvențe sunt reprezentate într-o oarecare măsură.

De ce este DCT mai bună decât transformata Fourier pentru compresia imaginii? Principalul motiv este că DCT are funcții bazate pe o jumătate de ciclu, adică S [0,1] și S [1,0]. După cum se arată în Fig. 27-10, acestea se înclină ușor dintr-o parte a matricei la cealaltă. În comparație, cele mai scăzute frecvențe din transformata Fourier formează un ciclu complet. Imaginile conțin aproape întotdeauna regiuni în care luminozitatea se schimbă treptat pe o regiune. Folosind o funcție de bază care se potrivește cu acest model de bază se permite o compresie mai bună.

Secțiunea următoare: MPEG