| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм фильтрации |
| Автор: empter 13.1.2009, 23:51 |
| Здравствуйте! Необходимо решение следующей задачи. Имеется массив значений, представляюший из себя значения некоторой функции в точках от 0 до N. Необходимо провести анализ массива на наличие неправильных значений (т.е. некоторые значения в массиве могут быть случайными выбросами и портить график функции). Такие значения необходимо выявить и заменить на предполагаемые правильные значения (интерполяцией, апроксимацией). Какие алгоритмы посоветуете ??? |
| Автор: sergejzr 14.1.2009, 00:38 |
| Похоже на median cut. иёшь маской в три точки средняя - рабочая, в неё записываешь медиан - среднее значение (но не путать со средним арифметическим!) Работает хорошо, если случайные значения не идут несколько подряд. Края (первое и последнее значение) не обрабатываются пример: //-- начало алгоритма Исходный массив, по которому идём маской: 2 3 30 5 7 Край не обрабатывается, записываем первое число как есть: ответ: 2 начинаем с 3 на её место записываем медиан(2,3,30) = 3 ответ: 2 3 следующая 30, на её место записываем медиан(3,30,5)=5 ответ: 2 3 5 следующая 5, на её место записываем медиан(30,5,7)=5 ответ: 2 3 5 5 Край не обрабатывается, записываем последнее число как есть: ответ: 2 3 5 5 7 //----Конец алгоритма Числа, которые не совпадают в исходном массиве и ответе - наш мусор. Как модификацию можно после фильтрации сравнить с исходным массивом и заменить числа, которые отличаются средним арифметическим соседей ответа. пример: //-- начало алгортма исходный массив: 2 3 30 5 7 фильтрованный массив: 2 3 5 5 7 2==2 - оставляем ответ: 2 3==3 - оставляем ответ: 2 3 30 != 5 решаем (3+5)/2 = 4 ответ: 2 3 4 5==5 - оставляем ответ: 2 3 4 5 7==7 - оставляем ответ: 2 3 4 5 7 //---- конец алгоритма Преимущество модификации - более сглаженный график. Недостатки - появляются значения, которых вообще не было (грубо говоря выдуманные) Алгоритм сохраняет контуры - резкие перепады значений, если это действительно ступенька. пример: исходный массив: 2 3 4 10 11 15 не измениться, хотя с 4 на десятку прыжок. Добавлено @ 00:41 PS: длину маски можно увеличить. |
| Автор: Фантом 14.1.2009, 00:46 |
| В общем случае - уже предложенная медианная фильтрация, а также сплайн-аппроксимация. А всерьез такой вопрос бессмысленно рассматривать без информации о том, что это за данные. Признаться сможете?  Если сможете, признайтесь заодно, есть ли какие-нибудь теоретические представления о том, как эта зависимость должна выглядеть? Если есть - какие? |
| Автор: podval 14.1.2009, 11:30 |
| Вообще-то, если имеется какая-то выборка, то ещё до начала построения каких-либо зависимостей проводят статистический анализ данных как раз на предмет обнаружения аномальных наблюдений (измерений). Такие наблюдения вообще удаляют для обеспечения робастности оценок. |
| Автор: ksili 14.1.2009, 11:52 | ||
Что значит удаляют? Может их на что-то заменяют? |
| Автор: GoldFinch 14.1.2009, 14:53 | ||
ksili, если измерение содержит грубую ошибку его отбрасывают, заменить можно только перемерив его
жуть какая... |
| Автор: empter 14.1.2009, 19:33 | ||||||||||
sergejzr Спасибо за идею!!, прикинул алгоритм, в некоторых случаях очень даже неплохо (когда случайные значения не идут подряд), однако встречается и именно такой случай, когда подряд сразу несколько значений являются не верными, так что проблема остается!!!
С апроксимацией в принципе понятно, но необходимо найти ряд неправильных значений, чтобы знать где апроксимировать!
В общих словах имеется система видеонаблюдения за некоторым объектом, одной из функций которой является вычисление углов отклонения этого объекта от горизонтального положения. Т.к. все это происходит на открытой местности, из за погодных условий и т.д ПО выдает неверные значения (в худшем случае до 10% значений неверные). Решили исправлять ошибки при анализе, для чего и нужен фильтр, восстанавливающий ошибочные значения.
Нету!. объекты разные, колебляться по разному, близко к синусойде канешно. но не обязательно.
Да!, но надо еще статистику набрать. 
Во во!!! |
| Автор: sergejzr 14.1.2009, 19:45 | ||
Я же говорю, можно маску удлинить. Но для творго случая наверное будут решения получше. |
| Автор: Severyanin 15.1.2009, 09:38 |
| Существует много реализаций такой фильтрации. Если вам надо сгладить аномальность таких значений, уменьшить их отклонение, советую вам применить цифровой фильтр нижних частот (интегратор). Теория и реализация в среде MatLab описана http://window.edu.ru/window_catalog/pdf2txt?p_id=22521&p_page=1. Если не подойдет- поищите информацию по цифровой фильтрации. А какой тип фильтра брать - КИХ или БИХ зависит от значений вашей функции |
| Автор: ksili 15.1.2009, 09:52 | ||
Медианный фильтр или фильтр скользящего среднего - это частные случаи КИХ-фильтра |
| Автор: GoldFinch 15.1.2009, 19:27 | ||
не верю, он нелинейный |
| Автор: empter 16.1.2009, 00:55 |
| Severyanin спасибо. думаю в этом направлении и надо искать, никто не встречал реализаций ФНЧ на C++??? чето погуглил, результатов немного. |
| Автор: Фантом 16.1.2009, 01:18 | ||
Т.е. зависимость периодическая или близкая к периодической? Обычный Фурье-анализ тогда не годится? Считаете преобразование Фурье, принудительно срезаете высокочастотную компоненту и делаете обратное преобразование. Ошибки и мелкая "тряска" при этом пропадут. |
| Автор: ksili 16.1.2009, 05:49 |
| GoldFinch, то как описал median cut sergejzr (по крайней мере как его понял я) выглядит будто результат каждого шага (то есть заново пересчитываемое значение i-го отсчета) зависит от его теперешнего отсчёта, предыдущего и позапрошлого: y[i] = 1/3*(x[i] + x[i-1] + x[i-2]) Чем не КИХ-фильтр? Если бы в формулу входили игреки, т.е. рез-ты предыдущих вычислений, то получился бы БИХ-фильтр. В принципе можно и так было реализовать. Правда может тогда он уже будет по-другому называться (не медианный фильтр) Есть старая книга - Хэмминг. "Цифровые фильтры". кажется 1980. Там в самом начале как раз идут вот такие примеры ЦФ, для того, чтобы люди которые раньше ничего не знали о ЦФ, поняли, что они на самом деле уже ими пользовались. |
| Автор: W4FhLF 16.1.2009, 07:57 |
| Я так и не понял. Обработка должна идти в режиме реального времени или у нас имеется выборка и нужно сделать постанализ? |
| Автор: GoldFinch 16.1.2009, 09:29 |
| ksili, median cut сортирует значения в окне и берет центральный (средний по индексу) элемент отсортированных значений окна, это нелинейная операция |
| Автор: ksili 16.1.2009, 09:59 | ||
А-а-а, так вот оно как работает. А я думал это то, что я описал. Тогда конечно нелинейная. |
| Автор: empter 16.1.2009, 23:57 | ||
Нет, не в реальном времени, уже есть результат (выборка) и ее надо отфильтровать (сделать пост анализ)! |
| Автор: W4FhLF 17.1.2009, 08:31 | ||
| Ну тогда, как уже выше сказали, можно обойтись простой статистикой. Задаться некоторым уровнем значимости, в рамки которого будет попадать, скажем, 99.9% значений твоей выборки. Например правило 3х сигм(σ -- стандартное отклонение):
После этого в местах отсутствующих значений можно провести простую интерполяцию(сплайнами). |
