Доброго времени суток!
Последнее время, на Хабре часто стал упоминаться алгоритм выделения границ Канни (который, к моему удивлению, переводится дословно: хитрый). Итак, я созрел поделиться с общественностью своим опытом реализации этого детектора.
В свободное время, в целях самообразования, я изучаю алгоритмы (в том числе и машинного зрения). Занимаюсь этим непрофессионально, во многом придерживаясь научнопопулярной литературы или собственных алгоритмических решений.
Чтобы с одной стороны, упростить кодирование, а с другой – придать повествованию нотки brainfuck-программирования, я покажу реализацию в среде компьютерной алгебры Mathcad (алгоритмы протестированы в версиях 13 и 14), с как можно меньшим использованием специфических встроенных методов. Подобный поход, на мой взгляд, улучшает восприятие демонстрации, и облегчает возможный перенос алгоритмов в другие среды проектирования/разработки. Следует отметить, что некоторые этапы работы детектора Канни могут подразумевать не только различную оптимизацию (например, программная реализация оператора Собеля с использованием SIMD-расширения системы команд процессора), но и возможность замены одних операторов (методов) другими (например, оператор Собеля может быть заменён оператором Робертса или Прюитта), и возможность варьирования коэффициентов, задающих параметры работы операторов.
Приведённая версия создана из соображений максимальной простоты реализации в среде Mathcad, возможно, в ущерб производительности по скорости и качеству детектирования, и приводится как демонстрация основных этапов функционирования детектора Канни.
Канни (John F. Canny; 1953 г.) изучил математическую проблему получения фильтра, оптимального по критериям выделения, локализации и минимизации нескольких откликов одного края. Это означает, что детектор должен реагировать на границы, но при этом игнорировать ложные, точно определять линию границы (без её фрагментирования) и реагировать на каждую границу один раз, что позволяет избежать восприятия широких полос изменения яркости как совокупности границ. Канни ввел понятие Non-Maximum Suppression (подавление не-максимумов), которое означает, что пикселями границ объявляются точки, в которых достигается локальный максимум градиента в направлении вектора градиента.
Хотя его работа была проведена на заре компьютерного зрения (1986 г.), детектор границ Канни до сих пор является одним из лучших детекторов. Кроме особенных частных случаев трудно найти детектор, который бы работал существенно лучше, чем детектор Канни.
В качестве демонстрации работы алгоритма будет решена задача по выделению границ на следующем изображении.
Алгоритм состоит из пяти отдельных шагов:
Для преобразования исходного изображения в изображение в градациях серого, необходимо получить его «яркость»-составляющую. Для этого удобно представить изображение в цветовой модели YUV (или HSL, HSV, других).
Изначально рисунок представлен в RGB цветовой модели, причём функция загрузки возвращает три компонента в виде одной матрицы.
Для перевода изображения в модель YUV выполним следующие операции.
Получим матрицы, описывающие компоненты модели (R,G,B):
Рассчитаем Y-компоненту YUV модели:
Коэффициенты перевода (они постоянны и определяются особенностями человеческого восприятия, а ведь именно с позиции человека мы здесь оцениваем границы):
Результат преобразования:
Для подавления шума, воспользуемся размытием изображения фильтром Гаусса.
Функция Гаусса для двумерного случая:
Метод, составляющий ядро фильтра размером size с параметром σ:
Процедура, применения фильтра с ядром размера size и параметром σ к матрице изображения Matrix:
Необходимо выбрать параметры фильтра, обеспечивающие наилучшее подавление шума. Влияние пикселей друг на друга при гауссовой фильтрации обратно пропорционально квадрату расстояния между ними: коэффициент пропорциональности, а, следовательно, и степень размытия, определяются параметром σ. Чрезмерное повышение коэффициента приведёт к усилению усреднения вплоть до равномерно чёрного цвета всех пикселей:
Выберем σ=1.0.
Ядро фильтра очень быстро убывает к нулю при удалении от точки (0, 0), и потому на практике можно ограничиться сверткой с окном небольшого размера вокруг (0, 0) (например, руководствуясь правилом трёх сигм, возьмём радиус окна равным 3σ). Ниже представлен результат применения фильтра с фиксированным значением параметра σ, и разным размером ядра (параметром size).
Выберем size=7. Результат применения фильтра с выбранными параметрами изображён на рисунке выше.
Оператор Собеля часто применяют в алгоритмах выделения границ. По сути, это дискретный дифференциальный оператор, вычисляющий приближенное значение градиента яркости изображения. Результатом применения оператора Собеля в каждой точке изображения является либо вектор градиента яркости в этой точке, либо его норма. Оператор Собеля основан на свёртке изображения небольшими целочисленными фильтрами в вертикальном и горизонтальном направлениях, поэтому его относительно легко вычислять. С другой стороны, используемая им аппроксимация градиента достаточно грубая, особенно это сказывается на высокочастотных колебаниях изображения.
Ядра фильтров:
Реализация (сопоставляет каждой точке вектор градиента):
Угол вектора квантуется по 45° — именно такие значения необходимы для одного из следующих этапов.
На рисунке ниже показан результат применения оператора к размытому (А) и исходному (в градациях серого) изображению (Б).
Пикселями границ объявляются пиксели, в которых достигается локальный максимум градиента в направлении вектора градиента. Значение направления должно быть кратно 45°.
Принцип подавления проиллюстрирован на рисунке выше. Почти все пиксели в примере «имеют ориентацию вверх», поэтому значение градиента в этих точках будет сравнено с ниже- и вышерасположенными пикселями. Обведённые белым контуром пиксели останутся в результирующем изображении, остальные – будут подавлены.
Реализация проверки точки на принадлежность изображению:
Сравнение значения:
Реализация подавления:
После подавления не-максимумов, края стали более точными и тонкими.
Ниже, на первом рисунке, представлено векторное поле градиентов (углы кратны 45°) всего исходного (то есть, до подавления) изображения, а на втором – небольшого фрагмента.
Следующий шаг — применение порога, чтобы определить находится или нет граница в данной точке изображения. Чем меньше порог, тем больше границ будет находиться, но тем более восприимчивым к шуму станет результат, выделяя лишние данные изображения. Наоборот, высокий порог может проигнорировать слабые края или получить границу фрагментами.
Выделение границ Канни использует два порога фильтрации: если значение пикселя выше верхней границы – он принимает максимальное значение (граница считается достоверной), если ниже – пиксель подавляется, точки со значением, попадающим в диапазон между порогов, принимают фиксированное среднее значение (они будут уточнены на следующем этапе).
Реализация:
Результат применения с порогами 55% и 60% от диапазона приведён на рисунке далее.
Упрощённо, задача сводится к выделению групп пикселей, получивших на предыдущем этапе промежуточное значение, и отнесению их к границе (если они соединены с одной из установленных границ) или их подавлению (в противном случае). Пиксель добавляется к группе, если он соприкасается с ней по одному из 8-ми направлений.
Реализация:
Результат трассировки:
В процессе разработки я использовал следующие источники (главным образом, [1]):
Буду рад критике и замечаниям, так как область машинного зрения не связана с моей профессиональной деятельностью.
upd А вот и критика. Спасибо andreyivanoff за указание на принципиальные ошибки в алгоритме и ссылке на статью (тут).
upd2 andreyivanoff даёт важные комментарии к алгоритму тут.
Последнее время, на Хабре часто стал упоминаться алгоритм выделения границ Канни (который, к моему удивлению, переводится дословно: хитрый). Итак, я созрел поделиться с общественностью своим опытом реализации этого детектора.
В свободное время, в целях самообразования, я изучаю алгоритмы (в том числе и машинного зрения). Занимаюсь этим непрофессионально, во многом придерживаясь научнопопулярной литературы или собственных алгоритмических решений.
Чтобы с одной стороны, упростить кодирование, а с другой – придать повествованию нотки brainfuck-программирования, я покажу реализацию в среде компьютерной алгебры Mathcad (алгоритмы протестированы в версиях 13 и 14), с как можно меньшим использованием специфических встроенных методов. Подобный поход, на мой взгляд, улучшает восприятие демонстрации, и облегчает возможный перенос алгоритмов в другие среды проектирования/разработки. Следует отметить, что некоторые этапы работы детектора Канни могут подразумевать не только различную оптимизацию (например, программная реализация оператора Собеля с использованием SIMD-расширения системы команд процессора), но и возможность замены одних операторов (методов) другими (например, оператор Собеля может быть заменён оператором Робертса или Прюитта), и возможность варьирования коэффициентов, задающих параметры работы операторов.
Приведённая версия создана из соображений максимальной простоты реализации в среде Mathcad, возможно, в ущерб производительности по скорости и качеству детектирования, и приводится как демонстрация основных этапов функционирования детектора Канни.
Выделение границ Канни
Канни (John F. Canny; 1953 г.) изучил математическую проблему получения фильтра, оптимального по критериям выделения, локализации и минимизации нескольких откликов одного края. Это означает, что детектор должен реагировать на границы, но при этом игнорировать ложные, точно определять линию границы (без её фрагментирования) и реагировать на каждую границу один раз, что позволяет избежать восприятия широких полос изменения яркости как совокупности границ. Канни ввел понятие Non-Maximum Suppression (подавление не-максимумов), которое означает, что пикселями границ объявляются точки, в которых достигается локальный максимум градиента в направлении вектора градиента.
Хотя его работа была проведена на заре компьютерного зрения (1986 г.), детектор границ Канни до сих пор является одним из лучших детекторов. Кроме особенных частных случаев трудно найти детектор, который бы работал существенно лучше, чем детектор Канни.
Задача
В качестве демонстрации работы алгоритма будет решена задача по выделению границ на следующем изображении.
Алгоритм состоит из пяти отдельных шагов:
- Сглаживание. Размытие изображения для удаления шума.
- Поиск градиентов. Границы отмечаются там, где градиент изображения приобретает максимальное значение.
- Подавление не-максимумов. Только локальные максимумы отмечаются как границы.
- Двойная пороговая фильтрация. Потенциальные границы определяются порогами.
- Трассировка области неоднозначности. Итоговые границы определяются путём подавления всех краёв, несвязанных с определенными (сильными) границами.
Преобразование в оттенки серого
Для преобразования исходного изображения в изображение в градациях серого, необходимо получить его «яркость»-составляющую. Для этого удобно представить изображение в цветовой модели YUV (или HSL, HSV, других).
Изначально рисунок представлен в RGB цветовой модели, причём функция загрузки возвращает три компонента в виде одной матрицы.
Для перевода изображения в модель YUV выполним следующие операции.
Получим матрицы, описывающие компоненты модели (R,G,B):
Рассчитаем Y-компоненту YUV модели:
Коэффициенты перевода (они постоянны и определяются особенностями человеческого восприятия, а ведь именно с позиции человека мы здесь оцениваем границы):
Результат преобразования:
Сглаживание
Для подавления шума, воспользуемся размытием изображения фильтром Гаусса.
Функция Гаусса для двумерного случая:
Метод, составляющий ядро фильтра размером size с параметром σ:
Процедура, применения фильтра с ядром размера size и параметром σ к матрице изображения Matrix:
Необходимо выбрать параметры фильтра, обеспечивающие наилучшее подавление шума. Влияние пикселей друг на друга при гауссовой фильтрации обратно пропорционально квадрату расстояния между ними: коэффициент пропорциональности, а, следовательно, и степень размытия, определяются параметром σ. Чрезмерное повышение коэффициента приведёт к усилению усреднения вплоть до равномерно чёрного цвета всех пикселей:
Выберем σ=1.0.
Ядро фильтра очень быстро убывает к нулю при удалении от точки (0, 0), и потому на практике можно ограничиться сверткой с окном небольшого размера вокруг (0, 0) (например, руководствуясь правилом трёх сигм, возьмём радиус окна равным 3σ). Ниже представлен результат применения фильтра с фиксированным значением параметра σ, и разным размером ядра (параметром size).
Выберем size=7. Результат применения фильтра с выбранными параметрами изображён на рисунке выше.
Поиск градиентов
Оператор Собеля часто применяют в алгоритмах выделения границ. По сути, это дискретный дифференциальный оператор, вычисляющий приближенное значение градиента яркости изображения. Результатом применения оператора Собеля в каждой точке изображения является либо вектор градиента яркости в этой точке, либо его норма. Оператор Собеля основан на свёртке изображения небольшими целочисленными фильтрами в вертикальном и горизонтальном направлениях, поэтому его относительно легко вычислять. С другой стороны, используемая им аппроксимация градиента достаточно грубая, особенно это сказывается на высокочастотных колебаниях изображения.
Ядра фильтров:
Реализация (сопоставляет каждой точке вектор градиента):
Угол вектора квантуется по 45° — именно такие значения необходимы для одного из следующих этапов.
На рисунке ниже показан результат применения оператора к размытому (А) и исходному (в градациях серого) изображению (Б).
Подавление не-максимумов
Пикселями границ объявляются пиксели, в которых достигается локальный максимум градиента в направлении вектора градиента. Значение направления должно быть кратно 45°.
Принцип подавления проиллюстрирован на рисунке выше. Почти все пиксели в примере «имеют ориентацию вверх», поэтому значение градиента в этих точках будет сравнено с ниже- и вышерасположенными пикселями. Обведённые белым контуром пиксели останутся в результирующем изображении, остальные – будут подавлены.
Реализация проверки точки на принадлежность изображению:
Сравнение значения:
Реализация подавления:
После подавления не-максимумов, края стали более точными и тонкими.
Ниже, на первом рисунке, представлено векторное поле градиентов (углы кратны 45°) всего исходного (то есть, до подавления) изображения, а на втором – небольшого фрагмента.
Двойная пороговая фильтрация
Следующий шаг — применение порога, чтобы определить находится или нет граница в данной точке изображения. Чем меньше порог, тем больше границ будет находиться, но тем более восприимчивым к шуму станет результат, выделяя лишние данные изображения. Наоборот, высокий порог может проигнорировать слабые края или получить границу фрагментами.
Выделение границ Канни использует два порога фильтрации: если значение пикселя выше верхней границы – он принимает максимальное значение (граница считается достоверной), если ниже – пиксель подавляется, точки со значением, попадающим в диапазон между порогов, принимают фиксированное среднее значение (они будут уточнены на следующем этапе).
Реализация:
Результат применения с порогами 55% и 60% от диапазона приведён на рисунке далее.
Трассировка области неоднозначности
Упрощённо, задача сводится к выделению групп пикселей, получивших на предыдущем этапе промежуточное значение, и отнесению их к границе (если они соединены с одной из установленных границ) или их подавлению (в противном случае). Пиксель добавляется к группе, если он соприкасается с ней по одному из 8-ми направлений.
Реализация:
Результат трассировки:
Список источников
В процессе разработки я использовал следующие источники (главным образом, [1]):
- Canny Edge Detection www.cvmt.dk/education/teaching/f09/VGIS8/AIP
- Википедия. Edge detection en.wikipedia.org/wiki/Edge_detection
- Википедия. Оператор Собеля ru.wikipedia.org/wiki/Оператор_Собеля
- Алгоритмические основы растровой графики www.intuit.ru/department/graphics/rastrgraph/8/rastrgraph_8.html
Буду рад критике и замечаниям, так как область машинного зрения не связана с моей профессиональной деятельностью.
upd А вот и критика. Спасибо andreyivanoff за указание на принципиальные ошибки в алгоритме и ссылке на статью (тут).
upd2 andreyivanoff даёт важные комментарии к алгоритму тут.
