Привет,

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

иллюстрация (если ее так назвать можно) прилагается...
ЗЫ вот то что там зелененькое это что-то вроде выхода фильтра на каждом этапе... далжна наблюдаться сходимость к истинному углу...

спасибо за любую помощь!

Это сообщение отредактировал(а) uvsoft - 14.10.2006, 00:08

Присоединённый файл ( Кол-во скачиваний: 41 )
 untitled.JPG 35,50 Kb

ну, например, метод наименьших квадратов
аппроксимирующая функция: ax+b

так это все тоже интергрирование тока в вариациях.... ну например я из каких-то соображений решил что буду держать историю в размере N штук... аппроксимирую ее по методу средних квадратов.... получаю значения... а что если этот интервал окажется очень маленьким, ведь для корректной оценки мне надо как миниму знать две ступеньки, а кто его знает скока там точек?... да и говорю же все эти методы неустойчивы, а мне нужна сходимость

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


а почему бы методу наименьших квадратов и не сходиться?
при поступлении точек он будет колебаться всё меньше и меньше

я и не говорю что он даст что-то нормальное пока у него не будет достаточной информации, это не реально, но вот то, что он выдаст, то что нужно, как только у него появятся две ступеньки, это точно... т.е. если фильтр бесконечный то он знает все и ничего не упускает из виду, тогда как суммирование которое ты предлагаешь с последующим усреднением величин обладает короткой паматью (а что если эта память покроет тока самый кончик ступеньки и самое начало следующий? что за криулина вниз получится???), я же не могу до бесконечности увеличивать какой-то там массивчик и постоянно суммировать все больше и больше и больше... это не реально и не рационально.

насчет устойчивости, все эти алгоритны, постоенные на интегрировании, выправляют входные данные когда они плохие и искажают когда они хорошие... нам такого не нужно, быть может в этом отношении я и не прав, особо не интересовался данной темой, но вот первое НО из предыдущего абзаца в любом случает заставлять отказаться от интегрирования.

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

uvsoft

К размышлению на тему:

Это сообщение отредактировал(а) Aloha - 17.10.2006, 16:40

Присоединённый файл ( Кол-во скачиваний: 14 )
 01.rar 11,52 Kb

Чем больше у вас априорной информации о процессе, тем лучше вы сможете его обработать. Судя по картинке ваш процесс есть сумма "белого" шума и детерминированного процесса в виде лесенки. Вы это знаете заранее. Значит вы должны применить последовательно два фильтра. Сначала подавить "белый" шум. На выходе этого фильтра в идеале будет чистая лестница.  Второй  фильтр должен сглаживать лестницу и на его выходе будет в идеале прямая линия. 

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

спасибо за ответ, но я там вижу только #ИМЯ? #ДЕЛ/0 и тому подобное, офис русский, должен вроде бы понимать... во втором столбце ругается вроде бы на СТРОКА()... и вот я смотрю, там расчеты производятся при известной величине шага, шума и т.д.... а этого не известно, можно конечно прикинуть, но не хотелось бы привязываться к этому...

Добавлено @ 21:08 

о каком методе ты говоришь?

пусть у нас есть набор x[n] и y[n] (скорее всего x[n] будет равно n, но это неважно)
задача: сумма (a*x[n]+b-y[n])^2 ->min
берём производные по a и b и приравниваем их к 0
(двойки я поубирал)
1.(по a) сумма x[n]*(a*x[n]+b-y[n]) = 0
2.(по b) сумма (a*x[n]+b-y[n])=0
упрощаем:
1. a*Sxx+b*Sx=Sxy
2. a*Sx+b*S1=Sy
здесь:
Sxx=сумма x[n]*x[n]
Sx=сумма x[n]
Sy=сумма y[n]
Sxy=сумма x[n]*y[n]
S1=сумма 1=N (количество отсчётов)

таким образом на каждом шагу нам нужно:
1. пересчитать всякие S
2. по ним определить оптимальные a и b
для пересчёта всех S совсем не нужно хранить все отсчёты от начала обработки - вполне достаточно их предыдущих значений+очередные значения x[n] и y[n]

maxim1000, то что ты описываешь это я как понимаю метод наименьших квадротов или линия тренда 1го порядка... ну да по сути ты прав, знать все члены вовсе не обязательно, можно просто к каждой сумме добавлять новое слагаемое, вот меня только количество беспокоит, т.е. чем долше будет работать алгоритм тем больше будет значение N и суммы, не говоря уже о суммах произведений, и если предположим у меня новые значения приходят часто, то хранение и использование постоянно возрастающих величит составляет проблему... найти бы какой-нибудь способ всего этого избежать....


ЗЫ
У кого-нить то что Aloha дал работает нормально?

чтобы избегать переполнения можно сделать так:
на каждом шаге умножать все суммы на число, меньшее 1
само умножение на результат никак не повлияет (т.к. соотношения останутся теми же), но в совокупности с прибавлением на каждом шагу даст такой эффект, что больше всего на результат будут влиять последние отсчёты, а с увеличением "давности" информации её влияние будет экспоненциально убывать...

Спасибо.

A = (<xy> - <y><x>) / (<x^2> - <x>^2)
B = (<x^2><y> - <xy><x>) / (<x^2> - <x>^2)

грубо говоря разность степеней числителя и знаменателя у A равна нулю, чего не скажешь про B, так что если я умножу каждую сумму на n*C, где C некоторая постоянная, а n это количество множителей в каждом слагаемом суммы, то получю следующее:

A' = (C^2<xy> - C^2<y><x>) / (C^2<x^2> - C^2<x>^2) = A
B' = (C^3<x^2><y> - C^3<xy><x>) / (C^2<x^2> - C^2<x>^2) = CB != B

так что для B это не прокатит, но по сути это слагаемое мне и не нужно, главное найти угол. и по-моему то что ты предлагаешь сразу же будет давать неправильный результат. первый-то раз я конечно вычислю правильно, а вот при последующих расчетах у меня результат не будут совпадать с тем что есть на самом деле. путь я начал анализироваль начиная с получения m'го значения (сделал небольшую задержку), получил суммы, одна из которых, например, S m (x) = C*SX, где SX это какая она должна быть без умножения, потом получил m+1 значение и сумма стала уже  S m+1 (x) = C*(C*SX + x[m +1]).... это вроде уж слишком круто, чтобы вот так прям урезать суммы...  а что если я знаю, что лесенка периодически повторяется (не одна ступенька, а вся лестница целиком - доходит до определенного значения, потом резко прыгает до первоначального положения и снова скатывается внизу, естественно переход, он же прыжок вверх, я учитывают при расчетах) и просто вновь полученное значения я делю на максимальную ординату всей этой периодичной лесенки? таким образом, получу суммы значений, не превосходящих единицы (опять таки на B наплевать), при всем при этом S m (x) = SX / C, а слудующая сумма S m+1 (x) = SX / C + x[m + 1] / C = (SX + x[m+1]) / C.... получаем что каждое слагаемое суммы одинаково важно для конечного результата... В этом есть смысле???

На самом деле, maxim1000, идея с затуханием значения старых элементов имеет смысл, нужно больше доверять относительно свежим элементам... (хотя если подумать с другой стороны, то можно решить что новые значения могут быть просто какими-то всплесками, отклонениями от нормального значения, а мы постараемся следовать за ними и ничего хорошего не выйдет...) вот только бы было это не так круто и не с такой погрешностью, которая появляется уже со второго шага... Может можно и это как-то обойти?

ну не знаю, я саму систему не решал, но в этом решении что-то не так: оно, как минимум, не содержит S1
я смотрю на систему уравнений:

и вижу, что при умножении всех S на константу ничего не меняется

не содержит твоей S1 потому что я все поделил на N = S1

1. a*Sxx+b*Sx=Sxy
2. a*Sx+b*S1=Sy

получил

1. a*<xx>+b<x>=<xy>
2. a*<x>+b=<y>

где <x>, <xx>, <xy>, <y>... это средние величины

b = <y> - a*<x>
a * <xx> + <x><y> - a*<x>^2 = <xy>
a = (<xy> - <x><y>) / (<xx> - <x>^2)
b = ...

да и вообще это можно сказать табличные формулы.... в любой книжке по обработке экспериментальных данных есть.

если ничего не делить то выражения получаются такие

a = (Sxy - SxSy/N) / (Sxx - SxSx/N)
b = (SxxSy/N - SxySx/N) / (Sxx - SxSx/N)

и если считать N тоже суммой (чего не сделал я в пердыдущий раз) то как раз и получается что умножение всех сумм на постоянный коэффициент никак не повлияет на конечный результат...)))

Это сообщение отредактировал(а) uvsoft - 18.10.2006, 11:39

именно это и имелось в виду 

протестил... как и педполагалось все это дело оч неустойчиво.... т.е. например приходят у меня точки и вдруг происходит резкий всплеск, и аглорит уже пререстает выдавать корректное значения которое он держал до этого... хотелось бы сделать его более устойчивым к таким вещам... и все равно я склоняюсь к теории фильтрации, вот только одна беда - я в ней полный 000... нашел какой-то курс лекций по теориии управления (http://window.edu.ru/window_catalog/files/r24738/5.pdf), вот там на 74 странице описываются фильтры, только там такие страшные формулы, просто нереально разобраться как это можно реализовать...

вообще наверняка есть люди которые разбираются во все этом... где же вы?!))

а тут ведь такое дело: если пришла точка, которая сильно не вписывается в прогноз, алгоритм думает, что его прогноз не верен (кстати, иногда это действительно так)...
в принципе, можно считать статистику по всем точкам, потом отбрасывать те, которые сильно от неё далеки, и считать уточнённую статистику по оставшимся
хотя это, конечно, усложнит процесс...

Это сообщение отредактировал(а) maxim1000 - 18.10.2006, 14:24

ммм даа.... тупик какой-та

кстати, пришла мысль:
нужно чётко разделить два случая:
1. характеристики сигнала могут меняться во времени
2. характеристики сигнала постоянны
в первом случае резкий скачёк сигнала и должен восприниматься алгоритмом, как симптом изменения параметров сигнала
во втором случае сама идея "бОльшего доверия последним значениям" неправильна
для второго случая основной проблемой, как мне видится, есть банальное переполнение аккумуляторов переменных S
тогда можно, например, сделать так:
1. после каждых 10 (к примеру) отсчётов считать для них весь набор переменных S
2. тогда для того, чтобы подсчитать S для последних 20 отсчётов достаточно взять среднее арифметическое от этих "10-отсчётных" S и предыдущих (их можно хранить)
3. для 20 отсчётов понадобится ещё одна копия
таким образом, размер требуемой памяти будет пропорционален логарифму количества отсчётов, которое мы захотим учитывать, а то - не так уж и много...

касательно ошибок способас затуханием - нужно хорошенько поэкспериментировать с коэффициентом затухания
если алгоритм слишком чувствителен к скачкам, сдвинуть коэффициент поближе к 1

мой случай наверное все же второй, характеристики сигнала постоянны, но заранее не известны. поэтому действительно, если работать с бесконейной памятью предыдущих точек, то возникает только одна проблема - переполнение. первые два шага твоего алгоритма я понял, т.е. помним суммы пердыдущих 10 отсчетов, знаем суммы текущих 10 отсчетов, находим нечто S'''(10) = (S'(10) + S''(10)) / 2, получаем среднюю сумму по 10 за педыдущие 20 шагов, потом ждем еще 10 шагов, находим среднюю сумму по ним S''''(10) и используем S'''(10) для получения очередной средней суммы по 10 за предыдущие 20 шагов, но на самом деле это будут не предыдущие 20 шагов, а все 30, т.к. S'''(10) вычислялась с учетом самых первых 10. таким образом общая формула примет вид:

S(x, n, m)[k] = { S(x, n, m)[k - m + 1] + ... + S(x, n, m)[k - 1] + x0 + ... + x(n - 1) } / m

где
S - сумма, в скобках ее параметры,
x - это то, чего сумма (т.е. в моем случает это будут суммы x, xx, xy, y),
n - порядок суммы, количество точек по которым она вычисляется,
m - количесто сумм для вычисления очередной средней суммы,
k - номер итерации.

если вычисляются десятками и очередная сумма считается по предыдущим двум, то вот частный случай

S(x)[k] = { S(x)[k - 1] + x0 + ... + x9 } / 2

а вот насчет твоего третьего пункта и логарифмической зависимости не врубился....
для того, что я написал, памяти нужно  M * (максимально_возможная_сумма - 1), чтобы хранить предыдущие суммы и соответственно N * (максимально_возможный_элемент) для хранения текущих отсчетов. как только посчиталась очередная сумма, самая первая считается недействительной и ее вытесняет вновь прибывшая.

так?? или я что-то перепутал или не учел )))

Добавлено @ 11:39 
тока вот это все равно все упирается в количество отсчетов по которому считается сумма (параметр n). есть у меня какое-то значение суммы на каком-то k-ом шаге. считаю сумму на текущем, а у меня, предположим, пришли такие величины!!! (напрер n не хватает чтобы охватить две ступеньки, а точнее начало одной и конец следующей, а хватает только чтобы сам скачек поимать), что после усреднения старой с новой, получится полный бред и все предыдущие вычисления коту под хвост....

короче, думаю ты не это имел ввиду, поясни, пожалуйста что там с логарифмами....

через каждые 10 отсчётов обновляется S для 10 отсчётов
через каждые 20 - для 20
через каждые 40 - для 40
при этом каждое SN использует два последовательных значения S(N/2)
так что для каждой длины анализируемого интервала нужно хранить всего 2 переменных (два последовательных значения S)
а т.к. длины растут экспоненциально, то необходимое количество переменных пропорционально логарифму

и до какого же N1 мне это делать и с какого N2 снимать сумму для проведения расчетов линии тренда? суммы SN то все равно будут возрастать с увеличением N, как это поможет от переполнения?

на этот раз надо использовать средние их значения
т.е. S20=(S10текущее + S10предыдущее)/2
тогда порядок значений сильно меняться не будет...

ясно, у всех сумм будет один порядок. получается с каждым разом мне надо все больше и больше сумм держать в памяти, чем ограничится? не приведет ли это ограничение к той же истории что и с интегрированием по конечному промежутку? и с какой суммой работать, с максимальным индексом? а если у меня этот индекс, например 160, то получается пока у меня еще 160 не насчитает значение выдаваемое алгоритмом будет постоянным... правильно ли это?

ps
кстати я тут чуток посчитал) в итоге если у меня отсчеты приходять, например, с частотой 50Гц или 20 в секунду, а каждый новый элемент будет меньше единицы и суммироваться будет к double + счетчик на dword, в которое поместится 4294967296 отсчетов, или 214748364,8 секунд или 3579139,4 минут или 59652,3 часов или 2485,5 дней или 6,8 високосных лет..... то я думаю хватит и такого варианта, лишь бы работал, но вначале надо с последним вариантом разобраться....

рост есть и там, и там
разница в го порядке
во втором случае он логарифмический, что очень часто подходит


если оценка нужна только хорошая, то поначалу было бы логично, если алгоритм откажется от прогнозов вообще (т.е. пока не сформирует первое правильное значение S для нужной длины)
если же в каждый момент времени нужна наиболее хорошая из возможных оценок (что более вероятно, исходя из рисунка), то стоит использовать S с максимально возможным индексом из тех, что известны

касательно того, когда ограничиваться:
можно просто держать динамический массив структур с переменными S в памяти и добавлять туда структуры по мере поступления информаци, достаточной для их вычисления (ну и старые тоже пересчитывать)
однако, никто не мешает его ограничивать на каком-то значении
его можно выбирать в зависимости от сигнала (можно, например, анализировать колебания значений) или, например, в зависимости от наличия свободной памяти




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