Capitolul 1

Extragerea contururilor

Contururile (muchiile) sunt frontierele obiectelor din imgine si sunt determinate de adiacentaregiunilor uniforme; pixelii de tip contur sunt deci caracterizati de schimbari impor-tante ale nivelelor de gri (luminanta sau proprietatea zica preluata de senzorul de mag-ine). Schimbarea valorilor imaginii este evaluata prin doua marimi: diferenta de valorisi marimea suportului spatial pe care are loc tranzitia. Astfel, ceea ce este importantpentru caracterizarea contururilor este rata de variatie a nivelelor de gri, deci derivatafunctiei imagine.

Pentru o imagine modelata printr-o functie continua, pe directia tranzitiei, derivata va maxima. Tehnica esentiala de extragere a contururilor este bazata deci pe calcululgradientului imaginii f(x, y) de-a lungul versorului r, orientat pe directia :

f(x, y)

r=

f(x, y)

x

x

r+

f(x, y)

y

y

r= fx(x, y) cos + fy(x, y) sin (1.1)

Dupa cum se observa, calculul gradientului dupa directia r oarecare se poate reducela calculul derivatelor pe orizontala fx(x, y) si verticala fy(x, y) ale imaginii n punctul

curent (x, y). Valoarea maxima a gradientului f(x,y)r

este obtinuta pentru o anumitaorientare 0, ce se poate obtine prin

(f(x, y)

r

)= 0 (1.2)

Rezolvarea ecuatiei () conduce imediat la fx cos + fy sin = 0, si deci la determinareadirectiei de variatie maxima a functiei imagine:

0(x, y) = arctanfx(x, y)

fy(x, y)(1.3)

1

Pe directia astfel determinata, modulul gradientului va dat de(f(x, y)

r

)max

=

f 2x(x, y) + f2y (x, y) (1.4)

1.1 Operatori de gradient

Extragerea punctelor de contur este atunci imediata: este sucient de a calcula pentruecare punct al imaginii valoarea maxima a gradientului, ce va apoi comparata cu unprag xat. Daca valoarea maxima a gradientului dintr-un punct este sucient de impor-tanta si depaseste valoarea pragului, atunci punctul corespunzator este declarat punctde contur. Toate metodele bazate pe estimarea gradientului se ncadreaza n aceastaschema. Ceea ce va diferentia metodele va modalitatea n care este calculata variatiamaxima a valorilor imaginii (nivelelor de gri) ntr-un punct.

Pentru determinarea variatiei maxime a imaginii este deci necesara determinarea derivatelorpe directiile orizontala si verticala. Realizarea derivatelor partiale dupa aceste directii im-plica trecerea n discret a derivatelor fx(x, y) si fy(x, y) (incluzand si modicarea notatiilorcoordonatelor, m ind versiunea discreta a lui x si n ind versiunea discreta a lui y):

fx(x, y) =f(x, y)

x=

f(m,n)

m

fy(x, y) =f(x, y)

y=

f(m,n)

n

Aceste derivate partiale discrete pot avea mai multe implementari:

fx = f(m,n) f(m+ 1, n), fy = f(m,n) f(m,n + 1) (1.5)

fx = f(m 1, n) f(m,n), fy = f(m,n 1) f(m,n) (1.6)fx = f(m 1, n) f(m+ 1, n), fy = f(m,n 1) f(m,n + 1) (1.7)

Toate expresiile date de (1.5), (1.6), (1.7) sunt combinatii liniare ale valorilor unor pixelidin imagine, situati n vecinatatea pixelului curent din pozitia (m,n). Deci toate acesteoperatii se pot realiza prin ltrari liniare cu masti potrivite: (1.8) pentru (1.5), (1.9)pentru (1.6), (1.10) pentru (1.7).

Wx =(

1 1 ) , Wy = ( 11)

(1.8)

2

Wx =(

1 -1), Wy =

(1-1

)(1.9)

Wx =(

1 0 1 ) , Wy = 101

(1.10)Este interesant de remarcat faptul ca descompunerea derivatei dupa directia r oarecare sepoate face dupa oricare alte doua directii ortogonale, nu numai orizontala si verticala [?].Considerand ca aceste directii de referinta sunt diagonalele principale ale sistemului decoordonate (deci orientate la /4 si 3/4 fata de orizontala), vor trebui determinate formediscrete pentru derivarea imaginii dupa diagonale. Asemenea derivate sunt realizate demastile de ltrare Roberts:

W/4 =

(0 11 0

), W3/4 =

(1 00 1

)(1.11)

De asemenea, se remarca faptul ca toate mastile de ltrare liniara prezentate, ce imple-menteaza operatii derivative, verica conditia de normare a ltrelor liniare derivative, sianume, suma coecientilor de ponderare din masca sa e nula (??).

Implementarea operatiei de extragere a punctelor de contur prin calculul gradientuluidupa doua directii ortogonale este data in gura 1.1.

Fig. 1.1: Schema bloc a extractorului de contururi bazat pe metoda de calcul a gradien-tului prin doua derivate dupa directii ortogonale.

Se observa, deci, existenta a trei rezultate de interes: harta de orientari 0(m,n) careeste o imagine ce contine, pentru ecare pixel, orientarea gradientului de modul maximn punctul respectiv, si este n general folosita la prelucrarea suplimentara a contururilor(conectare de contururi, extragere directionala de contururi), harta de intensitati detranzitie, g(m,n) care este o imagine ce contine, pentru ecare pixel, valoarea maxima agradientului pentru pozitia respectiva si harta de contururi e(m,n) care este o imagine

3

binara n care punctele marcate (puncte-obiect) corespund pozitiei punctelor de contur(puncte al caror gradient maxim depaseste pragul xat). O simplicare uzuala practicataeste nlocuirea normei L2 din calculul modulului maxim al gradientului (1.4) cu normaL1, ceea ce conduce la aproximarea:(

f(x, y)

r

)max

|fx(x, y)|+ |fy(x, y)|

1.2 Operatori de gradient cu netezire

Unul dintre dezavantajele principale legate de folosirea acestor masti derivative simple (ceimplementeaza direct operatia de derivare directionala discreta) este marea sensibilitatela zgomot. In urma derivarii, un zgomot alb, aditiv este amplicat de doua ori. Com-pensarea evidenta este de a realiza o operatie de reducere a zgomotului naintea derivarii,urmarind simultan pastrarea prolurilor abrupte de tranzitie (si deci introducerea unorefecte minime de ncetosare). Pentru ca prolul tranzitiei pe directia r sa nu e afectat,ltrarea de netezire va trebui deci aplicata pe directia perpendiculara. Atunci, derivareaorizontala va trebui precedata de o ltrare de netezire cu o masca verticala, iar derivareaverticala va trebui precedata de o ltrare de netezire cu o masca orizontala. Operatiile deltrare liniara ind realizate prin convolutii, sunt asociative, si deci este posibila deter-minarea unei masti unice de ltrare, care sa grupeze efectele de netezire si derivare dupacele doua directii perpendiculare. Considerand o netezire de tip mediere ponderata cucoecientul c R+ si operatii de derivare descrise de mastile din (1.10), obtinem mastileechivamente de ltrare:

Wx =

1c1

( 1 0 1 ) = 1 0 1c 0 c

1 0 1

Wy =

(1 c 1

) 101

= 1 1 10 0 01 1 1

Prin particularizari convenabile ale coecientului de ponderare c folosit la ltrarea denetezire se pot obtine diferite familii clasice de operatori de derivare cu netezire: Prewitt(c = 1, 1.12), Izotrop (c =

2, 1.13), Sobel (c = 2, 1.14) [?]. Se remarca faptul ca

constanta de ponderare globala a mastii de ltare este neesentiala, ntrucat conditia denormare ce trebuie ndeplinita este cea pentru ltre de contrastare (derivare) (??): sumacoecientilor mastii sa e nula.

Wx =

1 0 11 0 11 0 1

, Wy = 1 1 10 0 01 1 1

(1.12)4

Wx =

1 0 12 0 21 0 1

, Wy = 1 2 10 0 01 2 1

(1.13)

Wx =

1 0 12 0 21 0 1

, Wy = 1 2 10 0 01 2 1

(1.14)Metoda de combinare a derivarii si netezirii poate extinsa, folosind diferite tipuri demasti de derivare directionale de baza sau diferite tipuri de ltrari de netezire, chiarnedirectionala. Operatorii de derivare MDIF [?] sunt construiti printr-o ltrare de medierearitmetica ntr-o vecinatate V4 ce precede aplicarea unor masti de derivare Prewitt (1.12).Mastile rezultante sunt evident de dimensiune 5 x5:

Wx =

0 1 0 1 01 2 0 2 11 3 0 3 11 2 0 2 10 1 0 1 0

,Wy =

0 1 1 1 01 2 3 2 10 0 0 0 01 2 3 2 10 1 1 1 0

(1.15)

1.3 Operatori compas

Informatia de orientare este n general folosita n etape urmatoare ale prelucrarii; unghi-urile determinate dupa (??) ofera un unghi exact al directiei conturului n punctulcurent, calculat cu un efort semnicativ de calcul (mpartire si calcul de arctangenta). Inpractica, aceasta informatie este prea exacta: pe grila patrata de esantionare nu se potreprezenta cu usurinta drepte continue dupa orice directie; cateva directii sunt favorizatesi usor de utilizat (vertical, orizontal, cele doua diagonale). In acest caz se poate masura necare modulul gradientului dupa aceste cateva directii importante, si apoi se poate alegedirectia dupa care acest modul este maxim. Acesta este principul operatorilor compas.Operatorii compas calculeaza mai multe derivate directionale, dupa un set de N directii(N > 2). Gradientul maxim al functiei imagine n punctul respectiv este determinat camaximul valorilor derivatelor directionale, iar pentru decizia ulterioara se selecteaza doarinformatia corespunzatoare directiei pe care derivata a fost maxima. Daca N = 2 si celedoua directii sunt ortogonale, schema de prelucrare obtinuta este similara cu cea a unuiextractor de contururi bazat pe gradient n care estimarea gradientului maxim se faceprintr-o metrica de tip L (max). Schema bloc generala a unui operator compas esteprezentata n gura 1.2; ecare dintre mastile Wk realizeaza calculul unei derivate, pedirectia k.

5

Fig. 1.2: Schema bloc a extractorului de contururi bazat pe metoda de calcul a gradien-tului prin derivate dupa 8 directii.

Operatorul compas uzual are N = 8 masti de ltrare, ecare dintre ele realizand oderivare dupa o directie multiplu de /4; sunt astfel acoperite directiile principale (ver-tical, orizontal, cele doua diagonale), n cele doua sensuri. Cele N masti folosite suntderivate de la o unica masca de baza, implemenand de obicei o derivare orizontala, prinrotiri succesive ale acesteia cu unghiuri corespunzand diferentelor de directie a derivatelorfolosite. Pentru operatorul compas uzual cu N = 8, mastile de derivare folosite sunt 3 x3, si mastile corespunzatoare directiilor succesive diera printr-o rotatie de /4. Aceastarotatie de /4 este nsa echivalenta cu o deplasare circulara a valorilor de pe margineamastii:

W0 =

a b ch * dg f e

;W/4 = b c da * e

h g f

(1.16)Masca initiala ce corespunde directiei orizontale poate oricare dintre mastile de derivarecu netezire pe orizontala Wx prezentate, ca de exemplu Prewitt (1.12) sau Sobel (1.14).Suplimentar, au fost introduse masti speciale, asa ca mastile Kirsch, caracterizate de

Wx =

5 3 35 0 35 3 3

; cele 8 masti folosite de operatorul compas Kirsch (indexatedupa numele orientarilor punctelor cardinale corespunzatoare) sunt deci:

WE =

5 3 35 0 35 3 3

,WNE = 3 3 35 0 3

5 5 3

,WN = 3 3 33 0 3

5 5 5

,WNV = 3 3 3 0 53 5 5

WV =

3 3 53 0 53 3 5

,WSV = 3 5 53 0 53 3 3

,WS = 5 5 53 0 33 3 3

,WSE = 5 5 35 0 33 3 3

6

Se poate remarca cu usurinta ca exista o legatura ntre precizia unghiulara a operatoru-lui compas (deci diferenta dintre directiile alaturate dupa care se calculeaza derivateledirectionale) si dimensiunea mastilor de ltrare folosite; pentru o masca patrata de di-mensiune D x D, precizia unghiulara este de /2(D1) si numarul de masti utilizate deoperatorul compas este de N = 4(D 1).

1.4 Operatori compas cu netezire

Problemele legate de sensibilitatea derivatelor directionale la zgomot raman aceleasi sipentru operatorii compas; etapa logica a fost deci de a combina derivarea directionala(deja cu masti de derivare si netezire) cu o etapa suplimentara de netezire directionalaadaptiva. De exemplu, structura de ltrare propusa de Awajan [?] foloseste patru mastide mediere ponderata directionala (pe verticala, orizontala si cele doua diagonale); pentruecare pixel al imaginii, varianta sa netezita ce va folosita apoi la extragerea contu-rurilor, este determinata ca rezultatul ltrarii care difera cel mai putin de valoare initialadin pixelul considerat. Mastile de netezire sunt:

W0 =1

10

0 0 0 0 00 1 1 1 00.5 1 1 1 0.50 1 1 1 00 0 0 0 0

,W/4 = 110

0 0 0 0.5 0.50 0 1 1 0.50 1 1 1 00.5 1 1 0 00.5 0.5 0 0 0

W/2 =1

10

0 0 0.5 0 00 1 1 1 00 1 1 1 00 1 1 1 00 0 0.5 0 0

,W3/4 = 110

0.5 0.5 0 0 00.5 1 1 0 00 1 1 1 00 0 1 1 0.50 0 0 0.5 0.5

Operatorul compas propriu-zis foloseste 16 masti ce implementeaza derivate directionalepe directii orientate dupa unghiuri multiplu de /8; primele patru masti ale setului sunt:

W0 =

0 0 0 0 00 1 0 1 02 2 0 2 20 1 0 1 00 0 0 0 0

,W/8 =

0 0 0 0 0.50 0 1 2 20 1 0 1 0.52 2 1 0 00.5 0 0 0 0

7

W/4 =

0 0 0 0.5 20 0 1 2 0.50 1 0 1 00.5 2 1 0 02 0.5 0 0 0

,W3/8 =

0 0 0.5 2 0.50 0 1 2 00 1 0 1 00 2 1 0 00.5 2 0.5 0 0

In [?] este prezentata o varianta asemanatoare de operator compas cu netezire, carefoloseste pentru netezire o ltrare adaptiva Nagao.

O alta posibilitate de accentuare a neliniaritatii si de adaptare a operatorului compasconsta n calcularea derivatelor directionale numai pentru pixelii ce ndeplinesc anumiteconditii, ca de exemplu situarea pe mijlocul unei tranzitii pe directia data. Aceasta sepoate verica e prin operatori logici aplicati la nivelul valorilor individuale ale pixelilor(((P4 > P1) si (P4 > P6)) sau ((P4 < P1) si (P4 < P6)) si echivalentele pentru pixelii P5si P6), e prin vericarea ca rezultatul aplicarii unei masti de tipul: P1 P2 P3P4 P5 P6

P7 P8 P9

, 1 1 12 2 2

1 1 1

(1.17)

1.5 Detectia punctelor izolate

Principalul mod de determinare a punctelor izolate este bazat pe comparatie dintre val-oarea punctului testat si nivelul de gri mediu din vecinatatea acestuia; daca aceastadiferenta este importanta, punctul testat difera n mod semnicativ de vecinii sai, si esten consecinta cel pun un punct izolat. O masca simpla de determinare a diferentei ntrevaloare punctului curebt si media aritmetica a vecinilor sai este

W =

1 1 11 8 11 1 1

(1.18)

1.6 Detectia combinata

In cele mai multe cazuri, prelucrarea este realizata n vecinatati de dimensiune redusa(tipic 3 x 3) a pixelilor; deci ecarui pixel prelucrat i se asociza un vector de caracteristici(cu 9 componente, daca se foloseste o vecinatate 3 x 3), ce sunt chiar nivelele de gri alepixelilor selecteti de fereastra de prelucrare. Astfel, ecare pixel devine reprezentat de un

8

punt ntr-un spatiu 9-dimensional. Pe langa baza evidenta de reprezentare, constituitade versorii axelor carteziene de coordonate, n acest spatiu se pot introduce mai multebaze ortogonale de reprezentare, iar versorii vectorilor ce compun aceste baze pot transformati n matrici 3 x 3, ce vor folosite ca masti de ltrare.

(P1, P2, P3, P4, P5, P6, P7, P8, P9) P1 P2 P3P4 P5 P6

P7 P8 P9

(1.19)O astfel de baza a fost propusa de Frei si Chen si grupeaza 4 vectori (w1 w4) ce core-spund unei familii de operatori compas construite pe baza mastilor de gradient izotrop,4 vectori (w5 w8) cecorespund unor operatori de tip Laplacian (derivate secunde) siun vector ce corespunde unei medieri aritmetice. Mastile echivalente acestor vectori sunt

deci: w1 =

1 2 10 0 01 2 1

, w2 = 1 0 12 0 2

1 0 1

, w3 = 0 1 21 0 1

2 1 0

,w4 =

2 1 01 0 10 1

2

, w5 = 0 1 01 0 1

0 1 0

, w6 = 1 0 10 0 0

1 0 1

, w7 = 1 2 12 4 21 2 1

, w8 = 2 1 21 4 12 1 2

, w9 = 1 1 11 1 1

1 1 1

. Fiecare dintre cele treigrupuri mentionate de vectori va deni un subspatiu: subspatiul muchiilor, subspatiulliniilor si subspatiul punctelor.

Pentru un pixel oarecare din imagine vectorul sau de caracteristici (vecinatatea sa 3 x 3exprimata ca un vector linie, conform (1.19), este proiectat pe cele trei subspatii; marimeaacestor proiectii si unghiurile pe care acestea le fac cu vectorul original sunt date de:

pmuchii =

4i=1

(w

ip)2, muchii = arccos

pmuchii

p2

plinii =

8i=5

(w

ip)2, muchii = arccos

plinii

p2

ppuncte = w9,p , puncte = arccos ppunctep2

In functie de unghiurile si proiectiile astfel calculate, pentru ecare pixel, se decide careeste subspatiul cel mai apropiat, si deci natura respectivului pixel. Pixelii de contur suntselectati din subspatiile muchiilor si liniilor.

9

1.7 Operatori Laplacieni

Extragerea punctelor de contur pe baza primei derivate (si deci a gradientului, indiferentde modul de estimare a acestuia) este potrivita n cazul tranzitiilor relativ abrupte anivelelor de gri, si deci pentru frontiere bine conturate. Cu cat regiunea de tranzitiedevine mai larga (si deci panta proluli de tranzitie mai mica) centrul acestei tranzitii,detectat prin maximul gradientului, devine mai greu de determinat cu precizie. Astfel,contururile detectate vor formate din mai multi pixeli, nu neaparat situati pe centrulregiunii de tranzitie. Gasirea centrului tranzitiei va putea atunci realizata prin folosireaderivatelor de ordinul doi, grupate n operatorul Laplacian:

2f = 2f(x, y)

x2+

2f(x, y)

y2(1.20)

Operatorul Laplacian nu mai permite detectarea directiilor de tranzitie, deoarece informatiade orientare a tranzitiei este pierduta. Determinarea punctelor de contur ca puncte deextrem ale Laplacianului (maxime si minime, sau maxime ale valorii absolute a Laplacian-ului) produce muchii duble n harta de contururi, deoarece aceste puncte de extrem suntsituate de o parte si de alta a regiunii de tranzitie, marcand limitele acesteia. Mijlocultranzitiei este este marcat de trecerea (tranzitia) prin zero a Laplacianului: pe aceastaobservatie se bazeaza modelul de detector zero-crossing introdus de Marr si Hildreth.

Principalele masti utilizate pentru calculul Laplacianului sunt w7 =

1 2 12 4 21 2 1

,W =

1 1 11 8 11 1 1

, W = 0 1 01 4 1

0 1 0

.Desigur, sensibilitatea la zgomot a Laplacianului este mai mare decat a operatorilor degradient, ceea ce a dus la introducerea unor operatori de derivata secunda, combinaticu netezire. Unul dintre acesti operatori este LOG, Laplacian de Gaussiana; coecientiinucleului de ltrare sunt dati de

h(k, l) = K

(2 k

2 + l2

2

)exp

(k

2 + l2

22

)(1.21)

Scalarul K este determinat din conditia de normalizare a coecientilor mastii de ltrareliniara. O varianta separabila a acestui operator (deci care combina ltrari numai pe liniisi numai pe coloane) a fost propusa de Huertas si Medioni [?]:

LOG(g) = g1(x)g2(y) + g2(x)g1(y) (1.22)

10

unde cele doua nuclee liniare g1 si g2 sunt date de:

g1(x) =

K

2

(1 x

2

2

)exp

( x

2

22

); g2(y) =

K

2exp

( y

2

22

)(1.23)

Forma separabila a operatorului LOG pune n evidenta n mod clar operatiile de derivatasecunda unidirectionala a unei Gaussiene (g1) si de netezire pe directia ortogonala de-rivarii, dupa un nucleu Gaussian (g2). Avantajul formei separabile este posibilitateaimplementarii cu un numar redus de operatii.

Derivata secunda unidimensionala a nucleului Gaussian poate pusa si sub forma uneidiferente de Gaussiene cu dispersii diferite:

2G(x)

x2= G(x)G+d(x) (1.24)

1.8 Operatori morfologici de extragere a contururilor

Operatiile mofologice de baza, extinse pentru imagini cu nivele de gri, pot utilizatepentru a construi harti de intensitate de tranzitie, care sa masoare gradul n care valoareecarui pixel difera de cea a vecinilor sai. Cele mai simple extractoare morfologice decontur sunt conturul exterior (diferenta dintre dilatare si imaginea originala) si conturulinterior (diferenta dintre imaginea originala si erodarea sa):

f = f g f ; f = f f g (1.25)Gradientul morfologic este diferenta dintre imaginea dilatata si, respectiv erodata, cuacelasi element structurant (si deci este suma contururilor interior si exterior):

gradf = f g f g = f + f (1.26)

Daca interpretam sumarea contururilor interior si exterior ca pe o operatie de agregarea unor informatii partiale, realizarea agregarii se poate realiza si prin alte operatii, caminimul sau maximul; operatorii rezultati grupeaza deci doua etape de calcul de extrem (odata prin operatia morfologica si apoi prin operatorul de agregare) si deci sunt operatorimultietaj:

max (f, f) ;min (f, f) (1.27)

Varianta cu netezire a operatorului morfologic multietaj foloseste o varianta netezita aimaginii originale (prin ltrare liniara cu o masca de mediere h) si

min (f h (f h) g, (f h) g f h) (1.28)

11

Variantele directionale ale extractoarelor morfologice de contur se bazeaza pe posibilitateadenirii unor elemente structurante al caror suport sa e orientat, urmarind astfel com-portarea valorilor din vecnatatea ecarui punct pe o anumita directie. Alegerea directiepe care variatia este predominanta este realizata, desigur, printr-un operator de maximsau minim, rezultand, din nou, o structura multietaj. De exemplu:

min (f gA f, f gB f,max (|f gC1 f gC2| , |f gC3 f gC4|)) (1.29)sau

min (f f gA, f f gB,max (|f gC1 f gC2| , |f gC3 f gC4|)) (1.30)unde suporturile elementelor structuante folosite sunt A = {(0, 1) , (0,1) , (1, 0) , (1, 0)},B = {(1, 1) , (1,1) , (1, 1) , (1,1)}, C1 = {(0, 1) , (1, 0)}, C2 = {(0,1) , (1, 0)},C3 = {(0,1) , (1, 0)}, C4 = {(0, 1) , (1, 0)}.

1.9 Operatorul Haralick (aproximarea polinomiala)

1.9.1 Aproximari polinomiale liniare

Pentru orice set de n puncte diferite ntre ele, {x0, ..., xn1}, se poate determina unpolinom unic de grad n1 care sa aiba punctele date ca solutii, P (xi) = 0, i = 0, ..., n1.Pentru aceleasi n puncte se poate determina o familie de n polinoame de grad cel multn 1, ortogonale doua cate doua n raport cu setul de puncte {xi}, caracterizate de:

n1i=0

Pnu(xi)Pnv(xi) = 0, u = v (1.31)

Polinoamele familie astfel denite sunt deci Pnu, polinomul de grad u din familia celor npolinoame, si formeaza o baza n spatiul polinoamelor de grad cel mult n 1, denitan raport cu multimea de puncte {xi}. Orice polinom de grad cel mult n 1 va putea deci aproximat printr-o combinatie liniara de polinoame Pnu

P (x) =n1k=0

akPnk(x) (1.32)

Coecientii de ponderare ak se deduc din conditia de minimizare a erorii patratice deaproximare n punctele familiei {xi} :

2 =n1i=0

(P (xi)

n1k=0

akPnk(xi)

)2(1.33)

12

2

ak= 2

n1i=0

P (xi)Pnk(xi) + 2ak

n1i=0

P 2nk(xi) = 0 (1.34)

ak =

n1i=0 P (xi)Pnk(xi)n1

i=0 P2nk(xi)

(1.35)

Daca multimea punctelor de denitie este simetrica (xk {xi} xk {xi}) se potobtine de exemplu polinoamele Cebsev: n = 3, {xi} = {1, 0, 1}, cu

P30(x) = 1;P31(x) = x;P32(x) = x2 2

3(1.36)

sau n = 5, {xi} = {2,1, 0, 1, 2}, cu

P50(x) = 1;P51(x) = x;P52(x) = x2 2;P53(x) = x3 17

5x (1.37)

P54(x) =x4 + 210x2 144

160

1.9.2 Aproximare polinomiala bidimensionala

Portiunea de imagine situata n fereastra de analiza de dimensiune N x N , centrata npixelul de coordonate (i, j) (deci cu N impar si N = 2M + 1), este aproximata cu unpolinom al carui grad maxim n x si y nu depaseste N 1. Exista deci o multime deN2 puncte pentru care se construieste o baza de N2 polinoame, ce rezulta din produsulcartezian al celor doua baze de polinoame unidimensionale determinate pentru aceleasipuncte:

{PN2,00(x, y), PN2,01(x, y), ..., PN2,N1N1(x, y)} = {PN0(x), ..., PNN1(x)}{PN0(y), ..., PNN1(y)}(1.38)

Considerand N = 3 (M = 1) si multimile de puncte (i, j) {1, 0, 1} {1, 0, 1} ,polinoamele bazei bidimensionale sunt:

P9,00(x, y) = 1;P9,10(x, y) = x;P9,20(x, y) = x2 2

3

P9,01(x, y) = y;P9,11(x, y) = xy;P9,21(x, y) = y

(x2 2

3

)P9,02(x, y) = y

2 23;P9,12(x, y) = x

(y2 2

3

);P9,22(x, y) =

(x2 2

3

)(y2 2

3

)13

In fereastra de analiza aleasa, imaginea este aproximata ca

f(x, y) =

N1n=0

N1m=0

anmPN2,nm(x, y) (1.39)

si coecientii de aproximare sunt determinati din aceeasi conditie de eroare patraticaminima, ca

anm =

Mi=M

Mj=M f(i, j)PN2,nm(i, j)M

i=MM

j=M P2N2,nm(i, j)

(1.40)

Coecientii de aproximare anm se pot calcula printr-o ltrare liniara a imaginii (expresiade denitie () este liniara n valorile PN2,nm(i, j) = f(i, j)) cu o masca de ltrare a careicoecienti sunt dati de:

H(u, v) =PN2,nm(u, v)M

i=MM

j=M P2N2,nm(i, j)

(1.41)

Pentru polinoamele prezentate n exemplul anterior, mastile de ltrare prin care se pot

deduce coecientii sunt: H00 =19

1 1 11 1 11 1 1

, H10 = 16 1 1 10 0 0

1 1 1

, H20 =16

1 1 12 -2 21 1 1

, H02 = 16 1 2 11 -2 1

1 2 1

, H12 = 14 1 2 10 0 0

1 2 1

, H22 = 14 1 2 12 1 2

1 2 1

,H01 =

16

1 0 11 0 11 0 1

, H11 = 14 1 0 10 0 01 0 1

, H21 = 14 1 0 12 0 21 0 1

.Folosind expresia aproximativa a functiei imagine, data de (1.39), derivatele dupa directiileaxelor de coordonate se pot calcula ca:

f (x, y)

x=

N1n=0

N1m=0

anmPN2,nm(x, y)

x;f (x, y)

y=

N1n=0

N1m=0

anmPN2,nm(x, y)

y(1.42)

In centrul mastii (deci n punctul curent n care se face analiza), derivatele sunt date def(x,y)

x

(0,0) si

f(x,y)y

(0,0) .

Daca se folosesc polinoamele determinate anterior, se constata caPN2,nm(x,y)

x

(0,0) = 0, cu

exceptiaP9,10(x,y)

x

(0,0) = 1 si

P9,12(x,y)

x

(0,0) = 23 . Atunci, derivata pe directia verticala

este f(x,y)x

(0,0) = a10+a12, ceea ce este echivalent cu aplicarea directa a mastii de ltrare

14

H10 23H12 = 12

0 1 00 0 00 1 0

. In mod analog, masca de ltrare pe directia orizontalaeste 1

2

0 0 01 0 10 0 0

.

1.10 Cel mai potrivit plan

Functia imagine continua se poate aproxima cu o suprafata de ordinul unu, deci cu unplan. Ecuatia planului ce trece prin punctul de coordonate spatiale (m,n) este:

z(x, y) = z0 + (xm) + (y n) (1.43)

Coecientii si , care dau derivatele pe orizontala si verticala sunt date de expresiile:

=1

6(f11 + f01 + f11 f11 f01 f11) (1.44)

=1

6(f11 + f11 + f10 f11 f10 f11) (1.45)

si deci pot implementate prin mastile de ltrare liniara W =16

1 0 11 0 11 0 1

, W =16

1 1 10 0 01 1 1

(deci mastile Prewitt).

1.11 Cea mai potrivita cuadrica

Se urmareste construirea unei suprafete cuadrice (descrisa deci de o expresie polinomialade ordinul doi) care sa aproximeze cel mai bine (n sensul erorii patratice medii) functiacontinua ce modeleaza imaginea, n jurul unui pixel xat. Suprafata determinata vaaproxima prolul imaginii ntr-un spatiu tridimensional de reprezentare, n care coordo-nata valorica (axa z) este valoare nivelului de gri, iar coordonatele spatiale si pastreazasemnicatia, ind asociate primelor doua axe. Suprafata este descrisa de ecuatia:

z(x, y) = z0 +A(xm)2 +B(y n)2 +C(xm) +D(y n) +E(xm)(y n) (1.46)

15

unde z0 este valoarea imaginii n punctul curent n jurul caruia se face aproximarea, deciz0 = f(m,n). Aproximarea se face ntr-o vecinatate V a punctului de coordonate (m,n),formata din punctele {(m + k, n + l)|(k, l) V }, iar coecientii A E sunt determinatiprin minimizarea erorii patratice :

=

(k,l)V(f(m+ k, n + l) z(m + k, n + l))2 (1.47)

Minimizarea erorii patratice revine la a calcula derivatele partiale ale expresiei acesteiadupa cei cinci parametri ai suprafetei z si de a anula aceste derivate. Solutiile ecuatiilorastfel formate sunt valorile optime ale parametrilor. Vom adopta notatia simplicatoaref(m+ k, n+ l) = fkl (si deci, de exemplu, f(m+1, n 1) = f11). Atunci expresia eroriipatratice devine:

=

(k,l)V(fkl z(m + k, n + l))2 (1.48)

Cea mai simpla vecinatate este, desigur, vecinatatea extinsa de ordinul unu, deci V8 (deter-minata de o masca patrata 3 x3, centrata). Atunci V = {(1,1), (1, 0), (1, 1), (0,1), (0, 0), (0, 1), (1,si expresia erorii devine:

= (f11 f00 A B C D E)2 + (f01 f00 B D)2 + (1.49)+ (f11 f00 AB + C D + E)2 + (f10 f00 A + C)2 ++ (f11 f00 AB + C + D E)2 + (f01 f00 B + D)2 ++ (f11 f00 AB C + D + E)2 + (f10 f00 A C)2

Derivatele partiale dupa parametrii suprafetei cuadrice sunt atunci:

E= 8E 2f11 2f11 + 2f11 + 2f11 = 0 (1.50)

D= 12D 2f11 2f01 2f11 + 2f11 + 2f01 + 2f11 = 0 (1.51)

C= 12C 2f11 2f11 2f10 + 2f11 + 2f10 + 2f11 = 0 (1.52)

B= 12B + 8A + 12f00 2f11 2f01 2f11 2f11 2f01 2f11 = 0 (1.53)

A= 12A + 8B + 12f00 2f11 2f10 2f11 2f11 2f10 2f11 = 0 (1.54)

Rezolvand ecuatiile, parametrii cuadricei sunt:

E =1

4(f11 + f11 f11 f11) (1.55)

16

D =1

6(f11 + f01 + f11 f11 f01 f11) (1.56)

C =1

6(f11 + f11 + f10 f11 f10 f11) (1.57)

B =1

10(f11 + 2f10 f11 f11 + 2f10 f11 3f01 3f01 + 6f00) (1.58)

A =1

10(f11 + 3f10 + f11 + f11 + 3f10 + f11 2f01 2f01 6f00) (1.59)

Expresiile obtinute sunt liniare n valorile imaginii selectate de vecinatate, deci pot obtinute prin ltrarea liniara a imaginii, folosind masti de ltrare care sa corspunda expre-

siilor deduse. Aceste masti sunt: WA =110

1 3 12 6 21 3 1

, WB = 110 1 2 13 6 31 2 1

,WC =

16

1 0 11 0 11 0 1

, WD = 16 1 1 10 0 0

1 1 1

, WE = 14 1 0 10 0 01 0 1

.Ecuatia planului tangent suprafetei determinate n punctul de coordonate (m,n) (deci npunctul curent de calcul) este data de:

z = z0 +z(x, y)

x

(m,n)) (xm) + z(x, y)

y

(m,n)) (y n) (1.60)

deciz = f00 + C(xm) + D(y n) (1.61)

Deci, derivatele pe directiile orizontala si verticala (x si y), sunt date de coecientii C siD ai ecuatiei ce descrie suprafata de aproximare a imaginii n jurul pixelului (m,n). Dar,dupa cum se poate observa din forma mastile de determinare practica acestor coecienti,C si D sunt derivatele directionale obtinute prin mastile Prewitt.

Dupa cum se remarca din expresia de denitie a termenului de eroare patratica (1.47),ponderea diferitelor erori ce corespund pixelilor din vecinatatea utilizata (cu exceptiaoriginii, desigur, pentru ca suprafata de aproximare este constransa sa realizeze o eroarenula n punctul curent) este aceeasi, indiferent de distanta acestor diferite puncte fatade punctul central de coordonate (m,n). Se poate considera ca este mai important caaproximarea sa e mai buna pentru pixelii mai apropiati de pixelul considerat decatpentru pixelii situati la o distanta mai mare. In cazul folosirii unei masti 3 x3 patrate,centrate, ar putea deci considerat normal ca eroarea de aproximare a vecinilor imediati(pe linii si pe coloane) sa e ponderata cu un factor c (cu c > 1), astfel ncat contributiasa sae mai importanta decat cea ce corespunde vecinilor de pe diagonala. Daca se reiacalculul parametrilor A E ai suprafetei de aproximare, derivatele orizontal si verticala

17

C si D vor exprimate prin masti de gradient generalizate WC =1k

1 0 1c 0 c1 0 1

,WD =

1k

1 c 10 0 01 c 1

.

1.12 Abordarea topografica (cea mai potrivita cu-

bica)

Abordarea topograca [?, 145-146] face asocierea functiei tridimensionale construite pebaza reprezentarii nivelelor de gri a imaginii ca suprafata cu relieful unui teren, n carefrontierele dintre obiectele din imagine au rolul de creste si vai. Pentru detectia acestora,imaginea este modelata local cu o suprafata cubica (polinomiala de ordinul trei)

f(x, y) = k1 + k2x + k3y + k4x2 + k5xy + k6y

2 + k7x3 + k8x

2y + k9xy2 + k10y

3 (1.62)

Coecientii k1k10 se determina analog aproximarilor liniara si cuadrica, ntr-o vecinatatea ecarui pixel din imagine (vecinatate de dimensiune 5 x 5). Cum expresiile de calculale coecientilor sunt liniare dupa valorile pixelilor imaginii din vecinatatea considerata,coecientii vor putea calculati prin ltrarea liniara a imaginii (convolutie) prin mastile5 x 5 determinate.

Suprafata astfel determinata este apoi representata n coordonate polare prin

f(, ) = A3 + B2 + C+ k1 (1.63)

cu

A = k7 sin3 + k8 sin

2 cos + k9 cos2 sin + k10 cos

3 (1.64)

B = k4 sin2 + k5 sin cos + k6 cos

2

C = k2 sin + k3 cos

Atunci, derivatele partiale ale expresiei lui f(, ) sunt:

f(, )

= 3A2 + 2B + C

2f(, )

2= 6A + 2B

18

Deeterminarea vailor si crestelor se face pe baza

(2f(, )

2

)|=0 = 0 (1.65)

ceea ce conduce la a calcula B

= k5 cos 2 + (k4 k6) sin 2 = 0, de unde se determinadirectia tranzitiei ca

0 =1

2arctan

k5k6 k4 (1.66)

Pozitia 0 a tranzitiei se poate apoi determina dinf(,)

|=0 = 0 si conditia supli-

mentara ca < 0.5 (semnicand faptul ca tranzitia trebuie sa e apropiata de centrulferestrei de analiza curente).

1.13 Modelul Huckel

Acest model impune o forma liniara a dreptei de separatie ntre cele doua regiuni cuprinsen fereastra curenta de analiza. Valorile nivelului de gri n cele doua regiuni este constant,iar diferenta de nivel de gri este i; separatia dintre regiuni (muchia) este nclinata pedirectia fata de orizontala si este situata la distanta d fata de centrul ferestrei de analiza(gura 1.3). Fereastra de analiza folosita este patrata, de dimensiune relativ mare (2Nx 2N , cu N = 4 6) si este deplasata peste imagine din N n N pixeli, pe verticala siorizontala, ceea ce duce la suprapunerea de 50% a ferestrelor de analiza vecine.

Prin folosirea unei ferestre mari de analiza, tranzitiile abrupte nu sunt ngrosate n hartade contururi, iar prin determinarea variatiei muchiei n raport cu centrul ferestrei, latranslatia acesteia ntre pozitii succesive, muchiile sunt n general detectate n pozitiacorecta. Rezulattul operatorului nu este deci doar o unica valoare, reprezentand inten-sitatea maxima a tranzitiei locale (ca n cazul mastilor locale de gradient), ci un ntregsegment de dreapta, caracterizat de nclinare si pozitia n fereastra. Segmentul de dreaptaastfel determinat contribuie la harta de intensitati de tranzitie cu diferenta caracteristicade nivele de gri, i.

In modelul initial, detectia muchiei este redusa la o problema de optimizare, rezolvataaproximativ n coordonate spatiale continue. Daca se considera originea locala a sistemu-lui de coordonate n centrul ferestrei de analiza, muchia ideala este descrisa de modelul:{

sx+ ty = rs2 + t2 = 1

(1.67)

19

Fig. 1.3: Schema unei muchii liniare Hueckel.

iar functia imagine este descrisa n fereastra de analiza prin:

f(x, y, r, s, t, i,i) =

{i, sx + ty ri + i, sx + ty > r

(1.68)

Problema de optimizare consta n minimizarea erorii patratice de aproximare a imag-inii reale f prin modelul impus de prolul tranzitiei, f (cu un set xat de parametrir, s, t, i,i) pentru domeniul spatial ce corespunde ferestrei curente W .

2(r, s, t, i,i) =

W

(f(x, y) f(x, y, r, s, t, i,i)

)2dxdy (1.69)

Functiile f si f pot dezvoltate n serie dupa un set de functii de baza ortonormale{hk(x, y)}, avand ca suport fereastra W , ceea ce face posibila exprimarea erorii de aprox-

20

imare n functie de coecientii dezvoltarii n serie, Fk si Fk:

2(r, s, t, i,i) =

k=0

(Fk Fk(r, s, t, i,i)

)(1.70)

unde

Fk =

W

hk(x, y)f(x, y)dxdy, Fk =

W

hk(x, y)f(x, y, r, s, t, i,i)dxdy

Huckel a folosit o serie limitata de opt functii de baza, denite n ferestre circulare, pentrucare modelul muchiei aproximeaza doar componentele de joasa frecventa ale imaginiif(x, y) si care permit calculul parametrilor modelului cu un cost de calcul rezonabil (gura??). Complexitatea de calcul poate redusa folosind exprimarea functiilor de baza sitransformarea Fourier n coordonate polare. Chiar si asa, metoda nu este sucient dedirecta sau intuitiva.

1.13.1 Metoda Mero si Vassy

Metoda Mero si Vassy [?] permite identicarea rapida a unei frontiere liniare ce core-spunde unui model Huckel, prin determinarea parametrilor de nclinare si de distanta dfata de centrul ferestrei de analiza. Parametrul de nclinare al dreptei poate determinatprin utilizarea rezultatelor aplicarii mastilor h1 si h2 din gura 1.4 si combinarea acestoraprin

tan 1tan + 1

=f h1f h2 (1.71)

Fig. 1.4: Mastile de prelucrare folosite la determinarea orientarii muchiei din fereastra.

21

Dupa cum se remarca, obtinerea scalarilor f h1 si f h2 nu necesita decat operatii deadunare si scadere; o unica mpartire este deci necesara pentru a determina panta (tan)conturului. Mai mult, valoarea astfel calculata pentru orientarea conturului este relativstabila la prezenta zgomotului, ind dedusa printr-un calcul similar medierii valorilor dinimagine.

Determinarea parametrului de distanta la centrul ferestrei poate realizata pe bazaaceleiasi idei, de a minimiza diferenta dintre imaginea reala f si imaginea ideala, impusa

de modelul de muchie, f . Minimizarea erorii patratice 2 = (m,n) W(f(m,n) f(m,n))2este echivalenta cu maximizarea corelatiei dintre imaginea reala si imaginea model, =(m,n) Wf(m,n)f(m,n). Daca modelul este simplicat astfel ncat valorile lui fsa e +1 deasupra muchiei si -1 sub muchie, calculul corelatiei dintre imaginea reala siimaginea model revine la

(q) =

qj=1

f(j)N2

j=q+1

f(j) (1.72)

unde q este numarul de pixeli din imagine aati deasupra muchiei (si deci restul de N2qpixeli sunt situati sub muchie). Daca valorile imaginii din fereastra de analiza curente suntnormalizate (prin scaderea mediei valorilor f(m,n)), atunci suma valorilor din fereastra

este nula (N2

j=1 fnorm(j) = 0), ceea ce conduce la

qj=1

fnorm(j) = N2

j=q+1

fnorm(j) (1.73)

si atunci, evident, corelatia se poate scrie ca

(q) = 2

qj=1

fnorm(j) (1.74)

Asadar, corelatia ce trebuie maximizata este exprimata ca suma valorilor normalizate alepixelilor din fereastra de analiza situati deasupra muchiei cautate. Daca muchia modeleste translatata de-a lungul ferestrei de analiza, pastrandu-si directia, aceasta va ntalnipe rand toti pixelii din fereastra de analiza, ntr-o ordine determinata de distanta acestorafata de muchia modelului (dreapta nclinata la unghiul fata de orizontala) situata ncoltul din stanga sus al ferestrei de analiza. Pentru un pixel, a carui coordonate localesunt (m,n), aceasta distanta este

d2(m,n) =(m + (n 1) tan)2

1 + tan2 (1.75)

22

Cum numitorul expresiei este constant pentru un unghi dat, ordinea de parcurgere apunctelor va data doar de (m+ (n 1) tan)2.Odata ce este determinat maximul corelatiei (q) (1.74), din coordonatele pixelului pentrucare acest maxim este atins (si prin care trece muchia modelului) se poate calcula cuusurinta distanta pana la centrul ferestrei de analiza. In acest fel sunt parametrii muchiei;parametrii i si i + i pot determinati apoi ca nivelul de gri mediu al pixelilor situatide o parte si de alta a muchiei.

1.14 Detectia contururilor prin filtare optimala

Problema detectiei contururilor prin ltrare liniara se poate exprima ca proiectarea unuiltru a carui raspuns sa marcheze cu maxime bine denite pozitiile tranzitiilor din sem-nalul de intrare. Cazul de plecare este considerarea unor semnale mono-dimensionale(semnale de timp uzuale), n care contururile sunt modelate cu prin trepte de ampli-tudine, degradate cu zgomot Gaussian aditiv. Filtrul dedus trebuie sa e optimal, nsensul de a oferi cea mai buna performanta medie, pentru orice pozitie si intensitate atranzitiei si orice putere a zgomotului suprapus acesteia. Performanta de detectie a con-tururilor este masurata printr-o serie de caracteristici, precum detectia si localizarea bunaa tranzitiei, precum si minimizarea probabilitatii de detectie falsa prin maxime datorateexclusiv prezentei zgomotului.

Asadar, e semnalul de intrare f(x), compus dintr-o treapta ideala u(x) de amplitudineU0 si un zgomot aditiv, gaussian, de medie nula si putere N

20 , n(x):

f(x) = U0u(x) + n(x) (1.76)

Daca ltrul cautat are functia de pondere h(x), iesirea ltrului este data de

g(x) = f(x) h(x) =

f(t)h(x t)dt (1.77)

Cum tranzitia apare pentru x = 0, h(x) trebuie determinat astfel ncat g(0) sa e maximsi sa respecte constrangerile enuntate (buna detectie, buna localizare, evitare a maximelormultiple).

23

1.14.1 Proprietatea de buna detectie

Detectia este exprimata prin raportul semnal zgomot denit de raportul dintre raspunsulmaxim determinat doar de semnalul util si radicalul puterii zgomotului prezent la iesirealtrului:

RSZ =

U00

h(x t)dtE [ n(t)h(x t)dt2] = U0

0

h(x t)dt

N0

|h(t)|2 dt

(1.78)

Pentru obtinerea ultimei expresii am folosit teorema Parseval (echivalenta dintre putereaunui semnal calculata din spectrul de frecventa si din domeniul temporal) si proprietatilelegate de trecerea semnalelor aleatoare prin sisteme liniare. Pentru ca raspunsul ltruluih(x) la un semnl constant sa e nul, se alege o functie de pondere impara, pentru care0

h(t)dt +

0

h(t)dt = 0 si h(t) = h(t). Daca raportul este calculat pentru pozitiacorecta a tranzitiei, x = 0, se obtine

RSZ =U0N0

0

h(t)dt

|h(t)|2 dt

=U0N0

(1.79)

1.14.2 Proprietatea de buna localizare

Localizarea este masurata prin inversul variantiei distantei dintre maximul raspunsuluimaxim al ltrului si pozitia reala a tranzitiei (si deci 0 pentru modelul folosit). O lo-calizare buna nseamna o varianta mica a acestei distante si deci o valoare mare a inverseidistantei. Daca x0 este pozitia maximului semnalului de la iesirea ltrului, acesta va cor-spunde anularii primei sale derivate:(

g(x)

x

)|x=x0 =

(

xf(x) h(x)

)|x=x0 = (f(x) h(x)) |x=x0(

g(x)

x

)|x=x0 = U0 (u(x) h(x)) |x=x0 + (n(x) h(x)) |x=x0(

g(x)

x

)|x=x0 = U0

u(x0 t)h(t)dt+ (n(x) h(x)) |x=x0

24

(g(x)

x

)|x=x0 = U0

x0

h(t)dt+ (n(x) h(x)) |x=x0 = U0h(x0) + (n(x) h(x)) |x=x0

A fost folosita proprietatea h() = 0. Apoi, presupunand ca x0 nu este departat depozitia corecta (deci 0), h(x0) poate dezvoltat n serie Taylor truncheata n jurul lui x0ca h(x0) h(0) + x0h

(0). Dar functia h este impara, si atunci h(0) = 0 si:(g(x)

x

)|x=x0 = U0x0h(0) + (n(x) h(x)) |x=x0 (1.80)

In plus, h(x0) = h(0) = h(x0)/x0 si anularea derivatei(

g(x)x

)|x=x0 conduce la:

U0x0h(0) = (n(x) h(x)) |x=x0

U20x20 (h

(0))2 = |n(x) h(x)|2 |x=x0Cum x0 este o variabila aleatoare, ca si puterea de la iesirea ltrului determinata dezgomot, se aplica un operator de mediere statistica si se obtine:

U20 (h(0))2E

[x20]= E

[|n(x) h(x)|2

]|x=x0 = N20

|h(t)|2 dt (1.81)

E[x20]=

N20

|h(t)|2 dt

U20 (h(0))2

(1.82)

Cum variabila aleatoare x0 are medie nula (pentru ca presupunem ca estimarea pozitieitranzitiei se face ca o estimare nedeplasata printr-o eroare sistematica), atunci mediapatratica este egala cu varianta si localizarea (radical din inversul varaiantei) este:

1

E [x20]=

U0N0

|h(0)|

|h(t)|2 dt

=U0N0

(1.83)

eja se poate observa ca produsul dintre localizare si detectie nu mai depinde deamplitudinea tranzitiei si este invariant la schimbarea de scala, k:

=

0

h(t)dt

|h(t)|2 dt

|h(0)|

|h(t)|2 dt

(1.84)

ntr-adevar, considerand o varianta scalata a ltrului, hk(x) = h(x/k), atunci k =k

si k = /k (deci rezultand = kk).

25

1.14.3 Proprietatea de evitare a maximelor multiple

Pentru a reduce numarul de maxime de la iesirea ltrului (si pentru a nu avea raspunsurimultiple), va trebui minimizata densitatea trecerilor prin zero a raspunsului ltrului da-torate zgomotului. Aceasta densitate, d0 poate calculata printr-un model statistic.Pentru un proces Gaussian G(x) de medie nula si functie de autocorelatie BG(), densi-tatea trecerilor prin zero este

d0 =1

BG(0)BG(0)

(1.85)

In cazul considerat, raspunsul ltrului la zgomotul aplicat la intrare (G(x) = n(x)h(x))corespunde unui proces gaussian, atata vreme cat procesul de zgomot n(x) este alb, cudistributie Gaussiana. Atunci,

BG(0) =

qG()d = N20

|h(t)|2 dt (1.86)

unde qG() este densitatea spectrala de putere a raspunsului ltrului. In plus, avem

BG() = BG(), si atunci BG(0) = N20

|h(t)|2 dt. Atunci, densitatea trecerilor

prin zero ale raspunsului la zgomot al ltrului este

d0 =1

|h(t)|2 dt

|h(t)|2 dt(1.87)

Extremele semnalului de iesire (obtinut dupa ltrarea zgomotului) corespund tranzitiilordin semnalul de zgomot de la intrare; aceste extreme sunt nsa si trecerile prin zero alederivatei secunde ale semnalului de zgomot de la intrare, deci ale derivatei semnaluluide iesire (ntrucat ltrul h(x) este un derivator, avand un raspuns nul pentru un semnalconstant, g(x) = f(x) h(x) = f (x)). Atunci, nlocuind simbolic pe G(x) cu G(x)obtinem:

d0 =1

|h(t)|2 dt

|h(t)|2 dt(1.88)

Distanta medie dintre doua maxime datorate zgomotului va atunci 1/d0, iar distantamaxima dintre aceste maxime, xmax = 2/d0.

26

Toate aceste trei conditii sunt deci grupate ntr-o expresie de optimizat. In functie detipul de ltru ce se doreste (cu raspuns nit, sau cu raspuns innit), exista doua abordari:Canny si Deriche.

1.14.4 Abordarea Canny

Filtrul sintetizat de Canny are un raspuns nit la impuls, deci h(x) este o functie desuport marginit, [M,M ]. Conditia de evitare a maximelor multiple datorate zgomotuluicere ca numarul de maxime locale detectate ca raspuns la un unic contur sa e limitat,si distanta minima dintre maximele succesive sa e o fractiune din M (xmax = kmM).Atunci, ltrul h(x) este dedus prin maximizarea lui () cu constrangerea xmax = kmM .

Aceasta revina la a gasi h(x) care minimizeaza functionala

(x, h, h, h) = h2 + 1h2 + 2h2 + 3h (1.89)

si deci sunt solutiile ecuatiei

h

x

h+

2

x2

h= 0 (1.90)

sau, echivalent,2h(x) 21h(x) + 22h(x) + 3 = 0 (1.91)

Rezolvarea ecuatiei produce solutii de forma

h(x) = a1ex sinx+ a2e

x cosx+ a3ex sinx+ a4ex cosx (1.92)

cu 221/4 > 0, 22 = 1/22, 422 = (21 422)/422. Conditiile la limita impusesunt h(0) = 0, h(M) = 0, h(0) = S si h(0) = 0. Folosind tehnici numerice de optimizare,s-a dedus valoarea optima = 1.12. Cum ltrul ce rezulta este mult prea complex deimplementat, Canny a dedus ca ltrul DOG conduce la o valoare extrem de apropiata, = 0.92.

1.14.5 Abordarea Deriche

Deriche a propus sinteza unui ltru cu raspuns innit la impuls (deci cu M ). Solutiaecuatiei (1.92) este atunci

h(x) = ke|x| sinx (1.93)

si = 2/2 + 2. Daca consideram = m, atunci = 2m/

m2 + 1 si cazul cel

mai performant corespunde la m, pentru care rezulta = 2 sih(x) = 2xe|x| (1.94)

27