Полное решение для произвольных размеров и углов ядра Собеля
tl; dr: перейдите к разделу «Примеры»
Чтобы добавить другое решение, расширив этот документ (он не особо высокого качества, но показывает некоторые полезные графики и матрицы, начиная с нижней части страницы 2).
Цель
Что мы пытаемся сделатьэто оценка локального градиента изображения в положении (x, y).Градиент - это вектор, составленный из компонентов в направлениях x и y, gx и gy.
Теперь представьте, что мы хотим приблизить градиент на основе нашего пикселя (x, y) и его соседей как ядраоперация (3x3, 5x5 или любой другой размер).
Идея решения
Мы можем приблизить градиент путем суммирования проекций всех пар соседних центров на направление градиента.(Ядро Собеля - это просто особый метод взвешивания различных вкладов, как и Prewitt, в основном).
Явные промежуточные шаги для 3x3
Это локальное изображение, центральный пиксель (x,y) помечено как 'o' (в центре)
a b c
d o f
g h i
Допустим, нам нужен градиент в положительном направлении x.Единичный вектор в положительном направлении x равен (1,0) [Позже я буду использовать соглашение о том, что положительное направление y равно ВНИЗ, то есть (0,1), а (0,0) находится слева вверху от изображения).]
Вектор от o до f (для краткости «of») равен (1,0).Градиент в направлении 'of' равен (f - o) / 1 (значение изображения в пикселе здесь обозначено как f минус значение в центре o, деленное на расстояние между этими пикселями).Если мы спроецируем единичный вектор этого конкретного градиента соседа на желаемое направление градиента (1,0) через произведение точек, мы получим 1. Вот небольшая таблица с вкладами всех соседей, начиная с более простых случаев.Обратите внимание, что для диагоналей их расстояние равно sqrt2, а единичные векторы в диагональных направлениях равны 1 / sqrt2 * (+/- 1, +/- 1)
f: (f-o)/1 * 1
d: (d-o)/1 * -1 because (-1, 0) dot (1, 0) = -1
b: (b-o)/1 * 0 because (0, -1) dot (1, 0) = 0
h: (h-o)/1 * 0 (as per b)
a: (a-o)/sqrt2 * -1/sqrt2 distance is sqrt2, and 1/sqrt2*(-1,-1) dot (1,0) = -1/sqrt2
c: (c-o)/sqrt2 * +1/sqrt2 ...
g: (g-o)/sqrt2 * -1/sqrt2 ...
i: (i-o)/sqrt2 * +1/sqrt2 ...
. Изменить для уточнения: Есть два коэффициента 1 / sqrt (2) по следующей причине:
Нас интересует вклад в градиент в определенном направлении (здесь x), поэтому нам нужно спроецировать направленный градиент от центрального пикселя к соседнему пикселю в интересующем нас направлении. Это достигается путем скалярного произведения единичных векторов в соответствующих направлениях, которое вводит первоекоэффициент 1 / L (здесь 1 / sqrt (2) для диагоналей).
Градиент измеряет бесконечно малое изменение в точке, которую мы аппроксимируем конечными разностями.В терминах линейного уравнения m = (y2-y1) / (x2-x1).По этой причине разность значений от центрального пикселя до соседнего пикселя (y2-y1) должна быть распределена по их расстоянию (соответствует x2-x1), чтобы получить единицы всплытия на единицу расстояния.Это дает второй коэффициент 1 / L (здесь 1 / sqrt (2) для диагоналей)
Хорошо, теперь мы знаем вклады.Давайте упростим это выражение, комбинируя противоположные пары пиксельных вкладов.Я начну с d и f:
{(f-o)/1 * 1} + {(d-o)/1 * -1}
= f - o - (d - o)
= f - d
Теперь первая диагональ:
{(c-o)/sqrt2 * 1/sqrt2} + {(g-o)/sqrt2 * -1/sqrt2}
= (c - o)/2 - (g - o)/2
= (c - g)/2
Вторая диагональ дает (i - a) / 2.Перпендикулярное направление дает ноль.Обратите внимание, что все вклады от центрального пикселя 'o' исчезают.
Теперь мы вычислили вклады всех ближайших соседей в градиент в положительном x-направлении в пикселе (x, y), поэтому наше полное приближениеградиент в x-направлении является просто их суммой:
gx(x,y) = f - d + (c - g)/2 + (i - a)/2
Мы можем получить тот же результат, используя сверточное ядро, где коэффициенты записаны вместо соответствующего соседнего пикселя:
-1/2 0 1/2
-1 0 1
-1/2 0 1/2
Если вы не хотите иметь дело с дробями, умножьте это на 2 и получите хорошо известное ядро Sobel 3x3.
-1 0 1
G_x = -2 0 2
-1 0 1
Умножение на два служит только для получения удобных целых чисел.Масштабирование вашего выходного изображения в основном произвольное, в большинстве случаев вы все равно нормализуете его по диапазону изображения (чтобы получить четко видимые результаты).
По тем же рассуждениям, что и выше, вы получаете ядро для вертикального градиента gy, проецируя соседние вклады на единичный вектор в положительном направлении y (0,1)
-1 -2 -1
G_y = 0 0 0
1 2 1
Формуладля ядер произвольного размера
Если вы хотите использовать ядра 5x5 или более, вам нужно только обратить внимание на расстояния, например
A B 2 B A
B C 1 C B
2 1 - 1 2
B C 1 C B
A B 2 B A
, где
A = 2 * sqrt2
B = sqrt5
C = sqrt2.
Еслидлина вектора, соединяющего любые два пикселя, равна L, единичный вектор в этом направлении имеет коэффициент 1 / L.По этой причине вклад любого пикселя 'k' в (скажем) x-градиент (1,0) может быть упрощен до "(разности значений на квадрат расстояния) раз (DotProduct ненормализованного вектора направления 'ok' с вектором градиента, например (1,0)) "
gx_k = (k - o)/(pixel distance^2) ['ok' dot (1,0)].
Поскольку произведение точек связующего вектора с вектором единицы x выбирает соответствующую запись вектора, соответствующая запись ядра G_x в позиции k равна просто
i / (i*i + j*j)
где i и j - количество шагов от центрального пикселя до пикселя k в направлениях x и y.В приведенном выше расчете 3x3 пиксель «a» будет иметь i = -1 (1 слева), j = -1 (1 сверху), и, следовательно, запись ядра «a» равна -1 / (1 + 1).) = -1 / 2.
Записи для ядра G_y:
j/(i*i + j*j).
Если я хочу целочисленные значения для своего ядра, я выполняю следующие шаги:
- проверить доступный диапазон выходного изображения
- вычислить максимально возможный результат от применения ядра с плавающей запятой (т.е. принять максимальное входное значение для всех положительных записей ядра, поэтому выходное значение равно (сумма по всем положительным значениям ядра) *(Максимально возможное значение входного изображения.) Если у вас есть входные данные со знаком, вам также необходимо учитывать отрицательные значения. В худшем случае это сумма всех положительных значений + сумма всех абсолютных значений отрицательных значений (если максимальное значение введено при положительных значениях,-max ввод под отрицательными значениями). edit: сумма всех значений abs также точно названа weight ядра
- вычислить максимально допустимое масштабирование для ядра (без диапазона переполнениявыходное изображение)
- для всех целочисленных кратных (от 2 до максимума) ядра с плавающей запятой: проверьте, какая из наименьших сумм абсолютных ошибок округления, и используйте это ядро
Итак, в итоге:
Gx_ij = i / (i*i + j*j)
Gy_ij = j / (i*i + j*j)
где i, j - позиция в ядре, отсчитанная от центра.Масштабирование записей ядра по мере необходимости для получения целых чисел (или, по крайней мере, близких приближений).
Эти формулы применимы для всех размеров ядра.
Примеры
-2/8 -1/5 0 1/5 2/8 -5 -4 0 4 5
-2/5 -1/2 0 1/2 2/5 -8 -10 0 10 8
G_x (5x5) -2/4 -1/1 0 1/1 2/4 (*20) = -10 -20 0 20 10
-2/5 -1/2 0 1/2 2/5 -8 -10 0 10 8
-2/8 -1/5 0 1/5 2/8 -5 -4 0 4 5
Обратите внимание, что центральные 3x3 пикселя ядра 5x5 в нотации с плавающей запятой - это просто ядро 3x3, то есть более крупные ядра представляют собой непрерывное приближение с дополнительными, но менее взвешенными данными.Это продолжается до более крупных размеров ядра:
-3/18 -2/13 -1/10 0 1/10 2/13 3/18
-3/13 -2/8 -1/5 0 1/5 2/8 3/13
-3/10 -2/5 -1/2 0 1/2 2/5 3/10
G_x (7x7) -3/9 -2/4 -1/1 0 1/1 2/4 3/9
-3/10 -2/5 -1/2 0 1/2 2/5 3/10
-3/13 -2/8 -1/5 0 1/5 2/8 3/13
-3/18 -2/13 -1/10 0 1/10 2/13 3/18
Точные целочисленные представления становятся непрактичными на этом этапе.
Насколько я могу судить (не имею доступа к исходной статье),«Собел» в этом отношении правильно взвешивает вклады.Решение Prewitt можно получить, опуская весовые коэффициенты расстояния и просто вводя i и j в ядре, в зависимости от ситуации.
Бонус: ядра Собеля для произвольных направлений
Таким образом, мы можем аппроксимировать x иу компонентов градиента изображения (который на самом деле является вектором, как указано в самом начале).Градиент в любом произвольном направлении альфа (измеренный математически положительно, в данном случае по часовой стрелке, так как положительный y направлен вниз) можно получить, проецируя вектор градиента на единичный вектор альфа-градиента.
Вектор альфа-единицы равен(потому что альфа, грех альфа).Для альфа = 0 ° вы можете получить результат для gx, для альфа = 90 ° вы получите gy.
g_alpha = (alpha-unit vector) dot (gx, gy)
= (cos a, sin a) dot (gx, gy)
= cos a * gx + sin a * gy
Если вы попытаетесь записать gx и gy в виде сумм вкладов соседей, вы поймете, что можете сгруппировать результирующее длинное выражение по терминам, которые применяются к одному и тому же соседнему пикселю, а затем переписать это как одно сверточное ядро с записями
G_alpha_ij = (i * cos a + j * sin a)/(i*i + j*j)
Если вы хотите приблизительное целочисленное приближение, выполните действия, описанные выше.