Pull to refresh

О градиенте изображения

Image processing *

Аннотация


В статье рассказывается о вычислении градиента по изображению, с использованием разностных шаблонов. Предлагается очевидный и красивый способ оптимизировать последовательность: «Смаз -> Вычисление градиента». Статья является необходимой преамбулой к планируемой статье о быстрых и хитрых алгоритмах выделения контуров и углов.

Введение


Градиент — векторная величина, показывающая направление наискорейшего возрастания некоторой величины. В нашем случае «некоторая величина» — это двумерная функция яркости изображения, допустим что мы рассматриваем «псевдонепрерывное» изображение, тогда вектор градиента определяется формулой
image
где I – это наше изображение.
На практике, картинка дискретна и в классическом смысле производной не существует, поэтому используют ее разностные аналоги, например в простейшем случае
image
— левая разностная производная. Разностных аналогов существует великое множество, и все они обладают различными порядками аппроксимации, подробнее здесь. Увеличение порядка аппроксимации, например как тут в теории должно приводить к увеличению точности расчета производной. Более того, увеличив количество элементов в аппроксимации можно повысить устойчивость к шуму.
К примеру, будем использовать разностный аналог первой производной, шестого порядка точности аппроксимации по шагу дискретизации:
image
А теперь предположим, что I(i,j)независимые случайные величины, распределенные по любому закону распределению, и посмотрим дисперсии:
  1. Для первой аппроксимации получаем: image
  2. Для второй аппроксимации получаемimage

Как правило дисперсию аддитивного шума можно считать изотропной и тогда вытекает соотношения
image

Таким образом, коэффициент усиления шума (1.17), в случае аппроксимации производной разностью более высокого порядка, меньше чем коэффициент (2) в случае аппроксимации производной левой разностью. Логично, что при этом сильно возрастают вычислительные затраты. А теперь рисуночки:

Рисунок 1Исходное изображение, 2модуль градиента по первой формуле, 3модуль градиента по второй формуле.
image

В итоге мы рассчитали градиент, на котором шумовая компонента увеличилась не в 2 раза а всего в 1.17 раз, однако опять же, если на картинке есть шум, то было бы неплохо его диспресию предварительно (до вычисления градиента) уменьшить – например, смазать исходное изображение I, то есть сделать свертку например с гауссовым ядром f. Тогда градиент запишется как:
image
однако, из свойств оператора свертки известна формула:
image

Мы вычисляем производную не по изображению, а по ядру f; и выбор точеного шаблона для расчета разностного аналога производной ограничивается лишь размерами окна.

Таким образом, можно построить алгоритм «Смаз — Вычисление градиента»:
  1. Вычисляем разностные аналоги производных по ядру,
  2. Сворачиваем полученные ядра с изображением
  3. В итоге, получим компоненты вектора градиента.

В вычислительном плане:
Было: Одна свертка c окном (NxN) для смаза, + две свертки со специфическими окнами (1xN, Nx1) для вычисления производных.
Стало: Две свертки со специфическими окнами (но уже NxN) для вычисления производных.
Вычисление градиента смазанного изображения задача, которая очень часто встречается, например, в хитрых детекторах углов и контуров, о которых будет следующая статья.

Что будет работать быстрее, а главное — устойчивее к шуму? Я предлагаю ответить на этот вопрос в комментариях к статье самим читателям.
Tags:
Hubs:
Total votes 45: ↑45 and ↓0 +45
Views 21K
Comments Comments 18