Устройство для определения текущей медианы
Изобретение относится к вычислительной технике и предназначено для обработки изображений, представленных двумерными массивами. Целб изобретения - расширение функциональньсх возможностей за счет определения двумерной медианы. Цель достигается введением злементов И, НЕ, коммутатора, сумматоров и блоков памяти. 2 ил.
СОЮЗ СОВЕТСКИХ
С014ИАЛИСТИЧЕСКИХ
РЕСПУБЛИН (19) (И) SI) 4 G 06 F 15/36
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А BTOPCKOMY СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3863914/24-24 (22) 25.02.85 (46) 07.07.87. Бюл. N- 25 (71) Львовский политехнический институт им. Ленинского комсомола (72) А.В.Василькевич, В.M.Крищишин и Н.В.Черкасский (53) 681.333 (088.8) (56) Авторское свидетельство СССР
Р 771665, кп - 06 F 7/04, 1978.
Авторское свидетельство СССР
1 - 1259288, кл. G 06 F 15/36, 1985. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ТЕКУЩЕЙ МЕДИАНЫ (57) Изобретение относится к вычислительной технике и предназначено для обработки изображений, представленных двумерными массивами. Цель изобретения — расширение функциональных возможностей за счет определения двумерной медианы. Цель достигается введением элементов И, НЕ, коммутатора, сумматоров и блоков памяти. 2 ил.
1322314
Изобретение относится к вы пзслитель«ой технике и t toit eт быть 11спользовано в системе цифровой обработки сигналов, в частности при обработке изображений, представ IPI1«f: двумерными массивами.
Цель изобретения — расширение функциональных возможностей устройства за с 1ет определения д1зумерной медиагн1
tIa фиг.1 представлена функцпональ- 10 ная схема устройст«а; на фиг.2 — временные диаграммы его работы.
Устройство содержит элемент 1 задержки, одновибратор 2, второй счетчик 3, пятый элемент И 4, первый одновибратор 5, первый счетчик 6, второй элемент НЕ 7, трет11й и четвертый счет п1ки 8 и 9, второй и третий блоки 10 и 11 памяти, «торой регистр 12, элемент 2И-ИЛИ 13, ге«ератор 14 так- 20 товых импульсов, триггер 15, третий
»et teti f 11 16, пер«ый и второй сумматоры 17 и 18, дешифратор 19, группа эсзементов И 20, второй элемент И 21, третий элемент И11И 22, перззый блок
23 памяти, третий регистр 24, первый элем нт ИЛИ 25, первый коммутаfop 26, «торой элемент ИЛИ 27, первый и четвсртый элемент И 28 и ?9, первый элемепп НЕ 30, «торой t;ot t tyf atop 31, пер-З0 вый регистр 32, схему 33 срав«ения, «торой вхсд вь1бора режима 34, вход 35
"Пуct; вход 36 начал «ной уста«o«ttt »
pep«t ttt вход 37 выбтора режима, выход
38 импульсов сопро«ожде11пя, выходы 39 35 результата и вьгсс;1 40 конца работы. устройст«О пред«аз«а»сlio для наХО:1:ТТО111 Л Макс11м11111 111 !", (11111 .1!маз(Ь«ЬТх)
Тисел в массиве и uitpe!1oлсгн1я мдпавы, « двумерном массив размером шхп, где m — ч:ic:То строк; п — число столбцов, m — — ?, n"; Р S — целые положительные числа. Лг1ертура фильтра мо;11с.т бьп ь произвольной. Itic lo точек, входящих «;зпертуру равно К (К вЂ” tieчетное).
Ллгоритм работы следующий.
Среди элементов массива, входящих
« ;«1«ртуру, находится медиана и она зс1меняет пентральную точку апсргуры.
Ifoc::е этсзгп апертура сдвигается и новая центральная точка заменяется ме.;tt1t11o?t. Направление сдвига апертуры:
cnotn1 « lltp1«o и сверху вниз.
В 11рп«ятьТх обозначениях счет шк 6 является с Тетчпком с пересчетом К, К+1 счегч»к 3 — с пересчетом --- счет2 чик 9 — двоичный счетчик разрядности
S, а счетчик 8 — двоичный счетчик разрядности P. Разрядность блоков 10 и 11 памяти определяется числом К и формой апертуры. Разрядность блока
23 памяти, схемы 23 сравнения и регистра 32 определяется разрядностью обрабатываемых данных. Разрядность регистра 12 равна разрядности счетчика б. Количество выходов дешифратора 19, элементов И в группе элемен. тов И 20, разрядность регистра 24 и число входов коммутатора 26 равно К.
Сигнал логической "1" на втором входе выбора режима 34 задает операцию нахождения максимального (минимального) числа в массиве, а сигнал логического 0 — операцию определе«ия медианы.
Сигнал логического 0 на первом входе 37 выбора режима задает операцп1о поиска максимального числа в массиве, а сигнал логической "1" " операцию поиска минимального числа в массиве. При выполнении операции определе«ия медианы потенциал на первом входе 37 выбора режима может быть как
"0" так и "1", но должен остаться постоя«ным от начала и до конца операции определения медианы.
Единичный потенциал на входе 35
"Пуск" разрешает устройству начать работу. Единичный импульс на входе 36 начальной установки приводит в ucxogttoe состояние регистры и счетчики устройства. Единичный импульс на выходе 38 импульсо« сопровождения указь1«ает на то, что информация на выходах 39 результата подготовлена к выдаче. Сигнал логической "1" на выходе 40 конца работы указывает на окон«а««е операции в устройстве.
Исходный массив хранится в блоке
23 памяти. Нумеруют точки, входящие в апертуру, цифрами от 0 до К-1. Тогда в блоке 10 памяти по i-му адресу хранится смещение i-й точки апертуры по строкам, а в блоке 11 памяти — по столбцам. Смещение представляет собои число со знаком в дополнительном коде, причем под знак отводится два разряда.
В счетчиках 8 и 9 содержится текущий адрес центральной точки апертуры (номер строки и номер столбца соответственно). Суммирование текущего адреса центральной точки со смещением в сумматорах 17 и 18 позволяе1
1322314 4 жимое регистра 32, то нл выходе схемы 33 сравнения появляется сигнл» логической "1". В этом с»у«ае по переднему фронту первого импульса синхронизации (фиг. 2 к) нулевой элемент массива перепишется и регистр 32.
Одновременно к содержимому счетчикл
6 прибавляется +1, Ita Itt txoде f)локл 11
«лмяти — положительнс е чиг:lo 1, л нз выходе блока 10 памяти и гчетчиков 8 и 9 — нули. С выхода f)Jtîl»ÿ 23 памяти поступает на обработку «< p III tt лена выходе знаковых разрядов сумматора 17 и 18 свидетельствует о пере— полнении или отрицательном результлте, т.е. выходе части апертуры за размеры исходного массива.
Устройство работает cJ»e»,yt»It(Its Генератор 14 тактовых импульсов формирует последовательность тлктовых импульсов (фиг. 2 a ) . Сигнал логическои "1" на входе 34 ныбарл ре- 15 жима (фиг. 2 <) ) задает операцию по«гкл максимального (минималь«ог<)) числа в массиве длины К. Масс»»в хрлнитгя в блоке 23 памяти. В блоках 10 « 11 памяти хранятся смещения э.»ем««тон 20 массива относительно нулевого )ломе»та массива (по гтроклм и столбцам соответственно), например, в блоке 10 памяти — все ну»и, л в блоке 11 памяти — последовательные числа от 0 до К-1. Сигнал логической "1" на входе 37 вы— бора режима (фиг. 2 ) ) задает режим поис— ка минимального числа в массиве. По сигналу начальной установки (фиг. 22). 30 на входе 36 начальной установки счетчики 3, 6, 8 и 9 и регистры 12 и 24 сбрасываются в нуль, а все разряды регистра 32 устанавливаются в состояние 1 (максимально возможное число) 35 По сигналу "Пуск" (фиг.2 1 ) триггер 15 по переднему фронту тактового импульса (фиг.2 a ) устанавливается в "1" (фиг.2 & ) и разрешает выдачу ил»пульсов синхронизации с выхода элемен-40 та И 16 (фиг.2 )<с). После сигнала начальной установки (фиг.2 ) с выходов счетчиков 8 и 9 и блоков 10 и 11 памяти выдаются нули и на выходе блока 23 памяти появляется нулевой эле- 45 мент массива. Так как знаковые разряды сумматоров 17 и 18 равны нулю и с выхода коммутатора 26 также поступает нуль, то коммутатор 31 пропускает I нулевой элемент массива на вход схе- 5О мы 33 сравнения и регистра 32. Схема 33 сравнения по управляющему входу 37 настроена так, что выдает сигнал логической "1" в случае, если число на первых ее входах (соединень(с выходами коммутатора 31) меньше, чем на вторых. Поэтому, если нулевой элемент массива меньше, чем содерполучать лбг о.tt<) t ttt лдрег л точек, входящие в л«ертуру, для рлз гичных значений адреса центральной точки. При этом наличие хотя бы одной "1" мент масива. Таким образом сбраблть«лются все К элементов массива (с 0 — го «и К-1-й). К-1-й импульс синхр<)н«злции (ф«г.2 ж ) разрешает злно« последнего (К вЂ” 1) -ro элемента мл<.гt»R;l в регис тр 32 (при условии, что (К вЂ” 1) — и )лемент t»«It»»Ite содержимого рег«гтрл 32) и вызывает появление гигH,III» переноса на выходе переноса счстчикл 6. Одновибрлтор 5 преобрлзуст т )т сигнал н к<)роткеlй им«у.l ьс (фи t . 1, ) кото рый сбрасывает через .))I< м«нт 2И-1ПИ 13 и триггер 15 (фиг.- c ), зл«рещля даЛЬНЕйШуЮ ВЫдаЧу It t ttt i »ЬС с В «t»t VpO< низации (фиг. 2 )t< ) . ();t tt<)tip< w< IIII<) выдается сигнал окон» tt»tt»t <»1< );ltttttt и;1 вых<)д 40 конца рлботы (ф«».. " ), который разрешает выборку ре и "tt, I лтл с регистра 32 по выходлм 19 ре »ультлтл. Через определенное время (;»< < тлтс)»в ное для выборки ре.);JII,Tëòë) ««гнлл с выхода одновибрлторл ) ( После этого производят«)» )»зме пения условий на первом и втором входах Rt t бора режима (фиг.2Б,1) . При выполнении опера»сии с «роде:»<в ния медианы на втором входе 3 выбора режима установлен сигнал «< г«ческого "0" (фиг. 2 Б ) . На первом вхо;»е 37 выбора режима также ус.тлнгвлен гигнлл логического "О" (фиг.2 f ), т.е. I»ttf)op максимального числа в «Ia«ctlti< . По сигналу начальной устлновк« ltл входе 36 начальной установки (ф»»1 .2 ) сбрасываются регистры 12, 2- ) « 32 и счетчики 3, 6, 8 и 9. (1о сигн".лу "Пуск" с входа 35 "Пуск" (фи).2 1) по переднему фронту тактового IIM«ульса (фиг. 2 <» ) триггер 15 уста«»всп»вс»ется в "1" (фиг.2 e > и разреклет про- хождение импульсов синхро«1».. лции с выхода элемента И 16 (фи»-. ж ) . Об1322314 (. i!. Пас )С 3 1(«(зр<яеlн15! i! il»PТ? Рl,i («; 1.".t.t ..I и 3 < l >-t O ",," Л, I (,: i t 1 l l ;+ I — i <> II,) O .)!((l ) (i < П,. . !flip;i " Oprt > <),Op !(IPУ<- l C!I tipO I Ii If t ! ((г<л(з(<()п(«л!, с i, ) >< t t> å цгэ 2!< с()рл < )«; »т(( ()ГO IзыхОдС !1(I13 0 t1 l; O t«(! 6i () i) 1 o i ) 2 < I) () p— еffr-It;t)IB кар > г«,п(I!M 5-) : I >. < ) У: (1> (, P;! «P (! « < Il С чет f!fi(3 fl (3 I C i i П:3!! П< ii(3 ftti(.;3 .Ир у«т 1! о э T ) г О l l V J <1 ((«»и г . 2> <> ) :«с н-. И.((И 2 t гбр кантор((((t МИНИ!(а<ЕЕ ПОГ(t i(f0 10 и 11 плмятп хрл и(я r(.5!: меI относите)п(,ио I(c FIT!);IJIF,и("(т 1)(ее максtf,"(сзт(ьиое . ()<(попре !евно с зл((осо!«рег!<Стр 3? тс 1, f!!oг() Г,l а К (I l . .1 - t I I t t t I 0 Ч И < t f, <: :tP «< (С ) ) носитс)< ном»р )т(1! <3 <и(с Гп> и л (еp гV >о, 1 Й (fi 111 Ë I>C (Г пнхр> >If
<1>рон1 о. рл:зре«((1(зг(з11!!i(!. и и(гl:< I (> 32 нос)пеппего Е-1-гr) числа <; «;<;t TII ой Л ПЕР УPI! (IIPi 3 УС JI O!31!II 11 r) > Н < > О(i IT— )((и т< 1 yt((t ГО .«I)ачс нич 1 егп(1,>;i 3 ? (> П Л Ез! .1 Х 0 Et C . С Ч (I" (П К и ) 1 < (",. (I I it Г < :! (пг! Iл< t 1(t р >))op?iIIpvt .г и 3 и(I > <,. Г >тt!(, t i« :i <(< (:!н:< .,1 ) кот»; ыгf p.< Г «t«» «» < npv)пу !; .«<; и f(>(I «<-ГО < " (1>И) ГЕР(3 (i — I <) It t< (I j (i1O<3ilfT (à — f tt ? > M )КСИ I:3 (l,и()Е -«И;3 (С II .<() < I; t; +1 1. » д )()жп (ому (че! fi f л >. I(.-И .!ЬС С 1„.1 ..; );(,;) О,(И,>!«ti(<Р Гl, I il .," IIII; t 2 7 ..f ).и .(с) и И . - .;»; )(н ; . Iie— г icтo .. .. Ilni.(< >:; ),:::!: « я . « г<1 — -". Г 1) !IPО 0
M;>It < (Г<н;с )I.l;It! It > ?IЛЗ1(,llO) <) П(.<Л It< У « " (УГ Т, Т<)<Г (; ()) С (()К (; Г! С Г .3(и (С <: (, 35 ь < .г)улит )и 2 .> < !otl,:„!» г !(i()3<)хо,:, 1 1-! .. (Г<((и< л; . ..":Гл tIt р(3 > ),"«3! II ! ."> i (р lit!: l (г мУт(l T< P (1 ..;. 11(Р(«I c !«хо I PI <Е ПО<(()ЕТ, « <) <3)>< > (>(>,i 1!! )<, )(( П<) lf Т() >! < 1>(I I I)) око(i(:!i t> р Т ".)>!) f ((!— )сЕпзчл)<зтс(л и 3 рл с <отре )ия дил ил— )(<1(l (Et!i
Г !;) <Г « М Л ((. t (; If!!! f I (;I. (Ь < l t ) ! (Гя с тся единн((а. Одновременно он посту1! < (3 т и а 13 ь<х 0! 1, 3 8 и Г (Г1 у. I > с О 13 с О и р О 13 Ож ! o!t»5I )r рлзреп)а т выбор:cy первого ре.",II т<1Ti< с !«ь.хо;(ОB 39 резупьтлтл. .! с.(< )того и Iffyïüñ с выхода одно1:()6рлторл 3 (ер(зз );Ic!мент 1 з() церж)сп, <(с <:Сит Il)lll 27 и э-(СГ«елr I! 29 сбра»<пз<1(т р(г(tcTр 32 (
>Гр;)6< т „) I)c>ð!3< и центра.(ьпoй точки , )»(р)<(л<3 I(и< ллк клк счет<Гики Я и 9 t .IFI С брл 30tf, II< >(и(ОГрл< отки Ifoc ((<дней точки ! J ер», 3 <1<;)»ò ))(>I ТР .". t (! П)(.,:.(T CIIÃt t>1I pi t) < КД(пил и 3 !«I 1 t()> I 3 С> I! t!IT>JJI!!— (i !«<)ПР(>П< ж,)C>(пl)l . (, 11(Ill!T С Пl <::n(Tа . t н i! <, t р;) т О f ) <1 3 tl (р е 3 i <1(х! с и т 1:3 и ,«Г.l:I!»6р,j: <гл»т p(. I п(зтр 32 (<1)ftl . 2 ) (;<. tf;i l пс Г(и< (:<. с ных< д;) II(и(II(i(л т I) кл (> (<1>пг, 2 л< ) ((р» з 3.< .()мент "(I — . II 13»(р()(ы:з<3(т тригt »ð )э («:1 f1 . ("- ) II)>i 1" (Till!(;Iß ПF 1)(Л IV ИГ(!1УЧ I!(OE! ()tfIxpn»Tf i,Ii(;It((tI иг. 2 >It ) . Однонр(менпо < trr trB:t ii<.!t.. г; и;!с T r!B )3(t> п;< 30 p;l6t ты (;1>)IT .. . t ) . посл()тor п (. < и!»и е (<-5(с и(и;>-(" (;-< ° к," (t! > с < (t (tl >< ° т <><) < f15< с)пр с> (с 3!с 1<и5> (Ку)((е(1 .i (I ; ны, ». и(р.!;i):)(ее четырс. Счетчика, . I > Р Н):< I <>. I< К I IË М)>ТИ, П Р)113 ЫЙ, )3Т< >РОI< ) Т)>(Т(! Ii )С.: 11> ТРЬI, ((:C(>IМ; CP 11< it(3(Н(Я,,< .11<и< РГ Т(Р, (IC,>!ЗЫЙ i(ÎMMÓTËТОР ТРИГТ (".!(- Р;) т()P тактов(>)х III IIIVJtf>co!3, .<1< )(и - 3:1 < ржки, пер(зый э<(c".!»(t t (!Г, и(, ) i to: t) !10 IL Tíåðò1>III э I< м .н I t>t И ) руину эс)емеи.(oB И, пеpBII((второй : Г(ий ).) - Г(еиты И.(И, элемент 2И-И (И 1<с и > <й и (31орой о;<новибраторы, пр (чем l/o()13о! Р )11(;<С>)I ra 11! - Сnc,(lr(tc!1 С ):,!tl I »,>л ин< ) . я, пс риля группа ВхоНоВ кото. <>i I Г,. <5((f! I (< lf;3 е -(l ч 1>о)змлЦИОBFI(>IMII 13 ХО i) ; I 132231и 8 Г J I «J .c P (В х о (1 л «11 1 t c P и о 0 1 1 (3 T (? P о О 13 ( г (cTpotf, J3«J::«JI»: «3торого регистра соединены ((«хадлми цепн(фрлтс рл, Выходы к(эторого (.Оед!(ис II! I с первыми г«х(дами элементов И групш 1, вторые входы котор! (х coc.;(tftfetff t с Выходом г(ервого одис Ви6раторл, входом элемента зл;(ер «(ки и пергэым нхоцом элемс итл 2И-1131И, вь!хог(ы э:(ементов И t pyt(tibt соединены с информационными входами 10 CJc> p 1301 o «(«Ii>fx>тат op<3 > у прлвляюши Й ВХОД которого coot(If Jtc с Выходлми пер(!ого СЧс ТЧик II If f1(JJOI>bt>l(ttf(3«(«th! <(It «3ХОДлми «3торого регистра, !!ход С6ро(;l трст! его р(г««стрл со«динеtl с ш «ходом перIэ О ГО э! (Сме итл И. 1И > II(> 0Âb!É 13 ход От О рого oо JIJIII(и с и о;!лми с6роса 13c c х c«eT(»(J(ov и нхо;сом нлчальиой у(тлно(3ки устр(«(!ст««л, Второй вход иергог о эиемеитл 11(111 соединен с Выходом второго одиовибрлт орл, вход которого с ое;«пи е и с В Ixoдоь(пеðåноса (зторого счетчика, (3êoJ(пер«эого од«(о(эибратора соед!(неи 13ЫХ О;1 Э !!(3 МОНТ<э З ЛДС> Pit(K«f С О(Jilt «(C И С ие1««3!.(м входом нторогo элемента ИЛИ, г«торой вход элемеитл 2И-ИЛИ сое,!и— иеи с н Ор«,(м !3хо«(ом «ыборл режима устройст«3(1, первый Вход грет(-его 3 !elte(tтл И соед;(иеи с Выходом генератора т((ктО131(х и. (ну!ге>СОВ и ВхОДОм сиих1эо низлции тригг(рл, информационный вход 31,1! которого с ое!(пиен с входом Пуск устрой(тнл, ньгход триггера соединен с Ctторы 1 Входом третьего элемеитл И, о T;I и и л и (((е е с я. тем, чго, с целью рлснн(реиия функциональных возможностей устройства за счет оиреде45 «пения,;(Вуги риой медианы, в него (Jc3tJ(3:(HJJToJtbIIo нведень« второй элемент НЕ, пятый элемент И, второй коммутаг«р, два сумматора, второй и третий 6локи памяти, причем второй вход второго элемента ИЛИ соединен с входом илчлльиой установки устройства, выход второго .элемента ИЛИ соединен с вторыми входами первого и четвертого oJtefte«fTo«3 И, выход первого элемента И соедиис и с вхоцом установки первого р(-гистра, Выход четвертого элемента 55 С О М 11 Е Р «3 О! O С Ч C Т Ч И К а Р!«Х IJI, В Го(э(ЗГ«О.Je»«(IT(И Сон;3«fft(«J С третьего регистрл, выходы которого соединены с ии(Ьор(!лц«(о«!«!ыми входами с Выходом переноса первого счет п(ка, «3ыхо;! пе р «3с«гn эл (.".-(е нта HE с оедине и с первым Входом четвертого элемеитл И, И соединен г вх(эл(эм с6р(сл перв(го регистра, It«!pop!t(It(!to«J«tf,!((Вход«(котоРОГО СОЕДИИЕ«(Ы С ВЫХ(мд(1 !1(ВТОРОГО коммутатора, первая групил ииформлционньгх входон которого соединена с первым 13«coIl,oì ВыГорл р(.ж«1((а устройства, Вторая группа ииформлцио«!«и,!х нх«дон второго коммутлтора сосдииеил с выходами первого 6:I«vs плмят«(, уtl рлнляюц«гй вход второго коммутатора соединен с выходом третьего элемситл ИЛИ, первый и второй входы которого соединены с выходам« знаковых разрядов первого суммлгорл, третий и четВертый входы третьегс элемеитл ИЛИ соединены с выходами зилкоиых разрядон второго суммлтора, пятьп1 Вход третьего элементл ИЛИ соединен с ньгходом первого коммутатора, входы младших разрядов адреса первого блока памяти соединень! с информационнь(м31 выходами второго сумматора, входы старших разрядов адреса первого 6лок(3 памяти соединены с информационными выходами первого сумматора, первые входы первого сумматора соединены с выходами третьего счетчика, вторые входь« первого сумматора соединены с выходами второго блока памяти, адресные входы которого соединены с Выходами первого счетчика и адресными Входами третьего блока памяти, выхсцы когорого соединеиь(с первыми входами второго сумматора, вторые 35 Входы к(эторого соединены с выходами четвертого счетчика, выход переноса которого соединен со счетным входом третьего счетчика, выход переноса которого соединен с третьим входом элемента 2И вЂ И, четверть!й вход которого соединен с выходом второго элемента HE и первым входом пятого эле— мента И, второй вход которого соединен с выходом перного однонибратора, выход пятого элемента И соединен со счетным входом второго счетчика, вход второго элемента НЕ соединен с вторым входом выбора режима устройства, выход второго одновибрлтора соединен со счетным входом четвертого счетчика и ныходом импульсов сопровождения устройства, выход элемента 2И-ИЛИ соединен с входом сброса триггера и вьгходом конца работы устройства,вход сброса второго регистра соединен с входом начальной установки устройства 1322314 1322314 Составитель И.Дубинина Техред Л.Олейник Корректор С.Шекмар Редактор Н. Рогулич Заыаз 2867/47 Тираж 672 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4