getch 0 Posted September 9, 2011 · Report post Если сигнал поступает по 1 отсчёту, то ни Герцель, ни БПФ вам вообще не нужны. Считайте корреляцию в лоб. Видимо, я плохо пояснил. Дело в том, что при поступлении нового отсчета меняется и шаблон. Поэтому без БПФ не обойтись. Всвязи с этим желательно производить из предыдущего БПФ (сигнала, не шаблона) новый, т.к. вычислять полностью БПФ по приходу каждого нового отсчета - очень дорого. Quote Ответить с цитированием Share this post Link to post Share on other sites
Alexey Lukin 0 Posted September 9, 2011 · Report post Если на каждом новом отсчёте меняется и шаблон, то я не понимаю, как БПФ ускорит вычисление корреляции в одной точке. Или с каждым новым шаблоном надо считать корреляцию во множестве точек? Quote Ответить с цитированием Share this post Link to post Share on other sites
getch 0 Posted September 10, 2011 · Report post Да, с каждым новом шаблоном нужно считать корреляцию во всем множестве точек исходного сигнала. И тут есть две ситуации: 1. Меняется только шаблон, сигнал - нет. Тогда БПФ сигнала делать повторно не требуется при расчете корреляции. Делается только прямое БПФ шаблона и обратное БПФ. 2. Меняется и шаблон и сигнал (добавляется один отсчет). Вот тут и хочу БПФ сигнала с новым отсчетом получить из ранее посчитанного БПФ сигнала без этого отсчета. Quote Ответить с цитированием Share this post Link to post Share on other sites
getch 0 Posted September 10, 2011 · Report post На другом форуме есть очень схожая по задаче тема: Распознавание звукового сигнала (звука) по образцам. Привожу цитату одного поста оттуда: Я бы делал так. Взял бы базу. Для каждого фаила разбить на фрагменты с 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 то возможно составить словарь. Вариантов если их окажется меньше то просто будешь по этому словарю искать наиболее близкое слово. Или подумать о нечетком поиске или о эвристических методах и др способах кластеризации. Т.е. предлагаются альтернативные корреляции варианты, а также упоминается возможность значительного уменьшения признаков сравнения. Кто-нибудь использовал отличные от корреляционного методы или занимался уменьшением признаков сравнения? У меня корреляция через оптимизированный (насколько мог) БПФ считается, к сожалению, не так быстро, как хотелось бы. Quote Ответить с цитированием Share this post Link to post Share on other sites
getch 0 Posted September 10, 2011 · Report post Поискал в интернете схожие задачи. Выкладываю ссылки, возможно, кому-то пригодятся: Контурный анализ. Видео создания шаблона. Видео нахождения шаблона(-ов). Обнаружение устойчивых признаков изображения: метод SURF. «Выглядит похоже». Как работает перцептивный хэш. Алгоритм быстрого нахождения похожих изображений. Презентация «Поиск изображений. Методы индексирования изображений. Методы на основе хэш-функций. Обучение метрик. Фильтры объектов для классификации и поиска изображений.» (из курса лекций Введение в компьютерное зрение) Блог Распознавание образов для программистов. Тематические реализации (поисковики): Поиск изображений по исходному изображению. Распознавание шрифта по картинке. Поиск песни по ритму. Поиск песни по аудио-образцу. Поиск песни по напеву. Quote Ответить с цитированием Share this post Link to post Share on other sites
eugen_pcad_ru 0 Posted September 19, 2011 · Report post Кхм, может я глупый вопрос задам, но: метод наименьших квадратов не подходит? Корень из суммы квадратов разностей реального фрагмента и идеального фрагмента? Минимальная сумма соответствует наибольшей "похожести". При полном соответсвии получите нуль. P.S.: Хотя может я чего и не понял:) Quote Ответить с цитированием Share this post Link to post Share on other sites
getch 0 Posted September 22, 2011 · Report post метод наименьших квадратов не подходит? Алгоритмическая сложность такого метода "лобовая" - O(N^2). Быстрая корреляция через БПФ значительно эффективнее - O(N * log(N)). Quote Ответить с цитированием Share this post Link to post Share on other sites
xemul 0 Posted September 22, 2011 · Report post Алгоритмическая сложность такого метода "лобовая" - O(N^2). Ещё хуже, т.к. один из сравниваемых фрагментов придётся перед МНК отнормировать каким-то образом (каким?) под другой фрагмент. Quote Ответить с цитированием Share this post Link to post Share on other sites
getch 0 Posted September 22, 2011 · Report post Ещё хуже, т.к. какой-то из фрагментов придётся перед МНК отнормировать каким-то образом (каким?) под другой фрагмент. Существует итерационный алгоритм расчета СКО сдвинутого окна через СКО окна до сдвига. Нормировка делается через деление фрагмента на его почти бесплатно полученное СКО. При этом Среднее каждого фрагмента обнулять не требуется при сравнении. Надо лишь один раз отнормировать сам шаблон (что ищется) к СКО = 1 и Ср. = 0. Quote Ответить с цитированием Share this post Link to post Share on other sites