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 

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 

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

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:

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

 ,  

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

  ,  

Smer  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 
, ,  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:

,   atď.

Príklad výpočtu 
Konvolúciou zo vstupného obrázku a Sobelových jadier vypočítame  a . 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ť   . Keďže v  sú samé nuly G bude vyzerať rovnako ako . Čí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 
,  atď.

Kirschov operátor 
,  atď.

Robinsonov operátor 
,  atď.

Robertsonov operátor 
,

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 

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:

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:

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

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:

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 

Spracovanie obrazu