Устройство для гистограммной обработки изображений объектов Советский патент 1991 года по МПК G06T5/40 

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

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

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

Устройство для гистограммной обработки изображений объектов (фиг.1) содержит q блоков 1 памяти (q - разрядность обрабатываемых данных), 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 микрокоманд.

Шинный формирователь (фиг.З) содержит группу элементен И 33, з,.смент ИЛИ- НЕ 34 и элемент И 35.

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

Устройств ) работает в следующих режимах; обнуление значений отсчетов i ис- тограмм; включение входного отсчета в гистограмму i-i n/одного отсчитч

из гистограммы; скользящего выравнивания гистограммы; скользящей медианной фильтрации изображения.

Перед началом работы устройства регистры 3-5 обнулены, во всех запоминающих ячейках блоков памяти 1 j (| 1,q) записаны нулевые сигналы, а на выходах блока 6 управления сформированы следующие сигналы; выходы 18-1 - запись в регистр 5

0 результата запрещена (запись в двухтактный регистр 5 осуществляется по заднему фронту синхроимпульса) и разблокировка компаратора 9; выход 19-0- запись в регистр 4 порога запрещена; выход разреше5 ние чтения информации из блоков 1 памяти; выход 21-0- запрет выборки блоков 1 памяти; выход 22-0- информация передается с входов 13 устройства на входы регистра 5: выход 23-0- запись в регистры 3 данных

0 запрещена; выход - обнуление содержимого регистров 3 данных; выход 25-1 - блокировка шинных формирователей 10 (на их выходах сформированы нулевые сигналы); выход 26-р - запреще-ние управления

5 шинным формирователем 10,

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

В режиме обнуления значений отсчетов

5 гистограмм на информационном входе 11 устройства формируется код обнуления. На вход 14 поступает единичный импульс, который настраивает коммутатор 30 на передачу информации с входов 11 устройства

0 на вход регистра 29 адреса микрокоманды. При этом на выходах блока 6 управления устанавливаются следующие сигналы:

Выход 18 19 20 21 22 23 24 25 26 1 такт Р 0 0 0 0 0 } 1 0

5 2 такт 1 0 1 1 0 0 1 1 0

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

По заднему фронту сигнала, установленного на выходе 18 блока 6 управления, осуществляется запись адреса в регистр результата.

5Во втором такте происходит выборка

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

На входах 13 устройства формируется адрес очередной ячейки блоков 1 памяти, подлежащих обнулению и указанный процесс повторяется.

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

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

Режим исключения (вычитания) входного отсчета из гистограммы выполняется аналогично. При этом в регистр 4 порога с входа 12 записывается (-1), что обеспечивает выполнение операции уменьшения заданного отсчета гистограммы на единицу.

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

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

1такт 010 00011 1

2такт 1 р 0 1 0 1 J0 0 1 Единичным сигналом с выхода 19 блока

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

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

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

20

D

d 0

H(d).

где D - входной отсчет; D1 - результат;

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

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

Если L 2К (где К - целое, К 0), нормализация результата проводится тривиальным перемещением запятой относительно разрядной сетки результата. Если L 2К, нормализация выполняется программным или

аппаратным способом во внешнем устройстве, управляющем работой устройства.

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

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

00110

11000 1 1 ф ф ф 1 1 ф ф Ф

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

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

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

1такт 0100

2такт 1001

3такт 0001

4такт 1001

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

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

сумматора 71 (I 1 ,q) поступает информация, считанная с соответствующего блока 11 памяти. Инверсное значение знаков результатов, полученных в сумматора/ч 7 поступает на вторые входы коммутатора 8 (значит и на входы регистра 5 результата).

Кроме того, данные разряды (кроме младшего) поступают на компаратор 9. Если

соответствующие разряды регистра 5 и инверсные значения знаковых разрядов сумматоров 7 совпадают, то на выходе 16 устройства формируется единичный сигнал, свидетельствующий о том, что на выходе 15

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

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

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

а в блоках 1 памяти хранится следующая информация

блок 11 памяти блок 1а памяти блок 1з памяти олок )4 памяти

Пусть в режиме СВГ в регистр 5 последовательно записываются следующие коды 0110, 1001, 1010. Тогда согласно алгоритму на выходе сумматора 7q (а значит и на выходе 17 устройства) последовательно, в каждом такте работы устройства, сформируются следующие суммы (фиг.4)

+ #+Ы 1-9 + 6+эНЗ I - + b + Г, + 0| 1-9 + 2+11 6 I- L +0 f b +0 - j | | -9 + 24 f 7

т.е. с величиной (-L) суммируется информация только из тех блоков 1 памяти сослвет- ствующий разряд адреса которых равен нулю. Знаковый разряд в регистр 3q не записывается, а на выход 17 устроит гвя чсв да поступает положительное число

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

Результаты вычислений приведены в таблице.

Медианой для данного фрагмента изображения является чи.сло 1001. В первом случае старое и новое значение медианы

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

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

общее количество тактов равно трем. Если старое и новое значение медианы совпадают, то устройство в режиме поиска медианы работает один такт.

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

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

первому информационному входу компаратора, второй информационный вход которого соединен с разрядными выходами (q-1) старших разрядов регистру результата, адресные входы К-го (К 2,q) блока памяти

0 соединены с К-1 выходом старших разрядов регистра результата, выход j-ro разряда регистра результата соединен с вторым входом j-ro элемента И и с входом разрешения выборки в режиме выравнивания гистог5 рамм J-ro шинного формирователя, информационный вход которого соединен с выходом J-ro блока памяти, выход регистра порога подключен к вторым информационным входам сумматоров, выход 1-го шинного

0 формирователя подключен к (1+2)-му входу сумматоров с (1+1)-го по q-й, (д+2)-й вход q-ro сумматора соединен с выходом q-ro шинного формирователя, первый выход блока управления соединен с управляющим входом

5 компаратора, пятый выход-с управляющим входом коммутатора, шестой и седьмой - соответственно с входами разрешения записи и входами обнуления регистров данных, восьмой выход - с входами блокировки

0 информации в режиме поиска медианы (q- 1)-го шинных формирователей, входы блокировки информации в режиме выравнивания гистограмм которых являются входами задания логической единицы ус5 тройства, девятый выход блока управления соединен с входом блокировки информации в режиме выравнивания гистограмм q-ro шинного формирователя, вход блокировки информации в режиме поиска медианы ко0 торого является входом логического нуля устройства.

5 коммутатор адреса, матрицу памяти микропрограмм, регистр микрокоманд и генератор тактовых импульсов, выход которого подключен к тактовому входу дешифратора, выход которого соединен с адресным вхо0 дом памяти микропрограмм матрицы, выход которой подключен к информационному входу регистра микрокоманд, разрядные выходы первого информационного выхода которого являются соответственно с перво5 го по девятый выходами блока, второй информационный выход регистра микрокоманд соединен с первым информационным входом коммутатора адреса, второй информационный вход которого является входом начального адреса микрокоманды блока, а управляющий вход - вхо дом смены режима блока, выход коммутатора адреса соединен с информационным

входом регистра адреса выход которого подключен к информационному входу дешифратора

Фаг 2 18 26

ФигМ

Фиг. 5