Двухкаскадное устройство для ранговой фильтрации

 

Изобретение относится к специализированным устройствам цифровой вычислительной техники, ориентирован8 ным на ранговую фильтрацию полутоновых изображений (на поиск элемента выборки, отвечающего заданному критерию ранга). Цель изобретения - расширение области применения за счет фильтрации последовательностей произвольной длины. Поставленная цель достигается за счет того, что двухкаскадное устройство для ранговой фильтрации содержит вычислительный блок 1, блоки памяти 2, мультиплексор 3, дешифратор 4, реверсивный счетчик 5, группы элементов ИЛИ 6,7, вход управления считьшанием/записью 8, вход старших разрядов 9, вход младших разрядов 10, вход задания признака конца маски 11, вход задания знака приращения 12, вход задания критерия ранга 13, выход результата 14, выход признака готовности результата 15. 4 йл. & (Л со о 4 О оо О5

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

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

РЕСПУБЛИК

„SU» 1304036

А1 (51) 4 G 06 F 15/353

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

ВНВ Щ;: .;, ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3996010/24-24 (22) 25.12.85 (46) 15.04.87. Вюл. У 14 (71) Институт автоматики и электрометрии CO АН СССР (72) В.И. Знак (53) 681.32(088.8) (56) Dolman D.I. Digital pipelined

hardvare median filter disign for

real-time processing. — Proc. Soc.

Photoopt Iustr. Eng 1981, 298, р. 184-188.

Danie1son P.Е. Getting the median faster. — Camputer Graphics

and Image Processing, 1981, v. 17, р. 71-78. (54) ДВУХКАСКАДНОЕ УСТРОЙСТВО ДЛЯ

РАНГОВОЙ ФИЛЬТРАЦИИ (57) Изобретение относится к специализированным устройствам цифровой вычислительной техники, ориентированУ ным на ранговую фильтрацию полутоновых изображений (на поиск элемента выборки, отвечающего заданному критерию ранга). Цель изобретения — расширение области применения за счет фильтрации последовательностей произвольной длины. Поставленная цель достигается за счет того, что двухкаскадное устройство для ранговой фильтрации содержит вычислительный блок 1, блоки памяти 2, мультиплексор 3, дешифратор 4, реверсивный счетчик 5, группы элементов ИЛИ 6,7, вход управления считыванием/записью

8, вход старших разрядов 9, вход младших разрядов 10, вход задания признака конца маски 11, вход задания знака приращения 12 вход задания критерия ранга 13, выход результата 14, выход признака готовности результата 15. 4 ил.

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

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

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

Двухкаскадное устройство содержит вычислительный блок 1, блоки 2 памяти, мультиплексор 3, дешифратор 4, 20 реверсивный счетчик 5, первую группу элементов ИЛИ 6, вторую группу элементов ИЛИ 7, вход 8 управления считыванием/записью, вход 9 старших разрядов, вход 10 младших разрядов, вход

11 задания признака конца маски (2-й управляющий вход), вход 12 задания знака приращения (3-й управляющий вход), вход 13 задания критерия ранга (1-й управляющий вход), выход 14 30 результата и выход 15 признака готовности результата.

Вычислительный блок 1 содержит дешифраторы 16, приоритетные шифраторы 17, элементы ИЛИ 18, первую группу 35 элементов И 19, вторую группу элементов И 20, реверсивные счетчики 21, мультиплексоры 22, узлы 23 сравнения, третью группу элементов И 24, элемент HE 25, IK-триггер 26, первую 40 группу регистров 27, вторую группу регистров 28, D-триггеры 29, сумматор

30, элементы 31 задержки, двоичный счетчик 32, элемент ИСКЛ10ЧАЮЩЕЕ ИЛИ

33, информационные входы 34, выход 35 45 старших разрядов.

Современные системы цифровой обработки полутоновых изображений оперируют, как правило, с 256-ю градациями плотности освещения, т.е. с 8-разрядными бинарными кодами, представляющими плотность серого в различных точках изображения. В связи с этим изложение алгоритма работы устройства производится для конкретного случая 8-разрядных входных данных, что однако не меняет основных принципов функционирования устройства в целом.

S, =Qn. (I)==(n-1) а; =о (I=O И-l). (1)

В рассматриваемом случае I 0,255— плотность освещения в различных точках изображения.

Область значений плотности Т разбивается на шестнадцать локальных областей ь, равных друг другу по количеству составляющих I;, и неперекрывающихся, как представлено, например, на фиг, 3 (j=-0,15; i=0,15). В таком случае полный (8-разрядный) бинарный код плотности однозначно формируется из порядкового номера локальной области и порядкового номера плотности (их бинарных кодов), при этом номер области соответствует старшим и номер плотности в данной области— младшим разрядам полного бинарного кода плотности.

Каждой локальной области гистограммы соответствует локальная сумма вида

Б -= п,. (I) (2) 1Е М

Тогда поиск заданного элемента набора данных может производиться в соответствии с условием 11) в два этапа: использование локальных сумм (2) для оценки старших разрядов; использование значений плотности, входящих в локальную область, определяемую старшими разрядами, для оценки младших разрядов искомого элемента.

36 2

Тогда определенные ранее константы конкретизируются: К=В-разрядность;

a=b=k/2=4; m=n=2 =2 =2 =16).

Элементом заданного ранга а последовательности (набора данных) х,,... ...,х„, где n — нечетное, является такой элемент набора, что существует

n =(n-l) а элементов меньших или равных ему по величине и n>=(n-1) ° Ь элементов больших или равных ему по величине при условии а+Ь=1 (при а=Ь=0,5 такой элемент называется медианой).

Гистограммный поиск элемента определенного вида производится через построение и анализ гистограммы набора данных.

Пусть n(I) — количество элементов, значение которых равно I (I=

=0,1,2,...,N-l), тогда в качестве искомого выбирается такой элемент, цля которого выполняется условие

3 130403

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

Реализация данных этапов совмещается во времени, при этом гистограмма формируется по мере поступления данных (данные поступают последова- f0 тельно, порядок поступления безразличен). Старшие разряды результата вычисляются параллельным образом в темпе поступления данных. Младшие разряды вычисляются последовательно 15 на основе результата, полученного после оценки старших разрядов. Временная диаграмма рассмотренного процесса приведена на фиг. 4.

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

Значения гистограммы хранятся в шестнадцати независимо организованных блоках памяти. Выбор блока определяется четырьмя младшими разрядами входных данных (кодов плотности освещения в различных точках изображения или просто данных), а выбор адреса — четырьмя старшими. Содержимое выбранного адреса заданного блока па- 30 мяти увеличивается (или уменьшается в зависимости от режима) на единицу посредством реверсивного счетчика 5.

Рассмотренная укладка значений

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

Вычислительный блок 1 включает цепь вычисления старших разрядов и цепь вычисления младших разрядов результата. Основными составляющими первой выступают каскад двоичных универсальных счетчиков, каскад узлов 45 сравнения и приоритетный шифратор.

В i-м счетчике соответствующего каскада с каждым поступлением данных формируется i-я частная сумма, как определено условием (1) по локальным зонам гистограммы, которая затем сравнивается с критерием ранга (п-1)" са, и результат сравнения поступает на соответствующий вход приоритетного шифратора (i=1,16, n — объем Bbtборки данных; а — заданный ранг}.

Таким образом, старшие разряды результата доступны для чтения в любой момент времени и по поступлении при6 4 знака конца выборки фиксируются (с задержкой, определяемой временем срабатывания цепи) в соответствующем регистре. Исходное содержание каскада счетчиков — пусто.

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

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

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

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

5 laOaO

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

-последующих наложений регламентирует,ся пользователем.

В режиме полного перебора требует- fO ся обеспечивать последовательное поступление. данных на информационные входы устройства (вход старших и вход младших разрядов). При каждом поступлении данных на вход управления счи- l5 тыванием/записью подается управляющее воздействие "Считывание и затем — управляющее воздействие Запись". Состояние информационных входов сохраняется неизменным на весь 20 период времени, необходимый для считывания — инкремента-декремента — записи. По окончании перебора текуще— го набора данных после поступления последнего элемента на управляющий вход признака конца маски подается, если произведено считывание результата обработки предыдущего набора, Соответствующее воздействие, в противном случае подача признака конца ЗО маски задерживается. Считывание результата с информационного выхода устройства производится с установлением признака готовности результата на соответствующем выходе. С установ- 35 кой признака конца маски на соответствующем входе обеспечивается (без ожидания окончания признака конца маски) поступление данных следующей выборки (набора данных). В течение 40 всего процесса переброса данных текущей выборки на соответствующем входе установлен знак положительного приращения.

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

36 6 формула изобретения

Двухкаскадное устройство для ранговой фильтрации, содержащее блок памяти и вычислительный блок, информационный вход которого подключен к информационному входу вычислительного блока, первый управляющий вход которого является входом задания критерия ранга устройства, выходом результата которого является выход результата вычислительного блока, о тл и ч а ю щ е е с я тем, что с целью расширения области применения за счет фильтрации последовательностей произвольной длины, в него введены первая группа из п элементов ИЛИ, вторая группа из К элементов ИЛИ, п-1 блоков памяти (К вЂ” разрядность фильтрации, п=2, Ь=)К/2(, )х(— целая часть х), мультиплексор, дешифратор и реверсивный счетчик, причем первый информационный вход мультиплексора и старшие разряды информационного входа вычислительного блока объединены и являются старшими разрядами информационного входа устройства, старшие разряды выхода результата вычислительного блока подключены к второму информационному входу мультиплексора, управляющий вход которого соединен с первыми входами элементов ИЛИ первой группы, вторым управляющим входом вычислительного блока и является вхоцом задания признака конца маски устройства, входами младших разрядов информационного входа которого являются входы дешифратора, i-й (i=1,n) выход которого подключен к второму входу i-ro элемента ИЛИ первой группы, выход которого подключен к входу разрешения обращения i — ro блока памяти, выход мультиплексора подключен к адресному входу i-го блока памяти, вход управления зачисью-считыванием которого является входом управления записью-считыванием устройства, информационный выход реверсивного счетчика подключен к информационному входу i-ro блока памяти, выход j-ro (j=l,Ê) разряда которого подключен к i-му входу j-го элемента ИЛИ второй группы, выход i-го блока памяти подключен к i-му информационному входу вычислительного блока, выходы элементов ИЛИ второй группы подключены к входам соответствующих разрядов реверсивного счетчика, вход задания направления счета которого соединен

7 130403 с третьим управляющим входом вычислительного блока и является входом задания знака приращения устройства, выходом признака готовности результата которого является выход готов5 ности результата вычислительного бло— ка, причем вычислительный блок содержит два дешифратора, m реверсивных счетчиков, счетчик, IK-триггер, две группы регистров, три мультиплексора, lð

m+1 узлов сравнения, сумматор, п Dтриггеров, два приоритетных шифратора, три группы элементов И, m элементов ИЛИ, элемент исключающее ИЛИ, два элемента задержки и элемент HE 15 (m=2, n=2, a+b=k, a=b=Jk/2f), при этом старшими разрядами информационного входа вычислительного блока являются соответствующие входы первого дешифратора, i-й выход которого под- 2р ключен к 1-му входу J-го элемента

ИЛИ (i=2,m; 1=2,m; 3=1,i), а первый выход первого дешифратора подключен к первому входу i-го элемента ИЛИ, первым входам i=x элементов И первой 25 и второй групп, выход i-ro элемента

ИЛИ подключен к первым входам i-õ элементов И первой и второй групп, вторые входы элементов И первой группы соединены с входом элемента HE и ЗО являются третьим управляющим входом вычислительного блока, выход элемента НЕ подключен к вторым входам элементов И второй группы, выходы s=x (s=1,m) элементов И первой и второй групп подключены соответственно к суммирующему и вычитающему входам

s-го реверсивного счетчика, информационный выход которого подключен к

i-му информационному входу первого 4р мультиплексора и первому входу s-го узла сравнения, выход "Больше" кото.рого подключен к s-му входу первого приоритетного шифратора, выход которого подключен к управляющему входу первого мультиплексора, информационному входу второго регистра второй группы и является выходом старших разрядов выхода результата вычислительного блока, первым управляющим 5р входом которого являются соединенные между собой вторые входы всех узлов сравнения, тактовые входы регистров первой группы соединены с установочным входом IK-триггера, вхо- 55 дом обнуления счетчика, входом первого элемента задержки и является вторым управляющим входом вычислительного блока, выход первого элемента

6 8 задержки подключен к тактовому входу второго регистра второй группы, второму входу первого элемента ИЛИ и управляющему входу второго мультиплексора, i-м информационным входом вычислительного блока является информационный вход i-ro регистра первой группы, выход которого подключен к

i-му информационному входу третьего мультиплексора, управляющий вход которого соединен с входом второго дешифратора и подключен к информационному выходу счетчика, счетный вход которого подключен к выходу первого элемента И третьей группы, первые входы элементов И которой подключены к выходу IK-триггера, вход сброса которого соединен с входом второго элемента задержки и подключен к выходу третьего элемента И третьей группы, выход второго элемента задержки является выходом готовности результата вычислительного блока, входом синхронизации которого являются соединенные между собой вторые входы первого и второго элементов И третьей группы, второй вход третьего элемента И которой подключен к выхо— ду элемента ИСКПОЧАЮЩЕЕ ИЛИ, первый вход которого является входом задания логического нуля блока, выход второго элемента И третьей группы подключен к первому входу первого элемента ИЛИ, выход которого подключен к тактовому входу первого регистра второй группы, информационный вход которого подключен к выходу второго мультиплексора, а выход первого регистра второй группы подключен к первому входу сумматора и первому . входу (m+1)-го узла сравнения, выход третьего мультиплексора подключен к второму входу сумматора, выход которого подключен к первому информационному входу второго мультиплексора, второй информационный вход которого подключен к выходу первого мультиплексора, i-й выход второго дешифратора подключен к тактовому входу i-го

D òðèããåðà, выход которого подключен к i-му входу второго приоритетного шифратора, выход (ш+1)-го узла сравнения подключен к информационному входу i-ro D-триггера и второму входу элемента ИСКЛ1ОЧАИЩЕЕ ИЛИ, а выход второго регистра второй группы соединен с выходом второго приоритетного шифратора и является выходом результата вычислительного блока.

130403á

1304036

Яана

Прижав л гж м власии сл. р з

Мл оЗ

QA Б/ фм.юю гюлю/ю лтирюФиест

Составитель А. Баранов

Редактор E. Копча Техред В.Кадар

Корректор Н. Король

Заказ 1313/50 Тираж б73 Подписное

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

113035, Москва, 3-35, Раушская наб., д. 4/5

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