Detecția Primară a Semnelor de Circulație în Imagini Digitale

Universitatea “Politehnica” din București

Facultatea de Electronică, Telecomunicații și Tehnologia Informației

Detecția primară a semnelor de circulație în imagini digitale

Proiect de diplomă

Prezentat ca cerință parțială pentru obținerea

titlului de Inginer

în domeniul Electronică, Telecomunicații și Tehnologia Informației programul de studii de licență Electronică aplicată

Conducător științific Absolvent

CONF.dr.ing. Corneliu FLOREA Romeo BORCĂIAȘ

Anul 2016

Declarație de onestitate academică

Prin prezenta declar că lucrarea cu titlul “Titlul complet al proiectului”, prezentată în cadrul Facultății de Electronică, Telecomunicații și Tehnologia Informației a Universității “Politehnica” din București ca cerință parțială pentru obținerea titlului de Inginer în domeniul Electronică, Telecomunicații și Tehnologia Informației, programul de studii Electronică aplicată, este scrisă de mine și nu a mai fost prezentată niciodată la o facultate sau instituție de învățămînt superior din țară sau străinătate.

Declar că toate sursele utilizate, inclusiv cele de pe Internet, sunt indicate în lucrare, ca referințe bibliografice. Fragmentele de text din alte surse, reproduse exact, chiar și în traducere proprie din altă limbă, sunt scrise între ghilimele și fac referință la sursă. Reformularea în cuvinte proprii a textelor scrise de către alți autori face referință la sursă. Înțeleg că plagiatul constituie infracțiune și se sancționează conform legilor în vigoare.

Declar că toate rezultatele simulărilor, experimentelor și măsurătorilor pe care le prezint ca fiind făcute de mine, precum și metodele prin care au fost obținute, sunt reale și provin din respectivele simulări, experimente și măsurători. Înțeleg că falsificarea datelor și rezultatelor constituie fraudă și se sancționează conform regulamentelor în vigoare.

București, data

Absolvent Romeo BORCĂIAȘ

_________________________

Lista figurilor

1. Introducere

2. Baza de date

3. Transformata Hough

Transformata Hough(Hough,1962) reprezintă o tehnică de detectare a formelor în imagini.

Această tehnică este utilizată în special în extracția dintr-o imagine dată a liniilor,cercurilor, elipselor(sau secțiuni conice). În cazul extracției liniilor,definiția matematică a acestei tehnici este echivalentă cu transformata Radon(Deans,1981). Transformata Hough a fost introdusă de Hough(Hough,1962) și mai apoi a fost folosită pentru a detecta in special structura circuitelor mai mult decât pentru detectia anumitor forme din imagini. Cu toate acestea, Rosenfeld a remarcat potențialele avantaje ale acestei tehnici în vederea utilizării acesteia ca și algoritm de procesare al imaginilor(Rosenfeld,1969). Transformata Hough a fost prin urmare implementată în detecția liniilor în imagini(Duda,1972) și a fost extinsă foarte mult deoarece are multe avantaje și un potențial foarte bun de îmbunătățire a tehnicii. Principalul avantaj al acestei metode este acela că aceasta poate furniza același rezultat ca si în cazul tehnicii de potrivire a modelului, însă mult mai rapid(Princen,1992),(Sklansky,1978) ,(Stockman,1977). Acesta este obținut printr-o reformulare a metodei de potrivire a modelului,bazat pe abordarea de colectare a datelor, unde evidența voturilor exprimate este realizată cu ajutorul unei matrice accumulator. Implementarea transformatei Hough definește o transformare de la imaginea ințială într-un spațiu de acumulatori(spațiu Hough). Această transformare este obținută într-un mod eficient,bazat pe o funcție care descrie forma vizată. Această mapare necesită mult mai puține resurse de calcul în comparație cu metoda de potrivire a modelului. Cu toate acestea este necesar un spațiu mare de stocare a datelor și o putere de calcul ridicată. Aceste probleme au fost însă abordate mai târziu,datorită concentrării asupra dezvoltării continue a transformatei Hough. În orice caz,faptul că transformata Hough este echivalentă cu metoda de potrivire a modelului a făcut ca transformata Hough să fie una dintre cele mai populare metode de detecție a formelor în imagini.

3.1. Transformata Hough pentru linii

În primul rând vom lua în considerare detecția liniilor într-o imagine. Într-o parametrizare carteziană, punctele colineare într-o imagine cu coordinate (x,y) sunt legate cu ajutorului pantei m și unei constanței c,astfel:

(1)

Ecuația poate fi scrisă sub forma omogenă astfel:

, (2)

unde A = -1/c si B = m/c. Prin urmare,o linie este definită printr-o pereche de valori (A,B). În orice caz,se poate observa o simtetrie în definiția din ecuația (2). Această ecuație este simetrică deoarece o pereche de coordonate (x,y) definește deasemenea o linie în spațiu cu parametrii (A,B). De aceea,ecuația (2) poate fi privită ca ecuația unei linii pentru coordonatele fixe (x,y) sau poate fi privită ca ecuația unei linii pentru parametrii ficși (A,B). Prin urmare,aceste perechi de valori pot fi folosite pentru a defini simultan puncte și linii(Aguado,2000a). Transformata Hough colectează date privind punctul (A,B) luând în considerare faptul că toate punctele (x,y) definesc aceeași linie în spațiul (A,B). De aceea,dacă setul de puncte colineare{(xi,yi)} determină dreapta (A,B),atunci:

Axi + Byi + 1 = 0 (3)

Această ecuație poate fi privită ca un sistem de ecuații și poate fi rescrisă mai simplu cu ajutorul parametrizarii carteziene:

c = -xim + yi (4)

Prin urmare,pentru a determina linia trebuie să găsim valorile parametrilor (m,c) (sau (A,B) în forma omogenă) care satisfac ecuația (4)(respectiv (3)). Cu toate acestea trebuie observat faptul că sistemul este în general supradeterminat. De aceea avem mai multe ecuații decât necunoscute. Prin urmare,trebuie să identificăm soluția care are cele mai mari șanse de a satisfice toate ecuațiile simultan. Această problemă poate fi rezolvată folosind diferite tehnici. Transformata Hough folosește o abordare a colecatarii de date pentru a furniza soluția. Relația între un punct (xi,yi) dintr-o imagine și dreapta dată de ecuația (4) este ilustrată în Figura 1. Punctele (xi,yi) și (xj,yj) din Figura 1.a definesc liniile Ui respectiv Uj din Figura 1.b. Toate punctele colineare dintr-o imagine vor defini linii duble cu același punct de intersecție (A,B) . Acest lucru este independent față de parametrizarea liniei. Transformata Hough rezolvă problema într-un mod eficient prin simpla numărare a posibilelor soluții într-o matrice accumulator care stochează probe sau voturi. Numărătoarea se face prin urmărirea tuturor liniilor duble pentru fiecare punct (xi,yi). Fiecare punct rezultat prin urmărirea liniilor incrementează un element al matricei,de aceea problema extracției liniei se transformă în problema localizării unui maxim în spațiul de acumulatori. Această strategie este robustă și a demonstrat că poate gestiona problema zgomotului și a ocluziei dintr-o imagine.

Figura 1 Ilustrarea transformatei Hough pentru linii

Axele în spațiul dublu reprezintă parametrii liniei. În cazul parametrizarii carteziene panta m poate lua o infinitate de valori, deoarece liniile pot varia de la linii orizontale până la linii verticale. Faptul că voturile sunt colectate într-o matrice discretă poate produce anumite erori. Există posibilitatea să considerăm un lanț de voturi în spațiul acumulatorilor care să acopere toate valorile posibile. Acest lucru este specific anumitor tehnici care pot îmbunătăți metoda de colectare a voturilor (Brown, 1983), (Kiryati, 1991). Este important să remarcăm faptul că ecuația (4) nu este potrivită pentru implementare deoarece parametrii pot lua o mulțime infinită de valori. Pentru a gestiona mulțimea infinită de valori pentru c, se vor folosi în implementare două matrice. Când panta m este între – 45° și – 45° atunci c nu ia valori foarte mari. Pentru alte valori ale lui m termenul liber c poate lua valori extrem de mari. Prin urmare, se consideră câte o matrice pentru fiecare caz. În al doilea caz se va folosi o matrice care stochează punctele de intersecție cu axa Ox. Acest lucru rezolvă problema doar parțial deoarece nu putem garanta că valoarea lui c va fi mică atunci când panta m este între – 45° și – 45°. Figura 2 ilustrează 3 exemple de localizare a liniilor într-o imagine folosind transformata Hough.În Figura 2(a) există o singură linie ce generează vârful pe care îl putem vedea în Figura 2(d).Mărimea vârfului este proporțională cu numărul de pixeli de pe linia din care a fost generat. Contururile semnului de circulație din Figura 2(b) și 2(c) determină două linii principale. Figura 2(c) conține mult mai mult zgomot decât Figura 2(b). Această imagine a fost obținută utilizând o valoare mai scăzută a pragului la folosirea operatorului de detectie a conturilor fapt care a determinat apariția unui zgomot mai mare. Acumulatorii rezultați pentru Figura 2(b) și 2(c) sunt reprezentați în Figura 2(e) respectiv 2(f). Se poate observă faptul că cele două matrice acumulatori au în linii mari aceeași formă,iar vârful,în fiecare dintre acestea este situat în același loc. Coordonatele vârfurilor sunt combinații ale parametrilor liniilor care redau cel mai bine imaginea. Numărul suplimentar de puncte ale conturului din imaginea semnului de circulație cu mai mult zgomot dau naștere mai multor voturi în spațiul de acumulatori,așa cum se poate observa prin creșterea numărului de voturi din Figura 2(f) în comparație cu numărul de voturi din Figura 2(e). Faptul că vârful este situat în același loc arată că transformata Hough poate tolera un zgomot destul de mare. Rezulatele extracției,atunci când acestea se suprapun pe conturul imaginii sunt illustrate în Figurile 2(g),2(h) respective 2(i). Doar cele două linii corespunzătoare vârfurilor semnificative au fost desenate pentru imaginea semnului de circulație. Așadar parametrii care descriu liniile au fost extrași în mod corespunzător. Se observă faptul că punctele din capetele liniilor nu sunt furnizate de transformata Hough,ci doar parametrii care le descriu. Pentru a obține lungimea segmentului obținut trebuie să revenim la imaginea inițială

Figura 2

Se poate observa faptul că transformata Hough furnizează un răspuns corect,estimând corect parametrii utilizați pentru a preciza linia,cu condiția ca numărul de puncte colineare de-a lungul acelei linii să depășească numărul de puncte colineare de pe oricare altă linie din imagine. În orice caz, neliniaritatea parametrilor și discretizarea produc acumulatori cu destul de mult zgomot. O problemă majoră în implementarea transformatei Hough pentru linii în forma ei inițială o reprezintă definirea unui spațiu accumulator adecvat. În practică, algoritmul desenului linear al lui Bresenham(Bresenham, 1965) poate fi utilizat pentru desenarea liniilor de voturi în spațiul de acumulatori. Acesta asigură că liniile voturilor conectate vor fi desenate în contrast pentru a folosi ecuația (4) care poate conduce la crearea unor lacune în linia trasată. Deasemenea backmapping (Gerig, 1986) poate fi folosită pentru a determina în mod exact care puncte ale conturului contribuie cu voturi pentru un anumit vârf. Tehnica de Backmapping este o mapare inversă din spațiul acumulatorilor la datele inițiale și poate permite analiza formei imaginii prin îndepărtarea punctelor ale conturului care contribuiau cu voturi pentru anumite vârfuri și apoi folosind transformata Hough are loc o re-acumulare. Este de notat faptul că în cazul transformatei Hough,costul de calcul depinde de numărul de puncte ale conturului (ne) și de lungimea liniilor formate în spațiul parametrilor(l),rezultând un cost de calcul de O(nel). Acest cost de calcul este considerabil mai redus decât în cazul tehnicii de potrivire a modelului,și anume O(n2m2). O cale de a evita problemele care se ivesc în urma parametrizarii carteziene în implementarea transformatei Hough este aceea de a pune bazele funcției de mapare utilizând o parametrizare alternativă. Una dintre cele mai potrivite tehnici este aceea numită parametrizarea foot-of-normal. Această tehnică parametrizează o linie considerând un punct (x,y) ca funcție al unui unghi perpendicular pe linie,trecând prin originea imaginii. Aceasta redă o formă a transformatei Hough cunoscută drept transformata Hough cu coordonate polare pentru linii (Duda, 1972).

Punctul în care această linie intersectează linia din imagine este dată de relația:

(5)

unde θ este unghiul format de normal la linie într-o imagine iar ρ este distanța de la origine la punctul în care cele două linii se intersectează, așa cum este ilustrat in Figura 3.

Figura 3 Reprezentarea in coordonate polare a unei linii

Tinand cont de faptul ca cele doua linii sunt perpendiculare daca produsul pantelor lor este -1 si considerand geometria din Figura 3,vom obtine:

(6)

Prin înlocuirea în Ecuația (1) vom obține forma polară,și anume Ecuația (5). Această prevede o funcție de mapare diferită:voturile sunt exprimate acum într-o formă sinusoidală într-o matrice acumulator 2D,în funcție de ρ și θ, parametrii de interes. Avantajul acestei alternative de mapare este acela că valorile parametrilor θ și ρ sunt obligate să ia valori într-un anumit interval. Gama de valori ale lui ρ este în intervalul [0;180o], valorile posibile ale lui ρ sunt date de dimensiunea imaginii, deoarece lungimea maximă a liniei este , unde N este dimensiunea matricei(pătratice). Din moment ce intervalul de valori este stabilit, tehnica poate fi pusă în practică. Implementarea transformatei Hough cu coordonate polare pentru linii este redată în cele ce urmează. Matricea acumululator este un set de 180 de locații pentru valori ale lui θ în intervalul [0;180o],și pentru valori ale lui ρ între 0 și,unde este dimensiunea imaginii. Apoi ,pentru punctele conturului imaginii mai mari decât un anumit prag ales, unghiul care face referire la dimensiunea locației este evaluat(ca radiani în intervalul [0;π]) iar mai apoi, valoarea lui ρ este evaluată utilizând Ecuația (5) și elementelele adecvate ale acumulatorului sunt incremetate atâta timp cât parametrii sunt în intervalul prestabilit. Matricea accumulator obținută prin aplicarea acestei implementări asupra imaginilor din Figura (2) este ilustrată în figura (4). Figura 4.a arată faptul că o singură linie definește un vârf bine delimitat. Figurile 4.b și 4.c redau faptul că vârfurile sunt mult mai clare în comparație cu implementarea parametrizării carteziene. Acest lucru se întâmplă deoarece efectele negative ale discretizării sunt reduse atunci când folosim parametrizarea polară. Această caracteristică face că implementarea transformatei Hough cu coordonate polare pentru linii să fie de departe mai eficientă și mai ușor de pus în practică decât versiunea cu coordonate carteziene.

Figura 4 Aplicarea transformatei Hough pentru linii utilizand coordonate polare

3.2. Transformata Hough pentru cercuri

Transformata Hough poate fi extinsă prin înlocuirea ecuației curbei în procesul de detecție. Ecuația curbei poate fi dată în mod explicit sau în formă parametrică. În forma explicită, transformata Hough poate fi definită considerând ecuația unui cerc ,care este dată de următoarea relație:

(7)

Această ecuație definește un loc geometric al punctelor centrate într-o origine si având raza . Această ecuație poate fi privită din două perspective:ca un loc geometric de puncte dintr-o imagine, sau ca un loc geometric de puncte centrate în cu raza . Figura 5 ilustrează această dublă definiție. Fiecare punct de margine determină un set ce cercuri în spațiul de acumulatori. Aceste cercuri sunt determinate de toate valorile posibile pe care le poate lua raza și sunt centrate în coordonatele punctului respectiv al conturului. Figura 5.b redă 3 cercuri determinate de 3 puncte ale conturului. Aceste cercuri sunt definite pentru o anumită valoare dată a razei. În realitate,fiecare punct al conturului determină cercuri pentru oricare alte valori ale razei. Aceasta implică faptul că spațiul acumulatorilor este tridimensional(pentru cei 3 parametrii de interes) iar punctele conturului mapează pentru un con de voturi în spațiul acumulatorilor. Figura 5.c ilustrează acest accumulator conic. După colectarea voturilor de la punctele conturului,maximul din spațiul acumulatorilor corespunde parametrilor cercului din imaginea inițială. Procedura utilizată pentru colectarea voturilor este aceeași ca și în cazul transformatei Hough pentru linii,dar voturile sunt generate în conuri,în conformitate cu Ecuația7.

Ecuația 7 poate fi definită în forma parametrică astfel:

(8)

Avantajul acestei reprezentări este acela că ne permite să rezolvăm pentru cazul parametric. Astfel,maparea transformatei Hough este definită prin:

(9)

Aceste ecuații definesc punctele din spațiul de acumulatori(Figura 5.b). și modul cum acestea depind de raza r. Este de notat faptul că θ nu este un parametru liber, însă acesta definește modul cum este trasată curbă. Trasarea curbei(sau a suprafeței) este denumită ca funcția de extindere a punctelor(the point spread function).

Implementarea transformatei Hough pentru cercuri este similară cu implementarea transformatei Hough pentru linii,cu excepția faptului că funcția de vot corespunde Ecuației (9) iar spațiul acumulator este pentru datele de cerc. În realitate,acumulatorul din implementare este 2D,în ceea ce privește parametrii centrului cercului pentru o valoare fixă a razei r,dată ca argument al funcției. Această funcție ar trebui apelată pentru toate valorile posibile ale razei. Un cerc de voturi este generat variind unghiul θ de la 0 la 360°. Discretizarea unghiului θ controlează granulația voturilor,o creștere mică oferă o acoperire foarte fină a spațiului parametric pe când o valoare mare se manifestă printr-o acoperire brută(rarefiată) a spațiului parametric. Spațiul accumulator este incrementat doar pentru puncte ale căror coordonate se află în intervalul spefcificat(în acest caz centrul cercului nu se poate afla în afara imaginii originale).

Figura 5 Transformata Hough pentru cercuri

Aplicarea transformatei Hough pentru cercuri este ilustrată în Figura 6. Figura 6.a prezintă o imagine cu un cerc sintetic, în care marginile sunt complete și bine definite. Rezultatul obținut în urma procesului de aplicare a transformatei Hough pentru cercuri este în figura 6.d. Vârful spațiului accumulator se află în centrul cercului. Este de notat faptul că există voturi și în depărtarea centrului cercului,iar acestea cresc cu cât ne apropiem de locul geometric al cercului real iar aceste voturi de fundal sunt mult mai puține decât cele corespunzătoare vârfului real. Figura 6.b prezintă un exemplu de imagine care conține ocluzii și zgomot. Imaginea 6.c corespunde aceleeași scene însă nivelul de zgomot din imagine a fost ridicat schimbând valoarea pragului în procesul de detecție a conturului. Acumulatorii pentru aceste două imagini sunt prezentați în Figurile 6.e respective 6.f iar cercurile ce corespund vârfurilor din spațiul acumulatorilor sunt suprapuse pe conturul imaginilor în Figurile 6.g, 6.h respectiv 6.i.

Figura 6 Aplicarea transformatei Hough pentru cercuri

Se poate observa faptul că transformata Hough pentru cercuri are capacitatea de a tolera ocluziile și zgomotul. Este de notat faptul că nu mai avem problema de mai devreme cu capetele liniilor deoarece cercul este o formă geometrică închisă. În Figura 6.c există multe punct ale conturului ceea ce implică creșterea timpului de procesare. Transformata Hough va detecta cercul(furnizează rezultatul corect) atâta timp cât,cât mai multe puncte sunt situate în locul geometric descris de parametrii cercului țintă decât sunt în locul geometric al oricărui alt cerc. Avem așadar aceleași performanțe ca în cazul transformatei Hough pentru linii,așa cum era de așteptat,și acestea sunt în concordanță cu rezultatele tehnicii de potrivire a modelului.

În codul aplicației,algoritmul lui Bresenham pentru cercuri discrete(Bresenham,1977) poate fi folosit pentru desenarea cercului de voturi decât să utilizăm implementarea în formă polară a Ecuației (9). Acesta asigura faptul că întreg locul geometric de puncte este desenat și evită să aleagă o valoare pentru creșterea unghiului de urmărire a cercului. Algoritmul lui Bresenham poate fi folosit pentru a genera puncte pe un octant(o optime de arc de cerc) până când punctele care rămân pot fi obținute prin reflexie. Din nou,tehnica backmapping poate fi folosită pentru a determina ce puncte au contribuit la extracția cercului.

Un exemplu suplimentar de extracție a cercurilor utilizând transformata Hough este prezentată în Figura 7. Figura 7.a reprezintă o imagine reală(cu toate că are o rezoluție scăzută) care a fost procesată de către algoritmul Sobel de detecție a conturului și a folosit un prag pentru a reda imaginea din Figura 7.b. Cercul detectat în urma aplicării transformatei Hough pentru cercuri cu rază de 5 pixeli,suprapus pe margini,este prezentat în Figura 7.c. Se poate vedea că cercul obținut se potrivește destul de bine cu marginile conturului. Acest lucru evidențiază două avantaje majore ale transformatei Hough,și anume capacitatea de a gestiona zgomotul și ocluziile care intervin într-o imagine. Este de reținut faptul că transformata Hough pur și simplu detectează cercul cu maximum de puncte. Este posibil însă ca algoritmul să introducă și alte constrângeri în vederea unui control mai bun al procesului de selecție, cum ar fi direcția gradientului pentru obiecte cu un profil de iluminare cunoscut. În cazul semnelor de circulație(cele în formă de cerc),în majoritatea cazurilor, partea centrală este de obicei mai întunecată, spre margini avem o zona de alb că mai apoi la margine să avem conturul cu roșu(de cele mai multe ori). Figura 7 prezintă totodată unele dintre dificultățile transformatei Hough și anume faptul că este în esență o implementare a tehnicii de potrivire a modelului și nu folosește o bună parte a informațiilor existente în imagine. Spre exemplu,am putea cunoaște constrângeri în ceea ce privește dimensiunea sau informații în ceea ce privește luminozitatea. Acești factori pot fi formulați ca și constrângeri dacă punctele conturului pot vota în matricea acumulator. O simplă modificare este aceea de a face numărul voturilor proporțional cu amplitudinea conturului, în acest fel, punctele cu un contrast ridicat vor genera mai multe voturi și prin urmare vor avea o semnificație mai mare în procesul de votare. În acest fel,caracteristica extrasă de transformata Hough poate fi particularizată pentru anumite aplicații.

Figura 7 Detectia cercurilor folosind transformata Hough

4. Detectia marginilor (Edge detection)

Prezentare generală

Vom defini câteva caracteristici de bază ale căror extracție dintr-o imagine se poate face automat fără a cunoaște informații despre forma respectivă(informații despre relațiile spațiale). Prăguirea(thresholding) este de fapt o facilitate de extracție de nivel scăzut efectuată ca o operație punctuală. În mod normal, toate aceste abordări pot fi utilizate în extracția de nivel ridicat a caracteristicii vizate, pentru identificarea formelor din imagini. Există tehnici de bază dar și tehnici mai avansate de aceea ar trebuie să ne îndreptăm către una dintre cele mai populare abordări. Detectorii de ordinul întâi sunt echivalenți cu diferențierea de ordinul întâi și, în mod natural, detectorii de ordinul doi sunt echivalenți cu un grad mai mare de diferențiere.

Multe abordări asupra imaginilor sunt bazate pe contur deoarece analiza bazată pe detecția contururilor este insensibilă la schimbarea nivelului general de iluminare. Detecția marginilor scoate în evidență cotrastul imaginilor. Detectand contrastul,care reprezintă diferența de intensitate,putem evidenția limitele unor caracteristici într-o imagine. În mod natural,vederea umană poate percepe forma unui obiect deoarece acesta are o intensitate luminoasă diferită față de vecinătățile sale. În esență,limita unui obiect reprezintă un pas de schimbare a intensității nivelelor de iluminare. Conturul reprezintă poziția pasului de schimbare. Pentru detecția marginilor putem folosi diferențierea de ordinul întâi din moment ce aceasta evidențiază schimbările. Diferențierea de ordinul întâi nu oferă niciun răspuns când este aplicat semnalelor ce nu se schimbă. Diferențierea de ordinal întâi utilizează operatori de ordinal întâi de detecție a marginilor,printre care: Roberts,Cross,Smoothing,Prewitt,Sobel or Canny.

4.1. Detectorul de contur “Canny”

Operatorul de detectie a marginilor Canny(Canny,1986) reprezinta poate cea mai populara tehnica de detectie a marginilor la momentul actual.

Operatorul Canny are 3 obiective importante:

1. detectie optima fara raspunsuri eronate;

2. o buna localizare cu o distanta cat mai mica intre pozitia reala a marginii si cea detectata ;

3. un singur raspuns,elimina raspunsurile multiple,il furnizeaza pec el mai apropiat.

Prima cerinta are ca scop de a reduce raspunsul la zgomot. Acesta poate fi afectat de netezire. Canny a fost primul ce a demonstrat ca filtrarea gaussiana este optima pentru detectia marginilor. Al doilea criteriu are drept obiectiv acuratetea : marginile trebuie sa fie detectate in locul potrivit. Acest lucru poate fi realizat printr-un proces de suprimare non-maxima(care este echivalenta cu detectia varfului). Suprimarea non-maxima retine doar acele puncte din partea superioara a unui lant de date ale marginii,in timp ce le suprima pe toate celelalte. Asta rezulta in subtiere : rezultatele suprimarii non-maxime sunt niste linii subtiri ale punctelor de margine,in locul potrivit. Cea de-a treia constrangere se refera la amplasarea unui singur punct de margine ca raspuns la o modificare a luminozitatii. Asta se intampla deoarece poate fi indicata mai mult decat o margine a fi prezenta, in concordanta cu rezultatele in cazul celorlalti operatori.

Operatorul Gaussian este dat de relatia:

(1)

Prin diferentiere, pentru vectorii unitate si de-a lungul axelor de coordonate,vom obtine:

(2)

Ecuatia (2) ne ofera o modalitate de a calcula coeficientii unui sablon care combina diferentierea de ordinal intai cu netezirea Gaussiana. Aceasta este o imagine netezita, asadar, marginea va fi o stratificare a datelor. Pentru a marca o margine in locul potrivit(si pentru a reduce raspunsurile multiple) putem prelucra imaginea cu un operator ce furnizeaza derivate intai pe o directive perpendicular pe margine. Maximul acestei functii ar trebui sa fie varful marginii de date,unde variatia in imaginea originala este foarte clara,fiind prin urmare locatia marginii. In consecinta, cautam un operator, ,care sa fie derivata intai a functiei gaussiene pe directia normalei ,:

(3)

unde poate fi estimat prin diferenta de ordinal intai a functiei Gaussiene convoluta cu imaginea si scalata corespunzator,astfel:

(4)

Amplasarea reala a punctului de margine este asadar maximul lui ,convolut cu imaginea.

Acest maxim are loc atunci cand diferentiala(de-a lungul ) este zero:

(5)

Prin inlocuirea (3) in Ecuatia (5) ,vom obtine:

(6)

Ecuatia (6) constituie baza unui operator care indeplineste unul din criteriile lui Canny,si anume ca marginile ar trebui detectate in locul corespunzator. Aceasta este suprimarea non-maxima care este echivalenta cu varfurile de retinere care scade sansele ca operatorul de detectie sa fie in locul potrivit, fara raspunsuri multiple si cu reactie minima la zgomot. In orice caz, este practice imposibil sa se realizeze o implementare exacta a detectiei Canny avand in vedere obligatia de a evalua directia normala.

O alternative de implementare a abordarii Canny(Deriche,1987) folosea criteriile Canny pentru a dezvolta filter bidimensionale recursive. In esenta,suprimarea non-maximala localizeaza cele mai inalte puncte din marginea de date. Acest lucru se realizeaza utilizand informatii despre directia marginii pentru a verifica ca puntele sunt situate in varful crestei. Data fiind o regiune de , un punct este maxim daca gradientul oricarui punct din vecinatatea sa este mai mic decat gradientul punctului respectiv. Acest lucru implica faptul ca avem nevoie de valori ale gradientului in lungul unei linii care este perpendiculara pe margine intr-un punct. Acest lucru este ilustrat in Figura 1 ,care prezinta punctele aflate in vecinatatile punctului de interes, , directia marginii la si perpendicular pe directia marginii la . Punctul trebuie marcat ca maximum daca gradientul sau, , este mai mare decat gradientul punctelor si respectiv si . Deoarece avem o multime discrete de vecinatati, si trebuie sa fie interpolate.

Figura 1 Interpolarea in suprimarea non-maximala

Interpolarea de ordinal intai,folosind si la si valorile si pentru vecinatati, este urmatoarea:

(7)

si

(8)

Punctul este apoi marcat ca un maxim daca depaseste valorile si , in caz contrar este setat la zero. In acest mod sunt pastrate varfurile muchiilor marginii in timp ce acele care nu sunt la varf sunt setate la zero. Implementarea suprimarii non-maximale necesita in primul rand o functie care sa genereze coordonatele punctelor intre care amplitudinea conturului este interpolata. O exemplificare functiei care genereaza aceste coordonate este prezentata in Figura 2. Aceasta functie are ca argument unghiul normalei pe directia conturului si returneaza coordonatele punctelor situate de o parte si de alta a normalei la contur.

Figura 2 Generarea coordonatelor pentru interpolare

Mai apoi,operatorul de suprimare non-maximala interpoleaza amplitudinea conturului in cele doua puncte situate de fiecare parte a normalei la directia conturului. Daca amplitudinea conturului in punctul de interes depaseste ca valoare cele doua puncte, acesta este pastrat, in caz contrar punctul este inlaturat. Posibilele singularitati din Ecuatiile (7) si (8) pot fi anulate prin folosirea multiplicarii in cazul comparatiei amplitudinii cee ace vine in contrast cu diviziunea folosita la interpolare. In practica, aceasta implementare poate duce la o imprecizie numerica, cee ace poate duce la un rezultat eronat. Prin urmare, este mai bine sa implementam o interpretare simplificata a Ecuatiilor (7) si (8), aplicate separate celor 4 cadrane.

Functia de transfer asociata cu histograma binarizarii este prezenta in Figura 3. Punctele sunt setate la alb odata ce pragul superior este depasit sau la negru atunci cand este atins pragul inferior. Sagetile figurate reflecta sensul posibil de miscare: exista doar o singura cale de a schimba de la negru la alb si viceversa.

Figura 3 Functia de transfer a praguirii cu histerezis

Aplicarea suprimarii non-maximale si a praguirii cu histerezis este ilustrata in Figura 4. Aceasta contine o creasta de date ale conturului care corespunde amplitudinii conturului. Actiunea de suprimare non-maximala presupune selectia punctelor de-a lungul partii superioare a crestei. Avand in vedere faptul ca partea superioara a crestei depaseste initial pragul superior, rezultatul binarizarii este setat la alb pana cand varful crestei scade sub pragul inferior. Rezultatul binarizarii este mai apoi setat la negru pana cand varful crestei depaseste pragul superior de comutare. Curba de histerezis necesita doua praguri, un prag inferior si unul superior. Procesul incepe in momentul cand se constata ca un punct al conturului din suprimarea non-maximala pragul superior de comutare. Acesta este etichetat ca un punct al conturului(de obicei alb,cu valoarea 255) si reprezinta primul punct din linia de puncte a conturului respective. Vecinatatile punctului sunt examinate pentru a determina daca acestea depasesc sau nu pragul inferior de comutare. Orice punct din vecinatate care depaseste pragul inferior de comutare este etichetat ca un punct al conturului iar mai apoi vecinatatile sale sunt examinate pentru a determina daca acestea depasesc sau nu pragul inferior de comutare. In acest mod, primul punct al conturului identificat(cel care depaseste pragul superior de comutare) devine punctul de plecare pentru alta cautare. Vecinii sai,in schimb,devin puncte de plecare a cautarii daca depasesc pragul inferior de comutare si astfel cautarea se extinde de-a lungul ramurilor care apar de la vecinatati care depasesc pragul inferior. Pentru fiecare ramura cautarea se terminca in momentul in care se intalnesc punctele care nu au vecini cu valori peste pragul inferior.

Figura 4 Suprimare non-maximala si praguire cu histerezis

La punerea in aplicare,praguirea cu histerezis necesita in mod clar recursivitate,deoarece lungimea oricarei ramificatii este necunoscuta. Dupa ce s-a gasit punctul initial de start,acesta este setat la alb iar apoi se fac cercetari asupra vecinatatilor sale. Coordonatele fiecarui punct sunt verificate pentru a daca se incadreaza in dimensiunea imaginii. Vecinatatea este mai apoi cautata cu ajutorul unei functii care are ca argument imaginea obtinuta prin suprimarea non-maximala,coordonatele punctului de start a carei conectivitate se analizeaza si pragul inferior de comutare. Fiecare dintre vecini este verificat daca valoarea lui depaseste pragul inferior de comutare si punctul nu a fost inca etichetat ca alb(in caz contrar functia ar deveni o bucla infinita). Daca ambele conditii sunt satisfacute(iar punctul este in imagine) atunci punctul este setat la alb si devine un punct de start pentru o analiza suplimentara. Aceasta implmentare incearca verificarea punctului de start chiar daca acesta a fost deja setat la alb. Operatorul ar putea fi setat sa nu verifice punctul de start current,prin calcul direct fara bucle for,iar acest process ar fi mai rapid. Adaugand o constrangere suplimentara booleana pentru a opri aceasta verificare a punctului de start current, nu ar face decat sa incetineasca intregul proces. Rutina care se executa este recursive, astfel incat aceasta este apelata de fiecare data de noul punct de start. Procesul incepe cu punctul care depaseste pragul superior de comutare. In momentul in care este gasit un astfel de punct, acesta este setat la alb si el devine un punct de start de unde incepe analiza asupra conectivitatii.