medfilter

Краткое описание

Версия реализации медианного фильтра на языке программирования Си (POSIX-совместимая).

История

Алгоритм был взят из Википедии, хоть это и не самый авторитетный существующий источник. Было изучено большое количество материала, в мире существует множество реализаций медианного фильтра со значительными изменениями. Например, Wolfram Mathematica имеет медианный фильтр, который получает на выходе дробные значения из целых чисел, причём с окном "1". Честно говоря, я бы с удовольствием воспользовался бы "стандартным" описанием алгоритма медианного фильтра, если бы оно было. Больше всего материала было про 2D-медианный фильтр, ибо, как я догадываюсь, он либо чаще используется именно для изображений, либо потому что это самый наглядный пример работы данного фильтра.

Тем не менее, в моём случае алгоритм достаточно прост: Взаимодействие с пользователем: получаем данные о размере окна из аргументов командной строки и валидация этих данных. Считываем из stdin в буфер N элементов сигнала в бинарном виде, где N = (РАЗМЕР_ОКНА > 255 ? 1.5 * РАЗМЕР_ОКНА : 255) Для каждого элемента формируем окно -- массив с соседями. В случае, если соседи слева или справа отсутствуют, дублируем "себя". Пример: сигнал [ 1 2 3 ], для первого элемента с размером окна 5 получим окно (1 1 1 2 3). Получаем медиану из окна (используется сторонний алгоритм!) и выводим в stdout в бинарном виде.

В случае ошибок информация выводится в stderr. Если до компиляции указать #define DEBUG, то в stderr также будет выведена информация об окне для каждого элемента и "сигнальный буфер" на каждый этап считывания.

Кроме того, рядом с основной частью реализации медианного фильтра есть простенький генератор сигнала с "помехами", который принимает на себя желаемый размер сигнала, выводит в stderr человеко-понятный вид нового сигнала, а в stdout -- бинарный вид.

Далее, оптимизации зависят от задачи: мы можем оптимизировать программу либо по скорости исполнения, либо по памяти. Возможно, мне необязательно хранить всё окно целиком (в случае максимального размера 2^32-1 * sizeof(int32_t) ~ 16 Гб) и можно попытаться реализовать частичное хранение и выделение "локальных" медиан, среди которых мы будем опять искать медиану и так далее. Я не могу это математически доказать, поэтому на практике не применяю. В данном случае реализация идёт максимально простая и универсальная. При бОльших технических данных (информация о железе и информация о входных данных) можно оптимизировать программу ещё глубже. Так как у меня нет опыта в выборе нужных структур данных и, к сожалению, практически нет алгоритмической базы (книга Кормана так и не была осилена), то я слабо представляю, как улучшить мой вариант в плане быстродействия. Очевидно, что, к примеру, полное переформирование массива для окна и его сортировка -- это достаточно медленные операции, которые, вероятно, можно заменить какой-либо более подходящей структурой данных. Я видел реализации с двусвязными списками, с бинарными деревьями, с массивами, находил информацию о реализации медианного фильтра, работающего за константное время. Конечно, можно полезть дальше и играться с ассемблерными вставками и уже работать на уровне процессора, но в задании не указана конкретная архитектура, да и код должен быть портабельным. Воспользовался я сторонней реализацией поиска серединного элемента в массиве, потому что... хотелось хоть где-то улучшить время работы программы. Можно было легко воспользоваться тем же qsort'ом и выбрать "серединный" элемент после полной сортировки, но в данном случае полная сортировка будет излишней.

Сборка осуществляется при помощи make. Сборка успешно проверена на gcc 4.9.1 на Debian 7 (GNU/Linux 2.6.32 x86_64).