Детектор Canny Edge - Canny edge detector

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

Детектор края Canny применен к цветной фотографии паровой машины.

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

Разработка алгоритма Кэнни

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

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

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

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

Процесс алгоритма обнаружения края Canny

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

Применять Гауссов фильтр сгладить изображение, чтобы убрать шум
Найдите градиенты интенсивности изображения
Применяйте не максимальное подавление, чтобы избавиться от ложного отклика на обнаружение края
Применить двойной порог для определения потенциальных краев
Край трека по гистерезис: Завершите обнаружение краев, подавив все остальные слабые края, не связанные с сильными краями.

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

Изображение после гауссовой маски 5 × 5 было пропущено через каждый пиксель.

Поскольку на все результаты обнаружения границ легко влияет шум в изображении, важно отфильтровать шум, чтобы предотвратить ложное обнаружение, вызванное им. Для сглаживания изображения ядро фильтра Гаусса сворачивается с изображением. Этот шаг немного сгладит изображение, чтобы уменьшить влияние очевидного шума на детектор границ. Уравнение для ядра фильтра Гаусса размером (2k+1)×(2k+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, используемого для создания соседнего изображения, с ${ displaystyle sigma}$ = 1. (Звездочкой обозначен свертка операция.)

{ 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} * { .}

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

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

Край изображения может указывать в различных направлениях, поэтому алгоритм Кэнни использует четыре фильтра для обнаружения горизонтальных, вертикальных и диагональных краев в размытом изображении. В оператор обнаружения края (такие как Робертс, Prewitt, или же Собель ) возвращает значение для первой производной в горизонтальном направлении (G_Икс) и вертикальное направление (G_у). Исходя из этого, можно определить градиент и направление края:

{ 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 °.

Не максимальное подавление

Не максимальное подавление - это истончение края техника.

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

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

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

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

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

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

Двойной порог

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

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

Обнаружение резких краев, примененное к фотографии

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

Улучшение обнаружения края Canny

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

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

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

Заменить фильтр Гаусса

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

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

2. Рассчитайте значение градиента.

{ Displaystyle G_ {х} (х, у)}

и

{ Displaystyle G_ {у} (х, у)}

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 (используется Чжоу [10]) и Робертс Кросс.

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

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

Истончение края

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

Использование кривых

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

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

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

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

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

Параметры

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

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

Вывод

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