Cannyho hranový detektor

Cannyho hranový detektor je algoritmus zahrnující několik kroků pro získání co nejlepšího výsledku při detekci hran v dvourozměrném diskrétním obraze.

Požadavky při detekci

Minimální počet chyb (musí být detekovány všechny hrany, nesmí být detekována místa, která hranami nejsou)
Přesnost (poloha hrany musí být určena co nejpřesněji)
Jednoznačnost (odezva na jednu hranu musí být jedna, nesmí docházet ke zdvojení)

Doporučený postup

Eliminace šumu (Gaussovým filtrem)
Určení gradientu (první derivace)
Nalezení lokálních maxim (thinning)
Eliminace nevýznamných hran (thresholding)

Jednotlivé kroky

Eliminace šumu Gaussovým filtrem

Dvourozměrná varianta Gaussova normálního rozdělení je dána vztahem:

$G(x,y)={\frac {1}{2\pi \sigma ^{2}}}.e^{-{\frac {x^{2}+y^{2}}{2\sigma ^{2}}}}$

kde x,y jsou souřadnice pixelu v obraze a sigma je směrodatná odchylka rozděleni (běžně =1 až 1,4)

Výpočet je vhodné realizovat pomocí konvoluce. Vzorcem je tedy vypočtena pouze konvoluční maska, která se pak aplikuje na celý obraz.

Velikost a směr gradientu

Tedy standardní detekce hran. Nejvhodnější je využít Sobelův operátor, který není příliš citlivý na šum. Vrací nejen velikost gradientu (hrany) ale i její směr a ten je potřeba pro další kroky.

Ztenčení (Thinning)

Úkolem této funkce je vybrat z hodnot gradientů (stanovených v předchozím kroku) jen lokální maxima. Respektive odebrat body, které nejsou maximem (nonmaximum suppression). Tím zajistíme, že hrana bude detekována v místě největšího gradientu.

Prakticky to znamená najít pixely, jejichž okolí je ve směru a proti směru gradientu nižší. Máme-li například pixel, jímž prochází svislá hrana, musí být jeho levý a pravý soused nižší hodnoty (rozuměj hodnota jeho gradientu), aby byl „uznán“ jako skutečná hrana. Pokud podmínku nesplňuje,,je označen jako „není hrana“.

$E_{1}<E>E_{2}$

Které dva okolní pixely zahrnout do porovnávání, je dáno směrem gradientu (určeno v předchozím kroku).

Prahování (Thresholding)

Funkci můžeme nazývat prahování s hysterezí. V předchozím kroku jsme určili, kde přesně leží hrany, ale doposud jsme se nezabývali významem hran. V tuto chvíli jsou označeny i ty nejmenší hrany, protože i ty mají své lokální maximum. Není vhodné určit jeden práh, nad kterým budeme gradient považovat za významný, protože hodnota může kolísat například vlivem šumu.

Zvolíme tedy minimální (T1) a maximální (T2) hodnotu (prahy), mezi kterými může gradient kolísat. Pokud hodnota gradientu daného pixelu leží nad větším prahem T2 je přímo označen jako hranový. Pokud posuzujeme bod, jehož hodnota leží mezi T1 a T2, pak je „uznán“ jedině pokud sousedí s bodem, který už byl jako hrana označen dříve.

Programátorsky je vhodné použít rekurzivní funkci.

Odkazy

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu Cannyho hranový detektor na Wikimedia Commons