Нахождение самого похожего участка в сигнале

[getch 0]

Если сигнал поступает по 1 отсчёту, то ни Герцель, ни БПФ вам вообще не нужны. Считайте корреляцию в лоб.

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

[Alexey Lukin 0]

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

[getch 0]

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

 

И тут есть две ситуации:

1. Меняется только шаблон, сигнал - нет. Тогда БПФ сигнала делать повторно не требуется при расчете корреляции. Делается только прямое БПФ шаблона и обратное БПФ.

2. Меняется и шаблон и сигнал (добавляется один отсчет). Вот тут и хочу БПФ сигнала с новым отсчетом получить из ранее посчитанного БПФ сигнала без этого отсчета.

[getch 0]

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

 

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

Я бы делал так. Взял бы базу. Для каждого фаила разбить на фрагменты с 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 0]

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

 

Контурный анализ.

Видео создания шаблона.

Видео нахождения шаблона(-ов).

 

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

 

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

 

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

 

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

 

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

 

 

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

 

Поиск изображений по исходному изображению.

Распознавание шрифта по картинке.

Поиск песни по ритму.

Поиск песни по аудио-образцу.

Поиск песни по напеву.

[eugen_pcad_ru 0]

Кхм, может я глупый вопрос задам, но:

метод наименьших квадратов не подходит? Корень из суммы квадратов разностей реального фрагмента и идеального фрагмента?

Минимальная сумма соответствует наибольшей "похожести". При полном соответсвии получите нуль.

 

P.S.: Хотя может я чего и не понял:)

[getch 0]

метод наименьших квадратов не подходит?

Алгоритмическая сложность такого метода "лобовая" - O(N^2).

Быстрая корреляция через БПФ значительно эффективнее - O(N * log(N)).

[xemul 0]

Алгоритмическая сложность такого метода "лобовая" - O(N^2).

Ещё хуже, т.к. один из сравниваемых фрагментов придётся перед МНК отнормировать каким-то образом (каким?) под другой фрагмент.

[getch 0]

Ещё хуже, т.к. какой-то из фрагментов придётся перед МНК отнормировать каким-то образом (каким?) под другой фрагмент.

Существует итерационный алгоритм расчета СКО сдвинутого окна через СКО окна до сдвига.

Нормировка делается через деление фрагмента на его почти бесплатно полученное СКО.

 

При этом Среднее каждого фрагмента обнулять не требуется при сравнении. Надо лишь один раз отнормировать сам шаблон (что ищется) к СКО = 1 и Ср. = 0.