Устройство для гистограммной обработки изображений объектов

)5 ГОСУДАРСТВЕННПО ИЗОБРЕТЕНИПРИ ГКНТ СССР КОМИТЕТ И ОТКРЫТ ОПИСАНИЕ ИЗОБРЕТЕН СВИДЕТЕЛЬСТВ К АВТОР ут им листи вскии,ММНОЙ КТОВ(71) Киевский политехнический инст50-летия Великой Октябрьской соцческой революции(56) Авторское свидетельство ССС М 1196898, кл. 0 06 Е 15/36, 1985Авторское свидетельство ССС М 1312614, кл, 6 06 Р 15/36, 1986 (54) УСТРОЙСТВО ДЛЯ ГИСТОГРА ОБРАБОТКИ ИЗОБРАЖЕНИЙ ОБ(57) Изобретение относится к вычислительной технике, в частности к устройствам цифровой обработки информации и может использоваться для ранговой фильтрации иэображений. Цель изобретения - расширение функциональных возможностей путем реализации операции медианной фильтрации. Устройство содержит ц блоков 1 памяти (ц - разрядность обрабатываемых данных), о элементов И 2, о регистров 3 данных, регистр 4 порога; регистр 5 результата, блок 6 управления, ц сумматоров 7, коммутаторов 8, компаратор 9 и ц шинных формирователей 10. Для поиска медианы используется свойство высокой однородности элементов иэображения, принадлежащих одной области. 5 ил.,1 табл.10 15 20 Изобретение относится к вычислительной технике, в частности к устройствам цифровой обработки информации и можетиспользоваться для ранговой фильтрацииизображений,Цель изобретения - расширение функциональных возможностей путем реализации операции медианной фильтрации.На фиг.1 изображена структурная схемаустройства для гистограммной обработки, изображений обьектов; на фиг.2 - структурная схема блока управления; на фиг,3 -, структурная схема шинного формирователя; на фиг.4 - гистограмма фрагмента изображения; на фиг,5 - суммы, получаемые навыходах сумматоров при медианной фильтрации изображения.Устройство для гистограммной обра, ботки изображений объектов (фиг.1) содержит о блоков 1 памяти (ц - разрядностьобрабатываемых данных), о элементов И 2,о регистров 3 данных, регистр 4 порога,регистр 5 результата, блок 6 управления, цсумматоров 7, коммутатор 8, компаратор 9,о шинных формирователей 10, информационный 11 вход, вход 12 задания порога, вход13 задания начального значения медианыустройства, вход 14 смены режима устройства, информационный 15 выход устройства, выход 16 конца поиска медианы, выход17 результата операции выравнивания гис тограмм устройства, позициями с 18 по 26обозначены соответственно с первого подевятый выходы блока управления,Блок управления (фиг,2) содержит генератор 27 тактовых импульсов, дешифратор28, регистр 29 адреса микрокоманд, комму татор 30 адреса, матрицу 31 памяти микропрограмм и регистр 32 микрокоманд,Шинный формирователь (фиг,3) содержит группу элементов И 33, элемент ИЛИ -НЕ 34 и элемент И 35,В устройстве используются алгоритмскользящего выравнивания гистограмм(СВГ) с параллельным поиском результата иалгоритм быстрого поиска медианы (БМФ),использующий в.процессе поиска предыдущее значение медианы. Алгоритмы основаны на параллельном формировании тольконечетных точных и грубых отсчетов гистограмм в о блоках 1 памяти, последуюшемпараллельном (в течение одного такта) считывании из о блоков 1 памяти значений гистограмм, используемых для вычислениярезультата, и сведение операций обращения к гистогра,"лмэм к минимуму.Устройство работает в следующих режимах; обнуление значений отсчегов гистограмм; вклк 1 чение входного отсчета вгистограмму ч:.лючение входного о 1 счета 25 30 35 40 45 50 55 из гистограммы; скользящего выравнивания гистограммы; скользящей медианнойфильтрации изображения,Перед началом работы устройства регистры 3 - 5 обнулены, во всех запоминающих ячейках блоков памяти 1) О = 1,о) записаны нулевые сигналы, а на выходах блока 6 управления сформированы следующие сигналы: выходы 18 - 1 - запись в регистр 5 результата запрещена (запись в двухтактный регистр 5 осуществляется по заднему фронту синхроимпульса) и разблокировка компаратора 9; выход 19-Ф- запись в регистр 4 порога запрещена; выход 20-Й- разрешение чтения информации из блоков 1 памяти; выход 21-ф - запрет выборки блоков 1 памяти; выход 22-Ф - информация передается с входов 13 устройства на входы регистра 5; выход 23-Ф - запись в регистры 3 данных запрещена; выход 24 - 1 - обнуление содержимого регистров 3 данных; выход 25 - 1 -блокировка шинных формирователей 10 (на их выходах сформированы нулевые сигналы); выход 26-Р - запрещение управления шинным формирователем 10.На вход 14 устройства поступает нулевой сигнал, т,е. информационный код с входов 11 устройства на входы регистра 29 адреса микрокоманд не поступает, Изменение режимов работы устройства происходит при подаче единичного импульса на вход 14 устройства по установленному коду операции нэ входах 11 устройства,В режиме обнуления значений отсчетов гистограмм на информационном входе 11 устройства формируется код "обнуления". На вход 14 поступает единичный импульс, который настраивает коммутатор 30 на передачу информации с входов 11 устройства на вход регистра 29 адреса микрокоманды, При этом на выходах блока б управления устанавливаются следующие сигналы;Выход 18 19 20 21 22 23 24 25 261 такт У Я,И,О и 3 У 1 1 и2 такт 1 8 1 1 Я Я 1 1 Я В первом такте на входы регистра 5 результата поступает адрес ячейки памяти, подлежащей обнулению (адрес поступает с входов 13 устройства) и обнуляются регистры 3 устройства,По заднему фронту сигнала, установленного на выходе 18 блока б управления, осуществляется запись адреса в регистр результата.Во втором такте происходит выборка всех блоков 1 памяти и формируется сигнал разрешения записи (с выхода 21 блока б управления). Запись осуществляется только в блоки 1 памяти на соответствующую линию адреса которых подается сигнал единичного уровня, так как в блоках 1 памяти хранятся только нечетные отсчеты гистограммы,На входах 13 устройства формируется адрес очередной ячейки блоков 1 памяти, подлежащих обнулению и указанный процесс повторяется.Режимы включения (суммирования) входного отсчета в гистограмму и исключения (вычитания) входного отсчета из гистограммы используются для рекурсивного формирования гистограммы значений входных данных, При этом на выходах блока 6 управления формируются следующие сигналы;Выход 18 19 20 21 22 23 24 25 26 1 такт р 1 ,г,., 1 1 Ф 2 такт 1 ф ф 1 ф 1 ф 1 ф Зтакт 1 ф 1 1 ф фф 1 ф При поступлении на вход 14 блока 6 управляющего импульса. в регистр 29 адреса микрокоманд по входу 11 запишется код команды "Включение входного отсчета в гистограмму", В результате блоком б управления нулевым сигналом на выходе 18 и единичным сигналом на выходе 19 обеспечивается запись в регистр 5 результата адреса ячейки блоков 1 памяти, подлежащей видоизменению и запись (н 1) в регистр 4 порога с входов 12 устройства. Затем единичным сигналом с выхода 21 блока б управления разрешается выборка, а нулевым сигналом с выхода 20 осуществляется считывание информации из всех блоков 1 памяти по заданному адресу. Так как формирователи 10 ( = 1,р) заблокированы единичным сигналом с выхода 25 блока б, то считанная из блоков 1 памяти информация инкрементируется на сумматорах 7 и записывается (по единичному сигналу на выходе 23 блока 6 управления) в регистры 3 устройства. Единичным сигналом с выхода 20 блока б управления производится запись в соответствующие ячейки блоков памяти видоизмененного отсчета гистограммы.Режим исключения (вычитания) входного отсчета из гистограммы выполняется аналогично, При этом в регистр 4 порога с входа 12 записывается ( - 1), что обеспечивает выполнение операции уменьшения заданного отсчета гистограммы на единицу,В режиме скользящего выравнивания гистограммы на выходах блока б управления формируются следующие сигналы:Выход 18 19 20 21 22 23 24 25 26 1 такт )о 1 ф О О .,О 1 1 1 2 такт 1 ф 9 1 9 1 ,6 9 1 Единичным сигналом с выхода 19 блока б управления разрешается запись величины- ), где- количество элементов во фраг менте изображения, в регистр 4 порога, откуда она поступает на первые входы всех сумматоров 7. Затем разрешается считывание (сигналами с выходов 21 (1). 20 ф)блока б управления) информации иэ блоков 1 памяти по адресу (входному отсчету), записанному в регистр 5, при этом на сумматоре 7 р суммируется только информация с тех блоков 1 памяти, соответствующий (одноименный по номеру) разряд адреса которых равен нулю. В регистр Зр записывается ранг входного отсчета, который поступает на выходы 17 устройства.Таким образом, устройство для гистограммной обработки изображений объектов вычисляет результат операции СВГ по фор- муле 5 10 15 20 где О -входной отсчет;О - результат;Н(б) - гистограмма распределения значений выходных отсчетов.При 0О1 необходимо выполнятьнормализацию результата умножения на коэффициент 1/, где- размер апертуры;30 Если= 2 (где К - целое, КО), нормализация результата проводится тривиальным перемещением запятой относительно разрядной сетки результата, ЕслиФ 2 , норкмализация выполняется программным или аппаратным способом во внешнем устройстве, управляющем работой устройства.При медианной фильтрации изображений для поиска порядковой статистики (в рассмотренном случае медианы) в гистограммных фильтрах обычно суммируют элементы гистограммы до тех пор, пока их сумма не превысит величины И, где Й - номер порядковой статистики, или не станет ей равной. Индекс последнего просум мированного элемента гистограммы равенпорядковой статистике (медиане). Поэтому в предлагаемом устройстве для определения каждого разряда медианы используются приведенные на фиг.5 суммы. При этомразряд результата равен единице (истинендля хранимых нечетных отсчетов), если полученная сумма больше или равна й и равен нулю в противоположном случае. Так как в каждом такте работы устройства вычисляется как минимум одни разряд результата, а окончание процесса поиска определяется путем сравнения результатов двух последних итераций (по равенству), то сравнивать необходимо только рстарших разрядов, причем циклы сравнения и записи в регистр1667106 10 15 20 25 а- го тр блок 11 памяти 3 Пусть в рдовательно з0110, 1001, 1на выходе сумде 17 устройдом тактсформируютс инои (- из тех б разряд овый рэ ,анавь положит,е. с величия только твующий улю, Знак исываетс оступает 5 результата разнесены во времени (по переднему и заднему фронту синхроимпульса).В режиме скользящей медианной фильтрации изображения на выходах блока 6 управления устанавливаются следующие сигналы;Выход 18 19 20 21 22 23 24 25 26 1 такт ф 1 д Ф Ф Ф 1 1 Ф 2 такт 1 фФ 1 1 1 Ф Ф ф.Зтакт ф ф ф 1 1 1 Ф Ф Ф 4 такт 1 ф Ф 1 1 1 Ф Ф Ф Единичным сигналом с выхода 19 блока 6 управления разрешается запись величины порога (для рассмотренного случая меди- анной фильтрации величина порога равна (-( +1)/2) в регистр 4 по входам 12 устройства. Считанная из блоков 1 памяти информация поступает на входы сумматоров 7 при этом с отрицательной величиной порога суммируется только информация с тех блоков 1 памяти, соответствующий (одноименный по номеру) разряд адреса которых равен нулю, Кроме того, независимо от соответствующего разряда адреса на вход в блоках 1 памяти хранится следнформация блок 12 памяти блок 1 з памятиблок 14 памяти ежиме СВГ в регистр 5 послеписываются следующие коды 10, Тогда согласно алгоритму матора 7 ц (а значит и на выхотва) последовательно, в кажработы устройства, я следующие суммы (фиг 4)-+ а+ф+ф+ Ц = 1 - 9+ 6+31 - .- 31 - +Ф+ Ь+ +ф 1 =1 - 9+ 2 4. 11 =61- .+Ф+ Ь+-)1=1-9+2+1 =7) суммируется информа локов 1 памяти, соси вет адреса которых равен зряд в регистр Зц не за ход 17 устройства всегда ельное число. сумматора 7 (1 = 1,ц) поступает информация, считанная с соответствующего блока 1 памяти. Инверсное значение знаков результатов, полученных в сумматорах 7 поступает на вторые входы коммутатора 8(значит и на входы регистра 5 результата),Кроме того, данные разряды (кроме младшего) поступают на компаратор 9, Если соответствующие разряды регистра 5 и инверсные значения знаковых разрядов сумматоров 7 совпадают, то на выходе 16 устройства формируется единичный сигнал, свидетельствующий о том, что на выходе 15 устройства установлен результат поиска. В противном случае в регистр 5 результата записывается видоизмененное, грубое значение медианы и указанный процесс поиска повторяется,П р и м е р. Рассмотрим работу устройства в режимах СВГ и БМФ. Пусть изображение обрабатывается апертурой ЗхЗ элемента( = 9), причем ц =-4. Тогда гистограмма фрагмента изображения имеет, например следующий вид: Пусть в режиме ВМФ в регистре 5 хрнится значение медианы М предыдущефрагмента изображения, Рассмотримслучая. М = 1011; й = 0110; М = 1001,Результаты вычислений приведены в табл це.Медианой для данного фрагмента изображения является число 1001, В первом случае старое и новое значение медианы 5 отличается в третьем разряде, Поэтому максимальное количество тактов работы устройства равно двум (в каждом такте определяется по одному разряду (третий и четвертый разряд) медианы), Так как в пер вом такте хранимое в регистре 5 число 1011не совпадает тремя старшими разрядами с числом 1000, выставленным на знаковых выходах сумматоров 7, то необходим еще один такт работы,5 Во втором случае старое и новое значение медианы не совпадают в первом разряде (максимальное число тактов равно 4).Однако, так как во втором такте был определен не только второй, но и третий разряд, то 0 общее количество тактов равно трем. Еслистарое и новое значение медианы совпада10 15 20 25 30 35 45 50 55 ют, то устройство в режиме поиска медианыработает один такт,Для улучшения качества медианной фильтрации в устройстве полученное значение медианы замещает центральный элемент фрагмента изображения и используется (в качестве элемента изображения выбранного фрагмента) для обработки уже следующего фрагмента изображения, Кроме того, так как устройство является асинхронным, то для уменьшения времени считывания точки изображения на его входе целесообразно поставить накапливающий буфер, в качестве которого можно использовать ассоциативное запоминающее устройство. Помимо медианной в устройстве возможны и другие виды фильтрации, например, экстремальная фильтрация, необходимая для геометрической обработки изображения(утолщение и уменьшение линий),Формула изобретения 1, Устройство для гистограммной обработки изображений обьектов, содержащее ц блоков памяти (ц - разрядность обрабатываемых данных), ц сумматоров, ц регистров данных, ц элементов И, блок управления, регистр порога и регистр результата, выход которого является информационным выходом устройства, информационный вход устройства соединен с входом начального адреса микрокоманды блока управления, вход смены режима которого является одноименным входом устройства, выходы блока управления с первого по четвертый соединены соответственно с входом разрешения записи регистра результата, с входом разрешения записи регистра порога, с первыми входами элементов И и входами 40 считывания блоков памяти, информационный выход 1-го (1,ц) блока памяти соединен с первым входом -го сумматора. информационный выход )-го сумматора Ц = =1,ц) подключен к информационному входу -го регистра данных, выход которого подключен к информационному входу)-го блока памяти, выход )-го элемента И соединен с входом записи -го блока памяти, информационный вход регистра порога является входом задания порога устройства, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет реализации операции медианной фильтрации,в него введены ц шинных формирователей, компаратор и коммутатор. причем первый информационный вход коммутатора является входом задания начального значения медианы устройства, выход коммутатора подключен к информационному входу регистра результата, второй информационный вход коммутатора соединен со знаковыми выходами ц сумматоров, знаковые выходы (ц - 1) старших сумматоров подключены к первому информационному входу компаратора, второй информационный вход которого соединен с разрядными выходами (ц - 1) старших разрядов регистра результата, адресные входы К-го (К = 2,ц) блока памяти соединены с К - 1 выходом старших разрядов регистра результата, выход)-го разряда регистра результата соединен с вторым входом )-го элемента И и с входом разрешения выборки в режиме выравнивания гистограмм )-го шинного формирователя, информационный вход которого соединен с выходом )-го блока памяти, выход регистра порога подключен к вторым информационным входам сумматоров, выход 1-го шинного формирователя подключен к (+2)-му входу сумматоров с (1+1)-го по ц-й, (ц+2)-й вход ц-го сумматора соединен с выходом ц-го шинного формирователя, первый выход блока управления соединен с управляющим входом компаратора, пятый выход-с управляющим входом коммутатора, шестой и седьмой - соответственно с входами разрешения записи и входами обнуления регистров данных, восьмой выход - с входами блокировки информации в режиме поиска медианы (ц)-го шинных формирователей, входы блокировки информации в режиме выравнивания гистограмм которых являются входами задания логической единицы устройства, девятый выход блока управления соединен с входом блокировки информации в режиме выравнивания гистограмм ц-го шинного формирователя, вход блокировки информации в режиме поиска медианы которого является входом логического нуля устроиства.2. Устройство по п.1, о т л и ч а ю щ е ес я тем, что блок управления содержит дешифратор, регистр адреса микрокоманд, коммутатор адреса, матрицу памяти микропрограмм. регистр микрокоманд и генератор тактовых импульсов, выход которого подключен к тактовому входу дешифратора, выход которого соединен с адресным входом памяти микропрограмм матрицы, выход которой подключен к информационному входу регистра микрокоманд, разрядные выходы первого информационного выхода которого являются соответственно с первого по девятый выходами блока, второй информационный выход регистра микрокоманд соединен с первым информационным входом коммутатора адреса, второй информационный вход которого является входом начального адреса микро+2+ команды блока. а управляющий вход - вхо- входом регистра адреса, выход которого дом смены режима блока, выход коммутато- подключен к информационному входу дера адреса соединен с информационным шифратора.1667106 Корре Редак Палий сина при ГКНТ СССР осуд ород, ул.Гагарина, 101 зводствен аказ 252ВНИИ оставитель Е.Хуехред М,Морген Тираж 413 Подписное гвенного комитета по изобретениям и открыти 113035, Москва, Ж, Раушская наб 4/5 ательский комбинат "Патент"