Двухкаскадное устройство для ранговой фильтрации Советский патент 1987 года по МПК G06F17/17 

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

Тогда определенные ранее константы конкретизируются: К 3-разрядность; 2 16).

Элементом заданного ранга а послеизображении (на поиск элемента выбор- 5 довательности (набора данных) х,...

ки, отвечающего заданному критершо ранга).

Цель изобретения - расширение области применения за счет фильтрации

..., где п - нечетное, является такой элемент набора, что существуе Пд (п-1).а элементов меньших или равных ему по величине и ng(n-l)b

последовательностей произвольной элементов больших или равных ему по

ны.

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

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

Вычислительный блок 1 содержит дешифраторы 16, приоритетные шифрато-

величине при условии (при ,5 такой элемент называется медианой ).

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

Лусть n(l) - количество элементов, значение которых равно I (l 0,1,2,...,N-), тогда в качестве искомого выбирается такой элемент, для которого выполняется условие

I . .(l) (n-l)-a;

1 0

(1-0, N-1).

(О

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

Область значений плотности I разбивается на шестнадцать локальных областей &J , равных друг другу по количеству составляющих 1у и неперекрыры 17, элементы ИЛИ 18, первую группу 35 ающихся, как п |дстав 1 о, например, элементов И 19, вторую группу элементов И 20, реверсивные счетчики 21, мультиплексоры 22, узлы 23 сравнения, третью группу элементов И 24, элемент НЕ 25, 1К-триггер 26, первую группу регистров 27, вторую группу регистров 28, D-триггеры 29, сумматор 30, элементы 3 задержки, двоичный счетчик 32, элемент ИСКЛОЧАЮЩЕЕ ИЛИ

33, информационные входы 34, выход °« плотности, старших разрядов.Каждой локальной области гистона фиг. 3 (,5; ,15). В таком случае полный (8-разрядный) бинарный код плотности однозначно формируется из порядкового номера локальной об- Q ласти и порядкового номера плотности (их бинарных кодов), при этом номер области соответствует старшим и номер плотности в данной области - младшим разрядам полного бинарного.

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

Тогда определенные ранее константы конкретизируются: К 3-разрядность; 2 16).

Элементом заданного ранга а после..., где п - нечетное, является такой элемент набора, что существует Пд (п-1).а элементов меньших или равных ему по величине и ng(n-l)b

элементов больших или равных ему по

величине при условии (при ,5 такой элемент называется медианой ).

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

Лусть n(l) - количество элементов, значение которых равно I (l 0,1,2,...,N-), тогда в качестве искомого выбирается такой элемент, для которого выполняется условие

I . .(l) (n-l)-a;

1 0

(1-0, N-1).

(О

ающихся, как п |дстав 1 о, например,

на фиг. 3 (,5; ,15). В таком случае полный (8-разрядный) бинарный код плотности однозначно формируется из порядкового номера локальной об- ласти и порядкового номера плотности (их бинарных кодов), при этом номер области соответствует старшим и номер плотности в данной области - младшим разрядам полного бинарного.

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

S. ,. (I).

J . л

(2)

le t.j

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

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

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

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

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

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

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

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

5

0

5 0

0

5

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

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

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

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

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

51304036

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

Двухкаскад говой фильтра мяти и вычисл ционный вход информационно го блока, пер которого явля терия ранга у зультата кото зультата вычи личающе расширения об фильтрации по вольной длины группа из п э группа из К э памяти (к р , мультиплексор ный счетчик, ционный вход разряды инфор лительного бл ся старшими р го входа устр выхода резуль блока подключ ционному вход ляюш;ий вход к выми входами группы, вторы вычислительно дом задания п ройства, вход информационно ются входы де выход которог входу i-rb эл пы, выход кот разрешения об ти, выход мул адресному вхо вход управлен которого явля записью-считы формационный чика подключе ду i-ro блока

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

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

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

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

4036

Формула

6

3 о

5

O 5 0 0 35 0

45

50

р е т е н и я

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

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

с третьим управляющим входом вычислительного блока и является входом задания знака приращения устройства, выходом признака готовности результата которого является выход готов- ности результата вычислительного блока, причем вычислительный блок содержит два дешифратора, m реверсивных счетчиков, счетчик, 1К-триггер, две группы регистров, три мультиплексора т+1 узлов сравнения, сумматор, п D- триггеров, два приоритетных шифратора, три группы элементов И, m элементов ИЛИ, элемент исключающее ИЛИ, два элемента задержки и элемент НЕ

(, , , ), при этом старшими разрядами информационного входа вычислительного блока являются соответствующие входы первого дешифратора, i-й выход которого под- 20 ключен к 2-му входу j-ro элемента ИЛИ (,т; ,m; l,i), а первый . выход первого дешифратора подключен к первому входу i-ro элемента ИЛИ,

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

вторые входы элементов И первой группы соединены с входом элемента НЕ и являются третьим управляюш 1м входом вычислительного блока, выход элемента НЕ подключен к вторым входам элементов И второй группы, выходы (,m) элементов И первой и второй групп подключены соответственно к суммирующему и вычитающему входам s-ro реверсивного счетчика, информационный выход которого подключен к i-му информационному входу первого мультиплексора и первому входу з-го узла сравнения, выход Больше кото- .рого подключен к s-му входу первого приоритетного шифратора, выход которого подключен к управляющему входу первого мультиплексора, информационному входу второго регистра второй группы и является выходом старших разрядов выхода результата вычислительного блока, первым управляющим входом которого являются соединенные между собой вторые входы всех узлов сравнения, тактовые входы регистров первой группы соединены с

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

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

вход которого является входом задания логического нуля блока, выход второго элемента И третьей группы подключен к первому входу первого элемента НИИ, выход которого подклюг

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

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

nd

m

w,

1

j

j

(flue.3

Ланньге

/7pt/3f/aft AfCfCffU

И I И 1111 1 П M 11111 M M I n 11 i 111 i.. 11

I,I I

Г/ЯГ flff3ff/fm

гатовнас fTTU pP3-/rr r

Составитель A. Баранов Редактор E. Копча Техред в.Кадар Корректор Н. Король

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

(риеЛ

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