Напишите консольную утилиту, реализующую медианный фильтр. Программа должна запускаться под Linux. Также необходимо написать тесты для утилиты. Покрытие тестов на Ваше усмотрение.
Требования:
- на stdin поступают бинарные данные в целочисленном формате
- на stdout поступают бинарные данные в целочисленном формате
Параметр утилиты - окно фильтра, целое положительное число.
После обработки ошибок при чтении аргументов, происходит инициализация фильтра. Внутри него находится circular buffer, который реализован на указателях (double linked list). Главное преимущество это доступ к значениям самого старого (ageHead), наименьшего (valueHead) и медианы (medianHead) за O(1), но для этого нужно поддерживать порядок и совершать перестановки на каждой итерации.
При инициализации значения буфера равны 0, а указатели фильтра расставляются по местам, после этого значения в буфере становятся равным первому значению из stdin, потому что инициализированная медиана в начале не должна искажать данные. Чтение значений происходит в локальную переменную (по одному за раз, в других реализациях "сигнальный буфер" увеличивается), пропускается через фильтр.
На каждой итерации вставки происходит замена самого старого старого элемента на новый (sample), после чего перебором находится нужное место (по возрастанию).
Корректировка медианы совершается через вычисление позиции нового значения относительно медианы (по половинам). В начале функции мы убирали самое старое значение и в зависимости от его половины, временного переместили на 1 или оставили значение медианы. В конце функции мы возместили перемещение (было на 1 назад, сейчас на 1 вперед), если новое значение будет во второй половине.
Тестирование проводится за счет генерации случайного сигнала утилитой gensig (на вход количество значений), шум будет колебаться от 301 до 304 с резкими скачками до 399. Посмотреть корреляцию входных значений в фильтр и выходных значений можно только с включенной дерективой DEBUG при компиляции.
Дальше только глазами смотреть на размере окна 3, ошибок не находил. Не работал с DSP
Существуют другие реализации алгоритма.
- Можно сортировать выделенное для каждого нового значения окно и также выводить медиану в stdout.
- Можно использовать 2D окно (для обработки изображений), тогда придется использовать quickselect для нахождения медианы медиан.
git clone https://github.com/t1msi/filter.git
cd filter
make all
./gensig 100 | ./MedianFilter 3