Без наркоза

[zHz00]

Медианная фильтрация -- отличная штука. Спасает от случайных выбросов в данных.

В Матбале, естественно, есть готовая функция. А в Си -- нету. Мне сказали -- а возьми код из нашего соседнего проекта. Там большая, проверенная математическая библиотека есть. Мы её сами писали в своё время.

(что было дальше)

Взял. Результаты с матлабовскими не совпадают! При этом где-то 75% значений те же, а 25% отличаются. Взял тестовый массив, стал фильтровать вручную на бумажке. Получил результаты Матлаба.

Медианная фильтрация простая как валенок. Пусть мы хотим отфильтровать ячейку массива номер n. Мы берём ячейки n-1, n и n+1 и рассматриваем их совместно. Сортируем и смотрим, какое значение расположено в середине списка. Его и записываем в энную ячейку. Это если окно фильтрации равно трём. То есть, данные никак не преобразовываются. Мы просто исключаем не-средние значения.

Пусть есть массив: 1, 3, 1, 100, 2, 0.

Первый элемент мы фильтровать не будем, т.к. у него нет предыдущего. В различных реализациях с первым и последним элементом поступают по-разному, я лично просто оставлю его, как есть.

3: 1, 3, 1. Средняя тут единица.
1: 3, 1, 100. Средняя тут тройка.
100: 1, 100, 2. Средняя тут двойка.
2: 100, 2, 0. Средняя тут двойка.

Итог: 1, 1, 3, 2, 2, 0.

Как мы видим, выброс (100) исчез.

Я внимательно изучил позаимствованный мной исходник и обнаружил, что фильтрация происходит "наживую", то есть результат записывается в тот же массив, который мы фильтруем. На первый взгляд ничего плохого в этом нет -- мы вроде как уже эту ячейку обработали, значит можно её перезаписывать. Но не в случае с медианной фильтрацией, которая использует ПРЕДЫДУЩИЕ значения массива! Нет, такой вариант фильтрации всё равно подавит выбросы, но результат будет не тот.

Возьмём для примера опять массив 1, 3, 1, 100, 2, 0.

3: 1, 3, 1. Средняя тут единица. Теперь массив выглядит как 1, 1, 1, 100, 2, 0
1: 1, 1, 100. Средняя тут ЕДИНИЦА. Теперь: 1, 1, 1, 100, 2, 0.
100: 1, 100, 2. Средняя тут двойка. Теперь: 1, 1, 1, 2, 2, 0.
2: 2, 2, 0. Средняя тут двойка. Массив тот же.

Итог: 1, 1, 1, 2, 2, 0.

Как мы видим, одно значение получилось иным, а выброс всё равно исчез. Оценивать математические характеристики такого способа фильтрации, конечно, можно, но не нужно. Это просто ошибка в коде.

А фишка этой ошибки в том, что она прожила хрен знает сколько лет и была обнаружена случайно, причём вообще по другому поводу. Второй раз в жизни обнаруживаю столь застарелую ошибку. Мораль:

1. Повторно использовать код следует с осторожностью.
2. Математические алгоритмы перед введением в действие должны быть тщательно протестированы.
3. Не пили сук, на котором сидишь.