Cesko.wiki Derichův hranový detektor
Author
Albert FloresDerichů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é. +more * 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ů: # Eliminace šumu # Výpočet magnitudy a směru gradientu # Potlačení lokálních nemaxim # 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. +more 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. +more5), nebo naopak ve prospěch lokalizace, kdy se pro normální obrázky doporučuje α ≈ 1.
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_1x_{ij}+a_2x_{ij-1}+b_1y_{ij-1}^1+b_2y_{ij-2}^1
a zprava doleva dle:
: y_{ij}^2=a_3x_{ij+1}+a_4x_{ij+2}+b_1y_{ij+1}^2+b_2y_{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_1y_{i-1j}^1+b_2y_{i-2j}^1
: y_{ij}^2=a_7\theta_{i+1j}+a_8\theta_{i+2j}+b_1y_{i+1j}^2+b_2y_{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.
| 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.
| Původní obraz | +more65'>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. +more 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
[url=http://www-sop. inria. +morefr/athena/Site/RachidDeriche]Osobní stránka Rachida Deriche[/url] * [url=http://users. polytech. unice. fr/~lingrand/Ens/up/Lesson7and8-segmentation. pdf]Přednáška Diane Lingrandové o hranových detektorech[/url] * [url=http://www. cs. berkeley. edu/~jfc/]Osobní stránka Johna Cannyho[/url].