1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
# 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'ом` и выбрать "серединный" элемент после полной сортировки, но в данном
случае полная сортировка будет излишней.
|
