Нахождение самого похожего участка в сигнале, БПФ, БПХ и другие методы Опции

[getch]

Приветствую всех!

Я от ЦОС далек, но задача, по-моему, найдет здесь понимание.

Постановка задачи:
1. Есть ВР (временной ряд (вещественный), LEN точек), который с определенной частотой дополняется новым членом.
2. Есть Шаблон - N точек.
3. Надо найти в ВР участок, который наиболее сильно "похож" на Шаблон. Соответственно, в этом участке тоже N точек.

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

Нашел два оптимизированных алгоритма расчета быстрой корреляции: через БПФ (вещественное) и БПХ (Хартли).

Честно говоря, математическую часть алгоритмов слабо понимаю. И у меня возникло несколько вопросов:
1. Имеет ли смысл для моей задачи (с точки зрения скорости выполнения) использовать алгоритм БПФ для длин векторов, не являющихся степенями двойки? Это работы Бейли, Просекова и другие.
2. БПФ Винограда?
3. Возможно, есть другой эффективный критерий похожести, отличный от КК.
4. Задача, очевидно, стандартная и максимально эффективный велосипед уже давно изобретен. Подскажите, как официально она называется?
5. Какие могут быть оптимизации, чтобы не проделывать полностью вычисления БПФ? Поясню ниже на примере двух случаев:

1. Шаблон - это крайние N точек исходного ВР из Len точек. Пришло новое значение ВР, т.е. его длина стала (Len + 1) точек. Шаблон, соответсвенно "сместился" вправо (изменился) тоже на одно значение. БПФ заново пересчитывать?
2. Шаблон - это какой-то участок из N точек исходного ВР. Если я сдвигаю шаблон на одну точку в какую-то сторону, БПФ надо будет полностью пересчитывать?

И еще один вопрос, если надо найти похожий участок не только на шаблон, но и на "перевернутый шаблон" - точки в обратном направлениии (Было {1, 2, 5, 7}, стало {7, 5, 2, 1}), то можно ли из "нормального" БПФ перейти эффективно к "перевернутому" БПФ?

Уверен, моя косноязычная формулировка задачи вызовет улыбку у форумчан, особенно у гуру. Но это все же хорошие эмоции. Готов учиться и вникать.

P.S. Если возможно, разъясните на более понятном языке, что имелось в виду в этом посте (Сообщение #28)?

[ivan219]

Так мне же и надо иметь (Len - N) значений КК, чтобы среди них выбрать максимальное абсолютное значение. Т.е. если делать в лоб, то надо вычислить (Len - N) скалярных произведений векторов длины N. Поэтому и интересуюсь быстрой корреляцией через БПФ, БПХ и другие методы.

Тогда вам потребуется взять БПФ размеров 2 * (Len - N) округлёныый в большую сторону до степени двойки.
Нужно взять БПФ сигнала и БПФ образца после чего сделать комплексно сопряженный БПФ обрасца. Для этого нужно поменять знак его мнимой части. И перемножить эти спектры. После чего взять обратный БПФ в итоге получите 2 * (Len - N) коэфицентов корреляции.
Код могу привести на Delphi

Можете пояснить более подробно для слабо-разбирающегося в ЦОС?
Делается БПФ после чего у всех мнимых величин меняется знак на противоположный.

Сообщение отредактировал ivan219 - Sep 2 2011, 19:13

[getch]

Написал алгоритм быстрой корреляции через БПФ.
Как понял, быстрая корреляция, это то, что и ранее предлагалось - сумма попарных произведений. Но такой критерий похожести явно не работает в общем случае (когда у выборок МО != 0 и СКО != 1), т.к. максимум такой корреляции показывает совсем не там, где надо.
Подскажите, как от быстрой корреляции перейти к Пирсону с той же эффективностью алгоритма O(N * log(N))?

[getch]

Врубился, как сделать. Надо лишь перед БПФ привести шаблон к нулевому среднему и СКО единица.
А после вычисления через БПФ быстрой корреляции делить полученные элементы массива значений КК на СКО соответствующих выборок в сигнале.
При этом вычисление этих СКО дается практически бесплатно - итерационно.

[getch]

Подскажите, есть ли возможность из RealFFT(Signal, SignalLen) получить RealFFT(Signal, SignalLen + 1)?
Т.е. при приходе нового значения сигнала нужно ли проделывать полностью БПФ или же можно из предыдущего результата БПФ получить текущий?