Derichův hranový detektor

Derichův hranový detektor je hranový operátor vyvinutý R. Derichem v roce 1987. Jedná se o vícekrokový algoritmus pro získání optimálního výsledku při detekci hran v diskrétním dvourozměrném obraze. Tento algoritmus vychází z práce Johna F. Cannyho a přebírá jak jednotlivé kroky hranové detekce, tak také navržená kritéria pro optimální hranový detektor, kterými jsou:

• Kvalita detekce – Musí být nalezeny všechny hrany v obraze, a naopak nesmí být za hrany označeny ty části obrazu, které jimi nejsou.
• Přesnost − nalezené hrany musí být tak blízko skutečné hraně v obraze, jak je to jen možné.
• Jednoznačnost − nalezená hrana v obraze je označena jako hrana pouze jednou, nesmí docházet ke vzniku vícenásobné odezvy na jednu hranu.

Z tohoto důvodu se často tento operátor označuje jako Cannyho-Derichův detektor.

Rozdíl mezi Cannyho a Derichovým hranovým detektorem

Derichův hranový detektor se skládá stejně jako Cannyho hranový detektor ze 4 kroků:

1. Eliminace šumu
2. Výpočet magnitudy a směru gradientu
3. Potlačení lokálních nemaxim
4. Prahování s hysterezí (pomocí dvou prahů)

Podstatný rozdíl je však v implementaci prvních dvou kroků algoritmu, kdy na rozdíl od Cannyho Derichův detektor používá IIR filtr ve tvaru:

$f(x)={\frac {S}{\omega }}e^{-\alpha |x|}sin\omega x$

který optimalizuje Cannyho kritéria. Jak je patrné z předcházejícího vzorce, nejefektivnější filtr získáme v případě, kdy se $\omega$ limitně blíží k 0. Takovýto filtr pak používá vzorec: $f(x)=Sxe^{-\alpha |x|}$

Výhodou takového filtru je existence pouhého jednoho parametru, jehož změnou můžeme přizpůsobit filtr podle vlastností zpracovávaného obrazu buď ve prospěch lepší detekce, pokud je hodnota $\alpha$ malá (pro obraz zatížený šumem se doporučuje hodnota parametru $\alpha$ v rozmezí 0.25 až 0.5), nebo naopak ve prospěch lokalizace, kdy se pro normální obrázky doporučuje α ≈ 1

Příklad vyhlazování derichovým 2D filtrem

Obrázek	Příklad vyhlazování derichovým filtrem 0.25	Příklad vyhlazování derichovým filtrem 0.5	Příklad vyhlazování derichovým filtrem 1	Příklad vyhlazování derichovým filtrem 2
α	α = 0.25	α = 0.5	α = 1	α = 2

Použití IIR filtru má velký smysl především v případech, kdy je zpracováván obraz zatížený šumem či je potřeba provádět vyhlazení obrazu filtrem s velkým konvolučním jádrem. V těchto případech má Derichův detektor značnou výhodu oproti Cannyho detektoru, protože je schopen zpracovat obraz v konstantním krátkém čase nezávislém na požadovaném množství vyhlazení.

Implementace Derichova detektoru

Algoritmus popisující získání hodnoty 2D Derichova filtru je možné rozdělit do dvou částí. V první části se provádí horizontální průchody zleva doprava podle vzorce:

$y_{ij}^{1}=a_{1}x_{ij}+a_{2}x_{ij-1}+b_{1}y_{ij-1}^{1}+b_{2}y_{ij-2}^{1}$

a zprava doleva dle:

$y_{ij}^{2}=a_{3}x_{ij+1}+a_{4}x_{ij+2}+b_{1}y_{ij+1}^{2}+b_{2}y_{ij+2}^{2}$

Výsledek prvního kroku se pak uloží do dočasného dvourozměrného pole:

$\theta _{ij}=c_{1}(y_{ij}^{1}+y_{ij}^{2})$

Druhý krok algoritmu je velice podobný prvnímu. Jako vstup zpracovává dvourozměrné pole z předcházejícího kroku, ale tentokrát provádí průchody ve vertikálním směru shora dolů a zdola nahoru podle následujících matematických vztahů:

$y_{ij}^{1}=a_{5}\theta _{ij}+a_{6}\theta _{i-1j}+b_{1}y_{i-1j}^{1}+b_{2}y_{i-2j}^{1}$

$y_{ij}^{2}=a_{7}\theta _{i+1j}+a_{8}\theta _{i+2j}+b_{1}y_{i+1j}^{2}+b_{2}y_{i+2j}^{2}$

$\Theta _{ij}=c_{2}(y_{ij}^{1}+y_{ij}^{2})$

Vzhledem k nezávislosti zpracovávaných řádků (respektive sloupců), která vyplývá z popisu algoritmu, se řešení založené na IIR filtru často používá na vestavěných systémech či architekturách umožňujících vysoký stupeň paralelizace, jako je např. NVIDIA CUDA.

Koeficienty Derichova filtru

	vyhlazení	x-ová derivace	y-ová derivace
$k$	${\frac {{(1-e^{-\alpha })}^{2}}{1+2\alpha e^{-\alpha }-e^{-2\alpha }}}$	${\frac {{(1-e^{-\alpha })}^{2}}{1+2\alpha e^{-\alpha }-e^{-2\alpha }}}$	${\frac {{(1-e^{-\alpha })}^{2}}{1+2\alpha e^{-\alpha }-e^{-2\alpha }}}$
$a_{1}$	$k$	0	$k$
$a_{2}$	$ke^{-\alpha }(\alpha -1)$	1	$ke^{-\alpha }(\alpha -1)$
$a_{3}$	$ke^{-\alpha }(\alpha +1)$	-1	$ke^{-\alpha }(\alpha +1)$
$a_{4}$	$-ke^{-2\alpha }$	0	$-ke^{-2\alpha }$
$a_{5}$	$k$	$k$	0
$a_{6}$	$ke^{-\alpha }(\alpha -1)$	$ke^{-\alpha }(\alpha -1)$	1
$a_{7}$	$ke^{-\alpha }(\alpha +1)$	$ke^{-\alpha }(\alpha +1)$	-1
$a_{8}$	$-ke^{-2\alpha }$	$-ke^{-2\alpha }$	0
$b_{1}$	$2e^{-\alpha }$	$2e^{-\alpha }$	$2e^{-\alpha }$
$b_{2}$	$-e^{-2\alpha }$	$-e^{-2\alpha }$	$-e^{-2\alpha }$
$c_{1}$	1	$-{(1-e^{-\alpha })}^{2}$	1
$c_{2}$	1	1	$-{(1-e^{-\alpha })}^{2}$

Při praktické implementaci Derichova detektoru se často využívá matematických vlastností algoritmu, kdy stačí vytvořit kód pouze pro jednu část algoritmu, která se pak volá dvakrát, přičemž mezi jednotlivými voláními se provede transpozice matice výsledku zpracování obrazu.

Několik příkladů použití Derichova filtru

Původní obraz	Slunečnice v Červenci	Kouzelník, kresba	Nástroj	List
Výsledný obraz	Hranový detektor	Hranový detektor	Hranový detektor	Hranový detektor
Parametry filtru	α = 1.5 spodní práh = 20 horní práh = 40	α = 4.0 spodní práh = 50 horní práh = 90	α = 0.8 spodní práh = 26 horní práh = 41	α = 1.0 spodní práh = 15 horní práh = 35

Odkazy

Literatura

• R. Deriche, Using Canny's criteria to derive a recursively implemented optimal edge detector, Int. J. Computer Vision, Vol. 1, pp. 167–187, April 1987.
• R. Sirdey, A Gentle Introduction to the Deriche Optimal Edge Detector, Éditions des Nik's news, 1998.
• J. Canny, A Computational Approach To Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8(6):679–698, 1986.

Související články

• Cannyho hranový detektor
• Filtr s nekonečnou impulzní odezvou
• Detekce hran

Externí odkazy

• Osobní stránka Rachida Deriche
• Přednáška Diane Lingrandové o hranových detektorech
• Osobní stránka Johna Cannyho