Рекурсивный алгоритм вычисления свертки изображения с неразделимым двумерным полиномиальным КИХ-фильтром

Вычисление свертки - одна из базовых операций в теории сигналов и цифровой обработки изображений. Для двумерного (2- D ) случая вычисление свертки изображения x ( n 1 , n ₂ ) с линейным фильтром, заданным ИХ h ( n 1 , n ₂ ) , может быть представлено в виде:

У ( П 1 , n 2 ) = Е h ( m i , m 2 ) x ( n — ^m b n 2 — m 2 ) • (1) ( m i , m 2 ) e D

Здесь y ( n 1 , n ₂ ) - выходного изображение, D - область ненулевых значений ИХ фильтра. В дальнейшем предполагается, что область D финитна, то есть рассматриваются фильтры с конечными импульсными характеристиками - КИХ-фильтры. Для определенности положим

D = [ - M - , M + ] х [ - M ^- , M + ] .

Одним из существующих подходов к быстрому вычислению 1- D и 2- D сверток, помимо быстрых ортогональных преобразований, является их рекурсивная реализация. Существующая теория и результаты в этой области существенным образом ориентированы на 1- D случай [1-3]. В частности, известный метод перехода к двумерным рекурсивным КИХ-фильтрам использует декомпозицию ИХ фильтра с помощью разделимых функций p k ( m 1 ) p l ( m ₂), каждая из которых реализуется рекурсивно [1,3]:

KL

h ⁽ m_b m 2 ) = ЕЕ ₽ kl P k ^{( m} 1 ) P l ^{( m} 2 ) ⁽²⁾ k = 0 l = 0

Как показано в работах [1,2] удобными для рекурсивной реализации свертки являются полиномиальные функции, в частности, базис МВС. Этот базис позволяет реализовать свертку рекурсивно и с минимальным (для полиномиального базиса общего вида) числом арифметических операций.

В настоящей работе предлагается метод построения 2-D рекурсивного алгоритма вычисления свертки изображения с полиномиальной ИХ. В методе не требуется разложение ИХ на разделимые звенья. Показано, что рекурсивный алгоритм, получаемый при использовании указанного метода, позволяет снизить теоретическую сложность вычисления свертки (1), оцениваемую числом арифметиче- ских операций, на 20% по сравнению с известным (использует разделимые звенья).

Статья организована следующим образом. В первом разделе описан известный алгоритм рекурсивного вычисления свертки с 2- D полиномиальной ИХ, использующий декомпозицию ИХ набором разделимых звеньев. Также в этом разделе приведены известные результаты по 1- D рекурсивной фильтрации на основе МВС - базисов. Во втором разделе дано построение предлагаемого 2- D рекурсивного алгоритма. В третьем разделе приведен сам алгоритм, представлены оценки его вычислительной сложности и дано сравнение с известным алгоритмом по сложности реализации свертки.

1. Рекурсивное вычисление 2-D свертки на основе декомпозиции КИХ фильтра с помощью разделимых звеньев

Пусть ИХ фильтра представима в виде разложения по 2- D разделимым функциям (2). Тогда выражение (1) расчета свертки можно переписать следующим образом:

KL

y ⁽ n b n 2 ) = ЕЕ р ki ц ki ^{( n} 1 , n 2 ),                    ⁽³⁾

k = 0 l = 0

где

Ц kl (nbn 2 ) =

Mx '              M 2' / x                                 (4)

= E P k ^{( m} 1 ) E P i ^{( m} 2 ) x ^{( n} 1 ^- m b n 2 ^- m 2 )

m_x =- M ^—      m 2 =- M ^—

По аналогии с работами [1-3] величины ц _kl ( n 1 , n ₂ ) назовем обобщенными моментами . Очевидно, что в соответствии с выражением (4) вычисление 2- D свертки можно производить в построчнопостолбцовой манере, а именно:

• •    производится вычисление 1- D сверток вдоль строк (формируем полуспектр одномерных моментов по горизонтали):

M +

~ l ^{( n}1 ^- m J , ⁿ 2 ) = Е P l ^{( m} 2 ) x ^{( n} 1 ^- m b n 2 ^- m 2 ); ⁽⁵⁾ m 2 =- M 2"

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

M+ ц kl(n1, n 2 )=   E Pk(m1)P l(n1- m1,n 2);          (6)

m_t =- M ( ^-

• •    рассчитывается скалярное произведение значений обобщенных моментов (6) на коэффициенты разложения ИХ (3).

Сложность вычисления 2- D свертки с использованием такого построчно-постолбцового алгоритма складывается из сложностей каждой из трех указанных групп операций.

При использовании рекурсивного подхода вычисление 1- D сверток (5) и (6) производится рекурсивно. При использовании полиномиального базиса функции p k ( m | ) и p l ( m ₂) являются полиномами:

k

P k ^{( m} ) = E a ki m , ^k = ^{0 K} .                   ⁽⁷⁾

i = 0

В работах [1,3] показано, что коэффициенты { a ki } k = ₀ ( a kk * 0) могут быть подобраны таким образом, чтобы произвольная 1- D свертка с набором функций (7) выполнялась с минимальной вычислительной сложностью (МВС) для полиномиального базиса общего вида. Рекурсивный алгоритм формирования 1- D моментов и его вычислительная сложность в сложениях U ₊ ( K ) и умножениях U * ( K ) в пересчете на один отсчет выходного изображения составляют [1,3]:

Ц 0 ( n ) = Ц 0 ( n — 1) + x ( n + M - ) — x ( n — M ⁺ — 1),

‘Ц k ^{( n} ) = Ц k ^{( n -} 1) + Ц k - 1^{( n -} 1) ^{+                  (8)}

+ p mcc ( - M ^- ) x ( n + M ^- ), 1 <  k <  K .

U ₊ ( K ) = 2 ( K + 1 ) U * ( K ) = K .

При использовании базиса МВС { p mcc } K = ₀ вычислительная сложность расчета двумерной свертки в пересчете на один отсчет выходного изображения равна:

U ₊ ( K , L ) = 3 ( K + 1 )( L + 5/3 ),

U * ( K , L ) = 2 ( K + 1 )( L + 1 ) - 1.

Суммарная сложность, таким образом, циональнавеличине:

U + ( K , L ) + U * ( K , L ) = 5 KL .

пропор-

• 2.    Построение 2-D рекурсивного алгоритма вычисления свертки

Для построения 2- D рекурсивного алгоритма вычисления свертки воспользуемся тем фактом, что любая горизонтальная строка полиномиальной импульсной характеристики степени ( K , L ) также является полиномиальной функцией степени не выше чем L . Действительно, если импульсная характеристика фильтра представима в виде степенного ряда

KL

h(mb m 2 )=XZa kimkm 2, k=0 l=0

тогда m 1 -ая строка ИХ имеет вид:

L   < KЛ hm, (m 2 )=E m 21 Ea klm1 l=Ea m1 m 2 .

l=0    ^ k=0

Введем обозначение:

L pm 1 (m 2 )= hm1 (m 2 )=Ea m m 2 .

l = 0

Тогда свертка (1) представима:

y (nb n 2 )=   Epm' (m 2 )x(n1 -mb n 2 -m 2 )

( m 1 , m 2 je D

По аналогии с (4) обозначим:

M +

Ц m (nbn 2 )= E pm (m 2 )x(n1 - mb n 2 - m 2 )

m 2 =- M 2"

M +

Цl(nbn2 )= Ецm'(n1,n2 )

m 1 =- M -

Далее, для каждой полиномиальной p m ¹ ( m ₂ ) (вид функции зависит от m 1 ) последовательность полиномиальных { p m 1 } l = ₀ следующим образом l = L ,0 :

функции построим функций

P l ^m ' ' ^{( m} 2 ^- 1 ) = p m ^{1 ( m} 2 ) ^- p m ^{1 ( m} 2 ^- 1 ) .

Как показано в работах [1,3], для последовательности таких 1- D полиномов существует эффективный алгоритм рекурсивного вычисления свертки, который в 1- D случае выглядит следующим образом (индексы m ₁ для удобства опущены):

ц l ⁽ n ) = ц l ⁽ n ^- 1) + ц l - 1 ⁽ n ^- 1) +

⁺ p i ^{( - M} - ) x ⁽ n ^{+ M} - ) ^-

‘ - p l ( M ⁺+ 1) x ( n - M ⁺- 1), l = 1, L .          ⁽¹⁶⁾

Ц 0 ( n ) = Ц 0 ( n ^- 1) ⁺

+ p ₀ ( 0 ) - ( x ( n + M - ) - x ( n - M ⁺ - 1) )

Здесь

M ⁺

Ц l ^{( n ) =} E p i ^{( m} ) ^{x ( n - m} )•                     ⁽¹⁷⁾

m = - M -

Используя этот результат, можно переписать выражение (14) следующим образом:

Ц m 1 ( П 1 , n 2 ) = Ц m 1 ( П 1 , n 2 - 1 ) + Ц l ^m - ' ( П 1 , n 2 - 1 ) +

+ p m ¹ ( - M :- ) x ( n 1 - m 1 , n ₂ + M 2" ) -

- p m ¹ ( M + + 1) x ( n 1 - m 1 , n ₂ - M 2 - 1 ), l = 1, L

Подставив это рекуррентное соотношение в равенство (15), можно получить следующее выражение:

m+ ц l(n1,n 2)=   Ец ?(n1,n 2)= m 1 =-M1-

M ⁺                 M ⁺

=  Ецm1 (n1,n2 - 1)+  ЕцM(n1,n2 - 1) + m 1 =-M'"                  m 1 =-M1-

M +

⁺ E p m ^{1 ( - M} 2 - ) x ^{( n} 1 - ^m 1 , n 2 ^{+ M} - ) ^- m i =- M 1 -

M ⁺

-  E Pm1 (M 2+ + 1) x(n1 - m1, n - - M 2+ - 1’ • m i =- M1-

Упрощая первые два слагаемых по формуле (15), получим:

Ц l ( n 1 , n 2 ) =Ц l ( n 1 , n 2 - 1 ) +Ц l - 1 ( n 1 , n 2 - 1 ) +

M ⁺

+ E Pm1(-M - ) x(n1 - m1, n 2 + M 2-)- m 1 =-M1-

M ⁺

• - E P m 1 (M 2 + 1) x ( n - m 1 , n 2 - M 2 ⁺- 1 ) •   (18)

m 1 =- M 1 -

Очевидно, вычислительная сложность полученного 2- D рекурсивного алгоритма вычисления свертки с полиномиальным КИХ-фильтром зависит от вертикального размера ИХ. Для снижения сложности операций скалярного произведения в (18) их можно реализовать также рекурсивным образом.

Действительно, любая величина p_l^{m 1} ( M ) может быть представлена как полиномиальная функция степени K (или ниже) от m ₁ . Например, для случая l = L :

PL'(M )= EM- |E a k«i | = l=0    кk=0        J

= E m f f E a k, M> К E X a ’ M = Д: ’ M ( m ) k = 0 к l = 0         J k = 0

В общем случае выполняется:

Pm1(M ) = pK’" (m,)

l = 0, L , M = M + + 1 или M = - M -- .

Каждую из этих 2 ( L + 1 ) одномерных полиномиальных функций можно представить в виде разложения по 1- D полиномиальному МВС-базису (8) ^{ P mcc ^{( m} 1 ^)} K = 0 ^:

K

P KK ’ ^M ( m 1 ) = E ₽ k ^l ’ M P mcc ( m 1 ),    l = 0, L ,        (19)

k = 0

l = 0, L , M = M ₂ ⁺+ 1 или M =- M - ••

Свертка с функциями МВС-базиса, как указывалось ранее, реализуется рекурсивно (по столбцам) в соответствии с выражением (8). Таким образом, предлагаемый алгоритм рекурсивного вычисления 2- D свертки изображения с неразделимым КИХ-фильтром представим следующим образом.

• 3.    Алгоритм

Шаг 1. Рекурсивное вычисление 1- D обобщенных моментов за счет свертки столбцов изображения с полиномами МВС по выражению (8).

Шаг 2. Вычисление 2 ( L + 1 ) скалярных произведений значений 1- D обобщенных моментов на коэффициенты (19).

Шаг 3. Подстановка полученных 2 ( L + 1 ) значений в общее рекуррентной 2- D соотношение (18) и получение значения величины ц L ( n 1 , n ₂ ) = y ( n 1 , n ₂ ) на основании предшествующих значений 2- D свертки. Этот шаг не требует ни одной операции умножения.

Вычислительная сложность предложенного алгоритма в пересчете на один отсчет выходного изображения составляет:

U + (K, L) = 2(K +1) + 2(L +1)K + (3 L + 2),

U* (K, L) = K + 2(L +1)(K +1).

или, окончательно:

U +(K, L )= 2(K +1.5)(L + 2)- 2,

U * ( K , L ) = 2 ( K + 1 )( L + 1.5 ) - 1.

Итоговая сложность пропорциональна:

U + (K, L) + U*( K, L) = 4 KL , что на 25% ниже, чем у традиционного построчнопостолбцового алгоритма.

В заключении следует отметить, что предложенный подход может быть естественным образом обобщен на ситуацию представления ИХ фильтра произвольными рекуррентными последовательностями.

Работа выполнена при поддержке Министерства образования РФ, Администрации Самарской области и Американского фонда гражданских исследований и развития (CRDF Project SA-014-02) в рамках российско-американской программы "Фундаментальные исследования и высшее образование" (BRHE).