Detekcia hrán

**Detekcia hrán** () 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
náhľad|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
náhľad|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)
# *Vyhladenie obrázku* – ide o redukciu šumu, ktorý nevhodne ovplyvňuje výsledok detekcie.
# *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).
# *Detekcia hrán* – prahovaním alebo obdobnou technikou sa z kandidátskych bodov vyberú len tie, ktoré predstavujú hrany.

## Delenie metód
# *Metódy založené na prvej [[Derivácia (funkcia)|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.
# *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.
# *Metódy založené na parametrizácii hrán* – detegujú hrany s vopred známym tvarom. Príkladom môže byť Houghova transformácia.

bezrámu|center

## 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:

\nabla f(x,y)=({\partial f \over \partial x },{\partial f \over \partial y })
stred|bezrámu|290x290bod
Gradient sa v polárnych súradniciach vyjadruje svojou veľkosťou a smerom:

||\nabla f(x,y)||=\sqrt{\Big( {\partial f \over \partial x }\Big) ^2 + \Big( {\partial f \over \partial  y }\Big) ^2} ,  \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. 
stred|bezrámu|265x265bod
G=\sqrt{\Big( {G_x }\Big) ^2 + \Big( {G_y}\Big) ^2}  ,  \psi=arctan \Big(\frac{G_y}{G_x}\Big)

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

bezrámu|435x435bod

Následne je potrebné ešte dopočítať  G=\sqrt{( {G_x }) ^2 + ( {G_y}) ^2} . Keďže v  G_ysú 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:

bezrámu|435x435bod

(-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
\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:

\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:

[\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:

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


## Referencie

## Iné projekty

Kategória:Spracovanie obrazu