Устройство для медианной фильтрации двумерных массивов

 

Изобретение относится к вычислительной технике и может быть использовано при обработке двумерных массивов данных. Целью изобретения является повышение быстродейтсвия. Устройство содержит блоки 1-3 памяти, счетчики 4-8, сумматоры 9,10, регистры 11-16, блок 17 сравнения, дешифратор 18, коммутаторы 19,20 генератор 21 тактовых импульсов, делитель 22 частоты, регистр 23 сдвига, триггеры 24-26, одновибраторы 27,28 группу элементов И 29, элементы И 30-33, элементы ИЛИ 34-37, элемент НЕ 38, элемент задержки 39. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (19) (11) А1,(51! 4 Г 06 F 15/36

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

К АBTOPCKOMY СВИДЕТЕЛЬСТВУ

1 (21) 4205268/24-24 (22) 02,03„87 (46) 23,11,89, Бюл. N - 43 (72) А,В.Василькевич и В,М,Крищигп н (53) 681,3(088.8) (56) Авторское свидетельство ГСГР

Ф 771665, кл, G 06 F 7/04, 1978, Авторское свидетельство СССР

М 1322314, кл. С 06 F !5/36, 1985. (54) УСТРОЙСТВО ДГЯ МЕДИАННОЙ ФИЛЬТРАЦИИ ДВУМЕРНЫХ YiACCHROB (57) Изобретение относится к вычислительной технике и может быть ис2 пользовано при обработке двумерных массивов данных, Целью изобретения является повышение быстродействия, Устройство содержит блоки 1-3 памяти, счетчики 4-8, сумматоры 9, 10, регистры 11-16 блок 17 сравнения, дешифратор 18, коммутаторы 19, 20, генератор 21 тактовых импульсов, делитель 22 частоты, регистр 23 сдвига, триггеры 24-26, одновибраторы

27, 28 группу элементов И 29, элементы И 30-33, элементы К11И 34-37, элемент HF, 38, элемент задержки 39, ) ил.

1524067

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

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

На чертеже представлена функциональная схема устройства.

Устройство содержит блоки 1-3 памяти, счетчики 4-8, сумматоры 9 и

l0, регистры 11-16, блок 17 сравне- 15 ния, дешифратор 18, коммутаторы 19 и 20, генератор 21 тактовых импульсов, делитель 22 частоты, регистр 23 сдвига, триггеры 24-26, одновибраторы 27 и 28, группу .элементов Vi 29, 20 элементы И 30-33, элемент ИЛИ 34-37, элемент HF. 38, элемент 39 задержки, „1 вход 40 начальной установки, вход

41 пуска, выход 42 окончания работы устройства, выход 43 индикации резуль-25 тата первой выборки, информационный выход 44 устройства.

Вход 40 начальной установки соединен с входами сброса счетчиков 4-8, регистра 13 и с первыми входами 30 элементов ИЛИ 34, 36. Выход генератора 21 импульсов соединен с входом синхронизации регистра 23 сдвига и входом делителя 22 частоты, выход которого соединен с синхровходом триггера 24 и первым входом элемента И 30, второй вход которого соединен с выходом триггера 24. Информационные выходы счетчика 5 соединены с адресными входами блоков 1 и 2 памяти, выхо- 40 ды которых соединены соответственно с первыми группами входов сумматоров 9 и 10, вторые группы входов которых соединены соответственно с информационными выходами счетчиков 7 и 8. Выходы 45 сумм сумматоров 9 и 10 соединены через регистры 11 и 12 соответственно с группами старших и младших разрядов адресного входа блока 3 памяти.

Выходы знаковых разрядов сумматоров 9 и 10 соединены с первого по четвертый входами элемента ИЛИ 35. Выход элемента ИЛИ 35 соединен через триггеры 25 и 26 с первым входом элемента

HJIH 37, выход которого соединен с управляющим входом коммутатора 19. Выход коммутатора 20 соединен с вторым входом элемента ИЛИ 37, Выходы блока

3 памяти через регистр 16 соединены с первой группой входов коммутатора

19, вторая группа входов которого под— ключена к уровню лог. "0", Выходы коммутатора 19 соединены с первой группой входов блока 17 сравнения и информационными входами регистра 15, выходы которого являются выходами 44 о устройства и соединены с второй группой входов блока 17 сравнения. Выход переноса счетчика 5 соединен через одновибратор 27 со счетным входом счетчика 4 и через элемент HF 38 с третьим входом элемента И 30, выход которого соединен с информационным входом регистра 23 сдвига, входами записи триггера 25, регистров 11 и 12 и счетным входом счетчика 5, Выход переноса счетчика 4 соединен со счетным входом счетчика 8 и первыми входами элементов И 32 и 33. Выход переноса счетчика 8 соединен со счетным входом счетчика 7, Выход переноса счетчика 7 является выходом 42 окончания работы устройства и соединен с входом сброса триггера 24, информационный вход которого соединен с входом 41 пуска, Информационные выходы счетчика 6 соединены с информационными входами регистра 13 и управляющими входами коммутатора 20, информационные входы которого соединены с выходами регистра 14. Выходы регистра 13 соединены с входами дешифратора 18, выходы которого соединены с первыми входами элементов И группы 29, выходы которых соединены с информационными входами регистра

14. Выход переноса счетчика 6 через одновибратор 28 соединен с вторыми входами элементов И группы 29, вторым входом элемента И 32 и через элемент 39 задержки с вторыми входами элементов ИЛИ 34 и И 33, выход которого соединен с вторым входом элемента

ИЛИ 36. Выход блока 17 сравнения соединен с первым входом элемента V. 31, выход которого соединен с входами записи регистров 13 и 15. Вход сброса регистра 15 соединен с выходом элемен1 та ИЛИ 34. Второй выход регистра 23 сдвига соединен с входами записи триггера 26 и регистра 16. Четвертый выход регистра 23 сдвига соединен со счетным входом счетчика 6 и вторым входом элемента И 31. Выход элемента И 32 является выходом 43 устройства.

В первом такте по первому тактовому импульсу к содержимому счетчика

5 прибавляется единица, в регистры

ll и 12 заносятся старшие и младшие разряды адреса нулевой точки апертуры, полученные сложением адреса центральной точки, который хранится в счетчиках 7 и 8, и смещений, считанных из блоков 1 и 2 памяти (смещение по строкам и смещение по столбцам).

Если текущая точка в апертуре вьг ходит за границы исходного массива, то хотя бы в одном знаковом разряде сумматоров 9 или 10 будет сигнал лог, "1", который, пройдя через элемент ИЛИ 35, занесется в триггер 25 . по первому тактовому импульсу, По сформированному адресу из блока 3 памяти считывается соответствующее число и заносится в регистр 16 по первому тактовому импульсу с второго выхода регистра 23 сдвига, а в триггер 26 переписывается содержимое триггера 25. В этом же такте в регистры

ll и 12 заносится адрес первой точки апертуры по второму импульсу. Первое число проходит через коммутатор

19 и сравнивается с содержимбм (ну15240

Устройство предназначено для медианной фильтрации двумерных массивов данных размером m х и, m — число строк, i.

n — число столбцов, где m = 2, n = 2

P S — целые положительные числа.

Апертура фильтра может быть произвольной. Число точек, входящих в апертуру, равно К (К вЂ” нечетное).

Алгоритм работы устройства следую- 10 щий.

Среди элементов массива, входящих в в апертуру, находится медиана и она заменяет центральную точку апертуры.

После этого апертура сдвигается и но- !5 вая центральная точка заменяется медианой. Направление сдвига апертуры: слева направо и сверху вниз, Счетчики 5 и 6 являются счетчиками с пересчетом К, счетчик 4 — с 20

К+1 пересчетом --„-, счетчик 7 — двоич2 ный счетчик разрядности Р, счетчик

8 — двоичный счетчик раз р яднос ти S, Разрядность блоков памяти 1 и 2 25 определяется числом К и формой ааертуры, Разрядность блока 3 памяти, блока 17 сравнения, коммутатора 19 и регистров 15 и 16 определяется разрядностью обрабатываемых данных. Раз- 30 рядность регистра 13 равна разрядности счетчика 6. Количество выходов дешифратора 18, элементов И группы

29, разрядность регистра !4 и число входов коммутатора 20 равно К.

Исходный массив хранится в блоке

3 памяти., Пронумеруем точки, входящие в апертуру от 0 до К. Тогда в блоке 1 памяти по i-му адресу хранится смещение i-й точки апертуры от- 40 носительно центральной точки апертуры по строкам, а в блоке 2 памяти по столбцам,.Смещение представляет собой число со знаком в дополнительном коде, причем под знак отводится 45 два разряда, В счетчиках 7 и 8 содержится текущий адрес центральной точки апертуры (номер строки и номер столбца соответственно). Суммирование текущего адреса центральной точки со смещением в сумматорах 9 и 10 позволяет полу чать абсолютные адреса точек, входящих в апертуру, для раэличных значений адреса Центральной точки. При этом наличие хотя бы одной "1" на выходе знаковых разрядов сумматоров 9 и 1О (знак представляется двумя разрядами ) свидетельствует о переполнении или отрицательном результате, т.е. выходе части апертуры за размеры исходного массива.

Устройство работает следующим образом, По сигналу начальной установки 40 сбрасываются в "0" счетчики 4-8 и регистры 13 — 15, ! åíåðàòîð 21 импульсов формирует последовательность импульсов, частота которой делится на два делителем 22 частоты. По сигналу пуска по входу 41 триггер 24 устанавливается в единичное состояние по переднему фронту импульса, поступающему с делителя 22„ Единичное состояние триггера 24 разрешает прохождение импульсов синхронизации на выход элемента

И 30.

Импульсы, поступающие на информационный вход регистра 23 сдвига,сдвигаются в нем по сигналам, поступающим с генератора 21 импульсов. Для синхронизации узлов устройства используюrcя тактовые импульсы, снимаемые с второго и четвертого выходов регистра 23 сдвига.

В устройстве реализован конвейерный режим работы„

1524067 стра 15. (Если нулевая точвышла за границь1 исходното в триггер 26 эанесетлевым) реги ка апертуры го массива, ся лог."1" татор 19 та пит лог „"0" обеспечивае которая переключит комму5 к, что на его выходы постус вторых входов, чем и тся исключение точек из анализа при выходе апертуры за границы исходного массива). Fñëè первое число на выходе коммутатора 19 больше содержимого регистра 15, блок 17 сравнения сформирует на своем выходе единичный уровень„ который разрешит прохождение через элемент И 31 перво- !5

ro импульса с четвертого выхода регис rpa 23 сдвига, который, поступив на вход записи регистра 15, обеспечит запись большего числа в регистр 15.

Если число меньше или равно содержимо-20 му регистра 15, на выходе блока 17 сравнения — низкий уровень и в регистре 15 останется предыдущее число.

В этом же такте в регистры 11 и 12 заносится адрес второй точки аперту- 25 ры, а в регистр lб записывается значение первой точки апертуры.

Одновременно с занесением текущего максимального числа в регистр

15, его номер в апертуре заносится в 30 регистр 13 по импульсу с выхода элемента И 31. В последующих тактах устройство работает аналогично, По К-му импульсу в регистры ll и 12 заносится адрес последней (К-й) точки апер35 туры, а на выходе переноса счетчика

5 формируется импульс переноса, Одновибратор 27 формирует импульс, длительность которого выбирается такой, чтобы обеспечить надежное исключение 40 одного тактового импульса. Гигнал с выхода одновибратора 27 поступает через элемент НЕ 38 на третий вход элемента И 30 и обеспечивает исключение следующего тактового импульса, 45

По К-му импульсу с второго выхода регистра 23 сдвига в регистр 16 заносится значение (К-l)-й точки апертуры, По переднему фронту К-ro импульса с четвертого выхода регистра 23 сдвига заносится (К-1)-е число в регистр е5 (при условии, что оно больше текущего значения регистра 15), Таким образом, в регистре 15 оказывается наибольшее число в аперту55 ре, а в регистре 13 — его порядковый номер в апертуре„На выходе переноса счетчика 6 формируется импульс переноса, по переднему фронту которого одновнбратор 28 формирует короткий импульс. Номер наибольшего числа иэ регистра 13 поступает па входы дешифратора 18, на i-м выходе которого появляется уровен| лог, ! п!хи условии, что i-e число в апертуре имеет наибольшее значение), который разрешает прохождение импульса с выхода одновибратора 28 через 1 и элеменч И группы 29 и обеспечивает установку

i-го триггера регистра 14 в единичное состояние, В следующих проходах агертуры i-й элемент в определении максимального числа не будет участвовать, потому что когда счетчик б буде а име I L значение 1 коммутатор 20 пропустит на выход !" пз i-го триггера регистра !4 и через элемент

ИЛИ 37 переключит коммутатор !9 на входы, на которые подаются нули.

Импульс с выхода одновибратора 28 проходит элемент 39 задержки и элемент ИЛИ 34 и сбрасывает регистр !5.

Во втором цикле определяется второе по величине число.

К+1

В ----м цикле ка «ыходе перенс2 се счетчика 4 формируе-тся сигHïë. который поступает на первые входы злсментов И 32 и 33.

В регистр 15 вь.бирается медиана.

Импульс с выхода одновибратора 28 проходит через элемент И 32 на выход 43 и разрешает выборку первого результата„ После задержки элементом

39 задержки на время достаточное для снятия результата с выходов 44 устройства производится сброс регистУ ра 1 5 ° Импульс, задержанный элементом 39 задержки, проходит также через элемент V 33 (на второй вход которого поступает разрешение с выхода переноса счетчика 4 и элемент ИЛИ

36 и сбрасывает регистр 15, По импульсу с выхода счетчика 4 производится прибавление единипы к содержимому счетчика 8, т. е, формируется адрес следующей центральной точ;;и и аналогично определяется в оран медиана и т.д. !!осле отработки последней точ;-и массива на выходе переноса с -Ip". ÷èêà

7 формируется сигнал, который сбрасывает триггер 24 и поступает на вы-ход 4? окончания работы устройства.

9 15240

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

Устройство для медианной фильтрации двумерных массивов, с одержащее

5 четыре счетчика, два одновибратора, три блока памяти, элемент задержки, три регистра, элемент HF, два сумматора первый триггер, два коммутатора, блок сравнения, группу элементов

И, дешифратор, четыре элемента И, три элемента ИЛИ, генератор тактовых импульсов, причем выход переноса первого счетчика через первый одновибратор соединен с первыми входами эле- 15 ментов И группы, с первым входом первого элемента И и через элемент задержки - с первым входом первого элемента ИЛИ, выходы первого и второго блоков памяти подключены к первым 20 входам соответственно первого и второго сумматоров, выходы знаковых разрядов которых соединены с входами второго элемента ИЛИ, выход первого коммутатора подключен к информационно-25 му входу первого регистра и к первому входу блока сравнения, выход "Больше" которого соединен с первым входом второго элемента И, выход которого подключен к входам управления записью-3Q считыванием второго и первого регистров, выход первого регистра соединен с вторым входом блока сравнения и является информационным выходом устройства, выход второго регистра через 35 дешифратор подключен к вторым входам элементов И группы, выходы которых соединены с информационными входами третьего регистра, выход которого подключен к информационному входу вто-4Q рого коммутатора, вьжод второго счетчика соединен с входом второго одновибратора, информационные выходы третьего и че твертого сче тчик ов подключены к вторым входам, вьжод пере- 45 носа четвертого счетчика соединен со счетным входом третьего счетчика, выход элемента НЕ подключен к первому входу третьего элемента И, вход установки третьего регистра соединен с 50 выходом второго элемента ИЛИ, первый вход которого соединен с входами установки второго регистра, с первого по четвертый счетчиков, с вторым входом первого элемента ИЛИ и является входом начальной установки устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены пятый счетчик, 67 0 три регистра, регистр сдвига, два триггера, четвертый элемент ИЛИ и делитель частоты, вход которого соединен с входом управления сдвигом регистра сдвига и подключен к выходу генератора тактовых импульсов, а выход соединен с вторым входом третьего элемента И и с входом синхронизации первого триггера, входом установки в "1" которого является вход пуска устройства, прямой выход первого триггера подключен к третьему входу третьего элемента И, выход которого соединен с информационным входом регистра сдвига, с нулевым входом второго триггера, с входами синхронизации четвертого и пятого регистров и со счетным входом второго счетчика, выход которого подключен к адресным входам первого и второго блоков памяти, выход второго одновибратора соединен с входом элемента НЕ и со счетным входом пятого счетчика, вход начальной установки которого подключен к входу начальной установки устройства, а выход соединен со счетным входом четвертого счетчика, с вторым входом первого элемента И и с первым входом четвертого элемента И выход которого подключен к второму входу второго элемента ИЛИ, выход первого одновибратора через элемент saдержки соединен с вторым входом четвертого элемента И, выходы четвертого и пятого регистров подключень1 к адресным входам третьего блока памяти, выход которого соединен с информационным входом шестого регистра, выход которого подключен к информационному входу первого коммутатора, выход второго разряда регистра сдвига соединен с входом синхронизации шестого регистра и с нулевым входом третьего триггера, прямой выход которого подключен к первому входу третьего элемента ИЛИ, выход которого соединен с управляющим входом первого коммутатора, выход последнего разряда регистра сдвига подключен к второму входу второго элемента И и к счетному входу первого счетчика, выход которого сЬединен с информационным входом второго регистра и с управляющим входом второго коммутатора, выход которого подключен к второму входу третьего элемента ИЛИ, выход переноса третьего счетчика соединен с нулевым входом первого триггера, и яв1524067 12 та первой выборки является выход первого элемента И, ляется выходом окончания работы устройства, выходом индикации результаСоставитель С.Ионкин

Редактор А.Шандор Техред М.Ходанич

Корректор Т,Палий

Заказ 7045/51 Тираж 668 Подписное

-ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101