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

 

Изобретение относится к вычислительной технике, в частности к устройствам цифровой обработки информации, и может использоваться для ранговой фильтрации изображений. Цель изобретения - расширение функциональных возможностей путем реализации операции медианной фильтрации. Устройство содержит Q блоков 1 памяти (Q - разрядность обрабатываемых данных), Q элементов И2, Q регистров 3 данных, регистр 4 порога, регистр 5 результата, блок 6 управления, Q сумматоров 7, коммутаторов 8, компаратор 9 и Q шинных формирователей 10. Для поиска медианы используется свойство высокой однородности элементов изображения, принадлежащих одной области. 5 ил.

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

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

РЕСПУБЛИК (si)s 6 06 F 15/36

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

ПО ИЗОбРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

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

15 (21) 4682472/24 (22) 24.04.89 (46) 30.07.91. Бюл. ¹ 28 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) B.È,Êîðíåé÷óê, А.П.Марковский, В.В.Сидоров и Ю, В.Яблуновский (53) 681.3 (088,8) (56) Авторское свидетельство СССР № 1196898, кл. G 06 F 15/36, 1985.

Авторское свидетельство СССР № 1312614, кл, G 06 F 15/36, 1986, (54) УСТРОЙСТВО ДЛЯ ГИСТОГРАММНОЙ

ОБРАБОТКИ ИЗОБРАЖЕНИЙ ОБЪЕКТОВ

ЫЛ 1667106 А1 (57) Изобретение относится к вычислительной технике, в частности к устройствам цифровой обработки информации и может использоваться для ранговой фильтрации иэображений. Цель изобретения — расширение функциональных возможностей путем реализации операции медианной фильтрации. Устройство содержит q блоков 1 памяти (ц — разрядность обрабатываемых данных), о элементов И 2, q регистров 3 данных, регистр 4 порога; регистр 5 результата, блок 6 управления, q сумматоров 7, коммутаторов

8, компаратор 9 и q шинных формирователей 10. Для поиска медианы используется свойство высокой однородности элементов иэображения, принадлежащих одной области. 5 ил.,1 табл.

1667106

15

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

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

На фиг.1 изображена структурная схема

1 устройства для гистограммной обработки, изображений обьектов; на фиг.2 — структурная схема блока управления; на фиг,3—, структурная схема шинного формирователя; на фиг.4 — гистограмма фрагмента изображения; на фиг,5 — суммы, получаемые на выходах сумматоров при медианной фильтрации изображения.

Устройство для гистограммной обра, ботки изображений объектов (фиг.1) содержит о блоков 1 памяти (ц — разрядность обрабатываемых данных), q элементов И 2, q регистров 3 данных, регистр 4 порога, регистр 5 результата, блок 6 управления, q сумматоров 7, коммутатор 8, компаратор 9, q шинных формирователей 10, информационный 11 вход, вход 12 задания порога, вход

13 задания начального значения медианы устройства, вход 14 смены режима устройства, информационный 15 выход устройства, выход 16 конца поиска медианы, выход

17 результата операции выравнивания гис тограмм устройства, позициями с 18 по 26 обозначены соответственно с первого по девятый выходы блока управления, Блок управления (фиг,2) содержит генератор 27 тактовых импульсов, дешифратор

28, регистр 29 адреса микрокоманд, комму татор 30 адреса, матрицу 31 памяти микропрограмм и регистр 32 микрокоманд, Шинный формирователь (фиг.3) содержит группу элементе" ", 33, ",à"."ì.eíò ИЛИ—

НЕ 34 и элемент И 35, В устройстве используются алгоритм скользящего выравнивания гистограмм (СВГ) с параллельным поиском результата и алгоритм быстрого поиска медианы (БМФ), использующий в.процессе поиска предыдущее значение медианы. Алгоритмы основаны на параллельном формировании только нечетных точных и грубых отсчетов гистограмм в q блоках 1 памяти, последуюшем параллельном (в течение одного такта) считывании из о блоков 1 памяти значений гистограмм, используемых для вычисления результата, и сведение операций обращения к гистогра,"лмам к минимуму.

Устройств .> работает в следующих режимах; обнуление значений отсчеloB гистограмм; вклк1-1е» ие входного Отсчета в гистограмму: i : .лючение входного огас. ета

55 из гистогpGMMbl; скользящего выравнивания гистограммы; скользящей медианной фильтрации изображения, Перед началом работы устройства регистры 3 — 5 обнулены, во всех запоминающих ячейках блоков памяти 1 j 0 = 1,q) записаны нулевые сигналы, а на выходах блока 6 jjfl равления сформированы следующие сигналы: выходы 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 адреса микрокоманды, При этом на выходах блока 6 управления устанавливаются следующие сигналы:

Выход 18 19 20 21 22 23 24 25 26

1 такт Р P И,о О Я 1 1 8

2 такт 1 8 1 1 Я Я 1 1 Я

В первом такте на входы регистра 5 результата поступает адрес ячейки памяти, подлежащей обнулению (адрес поступает с входов 13 устройства) и обнуляются регистры 3 устройства, По заднему фронту сигнала, установленного на выходе 18 блока 6 управления, осуществляется запись адреса в регистр результатаа.

Во втором такте происходит выборка всех блоков 1 памяти и формируется сигнал разрешения записи (с выхода 21 блока 6 управления). Запись осуществляется только в блоки 1 памяти на соответствующую линию адреса которых подается сигнал еди1667106 ничного уровня, так как в блоках 1 памяти хранятся только нечетные отсчеты гистограммы, На входах 13 устройства формируется адрес очередной ячейки блоков 1 памяти, подлежащих обнулению и указанный процесс повторяется.

Режимы включения (суммирования) входного отсчета в гистограмму и исключения (вычитания) входного отсчета из гистограммы используются для рекурсивного формирования гистограммы значений входных данных. При этом на выходах блока 6 управления формируются следующие сигналы;

Выход 18 19 20 21 22 23 24 25 26

1 такт р 1 /,,/ 1 1 Ф

2 такт 1 P P 1 ф 1 ф 1 ф

Зтакт 1 ф 1 1 ф ф ф 1 ф

При поступлении на вход 14 блока 6 управляющего импульса. в регистр 29 адреса микрокоманд по входу 11 запишется код команды "Включение входного отсчета в гистограмму". В результате блоком б управления нулевым сигналом на выходе 18 и единичным сигналом на выходе 19 обеспечивается запись в регистр 5 результата адреса ячейки блоков 1 памяти, подлежащей видоизменению и запись (») в регистр 4 порога с входов 12 устройства. Затем единичным сигналом с выхода 21 блока б управления разрешается выборка, а нулевым сигналом с выхода 20 осуществляется считывание информации из всех блоков 1 памяти по заданному адресу. Так как формирователи 10! (i = 1.q-1) заблокированы единичным сигналом с выхода 25 блока б, то считанная из блоков 1 памяти информация инкрементируется на сумматорах 7 и записывается (по единичному сигналу на выходе 23 блока б управления) в регистры 3 устройства. Единичным сигналом с выхода

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

Режим исключения (вычитания) входного отсчета из гистограммы выполняется аналогично, При этом в регистр 4 порога с входа

12 записывается (— 1), что обеспечивает выполнение операции уменьшения заданного отсчета гистограммы на единицу.

В режиме скользящего выравнивания гистограммы на выходах блока 6 управления формируются следующие сигналы:

Выход 18 19 20 21 22 23 24 25 26

1такт ) 1 Р И О .Я 1 1 1

2 такт 1 P g 1 Р 1 ф 9 1

Единичным сигналом с выхода 19 блока

6 управления разрешается запись величины

{ — L), где L — количество элементов во фрагменте изображения, в регистр 4 порога, откуда она поступает на первые входы всех сумматоров 7. Затем разрешается считывание (сигналами с выходов 21 (1). 20(ф)блока

6 управления) информации иэ блоков 1 памяти по адресу (входному отсчету), записанному в регистр 5, при этом на сумматоре 7р суммируется только информация с тех блоков 1 памяти, соответствующий (одноименный по номеру) разряд адреса которых равен нулю. В регистр Зр записывается ранг входного отсчета, который поступает на выходы 17 устройства.

Таким образом, устройство для гистограммной обработки изображений объектов вычисляет результат операции СВГ по формуле

20 где D — входной отсчет;

D — результат;

H(d) — гистограмма распределения значений выходных отсчетов.

При 0 < D < 1 необходимо выполнять нормализацию результата умножения на коэффициент 1/L, где L — размер апертуры;

30 Если L = 2 (где К вЂ” целое, К > О), нормализация результата проводится тривиальным перемещением запятой относительно разрядной сетки результата. Если L A 2, норк мализация выполняется программным или аппаратным способом во внешнем устройстве, управляющем работой устройства.

При медианной фильтрации изображений для поиска порядковой статистики (в рассмотренном случае медианы) в гистограммных фильтрах обычно суммируют элементы гистограммы до тех пор, пока их сумма не превысит величины N, где N— номер порядковой статистики, или не станет ей равной. Индекс последнего просум45 мированного элемента гистограммы равен порядковой статистике (медиане). Поэтому в предлагаемом устройстве для определения каждого разряда медианы используются приведенные на фиг.5 суммы. При этом разряд результата равен единице (истинен для хранимых нечетных отсчетов), если полученная сумма больше или равна N и равен нулю в противоположном случае. Так как в каждом такте работы устройства вычисляется как минимум одни разряд результата, а окончание процесса поиска определяется путем сравнения результатов двух последних итераций (по равенству), то сравнивать необходимо только q-1 старших разрядов, причем циклы сравнения и записи в регистр

1667106

15

25

3 0

9 8 блок 11 памяти блок 1z памяти блок 1з памяти блок lp памяти

35

40 такт работы

5 результата разнесены во времени (по переднему и заднему фронту синхроимпульса).

В режиме скользящей медианной фильтрации изображения на выходах блока 6 управления устанавливаются следующие сигналы:

Выход 18 19 20 21 22 23 24 25 26

1такт ф 1 Р Ф у Ф 1 1 ф

2 такт 1 ф Ф 1 1 1 Ф ф ф

3 такт ф Р ф 1 1 1 ф ф ф

4 такт 1 ф Ф 1 1 1 ф ф ф

Единичным сигналом с выхода 19 блока

6 управления разрешается запись величины порога (для рассмотренного случая медианной фильтрации величина порога равна (-(L+1)/2) в регистр 4 по входам 12 устройства. Считанная из блоков 1 памяти информация поступает на входы сумматоров 7 при этом с отрицательной величиной порога суммируется только информация с тех блоков 1 памяти, соответствующий (одноименный по номеру) разряд адреса которых равен нулю, Кроме того, независимо от соответствующего разряда адреса на вход а в блоках 1 памяти хранится следующая информация

Пусть в режиме СВГ в регистр 5 последовательно записываются следующие коды

0110, 1001, 1010. Тогда согласно алгоритму на выходе сумматора 7q (a значит и на выходе 17 устройства) последовательно, в каждом такте работы устройства, сформируются следующие суммы (фиг 4) I — 1. + а+ф+ф+ Ц = I — 9+ 6+Э I =- 3

1 — L +4+ b + 3.+ ф 1 = I — 9 + 2 4- 1 1 =- 6

1-1+ + b+g+ jl = 1-9+ 2+ 1= 7 т,е. с величиной (- ) суммируется информация только из тех блоков 1 памяти, соответствующий разряд адреса которых равен нулю. Знаковый разряд в регистр 3q не записывается, а на выход17 устройства всегда поступает положительное число. сумматора 71(I = 1,q) поступает информация, считанная с соответствующего блока 11 памяти. Инверсное значение знаков результатов, полученных в сумматорах 7 поступает на вторые входы коммутатора 8 (значит и на входы регистра 5 результата), Кроме того, данные разряды (кроме младшего) поступают на компаратор 9, Если соответствующие разряды регистра 5 и инверсные значения знаковых разрядов сумматоров 7 совпадают, то на выходе 16 устройства формируется единичный сигнал, свидетельствующий о том, что на выходе 15 устройства установлен результат поиска. В противном случае в регистр 5 результата записывается видоизмененное, грубое значение медианы и указанный процесс поиска повторяется.

Пример. Рассмотрим работу устройства в режимах СВГ и БМФ. Пусть изображение обрабатывается апертурой 3х3 элемента (= 9), причем q =-4. Тогда гистограмма фрагмента изображения имеет, например следующий вид:

Пусть в режиме ВМФ в регистре 5 хранится значение медианы N предыдущего фрагмента изображения, Рассмотрим три случая . N = 1011; N = 0110; N = 1001, Результаты вычислений приведены в таблице.

Медианой для данного фрагмента изображения является число 1001, В первом случае старое и новое значение медианы отличается в третьем разряде, Поэтому максимальное количество тактов работы устройства равно двум (в каждом такте определяется по одному разряду (третий и четвертый разряд) медианы). Так как в первом такте хранимое в регистре 5 число 1011 не совпадает тремя старшими разрядами с числом 1000, выставленным на знаковых выходах сумматоров 7, то необходим еще один

45 Во втором случае старое и новое значение медианы не совпадают в первом разряде (максимальное число тактов равно 4).

Однако, так как во втором такте был определен не только второй, но и третий разряд, то общее количество тактов равно трем. Если старое и новое значение медианы совпада1667106

10

20

35 ми входами элементов И и входами 40

50

55 ют, то устройство в режиме поиска медианы работает один такт.

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

1. Устройство для гистограммной обработки изображений обьектов, содержащее ц блоков памяти (ц — разрядность обрабатываемых данных), q сумматоров, q регистров данных, ц элементов И, блок управления, регистр порога и регистр результата, выход которого является информационным выходом устройства, информационный вход устройства соединен с входом начального адреса микрокоманды блока управления. вход смены режима которого является одноименным входом устройства. выходы блока управления с первого по четвертый соединены соответственно с входом разрешения записи регистра результата, с входом разрешения записи регистра порога, с первысчитывания блоков памяти, информационный выход i-го (i -- 1,q-1) блока памяти соединен с первым входом i-ro сумматора. информационный выход )-го сумматора (j =

=1,ö) подключен к информационному входу

j-го регистра данных, выход которого подключен к информационному входу)-ro блока памяти, выход j-го элемента И соединен с входом записи j-го блока памяти, информационный вход регистра порога является входом задания порога устройства, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет реализации операции медианной фильтрации, в него введены q шинных формирователей, компаратор и коммутатор, причем первый информационный вход коммутатора является входом задания начального значения медианы устройства, выход коммутатора подключен к информационному входу реги25

30 стра результата, второй информационный вход коммутатора соединен со знаковыми выходами q сумматоров, знаковые выходы (ц — 1) старших сумматоров подключены к первому информационному входу компаратора, второй информационный вход которого соединен с разрядными выходами (q — 1) старших разрядов регистра результата, адресные входы К-го (К = 2,q) блока памяти соединены с К вЂ” 1 выходом старших разрядов регистра результата, выход J-го разряда регистра результата соединен с вторым входом J-го элемента И и с входом разрешения выборки в режиме выравнивания гистограмм J-го шинного формирователя, информационный вход которого соединен с выходом J-го блока памяти, выход регистра порога подключен к вторым информационным входам сумматоров, выход I-го шинного формирователя подключен к (i+2)-му входу сумматоров с (i+1)-го по q-й, (q+2)-й вход q-го сумматора соединен с выходом q-ro шинного формирователя, первый выход блока управления соединен с управляющим входом компаратора, пятый выход-cуправляющим входом коммутатора, шестой и седьмой— соответственно с входами разрешения записи и входами обнуления регистров данных, восьмой выход — с входами блокировки информации в режиме поиска медианы (q1)-ro шинных формирователей, входы блокировки информации в режиме выравнивания гистограмм которых являются входами задания логической единицы устройства, девятый выход блока управления соединен с входом блокировки информации в режиме выравнивания гистограмм q-го шинного формирователя, вход блокировки информации в режиме поиска медианы которого является входом логического нуля устройства.

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

12 команды блока. а управляющий вход — вхо- входом регистра адреса, выход которого дом смены режима блока, выход коммутато- подключен к информационному входу дера адреса соединен с информационным шифратора. мац умм.+2

+2+

+2+

+2

+2+

+2+ - 2

-p+, - Д - +2

+g+

+)+

+2

+2+

> 2+

+2 2 >

- 2+

1667106

1667106

Составитель Е.Хуртин

Техред M,Ìîðãåíòàë

Корректор Т,Палий

Редактор С.Лисина

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

- Заказ 2526 Тираж 413 Подписное

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

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