сравнение файлов WAV

Question

У меня есть (в основном) рабочая программа для сравнения двух файлов wav, чтобы увидеть, находится ли меньший в большем. Это сделано в Java.

Я делаю это, сначала убедившись, что оба wav-файла представлены в каноническом волновом формате. Затем я получаю из них байтовый массив данных, используя AudioInputStream. Я вынимаю данные порциями с определенной частотой кадров (например, прямо сейчас: 4096 байт). Я беру первый блок меньшего ввода и прохожу фрагменты того же размера на большом входе.

Я беру эти куски и создаю двойные массивы с одинаковыми данными. Я получаю их БПФ и использую функцию корреляции, чтобы найти пик в результирующем массиве коэффициентов корреляции. Затем я перехожу к следующему фрагменту меньшего входа и вижу, появляется ли аналогичный пик.

Это работает, пики очевидны, когда файлы одинаковы, и в большинстве случаев результаты верны. Я не получаю ложных срабатываний. Я, однако, получаю ложные негативы.

Это потому, что я не уверен, как "выровнять" данные. Меньший файл может прийти из любой точки большего файла. В большинстве случаев это происходит с помощью метода чанкинга, который я делаю. Но иногда, это как если бы файлы отличались, и пик не был найден, хотя файлы должны возвращать высокую корреляцию.

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

Я не уверен, как «выровнять» кусок меньшего файла по месту его появления в большем файле, чтобы функция корреляции определяла, где происходит корреляция. Все работает, мне просто нужно устранить ложные негативы. Любой совет?

Answer 1

Это называется согласованным фильтром . Ваша реализация страдает из-за чанкинга. Традиционно вы берете входные данные как непрерывный поток, извлекаете блок, начиная с каждого семпла, и выполняете корреляцию. Поэтому, если ваш вход имеет длину 10 тыс. Выборок, вы в конечном итоге запускаете фильтр 10 тыс. Раз, каждый раз беря 4 тыс. Выборок в фильтр (в вашем примере). Тем не менее, это медленно. Есть несколько способов ускорить процесс:

1. Используйте небольшие куски, например, 256 точек, чтобы ускорить вычисления FFT. Ваши корреляции, вероятно, не будут выглядеть так же хорошо, что приведет к большему количеству ложных срабатываний, но, возможно, вы сможете составить список возможных совпадений и вернуться назад и посмотреть с большими кусками.

2. Вместо того, чтобы брать буферы, начиная с каждого сэмпла на входе, скажем, брать 4k буферов, начиная с каждого 512-го сэмпла, и делать корреляции (аналогично предложению Марсело Кантоса в его комментарии) . Затем ищите пики в пределах 512 сэмплов вокруг середины, поскольку сдвиг по времени вызовет смещение пика. Кроме того, дополнительные некоррелированные выборки по краям приведут к тому, что пик не будет полноценным, поэтому вам нужно ослабить это ограничение, если оно у вас есть. Опять же, это может привести к большему количеству ложных срабатываний, поэтому вам снова придется прибегнуть к подходу со списком.

Что касается деталей реализации, я предполагаю, что вы уже предварительно вычислили фрагменты из меньшего файла? Кроме того, вы не говорите, проверяете ли вы корреляцию во временной или частотной областях. Вы могли бы искать плоскую величину в частотной области, которая была бы равна скачку во временной области, чтобы сэкономить обратное БПФ. Вам нужно будет провести несколько экспериментов, чтобы определить, насколько плоский спектр, но это может значительно сократить время.

Answer 2

Используйте сверточный фильтр для сравнения двух сигналов. Он скажет вам, если и где происходит совпадение. Быстрые алгоритмы для вычисления сверток доступны .

Answer 3

Вы можете взглянуть на эту статью .Он объясняет алгоритм, используемый сервисом shazam, который идентифицирует музыку из образца за несколько секунд.
Другой метод здесь , использующий самоорганизующиеся карты для кластеризации похожей музыки.Не совсем то, что вы хотите сделать, но это может дать вам идеи.

Answer 4

Я не уверен, что полностью понимаю алгоритм, который вы используете, но вот мысль: если вы можете заставить волны распознаваться, отбирая биты вручную в начале и в конце, разве это не является возможным решением для вашего алгоритм тоже?