Transformari sinusoidale - transformata Fourier - Probleme rezolvate

Transformari sinusoidale - transformata Fourier - Probleme rezolvate

1. Fie urmatorul bloc de 4×4 pixeli dintr-o imagine digitala:

a)     Deduceti matricea transformatei Fourier, F[4×4], necesara transformarii bidimensionale a acestui bloc de imagine.

b)     Sa se calculeze transformata Fourier bidimensionala unitara a blocului U.

c)     Cum arata matricea spectrului de amplitudine a transformatei Fourier bidimensionale unitare a blocului U?

d)     Pe matricea transformatei Fourier bidimensionale a blocului U, demonstrati conservarea energiei in domeniul transformat si examinati compactarea energiei in domeniul transformat fata de domeniul original.

Rezolvare:

a)          Ecuatia matricii transformatei Fourier unitare ne furnizeaza modul de calcul a coeficientilor din matricea F pentru orice linie k si coloana n a matricii, k=0, 1, 2, 3 si n=0, 1, 2, 3. Pentru reducerea volumului de calcule de realizat, observam ca matricea transformarii Fourier este simetrica, adica:

(din comutativitatea produsului algebric)

Este suficient atunci sa calculam elementele pana la diagonala principala (inclusiv cele de pe diagonala) pentru a avea matricea transformarii complet cunoscuta. Cu alte cuvinte, trebuie sa calculam termenii:

Pentru k=0, indiferent de valoarea lui n, produsul algebric kn=0, deci avem pentru N=4, obtinem

Pentru k=1, obtinem pentru cele trei elemente (n=1 sau 3):

Pentru k=2, obtinem pentru cele doua elemente (n=2 sau 3):

In fine, pentru k=3, obtinem f(3,3):

Ca urmare, elementele matricii transformarii Fourier unitare sunt:

b)          Transformata Fourier bidimensionala unitara a blocului U se poate calcula folosind expresia generala a transformarilor bidimensionale unitare de imagini in forma matriciala, tinand cont de faptul ca blocul de pixeli este o matrice patratica de dimensiune 4×4 pixeli si folosind ca matrice a transformarii - matricea F, corespunzatoare transformatei Fourier. In aceste conditii, formula de calcul a transformatei Fourier bidimensionale unitare a blocului (care conduce la blocul transformat V[4×4] de coeficienti Fourier) este:

.

Cum matricea transformarii Fourier, F, este simetrica, F^T=F, deci ecuatia de calcul a transformatei directe devine:

Inlocuind cu valorile din matricile F si U, obtinem:

c)          Matricea spectrului de amplitudine a transformatei Fourier bidimensionale unitare a blocului U este data de modulele coeficientilor din blocul V, notat aici simbolic prin |V|[4×4]. Reamintim ca modulul unui numar complex z de forma:

,

este dat de expresia:

Atunci matricea care reprezinta spectrul de amplitudine a transformatei Fourier bidimensionale unitare a blocului de imagine U va contine coeficientii:

.

Observam ca in spectrul de amplitudine al transformatei Fourier bidimensionale unitare a blocului, avem coeficienti nenuli doar pe prima linie, care corespunde unor frecvente spatiale orizontale nenule (frecventele spatiale verticale fiind zero, fapt explicabil daca examinam variatia luminantei pe fiecare coloana din blocul U: luminanta este constanta pe fiecare dintre coloanele din blocul U, ca urmare nu exista deloc tranzitii de luminanta in directie verticala, deci nici coeficienti de frecventa corespunzatori pe liniile a doua, treia si a patra din blocul V si din spectrul de amplitunine |V|, doar pe prima linie care corespunde unor frecvente spatiale orizontale nenule dar frecvente verticale zero). Daca forma tranzitiei luminantei pe fiecare linie in parte din blocul U ar fi fost de forma unui semnal sinusoidal sau portiuni de sinusoida, am fi obtinut un singur coeficient nenul, corespunzator frecventei orizontale a sinusoidei date de una din liniile matricii transformatei Fourier. Cum acesta nu a fost cazul, a fost necesara utilizarea tuturor coeficientilor Fourier de pe prima linie (de frecventa orizontala nenula si frecventa verticala zero) pentru descrierea completa, fara pierdere de informatie, a blocului U.

d)          Conservarea energiei blocului U in reprezentarea sa prin coeficientii transformatei sale Fourier bidimensionale, V, poate fi demonstrata fie indirect folosind proprietatile transformarilor ortogonale bidimensionale unitare, fie direct prin calculul energiilor din blocul U, notata prin E_U, respectiv din blocul V, notata prin E_V, si verificarea egalitatii celor doua energii. Daca cele doua energii sunt egale, evident concluzia este ca in urma transformarii Fourier bidimensionale unitare a blocului U, se conserva energia blocului U in reprezentarea sa in domeniul transformat.

In general, energia unui bloc de imagine se calculeaza ca suma patratelor valorilor luminantelor din bloc, iar energia blocului transformat - ca suma patratelor modulelor coeficientilor. Ca urmare, putem calcula energia E_U in blocul de imagine original si energia E_V in blocul de imagine reprezentat in domeniul transformat cu ecuatiile:

unde u(m,n) = luminanta pixelului de pe linia m si coloana n din blocul U, respectiv:

unde v(k,l) = valoarea coeficientului de pe linia k si coloana l din blocul transformat V.

Numeric, calculam:

Ca urmare , deci se conserva energia blocului in urma transformarii (transformarea este cu conservare a energiei, ceea ce ne indica faptul ca putem reconstitui oricand - prin transformare inversa - fara distorsiuni, blocul original de pixeli din reprezentarea sa in domeniul transformat).

Compactarea energiei blocului in domeniul transformat, in comparatie cu distributia energiei blocului in domeniul original, este data de numarul de coeficienti nuli sau foarte mici in comparatie cu coeficientii din blocul original. In blocul original, nu avem nici un coeficient nul, ca urmare putem estima energia necompactata deloc (ci distribuita relativ uniform intre cei 16 termeni). Daca examinam blocul V, observam ca doar patru coeficienti sunt nenuli. Ca urmare, energia este compactata in domeniul transformat in 4 din totalul de 16 coeficienti ai blocului. Avem o compactare a energiei in 4/16 din coeficienti, adica in 25% din coeficienti - deci putem spune ca transformarea a fost destul de eficienta din perspectiva compactarii energiei blocului (nu foarte eficienta - eficienta maxima atingandu-se atunci cand am avea un numar minim de coeficienti nenuli - un singur coeficient, adica, dar totusi destul de eficienta, dat fiind ca 75% din coeficienti nu mai trebuie stocati/transmisi).

2. Fie blocul U de 4×4 pixeli dintr-o imagine digitala, in care fiecare pixel este reprezentat prin luminanta sa - o valoare intreaga in multimea :

a)            Calculati transformata Fourier bidimensionala unitara a blocului, folosind matricea transformatei Fourier unitare de dimensiune 4×4:

F=.

b)            Calculati spectrul de amplitudine al blocului. Ce valori au: coeficientul de c.c.; coeficientii de c.a. introdusi de muchiile orizontale din bloc; coeficientii de c.a. introdusi de muchiile verticale din bloc? Ce alti coeficienti de c.a. apar, si cum explicati prezenta lor?

c)            Proiectati o masca de coeficienti G sub forma unei matrici de 4 linii si 4 coloane, cu ajutorul careia sa realizati o filtrare a blocului in domeniul frecventa, astfel incat in urma filtrarii sa se pastreze in bloc doar muchiile verticale, eliminand cu totul celelalte detalii din bloc si componenta continua (coeficientul de curent continuu). Operatia de filtrare cu masca G in domeniul coeficientilor transformatei Fourier bidimensionale unitare a imaginii va fi considerata a fi definita de ecuatia:

unde:

elementul de pe linia k si coloana l din matricea de coeficienti a blocului filtrat in domeniul transformatei Fourier bidimensionale, V_f

elementul de pe linia k si coloana l din matricea G

elementul de pe linia k si coloana l din matricea de coeficienti a transformatei Fourier bidimensionale a blocului U[ , notat prin V

Rezolvare:

a)          Transformata Fourier bidimensionala unitara a blocului U se poate calcula folosind expresia generala a transformarilor bidimensionale unitare de imagini in forma matriciala, tinand cont de faptul ca blocul de pixeli este o matrice patratica de dimensiune 4×4 pixeli si folosind ca matrice a transformarii - matricea F, corespunzatoare transformatei Fourier. Cum matricea transformarii Fourier, F, este simetrica, F^T=F, ecuatia de calcul a transformatei directe bidimensionale unitare a blocului (care conduce la blocul transformat V[4×4] de coeficienti Fourier) este:

Inlocuind cu valorile numerice din matricile F si U, obtinem:

Se poate observa ca, datorita distributiei luminantelor din blocul U, care "nu se potriveste" prea bine cu forma si faza functiilor de baza din matricea F (imaginati-va functiile din matricea F - pe linii respectiv pe coloane - reprezentate ca si functii 1-D, respectiv similar, liniile si coloanele U reprezentate ca functii 1-D), compactarea energiei blocului in urma reprezentarii sale in domeniul transformat nu este prea buna (avem doar 4 coeficienti nuli in domeniul transformat din totalul de 16), dar totusi, o cantitate mai mare din energia imaginii este impachetata in coeficientii de pe prima coloana (prima, a doua si a patra linie), corespunzator luminantei medii a blocului si unui numar mai mare de tranzitii de luminanta pe coloane decat pe liniile blocului (avem trei tranzitii de luminanta pe coloane si doar doua tranzitii de luminanta pe linii in blocul U).

b) Spectrul de amplitudine al blocului este dat de matricea care contine modulele coeficientilor transformatei Fourier bidimensionale unitare a blocului, matrice notata, ca si in problema anterioara, prin |V 4×4]. Coeficientii fiind numere complexe, modulul lor este calculat ca radical din suma patratelor partii reale si partii imaginare, ceea ce conduce la urmatoarele valori numerice in spectrul de amplitudine al blocului:

Coeficientul de c.c. al blocului este cel care corespunde frecventelor spatiale zero, adica, coeficientul din spectrul de amplitudine de pe prima linie si prima coloana a blocului. El corespunde unei medieri a luminantelor din bloc, fiind obtinut prin inmultirea cu linia de valori 1 si coloana de valori 1 din matricea F. Valoarea coeficientului de c.c. este de 35∙14=490. Daca examinam aceasta valoare prin comparatie cu media luminantelor din blocul de pixeli U, observam ca este de 4 ori mai mare decat luminanta medie (luminanta medie fiind (10∙70+6∙210)/16=1960/16=122.5, adica, 490/4). Faptul ca valoarea coeficientului de c.c. este de 4 ori mai mare decat luminanta medie a blocului original de pixeli U se datoreaza folosirii transformatei Fourier bidimensionale unitare, in care coeficientul cu care se multiplica matricea transformarii folosite in calculul transformatei directe este , si nu ca in transformata Fourier "uzuala" (dar neunitara) (ca urmare, si factorul prin care se impart coeficientii este (1/2)∙ (1/2), in loc de (1/4) ∙ (1/4), deci de 4 ori mai mic).

Coeficientii de c.a. introdusi de muchiile orizontale din bloc: muchiile orizontale sunt descrise de tranzitiile de luminanta pe coloanele blocului U, care apar "aliniate" pe linii, adica, apar pe exact aceeasi pozitie a liniei din blocul U, pe coloane succesive. Ca urmare, o muchie orizontala va corespunde unor frecvente spatiale verticale nenule si frecvente spatiale orizontale nule (va introduce in spectrul de amplitudine, coeficienti nenuli pe prima coloana din blocul spectrului de amplitudine - de frecventa spatiala orizontala zero - si pe liniile a doua, a treia si/sau a patra din blocul spectrului de amplitudine, linii care corespund unor frecvente verticale nenule). Coeficientii de c.a. care descriu muchiile orizontale (in cazul nostru, singura muchie orizontala, dintre primele doua si ultimele doua linii ale blocului U, aparuta in dreptul ultimelor trei coloane ale blocului U) sunt cei de pe prima coloana din blocul |V|, de pe a doua si a patra pozitie a acestei coloane: , pe fiecare din cele doua pozitii.

Coeficientii de c.a. introdusi de muchiile veticale din bloc: muchiile verticale sunt descrise de tranzitiile de luminanta pe liniile blocului U, care apar "aliniate" pe coloane, adica, apar pe exact aceeasi pozitie a coloanei din blocul U, pe linii succesive. Ca urmare, o muchie verticala va corespunde unor frecvente spatiale orizontale nenule si frecvente spatiale verticale nule (va introduce in spectrul de amplitudine, coeficienti nenuli pe prima linie din blocul spectrului de amplitudine - de frecventa spatiala verticala zero - si pe coloanele a doua, a treia si/sau a patra din blocul spectrului de amplitudine, coloane care corespund unor frecvente orizontale nenule). Coeficientii de c.a. care descriu muchiile verticale (in cazul nostru, singura muchie verticala, dintre prima coloana si a doua coloana ale blocului U, aparuta in dreptul primelor doua linii ale blocului U) sunt cei de pe prima linie din blocul |V|, de pe ultimele trei pozitii de pe linie: 2, pe fiecare din cele trei pozitii.

Pe langa coeficientii de c.a. introdusi de muchiile orizontale si verticale din blocul de luminante U, mai avem un set de coeficienti de c.a. corespunzatori unor frecvente spatiale orizontale si verticale simultan nenule, si anume, coeficientii de c.a. din blocul spectrului de amplitudine de pe a doua linie si coloanele a doua, treia si a patra, respectiv de pe ultima linie si coloanele a doua, treia si a patra (coeficienti care au toti aceeasi valoare numerica ). Ei pot fi explicati prin prezenta coltului de la intersectia celei de a doua linii si a doua coloane din blocul de luminante U (care corespunde unor frecvente spatiale orizontale si verticale simultan nenule).

c) Daca dorim sa proiectam o masca G care, inmultita element cu element cu transformata Fourier bidimensionala unitara V a blocului de pixeli U, sa conduca la o noua imagine filtrata (a carei transformata Fourier unitara bidimensionala va fi V_f), U_f[4×4], in care sa fie prezente doar muchiile verticale care apareau in blocul U, dar sa dispara muchiile orizontale si coltul, iar componenta de curent continuu sa fie nula, atunci inseamna ca va trebui sa eliminam toti coeficientii de c.a. din blocul V care reflecta muchiile orizontale si orice alte detalii de frecvente spatiale orizontala si verticala simultan nenule, si sa eliminam deasemenea coeficientul de c.c. Cum elementele din masca G joaca rol de ponderi de multiplicare element cu element cu matricea transformatei Fourier bidimensionale, pentru eliminarea coeficientilor nedoriti, trebuie ca elementele de pe pozitiile corespunzatoare din masca G sa aiba valoarea 0 (dand ca rezultat al produsului algebric - 0), iar coeficientii de c.a. care dorim sa ramana in imaginea filtrata reprezentata in domeniul transformatei Fourier bidimensionale unitare trebuie sa aiba ca si coeficienti corespunzatori - valori 1 in masca G.

Pentru a pastra muchiile verticale (in cazul nostru, muchia verticala) din blocul original U in exact aceeasi pozitie spatiala (intre prima si a doua coloana din U), trebuie sa pastram nemodificati toti coeficientii de c.a. responsabili de reprezentarea acestei muchii, adica, toti coeficientii de frecventa verticala nula si orizontala nenula - cei de pe prima linie din blocul transformatei Fourier bidimensionale unitare V, de pe coloanele a doua, treia si a patra din V. Bineinteles, eliminarea tuturor celorlalte tranzitii de luminanta va face ca muchia verticala sa se extinda, in blocul filtrat refacut prin transformata Fourier unitara inversa, pe toate cele 4 linii ale blocului (de sus pana jos in bloc).

Masca G care satisface conditiile de mai sus va avea coeficientii:

Rezultatul filtrarii, in conformitate cu ecuatia data in enunt, va conduce la blocul de coeficienti complecsi in domeniul transformatei Fourier bidimensionale unitare, notat prin V_f, cu elementele v­_f(k,l), k=0,1,2,3, l=0,1,2,3, de mai jos:

Transformarea Fourier bidimensionala unitara inversa a blocului, care ne permite sa verificam prezenta muchiei verticale in blocul filtrat reprezentat in domeniul spatial U_f, este data de ecuatia:

Cum (conform teoriei) matricea F este unitara si simetrica, ea satisface relatia:

Ca urmare, formula transformatei Fourier bidimensionale unitare inverse a blocului filtrat (in exprimare matriciala) devine:

unde F^* este matricea complex conjugata a matricii F, obtinuta prin conjugarea coeficientilor individuali din F, adica:

.

Inlocuind acum in ecuatia transformarii Fourier bidimensionale unitare inverse expresiile F^* si V_f, obtinem blocul filtrat reprezentat in domeniul spatial, U_f:

Observam ca se confirma, in blocul filtrat reprezentat in domeniul spatial U_f., prezenta unei singure muchii verticale, pe aceeasi pozitie spatiala in care aparea aceasta muchie in blocul U inainte de filtrare, adica, intre prima si a doua coloana. Componenta continua a blocului filtrat este zero, dat fiind ca media aritmetica a valorilor din bloc este zero (12∙17.5-4∙52.5=210-210=0). Ca urmare filtrarea a indeplinit cerintele din enunt.