Устройство для ранговой фильтрации с произвольной формой окна
СОЮЗ СО8ЕТСКИХ
СОЦИАЛИСТИЧ;СКИХ
РЕСПУБЛИК
I OtY+APCTBEI%bIA КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
И() ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
l Ь»
» (21) 4809369/24 (22) 04.04.90 (46) 15.04.92. Бюл. ¹ 14 (71) Ленинградский институт точной механики и. оптики (72) Ю.Ф.Романов, А,Ю.Тропченко и
К.M.Þñóïîâ (53) 681.325 (088.8) (56) Mostafavi H.. Mulgaonkar R. Fast аесИап
fllterlng and median-based thresholdlng
using à plpellned Image processor. — 5 th
AnuaI Int. Phonex. Conf., Comput. and
Common., Scottsldale, Ariz., March 26-28, 1986, Conf. Proc., р. 532-536. .Кучеренко К.П. и Никитин А.В. О реализации взвешенной медианной фильтрации сигналов в реальном масштабе времени.
Методы и микроэлектронные средства цифрового преобразования и обработки сигналов. —. Тезисы докладов конференции; Т. 2.
Рига, 1989, с. 43-45.... Ы,„, 1727137 À1
Устройство содержит матрицу размером M x M x P блоков 1 обработки, где M x M— максимальный размер окна фильтрации; P— разрядность входных данных, с первого по P-й блоки 2 постоянной памяти, с первой по М-ю-группы блоков 3 буферной памяти и сдвигающий регистр 4. 3 ил. 1727137 вым входом БО, а вход — с первым входом сумматора, второй вход сумматора соединен с пятым входом БО; выход сумматора соединен с первым. входом компаратора и третьим входом БО, второй вход компарато40 ра соединен с третьим выходом БО, а выход компаратора — с .первым входом схемы И, второй вход которой соединен с четвертым входом БО, выход схемы И соединен с вторым выходом БО и с входом управления трехстабильного формирователя, вход трехстабильного формирователя соединен с вторым входом БО, а выход-.с первым выходом БО. Недостатком данного устройства явля- 55 ется относительно невысокое быстродействие, поскольку время определения элемента !д пропорционально S. Цель изобретения — повышение. быстродействия. Изобретение относится к вычислительной технике и может быть использовано при высокоскоростной обработке данных, например при обработке изображений, Известно устройство для выполнения 5 медианной фильтрации, позволяющее формировать произвольную форму окна. Медианная фильтрация являетСя частным случаем ранговой фильтрации и заключается в поиске элемента tp ранга R =(S+ 1)/2, 10 где S — число элементов в окне фильтрации ($ — нечетное). Указанное устройство содержит один конвейерный процессор и четыре модуля видеопамяти. Недостатком известного устройства яв- 15 ляется низкое быстродействие, пропорциональное (S(S2 — 1)/8+ S). Наиболее близким по технической сущности и достигаемому результату к предлагаемому является устройство взвешенной 20 медианной фильтрации. При взвешенной медианной фильтрации произвольная форма обеспечивается бинарной матрицей ве-. совых коэффициентов, единичные биты которой определяют форму окна. 25 Устройство содержит схему сортировки и Sблоков обработки (БО),,причем БО включает преобразователь кода, сумматор, компаратор, схему И и трехстабильный формирователь, каждая пара выходов схе- 30 мы сортировки соединена с первым и вторым входами БО, третьи входы всех БО соединены с входом ранга, а первые выходы — с выходом результата устройства, второй и третий выходы i-ro БО соединены с четвер- 35 тым и пятым входами (i+ 1)-ro БО (i = 1, S — 1), причем четвертый и пятый. входы первого БО соединены с линией логического нуля. вход преобразователя кода соединен с перПоставленная цель достигается ем, что в устройство для ранговой фильтрации с производной формой окна, содержащее матрицу размером М х М блоков обработки, где М x M — максимальный размер окна фильтрации, введены с (M + 1)-ro no M -й столбцы и с (М + 1)-й по Р-ю строки матрицы блоковобработки,где Р- разрядность входных данных, с первого по P-й блоки постоянной памяти, с первой по М-ю группы блоков буферной памяти и сдвигающий регистр, причем вход данных устройства подключен к первому информационному входу блока обработки первой строки первого столбца матрицы блоков обработки и к информационному входу сдвигающего регистра, вход значения ранга и вход нулевого потенциала устройства подключены соответственно. к второму и третьему информационным входам блока обработки первого столбца первой строки матрицы, первый, второй и третий выходы блока обработки а-й строки Ь-го столбца матрицы блоков обработки (где а-1,...,P, Ь вЂ” 1,...,M-1) подключены соответственно к первому, второму и треть- . ему информационным входам блока обработки а-й строки (Ь+ 1)-го столбца матрицы блоков обработки, выход с-го блока буферной памяти (где с — 1,..., P— - 1) первой группы подключен к первому информационному входу блока обработки (с+ 1)-й строки первого столбца матрицы блоков обработки, первый выход блока обработки i-й строки (j + 1)-го столбца матрицы (где i— 1,...,,P, J-M, 2M,..., (М вЂ” 1)М) блоков обработки подключен к информационному входу j-го блока буферной памяти {j/M + 1)-й группы, выход которого подключен к первому информационному входу блока обработки i-й строки (j + 1)-ro столбца матрицы блоков обработки, второй и третий выходы блока обработки а-й строки (j +.Ь)-го столбца матрицы блоков обработки . подключены соответственно к второму и третьему информационным входам блока обработки а-й строки (j + b+ 1)-го столбца матрицы блоков обработки, первый и третий выходы блока обработки d-й строки (где d — 1,...,P-1) M -ro столбца матрицы бло2 ков обработки подключены соответственно к информационному входу б-го блока буферной памяти первой группы и к первому адресному входу d-ro блока постоянной памяти, второй выход блока обработки d-й строки М -ro столбца матрицы блока обра2 ботки подключен к второму адресному входу d-го блока постоянной памяти и к второму информационному входу блока обработки (d + 1)-й строки первого столбца матрицы блоков обработки, выход d-го блока постоянной памяти подключен к третье1727137 му информационному входу блока обработки (d+ 1)-й строки первого столбца матрицы блоков обработки, второй и третий выходы блока обработки М -го столбца P-й строки г матрицы блоков обработки подключены со- 5 ответственно к первому и второму адресным входам Р-го блока постоянной памяти, выход которого подключен к выходу устройства, выход синхронизации которого подключен к входам синхронизации всех 10 блоков обработки матрицы блоков обработки и к входам синхронизации блоков буферной, памяти всех групп, и-й выход сдвигающего регистра (где n - 11,...,М ) подключен к четвертым информационным вхо- 15 дам блоков обработки п-ro столбца матрицы блоков обработки, вход начальной установки устройства подключен к входу синхронизации сдвигающего регистра, причем каждый блок обработки содержит пять ре- 20 гистров, узел сравнения, арифметико-логический узел и элемент И, п ри этом в каждом блоке обработки первый, второй, третий и четвертый информационные входы блока обработки подключены соответственно к 25 информационному входу первого регистра, к первому информационному входу арифметико-логического узла, к информационному входу второго регистра и к первому входу элемента И, выход которого подключен к 30 второму информационному входу арифметико-логического узла, выход которого подключен к информационному входу третьего регистра, выход которого подключен к информационному входу четвертого регистра, 35 выход первого регистра подключен к первому выходу блока обработки и к первому входу узла сравнения; выход второго регистра подключен к информационному входу пятого регистра, к.входу кода операции арифме- 40 тико-логического узла и к второму входу узла сравнения, выход которого подключен к второму входу элемента И, выход четвертого и пятого регистров подключены соответственно к второму и третьему выходам 45 блока обработки, вход синхронизации которого подключен к входам записи-считывания регистров с первого по пятый, причем каждый блок буферной памяти содержит узел оперативной памяти и счетчик, при 50 этом в каждом блоке буферной памяти информационный вход блока буферной памяти подключен к информационному входу узла оперативной памяти, выход которого подключен к выходу блока буферной памя- 55 ти, вход синхронизации которого подключен к входу записи-считывания узла оперативной памяти и к счетному входу счетчика, информационный выход которого подключен к адресному входу узла оперативной памяти. Повышение быстродействия предлагаемого устройства ранговой фильтрации в S раз (S M ) по сравнению с известным до2 стигается за счет использования M x P блоков обработки, с первого no P-й блоки постоянной памяти, с первой по M-ю группы блоков буферной памяти и сдвигающего регистра, соединенных соответствующим образом, что обусловлено использованием нового алгоритма определения элемента изображения с заданным рангом, который Обесйечивает одновременно формирование гистограммы и поиск результата. Устройство ранговой фильтрации с и роизвольной формой окна (фиг. 1) содержит матрицу размером M х М х P блоков 1 обработки, где M x M — максимальный размер окна фильтрации, P — разрядность входных данных, с первого по P-й блоки 2 постоян. ной памяти, с первой по M-кт группы блоков 3 буферной памяти, сдвигающий регистр 4, При этом каждый блок 1 обработки (фиг. 21 содержит пять регистров 5. узел 6 сравнения, арифметико-логический узел 7 и элемент И 8. Блок 3 буферной памяти (фиг. 3) содержит узел 9 оперативной памяти и счетчик 10, Вход 11 данных устройства подключен к первому информационному входу 12 блока 1 обработки первой строки первого столбца матрицы блоков обработки и к информационному входу сдвигающего регистра 4. Вход 13 значения ранга и вход 14 нулевого потенциала устройства подключены соответственно к второму 15 и третьему 16 информационным входам блока 1 обработки первого столбца первой строки матрицы. Первый 17, второй 16 и третий 19 выходы блока 1 обработки а-й строки b-го столбца матрицы блоков обработки (где а — 1....,P, b1,. „M-1) подключены соответственно к первому 12, второму 15 и третьему 16 информационным входам блока 1 обработки а-й строки (Ь + 1)-го столбца матрицы блоков обработки, Выход 20 с-го блока 3 буферной памяти (где с-1,...,P-1} первой группы подключен к первому информационному входу 12 блока 1 обработки (с + 1)-й строки первого столбца матрицы блоков обработки, Первый выход 17 блока 1 обработки i-й строки j-го столбца (где! — 1;...,P, j — M, 2M,...,(M 1)М) матрицы блоков обработки подключен к информационному входу 21 iro блока 3 буферной памяти (j/М + 1)-й группы, выход 20 которого подключен к первому информационному входу 12 блока 1 обработки i-1 строки (l + 1)-го столбца матрицы блока обработки. Второй 18 и третий 19 вы1727137 ходы блока 1 обработки а-й строки (j + b)-го столбца матрицы блоков обработки подключены соответственно к второму 15 и третьему 16 информационным входам блока 1 обработки а-й строки O + Ь + 1)-го столбца матрицы блоков обработки. Первый 17 и третий 19 выходы блока 1 обработки d-й строки (где d-1,...,P-1) М2-го столбца матрицы блоков обработки подключены соответствейно к информационному входу 21 d-ro блока 3 буферной памяти первой группы и к первому адресному входу d-го блока 2 постоянной памяти. Второй выход 18 блока 1 обработки d-й строки М -го столбца матрицы блока обработки подключен к второму адресному входу d-го блока 2 постоянной памяти и к второму информационному входу 15 блока 1 обработки (б + 1)-й строки первого столбца матрицы блоков обработки. Выход d-го блока 2 постоянной памяти подключен к третьему информационному входу 16 блока 1 обработки (d + 1)-й строки первого столбца матрицы блоков обработки. Второй 18 и третий 19 выходы блока 1 обработки P-й строки M -ro столбца матрицы блоков обработки подключены соответственно к первому и второму адресным входам P-го блока 2 постоянной памяти, выход которого подключен к выходу 22 устройства. Вход 23 синхронизации устройства подключен к входам 24 синхронизации всех блоков 1 обработки матрицы блоков обработки и к входам 25 синхронизации блоков 3 буферной памяти всех групп. и-й выход сдвигающего регистра 4 (где п-1,...,У ) подключен к четвертым информационным входам 26 блоков 1 обработки и-го столбца матрицы блоков обработки. Вход 27 начальной установки устройства подключен к входу синхронизации сдвигающего регистра 4. Первый 12, второй 15, третий 16 и четвертый 26 информационные входы блока 1 обработки подключены соответственно к информационному входу первого регистра 5, первому информационному входу арифметико-логического узла 7, информационному входу второго регистра 5 и первому входу элемента И 8. Выход последнего подключен к второму информационному входу арифметико-логического узла 7, выход которого подключен к информационному входу третьего регистра 5, выход которого подключен к информационному входу четвертого регистра.5. Выход первого регистра 5 подключен к первому выходу 47 блока 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). Алгоритм поиска элемента IR с заданным рангом R в окне фильтрации размером 30 М х М элементов, являющийся основой работы устройства, имеет следующий вид (форма окна задается вектором Fj): начало алгоритма: Н1; -R,k1:=О, dt:=0(i=1,Р) (1) 35 для i = 1 Р цикл; для J = 1,М2 цикл; если kl. = О, то (Ii: = б1бгбз...би О); (2) если ((Df ó 1 ) и (Е = ff), то (Sf, = $ + 1). иначе (Sl. = $;)), иначе (fl. = d Id ...бь1 1); 40 если((Е)1 л I<) v(FI = ll), то($ . = St — 1), иначе($1: = S>)); конец по J; если$ < О,то(б . =1.Ь + :=О) (3) иначе (di: = О; ki+1: = 1); 45 $н-1: = $, конец по i; IR .= Ip, (4) конец алгоритма. Где Dl — j-й пиксел окна; 50 di — бинарная переменная, определяющая i-й разряд результата; А л  — условие совпадения I старших разрядов чисел А и В. Перед началом работы устройства про55 изводится начальная установка, заключаю-. щаяся в загрузке коэффициентов Ff в сдвигающий регистр 4. Коэффициенты Fi являются однобитными операндами, поэтому на информационный вход сдвигающего регистра 4 достаточно подать, например, стар1727137 1О р р д перанда с входа 11 данных Блок 3 буферной памяти работает слеустройства. На вход 27 начальной установки дующим образом, устройства поступают синхроимпульсы, по На информационный вход 21 блока 3 переднему фронту которых происходит за- буферной памяти поступает элемент изопись коэффициентов в сдвигающий регистр 5 бражения, значение которого записывается, После загрузки коэффициентов Ег устрой- в узел 9 оперативной памяти по низкому ство переводится в основной режим работы, уровню синхроимпульса, поступающего на вход 25 синхронизации. При этом адрес, по Элементы изображения Ог поступают которому происходит запись, определяется на вход 11 данных в такт с синхроимпульса- 10 содержимым счетчика 10 изм ми на входе 2 ст ойства. к, изменяющемся по заднему фронту синхроимпульса. Длии м Рассмотрим формирование первого тельность задержки узла 9 оперативной ро ежуточного результата, начиная с мо- мяти устанавливается коэффициентом тивно памента ввода элементов(М-1)-й строки кадра пересчета счетчика 10, иэображения. 15 После М тактов число с третьего выхода Очередной элемент изображения запи-. 19 и старший разряд числа с второго выхода сывается в первый регистр 5 блока 1 обра- 18блока 1 обработки первойстроки М2стол-. ботки первого столбца первой строки бца матрицы блоков обработки поступают матрицы блоков обработки по переднему навход первого блока2 постоянной памяти. фронту синхроимпульса, поступающего на 20 Прошивка блока 2 постоянно вхо 24 вход синхронизации блока 1 обработки.- ществляется в соответствии с операцией ? Одновременно происходит запись нуля во алгоритма. Необходимо учесть, что перевторой регистр 5. На второй вход 15 ариф- менная ki и (Р-I)-й старший разряд переменметико-логического узла блока 1 обработки ной h имеют одинаковы ; Такилг поступает отрицательное значение ранга с 25 образом, в i-м блоке 2 постоянно (! яннои памяти (, д 3 значения ранга устройства. Опера- = 1,...,Р) корректируется старший {P — i i 1)-гг ция 1 алгоритма. В узле 6 сравнения срав - разряд и устанавливается (P — !)нивают т (— )-и разряд ю ся старшие разряды данных, результата ii с учетом значения знакового записанных в первый и второй регистры 5; (старшего) разряда $ь На выходе P-го блока сли эти числа равны, то на выходе узла 6 30 2 постоянной памяти получим значение злесравнения появляется единица, иначе — мента с заданным рангом R. ноль. Однобитный операнд с выхода узла 6 Эффективность предлагаемого устройсравнения поступает на второй вход эле- ства заключается в повышении быстродеймента И 8, на первый вход которого посту- ствия. В предлагаемом уст и ффициент 1 с первого выхода 35 определения следующего результата необсдвигающего регистра 4. Результат с выхо- ходим один такт независимо от размера окда элемента И 8 поступает на второй вход на фильтрации, в то время как в известном арифметико-логического узла 7. Код опера- устройстве требуется S тактов. цииарифметико-логическогоузла7опреде- Ф о р мул а из о б рете н и я ляется P-м старшим разрядом числа во 40 Устройство для ранговой фильтрации с втором регистре 5: если P-й разряд равен произвольной формой окна, содержащее " ", то выполняется операция суммирова-. матрицу размером М х М влоков об бо ния ин иче — вычитания(операция 2 алгорит- где М х М вЂ” максимальный размер окна ма). Результат. с выхода фильтрации, о тл и ч а ю щ е е с я тем, что. арифметико-логическогоузла7записывает- 45 с целью увеличения быстродействия, оно ся в первый регистр 5 по заднему фронту содержит с(М+1)-го по М -й столбцы и c(M синхроимпульса. В четвертый регистр 5 за- + 1)-й по P-ю строки матрицы блоков о6рапись данных, поступающих с выхода треть- .ботки, где Р— разрядность входных данных, его регистра 5, происходит по переднему с первого по Р-й блоки постоянной памяти, фронту синхроимпульса. Работа остальных 50 с первой по М-ю группы блоков буферной блоков 1 обработки матрицы блоков обра- памяти и сдвигающий регистр, причем вход ботки аналогична работе блока 1 обработки данных устройства подключен к первому инпервого столбца первой строки этой матри- формационному входу блока обработки перцы. Блоки 3 буферной памяти с второй по: вой строки первого столбца матрицы блоков М-й группы обеспечиваютзадержкуданных 55 обработки и к информационном о ному входу () тактов (где — число. столбцов в сдвигающего регистра, вход значения ранга кадре изображения), а блоки буферной па- и вход нулевого потенциала устройства подмяти первой группы — на M тактов.. ключены соответственно к второму и третьему информационным входам блока обработки первого .столбца первой строки 1727137 12 матрицы, первый, второй и третий выходы блока обработки а-й строки Ь-го столбца матрицы блоковобработки(где а-1,...,P, Ь- 1,...,М вЂ” 1) подключены соответственно к первому,. второму и третьему информацион- 5 ным входам блока обработки а-й строки (Ь+ +1)-го столбца матрицы блоков обработки, выход с-го.блока буферной памяти (где с =1,...,P-1) первой группы подключен к первому информационному входу блока обра- 10 ботки (с + 1)-й строки первого столбца матрицы блоков обработки; первый выход блока обработки I-й строки J-го столбца матрицы (где I 1,.„,P, ) M; 2M,...,(M — 1)М) блоков обработки подключен к информаци- 15 онному входу I-ro блока буферной памяти 0/М + 1)-1 группы, выход которого подключен к первому информационному входу блока обработки 1-й строки Ц +.1)-го столбца матрицы блоков обработки, второй и третий 20 выходы блока обработки а-й строки Ц+ Ь)го столбца матрицы блоков обработки подключены соответственно к второму и третьему информационным входам блока обработки а-й строки Ц + Ь + 1)-го столбца матрицы 25 блоков обработки, первый и третий выходы блока обработки d-й строки (где d-1,...,,P-1) M -го столбца матрицы блоков обработки подключены соответственно к информационному входу б -го блока буферной памяти первой группы и к первому адресному входу d-го блока постоянной памяти, второй выход блока обработки d-й строки М --го столг бца матрицы блока. обработки подключен ко второму адресному входу б-го блока постоянной памяти и к второму информационному входу блока обработки (d + 1)-й строки первого столбца матрицы блоков обработки, выход б-го блока постоянной памяти подключен к третьему информационному входу блока обработки (d + 1)-й строки первого столбца матрицы блоков обработки, второй и третий выходы блока .обработки М -ro столбца P-й строки. матрицы блоков г обработки подключены соответственно к первому и второму адресным входам P-го блока постоянной памяти, выход которого подключен к выходу устройства. вход синхронизации которого подключен к входам синхронизации всех блоков обработки мат30 50 рицы блоков обработки и к входам синхронизации блоков буферной памяти всех. групп, и-й выход сдвигающего регистра (где п - 1,...,М ) подключен к четвертым информационным входам блоков обработки и-го столбца матрицы блоков обработки, вход начальной установки устройства подключен к входу синхронизации сдвигающего регистра, причем каждый блок обработки содержит пять регистров, узел сравнения, арифметико-логический узел и элемент И, при этом в каждом блоке обработки первый. второй, третий и четвертый информационные входы блока обработки подключены соответственно к информационному входу первого регистра, к первому информационному входу арифметико-логического узла. к информационному входу второго регистра и к первому входу элемента И, выход которого подключен к второму информационному входу арифметйко-логического узла, выход которого подключен к информационному входу третьего регистра, выход которого подключен к информационному входу четвертого регистра, выход первого регистра подключен к первому выходу блока обработки и к первому входу узла сравнения, выход второго регистра подключен к информационному входу пятого регистра, к входу кода операции арифметико-логического узла и к второму входу узла сравнения, выход которого подключен к второму входу элемента И, выходы четвертого и пятого регистров подключены соответственно к второму и к третьему выходам блока обработки, вход синхронизации которого подключен к входам записи-считывания регистров с первого по пятый, причем каждый блок буферной памяти содержит узел оперативной памяти и счетчик, при этом в каждом блоке буферной памяти информационный вход блока буферной памяти подключен к информационному входу узла оперативной памяти, выход которого подключен к выходу блока буферной памяти, вход синхронизации которого подключен к входу записи-считывания узла оперативной памяти.и к счетному входу счетчика, информационный выход которого подключен к адресному входу узла. оперативной памяти. 1727137 Составитель К. Юсупов Техред M.Mîðãåíòàë Корректор Н. Король Редактор М. Петрова Производственно-издательский комбинат "Патент", г. Ужгород. ул.Гагарина, 101 Заказ 1280 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., 4/5
