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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (51)4 G 06 F 15/66

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

И АВТОРСКОМУ СВИДЕТЕЛЬСТВУ вВ

С5

Ж

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4040872/24-24 (22) 24. 03. 86 (46) 15. 08. 88. Бюл. Ф 30 (71) Ленинградский институт точной механики и оптики (72) С.Е = Донченко, К.И. Кучеренко, Ю.Н.Матвеев и Е.Ф.Очин (53) 621.325 (088.8) (56) Swartzlander Е., Схlbert В;,, Reed f. Inner Product Computers.—

IEEE Trans on Computers, v. С-27, У 1, Jan. 1978, р. 21-31.

Reeves А.P. Computer Architectures for image processing in the

USA. — Signal Processing, v. 3, У 3, July 1981, р. 217-230. (54) УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОГО

ВЫЧИСЛЕНИЯ ЦИФРОВОЙ ДВУМЕРНОЙ СВЕРТКИ (57) Изобретение относится к вычислительной технике и может быть ис„„SU„„1416976 А1 пользовано при цифровой обработке сигналов. Целью изобретения является сокращение аппаратурных затрат при вычислении цифровой двумерной свертки (ЦДС) в случаях, когда ядро свертки симметрично относительно центрального столбца или строки или обладает обоими видами симметрии. Указанная цель достигается тем, что для вычисления ЦДС вместо алгоритма, построенного на одновременном умножении фрагмента входного массива на матрицу отсчетов ядра свертки используется более экономный алгоритм, требующий для вычисления каждого значения ЦДС столько умножений, сколько с ф различных отсчетов содержит симметричное ядро. Это позволяет .в зависимости от вида симметрии в 2 и 4 раза сократить число умножителей, а также С сократить число некоторых других элементов устройства. 5 з.п. фалы, 8 ил., 2

1416976!

)), k

P, = D. )и+! .-W

1а m

1 параллельном формировании в соо тве тствующих узлах ш-ro блока вычисления

N промежуточных результатов (частичных сумм) Б;;

55!!110 где р 717!а ч!}

= 0

9 р !7),k

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

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

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

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

D., )м,,Ä 9(«,(где ш=1,М, n=l,M

M u N — числа строк и столбцов ядра соответственно) на И N весовых коэффициентов W„„ и вычислении суммы

М у(1и» !те! . лизации которого требуется M N умно.— жителей и И N,регистров весовых коэффициентов, используется алгоритм вычисления ЦДС с ЯСС, основанный на па- 40 раллельном умножении каждого отсчета

D -,„м«,(m=1,N) столбца входного

7+ )7)- 2 фрагмента иэображения на (0+1)/2 различных весовых коэффициентов W k (k =

1, (N+1) /2) соответствующей m-й строки ЯСС

k = п при 1 и (Я+1)/2 k = N-n+l при (И+1)/2 с.n < N, то есть S ° . ск P и суммиi, 1- !р кут ровании промежуточных результатов

)у,М

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

),! м н

7!Ч и, !У),УЧ вЂ” i,j i j- Мбу

1 )1!к 1 (!)к

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

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

Устройство для параллельного вычисления ЦДС с ЯСС размером NNN состоит из N блоков вычисления 1 -...,1)„ и суммирующего блока, образованного :сумматорами 2 и регистрами 3. Каждый блок вычисления состоит из N узлов, каждый из которых включает регистр 4; i-й (i=2,N) узел каждого блока вычисления вкямчает также сумматор 5, а 1с-N ()г=1,(N+1)72) узел каждого блока вычисления - умножитель 6 и регистр 7 сдвига.

Основными информационными магистралями устройства являются информационные входы и выходы блоков 8 и у

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

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

3 l4

Предварительно в регистры сдвига записываются весовые коэффициенты

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

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

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

М1 И м и

С ° =а — 3 0 «й+1 Nkf W

Пуе1 Пи1 1+1 - — i) Р1 -— г

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

О, щ+1 . очередного (-го) столбца

1+ Рд- — i)

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

=1., (N+1) /2) соответствующего входноro отсчета D, „+1 с информационi+ — т ных входов 8,„и соответствующих весовых коэффициентов W ), с выходов

РегистРов 7 р,1 )й весовых коэффиЦиентов, запись в регистры произведения умножителей 6 1, значений произведений

111 k

i+10 -, j 1 в регистр 4д1 значения произведения

111,1 m,1

° =О, 1+1 . «1 „= S за11)-2 1+ to=, )-К " 1,) -2 лись в регистры 4 1, значений сумм

m,)с рп,)с-1 m, k М, с-1

Б,,, = 8),, + P-,, = Я,,,, 16976

+0 +, . 1у). ),=- П,+11, ",()-1) )сеЬ))д,Ь«

1+М вЂ” —,j запись в регистры 4,< (1 (N+3) 2,N) ъ ,„, р, Е-1,Е

3HaZeHHH C S; т = S),> З + Р1,)-1, ° еj 3 i+1д — —,)-I "рй, N-C а1

=, Е. D. м. -,, . W ), (при

b- д1 — ) (N+1)/2 с b N«W f,= W N-ь+1 ) ..Одновременно с этим частичные суммы

1п, N )-(М+«! „1 1адУ > ) -(да2)

= D @1

W =W,, m=1,M, поступают на

l I

55 сумматоры первого суммирующего узла суммирующего блока и по переднему фронту этого же (j "ro ) синхроимпульса сформированные суммы записываются в его регистры. Число суммирующих узлов t суммирующего блока определяется выражением t = Г1од< М ), где Г 1 обозначает ближайшее большее целое число. Следовательно, по переднему фронту j-го синхроимпульса в регистр последнего t го узла суммирующего блока будет записан результат ЦДС м

С 1, j-(«1+И-(t-1)-,;,; (Nf.L)-(4 f) ,который на следующем такте работы устройства может быть воспринят внешним устройством (например, по переднему фронту (j+1)-ro синхроимпульса).

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

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

ЦДС с произвольным ядром размером

N+1

M x (2 ), в каждый блок вычислений

1 (m=1,M) дополнительно вводится коммутатор 16» первые информационные входы которого соединены с выходами регистра 4 „N-й ступени соответствующего вычислительного конвейера 1, а вторые информационные входы коммутатора 16 сое14169

15

25 динены с выходами регистра 4 щ„ ууу, ""

N+1 г (— )-й ступени соответствующего

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

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

В зависимости от сигнала на первом входе 17 управления режимом работы устройства, каждый из коммутаторов 16 (m=1,М) передает на выходы 9 соответствующих блоков вы Т1 числения 1 либо частичные суммы м 3,„л 1 +„„(м+1 ) .,у+„ либо частичные суммы н 1 (ирф2

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

N+1 х (— — ).

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

N+1 ядром размером (2И-1) х (— ), симметричным относительно центральной стро ки в устрой ств о до полн и тельно вводятся (М-1) сумматоров, причем выходы 1-го (1=1,M-1) сумматора 18< (фиг.7) соединены с первыми входами всех умножителей 6< > (k=1, (N+1) /2)

1-ro вычислительного конвейера 1, а первые и вторые входы 1-го сумматора 18 соединены соответственно с 1-ми

8 и (2И-1)-ми 8 М р информационными входами устройства.

В процессе работы устройства на входы 8g и 8 „> (1=1,M-1) поступают отсчеты соответственно (-(М-1) )-й и (i+ (M-1) )-й строк входного изображе55 ния, симметричных относительно i-й строки, поступающей на информационный вход 8 . Ha выходе сумматора i 8 отсчетов в каждом такте работы устрой76 6 ства формируется сумма D +<

= О,, . +О<,<„» < . соответствуюI) щих отсчетов, которая поступает на первые входы умножителей 6 соответствующего блока вычислений 1 . При этом Hà k-м (k=1, (N+1) /2) умножителе

6 „1-ro (1=1,М-1) блока вычислений

Г.

1 р формируется произведение

«Е,k

r;1 =П Ц WÅ, „==D1-< -а>,1 1 Е +

+Р -W

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

И+1 или (2M-1) х (), симметричным относительно центральной, M-й, строки.

С целью расширения функциональных возможностей устройства за счет выбора режима выполнения операции ЦДС либо с ядром, состоящим из М различных строк весовых коэффициентов, либо с ядром, состоящим из 2М-1 строк, симметричным относительно М-й строки, в устройство дополнительно вводятся (М-1) коммутаторов информационные входы 1-го (1=1,M-1) коммутатора 19р (фиг.8) соединены с (2И-1)-ми информационными входами 8лм t устройства, выходы 1-го коммутатора 19 соединены с вторыми входами 1-ro сумматора

18 отсчетов, управляющие входы всех коммутаторов 19 соединены с вторым входом 20 управления режимом работы устройств а.

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

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

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

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

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

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

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

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

N+1 умножителя () =1, 2 ) соединен с выходом j-ro регистра сдвига, входы второго сомножителя всех умножителей соединены с информационным входом блока,входы синхронизации всех умножителей и регистров соединены с первым входом синхронизации блока, входы управления сдвигом всех регистров сдвига соединены с вторым входом синхронизации блока, входы последовательной эагруз16976 8 ки данных регистров сдвига являются входом загрузки весовых коэффициентов блока, выходы старшего разряда всех регистров сдвига являются выхо5 дом весовых коэффициентов блока.

3. Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что суммирующий блок содержит t узлов, где щ0 t = log< Мl, 1 х t обозначает наименьшее целое, большее или равное величине к, входы синхронизации всех суммирующих узлов соединены с входом синхронизации блока, информационные входы первого суммирующего узла являются одноименными входами блока, информационные входы а-ro суммирующего узла (а = 2,t) подключены к одноименным выходам (а-1)-го суммирующего узла, информационный выход

-t-ro суммирующего узла является одноименным выходом блока, причем первый суммирующий узел содержит К„=ГМ/2) регистров, с,=PM/21 сумматоров, где

2Q (Y3 означает целую часть У, а В-й суммирующий узел содержит R =(Rц, /21 регистров и с = f R a 1 /2 ) сумматоров, входы синхронизации всех регистров

b-го суммирующего узла (b=1,t) соединены с входом синхронизации b-ro суммирующего узла, выходы m-го сумматора b-го суммирующего узла (ш =

1,с ) соединен с входом m-го регистра, входы сумматоров и R<-го регистра (при R1;-с +1) являются информационными входами суммирующего узла, выходы регистров являются информационными выходами суммирующего узла.

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

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

5. Устройство по п. 1 и 2, о тл и ч а ю щ е е с я тем, что, с

1416 целью обеспечения возможности вычисления цифровой двумерной свертки с симметричным относительно центральной строки ядром, имеющим 2И-1 строк, 6

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

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

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

/4 6

Фиг.f

1416976

1416976

l4l6976

1416976

11 I е е е

Ф Ф Е е Ф е

1416976

° б

° б

° 1

° бб

° ° Ý

° Фб

1416976

Составитель Yi. Пышный

Редактор J1. Пчолинская Техред Л. Олийнык Корректор Л. Патай

Заказ 4065/46

Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4