одномерный медианный фильтр с модульной архитектурой

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

Одномерный медианный фильтр с модульной архитектурой, содержащий 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-го модуля упорядочивания и хранения отсчетов, третий, четвертый и пятый выходы комбинационной схемы подключены к первому, второму и третьему управляющим входам коммутатора шины, шестой выход комбинационной схемы соединен с входом разрешения работы регистра.

Описание изобретения к патенту

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

Известен цифровой медианный фильтр [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(RG ₁-RG_N); N модулей упорядочивания и хранения отсчетов 2(M₁-M_N), где N=(2k-1) - длина апертуры фильтра, k - натуральное число, большее единицы.

На фиг.2 представлена блок-схема модуля упорядочивания и хранения отсчетов. Каждый модуль упорядочивания и хранения отсчетов содержит коммутатор шины 3, компараторы 4 и 5, регистр 6, комбинационную схему 7.

На фиг. 1 и 2 приняты следующие обозначения входных и выходных сигналов модуля упорядочивания и хранения отсчетов: D_in, RG_N, М_i-1 , М_i+1 - первый, второй, третий и четвертый кодовые входы, М_i - кодовый выход, a₄ a₃ a₅ a₂ - первый, второй, третий и четвертый управляющие входы, a₀ c₀ c₁ - первый, второй, третий управляющие выходы.

Алгоритм работы фильтра заключается в упорядочивании отсчетов по возрастанию методом вставки [4]. В начальный момент времени по сигналу начальной установки reset все регистры схемы обнуляются. После этого данные в цепочке регистров в модулях М₁-М_N можно считать упорядоченными. Далее, на каждом такте работы схемы по шине D_in в параллельном l-разрядном коде поступает очередной отсчет, происходит вычисление медианы (упорядочивание по возрастанию) и результат выдается на шину D_out. Для упорядочивания отсчетов методом вставки данные со входа фильтра необходимо поместить в регистр одного из модулей M₁ - М_N. Для этого требуются пересылки данных между соседними модулями. Управление пересылками данных осуществляется на основе логической обработки результатов пар сравнений D _in>М_i, RG_N=M_i и сигналов a₅, a₂ и a₄, a₃ от двух соседних модулей. Запись нового отсчета в регистр i-го модуля и необходимые пересылки данных между соседними модулями производятся одновременно. Согласно методу вставки, отсчеты, хранящиеся в регистрах модулей M₁ - М_N, всегда упорядочены, т.е. медиана всегда содержится в регистре модуля с номером (N+1)/2.

Определим сигналы a₅-a₀ и синтезируем комбинационную схему (КС) i-го модуля. Обозначим результаты сравнения содержимого регистра i-го модуля с отсчетами D_in и RG_N как

соответственно. Для упорядочивания отсчетов необходима информация о том, с какой стороны от i-го модуля находится модуль, содержащий в регистре число, равное RG_N: справа

или слева

Составим таблицу 1, в которой представлены: номер набора - десятичный эквивалент двоичного набора четырех переменных a₃, a₂ a₁, a ₀; собственно набор этих четырех переменных и соответствующее этому набору содержимое регистра M_i.

Наборы с номерами 0, 1, 12, 13 соответствуют невозможным ситуациям. В первых двух случаях одновременно равны нулю a₁, a₂, a₃, т.е. ни в одном из регистров модулей М_i нет отсчета, значение которого совпадало бы с содержимым регистра RG_N. Для наборов с номерами 12, 13 и слева и справа от i-го модуля находятся модули, содержащие отсчеты, равные RG_N, но в то же время содержимое самого i-го модуля не равно RG_N. Это противоречит тому, что в регистрах модулей М₁-М_N отсчеты всегда упорядочены по возрастанию.

Таблица 1
№ набора	a 3	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 соответствует сохранение текущего содержимого регистра. В первом случае текущее содержимое регистра модуля M_i меньше значения отсчета D_in (a₀=1), при этом не равны значения отсчетов в регистрах М_i и RG _N (a₁=0), и справа от M_i есть свободный модуль (a₂=1), т.е. для упорядочивания отсчетов не требуется перемещать содержимое регистра M_i. Аналогичным образом получаем и для набора 8.

Наборам 7 и 15 соответствует прием содержимого регистра М_i+1. В обоих случаях содержимое регистра М_i меньше значения отсчета D_in (a₀=1), при этом RG_N=М и RG_N=М_i+1, это значит, что для упорядочивания требуется сдвиг влево, т.е. прием i-м модулем данных от i+1. Аналогичным образом получаем, что наборам 10 и 14 соответствует прием содержимого регистра i-1 модуля.

Анализ наборов 2-4, 6, 9, 11 показывает, что информации, содержащейся в значениях переменных a₃, a₂, a₁ , a₀, недостаточно для однозначного определения источника данных i-го модуля. Например, при комбинации номер 2 возможны два варианта:

- прием данных D_in со входа фильтра, когда содержимое i-1 модуля меньше отсчета D _in;

- прием данных от i-1 модуля, в остальных случаях.

При комбинации номер 3 также возможны два варианта:

- прием данных от i+1 модуля M _i+1, когда содержимое регистра модуля M_i+1 меньше отсчета D_in;

- прием данных D_in со входа фильтра, в остальных случаях.

Определим переменные a₄, a₅ с помощью выражений (5), (6) и заполним таблицу 1 для наборов 2-4, 6, 9, 11.

На основе таблицы 1 составим логические выражения из переменных a₃, a₂, a₁ , a₀, определяющих источник данных для регистра i-го модуля (см. таблицу 2).

Таблица 2
Выражение	Источник данных
	Мi
	Mi-1
a 2a1a0	Mi+1

После объединения и минимизации получаем выражения для 4-х переменных b₃, b₂, b₁, b₀, представленные в таблице 3. Поскольку данные выражения получены на основе таблицы 1, то переменные b₃, b₂, b₁, b₀ являются взаимоисключающими в том смысле, что в каждый момент времени единице может быть равна только одна из них. Сигналы b₂, b₁, b₀ управляют схемой мультиплексирования данных, а сигнал b₃ запрещает запись в регистр RG, когда нужно сохранить текущее значение регистра (см. фиг.2).

Таблица 3
Выражение	Источник данных
	D in
	Mi-1
	Mi+1
	Мi

Из выражений (3-6) видно, что каждый модуль должен передавать соседним модулям результаты сравнения D_in>М_i, RG _N=М_i. Для этого i-й модуль (см. фиг.2) формирует сигналы a₀, c₁, c₀, которые определяются согласно (3-6): c₀=a₁+a ₂, c₁=a₁+a₃ и соединяются с соответствующими входами a₅, a₄, a ₃, a₂ (i-1)-го и (i+1)-го модуля, согласно таблице 4.

Таблица 4
Входы управления i-го модуля	Источник информации
a2	c 0 от Mi+1
a3	c 1 от Mi-1
a4	a 0 от Mi-1
a5	a 0 от Mi+1

Из таблицы 4 видно, что сигналы a₄ , a₃ не определены для M₁ и a₅ , a₂ не определены для M_N. Для корректной работы схемы необходимо:

- на вход a₂ первого модуля и вход a₃ N-го модуля подать «0», поскольку в первом случае слева, а во втором - справа нет модуля, хранящего значение, равное содержимому регистра RG_N ;

- на вход a₄ первого модуля подать «1», а на вход a₅ N-го модуля подать «0» исходя из того, что отсчеты в регистрах модулей М₁ - М_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.