Устройство для ранговой фильтрации с произвольной формой окна Советский патент 1992 года по МПК G06F15/36 G06F15/66 

му информационному входу блока обработки (d + 1}-й строки первого столбца матрицы блоков обработки, второй и третий выходы блока обработки М2-го столбца Р-й строки матрицы блоков обработки подключены соответственно к первому и второму адресным входам Р-го блока постоянной памяти, выход которого подключен к выходу устройства, выход синхронизации которого подключен к входам синхронизации всех блоков обработки матрицы блоков обработки и к входам синхронизации блоков буфер- ной памяти всех групп, п-й выход сдвигающего регистра (где п 1М2) подключен к четвертым информационным входам блоков обработки n-го столбца матрицы блоков обработки, вход начальной установки устройства подключен к входу синхронизации сдвигающего регистра, причем каждый блок обработки содержит пять регистров, узел сравнения, арифметико-логический узел и элемент И, при этом в каждом блоке обработки первый, второй, третий и четвертый информационные входы блока обработки подключены соответственно к информационному входу первого регистра, к первому информационному входу арифметико-логического узла, к информационному входу второго регистра и к первому входу элемента И, выход которого подключен к второму информационному входу арифметико-логического узла, выход которого подключен к информационному входу третьего регистра, выход которого подключен к информационному входу четвертого регистра, выход первого регистра подключен к первому выходу блока обработки и к первому входу узла сравнения, выход второго регистра подключен к информационному входу пятого регистра, к входу кода операции арифметико-логического узла и к второму входу узла сравнения, выход которого подключен к второму входу элемента И, выход четвертого и пятого регистров подключены соответственно к второму и третьему выходам блока обработки, вход синхронизации которого подключен к входам записи-считывания регистров с первого по пятый, причем каждый блок буферной памяти содержит узел оперативной памяти и счетчик при этом в каждом блоке буферной памяти информационный вход блока буферной памяти подключен к информационному входу узла оперативной памяти, выход которого подключен к выходу блока буферной памяти, вход синхронизации которого подключен к входу записи-считывания узла оперативной памяти и к счетному входу счетчика, информационный выход которого

подключен к адресному входу узла оперативной памяти.

Повышение быстродействия предлагаемого устройства ранговой фильтрации в S 5 раз (S М2) по сравнению с известным достигается за счет использования М2 х Р блоков обработки, с первого по Р-й блоки постоянной памяти, с первой по М-ю группы блоков буферной памяти и сдвигающего ре- 10 гистра, соединенных соответствующим образом, что обусловлено использованием нового алгоритма определения элемента изображения с заданным рангом, который обеспечивает одновременно формирование 15 гистограммы и поиск результата.

Устройство ранговой фильтрации с произвольной формой окна (фиг. 1) содержи матрицу размером М х М х Р блоков 1 обработки, где М х М - максимальный размер

0 окна фильтрации, Р - разрядность входных данных, с первого по Р-й блоки 2 постоям ной памяти, с первой по М-ю группы блоков 3 буферной памяти, сдвигающий регистр А. При этом каждый блок 1 обработки (фиг. 2)

5 содержит пять регистров 5. узел 6 сравнения, арифметико-логический узел 7 и элемент И 8. Блок 3 буферной памяти (фиг. 3) содержит узел 9 оперативной памяти и счетчик 10..

0 Вход 11 данных устройства подключен к первому информационному сходу 12 блока 1 обработки первой строки первого столбца матрицы блоков обработки и к информационному входу сдвигающего регистра 4. Вход

5 13 значения ранга и вход 14 нулевого потенциала устройства подключены соответственно к второму 15 и третьему 16 информационным входам блока 1 обработ- ки первого столбца первой строки матрицы.

0 Первый 17, второй 16 и третий 19 выходы блока 1 обработки а-й строки b-го столбца

матрицы блоков обработки (где а-1Р, Ь1 ,...,М-1) подключены соответственно к первому 12, второму 15 и третьему 16

5 информационным входам блока 1 обработки а-й строки (Ь + 1)-го столбца матрицы блокоо обработки. Выход 20 с-го блока 3

буферной памяти (где с-1Р-1) первой

группы подключен к первому информацион0 ному входу 12 блока 1 обработки (с + 1)-й хггроки первого столбца матрицы блоков обработки. Первый выход 17 блока 1 обработки i-й строки j-ro столбца где 1-1,-...,P. J-M. 2М,...,(М-1)М матрицы блоков обработки

5 подключен к информационному входу 21 I- го блока 3 буферной памяти О/М + 1)-й группы, выход 20 которого подключен к первому информационному входу 12 блока 1 обработки 1-1 строки ( + 1)-го столбца матрицы блока обработки. Второй 18 и третий 19 выходы блока 1 обработки а-й строки 0 + Ь)-го столбца матрицы блоков обработки подключены соответственно к второму 15 и третьему 16 информационным входам блока 1 обработки а-й строки 0 + о + 1)-го столбца матрицы блоков обработки. Первый 17 и третий 19 выходы блока 1 обработки d-й строки (где d-1,...,P-1) столбца матрицы блоков обработки подключены соответственно к информационному входу 21 d-ro , блока 3 буферной памяти первой группы и к первому адресному входу d-ro блока 2 постоянной памяти. Второй выход 18 блока 1 обработки d-й строки М2-го столбца матрицы блока обработки подключен к второму адресному входу d-ro блока 2 постоянной памяти и к второму информационному входу 15 блока 1 обработки (d + 1)-й строки первого столбца матрицы блоков обработки. Выход d-ro блока 2 постоянной памяти подключен к третьему информационному входу 16 блока 1 обработки, (d + 1)-й строки первого столбца матрицы блоков обработки. Второй 18 и третий 19 выходы блока 1 обработки Р-й строки М2-го столбца матрицы блоков обработки подключены соответственно к первому и второму адресным входам Р-го блока 2 постоянной памяти, выход которого подключен к выходу 22 устройства. Вход 23 синхронизации устройства подкл.ючен к входам 24 синхронизации всех блоков 1 обработки матрицы блоков обработки и к входам 25 синхронизации блоков 3 буферной памяти всех групп, n-й выход сдвигающего регистра 4 (где п-1,...,М2) подключен к четвертым информационным входам 26 блоков 1 обработки n-го столбца матрицы блоков обработки. Вход 27 начальной установки устройства подключен к входу синхронизации сдвигающего регистра 4. Первый 12, второй 15, третий 16 и четвертый 26 информационные входы блока 1 обработки подключены соответственно к информационному входу первого регистра 5, первому информационному входу арифметико-логического узла 7, информационному входу второго регистра 5 и первому входу элемента И 8. Выход последнего подключен к второму информационному входу арифметико-логического узла 7, выход которого подключен к информационному входу третьего регистра 5, выход которого подключен к информационному входу четвертого регистра 5. Выход первого регистра 5 подключен к первому выходу 17 блока 1 обработки и к первому входу узла 6 сравнения. Выход второго регистра 5 подключен к информационному входу пятого регистра 5, входу кода операции арифмерико-логиче- ского узла 7 и второму входу узла б сравнения, выход которого подключен к второму входу элемента И 8. Выходы четвертого и- пятого регистров 5 подключены соответственно к второму 18 и к третьему 19 выходам блока 1 обработки. Вход 24 синхронизации блока 1 обработки подключен к входам записи-считывания первого-пятого регистров 5.

Информационный вход 21 блока 3 бу- 0 ферной памяти подключен к информационному входу узла 9 оперативной памяти, выход которого подключен к выходу 20 блока 3 буферной памяти. Вход 25 синхронизации блока 3 буферной памяти подключен к 5 входу записи-считывания узла 9 оперативной памяти и счетному входу счетчика 10. Информационный выход последнего подключен к адресному входу узла 9 оперативной памяти.

0 В качестве элементов устройства используются микросхемы, выпускаемые промышленностью. Так, например, в качестве регистров можно использовать микросхему К155ИР13 арифметико-логического узла 5 (К155ИПЗ). узла сравнения (К555СП1), счетчика (К155ИЕ7), узла оперативной памяти (132РУ8), элемента И (К155ЛИ1).

Алгоритм поиска элемента IR с заданным рангом R в окне фильтрации размером 0 М х М элементов, являющийся основой работы устройства, имеет следующий вид (форма окна задается вектором FJ): начало алгоритма:

Нi; - -R, kj: 0, di: 0 (i 1. Р)(1)

5 для I Г,Рецикл;

для j 1 ,М2 цикл;

если ki: 0, то (li: did2d3...di-i 0); (2)

если ((Dj л 10-и (Fj fi), то (Si: - Sj + .1),

иначе (Si: S;)). иначе (h: did2...di-i 1): 0 если ((Dj A li) и (Fj li), то (Si: Si - 1),

иначе (Sf: Si));

конец по J;

если Si 0, то (di: 1, ki + i: 0); (3)

иначе (di: 0; ki-ц: 1); 5 Sn-i: Si;

конец по I;

|R: IP;(4)

конец алгоритма. Где Dj - j-й пиксел окна; 0 di - бинарная переменная, определяющая 1-й разряд результата;

А Д В - условие совпадения i старших разрядов чисел А и В.

Перед началом работы устройства про- 5 изводится начальная установка, заключаю щаяся в загрузке коэффициентов Fj. в сдвигающий регистр 4. Коэффициенты FJ являются однобитными операндами, поэтому на информационный вход сдвигающего регистра 4 достаточно подать, например, старший разряд операнда с входа 11 данных устройства. На вход 27 начальной установки устройства поступают синхроимпульсы, по переднему фронту которых происходит запись коэффициентов в сдвигающий регистр 4. После загрузки коэффициентов FJ устройство переводится в основной режим работы.

Элементы изображения D/ поступают на вход 11 данных в такт с синхроимпульса ми на входе 23 устройства.

Рассмотрим формирование первого промежуточного результата, начиная с момента ввода элементов (М-1)-й строки кадра изображения.

Очередной элемент изображения записывается в первый регистр 5 блока 1 обработки первого столбца первой строки матрицы блоков обработки по переднему фронту синхроимпульса, поступающего на вход 24 синхронизации блока 1 обработки. Одновременно происходит запись нуля во второй регистр 5. На второй вход 15 арифметико-логического узла блока 1 обработки поступает отрицательное значение ранга с входа 13 значения ранга устройства. Операция 1 алгоритма. В узле 6 сравнения cpaeL ниваются старшие разряды данных, записанных в первый и второй регистры 5. Если эти числа равны, то на выходе узла 6 сравнения появляется единица, иначе - ноль. Однобитный операнд с выхода узла 6 сравнения поступает на второй вход элемента И 8, на первый вход которого поступает коэффициент FI с первого выхода сдвигающего регистра 4. Результат с выхода элемента И 8 поступает на второй вход арифметико-логического узла 7. Код операции арифметико-логического узла 7 определяется Р-м старшим разрядом числа во втором регистре 5: если Р-й разряд равен О, то выполняется операция суммирования, иначе - вычитания (операция 2 алгорит- ма).Результат свыхода

арифметико-логического узла 7 записывается в первый регистр 5 по заднему фронту синхроимпульса. В четвертый регистр 5 запись данных, поступающих с выхода третьего регистра 5, происходит по переднему фронту синхроимпульса. Работа остальных блоков 1 обработки матрицы блоков обработки аналогична работе блока 1 обработки первого столбца первой строки этой матрицы. Блоки 3 буферной памяти с второй по М-й группы обеспечивают задержку данных на (I + М) тактов (где I - число столбцов в кадре изображения}, а блоки буферной памяти первой группы - на М2 тактов..

Блок 3 буферной памяти работает следующим образом,

На информационный вход 21 блока 3 буферной памяти поступает элемент изо- 5 бражения, значение которого записывается в узел 9 оперативной памяти по низкому уровню синхроимпульса, поступающего на вход 25 синхронизации/При этом адрес, по которому происходит запись, определяется

0 содержимым счетчика 10, изменяющемся по заднему фронту синхроимпульса. Длительность задержки узла 9 оперативной памяти устанавливается коэффициентом пересчета счетчика 10.

15 После М тактов число с третьего выхода 19 и старший разряд числа с второго выхода 18 блока 1 обработки первой строки бца матрицы блоков обработки поступают на вход первого блока 2 постоянной памяти.

0 Прошивка блока 2 постоянной памяти осу ществляется в соответствии с операцией 3 алгоритма. Необходимо учесть, что пере менная ki и (Р-1)-й старший разряд переменной h имеют одинаковые значения. Таким

5 образом, в 1-м блоке 2 постоянной памяти (I

. 1.....Р) корректируется старший (Р -1 + 1)-й разряд и устанавливается (Р - 1)-й разряд результата II с учетом значения знакового (старшего) разряда Si. На выходе Р-ro блока

0 2 постоянной памяти получим значение элемента с заданным рангом R.

Эффективность предлагаемого устройства заключается в повышении быстродействия. В предлагаемом устройстве для

5 определения следующего результата необходим один такт независимо от размера окна фильтрации, в то время как в известном устройстве требуется S тактов.

Формула изобретения

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

произвольной формой окна, содержащее матрицу размером М х М БЛОКОВ обработки, где М х М - максимальный размер окна фильтрации, отличающееся тем, что,

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

0 с первой по М-ю группы блоков буферной памяти и сдвигающий регистр, причем вход данных устройства подключен к первому информационному входу блока обработки первой строки первого столбца матрицы блоков

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

матрицы, первый, второй и третий выходы блока обработки а-й строки b-го столбца матрицы блоков обработки (где а -1 ,...,Р, Ь - 1.....М - 1) подключены соответственно к первому, второму и третьему информационным входам блока обработки а-й строки (Ь + +1)-го столбца матрицы блоков обработки, выход с-го блока буферной памяти (где с 1р-1) первой группы подключен к первому информационному входу блока обработки (с + 1)-й строки первого.столбца матрицы блоков обработки, первый выход блока обработки 1-й строки j-ro столбца матрицы где I - 1.....Р, J М; 2М(М - 1)М

блоков обработки подключен к информационному входу 1-го блока буферной памяти Q/M + 1}-1 группы, выход которого подключен к первому информационному входу блока обработки 1-й строки Q + 1)-го столбца матрицы блоков обработки, второй и третий выходы блока обработки а-й строки О + Ь)-го столбца матрицы блоков обработки подключены соответственно к второму и третьему информационным входам блока обработки а-й строки 0 + Ь + 1)-го столбца матрицы блоков обработки, первый и третий выходы

блока обработки d-й строки (где d 1Р-1)

М2-го столбца матрицы блоков обработки подключены соответственно к информационному входу d -ro блока буферной памяти первой группы и к первому адресному входу d-ro блока постоянной памяти, второй выход блока обработки d-й строки М--го столбца матрицы блока.обработки подключен ко второму адресному входу d-ro блока постоянной памяти и к второму информационному входу блока обработки (d + 1)-й строки первого столбца матрицы блоков обработки, выход d-ro блока постоянной памяти подключен к третьему информационному входу блока обработки (d + 1}-й строки первого столбца матрицы блоков обработки, второй и третий выходы блика обработки М2-го столбца Р-й строки матрицы блоков обработки подключены соответственно к первому и второму адресным входам Р-го блока постоянной памяти, выход которого подключен к выходу устройства, вход синхронизации которого подключен к входам синхронизации всех блоков обработки матрицы блоков обработки и к входам синхронизации блоков буферной памяти всех, групп, n-й выход сдвигающего регистра (где п - 1М ) подключен к четвертым информационным входам блоков обработки п-го столбца матрицы блоков обработки, вход начальной установки устройства подключен к входу синхронизации сдвигающего регистра, причем каждый блок обработки содержит пять регистров, узел сравнения, арифметико-логический узел и элемент И, при этом в каждом блоке обработки первый, второй, третий и четвертый информационные входы блока обработки подключены соответственно к информационному входу первого регистра, к первому информационному входу арифметико-логического узла, к информационному входу второго регистра и к первому входу элемента И, выход которого

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

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

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

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

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

Фиг.2

Фиг. 3