operatii pe vecinatatealpha.imag.pub.ro/ro/cursuri/archive/05.pdf · dintr-un complex de oscilatii...

OPERATII PEVECINATATE

2

Tipuri de operatii de prelucrare

Clasificare dupa numarul de pixeli din imagineainitiala folositi pentru calculul valorii unui pixeldin imaginea prelucrata.

Operatii punctuale (toti pixelii de ac val => acelasi rez) Operatii pe vecinatate ( informatii suplimentare, din vecini) Operatii integrale

3

Operatii pe vecinatate

)c,l(VfT)c,l(g Noua valoare a oricarui pixel din imaginea prelucrata rezulta dincombinarea unui numar oarecare de valori ale pixelilor din imagineainitiala, situati in vecinatatea pixelului curent prelucrat.

linial

coloanac

imagine initiala f

linial

coloanac

imagine prelucrata g

Operatii pe vecinatate

4

)c,l(VfT)c,l(g

Definirea transformarii implica specificarea:

vecinatatii pixelului curent prelucrat, V(l,c)

functiei de combinare a valorilor extrase din imagine, T

Functii de combinare (transformari)

liniare

neliniare intrinsec neliniare

neliniare ca efect al adaptarii

5

Vecinatatea

),( clV

Definirea vecinatatii = specificarea pozitiilor pixelilor carefac parte din respectiva vecinatate, specificarea se facefata de pozitia curenta, adica fata de pixelul curentprelucrat, de coordonate (l, c).

linial

coloanac

imagine initiala f

Vecinatate = multime de pixelidin planul imaginii, situati injurul pixelului curent prelucrat.

6

Vecinatatea

KKcl nmnmnmV ,,...,,,, 2211),(

coordonate relative fatade pixelul curent prelucrat numar de pixeli din

vecinatate

Punctul curent prelucrat (l, c) este originea sistemului de coordonateatasat vecinatatii.

In sistemul de coordonate atasat imaginii, vecinatatea este:

KKcl ncmlncmlncmlV ,,...,,,, 2211),(

7

Exemple de vecinatati

sistem de coordonate atasat vecinatatii(NU SUNT COORDONATELE IMAGINII)

pixel curent(originea vecinatatii)

Vecinatatea imediata a pixelului : cei patru vecini imediati,pe linii si coloane ai pixelului dat.

pixel curent(origineavecinatatii)

)0,1(),0,1(),1,0(),1,0(),0,0(4 V

5K4V

Exemple de vecinatati

8

Vecinatatea extinsa a pixelului : cei opt vecini pe linii si coloane.8V

pixel curent(originea vecinatatii)

sistem de coordonate atasat vecinatatii(NU SUNT COORDONATELE IMAGINII)

)1,1(),1,1(),1,1(),1,1(

),0,1(),0,1(),1,0(),1,0(),0,0(8V

9K

9

Exemple de vecinatati

)1,0(),0,1(),0,0(V 3K

)1,0(),1,0( V 2K

)0,1(),0,1(),0,0( V

3K )1,0(),1,0(),0,0( V

3K

10

Operatia de vecinatate poate fi scrisa deci ca:

Operatii pe vecinatate

KK ncmlfncmlfncmlfTclg ,,...,,,,),( 2211

Transformarea T va fi deci o functie cu K variabile scalare.

Operatiile pe vecinatate (filtre)functie de T

Operatii (filtre) liniare

Operatii (filtre) neliniare

Filtrarea liniara a imaginilor

12

Filtrare liniara

Liniaritate = verificarea principiului superpozitiei.

Fie un operator T, care se aplica asupra unor elemente f, g.T este liniar daca, pentru orice constante scalare , avem:

)()()( gTfTgfT

In cazul particular de interes, f si g sunt imagini avand aceeasidimensiune, , sunt scalari reali si T este o operatie devecinatate.

Filtrare liniara

13

)c,l(VfT)c,l(g

KK ncmlfncmlfncmlfTclg ,,...,,,,),( 2211

R

mn

Vnmmn

w

cnlmfwclg),(

),(),(

wmn se numesc ponderi ale filtrului si sunt constante scalareasociate fiecarui punct al vecinatatii folosite.

T = combinatie liniara a valorilor din vecinatateaaleasa a pixelului curent

14

Filtrare liniaraOrice filtru liniar este definit de:

vecinatatea folosita, V

ponderile asociate vecinatatii, wmn

Vecinatatea cu ponderile asociate se numeste masca de filtrare

nucleul de filtrare

functia pondere a filtrului

Ponderile se numesc coeficientii filtrului.mnw

Filtrare liniara - exemple

15

)0,1(),0,1(),1,0(),1,0(),0,0(4 V5K

5.000 w125.010100110 wwww scriere

compacta125.0

125.05.0125.0125.0

Vnm

mn cnlmfwclg),(

),(),(

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

1010

011000

clfwclfwclfwclfwclfwclg

),1(),1()1,()1,(81),(

21),( clfclfclfclfclfclg

marcarea originii

Filtrare liniara - exemple

16

)0,1(),0,1(),1,0(),1,0(),0,0(4 V5K

5.000 w125.010100110 wwww

scrierecompacta

125.0125.05.0125.0

125.0

marcarea originii

Completarea vecinatatii cu ponderi nule

0125.00125.05.0125.00125.00

),1(),1()1,()1,(81),(

21),( clfclfclfclfclfclg

)1,0(),0,1(),0,0(V 3K

Coeficientii atasati punctelor:

4/110 w4/101 w

2/100 w

Operatia de vecinatate se scrie ca:

Vnm

mn cnlmfwclg),(

),(),(

)1,0()0,1()0,0(),( 011000 clfwclfwclfwclg

)1,(41),1(

41),(

21),( clfclfclfclg

4/14/12/1

scrieregrupata

marcarea originii

Filtrare liniara - exemple

17

)1,0(),0,1(),0,0(V 3K

Coeficientii atasati punctelor:

4/110 w4/101 w

2/100 w

)1,(41),1(

41),(

21),( clfclfclfclg

4/14/12/1

scrieregrupata

marcarea originii

Filtrare liniara - exemple

18

Completarea vecinatatii cu ponderi nule

025.0025.05.00000

19

Filtrare liniara - algoritm, implementare

Vnm

mn cnlmfwclg),(

),(),(

Pentru fiecare pixel al imaginii, situat in pozitia (l,c):

plaseaza vecinatatea V cu originea in pixelul curent (l,c)

extrage valorile pixelilor imaginii din vecinatate

combina valorile pixelilor extrasi din imagine

scrie noua valoare in imaginea de iesire la pozitia (l,c)

Treci la pixelul urmator.

20

“Fereastra glisanta”Vecinatatea folosita este o fereastra (deschidere) intr-un suport opacplasat in fata imaginii; din imagine nu se vede dacat portiunea cecorespunde ferestrei plasate in pozitia curenta.

Fereastra este glisata (“plimbata”) peste intreaga imagine, punctcu punct.

imagine initiala imagine prelucrata

21

“Fereastra glisanta”Ex. de aplicare a ferestrei glisante de dimensiune 3x3

Fereastra cu ponderile ei(nucleul de filtrare)

1,1 w 0,1w 1,1w

1,0 w 0,0w1,0w

1,1 w 0,1w 1,1w

1,1 clf 0,1 clf 1,1 clf

1,0 clf 0,0 clf 1,0 clf

1,1 clf 0,1 clf 1,1clf

imagine rezultataimagine initiala

Vnm

mn cnlmfwclg),(

),(),(

Valorile din fereastra

22

“Fereastra glisanta”probleme de implemenate

Ce se intampla pe marginile imaginii, daca vecinatatea “debordeaza” ?

vecinatatea (fereastra) de filtrare

imagine initiala imagine prelucrata

pixeli “problema”

23

“Fereastra glisanta”probleme de implemenate

Solutii de evitare a efectelor de margine:

•ignorarea liniilor/ coloanelor corespunzatoare pozitiilorcu probleme

•bordarea imaginii cu suficiente linii/ coloanecu pixeli avand valori “potrivite” (sa nu influentezerezultatul aplicarii functiei T de combinare a valorilor).

de exp: -valori identice cu cele ale liniilor si coloanelormarginale ale imaginii originale

-valori nule

24

“Fereastra glisanta”probleme de implemenate

4/14/12/1

Completarea vecinatatii cu ponderi nule

025.0025.05.00000

25

“Fereastra glisanta”probleme de implemenate

Complexitatea de calcul:

Vnm

mn cnlmfwclg),(

),(),( K inmultiri, K-1 adunaripentru fiecare pixel

Complexitatea de calcul creste cu cresterea vecinatatii.Este mai eficient sa se lucreze cu vecinatati de dimensiune mica.

Vecinatatile mari pot fi descompuse ?

(acelasi rezultat obtinut prin aplicarea iterativa a mai multe filtariliniare cu vecinatati mai mici)

K elemente in vecinatate

26

Tipuri de filtre liniare

Corespund celor doua tipuri de efecte esentiale dorite:

cresterea uniformitatii in interiorul regiunilor

cresterea contrastului pe frontierele regiunilor

netezire

contrastare

Filtrare liniara de netezire

27

Cresterea uniformitatii in interiorul regiunilor este echivalentacu reducerea micilor variatii ale valorilor pixelilor, datorate,de exemplu, zgomotului.

Scopul filtrarii liniare – cresterea uniformitatii regiunii

Netezire = reducere zgomot adaugat imaginii.

Corespunde definitiei frecventiale a termenului de filtru:

Filtrul este un sistem de circuite electrice, sonore, etc. cu care se selecteazadintr-un complex de oscilatii cu frecvente diferite, oscilatiile cu frecventelecuprinse între anumite limite.

Se presupune ca zgomotul poate fi descris in frecventa.

28

Filtrare liniara de netezireNormalizarea filtrelor de netezireCoeficientii wmn nu pot fi alesi oricum.In cazul unei imagini perfect uniforme (toti pixelii auaceeasi valoare), dupa o filtrare liniara de netezire aceasta valoarenu trebuie sa se modifice.

Vnm

mn cnlmfwclg),(

),(),(

),(,),(,),( clVnmctcnlmf

Vnm

mnwclg),(

),(

0,1),(

mnVnm

mn ww

29

Filtrare liniara de netezireZgomotul cel mai obisnuit: zgomot alb, gaussian, aditiv (ZAGA).

),(),(),( 0 clzclfclf 2,0),( Nclz

0fz 2

30

Filtrare liniara de netezireFiltrul optim de redurea ZAGA : filtrul de mediere aritmetica

Vnm

mn cnlmfwclg),(

),(),(

KVCard Kwmn

1

Vnmcnlmf

VCardclg

),(),(1),(

Ex. 154 KV

51mnw

05/105/15/15/1

05/10Ex. 2

98 KV

91mnw

9/19/19/19/19/19/19/19/19/1

31

Filtrare liniara de netezire

Netezire:medie aritmetica

5 x 5

9 x 9

13 x 13

Efectul de incetosarea imaginii

(blur)cu cresterea dimensiunii

ferestrei de filtrare

32

Filtrare liniara de netezire

3 x 3

7 x 711 x 11

Netezire:medie aritmetica

reducerea zgomotului(si blur)

33

Filtrare liniara de netezireDe ce apare incetosarea imaginii ?Incetosare (blur) : frontierele devin neclareFereastra de filtrarea selecteaza valori diferite, apartinand regiunilorvecine separate de contur. In urma medierii rezulta o valoareintermediara care inlocuieste conturul.

Ex. contur 1D ideal – (o linie din imagine) dupa mediere

34

Filtrare liniara de netezire

05/105/15/15/1

05/10

9/19/19/19/19/19/19/19/19/1

0125.00125.05.0125.00125.00

Filtrul de mediere aritmetica

Filtrul de mediere ponderata

075.0124.0075.0124.0204.0124.0075.0124.0075.0

Filtrul cuponderi dupao legegaussiana

Netezirea si corespunzator incetosarea in cazul unui filtru demediere ponderata (cu ponderea pixelului curent mai mare) e maimica decat pentru filtru de mediere aritmetica.

35

De ce apare incetosarea imaginii ?

O echivalenta in domeniul “frecventelor”:

Contur (detalii fine) frecvente inalteZone uniforme frecvente joase

Filtrarea de mediere filtrarea trece jos

Filtrare liniara de netezire

Filtrare liniara – calitatea filtrarii

36

Functii de masura a calitatii imaginii in raport cu o imagine dereferinta.

Daca imaginea zgomotoasa/ degradata/ testata este f, proveninddin imaginea originala/ corecta/ nedegradata f0 (referinta), putemmasura:

Eroarea patratica medie (Mean Squared Error - MSE)

1

0

1

0

20

20 ),(),(1 M

i

N

jnmfnmf

MNffMSE

Eroarea absoluta medie (Mean Absolute Error - MAE)

1

0

1

000 ),(),(1 M

i

N

jnmfnmf

MNffMAE

37

Filtrare liniara – calitatea filtrariiRaportul Semnal - Zgomot (Signal to Noise Ratio - SNR)

][

),(),(

),(log10 1

0

1

0

20

1

0

1

0

20

dBnmfnmf

nmfSNR M

i

N

j

M

i

N

j

Raportul Semnal de Varf - Zgomot (Peak Signal to Noise Ratio - PSNR)

][

),(),(

),(maxlog10 1

0

1

0

20

20

),( dBnmfnmf

nmfMNPSNR M

i

N

j

nm

intotdeauna PSNR > SNR

38

Filtrare liniara – calitatea filtrariiCalitate : SNR, PSNR

MSE, MAE

In general se foloseste SNR, ca in prelucrarea semnalelor 1D.Imaginea de calitate are SNR > 25 dBImaginea cu diferente imperceptibile are SNR > 30 dB

SNR=20 dB SNR=17 dB SNR=14 dB

39

Filtrare liniara de netezire

Proiectarea filtrului de mediere aritmetica

Kwmn

1 Factor de reglaj: forma si dimensiunea vecinatatii

Se poate demonstra ca puterea zgomotului alb, aditiv din imagineeste redusa de K ori.

Filtrare eficienta vecinatate mare.

Vecinatate mare efect puternic de incetosare a imaginii

40

Filtrare liniara de netezireFiltrul de mediere ponderata

Mai multa libertate in alegerea ponderilor asociate punctelor dinvecinatatea folosita.

Vnm

mn cnlmfwclg),(

),(),(

125.0125.05.0125.0

125.0

05.01.005.01.04.01.0

05.01.005.0

15.07.00

15.000

15.015.04.0

15.015.0

41

Filtrare liniara de contrastare/derivare

Scopul contrastarii unei imagini este îmbunatatirea perceperiivizuale a contururilor obiectelor (îmbunatatirea detectabilitatiicomponentelor scenei de-a lungul frontierelor acestora).

O experienta de perceptie vizuala subiectiva (“benzile lui Mach”)a pus în evidenta faptul ca sistemul vizual uman are tendinta de aadânci profilul zonelor de tranzitie dintre regiuni uniforme.

Studiul fiziologiei sistemului vizual a demonstrat ca acesta serealizeaza prin prelucrari de tip derivativ ce apar în diferitele etapepe care le parcurge informatia vizuala; efectul global poate fi descrisca scaderea din semnalul original a unei derivate secunde.

42

Filtrare liniara de contrastare/derivareperceptia unei linii mai intunecate

perceptia unei linii mailuminoase

Aceste linii NU EXISTA inimagine, ci sunt IMPRESIIcreate de sistemul vizual.

Benzile lui Mach

43

Filtrare liniara de contrastare/derivareSimularea efectului Mach

f

f’

f”

f - f”

44

Filtrare liniara de contrastare/derivareContrastare = Imagine – Derivata secunda

Derivata secunda a unei functii de doua variabile: dupa ce directie ?

Se foloseste Laplacianul: 2

2

2

2 ),(),(),(y

yxfx

yxfyxf

111181111

010141

010

121242

121

Filtre de derivare secunda (Laplacian):

Contrastarea imaginilor

45

medie 5 x 5

original

46

Filtrare liniara de contrastare/derivareImplementarea unei derivate secunde pentru cazuldiscret;

),1(),(),(' nmfnmfnmfm sau ),(),1(),(' nmfnmfnmfm

),(2),1(),1(),(),1(),( '''' nmfnmfnmfnmfnmfnmf mmm

),(2)1,()1,(),()1,(),( '''' nmfnmfnmfnmfnmfnmf nnn

sau)1,(),(),(' nmfnmfnmfn ),()1,(),(' nmfnmfnmfn

),(),(),( '''' nmfnmfnmf nm

),(4)1,()1,(),1(),1(),(

nmfnmfnmfnmfnmfnmf

47

Filtrare liniara de contrastare/derivare

Exp masca: Contrastare = Imagine – Derivata secunda

),(4)1,()1,(),1(),1(),( nmfnmfnmfnmfnmfnmf Derivata secunda:

010141010

0

0101411

010

000010000

010141010

48

Filtrare liniara de contrastare/derivareContrastare = Imagine – Derivata secunda

)},(),(2.1{5

)]},()1,()1,(

),1(),1([51),(2.1{5

)],()1,()1,(),1(),1([),(6

)],(4)1,()1,(),1(),1([),(),(),(

nmfnmf

nmfnmfnmf

nmfnmfnmf

nmfnmfnmfnmfnmfnmf

nmfnmfnmfnmfnmfnmfnmfnmf

49

Filtrare liniara de contrastare/derivare

“Unsharp masking” ),(),(),( nmfnmfnmfs

“Highboost filtering” ),(),(),( nmfnmfnmfhb

Contrastare = Imagine – Derivata secunda

)},(),(2.1{5),(),( nmfnmfnmfnmf

Filtrare liniara de contrastare/derivare

),(),(2),( nmfnmfnmfs

51

Filtrare liniara de contrastare/derivareNormalizarea filtrelor de derivareCoeficientii wmn nu pot fi alesi oricum.

In cazul unei imagini perfect uniforme (toti pixelii auaceeasi valoare dupa o filtrare de derivare, rezultatul trebuiesa fie nul.

Vnm

mn cnlmfwclg),(

),(),(

),(,),(,),( clVnmctcnlmf

0),(),(

Vnm

mnwclg

0),(

Vnm

mnw