Detekcia hrán

Detekcia hrán (Šablóna:Vjz) je dôležitou oblasťou spracovania obrazu. Hrany sú miesta, kde sa prudko mení hodnota jasu. Typicky sa vyskytujú ako hranica medzi dvoma odlišnými regiónmi. Hrany sú jedny z dôležitých čŕt, ktoré môžu byť z obrázku extrahované. Detekcia hrán má preto časté použitie v úlohách počítačového videnia.

Hrana

Typy hrán

Hrana v obrázku je oblasť, kde sa rapídne mení jeho intenzita. Hrany môžeme rozdeliť na skokové (step) a impulzné (line). Pri skokovej hrane sa intenzita prudko mení z jednej hodnoty na inú. Pri impulznej hrane sa hodnota taktiež rapídne zmení, ale po istej vzdialenosti sa opäť vráti do počiatočnej hodnoty. Skokové a impulzné hrany sa však v reálnom svete vyskytujú veľmi zriedka. Na fotkách sú bežnejšie nábežné (ramp) a strechové (roof) hrany, pri ktorých zmeny jasu nie sú okamžité ale nastávajú postupne.

Kroky detekcie

Kroky v detekcii hrán: (a) pôvodný obrázok, (b) gaussovo rozmazanie, (c) kandidátske hrany (Sobelov detektor), (d) detekcia hrán (globálnym prahovaním)

1. Vyhladenie obrázku – ide o redukciu šumu, ktorý nevhodne ovplyvňuje výsledok detekcie.
2. Zvýraznenie – tento krok zahŕňa extrahovanie všetkých bodov, ktoré sú možnými kandidátmi na hrany (oblasti s výraznou zmenou intenzity).
3. Detekcia hrán – prahovaním alebo obdobnou technikou sa z kandidátskych bodov vyberú len tie, ktoré predstavujú hrany.

Delenie metód

1. Metódy založené na prvej derivácii jasovej funkcie – tieto metódy po výpočte prvej derivácie signálu vyhľadávajú extrém a predpokladajú že práve v ňom sa nachádza hrana. Príkladom sú Sobelov, Robertsov, Prewittov, Kirschov a Robinsonov operátor.
2. Metódy založené na druhej derivácii – tieto metódy po výpočte druhej derivácie signálu hľadajú prechod nulou a predpokladajú hranu na tomto mieste. Príkladom týchto metód sú  Laplacián a LOG.
3. Metódy založené na parametrizácii hrán – detegujú hrany s vopred známym tvarom. Príkladom môže byť Houghova transformácia.

Metódy založené na prvej derivácii

Metódy založené na prvej derivácii hľadajú hrany na miestach s vysokou hodnotou derivácie jasovej funkcie. Výpočet prvej derivácie (gradientu) aproximuje táto skupina metód pomocou konvolúcie určitým jadrom. Gradient je vektorom parciálnych derivácii a pre 2D signál ho definujeme ako:

$\mathrm{\nabla }f(x,y)=(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y})$

Gradient sa v polárnych súradniciach vyjadruje svojou veľkosťou a smerom:

$||\mathrm{\nabla }f(x,y)||=\sqrt{(\frac{\partial f}{\partial x}{)}^2+(\frac{\partial f}{\partial y}{)}^2}$ , $\psi =arctan(\frac{\partial f}{\partial y}/\frac{\partial f}{\partial x})$

Hranu je potom možné určiť hodnotou tohto gradientu, čo je smerom a veľkosťou.

$G=\sqrt{(G_x{)}^2+(G_y{)}^2}$ , $\psi =arctan\left(\frac{G_y}{G_x}\right)$

Smer $\psi$ s hodnotou 0 indikuje vertikálnu hranu, ktorá je tmavšia na ľavej strane. Hodnota 180 indikuje vertikálnu hranu s opačným smerom a hodnoty 90 a 270 ° indikujú zase hrany horizontálne.

Sobelov operátor

$h_1=\left[\begin{array}{ccc}1& 2& 1\\ 0& 0& 0\\ -1& -2& -1\end{array}\right]$, $h_2=\left[\begin{array}{ccc}-1& 0& 1\\ -2& 0& 2\\ -1& 0& 1\end{array}\right]$, $h_3=\left[\begin{array}{ccc}0& 1& 2\\ -1& 0& 1\\ -2& -1& 0\end{array}\right]$ atď.

V praxi sa používajú aj väčšie konvolučné jadrá. Pri zvýšení jeho veľkosti sa totiž hranový detektor stáva viac odolný voči šumu. Výhodou to taktiež býva u nízko kontrastných obrázkoch, kde sú hrany ťažko detegovateľné.

Príklad Sobelovho jadra 5x5:

$h_1=\left[\begin{array}{ccccc}1& 2& 0& -2& -1\\ 4& 8& 0& -8& -4\\ 6& 12& 0& -12& -6\\ 4& 8& 0& -8& -4\\ 1& 2& 0& -2& -1\end{array}\right]$, $h_2=\left[\begin{array}{ccccc}-1& -4& -6& -4& -1\\ -2& -8& -12& -8& -2\\ 0& 0& 0& 0& 0\\ 2& 8& 12& 8& 2\\ 1& 4& 6& 4& 1\end{array}\right]$ atď.

Príklad výpočtu

Konvolúciou zo vstupného obrázku a Sobelových jadier vypočítame $G_x$ a $G_y$. Z nich je následné možné dopočítať smer a veľkosť G. (Na rozšírenie obrázku sú použité krajné hodnoty.)

Následne je potrebné ešte dopočítať $G=\sqrt{(G_x{)}^2+(G_y{)}^2}$ . Keďže v $G_y$sú samé nuly G bude vyzerať rovnako ako $G_x$. Čím väčšie čísla budú v G tým je väčšia šanca že patria hrane.

Ako sa počíta konvolúcia:

(-1*0)+(-2*0)+(-1*0)+(0*0)+(0*0)+(0*0)+(1*10)+(2*10)+(1*10) = 40

Pri konvolúcii sa najprv preklopí jadro v x-ovom aj y-ovom smere. Následne sa odpovedajúce dvojice z pôvodného obrázku a jadra vynásobia a sčítajú.

Prewittov operátor

$h_1=\left[\begin{array}{ccc}1& 1& 1\\ 0& 0& 0\\ -1& -1& -1\end{array}\right]$, $h_2=\left[\begin{array}{ccc}-1& 0& 1\\ -1& 0& 1\\ -1& 0& 1\end{array}\right]$ atď.

Kirschov operátor

$h_1=\left[\begin{array}{ccc}5& 5& 5\\ -3& 0& -3\\ -3& -3& -3\end{array}\right]$, $h_2=\left[\begin{array}{ccc}5& 5& -3\\ 5& 0& -3\\ -3& -3& -3\end{array}\right]$ atď.

Robinsonov operátor

$h_1=\left[\begin{array}{ccc}1& 1& 1\\ 1& -2& 1\\ -1& -1& -1\end{array}\right]$, $h_2=\left[\begin{array}{ccc}1& 1& 1\\ -1& -2& 1\\ -1& -1& 1\end{array}\right]$ atď.

Robertsonov operátor

$h_1=\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]$, $h_2=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]$

Metódy založené na druhej derivácii

Metódy založené na druhej derivácii hľadajú priechod s nulou. Využíva sa tu to, že nájdenie priechodu s nulou je jednoduchšie ako hľadanie extrémov. Nevýhodou druhej derivácie je väčšia citlivosť na šum.

Laplaceov operátor

${\mathrm{\nabla }}^{2}f=(\frac{{\partial }^{2}f}{\partial x^2},\frac{{\partial }^{2}f}{\partial y^2})$

Laplaceov operátor (skrátene Laplacián) je invariantný voči rotácii (izotropný) a nedetekuje orientáciu.Je taktiež viac citlivý na šum. Laplacián môže byť implementovaný použitím jadra:

$h=\left[\begin{array}{ccc}0& 1& 0\\ 1& -4& 1\\ 0& 1& 0\end{array}\right]$

Laplacian-of-Gaussian (LOG)

Z dôvodu vysokej citlivosti druhej derivácie na šum, je vhodné výpočet kombinovať s vyhladením. V praxi zaviedol Laplacián Gaussianu, ktorý kombinuje Laplacián a Gaussove rozostrenie:

${\mathrm{\nabla }}^2[G(x,y,\sigma )*f(x,y)]$

Keďže druhá derivácia a konvolúcia sú lineárne operácie, preto je možné zmeniť postup výpočtu na:

$[{\mathrm{\nabla }}^{2}G(x,y,\sigma )]*f(x,y)$

Derivácia Gaussovského filtru môže byť predpočítaná dopredu keďže je nezávislá na vstupnom obrázku. Príklad LOG jadra 5x5:

$h=\left[\begin{array}{ccccc}0& 0& -1& 0& 0\\ 0& -1& -2& -1& 0\\ -1& -2& 16& -2& -1\\ 0& -1& -2& -1& 0\\ 0& 0& -1& 0& 0\end{array}\right]$

Cannyho detektor

Navrhol ho John Canny v roku 1986. Navrhol ho tak aby spĺňal 3 základné kritériá:

• kritérium detekcie – musia byť detegované všetky dôležité hrany a nesmú byť detegované miesta, kde sa hrana nenachádza
• lokalizačné kritérium – vzdialenosť medzi detegovanou hranou a skutočnou musí byť čo najmenšia
• kritérium jednej odozvy – operátor deteguje len jednu odozvu na každú hranu

Cannyho detektor je realizovaný v niekoľkých krokoch:

1. Vyhladenie obrázku Gaussovým filtrom
2. Výpočet gradientu aproximáciou prvej derivácie.
3. NonMaxima Supression – v gradientnom obraze sú potlačené hodnoty, ktoré nie sú lokálne maximá.
4. Eliminácia nevýznamných hrán – používa sa globálne prahovanie alebo prahovanie s hysteréziou (hysteresis thresholding).