Автор: Билл Грин
Перевод с английского: Чудовская А.К.
Название статьи: Алгоритм выделения контуров CANNY
Источник: Дрексельская лаборатория автоматизированных систем, 2002.
http://www.pages.drexel.edu/~weg22/can_tut.html
Этот урок научит вас:
(1) Выделять края с помощью алгоритма Canny.
Края характеризуют границы изображения и поэтому являются оcнововполагающей проблемой обработки изображений. Края на изображении представляют собой области с сильным контрастом интенсивности - резкий скачок интенсивности при переходе к соседнему пикселю. Обнаружение краев в изображении значительно сокращает объем данных и отфильтровывает ненужную информацию, сохраняя важные структурные свойства изображения.
Алгоритм Canny известен многим как оптимальный детектора края. Canny намеревался усовершенствовать многие существующие алгоритмы. Он был очень успешен в достижении своих целей, его идеи и методы можно найти в статье "Вычислительный подход к обнаружению границ". В своей работе он следует определенным критериям для усовершенствования методов. Первым и наиболее очевидным является низкий уровень ошибок. Очень важно, чтобы присутствующие на изображении границы не были пропущены и не было ложных обнаружений. Вторым критерием является хорошая локализованность краевых точек. Другими словами расстояние между обнаруженными краевыми точками и фактическими точками границы должно быть минимальным. Третий критерий - одно обнаружение на одну границу. Он был введен так как первые два не могли полностью исключить возможность неоднократного обнаружения одних и тех же краев.
Базирующийся на этих критериях, алгоритм выделения краев Canny сначала сглаживает изображение, чтобы устранить шум. Далее он находит градиент изображения чтобы подсветить области с высокими пространственными производными. Далее алгоритм проходит по этим областям и подавляет все пиксели, которые не в максимуме (немаксимальное подавление). Градиентный массив далее уменьшается гистерезисом. Гистерезис используется, чтобы отследить оставшиеся пиксели, которые не были подавлены. Гистерезис использует два порога и если величина ниже первого порога, то она устанавливается в ноль (делается не краевой). Если величина выше высокого порога, она делается краевой. И если величина между этими 2 порогами, то она установливается в ноль, в том случае если нет пути от этого пиксела к пикселю с градиентом выше T2. Ниже приведены шаги алгоритма.
Шаг 1
Первым шагом является фильтрация шума в исходном изображении. Поскольку фильтр Гаусса можно вычислить с помощью простой маски, он используется исключительно в алгоритме Canny. После того как подходящая маска была рассчитана, сглаживание Гаусса может быть выполнено с помощью стандартных методов свертки. Маски свертки, как правило, гораздо меньше, чем само изображение. В результате, маска двигается над изображением, манипулируя квадратом пикселей за один раз. Чем больше ширина маски Гаусса, тем меньше чувствительность детектора к шуму. Локализация ошибки в обнаружении краев так же немного увеличивается с увеличением ширины Гауссианы. Ниже показана использующаяся у меня маска Гауссианы.
Шаг 2
Нахождение края силы путем взятия градиента изображения. Оператор Собеля выполняет 2-D пространственное измерение градиента в изображении. Тогда приближенные градиенты абсолютных величин (края сил) в каждой точке может быть найдено. Оператор Собеля использует пару 3x3 масок свертки: оценки градиента в направлении х (столбцы) и оценки градиента в Y-направлении (строк). Они показаны ниже:
Величина, или край силы, градиента затем аппроксимируется по формуле:
Шаг 3
Нахождение направления края тривиально, поскольку градиент в направлениях X и Y известны. Однако если сумма Х будет равняться нулю, будет сгенерирована ошибка. Так что при реализации алгоритма, должно быть ограничение набора, когда это происходит. Всякий раз, когда градиент в направлении х равен нулю, направление края должно быть равно 90 градусам или 0 градусов, в зависимости от того, чему равно значение градиента в направлении оси Y. Если GY имеет нулевое значение, направление края будет равно 0 градусов. В противном случае направление края будет равно 90 градусов. Формула для нахождения направления края:
Шаг 4
Связывание направления края с направлением, которое может быть прослежено в изображении. Таким образом, если пиксели 5x5 изображения расположены как указано ниже:
видно, что для пикселя "а" существуют только четыре возможных направления описания окружающих пикселей - 0 градусов (в горизонтальном направлении), 45 градусов (вдоль положительной диагонали), 90 градусов (в вертикальном направлении), или 135 градусов (по отрицательной диагонали). Теперь ориентация края должна быть выбрана в одном из этих четырех направлений, в зависимости от того, какое направление находится ближе (например, если угол ориентации оказывается +3 градуса, сделать его 0 градусов). Для этого представляют полукруг, разделенный на 5 регионов
Поэтому любое направление края, входящего в желтый диапазон (от 0 до 22,5 & 157,5 до 180 градусов) устанавливается в 0 градусов. Любое направление краю, попадающее в зеленый диапазон (22,5 до 67,5 градуса) устанавливается на 45 градусов. Любое направление краю в синем диапазоне(67,5 до 112,5 градусов) устанавливается в 90 градусов. И, наконец, любое направление края в красном диапазоне (112,5 до 157,5 градусов) устанавливается в 135 градусов.
Шаг 5
После того как известны направления краев, применяем немаксимальное подавление. Оно используется для отслеживания вдоль края в направлении края и подавлении любых значений пикселя (устанавливая их равным 0), которые не считаются краем. Это даст тонкую линию в результирующем изображении.
Шаг 6
Гистерезис используется в качестве средства устранения полос. Полоса – это разбиение контура края, вызванное оператором выходного колебания выше и ниже порогового уровня. Если единственный порог, T1 применяется к изображению и край имеет среднюю силу, равную T1, то из-за шума, будут случаи, когда край опускается ниже порогового уровня. В равной степени он будет также распространяться выше порога принятия края, похожего на пунктирную линию. Чтобы избежать этого, гистерезис использует 2 порога, высокий и низкий. Любой пиксель в изображении, который имеет значение большее, чем T1 предположительно является краевым пикселем, и немедленно обозначается как таковой. Затем, любые пиксели, которые соединяются с этим краевым пикселем, и которые имеют значение, большее, чем T2, также выбираются как краевые пиксели. Для начала движения вдоль края необходим градиент T2, а для окончания – градиент ниже T1.