Устройство ранговой фильтрации

(19 51)5 6 06 Р 15/35У 7 ТЕНИ ВИДЕТЕЛ ЬСТВУ АВТОР КО%25онструкторское бюроения СО АН СССР, Ю.В. Обидин и А.Н на 1 азтег,еззп 9,Оеп 1 п 9 йе весИа апб 1 ва 9 е Рго 71-78.детельство СССР 6 Р 15/353, 1985 РАНГОВОЙ ФИ ЬТРАотносится к спец твам вычислитель им ранговую фил ражений (поиск эл еленном месте в у иализиной техьтрацию емента, порядоиг,Г ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР САНИЕ ИЗОБР. (71) Специальное кучного приборостр(57) Изобретениерованным устройсники, выполняющполутоновых изобстоящего на опред ченнои последовательности из всех элементов выборки) в системах обработки изображений в реальном времени для устранения импульсных помех, Целью изобретения является упрощение устройства и увеличение быстродействия при получении результата из накопленной гистограммы, Цель достигается за счет того, что устройство состоит из р блоков (2рК где 1 - разрядность фильтрации), в блоках памяти происходит накопление гистрограмм не по одному значению, а в пределах определенных интервалов, из критерИя ранга вычитается значение, полученное в старших каскадах, после накопления гистограммы результат получается параллельным способом во всех блоках устройства. Устройство содержит вычислительный блок 1 и р - 1 блоков 2 на- Б копления гистограммы. 3 ил.Изобретение относится к специализированным устройствам вычислительной техники, ориентированным на ранговую фильтрацию полутоновых изображений (на поиск элемента выборки, отвечающего заданному критерию ранга), и может быть использовано в системах обработки изображений в реальном времени для устранения импульсных помех.Цель изобретения - упрощение устройства и увеличение быстродействия при получении результата из накопленной гистограммы;На фиг, 1 приведена структурная схема устройства; нэ фиг. 2 - функциональная схема вычислительного блока; на фиг, 3 - функциональная схема блока накопления гистограммы.Устройство (фиг. 1) содержит вычислительный блок 1, рблоков 2 накопления гистограммы, (2р 5 К 1 - разрядность фильтрации), вход 3 данных устройства, вход 4 критерия ранга, устройства, вход 5 знака приращения устройства, вход 6 признака конца маски устройства, вход 7 управления считыванием-записью устройства, выход 8 результата устройства,Вычислительный блок 1 (фиг. 2) содержит дешифратор 9, элемент НЕ 10, группу элементов ИЛИ 11, первую группу элементов И 12, вторую группу элементов И 13, группу реверсивных счетчиков 14, мультиплексор 15, группу узлов 16 сравнения, приоритетный шифратор 17, выход 18 результата блока, вход 19 логического нуля блока 1, выход 20 блока 1Блок 2 накопления гистограммы (фиг. 3) содержит мультиплексор 21, дешифратор 22, группу элементов ИЛИ 23, группу блоков 24 памяти, реверсивные счетчики 25, вычислитель 26, мультиплексор 27, группу узлов 28 сравнения, приоритетный шифратор 29, входы 30-32 блока, выходы 33 - 35 блока.Ранговая фильтрация последовательностей (набора данных) производится устройством в два этапа. На первом этапе, при поступлении в устройство набора данных производится подсчет элементов счетчиками, причем каждый счетчик считает элементы своего диапазона значений, На втором этапе путем сравнения состояний счетчиков с заданным рангом г(или функцией от него) производится определение значения Хг, соответствующего рангу,Устройство содержит несколько каскадов счетчиков. В первом каскаде весь диапазон допустимых значений данных разбивается на й равных зон. Каскад содержит Мсчетчиков для подсчета количества поступающих в устройство данных. Первый счетчик считает только те значения, которыепопадают в первую зону, второй считаетзначения, относящиеся к двум первым зонам, третий накапливает количество эле5 ментов, имеющих значения, ограниченныедиапазоном первой, второй и третьей зон ит,д, После обработки всей фильтруемой последовательности счетчики первого каскада будут содержать числа, показывающие10 сколько раз во входной последовательности встречались значения меньшие, чемграницы зон. Поскольку значение Х соответствует рангу в том случае, если в последовательности имеется г - 1 меньших или15 равных ему значений (по определению ранга), то, следовательно, номер счетчика, содержащего первое превышающее рангчисло, однозначно определяет зону, в которой следует искать Х,20 Для уточнения значения Хг каждая зонаразделяется на й участков во втором каскаде. Счетчики второго каскада работают впроцессе загрузки параллельно со счетчиками первого каскада. Распределение участ 25 ков диапазона между счетчиками однойэоны аналогично распределению в первомкаскаде, т.е, первый счетчик считает количество значений в первом участке диапазона,второй в первом и втором, третий - в пер 30 вом, втором и третьем и т.д. Счетчики накапливают количество элементов, значениякоторых лежат в пределах, ограниченныхснизу началом зоны, а сверху - концом своего участка в этой зоне. Такое разделение35 диапазона значений между счетчиками второго каскада может потребовать одновременно изменять содержимое не более чем уЙ - 1 счетчиков одной зоны, которые должныбыть реализованы аппаратно. Содержимое40 всех счетчиков второго каскада сохраняетсяв йблоках памяти (в первом блоке первыйсчетчик, во втором второй и т,д,). Номерзоны, к которой относится обрабатываемоезначение, определяет при этом ячейку памя 45 ти в каждом иэ блоков. Счетчики первойэоны лежат в первых ячейках блоков, счетчики второй зоны во вторых, третьей - втретьих и т.д.В третьем каскаде каждый из участков50 второго каскада разбивается еще на йравных частей. Работа третьего каскадане отличается от работы второго. Отличиетретьего каскада от второго заключаетсятолько в емкости каждого из й - 1 блоков55 памяти, которая равна полному числу участков (й й). Разбиение всего диапазона значений продолжается до тех пор, пока небудет обеспечена необходимая точностьвычисления значения Хг, соответствующегорангу. Для минимизации аппаратуры иудобства работы с двоичными значениями необходимо количество зон (участков, частей) выбирать крайным 2, В частности, для И=4 два старших разряда числа будут определять номер зоны, следующие: два - номер участка в зоне, еще два - часть участка и т,д.На втором этапе работы устройства, при определении значения Хг, соответствующего заданному рангу, производится одновременное сравнение содержимого счетчиков первого каскада с величиной ранга. Если к первых счетчиков содержит число элементов, меньшее чем ранг, а (к+1)-й счетчик - большее или равное рангу, это указывает, что Хг находится в зоне к+1, а код этой зоны определяет значение старших разрядов результата.Далее производится анализ счетчиков второго каскада для выбранной зоны 1+1.Поскольку эти счетчики указывают количество значений, попавших на различныеучастки (ф+ 1)-й зоны, для сравнения с величиной ранга их содержимое должно быть предварительно увеличино на число элементов во всех предыдущих (1-зонах или, что то же самое, из ранга необходимо вычесть это число, Число элементов в первых к зонах показывает счетчик К первого каскада. По итогам сравнения счетчиков второго каскада с уменьшенным значением ранга формируется номер участка для поиска Хг и, соответственно, следующая группа разрядов результата. В последующих каскадах процесс формирования результата идентичен указанному.В отличие от процесса накопления данных, когда счетчики всех каскадов работают параллельно, процесс извлечения результата - последовательный. Время поиска Хг определяется задержками в каскадах и их числом, .Рассмотрим работу устройства по схеме при конкретной реализации для к = В и а 1 же а 2= аз= а 4= 2.При накоплении гистограммы в первом счетчике 14 вычислительного блока 1 подсчитывается число элементов, имеющих коды 0 - 63, во втором - коды 0 - 127, в третьем - коды 0 - 191. Блоки памяти блока 2 имеют по четыре ячейки. В первом блоке 24 памяти подсчитывается число элементов, имеющих коды р 1+ Л 1, во втором - рг+ Л 1, в третьем - рз+ Л 1 (р 1 жв 0-15, рг= 0-31, рз= 0-47, рз= 0-47, Л 1= 0,64, 128, 192. Блоки памяти блока 2 имеют по 16 ячеек. В первом блоке 24 памяти блока 2 подсчитывается число элементов, имеющих коды г 1+ Ьг, во ВтОрОМ Г 2+ да, В трЕтЬЕМ ГЗ+ Й (Г 1 жв 0-3; г 2= 0-7; гз=О - 11; Лг =16; (=0,15), Блоки памя 30 35 40 45 50 5 10 15 20 25 ти блока 2 з имеют по 64 ячейки. В первом блоке 24 блока 2 з накапливается число элементов с кодами й, во втором - 9 г+ й, в третьем - 9 з+ й (92 сж 0,1; 9 з= = 0,12;й =.4 ь (=0,63), Таким образом, весь диапазон входного сигнала, составляющий 0 - 255, разбивается на четыре части в первом каскаде и во втором, третьем, четвертом каскадах, каждая часть предыдущего каскада разбивается еще на четыре части, что дает возможность анализировать 256 градаций входного сигнала.Сказанное можно записать в виде:Я = о ) - содержимое оервого( =осчетчика 14.Содержимое блоков 24 памяти блока 2 рав- но 64 вв 5 б 4 В 6 И 4 415,(о,)е, п(Ц 5 (б(Ц 5 (о 1( . (Ц,рб.О,Ь. 1 64 К 1=б 4 К 1640,Содержимое блоков 24 памяти блока 22 равно б(143 б(34 б(345,ф(Ц 52(Р) (Ц 5(ф(1(г (Ъ "О,Ю. 16(Ь 1 щЮ 1б(3 Содержание блоков 24 памяти блока 2 з равноЯ 1"(у) =и (4 у); Яг" (у) =п (4 у)+ + п(4 у+1);Яз (у) = и (4 у)+ п(4 у+1)+ п(4 у+2)Рассмотрим числовой пример. Пусть размерность маски равна 4 х 4=16 и на вход устройства поступает некоторая последовательность из 16-ти элементов, например 5, 8, 20, 40, 130, 131, 140, 150, 180, 18., 182,183, 201, 205, 205;.240 (они расположены в порядке возрастания, хотя поступают в произвольном порядке) и г= 6. Тогда искомый элемент Хг=131. Для блока 1 имеет Я 1=4; Я 2=4; Яз=12; Я 2гЯз . На выходе 18 результата блока 1 код "2". На входы узлов сравнения с вычитателя поступает код г- Я 2=2; Я 1=3; Яг=4; Яз=4; г-ЯгЯ 1, поэтому на выходе приоритетного шифратора блока 2 код О. На входы узлов сравненияблока 22 поступает код г - Я 2 - 0=2, Я 1"= 2; . Я 2"=2; Яз"=2, г - Я 2-0Я 1", поэтому на выходе приоритетного шифратора блока 22 код О. На входы узлов сравнения блока 2 з поступает код г - Я 2-0 - 0=2; Я 1 =О; Яг =-0; Яз"=1; г - Я 2=2Яз ", поэтому на выходе приоритетного шифратора блока 2 з код 3. Окончательный результат, поступающий на выход 8, равен 203 в=1311 оФормула изобретения Устройство ранговой фильтрации, содержащее вычислительный блок и блок накопления гистрограммы, причем вычислительный блок содержит дешифратор, группу реверсивных счетчиков, мультиплексор, группу узлов сравнения,. две группы элементов И, группу элементов ИЛИ, приоритетный шифратор и элемент НЕ, при этом 91 старших разрядов информационного входа устройства подключены к входам дешифратора вычислительного блока, 1-й выход которого подключен к Нму входу 1-го элемента ИЛИ, группы 2=2,2- 1, 1=1,21 - 1), первый выход дешифратора подключен к первому входу 1-го элемента ИЛИ группы, первым входам первых элементов И первой и второй группы, выход 1-го элемента ИЛИ группы подключен к первым входам 1-х элементов И первой и второй групп, вторые входы элементов И первой группы соединены с входом элемента НЕ и с входом знака приращения устройства, выход элемента НЕ подключен к вторым входам элементов И второй группы, выходы Я-х (Я=1,21 - 1) элементов И первой и второй групп подключены соответственно к суммирующему и вычитающему входам Я-го реверсивного счетчика группы, выход которого подключен к Я-му информационному входу мультиплексора и первому входу Я-го узла сравнения группы, выход "Больше" которого подключен к Я-му входу приоритетного шифратора, выход которого подключен к управляющему входу мультиплексора, выход мультиплексора вычислительного блока является первым управляющим выходом вычислительного блока, вторые входы узлов сравнения группы подключены к входу критерия ранга устройства, а блок накопления гистограммы содержит первый мультиплексор, дешифратор, группу блоков памяти, группу элементов ИЛИ и первый реверсивнцй счетчик, причем первый информационный вход первого мультиплексора подключен к старшим разрядам информационного входа устройства, управляющий вход первого мультиплексора соединен с первцми входами элементов ИЛИ группы и с входом признака конца маски устройства, входы дешифратора соединены с информационным входом устройства, н-йвыход дешифратора го=1, 2 т, ат - число входов дешифратора, равное числу разрядов результата) подключен к второму входу и-го элемента ИЛИ группы, выход которого подключен к входу разрешения обращения и-го блока памяти группы, выход первого мультиплексора подключен к адресным входам блоков памяти группы, входы управления считыванием-записью которых соединены с входом управления считыванием-записью устройства, информационный вцход первого реверсивного счетчика подключен к информационному входу первого блока памяти группы, вход задания направления счета первого реверсивного счетчика соединен с входом знака приращения устройства, выход приоритетного шифратора вычислительного блока является выходом результата вычислительного блока и соединен с вторым информационным входом первого мультиплексора блока накопления гистограммы, о т л и ч а ю щ е е с я тем, что, 25 с целью упрощения устройства и увеличения быстродействия при получении результата из накопленной гистограммы, в него введены р - 2 блоков накопления гистограммы (2рК 1 - разрядность фильтрации, р - полное число блоков устройства), причем информационный вход устройства соединен с информационным входом т-го блока накопления гистограммы (1=2,р - 1), первый управляющий вход которого соединен с входом признака конца маски устройства, второй управляющий вход с-го блока накопления гистограммы соединен с входом управления считыванием -записью устройства, третий управляющий вход т-го блока 40 накопления гистограммы соединен с входом знака приращения устройства, четвертый и пятый управляющие входы т-го блока накопления гистограммы соединены с первым и вторым управляющим выходами (1-1)- го блока накопления гистрограммы, вход результата т-го блока накопления гистограммы соединен с выходом результата (т)- го блока накопления гистограммы, в о-й 50блок накопления гистограммы (о=1, р) введены 211-2 реверсивных счетчиков (ау - число разрядов результата, определяемых ц-м блоком накопления гистограммы), вычитательвторой мультиплексор, группа 2 - 1 55 узлов сравнения, приоритетный шифратор,причем первый управляющий вход 1-го блока накопления гистограммы соединен ступравляющим входом первого мульти-.плексора и с первыми входами элементов ИЛИ группы, Х-й выходдешифратора соеди 1661794нен с (Х+1 г-м входом У.го элемента ИЛИ группы (Х=т 12 е - 1; у=хт 1, 2 в - 1), ннформационный выход 1-го реверсивного счетчика (1=2, 2-1) соединен с информационным входом 1-го блока памяти группы, выход Е-го5 блока памяти группы 2=1, 2(-1) соединен с информационным входом Е-го реверсивного счетчика, с Е-м информационным входом второго мультиплексора и первым входом 2-го узла сравнения группы, выход пбольше"которого соединен с Е-м входом приоритетного шифратора, выход которого соединен с управляющим входом второго мультиплексора, выход приоритетного 1 Б шифратора и вход результата о-го блока накопления гистограммы является выходом результата о-го блока накопления гистограммы, выход мультиплексора вычислительного бло- . ка и вход критерия ранга устройства соедине О ны соответственно с первым и вторым входами вычитателя первого блока накопления гистограммы, второй управляющий вход -го блока накопления гистограммы соединен с входами управления считыванием-записью блоков памяти группы, третий управляющий вход 1-го блока накопления гистограммы соединен с входами задания направления счета всех реверсивных счетчиков, четвертый и пятый управляющие входы т-го блока накопления гистограммы соединены с первым и вторым входами вычитателя, выход которого подключен к вторым входам узлов сравнения группы и является первым управляющим выходом блока накопления гистограммы, выход второго мультиплексора является вторым управляющим выходом блока накопления гистограммы, выход результата последнего блока накопления гистограммы является выходом результата устройства,1661794 Составитель М, ЛогачеваТехред М,Моргентал Корректор Н, Король Редактор А. Коз оизводственно-издател ьский комбинат "Патент", г. Ужгород, ул. Гагарина,Заказ 2126 Тираж 412 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Раушская наб., 4/5