Оператор Canny

Canny — оператор обнаружения границ. Был разработан в 1986 году Джоном Канни и использует многоступенчатый алгоритм для обнаружения широкого спектра границ в изображениях. Канни изучил математическую проблему получения фильтра, оптимального по критериям выделения, локализации и минимизации нескольких откликов одного края. Он показал, что искомый фильтр является суммой четырех экспонент. Он также показал, что этот фильтр может быть хорошо приближен первой производной Гауссианы. Канни ввел понятие Non-Maximum Suppression (подавление не-максимумов), которое означает, что пикселями границ объявляются пиксели, в которых достигается локальный максимум градиента в направлении вектора градиента. Хотя его работа была проведена на заре компьютерного зрения, детектор границ Канни до сих пор является одним из лучших детекторов. Кроме особенных частных случаев трудно найти детектор, который бы работал существенно лучше, чем детектор Канни.

Развитие Canny алгоритма

Удаление слабых границ
Для чего используются два порога?
1. Чтобы уменьшить влияние шума для инициализации кривой используем верхний порог;
2. Чтобы «не потерять хвост» используем нижний порог при прослеживании.

Поиск локальных максимумов
Проверяя является ли пиксель локальным максимумом вдоль направления градиента, приходится интерполировать «нецелые» пиксели p и r

Целью Канни было открыть для себя оптимальный алгоритм обнаружения границ, удовлетворяющий трем критериям:

• хорошее обнаружение (Канни трактовал это свойство как повышение отношения сигнал/шум);

• хорошая локализация (правильное определение положения границы);

• единственный отклик на одну границу.

Из этих критериев затем строилась целевая функция стоимости ошибок, минимизацией которой находится «оптимальный» линейный оператор для свертки с изображением. Алгоритм детектора границ Canny не ограничивается вычислением градиента сглаженного изображения. В контуре границы оставляются только точки максимума градиента изображения, а не максимальные точки, лежащие рядом с границей, удаляются. Здесь также используется информация о направлении границы для того, чтобы удалять точки именно рядом с границей и не разрывать саму границу вблизи локальных максимумов градиента. Затем с помощью двух порогов удаляются слабые границы. Фрагмент границы при этом обрабатывается как целое. Если значение градиента где-нибудь на прослеживаемом фрагменте превысит верхний порог, то этот фрагмент остается также «допустимой» границей и в тех местах, где значение градиента падает ниже этого порога, до тех пор пока она не станет ниже нижнего порога. Если же на всем фрагменте нет ни одной точки со значением большим верхнего порога, то он удаляется. Такой гистерезис позволяет снизить число разрывов в выходных границах. Включение в алгоритм Canny шумоподавления с одной стороны повышает устойчивость результатов, а с другой — увеличивает вычислительные затраты и приводит к искажению и даже потере подробностей границ. Так, например, таким алгоритмом скругляются углы объектов и разрушаются границы в точках соединений.

Основные этапы алгоритма

Оригинал

Изображение после применения маски Гауса 5x5.

Детектор границ Canny

Сглаживание. Размытие изображения для удаления шума. Канни использует фильтр который может быть хорошо приближен к первой производной Гауссианы. σ = 1.4:

$\mathbf{B} = \frac{1}{159} \begin{bmatrix} 2 & 4 & 5 & 4 & 2 \\ 4 & 9 & 12 & 9 & 4 \\ 5 & 12 & 15 & 12 & 5 \\ 4 & 9 & 12 & 9 & 4 \\ 2 & 4 & 5 & 4 & 2 \end{bmatrix} * \mathbf{A}.$

Поиск градиентов. Границы отмечаются там, где градиент изображения приобретает максимальное значение. Они могут иметь различное направление, поэтому Canny алгоритм использует четыре фильтра для обнаружения горизонтальных, вертикальных и диагональных ребер в размытом изображении.

$\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }$

$\mathbf{\Theta} = \operatorname{arctan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right).$

Угол направления вектора градиента округляется и может принимать такие значения: 0, 45, 90, 135.

Направление градиента

Подавление не-максимумов. Только локальные максимумы отмечаются как границы.

Двойная пороговая фильтрация. Потенциальные границы определяются порогами.

Трассировка области неоднозначности. Итоговые границы определяются путём подавления всех краёв, несвязанных с определенными (сильными) границами.

Перед применением детектора, обычно преобразуют изображение в оттенки серого, чтобы уменьшить вычислительные затраты. Этот этап характерен для многих методов обработки изображений.

См. также

• Градиент
• Выделение границ
• Оператор собеля
• Компьютерное зрение
• Оператор Прюитта
• Перекрёстный оператор Робертса

Ссылки

• Детектор границ Канни
• OpenCV. Обработка изображения — детектор границ Кенни (Canny)
• JOHN CANNY, A Computational Approach to Edge Detection