Виявляч контурів Деріша

Виявля́ч ко́нтурів Дері́ша (англ. Deriche edge detector) — це оператор виявляння контурів, розроблений Рашидом Дерішем 1987 року. Це багатокроковий алгоритм, який використовують для отримання оптимального результату виявляння контурів на дискретному двовимірному зображенні. Цей алгоритм ґрунтується на праці Джона Ф. Кенні, пов'язаній з виявлянням контурів (виявляч контурів Кенні), та його критеріях оптимального виявляння контурів:

• Якість виявляння — всі наявні контури повинно бути позначено, і не повинно ставатися хибного виявляння.
• Точність — позначені контури повинні бути якомога ближче до контурів на реальному зображенні.
• Однозначність — заданий контур на зображенні повинно бути позначено лише один раз. Не повинно ставатися кількох відгуків на один контур на реальному зображенні.

З цієї причини цей алгоритм часто називають виявлячем Кенні — Деріша.

Відмінності між виявлячами контурів Кенні та Деріша

Виявляч контурів Деріша, подібно до виявляча контурів Кенні, складається з таких 4 кроків:

1. Згладжування
2. Обчислення величини та напрямку градієнта
3. Придушування немаксимумів
4. Гістерезисне порогування (з використанням двох порогових значень)

Істотна відмінність полягає у втіленні перших двох кроків алгоритму. На відміну від виявляча контурів Кенні, виявляч контурів Деріша використовує НІХ-фільтр вигляду

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

Цей фільтр оптимізує критерії Кенні. Як видно з попередньої формули, найефективніший фільтр виходить при наближенні значення $\omega$ до 0. Тоді такий фільтр використовує формулу

$f(x)=Sxe^{-\alpha |x|}$

Перевага такого фільтра полягає в можливості пристосовування до характеристик оброблюваного зображення за допомогою лише одного параметра. Якщо значення α мале (зазвичай між 0,25 та 0,5), це призводить до кращого виявляння. З іншого боку, кращої локалізації досягають, коли параметр має вище значення (близько 2 або 3). Для більшості звичайних випадків рекомендовано значення параметра близько 1.

Приклад згладжування фільтром Деріша

Зображення
α	α = 0,25	α = 0,5	α = 1	α = 2

Використання НІХ-фільтра має сенс особливо у тих випадках, коли оброблюване зображення зашумлене або вимагає великого згладжування (що веде до великого ядра згортки для НІХ-фільтра). У цих випадках виявляч Деріша має значну перевагу над виявлячем Кенні, оскільки він здатний оброблювати зображення за короткий сталий час незалежно від бажаної величини згладжування.

Втілення виявляча Деріша

Процес отримання значення двовимірного фільтра Деріша можливо розділити на дві частини. У першій масив зображення проходять у горизонтальному напрямку зліва вправо за такою формулою:

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

і справа вліво за формулою:

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

Результат обчислення відтак зберігають у тимчасовому двовимірному масиві:

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

Другий крок алгоритму дуже схожий на перший. Як вхід використовують двовимірний масив із попереднього кроку. Його відтак проходять у вертикальному напрямку згори вниз і знизу вгору за такими формулами:

$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})$

З опису алгоритму випливає, що оброблювані рядки й стовпці незалежні один від одного. Як наслідок, рішення на основі НІХ-фільтра часто використовують у вбудованих системах та архітектурах, які підтримують високий рівень розпаралелювання.

Коефіцієнти фільтра Деріша

	згладжування	похідна за x	похідна за y
$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}$

Математичні властивості цього алгоритму часто використовують при практичному втілюванні виявляча Деріша. Достатньо втілити лише одну частину алгоритму, яка потім викликають двічі, виконуючи транспонування результатної матриці.

Приклади використання фільтра Деріша на різних вхідних зображеннях

Первинне зображення
Профільтроване зображення
Параметри фільтра	α = 1,5 нижній поріг = 20 верхній поріг = 40	α = 4,0 нижній поріг = 50 верхній поріг = 90	α = 0,8 нижній поріг = 26 верхній поріг = 41	α = 1,0 нижній поріг = 15 верхній поріг = 35

Див. також

• Виявляч контурів Кенні
• НІХ
• Виявляння контурів

Література

• 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 Transactions on Pattern Analysis and Machine Intelligence, 8(6):679–698, 1986. (англ.)

Посилання

• Особиста сторінка Рашида Деріша (англ.)
• Лекція Діани Лінґранд про виявлячі контурів (англ.)
• Особиста сторінка Джона Кенні (англ.)