medfilter
Версия реализации медианного фильтра на языке программирования Си (POSIX-совместимая).
Сборка
Сборка осуществляется при помощи команды make
. Сборка успешно проверена на
gcc 4.9.1
на Debian 7 (GNU/Linux 2.6.32 x86_64)
.
Предыстория
Алгоритм был взят из Википедии, хоть это и не самый авторитетный существующий источник. Было изучено большое количество материала, в мире существует множество реализаций медианного фильтра со значительными изменениями. Например, 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'ом
и выбрать "серединный" элемент после полной сортировки, но в данном
случае полная сортировка будет излишней.