Здравствуйте! 
Необходимо решение следующей задачи. Имеется массив значений, представляюший из себя значения некоторой функции в точках от 0 до N. Необходимо провести анализ массива на наличие неправильных значений (т.е. некоторые значения в массиве могут быть случайными выбросами и портить график функции). Такие значения необходимо выявить и заменить на предполагаемые правильные значения (интерполяцией, апроксимацией). Какие алгоритмы посоветуете ??? 

Похоже на 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:
длину маски можно увеличить. 

В общем случае - уже предложенная медианная фильтрация, а также сплайн-аппроксимация. 

А всерьез такой вопрос бессмысленно рассматривать без информации о том, что это за данные. Признаться сможете?   
Если сможете, признайтесь заодно, есть ли какие-нибудь теоретические представления о том, как эта зависимость должна выглядеть? Если есть - какие?

Вообще-то, если имеется какая-то выборка, то ещё до начала построения каких-либо зависимостей проводят статистический анализ данных как раз на предмет обнаружения аномальных наблюдений (измерений). Такие наблюдения вообще удаляют для обеспечения робастности оценок. 

Что значит удаляют? Может их на что-то заменяют?

ksili, если измерение содержит грубую ошибку его отбрасывают, заменить можно только перемерив его


жуть какая...

sergejzr Спасибо за идею!!, прикинул алгоритм, в некоторых случаях очень даже неплохо (когда случайные значения не идут подряд),  однако встречается и именно такой случай, когда подряд сразу несколько значений являются не верными, так что проблема остается!!!



С апроксимацией в принципе понятно, но необходимо найти ряд неправильных значений, чтобы знать где апроксимировать!




В общих словах имеется система видеонаблюдения за некоторым объектом, одной из функций которой является вычисление углов отклонения этого объекта от горизонтального положения. Т.к. все это происходит на открытой местности, из за погодных условий и т.д ПО выдает неверные значения (в худшем случае до 10% значений неверные). Решили исправлять ошибки при анализе, для чего и нужен фильтр, восстанавливающий ошибочные значения. 



Нету!. объекты разные, колебляться по разному, близко к синусойде канешно. но не обязательно.



Да!, но надо еще статистику набрать.  





Во во!!!  

Я же говорю, можно маску удлинить. Но для творго случая наверное будут решения получше.

Существует много реализаций такой фильтрации. Если вам надо сгладить аномальность таких значений, уменьшить их отклонение, советую вам применить цифровой фильтр нижних частот (интегратор). Теория и реализация в среде MatLab описана здесь. Если не подойдет- поищите информацию по цифровой фильтрации. А какой тип фильтра брать - КИХ или БИХ зависит от значений вашей функции

Медианный фильтр или фильтр скользящего среднего - это частные случаи КИХ-фильтра

не верю, он нелинейный

Severyanin спасибо. думаю в этом направлении и надо искать, никто не встречал реализаций ФНЧ на C++??? чето погуглил, результатов немного.

Т.е. зависимость периодическая или близкая к периодической? 

Обычный Фурье-анализ тогда не годится? Считаете преобразование Фурье, принудительно срезаете высокочастотную компоненту и делаете обратное преобразование. Ошибки и мелкая "тряска" при этом пропадут.

GoldFinch, то как описал median cut sergejzr (по крайней мере как его понял я) выглядит будто результат каждого шага (то есть заново пересчитываемое значение i-го отсчета) зависит от его теперешнего отсчёта, предыдущего и позапрошлого:

y[i] = 1/3*(x[i] + x[i-1] + x[i-2])

Чем не КИХ-фильтр? 
Если бы в формулу входили игреки, т.е. рез-ты предыдущих вычислений, то получился бы БИХ-фильтр. В принципе можно и так было реализовать. Правда может тогда он уже будет по-другому называться (не медианный фильтр)

Есть старая книга - Хэмминг. "Цифровые фильтры". кажется 1980. Там в самом начале как раз идут вот такие примеры ЦФ, для того, чтобы люди которые раньше ничего не знали о ЦФ, поняли, что они на самом деле уже ими пользовались.

Я так и не понял. Обработка должна идти в режиме реального времени или у нас имеется выборка и нужно сделать постанализ?