Детектор края Дериша

Детектор краев Дериша — это оператор обнаружения краев, разработанный Рашидом Деришем в 1987 году. Это многошаговый алгоритм , используемый для получения оптимального результата обнаружения краев в дискретном двумерном изображении. Этот алгоритм основан на работе Джона Ф. Кэнни, связанной с обнаружением границ ( детектор границ Кэнни ) и его критериях оптимального обнаружения границ:

Качество обнаружения – все существующие края должны быть отмечены и ложное обнаружение не должно происходить.
Точность – отмеченные края должны быть максимально приближены к краям реального изображения.
Однозначность – данный край на изображении должен быть отмечен только один раз. Никаких множественных реакций на один край реального изображения быть не должно.

По этой причине этот алгоритм часто называют детектором Кэнни-Дериша.

Различия между детектором кромок Canny и Deriche

Детектор краев Дериша, как и детектор краев Канни , состоит из следующих 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

См. также

Дальнейшее чтение

Р. Дериш, Использование критериев Кэнни для получения рекурсивно реализованного оптимального детектора границ , Int. Дж. Компьютерное зрение, Том. 1, стр. 167–187, апрель 1987 г.
Р. Сирди, Нежное введение в детектор оптимальных краев Дериша , Éditions des Nik's news, 1998.
Дж. Кэнни, Вычислительный подход к обнаружению границ , Транзакции IEEE по анализу шаблонов и машинному интеллекту, 8 (6): 679–698, 1986.

Внешние ссылки