Dericheův detektor hran - Deriche edge detector

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Březen 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Dericheův detektor hran je Detekce hrany operátor vyvinutý společností Rachid Deriche v roce 1987. Je to vícestupňový proces algoritmus slouží k získání optimálního výsledku detekce hran v diskrétním dvourozměrném obrazu. Tento algoritmus je založen na John F. Canny práce související s detekcí hran (Cannyho detektor hran ) a jeho kritéria pro optimální detekci hran:

• Kvalita detekce - všechny existující hrany by měly být označeny a nemělo by dojít k falešné detekci.
• Přesnost - označené okraje by měly být co nejblíže okrajům skutečného obrázku.
• Jednoznačnost - daná hrana na obrázku by měla být označena pouze jednou. Ve skutečném obrazu by nemělo dojít k více reakcím na jednu hranu.

Z tohoto důvodu se tento algoritmus často označuje jako Canny-Dericheův detektor.

Rozdíly mezi hranovým detektorem Canny a Deriche

Dericheův detektor hran, jako Hranatý detektor hran, se skládá z následujících 4 kroků:

1. Vyhlazení
2. Výpočet velikosti a směru gradientu
3. Non-maximální potlačení
4. Hystereze prahování (pomocí dvou prahů)

Zásadní rozdíl je v implementace prvních dvou kroků algoritmu. Na rozdíl od detektoru hran Canny používá detektor hran Deriche IIR filtr ve formě:

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

Filtr optimalizuje Cannyho kritéria. Jak je patrné z předchozího vzorce, nejúčinnější filtr se získá, když je hodnota ${ displaystyle omega}$ přístupy 0. Takový filtr pak používá vzorec:

${ displaystyle f (x) = Sxe ^ {- alfa | x |}}$

Výhodou takového filtru je, že jej lze přizpůsobit charakteristikám zpracovávaného obrazu pouze pomocí jednoho parametru. Pokud je hodnota α malá (obvykle mezi 0,25 a 0,5), vede to k lepší detekci. Na druhou stranu je lepší lokalizace dosažena, když má parametr vyšší hodnotu (kolem 2 nebo 3). Pro většinu běžných případů se doporučuje hodnota parametru kolem 1.

Příklad vyhlazení pomocí Dericheova filtru

obraz
α	a = 0,25	α = 0,5	α = 1	α = 2

Použití filtru IIR má smysl zejména v případech, kdy je zpracovaný obraz hlučný nebo je vyžadováno velké množství vyhlazení (což vede k velkému konvolučnímu jádru pro filtr FIR). V těchto případech má Dericheův detektor značnou výhodu oproti Cannyho detektoru, protože je schopen zpracovávat obrazy v krátké konstantní době nezávisle na požadovaném množství vyhlazení.

Implementace detektoru Deriche

Je možné rozdělit proces získávání hodnoty dvourozměrného Dericheova filtru na dvě části. V první části je obrazové pole předáváno ve vodorovném směru zleva doprava podle následujícího vzorce:

${ displaystyle 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 podle vzorce:

${ displaystyle 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 výpočtu se poté uloží do dočasného dvojrozměrného pole:

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

Druhý krok algoritmu je velmi podobný prvnímu kroku. Jako vstup se použije dvourozměrné pole z předchozího kroku. Poté se předává ve svislém směru shora dolů a zdola nahoru podle následujících vzorců:

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

${ displaystyle 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}}$

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

Z popisu algoritmu vyplývá, že zpracované řádky a sloupce jsou na sobě nezávislé. Výsledkem je, že řešení založené na filtru IIR se často používá ve vestavěných systémech a architekturách, které podporují vysokou úroveň paralelizace.

Dericheovy koeficienty filtru

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

Matematické vlastnosti algoritmu se často používají při praktické implementaci Dericheova detektoru. Při provádění transpozice výsledné matice stačí implementovat pouze jednu část algoritmu, která je poté volána dvakrát.

Příklady použití Dericheova filtru na různých zdrojových obrázcích

Zdrojový obrázek
Filtrovaný obrázek
Parametry filtru	α = 1,5 nízký práh = 20 vysoký práh = 40	a = 4,0 nízký práh = 50 vysoký práh = 90	α = 0,8 nízký práh = 26 vysoký práh = 41	α = 1,0 nízký práh = 15 vysoký práh = 35

Viz také

• Hranatý detektor hran
• IIR
• Detekce hrany

Další čtení

• R. Deriche, Použití Cannyho kritérií k odvození rekurzivně implementovaného optimálního detektoru hran, Int. J. Computer Vision, sv. 1, s. 167–187, duben 1987.
• R. Sirdey, Jemný úvod do detektoru optimálních hran DericheZprávy Éditions des Nik, 1998.
• J. Canny, Výpočetní přístup k detekci hran, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8 (6): 679–698, 1986.

externí odkazy

• Osobní stránka Rachid Deriche
• Přednáška Diane Lingrandové o detektorech hran
• Osobní stránka Johna Cannyho