Рассмотрим сначала одномерный случай. Пусть f(x) — дискретно заданная функция, определяющая яркость пикселя с целой координатой X. Определим дискретную производную как
:
○ для :
Для двумерного случая определим дискретную производную как средневзвешенное одномерных производных в трёх соседних точках по горизонтали или вертикали:
где
M — матрица весов. При она будет иметь вид:
○ для :
○ для :
Для использования целочисленной арифметики и ускорения вычислений указанные матрицы весов умножают на шесть (маска Превитта):
Кроме того, можно увеличить вес пикселей той же строки (столбца) для уменьшения эффекта сглаживания (маска Собеля):
А ещё есть маска Робертса (соответствует повернутому на 45° градиенту):
Чтобы не разрывать читателю шаблон, её можно представить в виде матрицы 3х3, в которой первая строка и столбец — нулевые. В качестве центрального элемента можно использовать, например, левый верхний. Благодаря меньшему размеру работает быстрее, чем маски Собеля / Превитта.
Используя одну из этих масок, можно найти частные производные и в каждой точке изображения, а значит и вектор градиента — он показывает, насколько резко изменяется яркость в точке. По его модулю можно определить, является ли пиксель граничным или нет:
● в точках высокого локального контраста:
○ имеет большое значение;
○ меняет знак, если достигает своего экстремума
● в точках низкого локального контраста:
○ первая производная имеет малое значение (либо 0).
Использование лог-фильтра. Для каждого пикселя делаем два размытия: маленькое и большое, и берём разницу между этими значениями.
c-радиус сглаживания. Лог-фильтр для одномерного случая:
При сильном увеличении влияния возможно возникновение эффекта гало.
Маска — это окрестность пикселя, она может быть развернута в вектор чисел. Все возможные значения окрестных пикселов образуют векторное пространство. Его базисом является множество векторов, в каждом из которых только один ненулевой элемент. Аi — базизные векторы, xi - множители. Матрица яркостей вокруг пикселей В этом же линейном пространстве можно задать другой базис, элементы которого будут иметь более сложную структуру, например, наличие вертикальной / горизонтальной границы. Тогда если мы разложим по новому базису окрестность, то получим набор чисел, которые показывают степень похожести окрестности на соответствующий базисный элемент. Анализируя этот набор чисел, можно принимать решение о наличии границы. Элементы, по которым раскладываем — “согласованные фильтры”. Например, если взять маску Превитта Mx, то yi будут показывать оценку вертикальной границы.
Главное достоинство метода — он позволяет обнаруживать даже широкие границы.
Входные параметры:
● размах (радиус) сглаживания
● верхний порог интенсивности — определяет минимальное значения градиента для начала детектирования границы
● нижний порог интенсивности — определяет минимальное значения градиента для продолжения детектирования границы
Алгоритм:
1 Сглаживание по Гауссу с заданным размахом. Границы приобретают гладкость, исключаются разрывы.
2 Вычисление градиента в каждой точке с помощью дифференциальных масок. Градиент показывает, в каком направлении яркость возрастает наиболее быстро.
3 Немаксимальное подавление. Для каждого пикселя рассматривается пара его соседей: один в направлении градиента, другой в обратном направлении. Если величина градиента среднего пикселя не является максимальной среди этих трёх, то она обнуляется.
4 Прослеживание контуров. Поиск начинается с пикселей, у которых значение градиента больше верхнего порога интенсивности. Рекурсивно рассматриваются соседние пиксели, у которых значение градиента больше нижнего порога интенсивности.