Устройство для медианной фильтрации двумерных массивов Советский патент 1989 года по МПК G06F17/18 

ff

ел

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

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

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

Устройство содержит блоки 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 задержки, v вход 40 начальной установки, вход 41 пуска, выход 42 окончания работы устройства, выход 43 индикации резуль тата первой выборки, информационный выход 44 устройства.

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

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

3 памяти через регистр 16 соединены с первой группой входов коммутатора 19, вторая группа входов которого подключена к уровню лог„ О. Выходы коммутатора 19 соединены с первой группой входов блока 17 сравнения и информационными входами регистра 15, выходы которого являются выходами 44 устройства и соединены с второй rfiyn- пой входов блока 17 сравнения о Выход переноса счетчика 5 соединен через одновибратор 27 со счетным входом счетчика 4 и через элемент НЕ 38 с третьим входом элемента И 30, выход которого соединен с информационным входом регистра 23 сдвига, входами записи триггера 25, регистров 1 1 и 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 сравнения соединен с первым входом элемента И 31, выход которого соединен с входами записи регистров 13 и 15. Вход сброса регистра 15 соединен с выходом элемента ИЛИ 34. Второй выход регистра 23 сдвига соединен с входами записи триггера 26 и регистра 16. Четвертый выхо регистра 23 сдвига соединен со счетны входом счетчика 6 и вторым входом элемента И 31„ Выход элемента И 32 является выходом 43 устройства.

Устройство предназначено для медианной фильтрации двумерных массивов данных размером mxn, m - число строк, п - число столбцов, где т 2 , Р, S - целые положительные числа Апертура фильтра может быть произвольной. Число точек, входящих в апертуру, равно К (К - нечетное).

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

Среди элементов массива, входявшх в в апертуру, находится медиана и она заменяет центральную точку апертуры. После этого апертура сдвигается и но- 15 вая центральная точка заменяется медианой. Направление сдвига апертуры: слева направо и сверху вниз.

Счетчики 5 и 6 являются счетчиками с пересчетом К, счетчик 4 - с 20

K-t-l

пересчетом ---, счетчик 7 - двоичный счетчик разрядности Р, счетчик 8 - двоичный счетчик разрядности S.

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

Исходный массив хранится в блоке 3 памятио Пронумеруем точки, входящие в апертуру от О до К. Тогда в блоке I памяти по i-му адресу хра25

30

35

НИИ или отрицательном результате, т.е. выходе части апертуры за размер исходного массива.

Устройство работает следуюпшм образом.

По сигналу начальной установки АО сбрасываются в О счетчики 4-8 и ре гистры 13 - 15,

Генератор 21 импульсов формирует последовательность импульсов, частота которой делится на два делителем 22 частоты. По сигналу пуска по входу 41 триггер 24 устанавливается в единичное состояние по переднему фронту импульса, поступающему с делителя 22 Единичное состояние триггера 24 разрешает прохождение импуль сов синхронизации на выход элемента И 30.

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

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

В первом такте по первому тактовому импульсу к содержимому счетчика 5 прибавляется единица, в регистры И и 12 заносятся старшие и младшие разряды адреса нулевой точки апертуры, полученные сложением адреса цент ральной точки, который хранится в счетчиках 7 и 8, и смещений, считаннится смещение i-й точки апертуры от- 40 блоков 1 и 2 памяти (смещение

по строкам и смещение по столбцам). Если текущая точка в апертуре выходит за границы исходного массива то хотя бы в одном знаковом разряде дг сумматоров 9 или 10 будет сигнал

носительно центральной точки апертуры по строкам, а в блоке 2 памяти - по столбцам. .Смещение представляет собой число со знаком в дополнительном коде, причем под знак отводится два разряда.

В счетчиках 7 и 8 содержится текущий адрес центральной точки апертуры (номер строки и номер столбца соответственно). Суммирование текущего адреса центральной точки со смещением в сумматорах 9 и 10 позволяет полу чать абсолютные адреса точек, входящих в апертуру, для различных значений адреса центральной точки. При этом наличие хотя бы однрй 1 на выходе знаковых разрядов сумматоров 9 и 10 (знак представляется двумя разрядами ) свидетельствует о переполне

5

0

5

0

5

НИИ или отрицательном результате, т.е. выходе части апертуры за размеры исходного массива.

Устройство работает следуюпшм образом.

По сигналу начальной установки АО сбрасываются в О счетчики 4-8 и регистры 13 - 15,

Генератор 21 импульсов формирует последовательность импульсов, частота которой делится на два делителем 22 частоты. По сигналу пуска по входу 41 триггер 24 устанавливается в единичное состояние по переднему фронту импульса, поступающему с делителя 22 Единичное состояние триггера 24 разрешает прохождение импульсов синхронизации на выход элемента И 30.

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

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

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

по строкам и смещение по столбцам). Если текущая точка в апертуре выходит за границы исходного массива то хотя бы в одном знаковом разряде сумматоров 9 или 10 будет сигнал

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

/1524067

левым) регистра 15. (Если нулевая точка апертуры вышла за rpaHHi ii исходного массива, то в триггер 26 занесется лог. М, которая переключит коммувш о а

татор 19 так, что на его выходы поступит лог с вторых входов, чем и - обеспечивается исключение точек из анализа при выходе апертуры за границы исходного массива). Если первое Q число па выходе коммутатора 19 больше содержге-1ого регистра 15, блок 17 сравнения сформирует на своем выходе единичный уровень, который разрешит

одновибратор 28 4 прмирует короткий nMnyjifjC. Номер наибольшего числа из регистра 13 поступает на входы дешифратора 18, на i-M выходе которого появляется уровень лог, при условии, что i-e число } япертуре имеет наибольшее значение, который разрешает прохождение импульса с выхода одновибратора 28 через i-й элемент И группы 29 и обеспечивает установку i-ro триггера регистра 14 в единичное состояние, В следующих проходах апертуры 1-й элемент в определении

Изобретение относится к вычислительной технике и может быть использовано при обработке двумерных массивов данных. Целью изобретения является повышение быстродейтсвия. Устройство содержит блоки 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 ил.

прохождение через элемент И 31 перво- (5 максимального числа не будет участ

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

15 этом же такте в регистры 11 и 12 заносится адрес второй точки апертуры, а в регистр 16 записывается значение первой точки апертурЫо

Одновременно с занесением текущего максимального числа в регистр 15, его номер в апертуре заносится в регистр 13 по импульсу с выхода элемента И 31. В последующих тактах уст- poficTBo работает аналогично. По К-му импульсу в регистры 11 и 12 заносится адрес последней (К-й) точки апертуры, а на выходе переноса счетчика 5 формируется импульс переноса. Одно- вибратор 27 формирует импульс, длительность которого выбирается такой, чтобы обеспечить надежное исключение одного тактового импульса Сигнал с выхода одноБибратора 27 поступает через элемент НЕ 38 на третий вход элемента И 30 и обеспечивает исключение следующего тактового импульса о

По К-му импульсу с второго выхода регистра 23 сдвига в регистр 16 заносится значение ()-й точки апертуры. По переднему«фронту К-го импульса с четвертого выхода регистра 23 сдвига заносится (К-1)-е число в регистр 45 (при условии, что оно больше текущего значения регистра 15).

Таким образом, в регистре 15 оказывается наибольшее число в апертуре, а в регистре 13 - его порядковый номер в апертуре На выходе переноса счетчика 6 формируется импульс переноса, по переднему фронту которого

5

0

5

д

0

5

0

5

вовать, потому что когда счетчик 6 будет иметь значение i, коммутатор 20 пропустит на выход 1 из i-ro триггера регистра 14 и через злемент ИЛИ 37 переключит коммутатор 19 на входы, на которые подаются нули,

Импульс с выхода одновибратора 28 проходит элемент 39 задержки и элемент ИЛИ 34 и сбрасывает регистр 15, Во втором пикле определяется второе по величине число,

К+1 В -г.-м цикле ь:а },ыходе пбрено са счетчика 4 формируется сигнал, который поступает па первые входы элементов И 32 и 33.

В регистр 15 выбирается медиана. Импульс с выхода одповибратора 28 проходит через элемент И 32 иа выход 43 и разрешает выборку первого результата„ После задержки элементом 39 задержки на время,достаточное для снятия результата с выходов 44 устройства.производится сброс регистра 15, Импульс, задержанный элементом 39 задержки, проходит также через элемент И 33 {на второй вход которого поступает разрешение с выхода переноса счетчика 4) и элемент ИЛИ 36 и сбрасывает регистр 15, По импульсу с выхода счетчика 4 производится прибавление единипы к содержимому счетчика 8, т„е, формируется адрес следующей центральной точки и аналогично определяется нторая медиана и т.д.

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

Формула ня

9 о б

15

р е т е н и я

Устройство для медианной фильтрации двумерных массивов, содержащее четыре счетчика, два одновибратора, три блока памяти, элемент задержки, три регистра, элемент НЕ, два сумматора первый триггер, два коммутатора, блок сравнения, группу элементов И, дешифратор, четыре элемента И, три элемента ШШ, генератор тактовых импульсов, причем выход переноса первого счетчика через первый одновиб- ратор соединен с первыми входами эле- ментов И группы, с первым входом первого элемента И и через элемент задержки - с первым входом первого элемента ИЛИ, выходы первого и второго блоков памяти подключены к первым входам соответственно первого и второго сумматоров, выходы знаковых разрядов которых соединены с входами второго элемента ИЛИ, выход первого

коммутатора подключен к информационно-25 вход начальной установки которого

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

45

дешифратор подключен к вторым входам элементов И группы, выходы которых соединены с информационными входами третьего регистра, выход которого подключен к информационному входу вто-40 рого коммутатора, выход второго счетчика соединен с входом второго одно- вибратора, информационные выходы третьего и четвертого счетчиков подключены к вторым входам, выход переноса четвертого счетчика соединен со счетным входом третьего счетчика, выход элемента НЕ подключен к первому входу третьего элемента И, вход уста- нойки третьего регистра соединен с выходом второго элемента ИЛИ, первый вход которого соединен с входами установки второго регистра, с первого по четвертый счетчиков, с вторым входом первого элемента ИЛИ и является входом начальной установки устройства, отличающееся тем.

и пятого регистров подключены к адресным входам третьего блока памяти, выход которого соединен с информационным входом PiecToro регистра, выход которого подключен к информационному входу первого коммутатора, выход второго разряда регистра сдвига соединен с входом синхронизации шестого регистра и с нулевым входом третьего триггера, прямой выход которого подключен к первому входу третьего элемента ИЛИ, выход которого соединен с управляющим входом первого коммутатора, выход последнего разря- 50 да регистра сдвига подключен к второму входу второго элемента И и к счетному входу первого счетчика, выход которого соединен с информационным входом второго регистра и с управляющим входом второго коммутатора, выход которого подключен к второму входу третьего элемента ИЛИ, выход переноса третьего счетчика соединен с нулевым входом первого триггера, и явЬ5

что, с целью повышения быстродействия, в него введены пятый счетчик.

152ДП67

10

три регистра, регистр сдвига, два триггера, четвертый элемент ИЛИ и делитель частоты, вход которого соединен с входом управления сдвигом регистра сдвига и подключен к выходу генератора тактовых импульсов, а выход соединен с вторым входом третьего элемента И и с входом синхронизации первого триггера, входом установки в 1 которого является вход пуска устройства, прямой выход первого триггера подключен к третьему входу третьего элемента И, выход которого соединен с информационным входом регистра сдвига, с нулевым входом второго триггера, с входами синхронизации четвертого и пятого регистров и со счетным входом второго счетчика, выход которого подключен к адресным входам первого и второго блоков памяти, выход второго одновибратора соединен с входом элемента НЕ и со счетным входом пятого счетчика,

подключен к входу начальной установки устройства, а выход соединен со счетным входом четвертого счетчика, с вторым входом первого элемента И и с первым входом четвертого элемента И , выход которого подключен к второму входу второго элемента ИЛИ, выход первого одновибратора через элемент задержки соединен с вторым входом чет

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

1 152406712

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