УСТРОЙСТВО ДЛЯ РАНГОВОЙ ФИЛЬТРАЦИИ Российский патент 1994 года по МПК G06F15/36 

Изобретение относится к вычислительной технике и может быть использовано при высокоскоростной обработке данных, например при обработке изображений.

Известно устройство для определения элемента данных с установленным рангом (Corry A. G., Arvind D.K., Conolly G.L., Korva R.R. Image processing with VLSI. - Microprocessors and microsistems, 1983,v.7, N 10, pp.482-486), содержащее 300 сортирующих элементов (СЭ), 25 элементов задержки и представляющее собой регулярную сортирующую сеть для апертуры фильтра 5х5 пикселей, выполненную в виде 25 ступеней, в каждой из которых содержится 12 СЭ и один элемент задержки.

Недостатком известного устройства является большой объем оборудования, равный L (L-1)/2 СЭ (L - число пикселей в окне).

Известно устройство для формирования порядковых статистик (авт. св. СССР N 1196897, кл. G 06 F 15/36, 05.06.84), содержащее три мультиплексора, группу регистров, регистр сдвига, блок выделения наибольшего числа, элементы И, блок управления, элементы ИЛИ, два счетчика, регистр маски, триггер, генератор и элементы задержки.

Недостатком данного устройства является низкое быстродействие, так как для получения i-й порядковой статистики необходимо N-r тактов (N - число пикселей, из которых определяется r-я порядковая статистика).

Наиболее близким по технической сущности и достигаемому результату к изобретению является устройство для обработки гистограмм (авт. св. СССР N 1196898, кл. G 06 F 11/06, 26.06.84), позволяющее выполнять медианную фильтрацию, которая является частным случаем ранговой фильтрации (Ярославский Л.П. Цифровая обработка сигналов в оптике и голографии. Введение в цифровую оптику. - М.: Радио и связь, 1987). Устройство содержит Q блоков памяти, Q формирователей прямоугольных импульсов, Q сумматоров, Q регистров результата, образующих Q блоков обработки (Q - разрядность обрабатываемых данных), и блок микропрограммного управления, причем первый информационный вход каждого сумматора соединен с выходом соответствующего формирователя прямоугольных импульсов, второй информационный вход первого сумматора соединен с информационным входом операционного блока, второй информационный вход (i+1)-го сумматора соединен с выходом i-го регистра результата ((i=)), информационный выход каждого сумматора соединен с информационным входом соответствующего регистра результата, информационный выход каждого блока памяти соединен с входом соответствующего формирователя прямоугольных импульсов, а информационный вход каждого блока памяти соединен с выходом соответствующего регистра результата, адресный вход операционного блока соединен с адресным входом каждого блока памяти, выход блока микропрограммного управления соединен с входами записи-чтения каждого блока памяти, входами разрешения каждого формирователя прямоугольных импульсов, входами управления каждого сумматора, входами стробирования каждого регистра результата, вход команд блока микропрограммного управления является входом выбора режима работы устройства.

Недостатком данного устройства является малое быстродействие, обусловленное тем, что ввод элементов столбца осуществляется последовательно за 2М циклов суммирования-вычитания, а поиск результата выполняется за Q циклов сравнения. Кроме того, быстродействие уменьшается c увеличением размера окна.

Цель изобретения - повышение быстродействия.

Цель достигается тем, что в устройство, содержащее Q узлов обработки (УО), в состав каждого из которых входит сумматор-вычитатель, введены регистр ранга, NxM-1 таких же УО (MxN - размер окна фильтра; Q - разрядность входных данных), Q блоков постоянной памяти, QxM-1 линий задержки, при этом УО содержит два регистра промежуточного результата, регистр входных данных, первый и второй регистры промежуточной суммы, компаpатор и сумматор-вычитатель, а линия задержки содержит ОЗУ и счетчик, причем входы первого регистра промежуточного результата, регистр входных данных и второй вход сумматора-вычитателя соединены с первым, вторым и третьим входами УО соответственно, входы синхронизации регистров промежуточного результата, регистра входных данных, первого и второго регистра промежуточной суммы УО соединены с четвертым входом УО, выходы первого регистра промежуточной суммы, регистра входных данных, второго регистра промежуточной суммы соединены с первым, вторым и третьим выходами УО соответственно, четвертый вход УО соединен с его четвертым выходом, выходы первого регистра промежуточного результата и регистра входных данных соединены с первым и вторым входами компаратора, выход которого соединен с первым входом сумматора-вычитателя, при этом Q-1 младших разрядов второго входа компаратора i,j-го УО (i=, j= , K = MxN) соединены с линией логического "0", выход сумматора-вычитателя соединен с входом первого регистра промежуточной суммы, вход выбора функций сумматора-вычитателя i,j-го УО соединен с (Q-i+1)-м старшим разрядом выхода первого регистра промежуточной суммы ((i=, j=)), выход первого регистра промежуточного результата соединен с входом второго регистра промежуточного результата, кроме того, первый вход линии задержки соединен с входом данных ОЗУ, второй вход - с входом синхронизации счетчика и входом записи-считывания ОЗУ, выход ОЗУ соединен с выходом линии задержки, первый и третий входы 1.1-го УО соединены с линией логического "0" и с выходом регистра ранга соответственно, второй вход 1.1-го УО соединен с входом данных, а четвертый вход - с входом синхронизации устройства, l-й выход i, j-го УО соединен с l-м входом (i,j+1)-го УО ((i=, j=, l= )), второй выход (i,Nxm)-го УО соединен с первым входом (m+1,i)-й линии задержки ((m= ), выход которой соединен с вторым входом (i,Nxm+1)-го УО, первый выход и старший разряд третьего выхода 1,К-го УО ((i=) соединены с адресным входом i-го блока постоянной памяти, выход которого соединен с первым входом (i+1,1)-го УО, третий и четвертый выходы i,К-го УО соединены непосредственно с третьим и четвертым входами, а второй выход - с первым входом (1,i+1)-й линии задержки, выход которой соединен с вторым входом (i+1,1)-го УО ((i=), первый выход и старший разряд третьего выхода O, K-го УО соединены с входом Q-го блока постоянной памяти, выход которого соединен с выходом устройства, а вторые входы всех линий задержки соединены с четвертыми входами УО.

Повышение быстродействия устройства ранговой фильтрации в 2М+Q раз по сравнению с прототипом достигается за счет использования NxQ блоков обработки, Q постоянных ЗУ, (Qxm-1) линий задержки, соединенных соответствующим образом, что обусловлено использованием нового алгоритма определения элемента изображения с заданным рангом, который обеспечивает одновременно формирование гистограммы и поиск результата.

В известных технических решениях не обнаружено совокупности существенных отличительных признаков заявляемого технического решения. На основании этого считают, что заявляемое техническое решение соответствует критерию "существенные отличия".

На фиг. 1 изображена структурная схема устройства для ранговой фильтрации; на фиг. 2 и фиг. 3 изображены структурная схема блока обработки и вариант реализации линии задержки соответственно.

Устройство (фиг. 1) состоит из регистра (1) ранга, NxMxQ УО 2 (MxN - размер окна фильтра; Q - разрядность входных данных), Q блоков 3 постоянной памяти, QxM-1 линий 4 задержки. УО 2 (фиг. 2) содержит два регистра 5 промежуточного результата, регистр 6 входных данных, первый 7 и второй 8 регистры промежуточной суммы, компаратор 9 и сумматор-вычитатель 10. Линия задержки (фиг. 3) содержит ОЗУ 11 и счетчик 12.

Входы первого регистра 5 промежуточного результата и регистра 6 входных данных (фиг. 2), второй вход сумматора-вычитателя 10 соединены с первым 13, вторым 14 и третьим 15 входами УО 2 соответственно, входы синхронизации двух регистров 5 промежуточного результата, регистра входных данных, первого 7 и второго 8 регистров промежуточной суммы УО 2 соединены с четвертым входом 16 УО 2. Выходы второго регистра 5 промежуточного результата, регистра 6 входных данных и второго регистра 8 промежуточной суммы соединены с первым 17, вторым 18 и третьим 19 выходами УО 2 соответственно. Четвертый вход 16 УО 2 соединен с его четвертым выходом 20. Выходы первого регистра 5 промежуточного результата и регистра 6 входных данных соединены с первым и вторым входами компаратора 9, выход которого соединен с первым входом сумматора-вычитателя 10. При этом Q-i младших разрядов второго входа компаратора 9 i,j-го УО 2 (i=, j=, K = MxN) соединены с линией логического "0". Выход сумматора-вычитателя 10 соединен с входом первого регистра 7 промежуточной суммы. Вход выбора функции сумматора-вычитателя 10 i,j-го УО 2 соединен с (Q-i+1)-м старшим разрядом выхода первого регистра 5 промежуточного результата ((i= , j=)). Выход первого регистра 5 промежуточного результата соединен с входом второго регистра 5 промежуточного результата.

Первый вход 21 линии задержки 4 (фиг. 3) соединен с входом данных ОЗУ 11, второй вход 22 - с входом синхронизации счетчика 12 и входом записи-считывания ОЗУ 11. Выход ОЗУ 11 соединен с выходом 23 линии задержки 4.

Первый и третий входы 1.1-го УО 2 (фиг. 1) соединены с линией логического "0" и с выходом регистра 1 ранга соответственно. Второй вход 1.1-го УО 2 соединен с входом 24 данных, а четвертый вход - с входом 25 синхронизации. С первого 17 по четвертый 20 выходы i,j-го УО 2 соединены с первого по четвертый входы (i,j+1)-го УО 2 соответственно ((i=, j=) ). Второй выход 18 (i,Nxm)-го УО 2 соединен с первым входом 21 (m+1,i)-й линии 4 задержки ((m= )). выход 23 которой соединен с вторым входом 14 (Nxm+1)-го УО 2. Первый выход 17 и старший разряд третьего выхода 19 (i, K)-го УО 2 ((i=)) соединен с адресным входом i-го блока 3 постоянной памяти, выход которого соединен с первым входом 13 (i+1,1)-го УО 2. Третий 19 и четвертый 20 выходы i,K-го УО 2 соединены непосредственно с третьим 15 и четвертым 16 входами, а второй выход 18 - с первым входом 21 (1,i+1)-й линии задержки 4, выход 23 которой соединен с вторым входом 14 (i+1,1)-го УО 2. Первый выход 17 и старший разряд третьего выхода 19 Q,K-го УО 2 соединены с входом Q-го блока 3 постоянной памяти, выход которого соединен с выходом 26 устройства. Вторые входы 22 всех линий 4 задержки соединены с четвертыми входами 16 УО 2.

Алгоритм поиска элемента 1_R с заданным рангом R в окне размером MxN пикселей, являющийся основой работы устройства, имеет следующий вид.

Начало алгоритма 1, S₁ : = - R, l₁ = 0, d_i=0 ((i=));
для i= цикл,
для j= цикл. 2. Если R_i = 0, то (l_i): = d₁d₂ ... d_i-1 0;
Eсли D_j l_i ,то (S_i: = S_i+1),
иначе (S_i: = S_i)),
иначе (l_i: = d₁d₂ ... d_i-1 1;
Если D_j l_i, то (S_i: = S_i-1),
иначе (S_i: = S_i));
конец по j_i. 3. Если S_i < 0, то (di_: = 1, l_i+1: = 0),
иначе (d_i: = 0, l_i+1: = 1);
S_i+1: = S_i;
конец по i. 4. 1_R : = l_Q;
конец алгоритма.

Здесь D_j - j-й пиксел окна; d_i - бинарная переменная, определяющая i-й разряд результата; A B - условие совпадения i старших разрядов чисел A и В.

Пиксели изображения D_j поступают на вод 24 данных в такт с синхроимпульсами на входе 25. Формирование первого промежуточного результата рассмотрим, начиная с момента ввода элементов (М-1)-й строки кадра.

Очередной элемент изображения записывается в регистр 6 входных данных 1.1-го УО 2 по переднему фронту синхроимпульса, поступающего на четвертый вход 16. Одновременно происходит запись нуля в первый регистр 5 промежуточного результата. На второй вход сумматора-вычитателя 10 через третий вход 15 УО 2 поступает отрицательное значение ранга с выхода регистра 1 ранга (операция 1 алгоритма). В компараторе 9 сравниваются старшие разряды данных, записанных в первый регистр 5 промежуточного результата и в регистр 6 входных данных. Если эти числа равны, то на выходе компаратора 9 будет единица, иначе - ноль. Однобитный операнд с выхода компаратора 9 поступает на первый вход сумматора-вычитателя 10. Код операции сумматора-вычитателя 10 определяется O-м старшим разрядом числа в первом регистре 5 промежуточного результата. Если O-й разряд равен "1", то выполняется операция суммирования, иначе - вычитания (операция 2 алгоритма). Результат с выхода сумматора-вычитателя 10 записывается в первый регистр 7 промежуточной суммы. Запись данных с выхода первого регистра 7 промежуточной суммы происходит по переднему фронту синхроимпульса. Работа остальных УО 2 аналогична работе 1,1-го УО 2. Каждая i,j-я линия 4 задержки ((i=, j=)) обеспечивает задержку данных на I+N тактов (I - число столбцов в кадре), а 1,n-я - на К тактов ((n=)).

Линия 4 задержки работает следующим образом. На ее первый вход 21 поступает пиксел изображения, значение которого записывается в ОЗУ 11 по низкому уровню синхроимпульса, поступающего на второй вход 22 линии 4 задержки . При этом адрес, по которому происходит запись, определяется содержанием счетчика 12, изменяющимся по заднему фронту синхроимпульса. Длительность задержки линии 4 устанавливается коэффициентом пересчета счетчика 12.

После К тактов число с первого выхода 17 и старший разряд с третьего выхода 19 1,К-го УО 2 поступает на вход блока 3 постоянной памяти. Прошивка блока 3 осуществляется в соответствии с операцией 3 алгоритма. Необходимо учесть, что переменная l_i и (Q-1)-й старший разряд переменной l_i имеют одинаковые значения.

Таким образом, в i-м блоке 3 ((i=)) корректируется старший (Q-i+1)-й разряд и устанавливается (Q-1)-й разряд результата l_i с учетом значения знакового (старшего) разряда S_i. На выходе Q-го блока 3 получают значение элемента 1_R с заданным рангом R.

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

Изобретение относится к вычислительной технике и может быть использовано при высокоскоростной обработке изображений. Целью изобретения является повышение быстродействия. Устройство содержит регистры, сумматоры-вычитатели, блоки памяти, компараторы и блоки постоянной памяти. 3 ил.

УСТРОЙСТВО ДЛЯ РАНГОВОЙ ФИЛЬТРАЦИИ, содержащее входной регистр, блоки памяти и узлы обработки информации, каждый из которых состоит из четырех регистров и сумматора-вычитателя, отличающееся тем, что, с целью повышения быстродействия, в него введены блоки постоянной памяти, а в состав каждого узла обработки информации дополнительно введены пятый регистр и компаратор, причем информационный вход первого регистра первого узла обработки является информационным входом устройства, в каждом узле обработки информации выход второго регистра соединен с информационным входом третьего регистра и с первыми входами сумматора-вычитателя и компаратора, выход которого подключен к входу задания режима сумматора-вычитателя, выход которого соединен с информационным входом четвертого регистра, выход которого подключен к информационному входу пятого регистра, выход первого регистра подключен к второму входу компаратора, выход входного регистра соединен с вторым входом сумматора-вычитателя первого узла обработки информации, выход пятого регистра каждого узла обработки информации, кроме последнего, соединен с вторым входом сумматора-вычитателя последующего узла обработки информации, информационный вход второго регистра первого узла обработки информации является входом задания постоянного значения устройства, информационный вход второго регистра каждого узла обработки информации, кроме (iK + 1)-х узлов, где i= , K = M · N - размер окна фильтрации, Q - разрядность данных, подключен к выходу третьего регистра предыдущего узла обработки информации, информационный вход второго регистра (iK + 1)-го узла обработки информации соединен с выходом i-го блока постоянной памяти, адресные входы которого соединены с выходами третьего и пятого регистров iK-го узла обработки информации, выход первого регистра каждого узла обработки информации, кроме iN-х узлов, соединен с информационным входом первого регистра последующего узла обработки информации, выход первого регистра iN-го узла обработки информации соединен с информационным входом i-го блока памяти, выход которого подключен к информационному входу первого регистра (iN + 1)-го узла обработки информации, синхровходы регистров и блоков памяти соединены с синхровходом устройства, выходы третьего и пятого регистров последнего узла обработки информации соединены с входами последнего постоянного запоминающего устройства, выход которого является выходом устройства.