Двумерная апериодическая свертка и корреляция

Важное место среди операций линейной обработки сигналов занимает операция перемножения матриц одинаковой размерности. Такая операция имеет вид:

, (5.15)

где и исходные матрицы порядка N, а - результирующая матрица того же порядка. Каждый элемент матрицы формируется в соответствии с выражением:

где - элементы исходных матриц.

На основе операций (5.15) и (5.16) выполняется вычисление функций двумерной апериодической свертки/корреляции исходного двумерного сигнала (изображения) с двумерным ядром. Подобное преобразование часто используется как для удаления шумов, так и для выделения мелких объектов.

Математически двумерная апериодическая свертка может быть описана следующим образом:

где - отсчеты результатов вычислений (отсчеты свертки), - отсчеты весовой функции окна (ядра свертки) размерностью M x M отсчетов, причем N >> M. Очевидно, что размерность матрицы, описывающей двумерную свертку, равна (N + M-1) x (N + M -1) отсчетов. Поэтому матрица исходных данных также должна быть дополнена до указанного размера нулевыми элементами по краям кадра.

Отсчеты свертки формируются при перемещении окна вдоль строки исходного изображения. Для каждого положения окна формируется один отсчет свертки, после чего окно сдвигается на один элемент вдоль строки (т.е. на один столбец). Обработка начинается с элемента x исходного изображения. После прохождения i-й строки изображения (i= 1,N) окно смещается на одну строку вниз и возвращается к началу следующей (i + 1)-й строки изображения. По окончании обработки кадра изображения окно перемещается в исходное положение.

При вычислении свертки можно распараллелить вычисления по столбцам окна сканирования, выполняя параллельно вычисление произведений столбцов ядра свертки и столбцов текущей полосы сканирования изображения. Поэтому для окончательного вычисления отсчета свертки достаточно сформировать сумму:

(5.18)

соответствующую отсчету свертки с номером j, расположенному в средней строке полосы шириной М.

Представляет интерес распараллеливание по разрядным срезам, поскольку в этом случае практически исключается операция умножения [16]. При разрядно-срезовой обработке данные должны быть представлены в формате с фиксированной точкой. Представим значение элемента изображения в следующем виде :

, (5.19)

где - q-ый разряд (q= 1,…, Q), (g=(1,Q)) где Q - разрядность данных.

С учетом этого процедура вычисления свертки принимает вид:

(5.20)

Таким образом, процедура двумерной апериодической свертки для одного положения окна сводится к M x N x Q операциям сложения и (Q-1) операциям сдвига. Умножение под знаком суммы сводится к операции вида :

при и при .

Поэтому разрядно-срезовый алгоритм вычисления свертки или корреляции для одного положения окна может быть представлен в виде [16]:

начало;

для цикл:

для цикл:

для цикл:

если , то

иначе ;

;

конец цикла по ;

конец цикла по ;

;

конец цикла по ;

;

конец.

Физический смысл функций свертки и корреляции состоит в том, что они являются количественной мерой совпадения (сходства) двух последовательностей f(x) и g(x). При этом наиболее полно мера сходства может быть определена по функции корреляции, в связи с чем функция взаимокорреляции (или кросскорреляции) может быть использована для распознавания сигналов. Если распознаваемый сигнал f(t) точно соответствует эталонному сигналу g(t), то результирующий сигнал w^k(t) принимает значение:

w^k(t)=max при f(t)º g(t),

что соответствует функции автокорреляции. Если сигналы отличаются, то w^k(t)<max.

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

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