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

[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)?

[Alexey Lukin]

Если на каждом новом отсчёте меняется и шаблон, то я не понимаю, как БПФ ускорит вычисление корреляции в одной точке. Или с каждым новым шаблоном надо считать корреляцию во множестве точек?

[getch]

Да, с каждым новом шаблоном нужно считать корреляцию во всем множестве точек исходного сигнала.

И тут есть две ситуации:
1. Меняется только шаблон, сигнал - нет. Тогда БПФ сигнала делать повторно не требуется при расчете корреляции. Делается только прямое БПФ шаблона и обратное БПФ.
2. Меняется и шаблон и сигнал (добавляется один отсчет). Вот тут и хочу БПФ сигнала с новым отсчетом получить из ранее посчитанного БПФ сигнала без этого отсчета.

[getch]

На другом форуме есть очень схожая по задаче тема: Распознавание звукового сигнала (звука) по образцам.

Привожу цитату одного поста оттуда:

Я бы делал так. Взял бы базу. Для каждого фаила разбить на фрагменты с 50% перекрытием
Каждый фрагмент длительностью около 0.1с (44.1КГц*0.1=4410 отсчетов) все фрагменты имеет одинаковую длительность.

Вычислить для каждого фрагмента БПФ найти максимумы амплитуды в полосах
0-2Гц
2-4Гц
4-8Гц
8-16Гц
16-32Гц
32-64Гц
64-128Гц
128-256Гц
256-512Гц
512-1024Гц
1024-2048Гц
2048-4096Гц

итого 12 коэффициентов, в секунде будет 240 коэффициентов вместо ваших 4000 что в 20 раз быстрее будет.
пусть у нас в среднем 5 минут на 1000 файлов= 5*60*240*1000= 72 000 000 будет считаться за доли секунд
Но это не все если эти коэффициенты представить в виде чисел от 0..255 или 0..16 то возможно составить словарь.
Вариантов если их окажется меньше то просто будешь по этому словарю искать наиболее близкое слово.
Или подумать о нечетком поиске или о эвристических методах и др способах кластеризации.

Т.е. предлагаются альтернативные корреляции варианты, а также упоминается возможность значительного уменьшения признаков сравнения.

Кто-нибудь использовал отличные от корреляционного методы или занимался уменьшением признаков сравнения?

У меня корреляция через оптимизированный (насколько мог) БПФ считается, к сожалению, не так быстро, как хотелось бы.

[getch]

Поискал в интернете схожие задачи. Выкладываю ссылки, возможно, кому-то пригодятся:

Контурный анализ.
Видео создания шаблона.
Видео нахождения шаблона(-ов).

Обнаружение устойчивых признаков изображения: метод SURF.

«Выглядит похоже». Как работает перцептивный хэш.

Алгоритм быстрого нахождения похожих изображений.

Презентация «Поиск изображений. Методы индексирования изображений. Методы на основе хэш-функций. Обучение метрик. Фильтры объектов для классификации и поиска изображений.» (из курса лекций Введение в компьютерное зрение)

Блог Распознавание образов для программистов.


Тематические реализации (поисковики):

Поиск изображений по исходному изображению.
Распознавание шрифта по картинке.
Поиск песни по ритму.
Поиск песни по аудио-образцу.
Поиск песни по напеву.