лых чисел
;
возможность локальной свертки без преобразований
(
таких
как БПФ и ТЧП
);
минимальное число обращений к элементам после
-
довательности и маски
,
задающей область свертки
;
простота програм
-
мирования и отсутствие ограничений на длину последовательности
(
в
отличие от методов
,
использующих кольцо целых чисел и модульную
арифметику
);
возможность б
´
ольшего сокращения операций за счет раз
-
деления ядра
(
для многомерных сигналов
).
Метод имеет и недостатки
,
а именно
,
во
-
первых
,
он эффективен
только тогда
,
когда разностная последовательность
(
c
0
. . . c
K
)
разреже
-
на
,
т
.
е
.
содержит существенные нулевые области
.
Если все
c
k
= 0
,
то требуется больше вычислительных операций
,
чем непосредствен
-
ная свертка
.
Таким образом
,
этот метод имеет узкое применение
.
Во
-
вторых
, “
бегущая сумма
”
s
n
будет накапливать ошибку
,
если в процес
-
се вычисления
s
n
происходит округление
.
Поэтому метод не приемлем
для вычислений с плавающей точкой
.
Приложениек обработкеизображения
.
Основным приложением
метода свертки с вычислением разностей является обработка изобра
-
жения
.
В задачах распознавания образов мы часто сталкиваемся с боль
-
шими ядрами
,
состоящими из нулей и единиц
.
Пусть исходное изобра
-
жение задано матрицей
|
f
m,n
|
,
где координаты
0
≤
m < M
,
0
≤
n < N
;
ядро задано матрицей
|
c
k,l
|
,
где
0
≤
k
,
l < K
,
и результат свертки запи
-
сывается в матрицу
|
s
m,n
|
.
Двумерная дискретная свертка определяется
выражением
s
m,n
=
m n
f
m ,n
c
m
−
m, n
−
n
.
(3)
Для реализации двумерной свертки методом разностного интегри
-
рования необходимо
: 1)
определить способ сканирования
(
то есть путь
окна по исходному изображению
)
таким образом
,
чтобы текущая сумма
вычислялась из предыдущей за минимальное число операций
;
простей
-
ший способ
—
сканирование зигзагом
(
рис
. 1); 2)
вычислить предва
-
рительно разностную матрицу
|
c
k,l
|
для каждого из возможных напра
-
влений движения
;
в случае сканирования зигзагом таких матриц будет
три
(
влево
,
вниз и вправо
); 3)
определить ненулевые элементы в раз
-
ностных матрицах и записать их в индексный массив
.
Особенно выгод
-
но предварительно рассчитать готовое смещение относительно начала
(
центра
)
матрицы ядра
; 4)
реализовать цикл сканирования
,
в котором
будут использоваться индексы
(
смещения
)
разностной матрицы в зави
-
симости от направления движения
.
На рис
. 2
приведена разностная матрица при движении налево диска
радиуса
R
= 4
,
5
.
Всего ядро имеет
57
ненулевых точек
,
в то время
как разностная матрица только
18.
Таким образом
,
выигрыш в числе
операций составляет
(57
−
18)
/
57 = 64
%.
ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. “
Приборостроение
”. 2005.
№
3 61
