Evidențierea marginilor

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 26 iunie 2016; verificările necesită 14 modificări .

Detectarea marginilor ( detecția marginilor ) - un termen din teoria procesării imaginilor și a vederii computerizate , parțial din domeniul căutării și selecției obiectelor, se bazează pe algoritmi care selectează puncte dintr-o imagine digitală în care luminozitatea se modifică brusc sau există şi alte tipuri de neomogenităţi.

Numire

Scopul principal al detectării schimbărilor bruște ale luminozității imaginii este de a surprinde evenimente și schimbări importante din lume. Acestea pot reflecta ipoteze diferite despre modelul de imagine, modificările luminozității imaginii pot indica:

modificări de adâncime;
modificări de orientare a suprafeței;
modificări ale proprietăților materialelor;
diferența de iluminare a scenei.

În mod ideal, rezultatul selecției limitelor este un set de curbe înrudite care reprezintă limitele obiectelor, fețelor și impresiilor pe o suprafață, precum și curbe care reprezintă modificări ale poziției suprafețelor. Astfel, aplicarea unui filtru de detectare a marginilor unei imagini poate reduce semnificativ cantitatea de date procesate datorită faptului că partea filtrată a imaginii este considerată mai puțin semnificativă, iar cele mai importante proprietăți structurale ale imaginii sunt păstrate. Cu toate acestea, nu este întotdeauna posibil să distingem granițele în imagini ale lumii reale de complexitate medie. Granițele extrase din astfel de imagini prezintă adesea astfel de neajunsuri precum fragmentarea (curbele granițelor nu sunt legate între ele), absența granițelor sau prezența unor limite false care nu corespund obiectului studiat.

Proprietăți chenar

Granițele evidențiate într-o imagine 2D a unei scene 3D pot fi subdivizate în cele dependente de punct de vedere sau independente de punct de vedere. Limitele independente de punct de vedere reflectă de obicei proprietățile moștenite de la obiectele dintr-o scenă 3D, cum ar fi culoarea suprafeței și forma. Limitele dependente de punctul de vedere se pot schimba odată cu punctul de vedere și pot reflecta geometria scenei, cum ar fi obiectele care se suprapun.

Un chenar normal poate fi, de exemplu, o chenar între blocuri roșii și galbene. Pe de altă parte, o linie poate fi un set de pixeli de o culoare diferită pe un fundal constant. Prin urmare, o linie poate avea o chenar pe fiecare parte a acesteia.

Marginile sunt destul de importante în multe aplicații de procesare a imaginilor, în special în sistemele de viziune artificială care analizează scene de obiecte artificiale în condiții fixe de iluminare. În ultimii ani, totuși, au existat studii consistente (și de succes) ale metodelor de viziune computerizată care nu se bazează pe detectarea marginilor ca pas de preprocesare.

Un model de bordură simplu

Deși unele literaturi iau în considerare selecția marginilor în trepte ideale, marginile dintr-o imagine naturală nu sunt de obicei. Ele sunt de obicei afectate de unul sau mai multe dintre următoarele efecte:

Focalizare încețoșată datorită fotografierii cu adâncime finită a câmpului,
Penumbra încețoșată de la surse de lumină non-punctuale,
Umbrirea obiectelor netede,

și, prin urmare, mulți cercetători folosesc marginea în trepte netezită de o funcție Gaussiană (funcția de eroare) ca cea mai simplă aproximare a modelului de margine ideal pentru modelarea limitelor neclare în probleme aplicate. Astfel, o imagine unidimensională care are exact o margine într-un punct poate fi modelată astfel: $f$ $x=0$

$f(x)={\frac {I_{r}-I_{l}}{2}}\left(\operatorname {erf} \left({\frac {x}{{\sqrt {2} }\sigma }}\right)+1\right)+I_{l}.$

Aici

\operatorname {erf} \,\left(u\right)={\frac {2}{\sqrt {\pi ))}\int \limits _{0}^{u}e^{-t ^{2}}\,dt

În stânga marginii este luminozitatea , în dreapta - . Parametrul se numește dimensiunea neclarității marginii. $I_{l}=\lim _{x\rightarrow -\infty }f(x)$ $I_{r}=\lim _{x\rightarrow \infty }f(x)$ $\sigma$

De ce selecția granițelor nu este o sarcină banală

Pentru a ilustra de ce detectarea marginilor este o problemă netrivială, luați în considerare problema detectării marginilor pe următorul semnal unidimensional. Aici putem spune imediat intuitiv că chenarul ar trebui să fie între al 4-lea și al 5-lea pixel.

5	7	6	patru	152	148	149

Dacă modificarea luminozității între al 4-lea și al 5-lea pixel ar fi mai mică, iar schimbarea luminozității între vecinii lor ar fi mai mare, nu ar mai fi atât de ușor să spunem că granița ar trebui să fie în acest loc. În plus, s-ar putea argumenta că ar trebui să existe mai mult de o graniță.

5	7	6	41	113	148	149

Prin urmare, fixarea greu a unui anumit prag asupra a ceea ce ar trebui să fie modificarea luminozității între doi pixeli adiacenți, astfel încât să putem spune că există o graniță, nu este întotdeauna o sarcină ușoară. Acesta este unul dintre motivele pentru care detectarea marginilor nu este o sarcină banală, cu excepția cazului în care obiectele din scenă sunt destul de simple și condițiile de iluminare sunt bine reglate.

Abordări ale detectării limitelor

Există multe abordări ale detectării marginilor, dar aproape totul poate fi împărțit în două categorii: metode bazate pe căutarea maximelor și metode bazate pe căutarea zerourilor. Metodele bazate pe vârfuri evidențiază marginile calculând „rezistența muchiei”, de obicei o expresie derivată prima, cum ar fi mărimea gradientului, și apoi căutând maximele locale ale rezistenței muchiei folosind direcția presupusă a muchiei, de obicei perpendiculară pe gradient. vector. Metodele bazate pe zero caută intersecții ale abscisei expresiei derivate a doua, de obicei zerouri ale Laplacianului sau zerouri ale unei expresii diferențiale neliniare, așa cum va fi descris mai târziu. Ca pas de preprocesare, netezirea imaginii este aproape întotdeauna aplicată la detectarea marginilor, de obicei cu un filtru gaussian.

Metodele de detectare a marginilor publicate diferă în filtrele anti-aliasing aplicate și în modul în care este calculată rezistența marginilor. Deși multe metode de detectare a marginilor se bazează pe calcularea gradientului unei imagini, ele diferă prin tipurile de filtre utilizate pentru a calcula gradienții în direcțiile x și y.

Evidențierea granițelor lui Canny

John Cannya studiat problema matematică a obținerii unui filtru optim în ceea ce privește selecția, localizarea și minimizarea mai multor răspunsuri ale unei muchii. El a arătat că filtrul dorit este suma a patru exponențiale. El a arătat, de asemenea, că acest filtru poate fi bine aproximat de prima derivată a Gaussianului. Canny a introdus conceptul de Non-Maximum Suppression (suprimarea non-maximelor), ceea ce înseamnă că pixelii de margine sunt declarați pixeli în care se atinge maximul local al gradientului în direcția vectorului gradient.

Deși munca sa a fost făcută în primele zile ale vederii computerizate, detectorul de margine Canny este încă unul dintre cei mai buni detectori de astăzi. Cu excepția cazurilor speciale, este dificil să găsești un detector care să aibă performanțe substanțial mai bune decât detectorul Canny.

Detectorul Canny-Deriché a fost derivat dintr-un criteriu matematic similar cu detectorul Canny, deși dintr-un punct de vedere diferit, a rezultat într-un set de filtre recursive pentru netezirea imaginii în loc de filtre exponențiale și gaussiene.

Alte metode de prim ordin

Pentru a estima mărimea unui gradient de imagine sau a versiunii sale netezite, pot fi aplicați diverși operatori de gradient. Cea mai simplă abordare este utilizarea diferențelor centrale:

L_{x}(x,y)=-1/2\cdot L(x-1,y)+0\cdot L(x,y)+1/2\cdot L(x+1,y ).

L_{y}(x,y)=-1/2\cdot L(x,y-1)+0\cdot L(x,y)+1/2\cdot L(x,y+1 ).

corespunzătoare aplicării următoarelor filtre la imagine:

L_{x}={\begin{bmatrix}-1/2&0&1/2\end{bmatrix}}*L\quad {\mbox{și}}\quad L_{y}={\begin{bmatrix} +1/2\\0\\-1/2\end{bmatrix}}*L

Cunoscutul operator Sobel se bazează pe următoarele filtre:

L_{x}={\begin{bmatrix}-1&0&+1\\-2&0&+2\\-1&0&+1\end{bmatrix}}*L\quad {\mbox{and}}\quad L_ {y}={\begin{bmatrix}+1&+2&+1\\0&0&0\\-1&-2&-1\end{bmatrix}}*L

Cu aceste estimări, putem calcula magnitudinea gradientului după cum urmează:

{\displaystyle |\nabla L|={\sqrt {L_{x}^{2}+L_{y}^{2))))

iar direcția gradientului se calculează astfel:

\theta =\operatorname {atan2} (L_{y}, L_{x})

Alți operatori pentru calcularea gradientului unei imagini au fost propuși de Judith Prewitt și Lawrence Roberts și sunt cunoscuți ca operator Pruitt și , respectiv, operator încrucișat Roberts .

Limitare și punere în comun

Odată ce am găsit puterea chenarului (de obicei, mărimea gradientului), următorul pas este să aplicăm un prag pentru a decide dacă chenarul se află sau nu într-un anumit punct al imaginii. Cu cât pragul este mai mic, cu atât vor fi mai multe margini, dar cu atât rezultatul va fi mai susceptibil la zgomot, evidențiind datele de imagine inutile. Dimpotrivă, un prag ridicat poate pierde marginile slabe sau poate primi o margine în fragmente.

Dacă pragul este aplicat pur și simplu imaginii cu magnitudinea gradientului, marginile rezultate vor fi groase și va fi necesară o post-procesare pentru a face marginea subțire și precisă. Dacă, totuși, limitele sunt selectate utilizând suprimarea non-maximă, granițele vor fi subțiri prin definiție și pot fi unite în poligoane prin procedura de îmbinare a marginilor (trasarea limitelor). Pe o grilă discretă, pasul de suprimare non-maximă poate fi implementat prin estimarea direcției gradientului folosind derivate prime, rotunjind direcția cu valori în incremente de 45 de grade și, în final, comparând valorile gradientului în direcția gradientului rezultat.

Abordarea tradițională pentru rezolvarea problemei găsirii unui prag adecvat este pragurile „târzii”. Metoda folosește mai multe praguri. Folosim pragul superior pentru a găsi punctul de început al graniței. Odată ce avem un punct de plecare, urmărim marginea, punct cu punct, până când valoarea forței marginii este peste pragul inferior. Acest algoritm presupune că marginile sunt cel mai probabil curbe continue și ne permite să urmărim zonele slabe ale marginilor fără a presupune că toate punctele zgomotoase din imagine vor fi etichetate drept margini. Cu toate acestea, există încă problema alegerii valorilor de prag adecvate pentru această metodă, deoarece parametrii optimi pot varia de la o imagine la alta.

Rafinarea limitei

Rafinarea granițelor este un proces care subțiază granițele prin eliminarea punctelor false nedorite care apar pe margine. Această tehnică este aplicată după ce imaginea a fost netezită (folosind un filtru median sau Gaussian), a fost aplicat un operator de margine (cum ar fi cel descris mai sus) pentru a calcula rezistența marginilor și după ce marginile au fost ștergete folosind praguri adecvate. Această metodă îndepărtează toate punctele nedorite și, atunci când este aplicată cu atenție, produce margini care au o grosime de un pixel.

Pro:

marginile ascuțite și subțiri îmbunătățesc eficiența recunoașterii obiectelor
atunci când utilizați transformarea Hough pentru a detecta linii sau elipse, marginile subțiri dau rezultate semnificativ mai bune
dacă granița este granița unei anumite zone, marginile subțiri vă permit să calculați parametri precum perimetrul fără nicio aritmetică complicată

Există multe metode populare pentru a rezolva această problemă. Unul dintre ele este descris mai jos:

Selectați tipul de conexiune: 8, 6 sau 4
- Este de preferat conectivitatea 8, care ia în considerare toți pixelii care înconjoară imediat pixelul curent
Ștergeți punctele de deasupra, dedesubt, stânga și dreapta unui punct
- Acest lucru ar trebui făcut în mai multe treceri, adică mai întâi eliminați puncte într-o direcție, apoi eliminați punctele în cealaltă direcție de pe imaginea procesată.
- Punctul se elimină în următorul caz:
  1. Acest punct nu are vecini de sus (în cazul procesării direcției "superioare", în caz contrar - în direcția corespunzătoare)
  2. Acest punct nu este sfârșitul liniei
  3. Eliminarea acestui punct nu va afecta în niciun fel conectivitatea vecinilor săi.
  4. SAU este un punct izolat
- În caz contrar, punctul nu este eliminat.
Pasul anterior poate fi repetat de mai multe ori, în funcție de nivelul dorit de „ordine” al chenarului.

Abordări de ordinul doi ale detectării limitelor

Unii operatori de selecție a marginilor folosesc derivate secunde ale luminozității imaginii în loc să lucreze cu un gradient. Acest lucru determină în mod natural puterea schimbării gradientului. Astfel, în cazul ideal, găsirea zerourilor derivatei a doua va face posibilă găsirea maximelor locale ale gradientului.

Operatorul Marr-Hildreth se bazează pe calcularea rădăcinilor operatorului Laplace aplicat unei imagini netezite de un filtru gaussian. Cu toate acestea, s-a demonstrat că acest operator evidențiază marginile false în zone omogene ale imaginii unde gradientul are un minim local. În plus, acest operator a localizat slab marginile rotunjite. Prin urmare, acest operator este acum mai degrabă de valoare istorică.

Detectare margine diferențială

O modalitate mai avansată de detectare a muchiilor de ordinul doi, care extrage, de asemenea, muchii cu precizie a pixelilor, este utilizarea următoarei abordări diferențiale pentru a detecta zerourile derivatei a doua în raport cu direcția vectorului gradient.

Să introducem în fiecare punct al imaginii un sistem local de coordonate , unde este direcția paralelă cu gradientul. Presupunând că imaginea a fost netezită cu un filtru gaussian și a fost calculată reprezentarea la scară pe scară , putem cere ca o valoare a gradientului de reprezentare a scalei care este egală cu derivata întâi în direcția - are o derivată întâi în direcția - egal cu zero $(u,v)$ $v$ $L(x,y;t)$ $t$ $L_{v}$ $v$ $v$

\partial _{v}(L_{v})=0

în timp ce derivata a doua în direcția - din trebuie să fie negativă, deoarece ne interesează doar maximele, adică: $v$ $L_{v}$

\partial _{vv}(L_{v})\leq 0

Scrisă ca o expresie explicită a derivatelor parțiale locale , … , această definiție a muchiei poate fi exprimată ca linii zero ale invariantului diferențial $L_{x)$ $L_{y)$ $L_{aaa)$

L_{v}^{2}L_{vv}=L_{x}^{2}\,L_{xx}+2\,L_{x}\,L_{y}\,L_{xy} +L_{y}^{2}\,L_{yy}=0,

care îndeplinește următoarea condiție:

L_{v}^{3}L_{vvv}=L_{x}^{3}\,L_{xxx}+3\,L_{x}^{2}\,L_{y}\, L_{xxy}+3\,L_{x}\,L_{y}^{2}\,L_{xyy}+L_{y}^{3}\,L_{yyy}\leq 0

unde , ... denotă derivate parțiale calculate pe reprezentarea la scară obținută prin filtrarea imaginii originale cu un filtru gaussian. $L_{x)$ $L_{y)$ $L_{aaa)$ $L$

În acest caz, marginile vor fi automat curbe continue cu precizie a pixelilor. Marginile rezultate pot fi aplicate suplimentar pentru evidențiere folosind prag întârziat.

În practică, primele derivate pot fi calculate așa cum s-a descris mai devreme, în timp ce derivatele secunde pot fi calculate din reprezentarea de scalare , după cum urmează: $L$

L_{xx}(x,y)=L(x-1,y)-2L(x,y)+L(x+1,y).

L_{xy}(x,y)=(L(x-1,y-1)-L(x-1,y+1)-L(x+1,y-1)+L(x +1,y+1))/4,

L_{yy}(x,y)=L(x,y-1)-2L(x,y)+L(x,y+1).

corespunzător următorilor operatori:

L_{xx}={\begin{bmatrix}1&-2&1\end{bmatrix}}*L\quad {\mbox{și}}\quad L_{xy}={\begin{bmatrix}-1/ 4&0&1/4\\0&0&0\\1/4&0&-1/4\end{bmatrix}}*L\quad {\mbox{and}}\quad L_{yy}={\begin{bmatrix}1\\-2 \\1\end{bmatrix}}*L

Derivatele de ordin superior pot fi calculate în mod similar.

Abordări de potrivire de fază

Cea mai recentă dezvoltare în tehnicile de detectare a marginilor utilizează o abordare a frecvenței pentru detectarea marginilor. Metodele de potrivire de fază încearcă să găsească zone din imagine în care toate sinusoidele din spațiul de frecvență sunt în fază. Aceste zone vor corespunde, de obicei, regiunilor marginii percepute, indiferent de cât de mult este schimbarea luminozității. Principalul avantaj al acestei metode este că accentuează puternic „ benzile Mach ” și evită granițele false tipice din jurul unei margini aspre.