Одномерный медианный фильтр с модульной архитектурой
Владельцы патента RU 2362209:
Государственное образовательное учреждение высшего профессионального образования Московский государственный институт электронной техники (технический университет) (RU)
Изобретение относится к специализированным средствам вычислительной техники и может быть использовано в системах, в которых требуется аппаратная реализация алгоритмов цифровой фильтрации сигналов. Техническим результатом является повышение быстродействия медианного фильтра с любой нечетной длиной апертуры на базе модульной архитектуры, позволяющей вычислять медиану на каждом такте работы схемы. Устройство содержит N элементов задержки входного сигнала, соединенных последовательно, N модулей упорядочивания и хранения отсчетов, каждый из которых состоит из коммутатора шины, двух компараторов, регистра и комбинационной схемы, предназначенной для управления пересылками данных между модулями на основе логической обработки результатов сравнения входных кодовых сигналов и управляющих сигналов от двух соседних модулей. 2 ил., 6 табл.
Изобретение относится к специализированным средствам вычислительной техники и может быть использовано в системах, в которых требуется аппаратная реализация алгоритмов цифровой фильтрации сигналов.
Известен цифровой медианный фильтр [1], состоящий из узлов подсчета числа выборок, узлов упорядочивания чисел, компаратора, блока управления и тактового генератора.
Известный медианный фильтр производит упорядочивание отсчетов при помощи одного компаратора, что ограничивает частоту поступления отсчетов входного сигнала.
Наиболее близким техническим решением к предлагаемой модульной архитектуре медианного фильтра является устройство [2], включающее элементы задержки входного сигнала, блок поиска максимального и минимального элементов и блок выбора рекурсивной медианы.
Недостатком известного рекурсивного медианного фильтра является большое количество последовательно включенных коммутаторов максимума и минимума, которые представляют собой комбинационные схемы, что снижает быстродействие фильтра. Кроме того, данное устройство реализует не классический алгоритм медианной фильтрации [3], а рекурсивный.
Задача изобретения - быстродействующая аппаратная реализация медианного фильтра с любой нечетной длиной апертуры на базе модульной архитектуры, позволяющей вычислять медиану на каждом такте работы схемы и обеспечивающей линейный рост аппаратных затрат при увеличении длины апертуры.
Это достигается тем, что в одномерный медианный фильтр с модульной архитектурой, содержащий N элементов задержки входного сигнала, ко входу 1-го элемента задержки подключена шина входного сигнала, вход i-го элемента задержки соединен с выходом (i-1)-го элемента задержки, отличающийся тем, что в него введены N модулей упорядочивания и хранения отсчетов, каждый из которых состоит из коммутатора шины, двух компараторов, регистра и комбинационной схемы, при этом тактовый сигнал и сигнал предварительной установки соединены с тактовым входом и входом предварительной установки i-го элемента задержки и i-го модуля упорядочивания и хранения отсчетов, шина входного сигнала и шина с выхода N-го элемента задержки подключены к первому и второму кодовым входам каждого модуля упорядочивания и хранения отсчетов, третий и четвертый кодовые входы i-го модуля упорядочивания и хранения отсчетов соединены с кодовыми выходами (i-1)-го и (i+1) модуля упорядочивания и хранения отсчетов соответственно, третий кодовый вход 1-го модуля упорядочивания и хранения отсчетов и четвертый кодовый вход N-го модуля упорядочивания и хранения отсчетов остаются не подключенными, первый и второй управляющие входы i-го модуля упорядочивания и хранения отсчетов соединены с первым и третьим управляющими выходами (i-1)-го модуля упорядочивания и хранения отсчетов, третий и четвертый управляющие входы i-го модуля упорядочивания и хранения отсчетов соединены с первым и вторым управляющими выходами (i+1)-го модуля упорядочивания и хранения отсчетов, на первый и второй управляющие входы первого модуля упорядочивания и хранения отсчетов поданы логические «1» и «0» соответственно, на третий и четвертый управляющий вход N-го модуля упорядочивания и хранения отсчетов поданы два логических «0», в i-м модуле упорядочивания и хранения отсчетов тактовый сигнал и сигнал предварительной установки подключены к тактовому входу и входу предварительной установки регистра, первый, третий и четвертый кодовые входы i-го модуля упорядочивания и хранения отсчетов соединены с первым, вторым и третьим кодовыми входами коммутатора шины, кодовый выход коммутатора шины соединен с кодовым входом регистра, первый кодовый вход i-го модуля упорядочивания и хранения отсчетов также соединен с первым кодовым входом компаратора 4, на второй кодовой вход компаратора 4 и 5, а также на кодовый выход i-го модуля упорядочивания и хранения отсчетов подан кодовый выход регистра, второй кодовый вход i-го модуля упорядочивания и хранения отсчетов подключен к первому кодовому входу компаратора 5, первый, второй, третий и четвертый управляющие входы i-го модуля упорядочивания и хранения отсчетов подключены к первому, второму, третьему и четвертому входам комбинационной схемы, выходы компараторов 4 и 5 соединены с пятым и шестым входами комбинационной схемы, выход компаратора 4 соединен с первым управляющим выходом i-го модуля упорядочивания и хранения отсчетов, первый и второй выходы комбинационной схемы подключены ко второму и третьему управляющим выходам i-го модуля упорядочивания и хранения отсчетов, третий, четвертый и пятый выходы комбинационной схемы подключены к первому, второму и третьему управляющим входам коммутатора шины, шестой выход комбинационной схемы соединен со входом разрешения работы регистра.
На фиг.1 представлена блок-схема предлагаемого одномерного медианного фильтра с модульной архитектурой, который состоит из N элементов задержки входного сигнала 1(RG1-RGN); N модулей упорядочивания и хранения отсчетов 2(M1-MN), где N=(2k-1) - длина апертуры фильтра, k - натуральное число, большее единицы.
На фиг.2 представлена блок-схема модуля упорядочивания и хранения отсчетов. Каждый модуль упорядочивания и хранения отсчетов содержит коммутатор шины 3, компараторы 4 и 5, регистр 6, комбинационную схему 7.
На фиг. 1 и 2 приняты следующие обозначения входных и выходных сигналов модуля упорядочивания и хранения отсчетов: Din, RGN, Мi-1, Мi+1 - первый, второй, третий и четвертый кодовые входы, Мi - кодовый выход, a4 a3 a5 a2 - первый, второй, третий и четвертый управляющие входы, a0 c0 c1 - первый, второй, третий управляющие выходы.
Алгоритм работы фильтра заключается в упорядочивании отсчетов по возрастанию методом вставки [4]. В начальный момент времени по сигналу начальной установки reset все регистры схемы обнуляются. После этого данные в цепочке регистров в модулях М1-МN можно считать упорядоченными. Далее, на каждом такте работы схемы по шине Din в параллельном l-разрядном коде поступает очередной отсчет, происходит вычисление медианы (упорядочивание по возрастанию) и результат выдается на шину Dout. Для упорядочивания отсчетов методом вставки данные со входа фильтра необходимо поместить в регистр одного из модулей M1 - МN. Для этого требуются пересылки данных между соседними модулями. Управление пересылками данных осуществляется на основе логической обработки результатов пар сравнений Din>Мi, RGN=Mi и сигналов a5, a2 и a4, a3 от двух соседних модулей. Запись нового отсчета в регистр i-го модуля и необходимые пересылки данных между соседними модулями производятся одновременно. Согласно методу вставки, отсчеты, хранящиеся в регистрах модулей M1 - МN, всегда упорядочены, т.е. медиана всегда содержится в регистре модуля с номером (N+1)/2.
Определим сигналы a5-a0 и синтезируем комбинационную схему (КС) i-го модуля. Обозначим результаты сравнения содержимого регистра i-го модуля с отсчетами Din и RGN как
соответственно. Для упорядочивания отсчетов необходима информация о том, с какой стороны от i-го модуля находится модуль, содержащий в регистре число, равное RGN: справа
или слева
Составим таблицу 1, в которой представлены: номер набора - десятичный эквивалент двоичного набора четырех переменных a3, a2 a1, a0; собственно набор этих четырех переменных и соответствующее этому набору содержимое регистра Mi.
Наборы с номерами 0, 1, 12, 13 соответствуют невозможным ситуациям. В первых двух случаях одновременно равны нулю a1, a2, a3, т.е. ни в одном из регистров модулей Мi нет отсчета, значение которого совпадало бы с содержимым регистра RGN. Для наборов с номерами 12, 13 и слева и справа от i-го модуля находятся модули, содержащие отсчеты, равные RGN, но в то же время содержимое самого i-го модуля не равно RGN. Это противоречит тому, что в регистрах модулей М1-МN отсчеты всегда упорядочены по возрастанию.
| Таблица 1 | |||||
| № набора | a3 | a2 | a1 | a0 | Mi |
| 0 | 0 | 0 | 0 | 0 | x |
| 1 | 0 | 0 | 0 | 1 | x |
| 2 | 0 | 0 | 1 | 0 |
|
| 3 | 0 | 0 | 1 | 1 |
|
| 4 | 0 | 1 | 0 | 0 |
|
| 5 | 0 | 1 | 0 | 1 | Мi |
| 6 | 0 | 1 | 1 | 0 |
|
| 7 | 0 | 1 | 1 | 1 | Мi+1 |
| 8 | 1 | 0 | 0 | 0 | Мi |
| 9 | 1 | 0 | 0 | 1 |
|
| 10 | 1 | 0 | 1 | 0 | Mi-1 |
| 11 | 1 | 0 | 1 | 1 |
|
| 12 | 1 | 1 | 0 | 0 | x |
| 13 | 1 | 1 | 0 | 1 | x |
| 14 | 1 | 1 | 1 | 0 | Mi-1 |
| 15 | 1 | 1 | 1 | Мi+1 |
Наборам 5 и 8 соответствует сохранение текущего содержимого регистра. В первом случае текущее содержимое регистра модуля Mi меньше значения отсчета Din (a0=1), при этом не равны значения отсчетов в регистрах Мi и RGN (a1=0), и справа от Mi есть свободный модуль (a2=1), т.е. для упорядочивания отсчетов не требуется перемещать содержимое регистра Mi. Аналогичным образом получаем и для набора 8.
Наборам 7 и 15 соответствует прием содержимого регистра Мi+1. В обоих случаях содержимое регистра Мi меньше значения отсчета Din (a0=1), при этом RGN=М и RGN=Мi+1, это значит, что для упорядочивания требуется сдвиг влево, т.е. прием i-м модулем данных от i+1. Аналогичным образом получаем, что наборам 10 и 14 соответствует прием содержимого регистра i-1 модуля.
Анализ наборов 2-4, 6, 9, 11 показывает, что информации, содержащейся в значениях переменных a3, a2, a1, a0, недостаточно для однозначного определения источника данных i-го модуля. Например, при комбинации номер 2 возможны два варианта:
- прием данных Din со входа фильтра, когда содержимое i-1 модуля меньше отсчета Din;
- прием данных от i-1 модуля, в остальных случаях.
При комбинации номер 3 также возможны два варианта:
- прием данных от i+1 модуля Mi+1, когда содержимое регистра модуля Mi+1 меньше отсчета Din;
- прием данных Din со входа фильтра, в остальных случаях.
Определим переменные a4, a5 с помощью выражений (5), (6) и заполним таблицу 1 для наборов 2-4, 6, 9, 11.
На основе таблицы 1 составим логические выражения из переменных a3, a2, a1, a0, определяющих источник данных для регистра i-го модуля (см. таблицу 2).
| Таблица 2 | |
| Выражение | Источник данных |
|
Мi |
|
Mi-1 |
| a2a1a0 | Mi+1 |
|
|
|
|
После объединения и минимизации получаем выражения для 4-х переменных b3, b2, b1, b0, представленные в таблице 3. Поскольку данные выражения получены на основе таблицы 1, то переменные b3, b2, b1, b0 являются взаимоисключающими в том смысле, что в каждый момент времени единице может быть равна только одна из них. Сигналы b2, b1, b0 управляют схемой мультиплексирования данных, а сигнал b3 запрещает запись в регистр RG, когда нужно сохранить текущее значение регистра (см. фиг.2).
| Таблица 3 | |
| Выражение | Источник данных |
|
Din |
|
Mi-1 |
|
Mi+1 |
|
Мi |
Из выражений (3-6) видно, что каждый модуль должен передавать соседним модулям результаты сравнения Din>Мi, RGN=Мi. Для этого i-й модуль (см. фиг.2) формирует сигналы a0, c1, c0, которые определяются согласно (3-6): c0=a1+a2, c1=a1+a3 и соединяются с соответствующими входами a5, a4, a3, a2 (i-1)-го и (i+1)-го модуля, согласно таблице 4.
| Таблица 4 | |
| Входы управления i-го модуля | Источник информации |
| a2 | c0 от Mi+1 |
| a3 | c1 от Mi-1 |
| a4 | a0 от Mi-1 |
| a5 | a0 от Mi+1 |
Из таблицы 4 видно, что сигналы a4, a3 не определены для M1 и a5, a2 не определены для MN. Для корректной работы схемы необходимо:
- на вход a2 первого модуля и вход a3 N-го модуля подать «0», поскольку в первом случае слева, а во втором - справа нет модуля, хранящего значение, равное содержимому регистра RGN;
- на вход a4 первого модуля подать «1», а на вход a5 N-го модуля подать «0» исходя из того, что отсчеты в регистрах модулей М1 - МN упорядочены по возрастанию.
В таблице 5 приведены данные по аппаратным затратам на реализацию медианных фильтров с предложенной модульной архитектурой. Сравнительный анализ данной архитектуры с известными реализациями медианных фильтров, позволяющими вычислять медиану на каждом такте [5], показал, что модульная архитектура дает существенную экономию аппаратных ресурсов при длине апертуры, большей 5.
| Таблица 5 | |
| Элемент | Количество |
| l-разрядный регистр, шт | 2N |
| l-разрядный компаратор, шт | 2N |
| l-разрядный мультиплексор 2 в 1, шт | 1.5N |
Практическая аппаратная реализация медианных фильтров с большими длинами апертуры (более 5 отсчетов) целесообразна на базе заказных или программируемых логических интегральных схем. С целью облегчения использования предложенной модульной архитектуры фильтра на различной элементной базе было разработано синтезируемое Verilog-описание, позволяющее реализовать медианный фильтр с любой нечетной длиной апертуры. В таблице 6 приведены данные по аппаратным затратам на реализацию модульной архитектуры на базе ПЛИС фирмы Xilinx серии Spartan3.
| Таблица 6 | |
| Количество отсчетов в апертуре фильтра | Количество конфигурируемых логических блоков |
| 3 | 17 |
| 5 | 31 |
| 7 | 49 |
| 9 | 60 |
Таким образом, разработанная модульная архитектура одномерного медианного фильтра обладает следующими особенностями:
- позволяет вычислять медиану на каждом такте работы схемы;
- обеспечивает линейный рост аппаратных затрат при увеличении длины апертуры;
- позволяет реализовывать фильтры с любой нечетной длиной апертуры на различной элементной базе.
Источники информации
1. Фридман П.А. Цифровой медианный фильтр. Описание изобретения к патенту РФ №4828474/24, Кл. G06F 17/18, 10.09.95.
2. Секунов Н.Ю. Рекурсивный медианный фильтр. Описание изобретения к патенту РФ №4844217/63, Кл. Н03Н 17/00, 27.09.95 (прототип).
3. Хуанг Т.С. Быстрые алгоритмы в цифровой обработке изображений. - М.: Радио и связь, 1984. - 224 с.
4. Кнут Д.Э. Искусство программирования. Том 3. Сортировка и поиск - К.: Вильямc, 2007. - 832 с.
5. Воробьев Н.В. Одномерный медианный фильтр с трехотсчетным окном. Chip News. - 1999. - №9.
Одномерный медианный фильтр с модульной архитектурой, содержащий N элементов задержки входного сигнала, к входу первого элемента задержки подключена шина входного сигнала, вход i-го элемента задержки соединен с выходом (i-1)-го элемента задержки, отличающийся тем, что в него введены N модулей упорядочивания и хранения отсчетов, каждый из которых состоит из коммутатора шины, двух компараторов, регистра и комбинационной схемы, предназначенной для управления пересылками данных между модулями на основе логической обработки результатов сравнения входных кодовых сигналов и управляющих сигналов от двух соседних модулей, при этом тактовый сигнал и сигнал предварительной установки соединены с тактовым входом и входом предварительной установки i-го элемента задержки и i-го модуля упорядочивания и хранения отсчетов, шина входного сигнала и шина с выхода N-го элемента задержки подключены к первому и второму кодовым входам каждого модуля упорядочивания и хранения отсчетов, третий и четвертый кодовые входы i-го модуля упорядочивания и хранения отсчетов соединены с кодовыми выходами (i-1)-го и (i+1) модуля упорядочивания и хранения отсчетов соответственно, третий кодовый вход первого модуля упорядочивания и хранения отсчетов и четвертый кодовый вход N-го модуля упорядочивания и хранения отсчетов остаются неподключенными, первый и второй управляющие входы i-го модуля упорядочивания и хранения отсчетов соединены с первым и третьим управляющими выходами (i-1)-го модуля упорядочивания и хранения отсчетов, третий и четвертый управляющие входы i-го модуля упорядочивания и хранения отсчетов соединены с первым и вторым управляющими выходами (i+1)-го модуля упорядочивания и хранения отсчетов, первый и второй управляющие входы первого модуля упорядочивания и хранения отсчетов предназначены для подачи логических «1» и «0» соответственно, третий и четвертый управляющий вход N-го модуля упорядочивания и хранения отсчетов предназначен для подачи логического «0», в i-м модуле упорядочивания и хранения отсчетов тактовый сигнал и сигнал предварительной установки подключены к тактовому входу и входу предварительной установки регистра, первый, третий и четвертый кодовые входы i-го модуля упорядочивания и хранения отсчетов соединены с первым, вторым и третьим кодовыми входами коммутатора шины, кодовый выход коммутатора шины соединен с кодовым входом регистра, первый кодовый вход i-го модуля упорядочивания и хранения отсчетов также соединен с первым кодовым входом первого компаратора, второй кодовый вход i-го модуля упорядочивания и хранения отсчетов подключен к первому кодовому входу второго компаратора, на второй кодовый вход обоих компараторов, а также на кодовый выход i-го модуля упорядочивания и хранения отсчетов подан кодовый выход регистра, при этом выход первого компаратора является признаком неравенства сравниваемых входных значений, соединен с пятым входом комбинационной схемы и является первым управляющим выходом i-го модуля упорядочивания и хранения отсчетов, выход второго компаратора является признаком равенства сравниваемых входных значений и соединен с шестым входом комбинационной схемы, первый, второй, третий и четвертый управляющие входы i-го модуля упорядочивания и хранения отсчетов подключены к первому, второму, третьему и четвертому входам комбинационной схемы, первый и второй выходы комбинационной схемы подключены ко второму и третьему управляющим выходам i-го модуля упорядочивания и хранения отсчетов, третий, четвертый и пятый выходы комбинационной схемы подключены к первому, второму и третьему управляющим входам коммутатора шины, шестой выход комбинационной схемы соединен с входом разрешения работы регистра.
