Comprimarea imaginilor digitale in web - context-JPEG, transformarea Culorii

In 1992, un comitet comun intre Organizatia Internationala de Standardizare ISO) si Industriei de Standardizare Telecomunicatii a Uniunii Internationale a Telecomunicatiilor ITU-T), cunoscut sub numele de Photographic Experts Group JPEG) a emis un standard care a fost aprobat in ISO IEC sau ITU-T . Acest standard a primit numele de tehnologia informatiei de compresie digitala si codare de tonuri continue in continuare cerintele de imagini si liniile directoare,dar este cunoscut ca standard JPEG.
Scopul initial al JPEG a fost de a oferi in continuare tehnici de imagine de compresie pentru o gama larga de tipuri de imagini, image-reconstruita calitatii, si un raport de compresie permitand in acelasi timp implementarea software-ului.

Calitatea solutiei propuse a facut ca acest standard sa fie un succes, astfel ca, in prezent, JPEG codate imagini sunt prezente in aproape toate domeniile si aplicatii. Exemple clare ale acestui succes sunt utilizarea constanta a JPEG codate imagini in medii cum ar fi universal   web sau de acceptare la nivel mondial in industria de aparate digitale de fotografiat standard pentru a fi stocate.
Vom prezenta si ilustra principalele concepte din spatele standardului JPEG. Noi nu vom prezenta in detaliu caracteristicile standard, dar ne vom concentra pe instrumente comune, generice si concepte care le foloseste. Mai mult decat atat, deoarece aceste concepte sunt aplicate in filme comprimare.

1 Context JPEG

Figura 1 prezinta schema bloc a unui comprimare imagine tipica si de sisteme de transport. In ea, putem observa doua perechi diferite de blocuri: codificator sursa decodor si codificator canal decodor. Obiectivul codificator sursa este de a reduce cantitatea de date numarul mediu de biti) necesare pentru a reprezenta informatiile din semnal. Aceasta compresie a datelor se realizeaza mai ales prin exploatarea redundanta in informatiile despre imagine. La randul sau, obiectivul codificator canal este de a adauga redundanta la iesirea codificatorului sursa pentru a imbunatati fiabilitatea pe transport. Mai jos, ne vom concentra pe problema de codare sursa.

fig. 1 Schema bloc a unei imagini de compresie si de sisteme de transport
Transformarea directa a blocurilor (Noll si Jayant 1984) schimba descrierea imaginii in cautarea noului, coreland mai putin setul de probe transformat care descrie semnalul. Imaginea poate fi exact recuperate de la probele transformate, adica, in etapa transformarii nu introduce pierderi in descriere.
  Etapa de cuantificare (Gersho Gray si 1993) reprezinta o serie de valori de o proba data transformata de catre o valoare unica in sir.
Setul valorilor de iesire sunt indici de cuantificare. Acest pas este responsabil pentru pierderile din sistem si, prin urmare, determina
realizate de compresie.
Entropia Encoderului (Cover si Thomas 1991) produce bitstream final. Acesta exploateaza nonformitatea probabilitatii distributiei indicilor de cuantificare (simboluri).
In scopul de a decoda corect (bitstream) produse de sistemul de codificare, encoderul trebuie sa partajeze anumite informatii cu decodorul.
Decodorul ar trebui sa stie modul in care cuvintele de cod diferite au fost stocate in bitstream (definitia sintaxa) si care sunt asociate cu actiunile valorilor decodate diferit. Acesta informatie care defineste un standard (Chiariglione 1999) si duce la, de exemplu, stabilirea transformarii specifice care urmeaza sa fie utilizate la un anumit stadiu al decodarii proces sau intervalul de valori posibile ale unui anumit cuantificator index.
Cu toate acestea, un standard nu stabileste modul in care diferitii parametri trebuie sa fie calculati, deschizand posibilitatea pentru implementarea mai buna a codificatoarii conform cu standard. Mai mult, un standard poate introduce o oarecare flexibilitate suplimentara, deoarece unele dintre instrumentele de codificare adoptate de catre standard pot fi adaptate la datele prelucrate.
Acesta este motivul pentru care reprezinta in mod explicit de cuantificare si codificare tabele in Fig. 1. De obicei, aceste elemente pot fi alese din partea encoderelor pentru a imbunatati performantele de codificare si sunt transmise la decodor in bitstream.
In aceasta sectiune, ne vom concentra pe un set foarte specific de instrumente dintre toate cele posibile in contextul de transformare, cuantificare, si codare entropica.

Aceste instrumente sunt cele de baza pentru intelegerea principiilor standard JPEG (si o parte a videoclipului standardelor de codificare). In acest fel, in contextul transformarii, ne vom adresa unor culori de baza care transforma de la RGB la YCbCr si, ca frecventa transforma, cosinus discrete transforma . La randul sau, in entropia-codare zona, vom prezenta codurile Huffman, deoarece acestea sunt entropia-codare cele mai frecvente Unelte imagine coding. Aceasta sectiune se completeaza cu o revizuire a cateva specificatii JPEG si o discutie cu privire la masurile de calitate cele mai frecvente .


2. Transformarea Culorii

In contextul de comprimare imagine si video, un mod comun de a reprezenta imagini color este cu ajutorul asa-numitului YCbCr . Relatia dintre aceste componente si cele RGB este dat de urmatoarele expresii.

Avand in vedere factorii de ponderare.

Relatia intre componente este data de:

Componenta Y este o medie ponderata a componentelor rosu, verde si albastru si, prin urmare, este denumit in mod obisnuit componenta de luminanta a imaginii. La randul sau, Cb Cr) este o diferenta ponderata intre albastru rosu)componenta si componenta luminanta. Aceste diferente de culoare sunt frecvent mentionate ca si componentele crominanta.
In principal datorita densitatii diferite de luminozitate si culoare fotoreceptori conuri si tije, respectiv), in ochiul uman, sistemul vizual uman este in mod substantial mai putin sensibila la denaturarea din componenta crominanta. Aceasta proprietate este exploatata in codoare imagine si video in maniere diferite. De exemplu, componentele crominante sunt, de obicei, prelevate de catre un factor de 2 in directiile orizontala si verticala.


3. Frecventa transformari: cosinus discreta transforme

Transformarile liniare finite sunt utilizate in mod obisnuit in comprimare imagine si video. O transformare eficienta ar trebui sa profite de dependente statistice, printre probe de semnal x n n = 0, , Ní1 de exemplu, corelarea lor) si sa obtina un set de probe transformat y (k) (k = 0, Mí1), care prezinta, la cele mai multe, dependente locale, de exemplu, o transformare ar trebui sa decorrelate probe originale. Mai mult decat atat, o transformare ar trebui sa separe relevante de informatii irelevante, in scopul de a identifica probe irelevante. Nu in ultimul rand, transformarea ar trebui sa fie inversibila in scopul de a recupera o aproximare a) semnalului de la probele cuantic transformate. Retineti ca exista posibilitatea de a se renunta la unii coeficienti este inclusa in procesul de cuantificare, si anume, de cuantificare pot seta unii coeficienti transformati la zero.
In mod obisnuit pentru a studia o transformare analizam mai intai rolul de transformare invers.Transformarea inversa poate fi vazuta ca o descompunere liniara a unui semnal x n) in ceea ce priveste o suma ponderata de functii elementare s n),ponderi fiind transformat probe y k):

Proiect: Discurile optice Referat: Notiuni generale si parti componente ale calculatorului

Unde        

Vectorul contine

este denumit in mod obisnuit sinteza vector KTH.Motivul este ca, prin intermediul combinatiei liniare a vectorilor sinteza semnalul original este sintetizat reconstruit). La randul sau, matricea S este cunoscuta sub numele matrice desinteza. Retineti ca vectorii de sinteza sunt coloanele de matrice sinteza S:

Transformarea directa este obtinuta comparand semnalul x(n) cu un set de functii elementare:

In acest caz vectorul este format din:

Transformarea coeficientului poate fi exprimata asa:

Pentru a avea o transformare reversibila, S trebuie sa fie din stanga-inverse de AH, de exemplu, SAH = I. Cu toate acestea, vom restrange studiul la cazul de nonexpansive transforma, suntem presupunand ca hartile transforma N esantioane de x (n) in probe de N a lui y (k). In acest caz, M = N si SI1 = AH, si, in cazul in care transformarea este real-de prim rang, SI1 = AT.

Aceasta caracteristica este foarte utila atunci cand se lucreaza cu probe transformate din actiunile intreprinse de peste un coeficient cu o interpretare clara in ceea ce priveste consumul final de energie al semnalului. Acesta este un aspect foarte relevant atunci cand cuantificarea coeficientilor in scopul de a transforma un semnal aproximativ.
Cu toate acestea, desi energia totala se pastreaza, nu este distribuit in mod egal intre coeficientii de diferitele transformat de exemplu, componentele de vector y). Acesta poate fi demonstrat de Noll si Jayant care transforma conduce la concentrare de energie optima este asa-numita Karhunen Loewe transforma KLT).

Locurile KLT ca energie mai mult posibil in coeficientii de putine posibil. Prin urmare, cea mai mare parte ', explica' semnalului de intrare in ceea ce priveste un numar limitat de vectori de sinteza cele pentru care y are coeficientii de mare sinteza), o proprietate care este imediat transformata in profit in pasul de cuantificare. Cu toate acestea, analiza matricea A, in cazul KLT nu este fix, ci depinde de proprietatile statistice ale semnalul in analiza. De fapt, vectorii sai analiza a vectorii proprii ale semnalului de corelatie R matrice: Prin urmare, este semnalul KLT adaptat si matricea de analiza care defineste transforma trebuie estimate pentru fiecare semnal. Desi algoritmi rapizi au fost propuse, complexitatea generala a KLT este semnificativ mai mare decat complexitatea transforma alte posibile.
In cazul imaginilor, un bun compromis intre concentratia de energie si complexitatea de calcul este discret cosinusul transforme DCT). O definitie comuna a componentelor vectorilor de analiza sinteza DCT este dat de urmatoarea expres.Vectorii de analiza / sinteza constau din probe de functii cosinus Fig. . Observati ca vectorul prima analiza A0) dispune de toate probele de sanse si, astfel, primul DCT coeficientul este legata de valoarea medie a probelor in semnalul. In literatura de specialitate, acest coeficient este mentionata ca coeficientul DC, in timp ce restul a coeficientilor transformate sunt denumite AC.
Pentru a analiza proprietatile DCT, ne vom muta la primul caz de transforma in doua dimensiuni. In acest fel, vom fi capabili sa
scoate in evidenta unele caracteristici ale DCT, in cazul de prelucrare a imaginilor.

2D transforma


Pentru a simplifica notatiei, vom sa presupunem ca transformam unitar. Definitia de transformare 2D este dat de Ca anterior, putem interpreta inversa transforma ca o descompunere liniara a unui semnal x m, n) in ceea ce priveste o suma ponderata de elementare functionea (m, n), care acum poate fi vazut ca imagini elementare.Daca aceste functii elementare 2D poate fi exprimata ca un produs de doi 1D functii elementare, fiecare una care se ocupa cu o singura dimensiune in 2D definitia unei functii elementare, transformarea este declarat a fi separabile. Mai mult decat atat, in cazul in care doua functii 1D elementare sunt aceleasi, transformarea este a spus sa fie simetrice:

Proprietatea separare face posibila pentru a calcula transforma o N × N imaginea prin intermediul a doua inmultiri matrice de dimensiune N × N. In cazul in care transformarea nu este separabila, am putea reprezenta imaginea printr-un singur vector de dimensiune N2 si, folosindu-se ecuatia 8.6), calculati transforma printr-una multiplicare de un vector de dimensiune N2 cu o matrice de N2 dimensiune N2. Prin urmare, complexitatea este reduced7 de la O N4) la O N3).
In cazul imaginilor, asa cum am comentat anterior, discret cosinus transforma este frecvent utilizat.DCT prezinta toate proprietatile de mai sus a comentat (este separabila si simetrica), in timp ce, in plus, fiind real-evaluate.Expresie a DCT 2D, prin urmare, este dat de cu parametrul e definit ca in expresia 8.14).
In ceea ce priveste concentratia de energie, DCT atinge valori foarte mari, ajungand foarte aproape de performanta KLT.

De fapt, se poate demonstra ca, pentru cazul specific al First ordine 2D procese Markov, DCT este optima, precum si Noll si Jayant . Aceasta energie de concentrare.
Proprietatea este ilustrat in fig.

Figura 8.3 prezinta o imagine originala de 176 × 144 pixeli, precum si coeficientii corespunzatori DCT (valori au fost convenabil mutat si scalate pentru vizualizare). In Fig. 8.4, procentul de energie a reprezentarii imaginii atunci cand utilizati un numar tot mai mare de coeficienti DCT este prezentat pentru a ilustra modul in care transforma DCT este in masura sa compact de energie de pixeli ai imaginii in coeficienti mai putine. In Fig. 8.4a, DCT.

Coeficientii au fost sortate in functie de ordinea descrescatoare a energiei.
Fig. 8.4b, o scanare zigzag a fost folosit pentru a comanda coeficientilor DCT.

In Fig. 8.7, acelasi experiment se realizeaza, dar, de aceasta data, coeficientii primelor N sunt selectate folosind o scanare in zig-zag. Se poate observa ca scanarea zigzag constituie o buna aproximare de selectare a coeficientilor cu energie mai mare.
In exemplul anterior, am observat ca, desi DCT poate compact de energie a semnalului intr-un numar redus de coeficienti, faptul ca imaginile sunt semnale nestationare impiedica transforma din exploatarea in continuare a omogenizarii statistica a semnalului.

Posibilitatea de segmentare a imaginii in partile sale statistic omogen nu a fost avuta in vedere in abordarile clasice din procesul de segmentare a imaginii este o sarcina foarte complicata (segmentare este numit de multe ori o problema prost-puse) si in cazul in care o segmentare a imaginii este obtinuta, utilizarea partitiei in scopuri de codificare ar necesita transmiterea formele a regiunilor arbitrare si aceasta informatie limita este extrem de dificil pentru a comprima.
Aceasta problema este de obicei rezolvata prin impartirea imaginii intr-un set de blocuri patrat si prelucrarea informatiilor in cadrul fiecarui bloc separat. Aceasta conduce la utilizarea a transforma asa-numitul bloc. In acest caz, o partitie de fix este folosit, care este cunoscut in prealabil de catre receptor si nu necesita sa fie transmise. Deoarece aceasta partitie este independent de imagine in cadrul analizei, datele continute in fiecare bloc, nu pot impartasi aceleasi proprietati statistice. Cu toate acestea, avand in vedere dimensiunea redusa a blocurilor folosite (de obicei, 8 × 8 pixeli), informatiile din interiorul blocurilor pot fi considerate destul de omogen. Atunci cand utilizati transforma bloc (de exemplu, atunci cand impun o partitie imagine independente pentru compresia imaginii), este probabil sa respecte structura de bloc din imagine reconstruita. Acest artefact este cunoscut sub numele de efect de bloc, si este ilustrat in fig. 8.22.
In cazul DCT, atunci cand se utilizeaza blocuri de 8 × 8, vectorii de analiza / sinteza corespund expresiei care poate fi interpretat ca un set de 64 imagini elementare pe care semnalul original este descompus. In Fig. 8.8, vom prezenta aceste 64 de imagini 8 × 8 pixeli fiecare. Retineti ca valorile de analiza / sinteza vectorul au fost convenabil deplasat si scalate pentru a le reprezenta sub forma de imagini.

Studiul de performanta a DCT folosit ca un bloc de transformare pentru compresia imaginii este abordat in urmatoarea sectiune.
In ceea ce priveste complexitatea de calcul a DCT, trebuie sa fie spus ca, in afara de faptul de a fi separabile si simetrica, DCT prezinta o structura apropiata de cea a FFT, care permite implementari extrem de eficiente. De exemplu, in Arai et al. , un DCT punere in aplicare este prezentat faptul ca doar impune, pentru blocuri de pixeli, 5 inmultiri si 29 completarile ulterioare, in loc de de baza inmultiri.
In plus, majoritatea operatiunilor multiplica pot fi efectuate in
in paralel, astfel ca algoritmul propus este ideal pentru o punere in aplicare in paralel.


Codificare entropiei

Encoder entropie exploateaza neoformitatea a distributiei de probabilitate a indicilor de cuantificare simboluri) pentru a genera fluxul de biti mai scurt reprezinta o secventa data de simboluri. Acest lucru se realizeaza prin atribuirea mai mari cuvinte de cod simboluri mai putin probabil si a cadrului teoretic de a face acest lucru este asa-numita teorie informatii .
Premisa fundamentala a teoriei informatiei este ca generarea de informatii poate fi modelat ca un proces probabilistic care pot fi masurate, astfel incat valoarea masurii este de acord cu intuitia noastra. In acest fel, un eveniment E aleatoare cu probabilitatea P E) se spune sa contina unitati de informatii. In cazul in care baza logaritmului este de 2, aceasta informatie este masurata in biti.

Retineti ca, in cazul in care P E) = 1 sau P E) = 0, evenimentul nu contine nicio informatie I E) = 0), si anume, in cazul in care evenimentul este sigur sa se intample sau imposibil, informatiile sale asociat este null. Mai mult decat atat, in cazul in care P E) = 0,5, informatiile transmise de catre evenimentului este maxima si egala cu 1 bit.
Sa ne gandim acum la un X sursa de evenimente statistic independente simb olurile) cu probabilitatile asociate .
  Entropia masoara incertitudinea de sursa, si anume, este mai mare entropia, cu atat mai incert sursa si, prin urmare, mai multe informatii pe care le transmite. Acesta poate fi dovedit ca, pentru o sursa de simboluri equiprobable entropia este maxima, si anume, in cazul in care toate simbolurile au aceeasi probabilitate de aparitie, incertitudinea cu privire la care simbolul va fi produs de sursa este maximal (capacul si Thomas .
 Teorema prima lui Shannon teorema silentioase codare) asigura ca entropia unui sursa este cel mai mic legat de numarul mediu de biti necesar pentru codul de simbolurile produs de sursa. Prin urmare, nici un programator poate produce cuvinte a caror cod de lungime medie este mai mica decat entropia sursei.Diferenta dintre lungimea medie a atins si entropia sursei este numit de concediere a unui cod. Acesta poate fi demonstrat (capacul si Thomas 1991) ca pentru o sursa care genereaza simboluri independente (asa-numita zero memorie sursa) cu entropie H (X), este posibil de a gasi un cod a carui lungime medie este R
In plus, astfel de coduri indeplinesc conditia asa-numita prefix, de exemplu, nici un cuvant de cod este un prefix de orice cuvant alt cod din set.

Aceasta este o proprietate foarte relevante dintr-un cod, deoarece nu exista simboluri suplimentare sunt necesare in fluxul de a marca separarea dintre codurile.
Mai multe coduri au fost propuse in literatura de specialitate pentru a genera un set de cuvinte-cod, care indeplinesc conditia precedenta. Dintre acestea, codurile Huffman sunt cele mai populare. Codurile Huffman furnizati un cod optim in temeiul
constrangere care simbolurile sunt codificate o la un moment dat.

Codurilor Huffman necesita cunostinte anterioare a functiei densitatii de probabilitate a source.8 algoritmul pentru construirea unui cod Huffman are doua etape principale. In prima etapa, o serie de reduceri de sursa este creat prin combinarea celor doua simboluri cu cea mai mica probabilitate intr-un simbol unic.
Acest simbol compus si a probabilitatii asociate sunt utilizate intr-un nou repetare a procesului de reducerea la sursa, cum este ilustrat in Fig. 8.9.
Procesul se repeta pana cand un simbol compus unic care reprezinta sursa completa se obtine. In a doua etapa, fiecare sursa de redusa este codat, incepand de la cele mai mici sursa (o sursa cu doar doua simboluri:
in exemplul din Fig. 8.9, simbolul A1 si simbolul compus
care reprezinta o combinatie de simboluri ramase versiunea originala: a2 A8). Cuvintele Codul de 0 si 1 sunt arbitrar atribuite la fiecare dintre cele doua simboluri. Aceste cuvinte cod propaga ca prefixe la cele doua simboluri care au fost folosite pentru a crea simbolul compus, iar procesul este iterate
la fiecare ramura a arborelui.

In exemplul din fig. 8.9, complet Huffman Codul sursa pentru date este prezentat. Retineti ca entropia sursei este H (X) = 2.48 biti, in timp ce lungimea medie este de R = 2.55 biti (si, prin urmare, de concediere este de numai 0.07 biti).

MATLAB dovada de concept

In aceasta sectiune, vom ilustra principalele concepte din spatele standardul JPEG. Aceste concepte sunt aplicate in compresie video, precum si in abordarea asa-numitu hibrid, care este baza pentru standardele, cum ar fi MPEG1 sau MPEG2 si, prin urmare, aceste concepte vor fi reevaluate in Capitolul 9. Retineti ca, in aceste doua capitole, nu vom concentra pe specificul de oricare dintre aceste standarde, dar pe instrumente comune, generice si concepte pe care le utilizeaza. Mai mult decat atat, in scopul de a ilustra aceste concepte, vom lucra in principal cu imagini nivelul de gri si sa explice extensiile care ar trebui sa fie introduse in sistemele propuse pentru a lucra cu imagini color.
Sa incepem prin citirea unei imagini la nivel gri. In cazul nostru, aceasta este prima imagine a unei secvente video care, in acest capitol vom folosi ca un exemplu pentru a studia cazul in continuare izolate), imaginea de codificare si de exploatare aspatiale concediere. Mai mult decat atat, in capitolul 9, acesta va fi folosit ca punct initial pentru studiul de codare secventa video si de exploatare a ambelor concedierile spatiala si temporala.