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