ОДНОМЕРНЫЙ МЕДИАННЫЙ ФИЛЬТР С МОДУЛЬНОЙ АРХИТЕКТУРОЙ
ONE-DIMENSIONAL MEDIAN FILTER WITH MODULAR ARCHITECTURE

Изобретение относится к специализированным средствам вычислительной техники и может быть использовано в системах, в которых требуется аппаратная реализация алгоритмов цифровой фильтрации сигналов.
Известен цифровой медианный фильтр [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
N
На фиг.1 представлена блок-схема предлагаемого одномерного медианного фильтра с модульной архитектурой, который состоит из N элементов задержки входного сигнала 1(RG-RG); N модулей упорядочивания и хранения отсчетов 2(M-M), где N=(2k-1) - длина апертуры фильтра, k - натуральное число, большее единицы.
На фиг.2 представлена блок-схема модуля упорядочивания и хранения отсчетов. Каждый модуль упорядочивания и хранения отсчетов содержит коммутатор шины 3, компараторы 4 и 5, регистр 6, комбинационную схему 7.
in
N
i-1
i+1
i
4
3
5
2
0
0
1
На фиг. 1 и 2 приняты следующие обозначения входных и выходных сигналов модуля упорядочивания и хранения отсчетов: D, RG, М, М - первый, второй, третий и четвертый кодовые входы, М - кодовый выход, a a a a - первый, второй, третий и четвертый управляющие входы, ac c - первый, второй, третий управляющие выходы.
1
N
in
out
1
N
in
i
N
i
5
2
4
3
1
N
Алгоритм работы фильтра заключается в упорядочивании отсчетов по возрастанию методом вставки [4]. В начальный момент времени по сигналу начальной установки reset все регистры схемы обнуляются. После этого данные в цепочке регистров в модулях М-М можно считать упорядоченными. Далее, на каждом такте работы схемы по шине D в параллельном l-разрядном коде поступает очередной отсчет, происходит вычисление медианы (упорядочивание по возрастанию) и результат выдается на шину D. Для упорядочивания отсчетов методом вставки данные со входа фильтра необходимо поместить в регистр одного из модулей M - М. Для этого требуются пересылки данных между соседними модулями. Управление пересылками данных осуществляется на основе логической обработки результатов пар сравнений D>М, RG=M и сигналов a, aи a, a от двух соседних модулей. Запись нового отсчета в регистр i-го модуля и необходимые пересылки данных между соседними модулями производятся одновременно. Согласно методу вставки, отсчеты, хранящиеся в регистрах модулей M - М, всегда упорядочены, т.е. медиана всегда содержится в регистре модуля с номером (N+1)/2.
5
0
in
N
Определим сигналы a-aи синтезируем комбинационную схему (КС) i-го модуля. Обозначим результаты сравнения содержимого регистра i-го модуля с отсчетами D и RG как
N
соответственно. Для упорядочивания отсчетов необходима информация о том, с какой стороны от i-го модуля находится модуль, содержащий в регистре число, равное RG: справа
или слева
3
2
1
0
i
Составим таблицу 1, в которой представлены: номер набора - десятичный эквивалент двоичного набора четырех переменных a, aa, a; собственно набор этих четырех переменных и соответствующее этому набору содержимое регистра M.
1
2
3
i
N
N
N
1
N
Наборы с номерами 0, 1, 12, 13 соответствуют невозможным ситуациям. В первых двух случаях одновременно равны нулю a, a, a, т.е. ни в одном из регистров модулей М нет отсчета, значение которого совпадало бы с содержимым регистра RG. Для наборов с номерами 12, 13 и слева и справа от i-го модуля находятся модули, содержащие отсчеты, равные RG, но в то же время содержимое самого i-го модуля не равно RG. Это противоречит тому, что в регистрах модулей М-М отсчеты всегда упорядочены по возрастанию.
Таблица 1
№ набора
a<sub>3</sub>
a<sub>2</sub>
a<sub>1</sub>
a<sub>0</sub>
M<sub>i</sub>
0
0
0
0
0
x
1
0
0
0
1
x
2
0
0
1
0
<img file="00000007.tif" he="12" wi="39" img-content="undefined" img-format="tif" />
3
0
0
1
1
<img file="00000008.tif" he="12" wi="40" img-content="undefined" img-format="tif" />
4
0
1
0
0
<img file="00000009.tif" he="12" wi="39" img-content="undefined" img-format="tif" />
5
0
1
0
1
М<sub>i</sub>
6
0
1
1
0
<img file="00000010.tif" he="12" wi="39" img-content="undefined" img-format="tif" />
7
0
1
1
1
М<sub>i+1</sub>
8
1
0
0
0
М<sub>i</sub>
9
1
0
0
1
<img file="00000011.tif" he="12" wi="40" img-content="undefined" img-format="tif" />
10
1
0
1
0
M<sub>i-1</sub>
11
1
0
1
1
<img file="00000012.tif" he="12" wi="40" img-content="undefined" img-format="tif" />
12
1
1
0
0
x
13
1
1
0
1
x
14
1
1
1
0
M<sub>i-1</sub>
15
1
1
1
М<sub>i+1</sub>
i
in
0
i
N
1
i
2
i
Наборам 5 и 8 соответствует сохранение текущего содержимого регистра. В первом случае текущее содержимое регистра модуля M меньше значения отсчета D(a=1), при этом не равны значения отсчетов в регистрах М и RG (a=0), и справа от M есть свободный модуль (a=1), т.е. для упорядочивания отсчетов не требуется перемещать содержимое регистра M. Аналогичным образом получаем и для набора 8.
i+1
i
in
0
N
N
i+1
Наборам 7 и 15 соответствует прием содержимого регистра М. В обоих случаях содержимое регистра М меньше значения отсчета D (a=1), при этом RG=М и RG=М, это значит, что для упорядочивания требуется сдвиг влево, т.е. прием i-м модулем данных от i+1. Аналогичным образом получаем, что наборам 10 и 14 соответствует прием содержимого регистра i-1 модуля.
3
2
1
0
Анализ наборов 2-4, 6, 9, 11 показывает, что информации, содержащейся в значениях переменных a, a, a, a, недостаточно для однозначного определения источника данных i-го модуля. Например, при комбинации номер 2 возможны два варианта:
in
in
- прием данных D со входа фильтра, когда содержимое i-1 модуля меньше отсчета D;
- прием данных от i-1 модуля, в остальных случаях.
При комбинации номер 3 также возможны два варианта:
i+1
i+1
in
- прием данных от i+1 модуля M, когда содержимое регистра модуля Mменьше отсчета D;
in
- прием данных D со входа фильтра, в остальных случаях.
4
5
Определим переменные a, a с помощью выражений (5), (6) и заполним таблицу 1 для наборов 2-4, 6, 9, 11.
3
2
1
0
На основе таблицы 1 составим логические выражения из переменных a, a, a, a, определяющих источник данных для регистра i-го модуля (см. таблицу 2).
Таблица 2
Выражение
Источник данных
<img file="00000015.tif" he="6" wi="32" img-content="undefined" img-format="tif" /><img file="00000016.tif" he="5" wi="25" img-content="undefined" img-format="tif" />
М<sub>i</sub>
<img file="00000017.tif" he="6" wi="13" img-content="undefined" img-format="tif" />
M<sub>i-1</sub>
a<sub>2</sub>a<sub>1</sub>a<sub>0</sub>
M<sub>i+1</sub>
<img file="00000018.tif" he="6" wi="33" img-content="undefined" img-format="tif" />
<img file="00000019.tif" he="14" wi="53" img-content="undefined" img-format="tif" />
<img file="00000020.tif" he="6" wi="32" img-content="undefined" img-format="tif" />
<img file="00000021.tif" he="15" wi="54" img-content="undefined" img-format="tif" />
3
2
1
0
3
2
1
0
2
1
0
3
После объединения и минимизации получаем выражения для 4-х переменных b, b, b, b, представленные в таблице 3. Поскольку данные выражения получены на основе таблицы 1, то переменные b, b, b, b являются взаимоисключающими в том смысле, что в каждый момент времени единице может быть равна только одна из них. Сигналы b, b, b управляют схемой мультиплексирования данных, а сигнал b запрещает запись в регистр RG, когда нужно сохранить текущее значение регистра (см. фиг.2).
Таблица 3
Выражение
Источник данных
<img file="00000022.tif" he="6" wi="80" img-content="undefined" img-format="tif" />
D<sub>in</sub>
<img file="00000023.tif" he="6" wi="62" img-content="undefined" img-format="tif" />
M<sub>i-1</sub>
<img file="00000024.tif" he="6" wi="65" img-content="undefined" img-format="tif" />
M<sub>i+1</sub>
<img file="00000025.tif" he="6" wi="45" img-content="undefined" img-format="tif" />
М<sub>i</sub>
in
i
N
i
0
1
0
0
1
2
1
1
3
5
4
3
2
Из выражений (3-6) видно, что каждый модуль должен передавать соседним модулям результаты сравнения D>М, RG=М. Для этого i-й модуль (см. фиг.2) формирует сигналы a, c, c, которые определяются согласно (3-6): c=a+a, c=a+a и соединяются с соответствующими входами a, a, a, a (i-1)-го и (i+1)-го модуля, согласно таблице 4.
Таблица 4
Входы управления i-го модуля
Источник информации
a<sub>2</sub>
c<sub>0</sub> от M<sub>i+1</sub>
a<sub>3</sub>
c<sub>1</sub> от M<sub>i-1</sub>
a<sub>4</sub>
a<sub>0 </sub>от M<sub>i-1</sub>
a<sub>5</sub>
a<sub>0 </sub>от M<sub>i+1</sub>
4
3
1
5
2
N
Из таблицы 4 видно, что сигналы a, a не определены для M и a, a не определены для M. Для корректной работы схемы необходимо:
2
3
N
- на вход a первого модуля и вход a N-го модуля подать «0», поскольку в первом случае слева, а во втором - справа нет модуля, хранящего значение, равное содержимому регистра RG;
4
5
1
N
- на вход a первого модуля подать «1», а на вход a N-го модуля подать «0» исходя из того, что отсчеты в регистрах модулей М - М упорядочены по возрастанию.
В таблице 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.