Transformata Fourier a imaginilor

Transformata Fourier a imaginilor

Exista mai multe tipuri de transformari ale imaginilor care produc reprezentari in care apar proprietati ale imaginilor nedisponibile in spatiul imaginii. Astfel, transformata Fourier a unei imagini este o reprezentare in domeniul frecventei. Multe prelucrari de imagine presupun eliminarea din imagine a componentelor de o anumita frecventa, de exemplu cele de nivel coborat sau cele de nivel inalt. Aceste operatii sunt usor de realizat pe transformata Fourier a imaginii.

O prelucrare de imagine bazata pe transformata Fourier are loc in trei pasi:

Se calculeaza transformata Fourier a imaginii

Se proceseaza reprezentarea in domeniul Fourier

Se calculeaza transformata Fourier inversa, obtinandu-se imaginea prelucrata

Transformata Fourier a unei imagini I(x,y) este:

F(u,v)= I(x,y) exp -j2p(ux + vy) dxdy

iar inversa transformarii:

I(x,y)= F(u,v) exp j2p(ux+vy) dudv

Domeniul Fourier este complex si poate fi reprezentat ca:

F(u,v)=Real(u,v) + j Imag(u,v)

In prelucrarea imaginilor se folosesc amplitudinea si faza:

|F(u,v)|= (Real(u,v)² + Imag(u,v)²)^1/2

_{Φ(u,v) = tan-1 ( Imag(u,v) / Real(u,v))}

Fie I(x) un semnal 1D. Transformata Fourier a functiei I(x) este:

unde j= iar u reprezinta frecventa.

Semnalul F(u) poate fi transformat din domeniul frecventei in domeniul spatial prin transformata Fourier inversa:

I(x)=

|F(u)| reprezinta spectrul amplitudinii semnalului.

I(x) se descompune intr-un set de componente de unda sinusoidale. Fiecare punct in |F(u)| specifica amplitudinea si frecventa unei singure componente sinusoidale de unda:

f(x) |F(u)|

x

-u 0 u

O functie bi-dimensionala, I(x,y) ( o functie imagine), se decompune intr-un set de frecvente spatiale |F(u,v)|. Un punct F(u,v) este o masura a frecventei spatiale (u,v) in imagine.

O frecventa spatiala, |F(u,v)|, este o suprafata cu ondulatii sinusoidale a caror rata de ondulatie este data de distanta punctului (u,v) fata de origine: (u² + v² )^1/2

Deci, toate frecventele spatiale cu aceeasi rata de ondulatie se reprezinta prin puncte aflate pe circumferinta unui cerc: r = (u² + v²)^1/2

Orientarea suprafetei (unghiul fata de axa OX) este data de tan^-1(u/v).

Un singur punct, F(u,v), ne spune cat de mult dintr-o anumita frecventa este continut intr-o imagine.

Transformata Fourier discreta (Discrete Fourier Transform

Fie I(x), , o secventa discreta reprezentand un semnal 1D esantionat. Transformata Fourier a semnalului astfel reprezentat se numeste transformata Fourier discreta:

O imagine, I(x,y), este un semnal discret bi-dimensional

Transformata Fourier a imaginii I(x,y) este:

iar transformata Fourier discreta inversa:

O prelucrare de imagine bazata pe transformata fourier inseamna:

Calculul transformatei F(u,v)

Procesarea transformatei prin aplicarea unui filtru H(u,v), care se realizeaza calculand produsul H(u,v)*F(u,v)

Calculul transformatei Fourier inverse a produsului H(u,v)*F(u,v)

Deci, imaginea prelucrata este:

unde F(u,v)=T(I(x,y))

Partea imaginara a functiei I' (x,y) se neglijeaza, fiind de regula foarte mica.

Definitie: Un filtru trece jos H(u,v) este definit astfel:

H(u,v) = 1 daca

H(u,v) = 0 daca

ceea ce inseamna eliminarea frecvantelor mai mari ca r din F(u,v) (care corespund la raze mai mari ca r):

daca atunci H(u,v)*F(u,v) = 0

Adesea, frecventele inalte reprezinta semnal fals in imagine (zgomot), indus de echipamentele electronice de producere a imaginilor discrete. Zgomotul se reprezinta prin puncte negre in zone de imagine albe sau puncte albe in zone de imagine negre.

Definitie: Un filtru trece sus H(u,v) este definit astfel:

H(u,v) = 0 daca

H(u,v) = 1 daca

Prin aplicarea unui filtru trece sus sunt eliminate frecvantele joase din F(u,v) (mai mici ca r ):

daca atunci H(u,v)*F(u,v) = 0

Scopul aplicarii unui filtru trece sus este de evidentiere a detaliilor din imagine.

Pot fi folosite si alte filtre

Pentru a rejecta o anumita banda de frecventa,

Pentru a retine doar o banda de frecvente

Pentru a retine sau elimina structuri coerente cu anumite orientari.

Implementarea transformatei Fourier

Se bazeaza pe o reprezentare matriciala. Consideram si notam cu

Fie matricea Z:

Z= | 1 1 1 _ _ _ _ _ 1 |

| 1 z _ _ _ _ _ |

| 1 _ _ _ _ _ |

| _ _ _ _ _ _ _ _ _ |

| 1 _ _ _ _ _ |

Z are N*N elemente. Z[i][j] =, 0

In majoritatea cazurilor, N este o putere a lui Z. Matricea Z poate fi simplificata observand ca:

Alte proprietati ale matricei Z:

Este simetrica

Produsul scalar al oricaror 2 randuri sau 2 coloane este egal cu zero

Produsul scalar al unei coloane cu ea insasi sau al unui rand cu el insusi este egal cu N

4. Inversa sa este egala cu (conjugata transpusei *1/N).

Transformata Fourier 1D se poate rescrie astfel:

Rezulta forma matriciala:

F=Z*f

iar pentru transformata Fourier bidimensionala:

F=Z*f*, unde

F este matricea imagine iar F- matricea transformatei Fourier a imaginii.

Aplicarea directa a formulei matriciale conduce la inmultiri cu numere complexe si adunari. De aceea, au fost eleborati algoritmi pentru calculul transformatei Fourier. Astfel este algoritmul FFT (Fast Fourier Transform) prezentat in continuare.

Transformata Fourier rapida 2D foloseste transformata Fourier rapida 1D. Mai exact, transformata Fourier 2D este implementata ca o transformare in 2 pasi.

Valorile din matricile F si Z sunt numere complexe:

Transformata Fourier rapida 1D

Se inlocuieste k cu m, astfel incat :

K = 2m pentru k par;

K = 2m+1 pentru k impar

Rescriem formula transformarii, punand in evidenta termenii pari si cei impari:

Notam : M=N/2;

g=

Atunci:

sau

Pentru N=2 (M=1):     F(0) = f(0)*g⁰ + z⁰*f(1) = f(0) +f(1)

F(1) = f(0) - f(1)

Implementarea algoritmului in C:

void FFT_1D(int N, complex *f)

fp = (complex *) malloc (N/2 * sizeof (complex));

fi = (complex *) malloc (N/2 * sizeof (complex));

for(m=0 ; m<N/2; m++)

FFT_1D (N/2, fp);

FFT_1D (N/2, fi);

for (i=0; i<N/2; i++)

free (fp);

free (fi);

Transformata Fourier rapida 2D

Este realizata ca o transformare in 2 pasi, folosind transformarea Fourier rapida 1 D:

Se determina transformarea Fourier a fiecarei coloane a matricei imagine;

Se determina transformarea Fourier a fiecarui rand din matricea obtinuta in prima etapa.

Implementarea algoritmului in C:

void FFT_2D (int N, complex **f)

for (l=0; l<N; l++) // pentru fiecare rand

Afisarea transformatei Fourier a unei imagini

In unele operatii de prelucrare a imaginilor (restaurare, filtrare) se lucreaza cu marimea si faza transformatei Fourier a imaginii.

Fie F matricea in care s-a memorat transformata Fourier a imaginii, FM - matricea in care s-a memorat marimea semnalului si FF matricea in care se memoreaza faza:

 FF[k1][k2] = │ atan2(F[k1][k2].im / F[k1][k2].re) pentru F[k1][k2].re >0

│ /2 pentru F[k1][k2].re = 0 si F[k1][k2].im >=0

│ - /2 pentru F[k1][k2].re =0 si F[k1][k2].im <0

Prin analiza marimii transformatei Fourier se pot obtine informatii utile despre frecventa semnalului 2D reprezentand imaginea. In acest scop, se transforma marimea transformatei Fourier intr-o imagine. Elementele matricei FM sunt scalate astfel inact sa poata fi afisate prin 256 nivele de gri. Totodata, asupra imaginii astfel obtinute se efectueaza o translatie circulara, prin care punctul corespunzator elementului F[0][0] ( originea in spatiul Fourier ) este adus in centrul ecranului. Se efectueaza o scalare la scara logaritmica pentru a fi posibila afisarea unui domeniu relativ mare de valori.

Translatia circulara a unei secvente discrete 2D, f(x,y), este definita astfel:

f'(x,y ) = f((x+m1)mod N1, (y+m2)mod N2),  (x,y)

Pentru N1 = N2 = N, m1 = m2 = N/2, translatia circulara este:

Programul prezentat in continuare realizeaza transformarea matricei marime intr-o matrice imagine cu 256 nivele de gri

#define N 1024   

typedef unsigned char ** imagine;

complex F[N][N];

float FM[N][N], t, max;

imagine img;

int r,c;

max=0;

//calculam marimea transformatei (amplitudinea) si valoarea maxima din FM

for (r=0; r<N; r++)

for (c=0; c<N; c++)

//calculam imaginea si efectuam translatii circulare

coef = 255.0/log(1.0 + max);

for( r = 0; r< N/2; r++)

for( r = N/2; r< N; r++)