Detekcia hrán

Detekcia hrán (angl. edge detection) 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:

${\textstyle \nabla f(x,y)=({\partial f \over \partial x},{\partial f \over \partial y})}$

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

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

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

${\textstyle G={\sqrt {{\Big (}{G_{x}}{\Big )}^{2}+{\Big (}{G_{y}}{\Big )}^{2}}}}$ , ${\textstyle \psi =arctan{\Big (}{\frac {G_{y}}{G_{x}}}{\Big )}}$

Smer ${\textstyle \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}={\begin{bmatrix}1&2&1\\0&0&0\\-1&-2&-1\end{bmatrix}}$, $h_{2}={\begin{bmatrix}-1&0&1\\-2&0&2\\-1&0&1\end{bmatrix}}$, $h_{3}={\begin{bmatrix}0&1&2\\-1&0&1\\-2&-1&0\end{bmatrix}}$ 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}={\begin{bmatrix}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{bmatrix}}$, $h_{2}={\begin{bmatrix}-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{bmatrix}}$ atď.

Príklad výpočtu

Konvolúciou zo vstupného obrázku a Sobelových jadier vypočítame ${\textstyle G_{x}}$ a ${\textstyle 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ť ${\textstyle G={\sqrt {({G_{x}})^{2}+({G_{y}})^{2}}}}$ . Keďže v ${\textstyle G_{y}}$sú samé nuly G bude vyzerať rovnako ako ${\textstyle 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}={\begin{bmatrix}1&1&1\\0&0&0\\-1&-1&-1\end{bmatrix}}$, $h_{2}={\begin{bmatrix}-1&0&1\\-1&0&1\\-1&0&1\end{bmatrix}}$ atď.

Kirschov operátor

$h_{1}={\begin{bmatrix}5&5&5\\-3&0&-3\\-3&-3&-3\end{bmatrix}}$, $h_{2}={\begin{bmatrix}5&5&-3\\5&0&-3\\-3&-3&-3\end{bmatrix}}$ atď.

Robinsonov operátor

$h_{1}={\begin{bmatrix}1&1&1\\1&-2&1\\-1&-1&-1\end{bmatrix}}$, $h_{2}={\begin{bmatrix}1&1&1\\-1&-2&1\\-1&-1&1\end{bmatrix}}$ atď.

Robertsonov operátor

$h_{1}={\begin{bmatrix}1&0\\0&-1\end{bmatrix}}$, $h_{2}={\begin{bmatrix}0&-1\\1&0\end{bmatrix}}$

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

${\textstyle \nabla ^{2}f=({\partial ^{2}f \over \partial x^{2}},{\partial ^{2}f \over \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={\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}$

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:

${\textstyle \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:

${\textstyle [\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={\begin{bmatrix}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{bmatrix}}$

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).

Iné projekty

Commons

• Commons ponúka multimediálne súbory na tému Detekcia hrán