Детектор Canny Edge

Детектора краев Канни является обнаружением края оператором , который использует многоступенчатый алгоритм для обнаружения широкого спектра кромок в изображениях. Он был разработан Джоном Ф. Кэнни в 1986 году. Кэнни также разработал вычислительную теорию обнаружения кромок, объясняющую, почему этот метод работает.

Исходное изображение.

Разработка алгоритма Кэнни [ править ]

Обнаружение «хитрых краев» - это метод извлечения полезной структурной информации из различных объектов обзора и значительного сокращения объема обрабатываемых данных. Он широко применяется в различных системах компьютерного зрения . Кэнни обнаружил, что требования к применению обнаружения края в различных системах технического зрения относительно схожи. Таким образом, решение по обнаружению кромок для удовлетворения этих требований может быть реализовано в широком диапазоне ситуаций. Общие критерии обнаружения края включают:

1. Обнаружение края с низким коэффициентом ошибок, что означает, что обнаружение должно точно улавливать как можно больше краев, показанных на изображении.
2. Точка кромки, обнаруженная оператором, должна точно находиться в центре кромки.
3. Заданный край изображения должен быть отмечен только один раз, и, по возможности, шум изображения не должен создавать ложных краев.

Для удовлетворения этих требований Кэнни использовал вариационное исчисление - метод, который находит функцию, оптимизирующую данный функционал . Функция оптимальной в детекторе Канни по описывается суммой четырех показательных терминов, но она может быть аппроксимирована первой производной от в гауссовой .

Среди методов обнаружения кромок, разработанных к настоящему времени, алгоритм обнаружения кромок Canny является одним из наиболее строго определенных методов, обеспечивающих хорошее и надежное обнаружение. Благодаря своей оптимальности для соответствия трем критериям обнаружения кромок и простоте процесса реализации, он стал одним из самых популярных алгоритмов обнаружения кромок.

Алгоритм обнаружения края Canny [ править ]

Алгоритм обнаружения края Canny можно разбить на 5 этапов:

1. Примените фильтр Гаусса, чтобы сгладить изображение и удалить шум
2. Найдите градиенты интенсивности изображения
3. Примените пороговое значение градиента или подавление отсечки нижней границы, чтобы избавиться от ложного ответа на обнаружение границ
4. Применить двойной порог для определения потенциальных краев
5. Отслеживание края по гистерезису : завершите обнаружение краев, подавив все остальные края, которые являются слабыми и не связаны с сильными краями.

Гауссов фильтр [ править ]

Поскольку на все результаты обнаружения границ легко влияет шум в изображении, важно отфильтровать шум, чтобы предотвратить ложное обнаружение, вызванное им. Для сглаживания изображения ядро ​​фильтра Гаусса сворачивается с изображением. Этот шаг немного сгладит изображение, чтобы уменьшить влияние очевидного шума на детектор границ. Уравнение для ядра фильтра Гаусса размером (2 k +1) × (2 k +1) задается следующим образом:

${\displaystyle H_{ij}={\frac {1}{2\pi \sigma ^{2}}}\exp \left(-{\frac {(i-(k+1))^{2}+(j-(k+1))^{2}}{2\sigma ^{2}}}\right);1\leq i,j\leq (2k+1)}$

Вот пример гауссовского фильтра 5 × 5, используемого для создания соседнего изображения, с = 1. (Звездочка обозначает операцию свертки .)${\displaystyle \sigma }$

${\displaystyle \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} .}$

Важно понимать, что выбор размера ядра Гаусса повлияет на производительность детектора. Чем больше размер, тем ниже чувствительность детектора к шуму. Кроме того, ошибка локализации для обнаружения края будет немного увеличиваться с увеличением размера ядра фильтра Гаусса. 5 × 5 - хороший размер для большинства случаев, но он также будет варьироваться в зависимости от конкретных ситуаций.

Нахождение градиента интенсивности изображения [ править ]

Край изображения может указывать в разных направлениях, поэтому алгоритм Кэнни использует четыре фильтра для обнаружения горизонтальных, вертикальных и диагональных краев в размытом изображении. Оператор обнаружения края (такой как Roberts , Prewitt или Sobel ) возвращает значение для первой производной в горизонтальном направлении (G _x ) и вертикальном направлении (G _y ). Исходя из этого, можно определить градиент и направление края:

${\displaystyle \mathbf {G} ={\sqrt {{\mathbf {G} _{x}}^{2}+{\mathbf {G} _{y}}^{2}}}}$

${\displaystyle \mathbf {\Theta } =\operatorname {atan2} \left(\mathbf {G} _{y},\mathbf {G} _{x}\right)}$,

где G можно вычислить с помощью функции гипотезы, а atan2 - это функция арктангенса с двумя аргументами. Угол направления кромки округляется до одного из четырех углов, представляющих вертикальную, горизонтальную и две диагонали (0 °, 45 °, 90 ° и 135 °). Направление края, попадающее в каждую цветовую область, будет установлено на определенные значения угла, например θ в [0 °, 22,5 °] или [157,5 °, 180 °] отображается на 0 °.

Установление порога величины градиента или подавление отсечки нижней границы [ править ]

Подавление минимальной отсечки значений градиента или пороговая обработка нижней границы - это метод прореживания краев .

Подавление отсечки по нижней границе применяется для поиска мест с наиболее резким изменением значения интенсивности. Алгоритм для каждого пикселя в градиентном изображении:

1. Сравните силу края текущего пикселя с силой края пикселя в положительном и отрицательном направлениях градиента.
2. Если сила края текущего пикселя является наибольшей по сравнению с другими пикселями в маске с тем же направлением (например, пиксель, который указывает в направлении y, будет сравниваться с пикселем выше и ниже него по вертикальной оси ) значение будет сохранено. В противном случае значение будет подавлено.

В некоторых реализациях алгоритм классифицирует направления непрерывного градиента на небольшой набор дискретных направлений, а затем перемещает фильтр 3x3 поверх выходных данных предыдущего шага (то есть силы кромки и направлений градиента). В каждом пикселе он подавляет силу края центрального пикселя (путем установки его значения на 0), если его величина не превышает величину двух соседей в направлении градиента. Например,

• если округленный угол градиента равен 0 ° (т.е. край находится в направлении север-юг), точка будет считаться находящейся на краю, если ее величина градиента больше, чем величины в пикселях в направлениях восток и запад ,
• если округленный угол градиента составляет 90 ° (т.е. край находится в направлении восток-запад), точка будет считаться находящейся на краю, если ее величина градиента больше, чем величины в пикселях в северном и южном направлениях,
• если округленный угол градиента составляет 135 ° (т.е. край находится в направлении северо-восток-юго-запад), точка будет считаться находящейся на краю, если ее величина градиента больше, чем величины в пикселях на северо-западе и юго-востоке направления,
• если округленный угол градиента составляет 45 ° (т.е. край находится в направлении северо-запад-юго-восток), точка будет считаться находящейся на краю, если ее величина градиента больше, чем величины в пикселях на северо-востоке и юге -Западные направления.

В более точных реализациях используется линейная интерполяция между двумя соседними пикселями, которые охватывают направление градиента. Например, если угол градиента составляет от 89 ° до 180 °, интерполяция между градиентами на северных и северо-восточных пикселях даст одно интерполированное значение, а интерполяция между южными и юго-западными пикселями даст другое (с использованием соглашений последнего абзаца). Величина градиента в центральном пикселе должна быть больше, чем у обоих, чтобы он был отмечен как край.

Обратите внимание, что знак направления не имеет значения, т.е. север-юг совпадает с юг-севером и так далее.

Двойной порог [ править ]

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

Отслеживание края по гистерезису [ править ]

Пока что пиксели с сильными краями обязательно должны быть задействованы в конечном краевом изображении, поскольку они извлекаются из истинных краев изображения. Тем не менее, будут некоторые споры о пикселях со слабыми краями, так как эти пиксели могут быть извлечены либо из истинного края, либо из вариаций шума / цвета. Для достижения точного результата следует удалить слабые края, вызванные последними причинами. Обычно пиксель со слабым краем, вызванный истинными краями, будет связан с пикселем с сильным краем, в то время как шумовые реакции не связаны. Чтобы отследить граничное соединение, применяется анализ больших двоичных объектов , рассматривая слабый краевой пиксель и его 8-соединенные соседние пиксели. Пока есть один сильный краевой пиксель, который участвует в большом двоичном объекте, эта слабая краевая точка может быть идентифицирована как точка, которую следует сохранить.

Пошаговое руководство по обнаружению края Canny [ править ]

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

Улучшение обнаружения Canny Edge [ править ]

Хотя традиционное обнаружение кромок Canny обеспечивает относительно простую, но точную методологию для решения проблемы обнаружения кромок, с более высокими требованиями к точности и надежности обнаружения, традиционный алгоритм больше не может справиться со сложной задачей обнаружения кромок. Основные недостатки традиционного алгоритма можно резюмировать следующим образом: ^[1]

1. Гауссов фильтр применяется для сглаживания шума, но он также сглаживает края, которые считаются высокочастотной характеристикой. Это увеличит вероятность пропуска слабых краев и появления изолированных краев в результате.
2. Для вычисления амплитуды градиента старый алгоритм обнаружения краев Кэнни использует центр в небольшом окне окрестности 2 × 2 для вычисления среднего значения конечной разности для представления амплитуды градиента. Этот метод чувствителен к шуму и может легко обнаруживать ложные края и терять реальные края.
3. В традиционном алгоритме обнаружения края Canny будет два фиксированных глобальных пороговых значения для фильтрации ложных краев. Однако по мере того, как изображение становится сложным, для разных локальных областей потребуются очень разные пороговые значения для точного определения реальных краев. Кроме того, глобальные пороговые значения определяются вручную путем экспериментов традиционным методом, что приводит к сложности вычислений, когда необходимо иметь дело с большим количеством различных изображений.
4. Результат традиционного обнаружения не может обеспечить удовлетворительно высокую точность одиночного отклика для каждого края - будут появляться многоточечные отклики.

Чтобы устранить эти дефекты, в поля ниже добавлено улучшение алгоритма хитрого края.

Заменить фильтр Гаусса [ править ]

Поскольку и край, и шум будут идентифицироваться как высокочастотный сигнал, простой фильтр Гаусса добавит сглаживающий эффект на них обоих. Однако для достижения высокой точности обнаружения реального края ожидается, что к шуму следует добавить более плавный эффект, а к краю - менее гладкий эффект. Бинг Ван и Шаошен Фань из Чаншанского университета науки и технологий разработали адаптивный фильтр, в котором фильтр будет оценивать разрыв между значениями шкалы серого для каждого пикселя ^{[ необходима ссылка ]}. Чем выше разрыв, тем меньшее значение веса установлено для сглаженного фильтра в этой точке. И наоборот, чем меньше разрыв между значениями шкалы серого, тем выше значение веса, установленное для фильтра. Процесс реализации этого адаптивного фильтра можно свести к пяти шагам:

1. K = 1, установить итерацию n и коэффициент амплитуды ребра h.

2. Рассчитайте значение градиента и${\displaystyle G_{x}(x,y)}$${\displaystyle G_{y}(x,y)}$

3. Рассчитайте вес по следующей формуле:

${\displaystyle d(x,y)={\sqrt {G_{x}(x,y)^{2}+G_{y}(x,y)^{2}}}}$

${\displaystyle w(x,y)=\exp \left(-{\frac {\sqrt {d(x,y)}}{2h^{2}}}\right)}$

4. Определение адаптивного фильтра:

${\displaystyle f(x,y)={\frac {1}{N}}\sum \limits _{i=-1}^{1}\sum \limits _{j=-1}^{1}f(x+i,y+j)w(x+i,y+j)}$

для сглаживания изображения, которое

${\displaystyle N=\sum \limits _{i=-1}^{1}\sum \limits _{j=-1}^{1}w(x+i,y+j)}$

5. Когда K = n, остановите итерацию, в противном случае k = k + 1, продолжайте делать второй шаг.

Улучшение расчета величины и направления градиента [ править ]

Величину и направление градиента можно вычислить с помощью множества различных операторов обнаружения кромок, и выбор оператора может повлиять на качество результатов. Очень часто выбирают фильтр Собеля 3x3 . Однако другие фильтры могут быть лучше, например, фильтр Собеля 5x5, который снижает шум, или фильтр Шарра, который имеет лучшую симметрию вращения. Другими распространенными вариантами являются Prewitt (используется Чжоу ^[2] ) и Roberts Cross .

Надежный метод определения значения двойного порога [ править ]

Чтобы решить проблемы, при которых трудно определить значение двойного порога эмпирически, метод Оцу ^[3] может быть использован на изображении с подавленной величиной градиента, отличным от максимума, для генерации высокого порога. В этом случае нижний порог обычно устанавливается равным 1/2 от верхнего порога. Поскольку изображение величины градиента имеет непрерывные значения без четко определенного максимума, метод Оцу должен быть адаптирован для использования пар значение / счетчик вместо полной гистограммы.

Прореживание кромки [ править ]

В то время как традиционное обнаружение «хитрого края» обеспечивает хороший результат обнаружения для соответствия первым двум критериям, он не соответствует строго единственному отклику для каждого края. Маллат С. и Чжун разработали математическую морфологию для утончения обнаруженного края. ^[4]

Использование Curvelets [ править ]

Кривые использовались вместо фильтра Гаусса и оценки градиента для вычисления векторного поля, направления и величины которого аппроксимируют направление и силу краев в изображении, к которому затем применяются шаги 3-5 алгоритма Кэнни. Кривые разлагают сигналы на отдельные компоненты разного масштаба, а удаление компонентов более мелких масштабов может уменьшить шум. ^[5]

Дифференциально-геометрическая формулировка детектора края Canny [ править ]

Более совершенный подход к получению краев с субпиксельной точностью заключается в использовании подхода дифференциального обнаружения краев , при котором требование не максимального подавления формулируется в терминах производных второго и третьего порядка, вычисленных из представления масштабного пространства (Линдеберг 1998) - подробное описание см. В статье об обнаружении краев .

Вариационная формулировка краевого детектора Харалика – Кэнни [ править ]

Было показано, что вариационное объяснение основного компонента детектора края Кэнни, то есть нахождение нулевых пересечений 2-й производной вдоль направления градиента, является результатом минимизации функционала Кронрода-Минковского при максимизации интеграла по выравниванию край с градиентным полем (Kimmel and Bruckstein 2003). См. Статью о регуляризованных лапласовских переходах через нуль и других оптимальных краевых интеграторах для подробного описания.

Параметры [ править ]

Алгоритм Кэнни содержит ряд настраиваемых параметров, которые могут влиять на время вычислений и эффективность алгоритма.

• Размер гауссовского фильтра: сглаживающий фильтр, используемый на первом этапе, напрямую влияет на результаты алгоритма Кэнни. Фильтры меньшего размера вызывают меньшее размытие и позволяют обнаруживать мелкие резкие линии. Фильтр большего размера вызывает большее размытие, размывая значение данного пикселя по большей области изображения. Большие радиусы размытия более полезны для обнаружения более крупных и гладких краев - например, края радуги.
• Пороги: использование двух пороговых значений с гистерезисом обеспечивает большую гибкость, чем при однопороговом подходе, но общие проблемы пороговых подходов все еще остаются. Слишком высокий порог может упустить важную информацию. С другой стороны, слишком низкий порог будет ошибочно идентифицировать нерелевантную информацию (например, шум) как важную. Трудно дать общий порог, который подходит для всех изображений. Испытанного подхода к этой проблеме пока не существует.

Заключение [ править ]

Алгоритм Кэнни адаптируется к различным средам. Его параметры позволяют адаптировать его для распознавания кромок с различными характеристиками в зависимости от конкретных требований данной реализации. В оригинальной статье Кэнни вывод оптимального фильтра привел к фильтру с конечной импульсной характеристикой , вычисление которого в пространственной области может быть медленным, если требуется степень сглаживания (в этом случае фильтр будет иметь большую пространственную поддержку) . По этой причине часто предлагается использовать форму бесконечного импульсного отклика Рашида Дериша фильтра Кэнни (детектор Кэнни-Дериша), который является рекурсивным и может быть вычислен за короткий фиксированный промежуток времени для любого желаемого количества сглаживания. Вторая форма подходит для реализаций в реальном времени в FPGA или DSP , или очень быстрых встроенных ПК. Однако в этом контексте регулярная рекурсивная реализация оператора Кэнни не дает хорошего приближения к вращательной симметрии и, следовательно, дает смещение в сторону горизонтальных и вертикальных краев.

См. Также [ править ]

• Обнаружение функций (компьютерное зрение)
• Извлечение признаков
• Масштабировать пространство
• Обнаружение гребня
• Компьютерное зрение
• Цифровая обработка изображений

Ссылки [ править ]

Внешние ссылки [ править ]

• Домашняя страница Джона Кэнни
• Список публикаций Рашида Дериша
• Журнальные публикации Рона Киммела
• Обнаружение хитрых краев в C ++ OpenCV
• Обнаружение хитрых краев в Python OpenCV
• Canny Edge World - пример видео