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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК1304036 1)4 С 06 353 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ ЕТ ЕНИЯ(71) Институт автоматики иметрии СО АН СССР(54) ДВУХКАСКАДНОЕ УСТРОЙСТВОРАНГОВОЙ ФИЛЬТРАЦИИ(57) Изобретение относится к слизированным устройствам цифрочислительной техники, ориентир электро 1 пе Гог Сйе шегар 1 п.с я 1, ч. 17 7,ю ециаой выван:Ь е 1 ОПИ САНИ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ным на ранговую фильтрацию полутоновых изображений (на поиск элементавыборки, отвечающего заданному критерию ранга), Цель изобретения - расширение области применения за счетфильтрации последовательностей произвольной длины. Поставленная цельдостигается за счет того, что двухкаскадное устройство для ранговойфильтрации содержит вычислительныйблок 1, блоки памяти 2, мультиплексор 3, дешифратор 4, реверсивныйсчетчик 5, группы элементов ИЛИ 6,вход управления считыванием/запись8, вход старших разрядов 9, входмладших разрядов 10, вход заданияпризнака конца маски 1, вход задания знака приращения 12, вход задания критерия ранга 13, выход результата 14, выход признака готовностирезультата 15, 4 ил.(2) Изобретение относится к специализированным устройствам цифровой вычислительной техники, ориентированнымна ранговую Фильтрацию полутоновыхизображений (на поиск элемента выборки, отвечающего заданному критериюранга).Цель изобретения - расширение области применения за счет Фильтрациипоследовательностей произвольной длиОны,На фиг. 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, элемент НЕ 25, 1 К-триггер 26, первую 40группу регистров 27, вторую группурегистров 28, Б-триггеры 29, сумматор30, элементы 31 задержки, двоичныйсчетчик 32, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ33, информационные входы 34, выход 35 45старших разрядов. Современные системы цифровой обработки полутоновых изображений оперируют, как правило, с 256-ю градациями плотности освещения, т.е, с 8-разрядными бинарными кодами, представляющими плотность серого в различных точках изображения. В связи с этим изложение алгоритма работы устройства производится для конкретного случая 8-разрядных входных данных, что однако не меняет основных принципов функционирования устройства в целом. 36 2Тогда определенные ранее константы конкретизируются: К=В-разрядность; а=Ь:1/2=4; ш-и":2 :24:16)Элементом заданного ранга а последовательности (набора данных) х ,х, где и - нечетное, является такой элемент набора, что существует и =(и) а элементов меньших или равных ему по величине и п=(п)Ь элементов больших или равных ему по величине при условии а+Ь= (при а=Ь=0,5 такой элемент называется медианой).Гистограммный поиск элемента определенного вида производится через построение и анализ гистограммы набора данных.Пусть п(1) - количество элементов, значение которых равно 1 (1= =0,1,2М), тогда в качестве искомого выбирается такой элемент, цля которого выполняется условие Б, = и. (1) =-. (и) а;(1=0, И). (1)В рассматриваемом случае 1=0,255 -плотность освещения в различных точках изображения.Область значений плотности 1 разбивается на шестнадцать локальных областей ь;, равных друг другу по количеству составляющих 1, и неперекрывающихся, как представлено, например, на фиг, 3 =:0,15; з.=О,5). В таком случае полный (8-разрядный) бинарный код плотности однозначно Формируется из порядкового номера локальной области и порядкового номера плотности (их бинарных кодов), при этом номер области соответствует старшим и номер плотности в данной области - младшим разрядам полного бинарного кода плотности.Каждой локальной области гистограммы соответствует локальная сумма вида Е МТогда поиск заданного элемента набора данных может производиться в соответствии с условиемв два этапа: использование локальных сумм (2) для оценки старших разрядов; использование значений плотности, входящих в локальную область, определяемую старшими разрядами, для оценки младших разрядов искомого элемента.3 130403Алгоритм работы устройства, основанный на изложенной концепции, включает следующие этапы: формированиегистограммы; оценка четырех старшихразрядов результата; оценка четырехмладших разрядов результата,Реализация данных этапов совмещается во времени, при этом гистограмма формируется по мере поступленияданных (данные поступают последова- Ютельно, порядок поступления безразличен). Старшие разряды результатавычисляются параллельным образом втемпе поступления данных. Младшиеразряды вычисляются последовательно 15на основе результата, полученногопосле оценки старших разрядов, Временная диаграмма рассмотренного процесса приведена на фиг. 4,Устройство работает следующим образом.Значения гистограммы хранятся вшестнадцати независимо организованных блоках памяти. Выбор блока определяется четырьмя младшими разрядами 5входных данных (кодов плотности освещения в различных точках изображения или просто данных), а выбор адреса - четырьмя старшими. Содержимоевыбранного адреса заданного блока памяти увеличивается (или уменьшаетсяв зависимости от режима) на единицупосредством реверсивного счетчика 5. Рассмотренная укладка значений35 гистограммы обеспечивает при необходимости одновременное считывание всех составляющих отдельной локальной области.Вычислительный блок 1 включает цепь вычисления старших разрядов и цепь вычисления младших разрядов результата. Основными составляющими первой выступают каскад двоичных универсальных счетчиков, каскад узлов 45 сравнения и приоритетный шифратор.В -м счетчике соответствующего каскада с каждым поступлением данных формируется -я частная сумма, как определено условием (1) по локальным зонам гистограммы, которая затем сравнивается с критерием ранга (и)" са, и результат сравнения поступает на соответствующий вход приоритетного шифратора (=1,16, и - объем выборки данных; а - заданный ранг). Таким образом, старшие разряды результата доступны для чтения в любой момент времени и по поступлении при 6 4знака конца выборки фиксируются (с задержкой, определяемой временем срабатывания цепи) в соответствующем регистре. Исходное содержание каскада счетчиков - пусто.В цепи младших разрядов аналогичный предыдущему процесс реализуется последовательно. Здесь по поступлении приказа конца выборки в каскаде регистров фиксируются составляющие локальной области гистограммы, а в накопителе (сумматор - регистр) - соответствующая частная сумма, где номер области и номер частной суммы задаются с выхода цепи старших разрядов. Тактирование процесса оценки младших разрядов может производиться независимо от работы устройства в целом и ограничивается сверху только быстродействием элементов цепи.С началом оценки младших разрядов текущей выборки может начинаться процесс оценки старших разрядов следующей выборки данных, однако признак конца следующей выборки может поступать только после завершения процесса оценки младших разрядов текущей выборки. Завершение такого процесса контролируется по состоянию выхода признака готовности результата.При фильтрации изображения происходит последовательное перемещение окна фильтра, определяющего объем выборки данных, от одной окрестности к другой - соседней (отстоящей от предыдущей на один отсчет или дискрет), т.е. часть точек изображения накрывается окном фильтра повторно, что позволяет новую выборку формировать путем добавления данных, соответствующих вновь накрытым точкам изображения, и отбрасывания такого же количества вщбывших. Учет этого обстоятельства при формировании гистограммы в определенных случаях существенно снижает трудоемкость фильтрации. Реализация такого режима в устройстве регулируется посредством управления знаком приращения, что, в свою очередь, определяет работу реверсивного счетчика 5 и работу цепи старших разрядов. Длительность процесса вычисления младших разрядов результата зависит только от индекса составляющей локальной области гистограммы, для которой выполнится условие (1).5 1 ЗО 40Будем различать режим полного перебора элементов маски (окна фильтрации)и режим перебора крайних (добавляемыхи отбрасываемых) элементов. При этомрежим полного перебора используетсяпри всяком первом наложении маски(получении первого результата), Режимпоследующих наложений регламентирует,ся пользователем,В режиме полного перебора требуется обеспечивать последовательное поступление. данных на информационныевходы устройства (вход старших и входмладших разрядов). При каждом поступлении данных на вход управления считыванием/записью подается управляющее воздействие "Считывание и затем - управляющее воздействие Запись", Состояние информационных входов сохраняется неизменным на весь 20период времени, необходимый для считывания - инкремента-декремента - записи, По окончании перебора текущего набора данных после поступленияпоследнего элемента на управляющий .25вход признака конца маски подается,если произведено считывание результата обработки предыдущего набора,Соответствующее воздействие, в противном случае подача признака конца 30маски задерживается, Считывание результата с информационного выходаустройства производится с установлением признака готовности результатана соответствующем выходе. С установ- З 5кой признака конца маски на соответствующем входе обеспечивается (.безожидания окончания признака концамаски) поступление данных следующейвыборки (набора данных). В течение 40всего процесса переброса данных текущей выборки на соответствующем входе установлен знак положительногоприращения. Режим перебора крайних элементов отличается от режима полного перебора только последним пунктом, который формируется в рассматриваемом случае следующим образом, При поступлении на информационные входы устройства тех данных, которые соответствуют добавляемым элементам, используется знак положительного приращения, а при поступлении данных, соответствующих отбрасываемым элементам, используется знак отрицательного приращения. При этом порядок поступления данных безразличен. 36 6формула изобретенияДвухкаскадное устройство для ранговой фильтрации, содержащее блок памяти и вычислительный блок, информационный вход которого подключен к информационному входу вычислительного блока, первый управляющий вход которого является входом задания критерия ранга устройства, выходом результата которого является выход результата вычислительного блока, о тл и ч а ю щ е е с я тем, что с целью расширения области применения за счет фильтрации последовательностей произвольной длины, в него введены первая группа из и элементов ИЛИ, вторая группа из К элементов ИЛИ, иблоков памяти (К - разрядность фильтрации, и=2, Ь=ЗК/2, 1 х( - целая часть х), мультиплексор, дешифратор и реверсивный счетчик, причем первый информационный вход мультиплексора и старшие разряды информационного входа вычислительного блока объединены и являются старшими разрядами информационного входа устройства, старшие разряды выхода результата вычислительного блока подключены к второму информационному входу мультиплексора, управляющий вход которого соединен с первыми входами элементов ИЛИ первой группы, вторым управляющим входом вычислительного блока и является входом задания признака конца маски устройства, входами младших разрядов информационного входа которого являются входы дешифратора, -й (1=1,и) выход которого подключен к второму входу -го элемента ИЛИ первой группы, выход которого подключен к входу разрешения обращения х-го блока памяти, выход мультиплексора подключен к адресному входу д-го блока памяти, вход управления зачисью-считыванием которого является входом управления записью-считыванием устройства, информационный выход реверсивного счетчика подключен к информационному входу 1.-го блока памяти, выход )-го =1,К) разряда которого подключен к -му входу )-го элемента ИЛИ второй группы, выход -го блока памяти подключен к -му информационному входу вычислительного блока, выходы элементов ИЛИ второй группыподключены к входам соответствующих разрядов реверсивного счетчика, вход задания направления счета которого соединен7 130403 с третьим управляющим входом вычислительного блока и является входом задания знака приращения устройства, выходом признака готовности результата которого является выход готов 5 ности результата вычислительного блока, причем вычислительный блок содержит два дешифратора, ш реверсивных счетчиков, счетчик, 1 К-триггер, две группы регистров, три мультиплексора, 1 О ш+1 узлов сравнения, сумматор, и Р- триггеров, два приоритетных шифратора, три группы элементов И, ш элементов ИЛИ, элемент исключающее ИЛИ, два элемента задержки и элемент НЕ 15 (ш=2 , и=2 , а+Ь=К, а=Ь=3/2 Г), при этом старшими разрядами информационного входа вычислительного блока являются соответствующие входы первого дешифратора, 1-й выход которого под ключен к 1-му входу )-го элемента ИЛИ (=2,п; Д=2.,т; И=,з.), а первый выход первого дешифратора подключен к первому входу -го элемента ИЛИ, первым входам =х элементов И первой 25 и второй групп, выход -го элемента ИЛИ подключен к первым входам -х элементов И первой и второй групп, вторые входы элементов И первой группы соединены с входом элемента НЕ и ЗО являются третьим управляющим входом вычислительного блока, выход элемента НЕ подключен к вторым входам элементов И второй группы, выходы з=х (в=1,п) элементов И первой и второй групп подключены соответственно к суммирующему и вычитающему входам з-го реверсивного счетчика, информационный выход которого подключен к -му информационному входу первого 40 мультиплексора и первому входу з-го узла сравнения, выход Больше" кото.рого подключен к з-му входу первого приоритетного шифратора, выход котоРого подключен к упРавляющему входу 45 первого мультиплексора, информационному входу второго регистра второй группы и является выходом старших разрядов выхода результата вычислительного блока, первым управляющим 5 О входом которого являются соединенные между собой вторые входы всех узлов сравнения, тактовые входы регистров первой группы соединены с установочным входом 1 К-триггера, вхо дом обнуления счетчика, входом первого элемента задержки и является вторым управляющим входом вычислительного блока, выход первого элемента 6 8задержки подключен к тактовому входу второго регистра второй группы, второму входу первого элемента ИЛИ и управляющему входу второго мультиплексора, -м информационным входом вычислительного блока является информационный вход -го регистра первой группы, выход которого подключен к -му информационному входу третьего мультиплексора, управляющий вход которого соединен с входом второго дешифратора и подключен к информационному выходу счетчика, счетный вход которого подключен к выходу первого элемента И третьей группы, первые входы элементов И которой подключены к выходу 1 К-триггера, вход сброса которого соединен с входом второгго элемента задержки и подключен к выходу третьего элемента И третьей группы, выход второго элемента задержки является выходом готовности результата вычислительного блока, входом синхронизации которого являются соединенные между собой вторые входы первого и второго элементов И третьей группы, второй вход третьего элемента И которой подключен к выходу элемента ИСКПОЧАЮЩЕЕ ИЛИ, первый вход которого является входом задания логического нуля блока, выход второго элемента И третьей группы подключен к первому входу первого элемента ИЛИ, выход которого подклю-. чен к тактовому входу первого регистра второй группы, информационный вход которого подключен к выходу второго мультиплексора, а выход первого регистра второй группы подключен к первому входу сумматора и первому . входу (ш+1)-го узла сравнения, выход третьего мультиплексора подключен к второму входу сумматора, выход которого подключен к первому информационному входу второго мультиплексора, второй информационный вход которого подключен к выходу первого мультиплексора, -й выход второго дешифратора подключен к тактовому входу -го Р-триггера, выход которого подключен к -му входу второго приоритетного шифратора, выход (ш+1)-го узла сравнения подключен к информационному входу -го Р-триггера и второму входу элемента ИСКЛ 1 ОЧА 1 ОЩЕЕ ИЛИ, а выход второго регистра второй группы соединен с выходом второго приоритетного шифратора и является выходом результата вычислительного блока.1304036 оин ража аюд асии Л ОФУУОЬ/ Составитель А, Барановактор Е. Копча Техред В.КадарКорректор Н, Корол Подписноитета СССР За ткрытиикая наб.,оектная,роизводственно-полиграфическое предприятие, г, Ужгоро флаг гююЮг тирвз 313/50 Тираж б 73 ВНИИПИ Государственного ко по делам изобретений и 113035, Москва, 3-35, Рауш