Устройство для ранговой фильтрации
Изобретение относится к вычислительной технике и может быть использовано при высокоскоростной обработке изображений. Целью изобретения является повышение быстродействия. Устройство содержит регистры, сумматоры-вычитатели, блоки памяти, компараторы и блоки постоянной памяти. 3 ил.
Изобретение относится к вычислительной технике и может быть использовано при высокоскоростной обработке данных, например при обработке изображений.
Известно устройство для определения элемента данных с установленным рангом (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. Алгоритм поиска элемента 1R с заданным рангом R в окне размером MxN пикселей, являющийся основой работы устройства, имеет следующий вид. Начало алгоритма 1, S1 : = - R, l1 = 0, di=0 ((i=)); для i= цикл, для j= цикл. 2. Если Ri = 0, то (li): = d1d2 ... di-1 0; Eсли Dj li ,то (Si: = Si+1), иначе (Si: = Si)), иначе (li: = d1d2 ... di-1 1; Если Dj li, то (Si: = Si-1), иначе (Si: = Si)); конец по ji. 3. Если Si < 0, то (di: = 1, li+1: = 0), иначе (di: = 0, li+1: = 1);Si+1: = Si;
конец по i. 4. 1R : = lQ;
конец алгоритма. Здесь Dj - j-й пиксел окна; di - бинарная переменная, определяющая i-й разряд результата; A B - условие совпадения i старших разрядов чисел A и В. Пиксели изображения Dj поступают на вод 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 алгоритма. Необходимо учесть, что переменная li и (Q-1)-й старший разряд переменной li имеют одинаковые значения. Таким образом, в i-м блоке 3 ((i=)) корректируется старший (Q-i+1)-й разряд и устанавливается (Q-1)-й разряд результата li с учетом значения знакового (старшего) разряда Si. На выходе Q-го блока 3 получают значение элемента 1R с заданным рангом R. Эффективность предлагаемого устройства заключается в повышении быстродействия. В предлагаемом устройстве для определения следующего результата необходим один такт независимо от размера окна, в то время как в прототипе требуется 2М+Q тактов.
Формула изобретения
РИСУНКИ
Рисунок 1, Рисунок 2, Рисунок 3
Похожие патенты:
Изобретение относится к вычислительной технике и радиотехнике и предназначено для применения в анализаторах спектра и устройствах цифровой обработки сигналов
Изобретение относится к вычислительной технике и может быть использовано в специализированных системах для обработки сигналов и изображений
Изобретение относится к вычислительной технике и может найти применение при проектировании программ для ЭВМ
Устройство для решения задачи анализа продолжительности функционирования сложного объекта // 2015547
Изобретение относится к вычислительной технике и может быть использовано для анализа продолжительности функционирования сложного объекта
Способ обмена информации в микрокалькуляторной сети и микрокалькуляторная сеть для его осуществления // 2015545
Изобретение относится к вычислительной технике и телеавтоматике, в частности к обучающим системам, построенным на микрокалькуляторах
Устройство для перебора перестановок // 2012054
Изобретение относится к вычислительной технике, предназначено для формирования в произвольной последовательности перестановок и может быть использовано для решения комбинаторных задач, а также в системах контроля для генерации кодовых последовательностей
Устройство для перебора перестановок // 2012054
Изобретение относится к вычислительной технике, предназначено для формирования в произвольной последовательности перестановок и может быть использовано для решения комбинаторных задач, а также в системах контроля для генерации кодовых последовательностей
Изобретение относится к вычислительной технике и может быть использовано в электронной цифровой вычислительной машине
Изобретение относится к электронным играм
Микроэвм // 2108619
Изобретение относится к области микропроцессорной техники, в частности, может применяться для реализации обмена информацией
Изобретение относится к области цифровой вычислительной техники и предназначено для обработки двух или больше компьютерных команд параллельно
Изобретение относится к области вычислительной техники и предназначено для создания высокоскоростных систем обработки больших потоков данных в реальном режиме времени
Схемное устройство для параллельной обработки двух или более команд в цифровом компьютере // 2111531
Изобретение относится к цифровым компьютерным системам и предназначено для обработки двух и более команд параллельно
Многопроцессорная векторная эвм // 2113010
Изобретение относится к вычислительной технике, точнее к построению многопроцессорных векторных ЭВМ
Изобретение относится к вычислительной технике и может найти применение в автоматизированных системах управления АСУ индустриального и специального назначения
Изобретение относится к изготовлению выкроек, в частности таких выкроек, которые должны использоваться при изготовлении предметов одежды