Устройство для параллельного вычисления цифровой двумерной свертки Советский патент 1988 года по МПК G06T7/60 

О)

|

05

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

Цель изобретения - сокращение ап- паратурных затрат при вычислении цифровой двумерной свертки (ЦЦС) с ядром, симметричным относительно центрального столбца.

Операции ЦДС с ядрами, имеющими симметрию такого вида, используются, например, при распознавании симметричных символов и объектов, а

:также для коррекции изображений, по- лу енных посредством оптических сие-

|Тем со щелевой диафрагмой.

Уменьшение аппаратурных затрат при реализации операции ЦДС с ядром, симметричным относительно центрального столбца (ЯСС), стали возможными вследствие изменения алгоритма функционирования устройства. Вместо алгоритма вычисления ЦДС, основанного на параллельном умножении М-N отсчетов входного фрагмента изображения ,.,„.М|1,,,,(где ,

М и N - числа строк и столбцов ядра соответственно) на M N весовых коэффициентов Wmn и вычислении суммы

М N

1,, Dt.-,j- W,, для pea;лизации которого требуется M-N умножителей и M N регистров весовых коэффициентов, используется алгоритм вычисления ЦДС с ЯСС, основанный на па раллельном умножении каждого отсчета

D. м+1 .(,М) столбца входного ,+ т--у-и

фрагмента изображения на (N+1)/2 раз- личных весовых коэффициентов W (k 1, (N+1)/2) соответствующей m-й строки ЯСС

Р-.;. I,

i+mJ ±L.;-Wtn(,,

1

параллельном формировании в соответ- ствующих узлах т-го блока вычисления N промежуточных результатов (частичч .П

ных сумм) S ,

,m,n

ni,n,,1Л, „ 1 .,

1,) bj-i + PI,,- - bN,

где 8,7 О,

рн1,п р т.к . .l- i,j

k п при п (N+1)/2; k N-n+1 при (N+1),

tn, И ч;- „ m, n есть S .. Х- Р ; -. J )

и суммировании промежуточных результатов

r.tJ -,)

с выходов блоков вычисления в

Q

5

0

5

0

0

5

.5

суммирующем блоке, при котором формируется результат ЦДС

мJ Л1 .N. У Т

1 f 1 ; ; - - t ; щ-г J iflri J n ,

При этом каждый промежуточный результат (частичная сумма) последовательно накапливается при движении по блоку вычисления в течение N тактов.

На фиг.1-3 изображена структурная схема устройства для параллельного вычисления цифровой двумерной свертки с ЯСС размером на фиг.4 - структурная схема одного из возможных вариантов реализации суммирующего блока для М 9; на фиг.5 и 6 -. структурная схема блока вычисления устройства для параллельного вычисления с расширенными функциональными возможностями; на фиг. 7 и 8 - фрагменты 1-го (,М-1) блока вычисления устройства с сумматором отсчетов (фиг.7) и сумматором отсчетов и ком- Статором отсчета (фиг.8) на входе блока вычисления.

Устройство для параллельного вы числения ЦДС с ЯСС размером MxN состоит из М блоков вычисления 1 ,,.., (.., 11VI и суммирующего блока, образованного .сумматорами 2 и регистрами 3. Каждый блок вычисления состоит из N узлов, каждый из которых включает регистр Aj i-й (,N) узел каждого блока вычисления включает также сумматор 5, а k-й ( , (N+r)/2) узел каждого блока вычисления - умножитель 6 и регистр 7 сдвига.

Основными информационными магистралями устройства являются информационные входы и выходы блоков 8 и 9 вычисления соответственно, выход сз ммирующего блока, являющийся выходом устройства 10, и входы загрузки весовых коэффициентов блоков 11 вычисления.

Устройство для параллельного вычисления цифровой двумерной свертки работает под управлением некоторого внешнего устройства следующим образом.

3

Предварительно в регистры сдвига записываются весовые коэффициенты ЯСС свертки. Регистры 7 постоянно находятся в состоянии ввода и сдвига по следовательно,го кода, и запись коэффициентов осуществляется поразрядно одновременно в регистры сдвиг всех ic-x (, (N+1)/2) узлов всех блоков вычисления начиная со старши разрядов весовьга коэффициентов первой строки ядра свертки. Для записи весовых коэффициентов внешнее уст- ройство формирует на входах М (k 1,(N+1)/2) загрузки весовых коэф- фициентов устройства соответствующи разряды весовых коэффициентов ;k-x .столбцов ЯСС и формирует синхроимпульсы на втором входе 14 синхронизации устройства (которые через выходы 13ц весовых коэффициентов пе- реписьюаются в другие блоки 1).

После окончания загрузки весовых коэффициентов устройство готово к вычислению ЦДС и ЯСС. В каждом так- те вычисления ЦДС с ЯСС размером

М N

С.. ZIII D.

М

(Wn,W,N-h+i )

на информационные входы 8p,( ,М-1) устройства из внешнего устройства поступают соответствующие отсчеты

D. д4) . очередного (j-ro) столбца nrn-- ij

входного фрагмента изображения. По переднему фронту очередного (j-ro) синхроимпульса на входе 15 синхронизации устройства в каждом блоке вычисления 1 (,М) выполняются следующие операции: запись в регистры входных данных умножителей 6 ( (k 1-,(N+1)/2) соответствующего входнос информационго

отсчета D. м-и .

+ т5- F J

ных ВХОДОВ 8 И соответствующих весовых коэффициентов W с выходов регистров 7|fl(( весовых коэффициентов запись в регистры произведения умножителей 6„ значений произведений т т

„ м+1 f (flV. +m--яг- , j-1

Г

запись

в регистр 4, значения произведения

заРМ-а,-.п.г,).1 зГ;;.1

пись в регистры шЛ m, S{,j.l - S},,-.j

-J значений сумм

+ Р

hi, k

l,j-l

S

M,V- f, j-э

6

,4.-«il,.,

4

-tD.

W

fcrl

л.т--5,(/-2)-Ь -Ь Л запись в регистры 4mf (l()/2,N)

сумм S

|,,е Л )-1

S

m,f-f 1.ГЗ

,4n.-Mi,j.jW,f,.,.,

,(j-21-f t -W.t

+

+ i,ri

(при

(N+1) N; W,fe W.N. ). .Одновременно с этим частичные суммы

1

S i, D,4n.-J, ,--(n.i) Ww«, Wft,., , поступают на

сумматоры первого суммирующего узла суммирующего блока и по переднему фронту этого же (j-ro) синхроимпульса сформированные суммы записываются в его регистры. Число суммирующих узлов t суммирующего блока определяется выражением t flog, Ml, гдеГ ) обозначает ближаГяиее большее целое число. Следовательно, по переднему фронту j-ro синхроимпульса в регистр последнего t-ro узла суммирующего

5

0

5

0

5

0

5

блока будет записан результат ВДС

м

с,,-()-(1м)) ,,(.,- ,

.который на следующем такте работы устройства может быть воспринят внешним устройством (например, по переднему фронту (j+1)-ro синхроимпульса).

Таким образом, процесс формирования каждого-результата ЦДС состоит из 2 тактов (запись сомножителей и запись произведения) формирования произведений, N тактов последовательного накопления частичных сумм (промежуточных результатов) при движении по вычислительному конвейеру и t тактов суммирования частичных сумм в суммирующем блоке. При этом в каждом такте работы устройства формируется новый результат ЦДС.

С целью расширения функциональных возможностей устройства для параллельного вычисления цифровой двумерной свертки за счет обеспечения дополнительной возможности выполнения ЦДС с произвольным ядром размером

М к ( в каждый блок вычислений

1. (,М) дополнительно вводится коммутатор 16, первые информационные входы которого соединены с выходами регистра ступени соответствующего вычислительного конвейера 1, а вторые информационные входы коммутатора 16 соединены с выходами регистра 4

,N+K

(,-)-и ступени соответствующего

N+j

г

блока вычислений 1. Выходы комму татора 16 являются выходами 9 соответствующего блока вычислений 1 и соединяются с соответствующими входами сумматора 2 регистра 3 (фиг.4) суммирующего блока.

Управляющие входы всех коммутаторов 16 соединены с первым выходом 17 управления режимом работы устройства.

В зависимости от сигнала на первом входе 17 управления режимом работы устройства,каждый из коммутаторов 16 ( ,М) передает на выходы 9, соответствующих блоков вычисления 1 либо частичные суммы

N

llj

). i-Ntn

ч 1

либо частичные суммы

Ntl(N4tV-Z

D,

W-1

W

),r()Ki,n

которые далее суммируются суммирующим блоком с образованием либо результата ЦДС с ЯСС размером MxN (в первом случае), либо результата ЦДС с произвольным ядром размером М х

,N+K X С-у-).

Для реализации операции свертки с ядром размером (2M-1)xN, обладающим центральной симметрией, или с

N+1

ядром размером (2М-1) х ( -А- ) , симметричным относительно центральной строки в устройство дополнительно вводятся (М-1) сумматоров, причем выходы 1-го ( ,М-О сумматора 18 (фиг.7) соединены с первыми входами всех умножителей 6 ( , (N+1)/2) 1-го вычислительного конвейера 1., а первые и вторые входы 1-го сумматора 18 соединены соответственно с 1-м 8g и (2М-1)-ми информационными входами устройства.

В процессе работы устройства на входы 8 и 8-,j( (,М-1) поступают отсчеты соответственно (1-(М-1))-й и (1+(М-1))-й строк входного изображения, симметричных относительно i-й строки, поступающей на информационны вход 8|. На выходе сумматора 18р отсчетов в каждом такте работы устрой

14169766

ства формируется сумма 0{.(«-е;, i +Du(u,f,,j соответствующих отсчетов, которая поступает на первые входы умножителей 6г)(Соответ.ствующего блока вычислений 1. При 1ЭТОМ на k-M ( , (N+1 )/2) умножителе 6 р), 1-го ( ,М-1) блока вычислений 1f формируется произведение

10

Л1,

P,-,i De,J-Wp,D,.(,,..Wg,4+ D;

W,

i(M-n,j k

которое учитывается в соответствую- щих частичных суммах, что позволяет на выходе устройства получать результаты ЦДС с ядром размером (2М-1) х N

N+1 или (2М-1) X (-у-), симметричным относительно центральной, М-й, строки. С целью расширения функциональных возможностей устройства за счет выбора режима выполнения операции ЦДС либо с ядром, состоящим из М различных

строк весовых коэффициентов, либо с ядром, состоящим из 2М-1 строк, симметричным относительно М-й строки, в устройство дополнительно вводятся (М-1) коммутаторов, информационные

входы 1-го (,М-1) коммутатора 19 (фиг.8) соединены с (2М-1)-ми инфор- мационньми входами 8( устройства, выходы 1-го коммутатора I9j соединены с вторыми входами 1-го сумматора 18f отсчетов, управляющие входы всех коммутаторов 19 соединены с вторым входом 20 управления режимом работы устройства.

В зависимости от сигнала на втором входе 20 управления режимом работы устройства с выходов каждого коммутатора 19 ( на входь соответствующих сумматоров 18 отсчетов подаются либо отсчеты с (2М-1)-х информационных входов ,-{ устройства, либо нулевые коды. На выходах устройства формируются результаты ЦДС, в первом случае с ядром, состоящим из (2М-1) строк весовых коэффициентов, а во втором случае - с ядром из М строк.,

Формула изобретения.

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

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

2, Устройство по п. 1, о т л и - ч а JO щ, е е с я тем, что каждый

иN+1

блок вычисления содержит регистров сдвига, где N - нечетное число

« N+1

столбцов ядра свертки, - умножителей, N-1 сумматоров и N регистров, выход К-го регистра (,N-1) соединен с входом первого слагаемого К-го сумматора, выход N-ro регистра является информационным выходом блока, выход первого умножителя соединен с информационным входом первого регистра и входом второго слагаемого (N-1)- го сумматора, выход i-ro умножителя

(, -т) соединен с входом второго

слагаемого 1-1 и (N-i)-ro сумматоров, ,N+1

ки данных регистров сдвига являются входом загрузки весовых коэффициентов блока, выходы старшего разряда всех регистров сдвига являются выхо дом весовых коэффициентов блока.

3. Устройство по п. чающееся тем.

1

о т л и 10

15

что суммирую щий блок содержит t узлов, где t ploga MI, f X обозначает наименьшее целое, большее или равное в личине X , входы синхронизации всех суммирующих узлов соединены с входо синхронизации блока, информационные входы первого суммирующего узла являются одноименными входами блока, информационные входы а-го суммирую щего узла (a 2,t) подключены к одноименным выходам (а-1)-го сумми20 рующего узла, информационный выход t-ro суммирующего узла является одн именным выходом блока, причем первы суммирующий узел содержит регистров, с ГМ/21 су1.1маторов, гд

25 tY означает целую часть Y, а а-й

(Суммирующий узел содержит Ra fRq-i / регистров и Со( CRc(-i/2l сумматоро входы синхронизации всех регистров Ь-го суммирующего узла (,t) сое30 динены с входом синхронизации Ь-го суммирующего узла, выходы т-го сумматора Ь-го суммирующего узла (т 1jC.) соединен с входом га-го регистра, входы сумматоров и R(,° Р

35 гистра (при ) являются инфор мационными входами суммирующего узла, выходы регистров являются информационными выходами суммирующего узла.

40 « Устройство по пп. 1 и 2, о т - личающееся тем, что, с целью обеспечения возможности вычисления цифровой двумерной свертки с произвольным ядром, имеющим (Р+1)/2

выход ()-го умножителя соединен с 45 столбцов, Р - число регистров блока

N-1 входом второго слагаемого ()-го сумматора ,вход первого сомножителя j-ro

N+1

умножителя (j 1 -о-) соединен с выходом j-ro регистра сдвига, входы второго Ьомножителя всех умножителей соединены с информационным входом блока,входы синхронизации всех умножителей и регистров соединены с первым входом синхронизации блока, входы управления сдвигом всех регистров сдвига соединены с вторым входом синхронизации блока, входы последовательной загрузвычислений, в каждый из М блоков вычислений введен коммутатор, первый и второй информационные входы которого соединены с выходами Р-го и (Р+1)/2gQ го регистров соответственно, выход коммутатора является информационным выходом блока, управляющий вход ком- мутатора соединен с первьм входом уп равления режимом работы блока, входы

55 управления режимом работы всех блоко вычислений соединены с одноименным входом устройства.

5. Устройство по п, 1 и 2,

личающееся

тем, что,

т -

с

ки данных регистров сдвига являются входом загрузки весовых коэффициентов блока, выходы старшего разряда всех регистров сдвига являются выходом весовых коэффициентов блока.

3. Устройство по п. чающееся тем.

1

о т л и

что суммирующий блок содержит t узлов, где t ploga MI, f X обозначает наименьшее целое, большее или равное величине X , входы синхронизации всех суммирующих узлов соединены с входом синхронизации блока, информационные входы первого суммирующего узла являются одноименными входами блока, информационные входы а-го суммирующего узла (a 2,t) подключены к одноименным выходам (а-1)-го суммирующего узла, информационный выход t-ro суммирующего узла является одноименным выходом блока, причем первый суммирующий узел содержит регистров, с ГМ/21 су1.1маторов, где

tY означает целую часть Y, а а-й

(Суммирующий узел содержит Ra fRq-i /2 регистров и Со( CRc(-i/2l сумматоров входы синхронизации всех регистров Ь-го суммирующего узла (,t) соединены с входом синхронизации Ь-го суммирующего узла, выходы т-го сумматора Ь-го суммирующего узла (т 1jC.) соединен с входом га-го регистра, входы сумматоров и R(,° Р

гистра (при ) являются информационными входами суммирующего узла, выходы регистров являются информационными выходами суммирующего узла.

« Устройство по пп. 1 и 2, о т - личающееся тем, что, с целью обеспечения возможности вычисления цифровой двумерной свертки с произвольным ядром, имеющим (Р+1)/2

вычислений, в каждый из М блоков вычислений введен коммутатор, первый и второй информационные входы которого соединены с выходами Р-го и (Р+1)/2gQ го регистров соответственно, выход коммутатора является информационным выходом блока, управляющий вход ком- мутатора соединен с первьм входом управления режимом работы блока, входы

55 управления режимом работы всех блоков вычислений соединены с одноименным входом устройства.

5. Устройство по п, 1 и 2,

ичающееся

тем, что,

т -

с

1416976

целью обеспечения возможности вычисления цифровой двумерной свертки с симметричным относительно центральной строки ядром, имеющим 2М-1 строк, М - число блоков вычисления устрой- ства в п-й блок вычислений (п 1,М-1) введен дополнительный сумматор, выход которого соединен с входами второго сомножителя всех умно- жителей блока, а первый и второй входы дополнительного сумматора являются информационными входами блока,

6. Устройство по п. 5, о т л и - чающееся тем, что, с целью

10

76

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

%Т

.«-/./

iL...

Н,ы Т ,

Г

Изобретение относится к вычислительной технике и может быть использовано при цифровой обработке сигналов. Целью изобретения является сокращение аппаратурных затрат при вычислении цифровой двумерной свертки (ЦДС) в случаях, когда ядро свертки симметрично относительно центрального столбца или строки или обладает обоими видами симметрии. Указанная цель достигается тем, что для вычисления ЦДС вместо алгоритма, построенного на одновременном умножении фрагмента входного массива на матрицу отсчетов ядра свертки используется более экономный алгоритм, требующий для вычисления каждого значения ЦДС столько умножений, сколько различных отсчетов содержит симметричное ядро. Это позволяет .в зависимости от вида симметрии в 2 и 4 раза сократить число умножителей, а также сократить число некоторых других элементов устройства, 5 з.п. ф-лы, 8 ил, , с (Л с

V/J

V

//-/,/

/-/.;

r3N S

//«.

W-/J

/Jy

Afy

.

MJ

ч

wy

j:

A/y

///

А/У

в

12.

.,..«С/1 5

-/.

LtZ

2 I

i

(1

n-i

S

V(

lt.tN-i-3 y

A/.r

«.l

«.

у ч

г

M

z

.

/ffФиг. 2

Фиг.

I3ei

15

IL

St/fc 11

ISt

ftet

физ.б

iSei

9

t

.«

I

let

la

... ...

fffi

15

fJes

.9