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

1416976 Составитель М, ПышныйРедактор Л. Пчолинская Техред Л, Олийнык Корректор Л,Патай Заказ 4065/46 Тираж 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д, 4/5= О,Р уУ),17 Изобретение относится к вычислительной технике и может быть использовано при обработке изображений, например, с целью распознавания симметричных символов и объектов, а также для коррекции изображений, полу-. ченных посредством оптических систем со щелевой диафрагмой.Цель изобретения - сокращение аппаратурных затрат при вычислении цифровой двумерной свертки (ЦДС) с ядром, симметричным относительно цент рального столбца.Операции ЦДС с ядрами, имеющими симметрию такого вида, используются, например, при распознавании симметричных символов и объектов, а также для коррекции изображений, полуЧенных посредством оптических сис,тем со щелевой диафрагмой.Уменьшение аппаратурных затрат при реализации операции ЦДС с ядром, симметричным относительно центрального столбца (ЯСС), стали возможными вследствие изменения алгоритма функционирования устройства, Вместо алгоритма вычисления ЦДС, основанного на параллельном умножении М Б отсчетов входного фрагмента изображения П., им ,7)б 1,(где ш=1,М, п=1,М М и М - числа строк и столбцов ядра соответственно) на МгН весовых коэффициентов )7) и вычислении суммыМ у 21 ителизации которого требуется М Н умно. - жителей и ММ,регистров весовых коэффициентов, используется алгоритм вычисления ЦДС с ЯСС, основанный на па раллельном умножении каждого отсчета Р, м ,(ш=1,М) столбца входного7+ )7)"фрагмента иэображения на (0+1)/2 различных весовых коэффициентов Ы (к =1, (21+1)/2) соответствующей ш-й строки ЯСС 1 с = п при 1 с п(И+1)/2;11 с = М-и+1 при (И+1)/2 С и с И,то есть 8ск 2 Р и сумми 1,1-)бк)т Эровании промежуточных результатов)Уу, )чБ, с выходов блоков вычисления в)суммирующем блоке, при котором форми"руется результат ЦДС=;8",.". =. Е Р" .,тк 1 1) 1)кПри этом каждый промежуточный результат (частичная сумма) последовательно накапливается при движении поблоку вычисления в течение Б тактов.Ча фиг.1-3 изображена структурнаясхема устройства для параллельноговычисления цифровой двумерной свертки с ЯСС размером МдВ; на фиг.4 структурная схема одного из возможных вариантов реализации суммирующего блока для М = 9; на фиг.5 и 6 - .структурная схема блока вычисленияустройства для параллельного вычисления с расширенными функциональнымивозможностями; на фиг. 7 и 8 - фрагменты 1-го (1=1,М) блока вычисления устройства с сумматором отсчетов(фиг.7) и сумматором отсчетов и ком)мутатором отсчета (фиг.8) на входеблока вычисления.Устройство для параллельного вычисления ЦДС с ЯСС размером М)10 состоит из М блоков вычисления 1 ),11 и суммирующего блока, образованного :сумматорами 2 и регистрами 3. Каждый блок вычисления состоит из И узлов, каждый из которыхвключает регистр 4; -й (=2,Н) узел каждого блока вычисления вкямчает также сумматор 5, а )с-й )гд 1,(К+1)72)узел каждого блока вычисления - умно- житель 6 и регистр 7 сдвига. Основными информационными магистралями устройства являются информационные входы и выходы блоков 8 и 9 вычисления соответственно, выход суммирующего блока, являющийся выходом устройства 10, и входы загрузки весовых коэффициентов блоков 11 вычисления.Устройство для параллельного вычисления.цифровой двумерной свертки работает под управлением некоторого внешнего устройства следующим образом,3 14Предварительно в регистры сдвига записываются весовые коэффициенты ЯСС свертки. Регистры 7 постоянно находятея в состоянии ввода и сдвига последовательного кода, и запись коэффициентов осуществляется поразридио одновременно в регистры сдвига всех Е-х В=1(И+1)/2) узлов всех блоков вычисления начиная со старших разрядов весовых коэффициентов первой строки ядра свертки. Для записи весовых коэффициентов внешнее уст" ройство формирует на входах 12 ), Ь = = 1,(Я+1)/2) загрузки весовых коэффициентов устройства соответствующие разряды весовых коэффициентов К-х столбцов ЯСС и формирует синхроимпульсы на втором входе 14 синхронизации устройства (которые через выходы 13) весовых коэффициентов переписываются в другие блоки 1).После окончания загрузки весовых . коэффициентов устройство готово к вычислению ЦДС и ЯСС. В каждом такте вычисления ЦДС с ЯСС размером М 1 И 16976(и+1)/2 с ь и; и (= и 11 )р). одновременно с этим частичные суммыре М(1 й 1 г ы= аду --) - (аг)1 рИ 1Я,=и, ),) , р ш,М, поступают на1, - +1 15 20 25 30 35 40 45 50 55 О, 1+1 . очередного Ц-го) столбца 1+ Рд- -гвходного фрагмента изображения, По переднему фронту очередного (1-го) синхроимпульса на входе 15 синхронизации устройства в каждом блоке вычисления 1 (ш=1,М) выполняются следующие операции: запись в регистры входных данных умножителей 6Е й =1.,(И+1)/2) соответствующего входного отсчета Р, 1 с информацион 1+н 1ных входов 8,и соответствующих весовых коэффициентов И,с с выходов регистров 71)й весовых коэффициентов, запись в регистры произведения умножителей 6 т 1 с значений произведений1 )с1+1-, ) 1 У" 1, )-1 Рв регистр 4 д 1 значения произведения1,1 1,1 Р =011 И = Б,. г р зау.1 1,) -2 р лись в регистры 4 ), значений сумм1, 11, )с1 и, )м, сна информационные входы 8,(ш=1,М)устройства из внешнего устройствапоступают соответствующие отсчеты сумматоры первого суммирующего узласуммирующего блока и по переднемуфронту этого же Ц "го) синхроимпульса сформированные суммы записываютсяв его регистры. Число суммирующихузлов г, суммирующего блока определяется выражением С = Г 1 ояг М, где Г 1обозначает ближайшее большее целоечисло. Следовательно, по переднемуфронту )-го синхроимпульса в регистрпоследнего -го узла суммирующегоблока будет записан результат ЦДСмС 1,-(1+г)-(+-1)- - 1 , 1, -(м 1 г)-(+-м 1 фгкоторый на следующем такте работыустройства может быть воспринят внешним устройством (например, по переднему фронту (З+1)-го синхроимпульса),Таким образом, процесс формирования каждого результата ЦДС состоитиз 2 тактов (запись сомножителей изапись произведения) формированияпроизведений, И тактов последовательного накопления частичных сумм (промежуточных результатов) при движениипо вычислительному конвейеру итактов суммирования частичных суммв суммирующем блоке. При этом в каждом такте работы устройства формируется новый результат ЦДС,С целью расширения функциональныхвозможностей устройства для параллельного вычисления цифровой двумерной свертки за счет обеспечения дополнительной возможности выполненияЦДС с произвольным ядром размеромИ+1М х ( 2 ), в каждый блок вычислений1(ш=1,М) дополнительно вводитсякоммутатор 16 первые информационные входы которого соединены с выходами регистра 4 1 И-й ступени соответствующего вычислительногоконвейера 1 , а вторые информационные входы коммутатора 16 й сое14169 10 15 20 25 ао динены с выходами регистра 4 И+1г ( - )-й ступени соответствующего2блока вычислений 1 . Выходы коммутатора 16 являются выходами 9 у, соответствующего блока вычислений 1 и соединяются с соответствующими входами сумматора 2 регистра 3 (Фиг.4) суммирующего блока.Управляющие входы всех коммутаторов 16 соединены с первым выходом 17 управления режимом работы устройства.В зависимости от сигнала на первом входе 17 управления режимом работы устройства, каждый из коммутаторов 16 д (ш=1,М) передает на выходы 9 соответствующих блоков выТчисления 1 либо частичные суммын(М+ )либо частичные суммын (ир 11 егП 31х И которые далее суммируются суммирующим блоком с образованием либо результата ЦДС с ЯСС размером МрИ (в первом случае), либо результата ЦДС с произвольным ядром размером М хИ+1х ( - у-)35Для реализации операции свертки с ядром размером (2 М) х М, обладающим центральной симметрией, или с0+1ядром размером (2 М) х ( в ), симметричным относительно центральной строки в устройство дополнительно вводятся (М) сумматоров, причем выходы 1-го (11,М) сумматора 18 (фиг. 7) соединены с первыми входами всех умножителей брт, В=1, (И+1) /2) 1-го вычислительного конвейера 11, а первые и вторые входы 1-го сумматора 18 соединены соответственно с 1-ми 8 Е и (2 И)-ми 8 м Е информационными входами устройства.В процессе работы устройства на входы 8 Е и 8 м е (1=1,м) поступают отсчеты соответственно (-(М-й и (1+(М-й строк входного изображе 55 ния, симметричных относительно -й строки, поступающей на информационный вход 8 . На выходе сумматора 18 Е отсчетов в каждом такте работы устрой 76 6ства формируется сумма Ле,1-(м-И+у Фр(м- Е 1соответствующих отсчетов, которая поступает на первые входы умножителей 6 ее,соответствующего блока вычислений 1 Е, При этом на 1 с-м (1 с=1,(И+1)/2) умножителе 6 Е 1-го (1=1,М) блока вычислений 1 е Формируется произведениее,кр 1 =П Е З" ЕК =1-(м-Е 1,;" Е+ Д -Е 1,1"ЕР которое учитывается в соответствующих частичных суммах, что позволяет на выходе устройства получать результаты ЦДС с ядром размером (2 М) х БИ+1или (2 М) х ( ), симметричным относительно центральной, М-й, строки.С целью расширения функциональных возможностей устройства за счет выбора режима выполнения операции ЦДС либо с ядром, состоящим из М различных строк весовых коэффициентов, либо с ядром, состоящим из 2 Мстрок, симметричным относительно М-й строки, в устройство дополнительно вводятся (М) коммутаторов информационные входы 1-го (1=1,М) коммутатора 19 Е (фиг.8) соединены с (2 И)-ми информационными входами 8 е устройства, выходы 1-го коммутатора 19 Е соединены с вторыми входами 1-го сумматора 18 е отсчетов, управляющие входы всех коммутаторов 19 соединены с вторым входом 20 управления режимом работы устройства.В зависимости от сигнала на втором входе 20 управления режимом работы устройства с выходов каждого коммутатора 19 е на входы соответствующих сумматоров 18 отсчетов подаются либо отсчеты с (2 И)-х информационных входов 8 ем е устройства, либо нулевые коды. На выходах устройства формируются результаты ЦДС, в первом случае с ядром, состоящим из (2 М) строк весовых коэффициентов, а во втором случае - с ядром иэ М строк.,Формула изобретения 1. Устройство для параллельного вычисления цифровой двумерной свертки, содержащее регистры сдвига, умножители, сумматоры и регистры, о тл н ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат,30 35 7 14 оно содержит М блоков вычисления, где М - нечетное число строк ядра свертки, и суммирующий блок, информационные входы блоков вычисления являются информационными входами устройств, вход загрузки весовых коэф.фициентов М-го блока вычисления является одноименным входом устройства, вход загрузки весовых коэфьщиентов и-го блока вычислений (и 1,М) подключен к выходу весовых коэффициентов (и+1)-го блока вычисления, первые входы синхронизации блоков вычисления и вход синхронизации суммирующего блока соединены с первым входом синхронизации устройства,.вторые входы синхронизации блоков вычисления соединены с вторым входом синхронизации устройства, информационные входы суммирующего блока подключены к информационным выходам блоков вычисления, информационный выход суммирующего блока является информационным выходом устройства.2. Устройство по п. 1, о т л ич а ю щ,е е с я тем, что каждыйИ+1 . блок вычисления содержит регистров сдвига, где Ю - нечетное число0+1 столбцов. ядра свертки, 2 умнояц- телей, Бсумматоров и Н регистров, выход К-го регистра (К=1,Н) соединен с входом первого слагаемого К-го сумматора, выход М-го регистра является информационным выходом блока, выход первого умножителя соединен с информационным входом первого регистра и входом второго слагаемого (В)- го сумматора, выход д-го умножителяЯ(ь=2, 2 ) соединен с входом второго слагаемого -1 и (Н-)-го сумматоров,0+1выход ( )-го умножителя соединен с.2Нвходом второго слагаемого ( - )-го сум 2 матора,вход первого сомножителя -го0+1умножителя (1=1, 2 ) соединен с выходом 1-го регистра сдвига, входы второго сомножителя всех умножителей соединены с информационным входом блока,входы синхронизации всех умножителей и регистров соединены с первым входом синхронизации блока, входы управления сдвигом всех регистров сдвига соединены с вторым входом синхронизации блока, входы последовательной загруз" 16976 8ки данных регистров сдвига являютсявходом загрузки весовых коэффициентов блока, выходы старшего разрядавсех регистров сдвига являются выхо- Бдом весовых коэффициентов блока.3, Устройство по п. 1, о т л и -ч а ю щ е е с я тем, что суммирующий блок содержит Т узлов, где щ 0 С = Г 1 од М ,хобозначает наименьшее целое, большее или равное величине х, входы синхронизации всехсуммирующих узлов соединены с входомсинхронизации блока, информационныевходы первого суммирующего узла являются одноименными входами блока,информационные входы а-го суммирующего узла (а = 2,С) подключены к одноименным выходам (а)-го суммирующего узла, информационный выход1-го суммирующего узла является одноименным выходом блока, причем первыйсуммирующий узел содержит К=ГМ/23регистров, с,=ГМ/2 1 сумматоров, где 26 173 означает целую часть У, а В-йсуммирующий узел содержит В. =Кц, /21регистров и со, = ГК, /21 сумматоров,входы синхронизации всех регистровЬ-го суммирующего узла (Ь=1,с) соединены с входом синхронизации Ь-го суммирующего узла, выходы ш-го сумматора Ь-го суммирующего узла (ш =1,с ) соединен с входом ш-го регистра, входы сумматоров и К-го регистра (при Ко=с+1) являются информационными входами суммирующего узла, выходы регистров являются информационными выходами суммирующегоузла. 40 4. Устройство по пп. 1 и 2, о т -л и ч а ю щ е е с я тем, что, с целью обеспечения возможности вычисления цифровой двумерной свертки с произвольным ядром, имеющим (Р+1)/2 столбцов, Р - число регистров блока вычислений, в каждый из М блоков вычислений введен коммутатор, первый и второй информационные входы которого соединены с выходами Р-го и (Р+1)/2- 60 го регистров соответственно, выходкоммутатора является информационным выходом блока, управляющий вход коммутатора соединен с первым входом управления режимом работы блока, входы 66 управления режимом работы всех блоковвычислений соединены с одноименным входом устройства.5. Устройство по п, 1 и 2, о тл и ч а ю щ е е с я тем, что, с1416 целью обеспечения возможности вычисления цифровой двумерной свертки с симметричным относительно центральной строки ядром, имеющим 2 Мстрок, Б И - число блоков вычисления устройства в и-й блок вычислений (и1,И) введен дополнительный сумматор, выход которого соединен с входами второго сомножителя всех умножителей блока, а первый и второй входы дополнительного сумматора являются информационными входами блока.6. Устройство по п. 5, о т л и - ч а ю щ е е с я тем, что, с целью 976 1 Ообеспечения возможности вычисления цифровой двумерной свертки с ядром, имеющим М строк, в и-й блок вычислений введен коммутатор, выход которого соединен с вторым входом дополнительного сумматора, информационные входы коммутатора являются одноименными входами блока, управляющий вход коммутатора соединен с вторым входом управления режимом работы блока, вторые входы управления режимом работы всех блоков вычисления соединены с одноименным входом устройства,