Медианный фильтр., Нужен быстрый алгоритм медианного фильтра. Опции

[Elf]

Здравствуйте спецы,

Хочу синтезировать на ПЛИС медианный фильтр для одномерного массива.
Нужен быстрый алгоритм желательно без использования перестановки элементов массива.
Может кто поделится опытом или даст ссылку.

В литературе которую нашел предлагается каждый элемент массива сравниавть с остальными элементами и суммировать результаты сравнения. Т. о. для каждого элемента определяется его номер (вес) в упорядоченном ряду. Очевидно, медиана - это элемент со средним номером (весом).

Но есть проблема - если допустим в массиве из пяти элементов большая их часть равна друг другу, то их номера(веса) получаются одинаковыми - в результате элемента с номером(весом) медианы в ряду нет.

Пример:
Ряд____________________ 9, 5, 5, 5, 5
Номер(вес)_____________ 4, 3, 3, 3, 3

Медиана в упорядоченном ряду из пяти элементов имеет номер (вес) - 2.
Ясно что в ряду нет медианы в явном виде - значит надо брать элемент у которого присутствует больше одних и тех же номеров и. т. д. При реализации на ПЛИС (да еще если комбинаторно) все это становится слишком мудреным.
На процессоре понятнее - сортируем массив по возрастанию и берем средний элемент.

Скорее всего изъяснился непонятно. Подробнее можно посмотреть например
http://www.module.ru/files/papers-cos012005.pdf

Может кто работал с такой темой...? Help...

Сообщение отредактировал Elf - Aug 24 2006, 07:17

[NickNich]

Сложно у Вас все как-то. Попробуйте гуглем пройтись median filtering FPGA. Сразу находистя много сцылок:
http://csdl2.computer.org/comp/proceedings...00/77550523.pdf
http://www.xilinx.com/xcell/xl23/xl23_16.pdf

И размеритесь с определением медианы. Она всегда есть в явном виде у любого массива нечетной размерности. С четоной - там сложнее, нужно договариваться, что считать медианой...

Статью не читал, поверил Вашему описанию. Но, сдается мне, прямой перебор с хитрыми весами - не самый лучший метод поиска медианы. Гораздо лучше - банальный метод "пузырька"...

Сообщение отредактировал NickNich - Aug 24 2006, 08:07

[Elf]

Спасибо за ссылки. Я прошелся по теме в интернете достаточно серьезно. Как правило - общие подходы. Возможно практические методы являются интелектуальной собственностью поэтому их особенно не афишируют.
По поводу "пузырьковой" сортировки согласен - все ясно и надежно.
Есть только один момент - работая с весами можно обрабатывать весь массив сразу (параллельно). В случае "пузырьковой" сортировки за такт обрабатывается пара элементов. Разница в скорости получается существенная (естественно и обратная разница в аппаратных затратах).

Сообщение отредактировал Elf - Aug 24 2006, 08:57

[Doka]

Ясно что в ряду нет медианы в явном виде - значит надо брать элемент у которого присутствует больше одних и тех же номеров и. т. д. При реализации на ПЛИС (да еще если комбинаторно) все это становится слишком мудреным.
На процессоре понятнее - сортируем массив по возрастанию и берем средний элемент.

почему это у вас при изменении элементной базы меняется само определение медианы?!

Код

медианой последовательности y1, y2, ... , ym (m — нечётное) является средний по значению член ряда, получаемый после упорядочения последовательности по возрастанию. Для чётного m медиана определяется как среднее арифметическое двух средних членов. В литературе можно найти и другие определения, но они мало отличаются друг от друга, а в подавляющем большинстве случаев принимают m нечётным.
источник: http://www.chipnews.ru/html.cgi/arhiv/99_08/stat_29.htm

что плис, что процессор -алгоритм тот же
различия лишь в реализации, учитывая особенности элементной базы

upd: а о какой размерности фильтра идет речь?

[Elf]

Предположительно, по минимуму, массив из одиннадцати 32-разрядных чисел.

А различия в реализации именно в том, что на ПЛИС можно синтезировать комбинаторную схему, скорость работы которой определяется задержками составляющих ее элементов. Ну а в проце все равно все покомандно с учетом тактовой частоты.

Я написал на VHDL в качестве теста комбинаторный медианный фильтр для 7-и 32-байтных чисел. По оценке временного анализатора (конкретная эл. база) полоса порядка 170МГц. С подобной частотой можно обновлять массив (на практике возможно все не так гладко).
На "среднем" проце при попарной сортирвке все будет медленнее.
В написанном тесте я забил на случаи когда нет половинного веса и брал за медиану старший элемент, что естественно неправильно.

Если интересно посмотри http://chipnews.gaw.ru/html.cgi/arhiv/99_08/stat_29.htm
Там реализован трехотсчетный фильтр. Но для большего количесва отсчетов получается сложный дешифратор (КС у автора). Не приведено никакой формулы, только таблица.