Compresia imaginilor statice - probleme rezolvate

Compresia imaginilor statice - probleme rezolvate

1. Pentru o clasa de imagini, se aplica cuantizarea uniforma a nivelelor de gri pe 2 biti, astfel incat in orice imagine din aceasta clasa pot fi prezente doar nivelele de gri: 0; 85; 170; 255. Probabilitatile de aparitie ale celor 4 nivele de gri in imaginile din aceasta clasa sunt date in histograma liniara normalizata a nivelelor de gri ale imaginilor din clasa din figura. Se va considera ca cele 4 nivele de gri reprezinta simboluri posibile a fi emise de catre o sursa S, in ordinea descrescatoare a probabilitatilor lor de aparitie: S==. Daca pentru un bloc de imagine U 4] din clasa mentionata, prima linie din bloc este: , sa se codeze aceasta linie ca secventa emisa de sursa S folosind codarea aritmetica.

Rezolvare:

Codarea aritmetica presupune o codare a secventei emise de sursa printr-un singur cuvant de cod, intr-un sub-interval al intervalului probabilistic [0 ]. Deducerea intervalului din care se alege numarul care va coda secventa se realizeaza intr-o procedura iterativa de mapare a simbolurilor in sub-intervale din [0 ] gasite prin divizarea succesiva a sub-intervalelor folosite pentru reprezentarea simbolurilor sursei, la fiecare pas de transmisie a unui simbol.

Pasul initial al codarii presupune asignarea de intervale (sub-intervale ale lui [0;1]) fiecarui dintre simbolurile posibile a fi emise de sursa, in ordinea considerata pentru ele in dictionarul sursei: a₁, a₂, a₃, a₄, astfel incat primului simbol i se aloca initial intervalul [0; probabilitatea emisiei lui a₁), celui de-al doilea simbol i se aloca initial intervalul imediat urmator, adica, [probabilitatea emisiei lui a₁; probabilitatea emisiei lui a₁+ probabilitatea emisiei lui a₂), celui de-al treilea simbol i se aloca initial intervalul urmator avand latimea egala cu probabilitatea de emisie a lui a₃, adica, [probabilitatea emisiei lui a₁+probabilitatea emisiei lui a₂; probabilitatea emisiei lui a₁+ probabilitatea emisiei lui a₂+ probabilitatea emisiei lui a₃), si in fine, celui de-al patrulea simbol i se aloca ultimul sub-interval ramas, [probabilitatea emisiei lui a₁+probabilitatea emisiei lui a₂+probabilitatea emisiei lui a₃;1).

Astfel, intervalele initial alocate celor patru simboluri vor fi:

Pentru a₁ (nivelul de gri 170): intervalul [0;0.5);

Pentru a₂ (nivelul de gri 85): intervalul [0.5;0.5+0.3)= [0.5;0.8);

Pentru a₃ (nivelul de gri 0): intervalul [0.5+0.3;0.5+0.3+0.1)= [0.8;0.9);

Pentru a₄ (nivelul de gri 255): intervalul [0.5+0.3+0.1 )= [0.9;1).

Dupa initializare, incepe analiza secventei de codat (secventei emise de sursa). In cazul nostru, aceasta secventa este vectorul , de patru simboluri, care cu notatiile a₁=170, a₂=85, a₃=0 si a₄=255, se descrie ca secventa de simboluri emisa [a₁ a₁ a₃ a₃], in aceasta ordine. Atunci, la emisia simbolului a₁, se considera ca se transmite de fapt mai departe orice numar din intervalul initial alocat lui a₁, adica, din [0;0.5). Acest interval devine "intervalul de referinta" pentru pasul urmator de emisie, adica, din intervalul [0;0.5), se "aloca" noi sub-intervale simbolurilor ale sursei, dupa acelasi formalism ca la alocarea initiala, proportional cu probabilitatile simbolurilor, tinand cont insa la alocare ca valoarea minima posibila este limita inferioara a intervalului corespunzator primului simbol emis (in cazul nostru - 0), iar valoarea maxima posibila este limita superioara a intervalului corespunzator primului simbol emis (in cazul nostru - 0.5).

Pentru calculul practic al intervalelor alocate simbolurilor la fiecare pas, putem nota intervalul de divizare rezultat total disponibil de la pasul anterior prin [p_min, p_Max) [0;1), si putem spune ca intervalele de alocat simbolurilor individuale sunt proportionale ca latime cu probabilitatile de aparitie ale acestor simboluri. Vom nota prin:

p₁=0.5 - probabilitatea de aparitie a simbolului a₁ (nivelului de gri 170);

p₂=0.3 - probabilitatea de aparitie a simbolului a₂ (nivelului de gri 85);

p₃=0.1 - probabilitatea de aparitie a simbolului a₃ (nivelului de gri 0);

p₄=0.1 - probabilitatea de aparitie a simbolului a₄ (nivelului de gri 255).

Atunci, latimea fiecarui interval alocat unui simbol a_i este data de (p_Max-p_min)∙p_i, i=1,2,3,4. Observam ca in cazul initial, p_Max=1 si p_min=0, obtinem ca si latimi ale intervalelor alocate initial, exact probabilitatile simbolurilor emise de sursa, iar pentru pasii urmatori, aceasta ecuatie ne arata doar ca divizarea intervalului probabilistic curent disponibil se realizeaza proportional cu probabilitatile de aparitie ale simbolurilor individuale.

Intervalele alocate simbolurilor individuale sunt adiacente, iar regula de alocare este totdeauna in ordinea considerata pentru simbolurile sursei, plecand de la p_min ca limita inferioara a sub-intervalului alocat lui a₁ la pasul curent, si ajungand la p_Max ca limita superioara a sub-intervalului alocat ultimului simbol (in cazul nostru a₄) la pasul curent. Atunci, la un pas de emisie oarecare, descris prin intervalul de divizat [p_min, p_Max), avem urmatoarele sub-intervale pentru cele patru simboluri ale sursei:

Pentru a₁: intervalul [p_min;p_min+(p_Max-p_min) ∙p₁);

Pentru a₂: intervalul [p_min+(p_Max-p_min) ∙p₁; p_min+(p_Max-p_min) ∙(p₁+p₂));

Pentru a₃: intervalul [p_min+(p_Max-p_min) ∙(p₁+p₂); p_min+(p_Max-p_min) ∙(p₁+p₂+p₃));

Pentru a₄: intervalul [p_min p_Max-p_min) ∙(p₁+p₂+p₃); p_min+(p_Max-p_min) ∙(p₁+p₂+p₃+p₄)), dar cum p₁+p₂+p₃+p₄=1, rezulta intervalul [p_min+(p_Max-p_min) ∙(p₁+p₂+p₃); p_Max).

Atunci, daca primul simbol din secventa emisa de sursa considerata este a₁ (=nivelul de gri 170), la emiterea celui de-al doilea simbol al secventei, avem ca interval de divizare inainte de emiterea sa - intervalul [p_min, p_Max [0; 0.5). Sub-intervalele alocate simbolurilor a_i, i=1 , la acest pas curent la care urmeaza sa se emita al doilea simbol din secventa se calculeaza cu formulele de mai sus si vor fi:

Pentru a₁ (nivelul de gri 170): intervalul [0;0+(0.5-0) )= [0;0.25);

Pentru a₂ (nivelul de gri 85): intervalul [0.25;0+(0.5-0) ) = [0.25;0.4);

Pentru a₃ (nivelul de gri 0): intervalul [0.4;0+(0.5-0) )= [0.4;0.45);

Pentru a₄ (nivelul de gri 255): intervalul [0.45; (0.5-0 )= [0.45;0.5).

La acest moment de timp curent, se emite mai departe din nou simbolul a₁, adica, se emite intervalul aferent la pasul curent lui a₁, care conform calculelor de mai sus, este intervalul [0 ). Acesta devine noul interval de divizat, adica, noul interval [p_min; p_Max), din care trebuie alocate noile intervale celor patru simboluri ale sursei, folosind tot ecuatiile anterioare, dar in care inlocuim p_min=0 si p_Max=0.25. Sub-intervalele alocate simbolurilor a_i, i=1 , la acest pas curent la care urmeaza sa se emita al treilea simbol din secventa vor fi:

Pentru a₁ (nivelul de gri 170): intervalul [0;0+(0.25-0) )= [0;0.125);

Pentru a₂ (nivelul de gri 85): intervalul [0.125;0+(0.25-0) ) = [0.125;0.2);

Pentru a₃ (nivelul de gri 0): intervalul [0.2;0+(0.25-0) )= [0.2;0.225);

Pentru a₄ (nivelul de gri 255): intervalul [0.225 ).

Plecand de la aceste noi sub-intervale alocate, se emite in continuare al treilea simbol din secventa (a treia luminanta a liniei), adica, simbolul a₃ (a treia luminanta a liniei fiind 0). Aceasta inseamna ca selectam ca nou sub-interval [p_min; p_Max) - sub-intervalul care a corespuns mai sus simbolului a₃, adica, [0.2 ). Acesta devine noul interval de divizat, din care trebuie alocate noile intervale celor patru simboluri ale sursei, folosind ecuatiile anterioare cu p_min=0.2 si p_Max=0.225. Sub-intervalele alocate simbolurilor a_i, i=1 , la acest pas curent la care urmeaza sa se emita al patrulea simbol din secventa vor fi:

Pentru a₁ (nivelul de gri 170): intervalul [0.2;0.2+(0.225-0.2) )= [0.2;0.2125);

Pentru a₂ (nivelul de gri 85): intervalul [0.2125;0.2+(0.225-0.2) ) = [0.2125;0.22);

Pentru a₃ (nivelul de gri 0): intervalul [0.22;0.2+(0.225-0.2) )= [0.22;0.2225);

Pentru a₄ (nivelul de gri 255): intervalul [0.2225 ).

In fine, la ultimul pas, se emite din nou simbolul a₃ (ultima luminanta de pe linie fiind 0), ceea ce inseamna ca se emite (conform calculelor de mai sus) intervalul curent alocat lui a₃, [0.22 ). Ca urmare, codul secventei emise de sursa va fi orice numar in intervalul [0.22 ). Uzual, se alege o valoare din mijlocul intervalului (pentru o margine de zgomot cat mai buna - adica pentru insensibilitate la perturbatii, astfel incat si daca apare o perturbatie asupra codului, el sa ramana in acelasi interval), si daca este posibil, cu un numar minim de zecimale (pentru o reprezentare prin cat mai putini biti); o valoare care satisface ambele cerinte va fi reprezentata cu 4 zecimale, iar media aritmetica a intervalului nostru este (0.22+0.2225)/2=0.22125, deci am putea alege 0.221 sau 0.222.

Reprezentarea grafica a algoritmului de codare aritmetica este redata in urmatoarea figura.

Fie urmatoarea linie dintr-o imagine digitala pe nivele de gri:

Dorim sa codam aceasta linie de imagine (mai putin primul pixel, u(0)=100) folosind modulatia delta, avand la dispozitie un cuantizor pe 1 bit cu nivelele de cuantizare:

si functia de transfer:

Se considera reprezentarea valorilor de codat prin sirul de luminante = . Daca valoarea decodata reconstruita a primului esantion, , calculati:

a) sirul erorilor de predictie , n=1,2,,7;

b) sirul erorilor de predictie cuantizate , n=1,2,,7;

c) linia din imagine reconstruita la decodor.

Rezolvare:

Modulatia delta este cea mai simpla tehnica de codare DPCM, care presupune existenta unui predictor de 1 tact si a unui cuantizor de 1 bit.

Pentru a putea determina sirul erorilor de predictie, al erorilor de predictie cuantizate si linia din imagine reconstruita la decodor, este nevoie sa cunoastem si sa urmam pasii (ecuatiile) algoritmului de codare si apoi, de decodare folositi in modulatia delta.

Ecuatiile codorului prin modulatie delta a unui sir de esantioane (in cazul nostru, sirul este format din luminantele liniei) sunt:

Predictia valorii esantionului urmator:

, n=1,2,,7,

unde prin notam valoarea prezisa a esantionului n, iar prin - valoarea decodata (reconstruita la decodor) a esantionului n-1.

Calculul erorii de predictie:

, n=1,2,,7

Cuantizarea erorii de predictie in vederea transmisiei sale:

, n=1,2,,7.

Ecuatia decodorului prin modulatie delta a sirului de esantioane (in cazul nostru, sirului format din luminantele liniei) sunt:

Predictia valorii esantionului care trebuie reconstruit, pe baza esantioanelor reconstruite anterioare:

, n=1,2,,7,

cu aceleasi notatii de la pasul 1 al codorului.

Calculul valorii decodate (reconstruite) a esantionului n, prin insumarea predictiei sale cu valoarea erorii de predictie cuantizate (singura disponibila la decodor, deoarece valoarea dinainte de cuantizare nu este cunoscuta decat la codor; ca urmare ceea ce se obtine este doar o aproximare a lui u(n) original):

, n=1,2,,7.

In enuntul problemei, se da valoarea decodata (reconstruita) a primei luminante a liniei (esantionului n=0); aceasta valoare ne va permite sa prezicem a doua luminanta a liniei (esantionul u(1)) si sa determinam si eroarea de predictie pentru acest esantion, e(1). Celelalte valori vor rezulta urmand pasii de codare si decodare de mai sus, in conformitate cu calculele urmatoare:

Pentru n=1:

o       la codare:

prezicem

calculam eroarea de predictie:

cuantizam eroarea de predictie: e(1)>0 => .

o       la decodare:

prezicem

reconstruim

Pentru n=2:

o       la codare:

prezicem

calculam eroarea de predictie:

cuantizam eroarea de predictie: e(2)>0 => .

o       la decodare:

prezicem

reconstruim

Pentru n=3:

o       la codare:

prezicem

calculam eroarea de predictie:

cuantizam eroarea de predictie: e(3)>0 => .

o       la decodare:

prezicem

reconstruim

Pentru n=4:

o       la codare:

prezicem

calculam eroarea de predictie:

cuantizam eroarea de predictie: e(4)<0 => .

o       la decodare:

prezicem

reconstruim

Pentru n=5:

o       la codare:

prezicem

calculam eroarea de predictie:

cuantizam eroarea de predictie: e(5)<0 => .

o       la decodare:

prezicem

reconstruim

Pentru n=6:

o       la codare:

prezicem

calculam eroarea de predictie:

cuantizam eroarea de predictie: e(6)<0 => .

o       la decodare:

prezicem

reconstruim

Pentru n=7:

o       la codare:

prezicem

calculam eroarea de predictie:

cuantizam eroarea de predictie: e(7)<0 => .

o       la decodare:

prezicem

reconstruim

Ca si rezultat al calculelor, avem disponibile direct rezultatele cerute prin enuntul problemei:

a)      sirul erorilor de predictie , n=1,2,,7:

e(1)=25; e(2)=20; e(3)=13; e(4)=-66; e(5)=-51; e(6)=-36; e(7)=-21

=> sirul .

b)      sirul erorilor de predictie cuantizate , n=1,2,,7:

; ; ; ; ; ; .

=> sirul .

c)      linia din imagine reconstruita la decodor:

Inlocuind cu valorile refacute la decodor ale esantioanelor, obtinem:

Observam ca linia refacuta la decodor difera fata de cea din imaginea originala (ale carei luminante erau ). In principal, erorile se datoreaza cuantizorului de 1 bit specific modulatiei delta, care face imposibila urmarirea variatiilor mari in semnal, cum este in principal scaderea brusca a luminantei de la 128 la 64. Solutia pentru reducerea erorii ar reprezenta-o o codare DPCM 1-D cu mai multi biti pentru cuantizarea erorii.