Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE




loading...



AnimaleArta culturaDivertismentFilmJurnalismMuzica
PescuitPicturaVersuri

Compresia imaginilor statice - probleme rezolvate

diverse

+ Font mai mare | - Font mai mic








DOCUMENTE SIMILARE

Trimite pe Messenger
ADEVERINTA MEDICALA STAMPIATA
O zi de vara ( compunere)
NUME SI SEMNIFICATIA NUMELOR
EXPRESII CELEBRE (din limba engleza)
ROTARY INTERNATIONAL - Lumea Rotariana
DETECTIE ANTIEFRACTIE INTERIOR
Proiect - Instalatie de concentrare cu triplu efect si termocompresie destinata obtinerii sucului de mere concentrat
PROIECT Tehnician poligraf PROIECTAREA REALIZARII UNOR ETICHETE AUTOADEZIVE PE HARTIE IN ROLA
Depunerea laser pulsata
Presupozitii si tematizari antropologice in filosofie

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: a1, a­2, a3, a4, astfel incat primului simbol i se aloca initial intervalul [0; probabilitatea emisiei lui a1), celui de-al doilea simbol i se aloca initial intervalul imediat urmator, adica, [probabilitatea emisiei lui a1; probabilitatea emisiei lui a1+ probabilitatea emisiei lui a2), celui de-al treilea simbol i se aloca initial intervalul urmator avand latimea egala cu probabilitatea de emisie a lui a3, adica, [probabilitatea emisiei lui a1+probabilitatea emisiei lui a2; probabilitatea emisiei lui a1+ probabilitatea emisiei lui a2+ probabilitatea emisiei lui a3), si in fine, celui de-al patrulea simbol i se aloca ultimul sub-interval ramas, [probabilitatea emisiei lui a1+probabilitatea emisiei lui a2+probabilitatea emisiei lui a3;1).

Astfel, intervalele initial alocate celor patru simboluri vor fi:

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

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

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

Pentru a4 (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 a1=170, a2=85, a3=0 si a4=255, se descrie ca secventa de simboluri emisa [a1 a1 a3 a3], in aceasta ordine. Atunci, la emisia simbolului a1, se considera ca se transmite de fapt mai departe orice numar din intervalul initial alocat lui a­1, 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 [pmin, pMax) [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:

p1=0.5 – probabilitatea de aparitie a simbolului a1 (nivelului de gri 170);

p2=0.3 – probabilitatea de aparitie a simbolului a2 (nivelului de gri 85);

p3=0.1 – probabilitatea de aparitie a simbolului a3 (nivelului de gri 0);

p4=0.1 – probabilitatea de aparitie a simbolului a4 (nivelului de gri 255).

Atunci, latimea fiecarui interval alocat unui simbol ai este data de (p­Max-pmin)∙pi, i=1,2,3,4. Observam ca in cazul initial, pMax­=1 si pmin=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 pmin ca limita inferioara a sub-intervalului alocat lui a1 la pasul curent, si ajungand la pMax ca limita superioara a sub-intervalului alocat ultimului simbol (in cazul nostru a4) la pasul curent. Atunci, la un pas de emisie oarecare, descris prin intervalul de divizat [pmin, p­Max), avem urmatoarele sub-intervale pentru cele patru simboluri ale sursei:

Pentru a1: intervalul [pmin;pmin+(pMax-pmin) ∙p1);

Pentru a2: intervalul [pmin+(pMax-pmin) ∙p1; pmin+(pMax-pmin) ∙(p1+p2));

Pentru a3: intervalul [pmin+(pMax-pmin) ∙(p1+p2); pmin+(pMax-pmin) ∙(p1+p2+p3));

Pentru a4: intervalul [pmin pMax-pmin) ∙(p1+p2+p3); pmin+(pMax-pmin) ∙(p1+p2+p3+p4)), dar cum p1+p2+p3+p4=1, rezulta intervalul [pmin+(pMax-pmin) ∙(p1+p2+p3); pMax).

Atunci, daca primul simbol din secventa emisa de sursa considerata este a1 (=nivelul de gri 170), la emiterea celui de-al doilea simbol al secventei, avem ca interval de divizare inainte de emiterea sa – intervalul [pmin, pMax [0; 0.5). Sub-intervalele alocate simbolurilor ai, 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 a1 (nivelul de gri 170): intervalul [0;0+(0.5-0) )= [0;0.25);

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

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

Pentru a4 (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 a1, adica, se emite intervalul aferent la pasul curent lui a1, care conform calculelor de mai sus, este intervalul [0 ). Acesta devine noul interval de divizat, adica, noul interval [pmin; pMax), din care trebuie alocate noile intervale celor patru simboluri ale sursei, folosind tot ecuatiile anterioare, dar in care inlocuim pmin=0 si pMax=0.25. Sub-intervalele alocate simbolurilor ai, i=1 , la acest pas curent la care urmeaza sa se emita al treilea simbol din secventa vor fi:

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

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



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

Pentru a4 (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 a3 (a treia luminanta a liniei fiind 0). Aceasta inseamna ca selectam ca nou sub-interval [pmin; pMax) – sub-intervalul care a corespuns mai sus simbolului a3, adica, [0.2 ). Acesta devine noul interval de divizat, din care trebuie alocate noile intervale celor patru simboluri ale sursei, folosind ecuatiile anterioare cu pmin=0.2 si pMax=0.225. Sub-intervalele alocate simbolurilor ai, i=1 , la acest pas curent la care urmeaza sa se emita al patrulea simbol din secventa vor fi:

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

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

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

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

In fine, la ultimul pas, se emite din nou simbolul a3 (ultima luminanta de pe linie fiind 0), ceea ce inseamna ca se emite (conform calculelor de mai sus) intervalul curent alocat lui a3, [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.



loading...






Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 810
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2020 . All rights reserved

Distribuie URL

Adauga cod HTML in site