2. transformate pentru semnale … · 2. transformate pentru semnale multidimensionale 13 figura...

2. TRANSFORMATE PENTRU SEMNALE MULTIDIMENSIONALE

Acest capitol î i propune s prezinte pe scurt modalit ile de analiz ale semnalelor bi-

i tridimensionale folosind transformatele cele mai des utilizate în procesarea digital a imaginilor i secven elor video.

Exist multe unelte disponibile pentru analiza semnalelor. Uneltele comune folosite pentru studierea semnalelor unidimensionale sunt transformatele Fourier, Laplace i Z. Pentru semnalele bidimensionale au fost folosite transformatele Fourier Discret , Haar, Cosinus Discret (DCT) i Karhunen-Loeve (KLT) pentru a descompune imaginea intr-un set de imagini de baz , care corespund func iilor de baz în cazul 1-D. DCT-2D a fost folosit în compresia imaginilor datorate capacit ilor sale de compactare a energiei. Mai recent, Transformarea Wavelet Discret (DWT) a devenit o unealta importanta pentru procesarea semnalelor, datorit propriet ilor ei superioare de descompunere spa iu-frecven . Pentru semnale video se pot aplica transformatele 2D pentru fiecare cadru al secven ei video sau se poate folosi transformatele 3D echivalente. În continuare vom discuta despre transformatele cele mai des utilizate pentru imagini i secven e video: Transformata Fourier Discret , Transformata Cosinus Discret i Transformata Wavelet Discret .

2.1. Transformata Fourier Discret Transformata Fourier Discret 2D se ob ine prin e antionarea Transformatei Fourier în

Spa iu Discret (Discrete Space Fourier Transform - DSFT), care este extensia la dou dimensiuni a Transformatei Fourier în Timp Discret. Pentru o imagine digital I expresia transformatei DSFT este dat în rela ia (2.1).

1 2

1 1( )

1 20 0

( , ) ( , ) ,N M

j x y

x yF I x y e (2.1)

( , )I x y este intensitatea pixelului de la pozi ia ( , )x y ;

1 12 f este pulsa ia spa ial pe orizontal ;

2 22 f este pulsa ia spa ial pe vertical ;

12 Analiza i prelucrarea digital a semnalelor video

Se observ , c aceast transformat este o func ie continu de frecven i este astfel neindicat pentru procesarea digital de semnal. Pentru procesarea digital avem nevoie de o versiune discret a acestei transformate. Aceasta este Transformata Fourier Discret 2D, ob inut prin e antionarea transformatei DSFT cu frecven de e antionare constant i dat în rela ia (2.2).

1 2

1 1 22 21 2 ,

0 0

0,..., 1( , ) ( , ) ( , ) ,

0,..., 1

ux vyN M jN M

u vM N x y

u MF u v F I x y e

v N (2.2)

Transformata Fourier Discret Invers 2D are expresia:

1 1 2

0 0

0,..., 11( , ) ( , ) ,0,..., 1

ux vyN M jN M

u v

x MI x y F u v e

y NMN (2.3)

Frecven a spa ial m soar cât de repede se modific intensitatea imaginii în planul imaginii i este caracterizat prin frecven e de varia ie pe dou dimensiuni ortogonale:

pe orizontal , în cicluri/unitatea de distan pe orizontal ; pe vertical , în cicluri/unitatea de distan pe vertical .

Pentru o în elegere mai bun a frecven elor spa iale, în Figura 2.1 sunt date dou exemple de func ii 2D i reprezentarea lor ca imagini digitale, unde culoarea neagr reprezint valoarea 1, iar culoarea alb reprezint valoarea -1. Se observ , c pentru imaginea din Figura 2.1a frecven ele spa iale sunt ( , ) (5;0)u v i pentru imaginea din Figura 2.1b ( , ) (5;10)u v .

5u înseamn c avem 5 cicluri (perioade) pe fiecare rând, iar 10v înseamn c avem 10 cicluri (perioade) pe fiecare coloan .

În Figura 2.2 sunt reprezentate spectrele DFT-2D pentru dou imagini digitale. A doua imagine s-a ob inut prin filtrarea median a primei imagini. Aceast filtrare corespunde unui filtru trece-jos, ceea ce se poate observa i pe spectrul celei de-a doua imagini.

( , ) sin(10 )I x y x ( , ) sin(10 20 )I x y x y

a) b)

Figura 2.1. Func ii bidimensionale reprezentate ca imagini

2. Transformate pentru semnale multidimensionale 13

Figura 2.2. Spectrele imaginii „Einstein” i a imaginii dup o filtrare median

2.2. Transformata Cosinus Discret Ca i transformata DFT-2D, Transformata Cosinus Discret 2D (DCT-2D) realizeaz o

conversie imagine (cadru video) – frecven spa ial . Varia ii lente de intensitate în imagine corespund frecven elor joase i sunt cel mai bine percepute de ochi. Tranzi iile bru te corespund frecven elor înalte i nu sunt percepute mai greu de c tre ochiul uman.

La majoritatea standardelor de compresie, Transformata DCT-2D se aplic pe blocuri ale imaginii. Pentru un bloc de luminan de dimensiune M N pixeli, Transformata Cosinus Discret 2-D este dat de:

1 1

0 0

0,1,..., 11 1( , ) ( , ) cos cos ,0,1,..., 12 2

N M

x y

u NC u v I x y x u y v

v MN M (2.4)

( , )I x y este luminan a pixelului de la pozi ia ( , )x y ; ( , )C u v este coeficientul DCT de frecven e ( , )u v .

În literatura de specialitate de cele mai multe ori se utilizeaz rela ia simplificat (2.5):

1 1

0 0

2 1 2 1( , ) ( , ) cos cos ,

2 2

M N

m nx y

x m y nC m n k k I x y

M N (2.5)

unde


1 , pentru 0

2 , în restm

mMk

M

(2.6)

1 , pentru 0

2 , în restn

nNk

N

(2.7)

Coeficientul 00C se nume te coeficient DC i reprezint frecven a spa ial 0 sau media

valorilor pixelilor din bloc. Ceilal i coeficien i se numesc coeficien i AC i reprezint frecven ele spa iale orizontale i verticale din bloc.

Pentru decodare se folose te Transformata Cosinus Discret Invers 2D (IDCT-2D):

1 1

0 0

2 1 2 1( , ) ( , ) cos cos ,

2 2

M N

u vu v

x u y vI x y k k C u v

M N (2.8)

Pentru a exemplifica importan a diferi ilor coeficien i pentru ochiul uman, în Figura 2.3 sunt reprezentate imaginile care se ob in, dac se utilizeaz pentru decodare, pe rând, doar coeficien ii DCT de o anumit frecven . Se observ c cele mai multe detalii sunt con inute în imaginea ob inut din coeficien ii DC ai fiec rui bloc, iar, pe m sur ce frecven ele spa iale cresc, avem tot mai pu ine detalii con inute în imaginea corespunz toare.

Transformata DCT-2D aproximeaz orice imagine de dimensiune M N pixeli cu o combina ie liniar a M N blocuri de baz . În Figura 2.4 sunt reprezentate cele 64 de blocuri de baz pentru o imagine de 8 8 pixeli. Se observ , c , de la stânga la dreapta i de sus în jos frecven a spa ial cre te cu 0,5 cicluri. Orice imagine sau bloc din imagine de 8 8 pixeli poate fi aproximat ca o combina ie liniar a celor 64 de blocuri de baz , unde coeficien ii DCT sunt constantele cu care se înmul esc fiecare dintre blocuri.

Figura 2.3. a) Imaginea original ; b) imaginile ob inute, dac la decodare, se utilizeaz , pe rând, doar

coeficien ii DCT de o anumit frecven


Figura 2.4. Cele 64 de blocuri de baz ale transformatei DCT-2D pentru o imagine de 8 8 pixeli

În cazul secven elor video se poate aplica transformata DCT-2D fiec rui cadru al

secven ei video. O metod de a integra i dimensiunea temporal este utilizarea transformatei DCT-3D. Aceasta se aplic de regul pe grupuri de cadre. Scopul principal al utiliz rii transformatei 3D este eliminarea atât a corela iei intra-cadru, cât i inter-cadru. Expresia transformatei DCT-3D este:

1 1 1

0 0 0

1 1 1( , , ) ( , , ) cos cos cos ,2 2 2

X Y Z

x y zC m n p I x y z x m y n z p

X Y Z(2.9)

unde ( , , )I x y z este intensitatea pixelului de la pozi ia ( , )x y din cadrul z. i transformata 3D se aplic , de regul pe blocuri tridimensionale de date, de exemplu

de dimensiune 8 8 8 , ob inându-se blocuri 3D de coeficien i DCT (vezi Figura 2.5). Fiecare bloc 3D de coeficien i con ine un coeficient DC, (0,0,0)C , iar ceilal i coeficien i sunt coeficien i AC. Cele mai importante componente ale semnalului sunt concentrate în apropiere de coeficientul DC.

Figura 2.5. Transformata Cosinus Discret aplicat pe blocuri 3D de date video

3D-DCT pe blocuri 3D

timp

blocuri 3D de date video blocuri 3D de coeficien i DCT


2.3. Transformata Wavelet Discret 2.3.1. Transformata Wavelet Discret Unidimensional Pentru început analiz m cazul în care semnalul de analizat este unidimensional, adic

este o func ie )(tf . Orice func ie )(tf poate fi exprimat dup cum urmeaz :

k

j

ikij

i

kkjj

j

kkj

kkj

kkj

tkdtks

tkdtks

tkstf

0

0

0

1,,

,11

,11

,0

)()()()(

)()()()(

)()()(

(2.10)

unde

)2(2)(, ktt jjkj (2.11)

este func ia de scalare contractat cu j2 (cu indicele de scalare j) i decalat cu k, cu Nkj, i

)2(2)(, ktt jjkj (2.12)

este func ia Wavelet (detaliu) contractat cu j2 (cu indicele de scalare j) i decalat cu k, unde Nkj, . )(t este func ia de scalare de baz i )(t este func ia wavelet mam . Func iile )(t i )(t sunt ortogonale. În Figurile 2.6 i 2.7 sunt prezentate func ia de scalare de baz i wavelet mam pentru familiile Haar, respectiv Dauberchies de ordin 4.

Coeficien ii s se numesc coeficien i de scalare (aproximare) i coeficien ii d se numesc coeficien i Wavelet (de detaliu). Pentru a descompune func ia )(tf pornim cu setul de

coeficien i 0s cu indicele de scalare j i ob inem dou seturi de coeficien i 1s i 1d cu indicele de scalare j-1. Invers, pentru a genera func ia )(tf pornim cu dou seturi de

coeficien i 1s i 1d cu indicele de scalare j-1 i ob inem setul de coeficien i 0s cu indicele de scalare j.

Coeficien ii se ob in în modul urm tor:

n

jkjj

j

n

jkjj

j

nskngttfkd

nsknhttfks

)()2()(),()(

)()2()(),()(

1,

1,

0

0

0

0

0

0

(2.13)

unde )(nh i )(ng sunt filtrele de analiz multirezolu ie.

Not m )()(~ nhnh i )()(~ ngng i ob inem:


Figura 2.6. Func ia de scalare i func ia Wavelet mam pentru familia Haar

Figura 2.7. Func ia de scalare i func ia Wavelet mam pentru familia Dauberchies de ordin 4

)](*)(~[)(

)](*)(~[)(12

12

00

00

kskgkdkskhks

jj

jj

(2.14)

unde operatorul 2 reprezint opera ia de decimare cu factorul 2.

0 0.2 0.4 0.6 0.8 1 1.2

-1

-0.5

0

0.5

1

Functia de scalare de baza Haar

0 0.2 0.4 0.6 0.8 1 1.2

-1

-0.5

0

0.5

1

Functia Wavelet mama Haar

0 1 2 3 4 5 6 7-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

1.2Functia de scalare de baza Dauberchies de ordin 4

0 1 2 3 4 5 6 7-1

-0.5

0

0.5

1

1.5Functia Wavelet mama Dauberchies de ordin 4


Se observ c Ecua iile (2.14) permit determinarea pe cale iterativ a tuturor coeficien ilor s i d, presupunând cunoscute filtrele h i g.

Bancul de filtre de analiz Din Ecua iile (2.14) pentru 10j , folosind un banc de 2 filtre, se pot determina

coeficien ii )(1 ks i )(1 kd prin filtrare i decimare (vezi Figura 2.8). Bancul de filtre format

din filtrele )(~ nh i )(~ ng se nume te banc de filtre de analiz i ofer pe ramura de sus (trece sus) coeficien ii Wavelet (de detaliu) i pe ramura de jos (trece jos) coeficien ii de scalare cu indicele de scalare mai mic cu o unitate.

Coeficien ii )(ksm i )(kd m pentru m=1,2,3 pot fi calcula i prin itera ii folosind Ecua ia (2.12) sau cascadând mai multe bancuri de filtre cu un singur nivel ca cel din Figura 2.8 pentru a ob ine un banc de filtre cu mai multe nivele. Bancul de filtre cu 3 nivele este reprezentat în Figura 2.9.

Filtru trece-jos

2

2

Filtru trece-sus

Figura 2.8. Bancul de filtre de analiz cu un nivel

Figura 2.9. Bancul de filtre de analiz cu 3 nivele


Bancul de filtre de sintez Pentru a ob ine coeficientul de scalare cu indice de scalare j din coeficientul de scalare

i coeficientul wavelet cu indici j+1 se deduce din ecua iile (2.14) urm toarea formul :

)(*)(*)( 1212 kdgkshks jjj (2.15)

unde operatorul 2 reprezint opera ia de interpolare cu 2.

Folosind Ecua ia (2.15) se pot determina coeficien ii de scalare )(0 ks din coeficien ii

)(1 ks i )(1 kd prin interpolare i filtrare (vezi Figura 2.10). Bancul de filtre format din filtrele )(nh i )(ng se nume te banc de filtre de sintez i ofer , dup însumarea semnalelor de pe

cele dou ramuri coeficientul de scalare )(0 ks cu indicele de scalare mai mare cu o unitate. Ie irile unui banc de filtre de analiz cu mai multe nivele pot fi legate la intr rile unui

filtru de sintez cu mai multe nivele pentru a reproduce coeficien ii originali. De exemplu, un banc de filtre de analiz cu 3 nivele produce la ie ire coeficien ii )(1 kd , )(2 kd , )(3 kd i

)(3 ks . Ace ti coeficien i sunt aplica i unui banc de filtre de sintez cu 3 nivele (vezi Figura

2.11), iar la ie ire se ob in coeficien ii de scalare )(0 ks .

Figura 2.10. Bancul de filtre de sintez cu un nivel

Figura 2.11. Bancul de filtre de sintez cu 3 nivele

)(0 ks

2

2 )(nh)(1 kd

)(1 ks

)(ng


2.3.2. Transformata Wavelet Bidimensional Pân acum ne-am ocupat de Transformata Wavelet Unidimensional , înc nu am stabilit

cum se aplic transformata bi- sau multidimensional . Cea mai simpla metod de a aplica o transformat bidimensional este s privim imaginea ca ni te rânduri de semnale unidimensionale i s le transform m pe acestea. Dup aceasta le transform m i pe direc ia cealalt . Deci solu ia ar fi s aplic m Transformata Wavelet discret mai întâi pe linii i apoi pe coloane, a a cum este prezentat în Figura 2.12.

Cele patru subimagini sunt: I – Imaginea filtrat trece-jos pe linii i coloane, notat în literatura de specialitate cu

LL (low subbands for row and column filtering – subbenzi de frecven joas pentru filtrarea pe linii i coloane);

II – Imaginea filtrat trece-sus pe linii i trece-jos pe coloane, notat în literatura de specialitate cu HL (high subband for row filtering and low subband for column filtering – subband de frecven înalt pentru filtrarea pe linii i subband de frecven joas pentru filtrarea pe coloane);

III – Imaginea filtrat trece-jos pe linii i trece-sus pe coloane, notat în literatura de specialitate cu LH (low subbands for row filtering and high subbands column filtering – subband de frecven joas pentru filtrarea pe linii i subband de frecven înalt pentru filtrarea pe coloane);

IV – Imaginea filtrat trece-sus pe linii i coloane, notat în literatura de specialitate cu HH (high subbands for row and column filtering – subbenzi de frecven înalt pentru filtrarea pe linii i coloane).

Dup o transformare unidimensional r mânem doar cu jum tate din coeficien ii de scalare s. O transformare bidimensional transform coloanele care con in atât coeficien i de scalare s, cât i coeficien i Wavelet d, dar pe coloane se afl doar coeficien i noi de scalare (ob inu i dup transformarea pe linii), care sunt apoi folosi i în transformarea pe coloane. În concluzie, o s r mânem (în subbanda LL) cu doar 1/4 din datele ini iale, ceea ce înseamn c transform rile viitoare or s aib nevoie de mult mai pu in timp de calcul.

Figura 2.12. Aplicarea Transformatei Wavelet unei imagini pe linii i coloane

Imagine Imagine filtrat pe

linii Imagine filtrat pe

linii i coloane

I II

III IV


Aplicând Transformata Wavelet Invers coeficien ilor din subbanda LL o s ob inem corespondentul imaginii originale, dar la un nivel de rezolu ie mai mic cu o unitate. Pentru subbanda LL se aplic din nou Transformata Wavelet în acela i mod. Acest procedeu se poate repeta succesiv pân la un nivel dorit de rezolu ie sau pân la cel mai mic nivel de rezolu ie permis de imaginea curent .

În Figura 2.13 se prezint trei etape de aplicare a transformatei cu subbenzile corespunz toare.

Ca exemplu, în Figura 2.14 este prezentat pozi ionarea coeficien ilor în subbenzi dup descompunerea unei imagini de rezolu ie 8x8 pixeli pe trei nivele de rezolu ie ( 8log2 ).

LL3

LH3

LL1 HL1

LH1 HH1

HL1

LH1 HH1

HL1

LH1 HH1

LL2 HL2

LH2 HH2

HL3

HL2

LH2 HH2

HH3

Prima descompunere A doua descompunere

A treia descompunere Figura 2.13. Exemplu de aplicare a Transformatei Wavelet pe trei nivele de rezolu ie

Figura 2.14. Distribu ia coeficien ilor de scalare i Wavelet pentru o imagine de 8x8 pixeli descompus pe 3 nivele


este coeficientul Wavelet la nivelul de rezolu ie j i de la pozi ia (x,y) din subbanda LH;

este coeficientul Wavelet la nivelul de rezolu ie j i de la pozi ia (x,y) din subbanda HL; xyjyxd , este coeficientul Wavelet la nivelul de rezolu ie j i de la pozi ia (x,y) din subbanda HH.

Se observ c se ob ine doar un coeficient de scalare pe pozi ia (1,1) în subbanda

LL3. Acest coeficient con ine o aproximare a imaginii ini iale la nivelul de rezolu ie 3 (rezolu ie 1x1 pixeli). Coeficien ii Wavelet d con in detaliile imaginii ini iale la nivelul corespunz tor de rezolu ie; pe m sur ce nivelul coeficientului este mai mic, detaliile pe care le con ine sunt mai fine.

Pentru reconstruc ia (sinteza) imaginii originale se aplic algoritmul piramidal din Figura 2.11 pe linii i coloane. Folosind doar coeficientul de scalare se ob ine

corespondentul imaginii originale la nivelul de rezolu ie 3, adic la o rezolu ie de 1x1 pixeli. Folosind coeficientul de scalare 3

1,1s i coeficien ii Wavelet de nivel 3 se ob ine imaginea

la nivelul de rezolu ie 2 (rezolu ie de 2x2 pixeli). Utilizând i coeficien ii de nivel 2 2, yxd se

ob ine imaginea la nivelul de rezolu ie 1 (rezolu ie 4x4 pixeli) i în final folosind i coeficien ii 1

, yxd se ob ine imaginea original de rezolu ie 8x8. În Figura 2.15 este prezentat

o descompunere pe dou nivele de rezolu ie a imaginii „Lena” de rezolu ie 256x256 pixeli. Imaginea din col ul stânga sus este corespondentul imaginii originale la nivelul de rezolu ie 2 (rezolu ie de 64x64 pixeli). Celelalte imagini au fost ob inute doar din coeficien ii Wavelet (de detaliu) din subbanda respectiv i reprezint imaginea detaliu corespunz toare subbenzii.

Figura 2.15. Descompunerea imaginii „Lena” pe dou nivele de rezolu ie

xjyxd ,

yjyxd ,

31,1s

31,1s

3, yxd


2.3.3. Transformata Wavelet Tridimensional Trecerea de la dou dimensiuni la mai multe dimensiuni nu este mai complicat decât

trecerea de la una la dou . O secven a animat de imagini este de fapt un cub tridimensional de informa ie. Pentru a ob ine transformarea tridimensional , aplic m Transformata Wavelet pe direc ia x, apoi pe direc ia y i în fine pe direc ia z. Transformata aplicat pe direc ia z elimin redundan a spa ial între imaginile pe care se aplic . O reprezentare vizual a grup rii coeficien ilor este prezentat în Figura 2.16.

Figura 2.16. Descompunerea Wavelet tridimensional a unei secven e de imagini

2. transformate pentru semnale … · 2. transformate pentru semnale multidimensionale 13 figura...

Documents