Jump to content

    
Sign in to follow this  
getch

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

Recommended Posts

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

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

 

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

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

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

Share this post


Link to post
Share on other sites

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

 

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

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

Вариантов если их окажется меньше то просто будешь по этому словарю искать наиболее близкое слово.

Или подумать о нечетком поиске или о эвристических методах и др способах кластеризации.

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

 

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

 

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

Share this post


Link to post
Share on other sites

Share this post


Link to post
Share on other sites

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

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

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

 

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

Share this post


Link to post
Share on other sites
метод наименьших квадратов не подходит?

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

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

Share this post


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

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

Share this post


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

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

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

 

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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this