Устройство для определения текущей медианы Советский патент 1987 года по МПК G06F17/18 

1132

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

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

Па фиг.1 нредставлена функциональ- ная схема устройства; на фиг.2 - временные диаграммы его работы.

Устройство содержит элемент 1 задержки, одновибратор 2, второй счетчик 3, пятый элемент И 4, первый од- новибратор 5, первый счетчик 6, второй элемент НЕ 7, третий и четвертый счетчики 8 и 9, oTopoii и третий блоки 10 и 11 памяти, второй регистр 12, элемент 2И-ПЛИ 13, генератор 14 так- товых импульсов, триггер 15, третий элемент II 16, первый и второй сумматоры 17 и 18, дешифратор 19, группа элементов И 20, второй элемент И 21, трети11 элемент ИЛИ 22, первый блок 23 памяти, трети11 рег истр 24, первьт элемент V} 25, первый коммутатор 26, второй элемент ИЖ 27, первый и четвертый элемент И 28 и 29, первый элемент НЕ 30, второй коммутатор 31, пер вьи регистр 32, схему 33 сравнения, второй вход выбора режима 34, вход 35 Пуск, вход 36 начальной установки, nepBLiii вход 37 выбора режима, выход 38 импульсов сопровождения, выходы 39 результата и вькод 40 конца работы.

Устройство предназначено /щя на- ,ен1;я м,аксимальнь х (минимальных) чисел в массиве и ог1ред,еления мади

аны, в двумерном массива размером ткп, где m - число строк; п - число столбцов, m 2 , Р S - целые пололеительные числа. Апертура фильтра может быть произвольной. Число точек входящих i апертуру равно К (К - не- четное).

Алгоритм работы следующий.

Среди элементов массива, входящих в апертуру, находится медиана и она заменяет н,ентральную точку анертуры. Пос::е этого апертура сдвигается и новая центральная точка заменяется ме- ;uiaHo;i. Нанравлеьн е сдвига апертуры: слегка направо и сверху вниз.

В принятых обозначениях счетчик 6 являегся счетчиком с пересчетом К,

,,К+1

счетчик 3-е пересчетом , счет

42

чик 9 - двоичный счетчик разрядности S, а счетчик 8 - двоичный счетчик разрядности Р. Разрядность блоков 10 и 11 памяти определяется числом К и формой анертуры. Разрядность блока 23 памяти, схемы 23 сравнения и ре- 32 определяется разрядностью обрабатываемых данных. Разрядность регистра 12 равна разрядности счетчика 6. Количество выходов дешифратора 19, элементов И в группе элементов И 20, разрядность регистра 24 и число входов коммутатора 26 равно К.

Сигнал логической 1 на втором входе выбора режима 34 задает операцию нахождения максимального (минимального) числа в массиве, а сигнал огического О - операцию определения медианы.

Сигнал логического О на первом входе 37 выбора режима задает операцию поиска максимального числа в массине, а сигнал логической 1 - операцию поиска минимального числа в массиве. При выполнении операции определения медианы потенциал на первом входе 37 выбора режима может быть как О так и 1, но должен остаться постоянным от начала и до конца операции определения медианы.

Единичный потенциал на входе 35 Пуск разрешает устройству начать работу. Единичный импульс на входе 36 начальной установки приводит в исходное состояние регистры и счетчики устройства. Единичный имнульс на выходе 38 импульсов сопровождения указывает на то, что информация на выходах 39 результата подготовлена к

40 даче. Сигнал логической 1 на выходе 40 конца работы указывает на окончание онерации в устройстве.

Исходный массив хранится в блоке 23 памяти. Нумеруют точки, в х.одящке в апертуру, цифрами от О до К-1. Тогда в блоке 10 намяти по i-му адресу хранится смещение i-й точки анер туры но строкам, а в блоке 11 памяти - по столбцам. Смещение представляет собой число со знаком в дополнительном коде, причем,под знак отводится два разряда.

В счетчиках 8 и 9 содержится текущий адрес центральной точки апертуры (номер строки и номер столбца соответственно). Суммирование текущего адреса центральной точки со смещением в сумматорах 17 и 18 позволяет

fO

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

Устройство работает следующим образом.

Генератор 14 тактовых импульсов формирует последовательность такто- вьЕх импульсов (фиг. 2 а ). Сигнал логической 1 на входе 34 выбора режима (фиг,25 ) задает операцию поиска максимального (минимального) числа в массиве длины К. Массив крутится в блоке 23 памяти. В блоках 10 п 11 памяти хранятся смеще1П1Я элементов 20 массива относительно нулевого элемента массива (по строкам и столбцам соответственно), например, в блоке 10 памяти - все нупи, а в блоке 11

жимое регистра 32, то на выходе схемы 33 сравнения появляется сигна-П логической 1. В этом случае по переднему фронту первого импульса синхро- г низации (фиг. 2.) нулелоГ элемент

массива перепишется н регистр 32. Одновременно к содержимому счетчика 6 прибавляется +1, на выходе блока 11 памяти - положительное число 1, а на выходе блока 10 памяти и счетчиков 8 и 9 - нули. С выхода блока 23 памяти поступает на обработку порвьп элемент масива.

Таким образом обрабат1,и1аются все К )5 элементов массива (с 0-го по К-1-й).

К-1-и импульс синхронизации (фиг. 2 ж ) разрешает зан(с последнего (К-1)-го элемента массива в регистр 32 (при условии, что (К-1)-й элемент меньше содержимого регистра 32) и В1,131,1вает появление сигнала переноса на выходе переноса счетчика Ь. Одно- виб1)атор 5 преобразует этот сигнал в короткий импульс (фиг.2 1., котопамяти - последовательные числа от О рый сбрасывает через элемент 2H-1L 1H до К-1.13 и триггер 15 (фиг. 2 с ), запрещая

Сигнал логической входе 37 вы- дальнейшую вьцдачу импульсов синхро- бора режима (фиг.2ь) задает режим поис- низации (фиг.2ж). Одионременно выдана минимального числа в массиве. По ется сигнал окончания операции на вы- сигналу начальной установки (фиг.22). ход 40 конца работы (фиг.н. ), кото- на входе 36 начальной установки счетчики 3, 6, 8 и 9 и регистры 12 рг 24 сбрасываются в нуль, а все разряды регистра 32 устанавливаются в состоярый разрешает выборку речл- и/гата с регистра 32 по выходам j9 результата. Через определенное время (д ч-таточ- ное для выборки результата) гигнал с

ние 1 (максимально возможное число) 35 выхода одновибратора 3 (фи1-.2п ) чеПо сигналу Пуск (фиг.2 а ) триггер 15 по переднему фронту тактового импульса (фиг.2 q) устанавливается в l (фиг.2 е ) и разрешает выдачу импульсов синхронизации с выхода элемен-40 условий на первом и втором входах вы- та И 16 (фиг.2 л). После сигнала на- бора режима (фиг . 2S , Р) .

чальной установки (фиг.2 2) с выходов счетчиков 8 и 9 и блоков 10 и 11 памяти выдаются нули и на выходе блока 23 памяти появляется нулевой эле- 45 мент массива. Так как знаковые разряды сумматоров 17 и 18 равны нулю и с выхода коммутатора 26 также поступает нуль, то коммутатор 31 пропускает I

нулевой элемент массива на вход схемы 33 сравнения и регистра 32. Схема 33 сравнения по управляющему входу 37 настроена так, что выдает сигнал

50

логической 1 в случае, если число

При выполнении операции определения медианы на втором входе 34 выбора режима установлен сигнал логического О (фиг.2 ). На первом входе 37 выбора режима также установлен сигнал логического О (фиг.2{ ), т.е. внОор максимального числа в масгире. По сигналу начальной установки на вуоде 50 36 начальной установки (фиг. 2 -г ) сбрасываются регистры 12, 24 и 32 и счетчики 3, 6, 8 и 9. По сигналу Пуск с входа 35 Пуск (фи1.2;р по переднему фронту тактового импульса

на первых ее входах (соединены с вы- 55 (фиг.) триггер 15 устанавливается

ходами коммутатора 31) меньше, чем на вторых. Поэтому, если нулевой элемент массива меньше, чем содерfO

20 223144

жимое регистра 32, то на выходе схемы 33 сравнения появляется сигна-П логической 1. В этом случае по переднему фронту первого импульса синхро- г низации (фиг. 2.) нулелоГ элемент

массива перепишется н регистр 32. Одновременно к содержимому счетчика 6 прибавляется +1, на выходе блока 11 памяти - положительное число 1, а на выходе блока 10 памяти и счетчиков 8 и 9 - нули. С выхода блока 23 памяти поступает на обработку порвьп элемент масива.

Таким образом обрабат1,и1аются все К )5 элементов массива (с 0-го по К-1-й).

К-1-и импульс синхронизации (фиг. 2 ж ) разрешает зан(с последнего (К-1)-го элемента массива в регистр 32 (при условии, что (К-1)-й элемент меньше содержимого регистра 32) и В1,131,1вает появление сигнала переноса на выходе переноса счетчика Ь. Одно- виб1)атор 5 преобразует этот сигнал в короткий импульс (фиг.2 1., кото рый сбрасывает через элемент 2H-1L 1H 13 и триггер 15 (фиг. 2 с ), запрещая

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

рый разрешает выборку речл- и/гата с регистра 32 по выходам j9 результата. Через определенное время (д ч-таточ- ное для выборки результата) гигнал с

рез элемент 1 задержки поступает на вход элемента l-iTM 27 и произ1зодит начальную установку регистра VI (фиг.2г). После этого производятся изменения

При выполнении операции определения медианы на втором входе 34 выбора режима установлен сигнал логического О (фиг.2 ). На первом входе 37 выбора режима также установлен сигнал логического О (фиг.2{ ), т.е. внОор максимального числа в масгире. По сигналу начальной установки на вуоде 36 начальной установки (фиг. 2 -г ) сбрасываются регистры 12, 24 и 32 и счетчики 3, 6, 8 и 9. По сигналу Пуск с входа 35 Пуск (фи1.2;р по переднему фронту тактового импульса

в 1 (фиг.2е ) и разрешает прохождение импульсов синхронизации с выхода элемента И 16 (фиг.2ж). Об

работка ( : , массипл, пходп- 1ЦИХ в апертуру, пр(1исхол,ит лиалот ич- IIO описанному проп.с-сс у 1 ахож;( минимального числа. С пь Ь со п Плсясах 10 и 11 памяти хра)Я гся ;:меп;е((ия

относитсл1)11о п,ент1К1Л1,Н(111 точ1;и апор- туры, а в эегистр 32 ы )ирается текущее максимальное число. (Хллопрсмсн- ио с уаиосом г jieri CTp 32 reicviiforo максим..льл ого числа ; 12 за- носите; номер этого числа н aneivrype K-H имнул)зС с:инхрони: а1П и К . рслдшм фронтом ; 1 зре 1ае г занись и рсгис/м) 3 последнего К-1-го числа из ;iaiiFoi i аиертуры (при услонии, что оно пгглт,- и;е текущс го значения гк гис/i na 32) , а на пмходе сче тли:са Ь и(:я1 л; ( сигнач , . (1лии-тмир/ч пг) 3 (Ьормируот 1ГЗ нел о г рочлл; пгмулг,;;- (фиг, 2 С J КОТОПЫ -I P T IUMI; г ijf j)

группу :1ЛС ме1Г1-о1 И 20 уг;::ч:см. -yri;- пог о 1Г пчпч сроч f i-ro) Mr i :м ч ра 2)

1 1 (npjil уС,ЛОБПИ, i - l :: М1Ч|Т

.1ЛС ртур.1 имеет г лг рг .-.1 -ч);.-.-п г- а -;симал 1ное значение) и п тиГ м i чие г + к ci.v U- p: iii-;oMy сче мпч.а . |гул)е с H::ixi);r,a о,(Г) Ч а ; f r lfr . 2: через элемент 1 задег я:-;;, кчсг- енг lUiil 27 и лле.|ечг П 2 cOji iririi-ne ; ре- rnci p 2, iloc;ie э:ч1Г1 - ;; :; ся что I ioft чрохоа анерту;), ivarna i-;i че- мен г ( Г1аксч -.1Г1льл).111 ; тч-п/,; in ;.-г ем про- yoTTf.)i4 опре;;ечелпи чТ .ми -;; :;:и- м; лтл101 о ч1и-ла не учасчч ует, так |::ак 1 :огл,а счегчик ; 1 мес i з ачучт с i,

К(1ммутатор 26 npoiivci ae ла H -ixo, 1 и:г i-Tu р1лл-(ра рг: стра A l и через НЛП 22 i:(.pei: г ivOM мутатс р Ч ; иервые чхоли, на /чг. pi-;e подается значение с хо- да р.. :.1,лма (ijun . 2 h ) , т.е. О

При третт ем г рохсде /ini p j yi -i ис кточаются из рассмотрения л.па на.- ибочыпих по r.ej4H4iiHe числа и i . .

,

Г КИ еима л ( минима.гилюе ) число

является -чедиано. Поече зал С ршения Kf 1

no;i I ) регистр 24, сбра.оа аеч ся счетчик 3 и на tiro поилляется сигпал переноса. Одповибратор 2 iljoj r- мирует из этого счггпала ix-opciTs nn им- (фиг. 2 л ), которь й через эле- меш ИЛИ 25 сбра( регистр 2, а к coдepжи o y счетчикм 9 прибанля

f, - 20

223146

ется единида, Од11овременпо он посту- иает на пькод 38 импульсов сопровож- д, и раз)е111ает выбор;су первого ре- .ультата с нь ходов 39 результата. После зтогсз имнульс с выхода одно- иибратора 5 черс;з элемент 1 задержки, хле -;ент 11JII 27 и элемент И 29 сбрасывает регистр 32 (фи1ч2. ). На этом пП|1аГ1отка первой дешфа.чьной точки 34 г ершается, так как счетчики 8 и 9 у:.-.А с.о;|,ер;кат адрес сле/ ующей цепт- альной Т11ЛКИ, то работа устройства нрол,плж;1ете.я а налоги гным образом.

llric.iic; обраготки поепедней точки масчлгпа ,л с нихода одно1зибра- тора 3 (.2 } ) разреи. ает запись о герС Д, елининь 24, еиг

С i i4i i inae-T нч истр 2ч и ,пет сиг- л- 1ч сонр(Ч ,(1л:дении на. выход 38 имнуль- С(Л с;;иро1и л;лепия . Сиглкал с Н1)Гхода м;м1оу ч ,ч1чтора 5 че1к: з эл(мент 1 за- д,ср:1чч: i-,6ii;iC:4iaeT регист 32 (фи1 .2 г) ( ч лал переноса с ныход.а ri penoc;i счс тч1ч-;а 8 ( м) через элемепт 2;|-ИЛП 13 е ()рас1,1вает триггер 15 (фиг.2е}, прекра1;(ая 1Л1дачу имиульсон сипх1)олизадии . ). Однонремеппо этот сигнал поступает па выход чО конпа работы ( 4)пг.2ч). После этого С чп.а.е1 ся С пч1ач уск (фиг.2|г).

41 (1 14 м у .4 а изо о ;

С- Н И Я

35

0

5

5(1

55

Устройство д,ля ог1ределе11ия текущей , t; сп1,ер;ка:цее четыре счетчика, черпг . пам}гги, nepBijii i, i TpeTiiii 1)егистры, схему сравнения, Д(.ч 11( рратор, перпьи коммутатор, триггер, тчмгератор тактовых импульсов, (.-М(ЛГ;- задг-ржк, первы э.1 еме1гг НЕ, с черного по четвертый элементы И, iiyiiny э.чементов И, первый, второй п треч ий элемент ; ИЛИ, элемент Zli-lUIH ) и BTopoi оддюБИбраторы, приче x,.-;j( FfepBorci элемента ПЕ соединен с 1Ь Э 1 лм входом иыбс1ра режима ycTpoiicT- на , 11е;)гл.м входом первого элемента Г1 If Счилом разрешения сравнении схет-м с |)а. пне ЛИЯ , первая гругига входов кото- ;ич сс еЛ1 Л1:л1а с инфорг шционными входами первсччл pfinicTpa, выходы кото- }ji:)ro соединены с выходами результата ye j poi icTBa и грунпой входов схемы сравнения, выход которой соединен с первым входом второго эле- t-ieHTa И, второй вход которог о соединен е выходом третьего элемента И

ч сче гц.|м нхо,пом первого счетчика, выхоц иторого э;демс1 та И соединен с синхроихонами исрпого и второго ре- гистроп, F fiiKoiu, второго регистра соединены с пходами дешифратора, выходы которого соединены с первыми входами элементов И грунгнч, вторые входы которых соединен, с выходом первого о,днопибратора, входом элемента задержки и первым входом элемента 2И-НЛГ1, выходы элементов И группы соединены с ит{формациониыми входами третьего регистра, выходы которого соединены с информационными входами

первого коммута ора, управляюпци вход f5 верт)1й входы третьего элемента 11ГГИ

которого соединен с выходами первого счетчик- и ин()ормап,ио 1ными } ходами вто1эог о регистра, вход сброса го регистра слн ,д. с Н,1ходс1м первого элемента ИЛИ, ггервый вход которого соединен с входами сброса всех счетчиков 1 входом нача; ьной установки устройства, второй пход первого эле- ИЛИ соединен с выходом второго одповибратора , вход которого соелинен с выходом переноса втстрого ечетчи а, вход первого одновибратора соединен с в -1ходом nepei oca первого счетчика, первого элеменч З НЕ соединен с riepn,iM 1 ходом четвертог о элеме 1та И, выход элемента задержки соедине с первым входом второг о элемента ИЛИ, пторо) вход элемента 2И-ИЛИ соеди- ен с 1зторым входом выбора режима устроиства, первый вход третьего племен- которого соединены с выxoдa ш та И сое/ ;ине11 с выходом генератора четвертого счетчика, выход переноса акто1 ых имг ульсов и. входом синхро- которого соединен со счетным входом низацпи триггера, информационн,Й вход третьего счетчика, выход переноса

которого сосудинен с входом Пуск устройства, выход триггера соединен с БТор)Г1 тзходом трвтьего элемелп а И, о т л и ч а 10 L ( е е с я. тем, что, с целью рас1 ирения функциональнь х возможностей устройства за счет опреде- дпумерной медианы, в него дополнительно введены второй элеме 1т НЕ, ПЯТШ1 элемент И, второй коммутатор, два сумматора, второй и третий блоки памяти, причем второй вход элемента ИНН соединен с входом 50 со счетным входом четвертого счетчи- начальной установки устройства, выход ка и выходом импульсов сопровождения второг о элемента ИЛИ соединен с вто- устройства, выход элемента 2И-ИЛИ p,Mtf входами первого и четвертого соединен с входом сброса триггера и элементов И, выход первого элемента И выходом конца работы устройства,вход coe;aiHe i с входом установки первого 55 сброса второго регистра соединен с регистра, пыход четвертого элемента входом начальной установки устройства.

3223148

11 соединер с входом cfipoca первс го регистра, информационныг входы которого соединен, с u lxoдa и второго коммл татора, первая групг а информа- 5 ционных входов которого соединена с первым входом выбора режима устройства, вторая группа информацщчнньгк входов второго коммутатора соеди 1ена с выходами первого блока памяти, уп- fO равляющий вход второго коммутатора соединен с выходом третьего элемента ИЛИ, первый и второй входы которого соединены с выходами янаковьгх разрядов первого сумматора, третий и чет0

соединены с выходами знаковых разрядов второго сумматора, пятьй иход третртего элемента НИИ соединен с В1.ГХОДОМ первого коммутатора, входы штадших разрядов адреса первого блока памяти соединены с информадионпы- ми выходами второго сумматора, входы старших разрядов адреса первого блока памяти соединены с информационными выходами первого сумматора, первые входы первого сумматора соединены с выходаму третьего счетчика, вторые входы первого сумматора соединены с вь ходами второго блока памяти, ад- 0 ресн,е входы которого соединены с выходами первого счетчика и адресными входами третьего блока памяти, вы- которого соединены с первыми входами второго сумматора, вторые

5

которого соединен с третьим входом 40 элемента 2И-ИЛИ, четвертый вход которого соединен с выходом второго элемента НЕ и первым входом пятого элемента И, второй вход которого соединен с выходом первого одновибратора, 45 выход пятого элемента И соединен со счетным входом второго счетчика, вход второго элемента НЕ соединен с вторым входом выбора режима устройства, выход второго одновибратора соеди 1ен

-S -4оЧоН- - Чо-fJ ЧоЧо-Но

5JXi, «vjn5)CX)j-

Редактор Н.Рогулич

Составитель И.Дубинина Техред Л. Олейник

Заказ 2867/47Тираж 672Подписное

,.ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

CvJ со

Корректор С .Шекмар

Изобретение относится к вычислительной технике и предназначено для обработки изображений, представленных двумерными массивами. Целб изобретения - расширение функциональньсх возможностей за счет определения двумерной медианы. Цель достигается введением злементов И, НЕ, коммутатора, сумматоров и блоков памяти. 2 ил.