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

Шаблон:Виявляння ознак (комп'ютерний зір)

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

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

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

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

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

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

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

f (x) = \frac{S}{ω} e^{- α | x |} \sin ω x

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

f (x) = S x e^{- α | x |}

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

Приклад згладжування фільтром Деріша
Зображення
α	α = 0,25	α = 0,5	α = 1	α = 2

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

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

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

y_{i j}^{1} = a_{1} x_{i j} + a_{2} x_{i j - 1} + b_{1} y_{i j - 1}^{1} + b_{2} y_{i j - 2}^{1}

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

y_{i j}^{2} = a_{3} x_{i j + 1} + a_{4} x_{i j + 2} + b_{1} y_{i j + 1}^{2} + b_{2} y_{i j + 2}^{2}

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

θ_{i j} = c_{1} (y_{i j}^{1} + y_{i j}^{2})

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

y_{i j}^{1} = a_{5} θ_{i j} + a_{6} θ_{i - 1 j} + b_{1} y_{i - 1 j}^{1} + b_{2} y_{i - 2 j}^{1}

y_{i j}^{2} = a_{7} θ_{i + 1 j} + a_{8} θ_{i + 2 j} + b_{1} y_{i + 1 j}^{2} + b_{2} y_{i + 2 j}^{2}

Θ_{i j} = c_{2} (y_{i j}^{1} + y_{i j}^{2})

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

Коефіцієнти фільтра Деріша
	згладжування	похідна за x	похідна за y
$k$	$\frac{{(1 - e^{- α})}^{2}}{1 + 2 α e^{- α} - e^{- 2 α}}$	$\frac{{(1 - e^{- α})}^{2}}{1 + 2 α e^{- α} - e^{- 2 α}}$	$\frac{{(1 - e^{- α})}^{2}}{1 + 2 α e^{- α} - e^{- 2 α}}$
$a_{1}$	$k$	0	$k$
$a_{2}$	$k e^{- α} (α - 1)$	1	$k e^{- α} (α - 1)$
$a_{3}$	$k e^{- α} (α + 1)$	-1	$k e^{- α} (α + 1)$
$a_{4}$	$- k e^{- 2 α}$	0	$- k e^{- 2 α}$
$a_{5}$	$k$	$k$	0
$a_{6}$	$k e^{- α} (α - 1)$	$k e^{- α} (α - 1)$	1
$a_{7}$	$k e^{- α} (α + 1)$	$k e^{- α} (α + 1)$	-1
$a_{8}$	$- k e^{- 2 α}$	$- k e^{- 2 α}$	0
$b_{1}$	$2 e^{- α}$	$2 e^{- α}$	$2 e^{- α}$
$b_{2}$	$- e^{- 2 α}$	$- e^{- 2 α}$	$- e^{- 2 α}$
$c_{1}$	1	$- {(1 - e^{- α})}^{2}$	1
$c_{2}$	1	1	$- {(1 - e^{- α})}^{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. Шаблон:Ref-en
R. Sirdey, A Gentle Introduction to the Deriche Optimal Edge Detector, Éditions des Nik's news, 1998. Шаблон:Ref-en
J. Canny, A Computational Approach To Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6):679–698, 1986. Шаблон:Ref-en

Посилання

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

Зміст

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

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

Див. також

Література

Посилання

Навігаційне меню

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

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

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

Див. також

Література

Посилання

Навігаційне меню

Пошук