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

,1511 4 Г 06 Г 15/3 ГОСУДАРСТВЕНН ПО ИЗОБРЕТЕНИЯ ПРИ ГКНТ СССР НО МИТЕ ОТНРЫТ 1 ТН ПИСАНИЕ ИЗОБРЕТ ВТОРСКО пользовано при о массивов данных,аботке двумерных елью изобретения М: 43ч и В,М,Крищигпн тво ГСГР1978,о СССР6, 1985,ель 7/О ельс Р 5 МЕДИАННОЙ фИЛВТИВОВ сится к выч ыть исож(54) УСТРОЙСТВО ДГЯРАЦИИ ДВУМЕРНЫХ МА(57) Изобретение олительной технике СВИДЕТЕЛЬСТВУ является повышениУстройство содержити, счетчики 4-8,регистры 11 - 16, бдешифратор 18, комгенератор 21 тактлитель 22 частотыга, триггеры 24-227, 28 группу элемменты И 30-33, элэлемент НЕ 38, эл1 ил,быстродействия, т блоки 1-3 памясумматоры 9, 10, ок 17 сравнения, мутаторы 19, 20, вых импульсов, дерегистр 23 сдвиодновибраторы ентов И 29, элементы КПИ 34-37, мент задержки 39,Изобретение относится к вычислительной технике и предназначенодля использования в специализированных вычислительных устройствахпри обработке двумерных массивовданных например, при обработкеиэображений.Целью изобретения является повышение быстродействия, 10На чертеже представлена функциональная схема устройства,Устройство содержит блоки 1-3 памяти, счетчики 4-8, сумматоры 9 и1 О, регистры 11-16, блок 17 сравнения, дешифратор 18, коммутаторы 19и 20, генератор 21 тактовых импульсов, делитель 22 частоты, регистр 23сдвига, триггеры 24-26, одновибраторы 27 и 28, группу элементов И 29, 20элементы И 30-33, элемент ИЛИ 34-37,элемент НЕ 38, элемент 39 задержки,вход 40 начальной установки, вход41 пуска, выход 42 окончания работыустройства, выход 43 индикации резуль тата первой выборки, информационныйвыход 44 устройства,Вход 40 начальной установки соединен с входами сброса счетчиков 4-8,регистра 13 и с первыми входами 30элементов ИЛИ 34, 36, Выход генератора 21 импульсов соединен с входом синхронизации регистра 23 сдвига и вхо.дом делителя 22 частоты, выход которого соединен с синхровходом триггера 24 и первым входом элемента И 30,второй вход которого соединен с выходом триггера 24, Информационные выходы счетчика 5 соединены с адресными входами блоков 1 и 2 памяти, выходы которых соединены соответственно спервыми группами входов сумматоров 9и 10, вторые группы входов которых соединены соответственно с информационными выходами счетчиков 7 и 8. Выходы 45сумм сумматоров 9 и 10 соединены через регистры 11 и 12 соответственнос группами старших и младших разрядовадресного входа блока 3 памяти,50Выходы знаковых разрядов сумматоров 9 и 10 соединены с первого по четвертый входами элемента ИЛИ 35. Выход элемента ИЛИ 35 соединен через триггеры 25 и 26 с первым входом элемента55 КПИ 37, выход которого соединен с управляющим входом коммутатора 19, Выход коммутатора 20 соединен с вторым входом элемента ИЛИ 37, Выходы блока 3 памяти через регистр 1 б соединены с первой группой входов коммутатора 19, вторая группа входов которого под - ключена к уровню лог, 0", Выходы коммутатора 19 соединены с первой группой входов блока 17 сравнения и информационными входами регистра 15, выходы которого являются выходами 44о устройства и соединены с второй группой входов блока 17 сравнения, Выход переноса счетчика 5 соединен через одновибратор 27 со счетным входом счетчика 4 и через элемент НЕ 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 сравнения соединен с первым входом элемента И 31,выход которого соединен с входами записи регистров 13 и 15, Вход сбросарегистра 15 соединен с выходом элемента ИЛИ 34, Второй выход регистра 23сдвига соединен с входами записи триггера 26 и регистра 16. Четвертый выходрегистра 23 сдвига соединен со счетнымвходом счетчика 6 и вторым входомэлемента И 31. Выход элемента И 32 является выходом 43 устройства,В первом такте по первому тактовому импульсу к содержимому счетчика5 прибавляется единица, в регистры11 и 12 заносятся старшие и младшиеразряды адреса нулевой точки апертуры, полученные сложением адреса центральной точки, который хранится всчетчиках 7 и 8, и смещений, считанных из блоков 1 и 2 памяти (смещениепо строкам и смещение по столбцам),Если текущая точка в апертуре вьгходит за границы исходного массива,то хотя бы в одном знаковом разрядесумматоров 9 или 10 будет сигналлог, "1", который, пройдя через элемент ИЛИ 35, занесется в триггер 25 по первому тактовому импульсу, По сформированному адресу из блока 3памяти считывается соответствующее число и заносится в регистр 16 по первому тактовому импульсу с второго выхода регистра 23 сдвига, а в триггер 26 переписывается содержимое триггера 25, В этом же такте в регистры 1 и 12 заносится адрес первой точки апертуры по второму импульсу, Первое число проходит через коммутатор 19 и сравнивается с содержимбм (ну 15240Устройство предназначено для медианной фильтрации двумерных массивовданных размером ш х и, пг - число строк,Р 5,и - число столбцов, где ш = 2, и = 2Р, Б - целые положительные числа,Апертура фильтра может быть произвольной, Число точек, входящих в апертуру равно К (К - нечетное),Алгоритм работы устройства следующий.Среди элементов массива, входящих вв апертуру, находится медиана и оназаменяет центральную точку апертуры,После этого апертура сдвигается и новая центральная точка заменяется медианой, Направление сдвига апертуры: слева направо и сверху вниз,Счетчики 5 и 6 являются счетчиками с пересчетом К, счетчик 4 - с 20К+1пересчетом -, счетчик 7 - двоичный счетчик разрядности Р, счетчик8 - двоичный счетчик разрядности 8,Разрядность блоков памяти 1 и 2 25определяется числом К и формой аггер -туры, Разрядность блока 3 памяти, блока 17 сравнения, коммутатора 19 и регистров 15 и 16 определяется разрядностью обрабатываемых данных, Разрядность регистра 13 равна разрядности счетчика 6, Количество выходовдешифратора 18, элементов И группы29, разрядность регистра 4 и числовходов коммутатора 20 равно К,Исходный массив хранится в блоке3 памяти, Пронумеруем точки, входящие в апертуру от 0 до К, Тогда вблоке 1 памяти по 1-му адресу хранится смещение 1-й точки апертуры относительно центральной точки апертуры по строкам, а в блоке 2 памятипо столбцам,.Смещение представляетсобой число со знаком в дополнительном коде, причем под знак отводится 45два разряда,В счетчиках 7 и 8 содержится текущий адрес центральной точки апертуры(номер строки и номер столбца соответственно). Суммирование текущегоадреса центральной точки со смещением в сумматорах 9 и 10 позволяет получать абсолютные адреса точек, входящих в апертуру, для раэличных значений адреса Центральной точки, Приэтом наличие хотя бы одной "1" на выходе знаковых разрядов сумматоров 9и 10 (знак представляется двумя разрядами ) свидетельствует о переполнениц или отрицательном результате,т.е, выходе части апертуры за размерыисходного массива.Устройство работает следующим образом,По сигналу начальной установки 40сбрасываются в "0" счетчики 4-8 и регистры 13 - 15,енератор 21 импульсов формируетпоследовательность импульсов, частота которой делится на два делителем 22 частоты, По сигналу пуска повходу 41 триггер 24 устанавливаетсяв единичное состояние по переднемуфронту импульса, поступающему с делителя 22 Единичное состояние триггера 24 разрешает прохождение импульсов синхронизации на выход элементаИ 30,Импульсы, поступающие на информационный вход регистра 23 сдвига,сдвигаются в нем по сигналам, поступающим с генератора 21 импульсов, Длясинхронизации узлов устройства используются тактовые импульсы, снимаемыес второго и четвертого выходов регистра 23 сдвига,В устройстве реализован конвейерный режим работыстра 15. (Если нулевая точвышла за границь 1 исходното в триггер 26 эанесетлевым) реги ка апертуры го массива, ся лог,"1", тдтор 19 та пит лог"0" обеспечивде которая переключит комму 5 к, что на его выходы постус вторых входов, чем и тся исключение точек из анализа при выходе апертуры за границы исходного массива), Если первоечисло на выходе коммутатора 19 больше содержимого регистра 15, блок 17сравнения сформирует на своем выходеединичный уровень который разрешитпрохождение через элемент И 31 первого импульса с четвертого выхода регистра 23 сдвига, который, поступивна вход записи регистра 15, обеспечитзапись большего числа в регистр 15,Если число меньше или равно содержимо му регистра 15, на выходе блока 17сравнения - низкий уровень и в регистре 15 останется предыдущее число.В этом же такте в регистры 11 и 12заносится адрес второй точки апертуры, а в регистр 16 записывается значение первой точки апертуры.Одновременно с занесением текущего максимдльного числа в регистр15, его номер в апертуре заносится в 30регистр 13 по импульсу с выхода элемента И 31, В последующих тактах устройство работает аналогично, По К-муимпульсу в регистры 11 и 12 заносится адрес последней (К-й) точки апер 35туры, а на выходе переноса счетчика5 формируется импульс переноса, Одновибратор 27 формирует импульс, длительность которого выбирается такой,чтобы обеспечить надежное исключениеодного тактового импульса, Гигнал свыхода одновибратора 27 поступает через элемент НЕ 38 на третий вход элемента И 30 и обеспечивает исключение следующего тактового импульса,По К-му импульсу с второго выходарегистра 23 сдвига в регистр 16 заносится значение (К)-й точки апертуры, По переднему фронту К-го импульсас четвертого выхода регистра 23 сдвига заносится (К)-е число в регистр1 5 (при условии, что оно больше текущего значения регистра 15),Таким образом, в регистре 15 оказывается наибольшее число в аперту 5ре, а в регистре 13 - его порядковыйномер в апертуре На выходе переносасчетчика 6 формируется импульс переноса, по переднему фронту которого одновибрдтор 28 формирует короткий импульс, Номер наибольшего числа иэ регистра 3 поступает на входы дешифраторд 18, на 1-м выходе которого появляется уровень лог,при условии, что 1-е число в апертуре имеет наибольшее значение), который разрешает прохождение импульса с выхода одновибраторд 28 через 1-й элеменч И группы 29 и обеспечивает установку 1-го триггера регистра 14 в единичное состояние, В следующих проходах дгертуры 1.-й элемент в определении максимального числа не будет участвовать, потому что когда счетчик б буде а иметь значение 1, коммутатор 20 пропустит нд выход " пз 1-го триггера регистра 4 и через злемепт ИЛИ 37 переключит коммутатор 9 навходы, на которые поддются нули,Импульс с выхода одновибратора 28 проходит элемент 39 задержки и элемент ИЛИ 34 и сбрасывает регистр 5, Во втором цикле определяется второепо величине число,К+1В м цикле ца ыходе перено 2сд счетчика 4 формируется сигнал,который поступает пд первые входызлсментов И 32 и 33.В регистр 5 выбирается медиана, Импульс с выхода одновибрдтора 28 проходит через элемент И 32 на выход 43 и разрешает выборку первого результата После задержки элементом 39 задержки на время достаточное для снятия результата с выходов 44 устройства производится сброс регистУра 15Импульс, задержанный элементом 39 задержки, проходит также через элемент И 33 (на второй вход которого поступает разрешение с выхода переноса счетчика 4и элемент ИЛИ/36 и сбрасывает регистр 15, По импульсу с выхода счетчика 4 производится прибавление единицы к содержимому счетчика 8, т.е, формируется адрес следующей центральной точки и аналогично определяется в оран медиана ит.д.После отработки последней точки массива нд выходе переноса сче".чикд 7 формируется сигнал, который сбрасывает триггер 24 и поступает нд вы-. ход 42 окончания работы устройства,Устройство для медианной фильтрации двумерных массивов, содержащее5 четыре счетчика, два одновибратора, три блока памяти, элемент задержки, три регистра, элемент НЕ, два сумматорапервый триггер, два коммутатора, блок сравнения, группу элементов И, дешифратор, четыре элемента И, три элемента ИЛИ, генератор тактовых импульсов, причем выход переноса первого счетчика через первый одновибратор соединен с первыми входами эле ментов И группы, с первым входом первого элемента И и через элемент задержки - с первым входом первого элемента ИЛИ, выходы первого и второго блоков памяти подключены к первым 20входам соответственно первого и второго сумматоров, выходы знаковых разрядов которых соединены с входами второго элемента ИЛИ, выход первого коммутатора подключен к информационному входу первого регистра и к первому входу блока сравнения, выход "Больше" которого соединен с первым входом второго элемента И, выход которого подключен к входам управления записью.30считыванием второго и первого регистров, выход первого регистра соединен с вторым входом блока сравнения и является информационным выходом устройства, выход второго регистра через З 5 дешифратор подключен к вторым входам элементов И группы, выходы которых соединены с информационными входами третьего регистра, выход которого подключен к информационному входу вто.40 рого коммутатора, выход второго счетчика соединен с входом второго одновибратора, информационные выходы третьего и четвертого счетчиков подключены к вторым входам, вьжод пере носа четвертого счетчика соединен со счетным входом третьего счетчика, выход элемента НЕ подключен к первому входу третьего элемента И, вход установки третьего регистра соединен с 50 выходом второго элемента ИЛИ, первый вход которого соединен с входами установки второго регистра, с первого по четвертый счетчиков, с вторым входом первого элемента ИЛИ и является входом начальной установки устройства,отличающееся тем, что, с целью повышения быстродействия, в него введены пятый счетчик,67 10три регистра, регистр сдвига, два триггера, четвертый элемент ИЛИ и делитель частоты, вход которого соединен с входом управления сдвигом регистра сдвига и подключен к выходу генератора тактовых импульсов, а выход соединен с вторым входом третьего элемента И и с входом синхронизации первого триггера, входом установки в "1" которого является вход пуска устройства, прямой выход первого триггера подключен к третьему входу третьего элемента И, выход которого соединен с информационным входом регистра сдвига, с нулевым входом второго триггера, с входами синхронизации четвертого и пятого регистров и со счетным входом второго счетчика, выход которого подключен к адресным входам первого и второго блоков памяти, выход второго одновибратора соединен с входом элемента НЕ и со счетным входом пятого счетчика, вход начальной установки которого подключен к входу начальной установки устройства, а выход соединен со счетным входом четвертого счетчика, с вторым входом первого элемента И и с первым входом четвертого элемента Ивыход которого подключен к второму входу второго элемента ИЛИ, выход первого одновибратора через элемент задержки соединен с вторым входом четвертого элемента И, выходы четвертого и пятого регистров подключены к адресным входам третьего блока памяти, выход которого соединен с информационным входом шестого регистра, выход которого подключен к информационному входу первого коммутатора, выход второго разряда регистра сдвига соединен с входом синхронизации шестого регистра и с нулевым входом третьего триггера, прямой вьжод которого подключен к первому входу третьего элемента ИЛИ, выход которого соединен с управляющим входом первого коммутатора, выход последнего разряда регистра сдвига подключен к второму входу второго элемента И и к счетному входу первого счетчика, выход которого сЬединен с информационным входом второго регистра и с управляющим входом второго коммутатора, выход которого подключен к второму входу третьего элемента ИЛИ, выход переноса третьего счетчика соединен с нулевым входом первого триггера, и яв1 524061 12та первой выборки является выход первого элемента И,ляется выходом окончания работы устройства, выходом индикации результаСоставитель С,ИонкинРедактор А.Шандор Техред М.Ходанич Корректор т.Палий Заказ 7045/51 Тираж 668 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г,ужгород, ул. Гагарина,101