Устройство для ранговой фильтрации с произвольной формой окна

(5)5 ОПИСАНИЕ ИЗОБРЕТК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ АН ГО ВОЙ Ф ИЛ Ь.ОЙ ФОРМОЙ ОК.(57) Изобретение относи ной технике и может быть высокоскоростной обра пример при обработке и изобретения - повышен и Устройство содержит ма х М х Р блоков 1 обраб максимальный размер ок разрядность входных дан Р-й блоки 2 постоянной и М-ю .группы блоков 3 б сдвигающий регистр 4, 3 ГОСУДАРСТВЕ)ВЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР. (21) 4809369/24 (22) 04.04.90 (46) 15,04.92. Бюл. М 14 (71) Ленинградский институт точной механики и оптики (72) Ю.Ф.Романов, А,Ю.Тропченко и К.М.Юсупов (53) 681.325 (088.8) (56) Мозта 1 ач 1 Н., Мц 19 аоп 1 аг й. Разт п)еб 1 ап: т 1 тег 1 п 9 апб веб 1 ап-Ьазеб .йгез 1)о б п 9 из 1 пд а р 1 реИпеб 1 п)аце ргосеззог. - 5 й Апца пс. Р)опех. Соп 1., Соп)рцэр. апб Соп)топ., Зсойзбае, АггМагс) 26-28, 1986, Соп 1. Ргос., р. 532-536.Кучеренко КЛ. и Никитин А.В. О реализации взвешенной медианной фильтрации сигналов в реальном масштабе времени. Методы и микроэлектронные средства цифрового преобразования и обработки сигналов. - Тезисы докладов конференции; Т. 2. Рига, 1989, с. 43-45. тся к вычислитель использовано при ботке данных, назображений, Цель е быстродействия. трицу размером М отки, где М х М - на фильтрации Р ных, с первого по амяти, с первой по ферной памяти и ил.вым входом БО, а вход - с первым входом сумматора, второй вход сумматора соединен с пятым входом БО; выход сумматора соединен с первым. входом компаратора и третьим входом БО, второй вход компарато 40 ра соединен с третьим выходом БО, а выход компаратора - с .первым входом схемы И,второй вход которой соединен с четвертым входом БО, выход схемы И соединен с вторым выходом БО и с входом управления трехстабильного формирователя, вход трехстабильного формирователя соединен свторым входом БО, а выход-.с первым выходом БО. 50 Недостатком данного устройства явля ется относительно невысокое быстродействие, поскольку время определения элемента в пропорционально 3.Цель изобретения - повышение. быстродействия,Изобретение относится к вычислительной технике и может быть использовано привысокоскоростной обработке данных, например при обработке изображений,Известно устройство для выполнения 5медианной фильтрации, позволяющее формировать произвольную форму окна. Медианная фильтрация являетСя частнымслучаем ранговой фильтрации и заключается в поиске элемента в ранга й = (5+ 1)/2, 10где Я - число элементов в окне фильтрации(Я - нечетное). Указанное устройство содержит один конвейерный процессор и четыремодуля видеопамяти.Недостатком известного устройства является низкое быстродействие, пропорциональное (Я(Я - 1)/8+ Я).Наиболее близким по технической сущности и достигаемому результату к предлагаемому является устройство взвешенной 20медианной фильтрации. При взвешенноймедианной фильтрации произвольная форма обеспечивается бинарной матрицей ве-.совых коэффициентов, единичные битыкоторой определяют форму окна. 25Устройство содержит схему сортировкии Я блоков обработки (БО), причем БО включает преобразователь кода, сумматор, компаратор, схему И и трехстабильныйформирователь, каждая пара выходов схемы сортировки соединена с первым и вторым входами БО, третьи входы всех БОсоединены с входом ранга, а первые выходы- с выходом результата устройства, второйи третий выходы -го БО соединены с четвертым и пятым входами(+1)-го БО ( = 1,- 1),причем четвертый и пятый. входы первогоБО соединены с линией логического нуля,вход преобразователя кода соединен с перПоставленная цель достигается ем, что в устройство для ранговой фильтрации с производной формой окна, содержащее матрицу размером М х М блоков обработки, где М х М - максимальный размер окна фильтрации, введены с (М + 1)-го по М -й столбцы и с(М+ 1)-й по Р-ю строки матрицы блоковобработки,где Р- разрядность входных данных, с первого по Р-й блоки постоянной памяти, с первой по М-ю группы блоков буферной памяти и сдвигающий регистр, причем вход данных устройства подключен к первому информационному входу блока обработки первой строки первого столбца матрицы блоков обработки и к информационному входу сдвигающего регистра, вход значения ранга и вход нулевого потенциала устройства подключены соответственно к второму и третьему информационным входам блока обработки первого столбца первой строки матрицы, первый, второй и третий выходы блока обработки а-й строки Ь-го столбца матрицы блоков обработки (где аР, Ь - 1М) подключены соответственно к первому, второму и третьему информационным входам блока обработки а-й строки (Ь+ 1)-го столбца матрицы блоков обработки, выход с-го блока буферной памяти (где с - 1.Р - 1) первой группы подключен к первому информационному входу блока обработки (с+ 1)-й строки первого столбца матрицы блоков обработки, первый выход блока обработки -й строки О + 1)-го столбца матрицы (где- 1Р, -М, 2 М,., (М - 1)М блоков обработки подключен к информационному входу 1-го блока буферной памяти О/М + 1)-й группы, выход которого подключен к первому информационному входу блока обработки -й строки О + 1)-го столбца матрицы блоков обработки, второй и третий выходы блока обработки а-й строки О +.Ь)-го столбца матрицы блоков обработки . подключены соответственно к второму и третьему информационным входам блока обработки а-й строки О+ Ь+ 1)-го столбца матрицы блоков обработки, первый и третий выходы блока обработки б-й строки (где б - 1 Р) М -го столбца матрицы бло 2ков обработки подключены соответственно к информационному входу б-го блока буферной памяти первой группы и к первому адресному входу б-го блока постоянной памяти, второй выход блока обработки б-й строки М -го столбца матрицы блока обра 2ботки подключен к второму адресному входу б-го блока постоянной памяти и к второму информационному входу блока обработки (б + 1)-й строки первого столбца матрицы блоков обработки, выход б-го блока постоянной памяти подключен к третьему информационному входу блока обработки (д+ 1)-й строки первого столбца матрицы блоков обработки, второй и третий выходы блока обработки М -го столбца Р-й строкигматрицы блоков обработки подключены со ответственно к первому и второму адресным входам Р-го блока постоянной памяти, выход которого подключен к выходу устройства, выход синхронизации которого подключен к входам синхронизации всех 10 блоков обработки матрицы блоков обработки и к входам синхронизации блоков буферной, памяти всех групп, и-й выход сдвигающего регистра (где и -1М ) подключен к четвертым информационным вхо дам блоков обработки п-го столбца матрицы блоков обработки, вход начальной установки устройства подключен к входу синхронизации сдвигающего регистра, причем каждый блок обработки содержит пять ре гистров, узел сравнения, арифметико-логический узел и элемент И, и ри этом в каждом блоке обработки первый, второй, третий и четвертый информационные входы блока обработки подключены соответственно к.25 информационному входу первого регистра, к первому информационному входу арифметико-логического узла, к информационному входу второго регистра и к первому входу элемента И, выход которого подключен к 30 второму информационному входу арифметико-логического узла, выход которого подключен к информационному входу третьего регистра, выход которого подключен к информационному входу четвертого регистра, 35 выход первого регистра подключен к первому выходу блока обработки и к первому входу узла сравнения; выход второго регистра подключен к информационному входу пятого регистра, к входу кода операции арифме тико-логического узла и к второму входу узла сравнения, выход которого подключен к второму входу элемента И, выход четвертого и пятого регистров подключены соответственно к второму и третьему выходам 45 блока обработки, вход синхронизации которого подключен к входамзаписи-считывания регистров с первого по пятый, причем каждый блок буферной памяти содержит узел оперативной памяти и счетчик, при 50 этом в каждом блоке буферной памяти информационный вход блока буферной памяти подключен к информационному входу узла оперативной памяти, выход которого подключен к выходу блока буферной памя ти, вход синхронизации которого подкаючен к входу записи-считывания узла оперативной памяти и к счетному входу счетчика, информационный выход которого подключен к адресному входу узла оперативной памяти,Повышение быстродействия предлагаемого устройства ранговой фильтрации в 8 раз (ЯМ ) по сравнению с известным до 2стигается за счет использования М х Р блоков обработки, с первого по Р-й блоки постоянной памяти, с первой по М-ю группы блоков буферной памяти и сдвигающего ре.гистра, соединенных соответствующим об.разом, что обусловлено использованием нового алгоритма определения элемента изображения с заданным рангом, который обесйечивает одновременно формирование гистограммы и поиск результата.Устройство ранговой фильтрации с и роизвольной формой окна (фиг, 1) содержи 1 матрицу размером М х М х Р блоков 1 обработки, где М х М - максимальный размер окна фильтрации, Р - разрядность входных данных, с первого по Р-й блоки 2 постоян ной памяти, с первой по М-к 1 группы блоков 3 буферной памяти, сдвигающий регистр 4, При этом каждый блок 1 обработки (фиг. 2 содержит пять регистров 5, узел 6 сравне.ния, арифметико-логический узел 7 и элемент И 8, Блок 3 буферной памяти (Фиг. 3) содержит узел 9 оперативной памяти и счетчик 10,Вход 11 данных устройства подключен к первому информационному входу 12 блока 1 обработки первой строки первого столбца матрицы блоков обработки и к информационному входу сдвигающего регистра 4. Вход 13 значения ранга и вход 14 нулевого потенциала устройства подключены соответственно к второму 15 и третьему 16 информационным входам блока 1 обработки первого столбца первой строки матрицы, Первый 17, второй 16 и третий 19 выходы блока 1 обработки а-й строки Ь-го столбца матрицы блоков обработки (где а - 1,Р, Ь,. М) подключены соответственно к первому 12, второму 15 и третьему 16 информационным входам блока 1 обработки а-й строки (Ь + 1)-го столбца матрицы блоков обработки, Выход 20 с-го блока 3 буферной памяти (где сР) первой группы подключен к первому информационному входу 12 блока 1 обработки (с + 1)-й строки первого столбца матрицы блоков обработки, Первый выход 17 блока 1 обработки -й строки )-го столбца где - 1;.,Р, ) - М, 2 М(М - 1)ЬЦ матрицы блоков обработки подключен к информационному входу 21 1- го блока 3 буферной памяти Д/М+ 1)-й группы, выход 20 которого подключен к первому информационному входу 12 блока 1 обработки 3-1 строки Я + 1)-го столбца матрицы блока обработки. Второй 18 и третий 19 выходы блока 1 обработки а-й строки 0 + Ь)-го столбца матрицы блоков обработки подключены соответственно к второму 15 и третьему 16 информационным входам блока 1 обработки а-й строки 0 + Ь + 1)-го столбца матрицы блоков обработки. Первый 17 и третий 19 выходы блока 1 обработки б-й строки (где бР) М 2-го столбца матрицы блоков обработки подключены соответствейно к информационному входу 21 б-го блока 3 буферной памяти первой группы и к первому адресному входу б-го блока 2 постоянной памяти, Второй выход 18 блока 1 обработки б-й строки М -го столбца матрицы блока обработки подключен к второму адресному входу б-го блока 2 постоянной памяти и к второму информационному входу 15 блока 1 обработки (б + 1)-й строки первого столбца матрицы блоков обработки, Выход б-го блока 2 постоянной памяти подключен к третьему информационному входу 16 блока 1 обработки (б + 1)-й строки первого столбца матрицы блоков обработки, Второй 18 и третий 19 выходы блока 1 обработки Р-й строки М -го столбца матрицы блоков обработки подключены соответственно к первому и второму адресным входам Р-го блока 2 постоянной памяти, выход которого подключен к выходу 22 устройства. Вход 23 синхронизации устройства подключен к входам 24 синхронизации всех блоков 1 обработки матрицы блоков обработки и к входам 25 синхронизации блоков 3 буферной памяти всех групп. и-й выход сдвигающего регистра 4 (где пУ) подключен к четвертым информационным входам 26 блоков 1 обработки и-го столбца матрицы блоков обработки. Вход 27 начальной установки устройства подключен к входу синхронизации сдвигающего регистра 4.Первый 12, второй 15, третий 16 и четвертый 26 информационные входы блока 1 обработки подключены соответственно к информационному входу первого регистра 5, первому информационному входу арифметико-логического узла 7, информационному входу второго регистра 5 и первому входу элемента И 8, Выход последнего подключен к второму информационному входу арифметико-логического узла 7, выход которого подключен к информационному входу третьего регистра 5, выход которого подключен к информационному входу четвертого регистра.5, Выход первого регистра 5 подключен к первому выходу 17 блока 1 обработки и к первому входу узла 6 сравнения, Выход второго регистра 5 подключен к информационному входу пятого регистоа 5, входу кода операции арифмерико-логического узла 7 и второму входу узла 6 сравнения, выход которого подключен к второмувходу элемента И 8. Выходы четвертого и.пятого регистров 5 подключены соответственно к второму 18 и к третьему 19 выходам. 5 блока 1 обработки. Вход 24 синхронизации блока 1 обработки подключен к входамзаписи-считывания первого-пятого регистров 5,Информационный вход 21 блока 3 бу,10 ферной памяти подключен к информационному входу узла 9 оперативной памяти,выход которого подключен к выходу 20 блока 3 буферной памяти. Вход 25 синхронизации блока 3 буферной памяти подключен к15 входу записи-считывания узла 9 оперативной памяти и счетному входу счетчика 10,Информационный выход последнего подключен к адресному входу узла 9 оперативной памяти,20 В качестве элементов устройства используются микросхемы, выпускаемые промышленностью. Так, например, в качестверегистров можно использовать микросхемуК 155 ИР 13 арифметико-логического узла25 (К 155 ИПЗ). узла сравнения (К 555 СП 1), счетчика (К 155 ИЕ 7), узла оперативной памяти(132 РУ 8), элемента И (К 155 ЛИ 1).Алгоритм поиска элемента 1 я с заданным рангом В в окне фильтрации размером30 М х М элементов, являющийся основой работы устройства, имеет следующий вид(форма окна задается вектором Е);начало алгоритма:Н 1; -Й,1(1:=О, б 1:=0(1=1,Р) (1)35 для 1 = 1 Р цикл;для 1=1,М 2 цикл;если се: = О, то (1; = б 1 бгбзби О); (2)если 01 у 11) и (Е 1 = 1), то (Я: = Я у + 1),иначе(Я: = Я;, иначе(Ь: = б 1 б 2.би 1);40 если О 1 л 11) и (Е 1 = 1), то (Я: = Я - 1),иначе(31: =Зконец по);если 31О, то (б 1: = 1, Ь+ 1: = 0) (3)иначе(б 1: =0; кн 1: =1):45 Ян: = Ь;конец по 1;1 я: = 1 р, (4)конец алгоритма,Где 01 - )-й пиксел окна;50 б - бинарная переменная, определяющая 1-й разряд результата;А д В - условие совпадения 1 старшихразрядов чисел А и В.Перед началом работы устройства про 55 изводится начальная установка, заключаю-.щаяся в загрузке коэффициентов Е 1 всдвигающий регистр 4. Коэффициенты Е 1 являются однобитными операндами, поэтомуна информационный вход сдвигающего регистра 4 достаточно подать, например, старший разряд операнда с входа 11 данных Блок 3 буферной памяти работает слеустройства. На вход 27 начальной установки дующим образом,устройства поступают синхроимпульсы, по На информационный вход 21 блока 3переднему фронту которых происходит за- буферной памяти поступает элемент изопись коэффициентов в сдвигающий регистр 5 бражения, значение которого записывается, После загрузки коэффициентов Г 1 устрой- в узел 9 оперативной памяти по низкомуство переводится в основной режим работы, уровню синхроимпульса, поступающего навход 25 синхронизации. При этом адрес, поЭлементы изображения Ог поступают которому происходит запись, определяетсяна вход 11 данных в такт с синхроимпульса содержимым счетчика 10 измми на входе 23 ст ойства.к, изменяющемсяпо заднему фронту синхроимпульса. Длии мРассмотрим формирование первого тельность задержки узла 9 оперативнойро ежуточного результата, начиная с мо- мяти устанавливается коэффициентомтивно памента ввода элементов(М)-й строки кадра пересчета счетчика 10,иэображения. 15 После М тактов число с третьего выходаОчередной элемент изображения запи-. 19 и старший разряд числа с второго выходасывается в первый регистр 5 блока 1 обра блока 1 обработки первой строки М 2 столботки первого столбца первой строки бца матрицы блоков обработки поступаютматрицы блоков обработки по переднемунавходпервогоблока 2 постоянной памяти.фронту синхроимпульса, поступающего на 20 Прошивка блока 2 постоянновхо 24вход синхронизации блока 1 обработки.- ществляется в соответствии с операциейОдновременно происходит запись нуля во алгоритма. Необходимо учесть, что пере.второй регистр 5. На второй вход 15 ариф- менная Ь и(Р)-й старший разряд переменметико-логического узла блока 1 обработки ной 1 г имеют одинаковые значения; Такилгпоступает отрицательное значение ранга с 25 образом, в 1-м блоке 2 постоянно (яннои памятигд 3 значения ранга устройства. Опера- =1Р) корректируется старший(Р -+ 1)-йция 1 алгоритма. В узле 6 сравнения срав- разряд и устанавливается (Р - )ниваютт ( - )-и разрядю ся старшие разряды данных, результата гг с учетом значения знаковогозаписанных в первый и второй регистры 5; (старшего) разряда Яь На выходе Р-го блокасли эти числа равны, то на выходе узла 6 30 2 постоянной памяти получим значение элесравнения появляется единица, иначе - мента с заданным рангом В.ноль. Однобитный операнд с выхода узла 6 Эффективность предлагаемого устройсравнения поступает на второй вход эле-ства заключается в повышении быстродеймента И 8, на первый вход которого посту- ствия. В предлагаемом уст йффициент 1 с первого выхода 35 определения следующего результата необсдвигающего регистра 4. Результат с выхо- ходим один такт независимо от размера окда элемента И 8 поступает на второй вход на фильтрации, в то время как в известномарифметико-логического узла 7. Код опера- устройстве требуется 3 тактов,цииарифметико-логическогоузла 7 опреде-Формула из об ретени яляется Р-м старшим разрядом числа во 40 Устройство для ранговой фильтрации свтором регистре 5: если Р-й разряд равен произвольной формой:окна, содержащее" ", то выполняется операция суммирова-. матрицу размером М х М влоков об бония иниче - вычитания(операция 2 алгорит- где М х М - максимальный размер окнама), Результат. с выхода фильтрации, отл и ча ю щееся тем, что,арифметико-логическогоузла 7 записывает с целью увеличения быстродействия, онося в первый регистр 5 по заднему фронту содержит с(М+1)-го по М -й столбцы.и с(Мсинхроимпульса. В четвертый регистр 5 за- + 1)-й по Р-ю строки матрицы блоков обрапись данных, поступающих с выхода треть-,ботки, где Р - разрядность входных данных,его регистра 5, происходит по переднему с первого по Р-й блоки постоянной памяти,фронту синхроимпульса, Работа остальных 50 с первой по М-ю группы блоков буфернойблоков 1 обработки матрицы блоков обра- памяти и сдвигающий регистр, причем входботки аналогична работе блока 1 обработки данных устройства подключен к первому инпервого столбца первой строки этой матри" формационному входу блока обработки перцы. Блоки 3 буферной памяти с второй по: вой строки первого столбца матрицы блоковМ-й группы обеспечиваютзадержкуданных 55 обработки и к информационном оному входу( ) тактов (где- число. столбцов в сдвигающего регистра, вход значения рангакадре изображения), а блоки буферной па- и вход нулевого потенциала устройства подмяти первой группы - на М тактов.,ключены соответственно к второму и третьему информационным входам блокаобработки первого .столбца первой строки=1 Р) первой группы подключен к первому информационному входу блока обработки (с + 1)-й строки первого столбца а-й строки О + Ь + 1)го столбца матрицы 25 блоков обработки, первый и третий выходы блока обработки б-й строки (где б -1 Р) М -го столбца матрицы блоков обработки подключены соответственно к информаци 30 35 матрицы, первый, второй и третий выходы блока обработки а-й строки Ь-го столбца матрицы блоковобработки(где а" 1Р, Ь" - 1М - 1) подключены соответственно к первому, второму и третьему информационным входам блока обработки а-й строки (Ь+ +1)-го столбца матрицы блоков обработки, выход с-го.блока буферной памяти (где с матрицы блоков обработки; первый выход блока обработки 1-й строки -го столбца матрицы (где 1 1,.,Р, 1 М; 2 М(М - 1)М блоков обработки подключен к информационному входу 1-го блока буферной памяти О/М + 1)1 группы, выход которого подключен к первому информационному входу блока обработки 1-й строки О + 1)-го столбца матрицы блоков обработки, второй и третий выходы блока обработки а-й строки О+ Ь)го столбца матрицы блоков обработки подключены соответственно к второму и третьему информационным входам блока обработки онному входу б-го блока буферной памяти первой группы и к первому адресному входу б-го блока постоянной памяти, второй выход блока обработки б-й строки Мг-го столбца матрицы блока. обработки подключен ко второму адресному входу б-го блока постоянной памяти и к второму информационному входу блока обработки (б + 1)й строки первого столбца матрицы блоков обработки, выход б-го блока постоянной памяти подключен к третьему информационному входу блока обработки (б+ 1)-й сроки первого столбца матрицы блоков обработки, второй и третий выходы блока.обработки М -го столбца Р-й строки матрицы блоков гобработки подключены соответственно к первому и второму адресным входам Р-го блока постоянной памяти, выход которого подключен к выходу устройства. вход синхронизации которого подключен к входам синхронизации всех блоков обработки мат 15 20 40 45 50 рицы блоков обработки и к входам синхронизации блоков буферной памяти всех. групп, и-й выход сдвигающего регистра (где п" 1,.,М ) подключен к четвертым инфоргмационным входам блоков обработки и-го столбца матрицы блоков обработки, вход начальной установки устройства подключен к входу синхронизации сдвигающего регистра, причем каждый блок обработки содержит пять регистров, узел сравнения, арифметико-логический узел и элемент И, при этом в каждом блоке обработки первый, второй, третий и четвертый информационные входы блока обработки подключены соответственно к информационному входу первого регистра, к первому информационному входу арифметико-логического узла. к информационному входу второго регистра и к первому входу элемента И, выход которого подключен к второму информационному входу арифметйко-логического узла, выход которого подключен к информационному входу третьего регистра, выход которого подключен к информационному входу четвертого регистра, выход первого регистра подключен к первому выходу блока обработки и к первому входу узла сравнения, выход второго регистра подключен к информационному входу пятого регистра, к входу кода операции арифметико-логического узла и к второму входу узла сравнения, выход которого подключен к второму входу элемента И, выходы четвертого и пятого регистров подключены соответственно к второму и к третьему выходам блока обработки, вход синхронизации которого подключен к входам записи-считывания регистров с первого по пятый, причем каждый блок буферной памяти содержит узел оперативной памяти и счетчик, при этом в каждом блоке буферной памяти информационный вход блока буферной памяти подключен к информационному входу узла оперативной памяти, выход которого подключен к выходу блока буферной памяти, вход синхронизации которого подключен к входу записи-считывания узла оперативной памяти.и к счетному входу счетчика, информационный выход которого подключен к адресному входу узла, оперативной памяти.1727137 Фиг Составитель К. ЮсуповРедактор М. Петрова Техред М.Моргентал Корректор Н. Ко Заказ 1280 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при 113035, Москва, Ж, Рауаская наб 4/5 ГКНТ СССР Производственно-издательский комбинат "Патент", г, Ужгород. ул.Гагарина, 101