Детектор края Канни

Детектор края Канни применен к цветной фотографии парового двигателя.

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

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

Разработка

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

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

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

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

Процесс

Процесс алгоритма обнаружения границ Канни можно разбить на пять различных этапов:

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

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

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

$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, используемого для создания соседнего изображения, с $\sigma$ = 1. (Звездочка обозначает операцию свертки .)

\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 ). Отсюда можно определить градиент и направление края:

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

\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°, интерполяция между градиентами на северном и северо-восточном пикселях даст одно интерполированное значение, а интерполяция между южным и юго-западным пикселями даст другое (используя соглашения последнего абзаца). Величина градиента в центральном пикселе должна быть больше, чем оба этих значения, чтобы его можно было пометить как край.

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

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

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

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

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

Прохождение алгоритма

В этом разделе будет показано продвижение изображения по каждому из пяти этапов.

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

Изображение было уменьшено до оттенков серого и применен фильтр Гаусса 5x5 с σ=1,4.

Градиент интенсивности предыдущего изображения. Края изображения были обработаны путем репликации.

Немаксимальное подавление применено к предыдущему изображению.

Двойной порог применен к предыдущему изображению. Слабые пиксели — это пиксели со значением градиента от 0,1 до 0,3. Яркие пиксели имеют значение градиента более 0,3.

Гистерезис, примененный к предыдущему изображению

Улучшения

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

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

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

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

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

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

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

G_{x}(x,y)

и

G_{y}(x,y)

3. Рассчитайте вес по формулам ниже:

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

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

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

$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)$

сгладить изображение, где

$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 ]}) и Робертс Кросс .

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

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

Утончение края

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

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

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

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

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

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

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

Параметры

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

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

Заключение

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

См. также

Ссылки

^ Ли, К., Ван, Б., и Фань, С. (2009). Просмотр публикаций конференции Информатика и инженерия ... Помощь Работа с тезисами Улучшенный алгоритм обнаружения границ CANNY. В 2009 г. результаты второго международного семинара по информатике и инженерии: WCSE 2009: 28–30 октября 2009 г., Циндао, Китай (стр. 497–500). Лос-Аламитос, Калифорния: Компьютерное общество IEEE
^ Чжоу П., Йе В. и Ван К. (2011). Улучшенный алгоритм Канни для обнаружения краев. Журнал вычислительных информационных систем, 7 (5), 1516–1523.
^ Оцу Н. Метод выбора порога из гистограмм уровня серого. IEEE Trans Systems, Человек и кибернетика, 9 (1): 62–66, 1979.
^ Маллат С., Чжун С. Характеристика сигналов от многомасштабных краев [J]. IEEE Trans на PAMI, 1992, 14 (7):710-732.
^ Гебек, Т.; Кумутсакос, П. (2009). «Обнаружение краев на микроскопических изображениях с использованием кривых» . БМК Биоинформатика . 10:75 . дои : 10.1186/1471-2105-10-75 . ПМЦ 2663783 . ПМИД 19257905 .

Кэнни, Дж., Вычислительный подход к обнаружению границ , Транзакции IEEE по анализу шаблонов и машинному интеллекту, 8(6):679–698, 1986.
Р. Дериш, Использование критериев Кэнни для получения рекурсивно реализованного оптимального детектора краев , Int. Дж. Компьютерное зрение, Том. 1, стр. 167–187, апрель 1987 г.
Линдеберг, Тони «Обнаружение краев и обнаружение гребней с автоматическим выбором масштаба», International Journal of Computer Vision, 30, 2, стр. 117–154, 1998. (Включает дифференциальный подход к немаксимальному подавлению.)
Киммел, Рон и Брукштейн, Альфред М. «О регуляризованных лапласовых пересечениях нуля и других оптимальных интеграторах ребер», International Journal of Computer Vision, 53 (3): 225–243, 2003. (Включает геометрическую вариационную интерпретацию для Харалика – Кэнни детектор края.)
Моеслунд, Т. (23 марта 2009 г.). Обнаружение Канни Края. Проверено 3 декабря 2014 г.
Томас Б. Мёслунд. Обработка изображений и видео. август 2008 г.
Грин, Б. (1 января 2002 г.). Учебное пособие по обнаружению Canny Edge. Проверено 3 декабря 2014 г .; заархивировано здесь

Внешние ссылки

[1] Ли, К., Ван, Б., и Фань, С. (2009). Просмотр публикаций конференции Информатика и инженерия ... Помощь Работа с тезисами Улучшенный алгоритм обнаружения границ CANNY. В 2009 г. результаты второго международного семинара по информатике и инженерии: WCSE 2009: 28–30 октября 2009 г., Циндао, Китай (стр. 497–500). Лос-Аламитос, Калифорния: Компьютерное общество IEEE

[2] Чжоу П., Йе В. и Ван К. (2011). Улучшенный алгоритм Канни для обнаружения краев. Журнал вычислительных информационных систем, 7 (5), 1516–1523.

[3] Оцу Н. Метод выбора порога из гистограмм уровня серого. IEEE Trans Systems, Человек и кибернетика, 9 (1): 62–66, 1979.

[4] Маллат С., Чжун С. Характеристика сигналов от многомасштабных краев [J]. IEEE Trans на PAMI, 1992, 14 (7):710-732.

[5] Гебек, Т.; Кумутсакос, П. (2009). «Обнаружение краев на микроскопических изображениях с использованием кривых» . БМК Биоинформатика . 10:75 . дои : 10.1186/1471-2105-10-75 . ПМЦ 2663783 . ПМИД 19257905 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]