Transformari unitare bidimensionale separabile - in general - Probleme rezolvate

Transformari unitare bidimensionale separabile - in general - Probleme rezolvate

Fie blocul de imagine U de dimensiune 4 4 pixeli de mai jos, care reprezinta o portiune dintr-o imagine tip tabla de sah, in care fiecare pixel este reprezentat prin luminanta sa. Dorim sa aplicam o transformare unitara asupra blocului U astfel incat sa se conserve, in urma transformarii, in totalitate energia blocului, dar in acelasi timp, sa se compacteze intr-un numar mult mai mic de coeficienti nenuli decat numarul coeficientilor nenuli din blocul U reprezentat in domeniul spatial.

a)     Daca matricile transformarilor pe care le avem la dispozitie sunt: matricea transformarii Hadamard unitara ordonata, H₄ 4] ; matricea transformarii cosinus discrete, C₄ 4]; matricea transformarii Fourier discrete unitare, F 4], pe care dintre ele ati alege-o pentru a asigura atat conservarea cat si compactarea energiei? Justificati raspunsul.

b)     Cum arata blocul de imagine V 4] in domeniul transformat, folosind matricea transformarii aleasa? (Se va realiza o transformare bidimensionala a imaginii). Demonstrati conservarea energiei blocului in urma transformarii si estimati compactarea energiei blocului obtinuta prin transformare.

.

;;

Rezolvare:

a) Toate cele trei transformari bidimensionale de imagini: transformarea Hadamard unitara ordonata, transformarea cosinus discreta si transformarea Fourier discreta unitara asigura principiul conservarii energiei, dat fiind ca ele sunt toate reprezentate prin matrici unitare ale transformarilor (conform teoriei, orice transformare unitara bidimensionala garanteaza conservarea energia imaginii in domeniul transformat). Putem verifica faptul ca toate cele matrici ale transformarilor sunt unitare, verificand proprietatile:

In plus, toate cele trei matrici au dimensiunea corespunzatoare aplicarii lor pentru calculul transformarii bidimensionale unitare a blocului de dimensiune 4×4 pixeli, fiind de dimensiune 4×4. Deci, din aceasta perspectiva, oricare din cele trei matrici poate fi folosita pentru transformarea bidimensionala a blocului U, asigurand conservarea energiei in urma transformarii. Singurele criterii de selectie a unei transformari fata de alta raman:

1. eficienta in compactarea energiei (numar minim de coeficienti nenuli in care sa se reprezinte toata energia blocului U in domeniul transformat);

2. eficienta numerica (complexitate minima de calcul a transformarii).

Din punctul de vedere al eficientei numerice, cea mai eficienta pare transformata Hadamard, care necesita doar operatii de adunare si scadere intre luminantele blocului U. Transformata Fourier implica si calcule cu numere complexe, iar transformata cosinus, desi presupune numai calcule cu valori reale, are coeficienti care necesita inmultiri cu doua zecimale (in plus, aproximarile numerice facute prin trunchierea coeficientilor din matricea C₄ la doua zecimale nu garanteaza decat aproximativ conservarea energiei).

Din punctul de vedere al compactarii energiei, observam ca semnalele de pe liniile matricii de luminante U "seamana" perfect ca distributie a luminantelor cu a doua coloana din matricea H₄, iar semnalele de pe coloanele matricii de luminante U "seamana" perfect ca distributie a luminantelor cu ultima linie din matricea H₄ (cu exceptia unei translatari a luminantelor blocului la valori strict pozitive, comparativ cu valorile din matricea H₄ care sunt simetrice fata de zero; este de asteptat ca aceasta translatare sa se reflecte doar intr-un coeficient de curent continuu nenul). In schimb, potrivirea distributiei luminantelor pe liniile blocului U cu coloanele sau liniile matricilor F₄ si C₄ nu este atat de buna. Ca urmare este de asteptat o compactare a energiei mai buna cand se foloseste pentru transformarea bidimensionala unitara separabila a blocului U - matricea transformarii Hadamard ordonate H₄, decat in cazul folosirii celorlate doua transformari.Cea mai slaba compactare este de asteptat in cazul folosirii transformatei cosinus discrete, a carei forma de variatie a coeficientilor difera cel mai mult fata de varianta luminantelor din U (in cazul matricii transformatei Fourier unitare, observam ca a treia linie reda foarte bine forma de variatie a luminantelor pe coloanele lui U, fapt care nu este valabil pentru nici unele din liniile si coloanele matricii transformatei cosinus discrete, C₄).

Obs. Discutia anterioara s-a bazat pe interpretarea transformarilor unitare de imagini din perspectiva capacitatii lor de a descrie imaginile prin descompunerea in suma ponderata de vectori de baza (pentru cazul transformarii unidimensionale), respectiv imagini de baza (pentru cazul transformarii bidimensionale). Cu cat numarul de vectori de baza, respectiv imagini de baza necesare pentru descompunerea imaginii reprezentate spatial in suma liniara ponderata este mai mic, cu atat numarul de ponderi nenule = coeficienti ai transformatei nenuli este mai mic, deci compactarea energiei este mai buna. Spunem asadar ca transformarea optima pentru un bloc de imagine dat (reprezentat spatial prin luminantele sale) este cea care are ca vectori de baza in matricea transformarii, vectori care "se potrivesc" cat mai bine ca forma cu semnalele de pe liniile si respectiv coloanele blocului (distributia/variatia luminantei de pe liniile si coloanele blocului), pentru ca atunci vectorii de baza cei mai potriviti distributiei luminantei pe linii/coloane vor fi suficienti in insumarea ponderata, iar ponderile lor vor fi coeficientii transformatei (singurii nenuli, care trebuie memorati sau transmisi).

In conformitate cu observatiile de mai sus, putem estima ca cea mai convenabila transformare unitara bidimensionala separabila pentru blocul de luminante U de tip "tabla de sah" va fi transformata Hadamard ordonata, descrisa de matricea transformarii H₄ - atat din punctul de vedere al compactarii energiei, cat si din punctul de vedere al complexitatii minime de cacul (asigurand bineinteles si conservarea completa a energiei in domeniul transformat).

Vom verifica afirmatia facuta calculand transformatele directe bidimensionale obtinute cu fiecare din cele trei matrici, pentru blocul U:

A.    Transformata Hadamard bidimensionala ordonata:

Inlocuind numeric, obtinem:

Dupa cum ne asteptam, compactarea energiei este foarte buna; cum liniile din matricea de luminante U se potriveau perfect cu a doua coloana din H₄, iar coloanele din U se potriveau perfect cu a patra linie din H₄, apare un singur coeficient de c.a. nenul in domeniul transformat, pe ultima linie si a doua coloana din blocul V_H de coeficienti ai transformatei Hadamard bidimensionale unitare ordonate a blocului U. In plus, tot de asteptat, mai avem nenul coeficientul de curent continuu (v. comentariile de mai sus asupra componentei continue a blocului U).

B.    Transformata Fourier discreta bidimensionala unitara:

Inlocuind numeric, obtinem:

Asa cum ne asteptam, compactarea energiei nu este atat de buna ca si in cazul transformarii Hadamard ordonate bidimensionale; avem nevoie de doi coeficienti nenuli de c.a. si un coeficient de c.c. pentru reprezentarea blocului in domeniul transformat.

C.    Transformata cosinus discreta bidimensionala:

Inlocuind numeric, obtinem:

Asa cum ne asteptam, compactarea energiei este mai slaba si decat in cazul transformatei Fourier bidimensionale unitare, si cu atat mai mult fata de transformarea Hadamard ordonata bidimensionala; avem nevoie (chiar cu aproximari numerice) de 6 coeficienti de c.a. si de coeficientul de c.c. pentru reprezentarea blocului in domeniul transformat, data fiind potrivirea cea mai slaba intre forma de variatie (de tip salturi dreptunghiulare) a semnalului de luminanta pe liniile si coloanele din blocul U si forma de variatie de tip cosinusoidal a semnalelor pe liniile si coloanele matricii transformatei cosinus discrete C_4­ date in enunt.

Se confirma (prin calcule) observatiile din discutia initiala: cea mai buna alegere pentru blocul U cu variatia de luminanta de tip tabla de sah este transformata Hadamard, capabila sa asigure conservarea energiei, sa impacheteze (compacteze) energia intr-un numar minim de coeficienti si preferata adesea si pentru simplitatea calculelor implicate, in imagini cu astfel de variatie a luminantei.

b) Blocul de imagine V 4] in domeniul transformat, folosind oricare din matricile transformarilor, este calculat la pct. anterior. Conservarea energiei blocului a fost demonstrata indirect; considerand transformarea optima - transformarea Hadamard, si alegand in conformitate matricea transformarii H , putem demonstra si direct pe blocurile U si V V astfel calculate conservarea energiei, calculand energiile celor doua blocuri in parte si demonstrand ca sunt egale:

Cum E_U E_V, avem demonstrata conservarea energiei blocului.

Compactarea energiei blocului obtinuta prin transformare este in doar 2 din totalul de 16 coeficienti, deci avem o compactare a energiei in 12.5% din coeficientii transformatei - maximul de compactare posibila pentru acest bloc de imagine cu matricile transformarilor disponibile.