Pull to refresh

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

Image processing *
Sandbox
Доброго времени суток!

Последнее время, на Хабре часто стал упоминаться алгоритм выделения границ Канни (который, к моему удивлению, переводится дословно: хитрый). Итак, я созрел поделиться с общественностью своим опытом реализации этого детектора.

В свободное время, в целях самообразования, я изучаю алгоритмы (в том числе и машинного зрения). Занимаюсь этим непрофессионально, во многом придерживаясь научнопопулярной литературы или собственных алгоритмических решений.
Чтобы с одной стороны, упростить кодирование, а с другой – придать повествованию нотки brainfuck-программирования, я покажу реализацию в среде компьютерной алгебры Mathcad (алгоритмы протестированы в версиях 13 и 14), с как можно меньшим использованием специфических встроенных методов. Подобный поход, на мой взгляд, улучшает восприятие демонстрации, и облегчает возможный перенос алгоритмов в другие среды проектирования/разработки. Следует отметить, что некоторые этапы работы детектора Канни могут подразумевать не только различную оптимизацию (например, программная реализация оператора Собеля с использованием SIMD-расширения системы команд процессора), но и возможность замены одних операторов (методов) другими (например, оператор Собеля может быть заменён оператором Робертса или Прюитта), и возможность варьирования коэффициентов, задающих параметры работы операторов.
Приведённая версия создана из соображений максимальной простоты реализации в среде Mathcad, возможно, в ущерб производительности по скорости и качеству детектирования, и приводится как демонстрация основных этапов функционирования детектора Канни.

Выделение границ Канни


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

Задача


В качестве демонстрации работы алгоритма будет решена задача по выделению границ на следующем изображении.
image
Алгоритм состоит из пяти отдельных шагов:
  1. Сглаживание. Размытие изображения для удаления шума.
  2. Поиск градиентов. Границы отмечаются там, где градиент изображения приобретает максимальное значение.
  3. Подавление не-максимумов. Только локальные максимумы отмечаются как границы.
  4. Двойная пороговая фильтрация. Потенциальные границы определяются порогами.
  5. Трассировка области неоднозначности. Итоговые границы определяются путём подавления всех краёв, несвязанных с определенными (сильными) границами.
Перед применением детектора, преобразуем изображение в оттенки серого, чтобы уменьшить вычислительные затраты. Этот этап характерен для многих методов обработки изображений.

Преобразование в оттенки серого

Для преобразования исходного изображения в изображение в градациях серого, необходимо получить его «яркость»-составляющую. Для этого удобно представить изображение в цветовой модели YUV (или HSL, HSV, других).
Изначально рисунок представлен в RGB цветовой модели, причём функция загрузки возвращает три компонента в виде одной матрицы.
image
Для перевода изображения в модель YUV выполним следующие операции.
Получим матрицы, описывающие компоненты модели (R,G,B):
image

Рассчитаем Y-компоненту YUV модели:
image

Коэффициенты перевода (они постоянны и определяются особенностями человеческого восприятия, а ведь именно с позиции человека мы здесь оцениваем границы):
image

Результат преобразования:
image

Сглаживание

Для подавления шума, воспользуемся размытием изображения фильтром Гаусса.
Функция Гаусса для двумерного случая:
image
Метод, составляющий ядро фильтра размером size с параметром σ:
image
Процедура, применения фильтра с ядром размера size и параметром σ к матрице изображения Matrix:
image
Необходимо выбрать параметры фильтра, обеспечивающие наилучшее подавление шума. Влияние пикселей друг на друга при гауссовой фильтрации обратно пропорционально квадрату расстояния между ними: коэффициент пропорциональности, а, следовательно, и степень размытия, определяются параметром σ. Чрезмерное повышение коэффициента приведёт к усилению усреднения вплоть до равномерно чёрного цвета всех пикселей:
image
Выберем σ=1.0.
Ядро фильтра очень быстро убывает к нулю при удалении от точки (0, 0), и потому на практике можно ограничиться сверткой с окном небольшого размера вокруг (0, 0) (например, руководствуясь правилом трёх сигм, возьмём радиус окна равным 3σ). Ниже представлен результат применения фильтра с фиксированным значением параметра σ, и разным размером ядра (параметром size).
image
Выберем size=7. Результат применения фильтра с выбранными параметрами изображён на рисунке выше.

Поиск градиентов

Оператор Собеля часто применяют в алгоритмах выделения границ. По сути, это дискретный дифференциальный оператор, вычисляющий приближенное значение градиента яркости изображения. Результатом применения оператора Собеля в каждой точке изображения является либо вектор градиента яркости в этой точке, либо его норма. Оператор Собеля основан на свёртке изображения небольшими целочисленными фильтрами в вертикальном и горизонтальном направлениях, поэтому его относительно легко вычислять. С другой стороны, используемая им аппроксимация градиента достаточно грубая, особенно это сказывается на высокочастотных колебаниях изображения.
Ядра фильтров:
image
Реализация (сопоставляет каждой точке вектор градиента):
image
Угол вектора квантуется по 45° — именно такие значения необходимы для одного из следующих этапов.
На рисунке ниже показан результат применения оператора к размытому (А) и исходному (в градациях серого) изображению (Б).
image

Подавление не-максимумов

Пикселями границ объявляются пиксели, в которых достигается локальный максимум градиента в направлении вектора градиента. Значение направления должно быть кратно 45°.
image
Принцип подавления проиллюстрирован на рисунке выше. Почти все пиксели в примере «имеют ориентацию вверх», поэтому значение градиента в этих точках будет сравнено с ниже- и вышерасположенными пикселями. Обведённые белым контуром пиксели останутся в результирующем изображении, остальные – будут подавлены.
Реализация проверки точки на принадлежность изображению:
image
Сравнение значения:
image
Реализация подавления:
image
После подавления не-максимумов, края стали более точными и тонкими.
image
Ниже, на первом рисунке, представлено векторное поле градиентов (углы кратны 45°) всего исходного (то есть, до подавления) изображения, а на втором – небольшого фрагмента.
image
image

Двойная пороговая фильтрация

Следующий шаг — применение порога, чтобы определить находится или нет граница в данной точке изображения. Чем меньше порог, тем больше границ будет находиться, но тем более восприимчивым к шуму станет результат, выделяя лишние данные изображения. Наоборот, высокий порог может проигнорировать слабые края или получить границу фрагментами.
Выделение границ Канни использует два порога фильтрации: если значение пикселя выше верхней границы – он принимает максимальное значение (граница считается достоверной), если ниже – пиксель подавляется, точки со значением, попадающим в диапазон между порогов, принимают фиксированное среднее значение (они будут уточнены на следующем этапе).
Реализация:
image
Результат применения с порогами 55% и 60% от диапазона приведён на рисунке далее.
image

Трассировка области неоднозначности

Упрощённо, задача сводится к выделению групп пикселей, получивших на предыдущем этапе промежуточное значение, и отнесению их к границе (если они соединены с одной из установленных границ) или их подавлению (в противном случае). Пиксель добавляется к группе, если он соприкасается с ней по одному из 8-ми направлений.
Реализация:
image
Результат трассировки:
image
image

Список источников


В процессе разработки я использовал следующие источники (главным образом, [1]):
  1. Canny Edge Detection www.cvmt.dk/education/teaching/f09/VGIS8/AIP
  2. Википедия. Edge detection en.wikipedia.org/wiki/Edge_detection
  3. Википедия. Оператор Собеля ru.wikipedia.org/wiki/Оператор_Собеля
  4. Алгоритмические основы растровой графики www.intuit.ru/department/graphics/rastrgraph/8/rastrgraph_8.html

Буду рад критике и замечаниям, так как область машинного зрения не связана с моей профессиональной деятельностью.

upd А вот и критика. Спасибо andreyivanoff за указание на принципиальные ошибки в алгоритме и ссылке на статью (тут).

upd2 andreyivanoff даёт важные комментарии к алгоритму тут.
Tags: машинное зрениевыделение границобнаружение границКанниCanny edge detection
Hubs: Image processing
Total votes 70: ↑67 and ↓3 +64
Comments 26
Comments Comments 26

Popular right now

Top of the last 24 hours