Поиск по короткому аудио фрагменту

Рад всех приветствовать, тема на мой взгляд очень интересная, начнём!

Постановка задачи

Есть короткая аудио запись продолжительностью от 3 до 6 секунд. Требуется найти: откуда она?

Практическое применение

Аудио поиск может быть востребован для поиска:

• музыки

• фильмов

• сериалов

• мультфильмов

• аниме

• аудио книг

• новостей

• ток-шоу

• радио и тв передач

• аудио записей телефонных переговоров

• интервью

• т.д.

Что люди уже сделали?

Самые известные и популярные сервисы и приложения

• Shazam

• Яндекс Музыка

• Sound Hound

• Midomi

• AudioTag

Cсылки на ресурсы в Интернет

• Shazamвикипедия

• Shazam:алгоритмы распознавания музыки,сигнатуры, обработка данных

• СоздаемShazam на Java

• КакЯндекс распознаёт музыку с микрофона

• ЯндексМузыка — Wikipedia

• AnIndustrial-Strength Audio Search Algorithm

Своя реализация

Определения

Аудио сигнал

Аудиосигнал — это представление звука в виде электрического тока или напряжения, который можно легко записать, изменить или передать по проводам.

Исходное аудио

Исходное аудио — это аудио файл или видео файл с аудио дорожкой. У файла есть имя, размер, продолжительность воспроизведения. Само аудио имеет следующие аттрибуты: частоту дискретизации, разрядность аудио сигнала, тип аудио дорожки (моно, стерео, 5.1 и т.д), кодек и битрейт.

Аудио запрос

Аудио запрос — это аудио данные в памяти компьютера или файл на диске. Имеет следующие характеристики: частоту дискретизации, разрядность аудио сигнала, тип аудио дорожки. Нет смысла сжимать аудио запрос какими либо кодеками — во-первых он имеет сравнительно небольшой размер, а во-вторых, сжатие изменяет аудио сигнал в сторону больших отличий от исходного аудио сигнала.

Огибающая

Что же такое огибающая?

Вкратце — это кривая, проходящая через пики амплитуд аудио сигнала.

Спектр аудио сигнала

Спектр — это набор значений, представляющий сигнал в частотной области.

Ключевая точка

Ключевая точка в данном случае — это точка на графике, которая обладает уникальными характеристиками для заданного отрезка, например, является точкой локального максимума в искомой области. Можно использовать и другие критерии, например, можно брать точку максимума (или минимума) Фурье-спектра для какой то частоты или области частот. Главный критерий: повторяемость и желательно небольшой объём вычислений.

Теория

Для решения задачи аудио поиска по короткому аудио фрагменту были предприняты следующие действия.

Приведение аудио данных к единому стандарту

Невозможно производить сравнение аудио сигнала не приведя его к общему виду.
Например такому:

Разрядность: 16 бит
Частота оцифровки: 48 кГц
Количество каналов: 1 (моно).

Деление на равные отрезки

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

Вычисление огибающих

Когда у нас есть две аудио записи, то чтобы не сравнивать их в каждой точке аудио сигнала, можно вычислить огибающую (силуэт) для каждого из них и сравнивать их. Дело в том, что аудио сигнал продолжительностью, скажем, 10 секунд и с частотой оцифровки 48 кГц имеет 480 тысяч отсчётов. Для огибающей, имеющей частоту 100 отсчётов в секунду, общее количество отсчётов будет лишь 1 тысяча. Меньше в 480 раз! Это позволяет экономить память и ускоряет вычисления. И тем не менее для большинства случаев (человеческая речь, значительная часть музыки, обычные звуки, вроде мычания коровы или лая собак) этой частоты огибающей вполне достаточно!

int getEnvelope(short *data, int data_size, short* &envelope) {int area_size = 480, max, value, k = 0, envelope_size;// Если указатель указывает на существующий объект, то удаляем ранее созданный массивif (envelope != NULL) delete[] envelope;// Находим кол-во элементов огибающейenvelope_size = data_size / area_size;// Создаём массив огибающейenvelope = new short [envelope_size];// Ищем в цикле значения огибающейfor (int i = 0; i < envelope_size; i++) {max = 0;// Поиск максимального значения по модулюfor (int j = 0; i < area_size; i++) {value = abs(data[k]);if (value > max) max = value;}// Присваиваем найденное значениеenvelope[i] = max;}// Возвращаем кол-во элементов в массиве огибающейreturn envelope_size;}

Проблема сравнения

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

Однако, это ещё не всё. Амплитуды образца и исходного аудио тоже могут быть различны. Это может быть связано с настройками громкости воспроизведения в плеере или браузере. Для решения этой проблемы необходимо вычислить нормировочные коэффициенты и сделать это лучше не по значениям точек локального максимума (что быстрее и проще), а по сумме модулей значений амплитуды на рассматриваемом отрезке.

Вычисление спектров

Для нахождения спектров (уникальностей) нашей ключевой точки будем использовать частотный спектр Фурье. Однако, встаёт вопрос: какого размера должна быть область для его вычисления. Понятно, что для быстрого преобразования Фурье количество отсчётов должно быть кратно 2-ке в какой то степени, но в какой?

Если брать много точек (16384, 32768, 65536), то существенно возрастает объём вычислений, а главное мы вычисляем спектр по области порядка 1/3, 2/3, 4/3 секунды. Это означает, что информация о конкретной точке размазывается и в неё включается всё больше и больше информации о соседних точках. С другой стороны, хранить и обрабатывать результаты такого спектра довольно накладно: 8192б 16384, 32768 значений — это много.

Если брать мало точек (128, 256, 512), то мы попадаем под достаточно сильное влияние отличий, возникающих при переконвертации аудио или аналоговом захвате аудио.

Довольно логичное решение брать 1024 или 2048 точек. В этом случае мы берём приблизительно 1/48 или 2/48 секунды, что достаточно хорошо локализует большинство звуков человеческой речи и музыкальных инструментов. Объём вычислений уменьшается, а чтобы не хранить 512 или 1024 значений можно их разбить на несколько групп (8-16) и хранить усреднённые значения.

// AVal - массив анализируемых данных, Nvl - длина массива должна быть кратна степени 2.// FTvl - массив полученных значений, Nft - длина массива должна быть равна Nvl.void FFTAnalysis(double *AVal, double *FTvl, int Nvl, int Nft) {int i, j, n, m, Mmax, Istp;double Tmpr, Tmpi, Wtmp, Theta;double Wpr, Wpi, Wr, Wi;double *Tmvl;n = Nvl * 2;Tmvl = new double[n];for (i = 0; i < n; i += 2) {Tmvl[i] = 0;Tmvl[i+1] = AVal[i/2];}i = 1;j = 1;while (i < n) {if (j > i) {Tmpr = Tmvl[i];Tmvl[i] = Tmvl[j];Tmvl[j] = Tmpr;Tmpr = Tmvl[i+1];Tmvl[i+1] = Tmvl[j+1];Tmvl[j+1] = Tmpr;}i = i + 2; m = Nvl;while ((m >= 2) && (j > m)) {j = j - m;m = m >> 1;}j = j + m;}Mmax = 2;while (n > Mmax) {Theta = -TwoPi / Mmax; Wpi = sin(Theta);Wtmp = sin(Theta / 2); Wpr = Wtmp * Wtmp * 2;Istp = Mmax * 2; Wr = 1; Wi = 0; m = 1;while (m < Mmax) {i = m; m = m + 2; Tmpr = Wr; Tmpi = Wi;Wr = Wr - Tmpr * Wpr - Tmpi * Wpi;Wi = Wi + Tmpr * Wpi - Tmpi * Wpr;while (i < n) {j = i + Mmax;Tmpr = Wr * Tmvl[j] - Wi * Tmvl[j-1];Tmpi = Wi * Tmvl[j] + Wr * Tmvl[j-1];Tmvl[j] = Tmvl[i] - Tmpr;Tmvl[j-1] = Tmvl[i-1] - Tmpi;Tmvl[i] = Tmvl[i] + Tmpr;Tmvl[i-1] = Tmvl[i-1] + Tmpi;i = i + Istp;}}Mmax = Istp;}for (i = 0; i < Nft; i++) {j = i * 2;FTvl[i] = 2 * sqrt(pow(Tmvl[j], 2) + pow(Tmvl[j+1], 2)) / Nvl;}delete[] Tmvl;

Поиск ключевых точек

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

/*Ищем ключевую точкуВозвращает true или false - нашли или не нашли.buf[len] - массив аудио данных(a, b) - отрезок на котором осуществляется поискВыходные данные:pos - позиция ключевой точкиradius - радиус превосходства ключевой точки*/bool FindControlPoint(short *buf, int len, int a, int b, int &pos, int &radius) {int v1, v2, v3;int left_radius, right_radius;// Проверка границif (a <= 0) a = 1;if (b >= len) b = len - 1;pos = 0;radius = 0;// Цикл по точкамfor (int i = a; i < b; i++) {v1 = abs(buf[i - 1]);v2 = abs(buf[i]);v3 = abs(buf[i + 1]);if ((v2 > v1) && (v2 > v3)) { // Точка максимума// Находим левый радиусfor (int j = 2; j < 65536; j++) {if (i - j < 0) { // Выход за левую границуleft_radius = j;break;}// Значения слева и справаv1 = abs(buf[i - j]);if (v1 >= v2) { // Достигли левого берегаleft_radius = j;break;}if (j == 65535) {left_radius = j;break;}}// Находим правый радиусfor (int j = 2; j < 65536; j++) {if (i + j >= len) { // Выход за правую границуright_radius = j;break;}// Значения слева и справаv3 = abs(buf[i + j]);if (v3 >= v2) { // Достигли левого берегаright_radius = j;break;}if (j == 65535) {right_radius = j;break;}}if (left_radius > right_radius) left_radius = right_radius;//if (left_radius + right_radius > radius) { // Нашли лучшего кандидатаif (left_radius > radius) { // Нашли лучшего кандидатаradius = left_radius;pos = i;}}}return radius > 0;}

Алгоритм поиска

• Цикл по ключевым точкам

• Сравнение спектров

• Сравнение огибающих

• Добавление результатов поиска в набор

• Сортировка результатов и выбор наилучших

Помощники

Для извлечения аудио дорожек из видео, преобразования их в необходимый формат, удобный для обработки, а также получения ID3 тэгов из файлов, которые эти тэги содержат можно использовать широко известные бесплатные утилиты:

• FFMPEG

• SOX

• ID3TagsCLI

Для работы с аудио в C++ Builder я использовал библиотеку BASS, а захват аудио из приложений осуществлялся с помощью немного модифицированного кода приложения «Application loopback audio capture».

Некоторые полезные команды для работы с видео и аудио

Получить информацию о видео

ffmpeg -i "имя_файла"

Получить кол-во видео дорожек

ffprobe -v error -select_streams v -show_entries stream=index -of csv=p=0 "имя_файла"

Получить кол-во аудио дорожек

ffprobe -v error -select_streams a -show_entries stream=index -of csv=p=0 "имя_файла"

Получить кол-во дорожек субтитров

ffprobe -v error -select_streams s -show_entries stream=index -of csv=p=0 "имя_файла"

Получить конкретную аудио дорожку

ffmpeg -i "имя_файла" -vn -map 0:a:0 "имя_файла"

Получить информацию о дорожке (кол-во каналов)

ffprobe -v error -select_streams a:0 -show_entries stream=codec_name,channels,channel_layout -of default=noprint_wrappers=1:nokey=1 "имя_файла"

Получить полную информацию о дорожке (кол-во каналов)

ffprobe -v quiet -print_format json -show_streams "имя_файла"

Преобразовать WAV файл в DAT файл

sox.exe "имя_файла" --bits 16 --channels 1 --encoding signed-integer --rate 48000 --type raw "имя_файла_результатов"

Получить конкретную дорожку субтитров

ffmpeg.exe -i "имя_файла" -map 0:s:0 "имя_файла_результатов"

Получить ID3 теги из медиа файла

Id3TagsCLI "имя_файла"

Приложение

• Аудио Поиск

• Аудио Индекс

Логика работы с программным комплексом следующая. На первом этапе небходимо создать в программе «Аудио Поиск» базу данных, добавить в проект медиа файлы (аудио и / или видео) и запустить процесс индексации. В результате аудио информация будет обработана и добавлена в базу данных. Далее, можно запускать программу «Аудио Поиск» и выбрать в ней созданную базу данных. После чего можно в любом приложении (браузере, аудио или видео плеере) воспроизвести любой фильм, песню, аудио книгу и т. д. Программа «Аудио Поиск» по нажатию кнопки «Поиск» или «Автопоиск» захватит воспроизводимое аудио и осуществит поиск по базе данных, а результаты покажет в соответствующем информационном блоке.

Функционал

• Создание базы данных проиндексированного аудио.

• Индексация аудио данных из аудио файлов.

• Индексация аудио данных из видео файлов.

• Получение статистики по базе данных.

• Просмотр проиндексированных данных.

• Захват аудио с микрофона, микшераили любого другого аудио устройства.

• Поиск названия и позиции воспроизводимого трека (фильма, сериала,песни, аудиокниги) по захваченному аудио фрагменту.

Скриншоты

Тестирование

Для тестирование использовались компьютеры со следующие параметрами:

• IntelXeon E5-2680 V4 @2.4GHz, 128 Gbytes DDR4

• IntelXeon E5-2650 V2 @2.6GHz, 64 Gbytes DDR3

• IntelCore I5-3479 @3.2GHz, 16 Gbytes DDR3

Результаты

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

• Скорость индексации аудио меня вполне удовлетворяет, главным образомблагодаря приложениям FFMPEGи SOX.

• Скорость поиска далека от идеала, хотелось бы большего, вероятно следует более тщательно заняться распараллеливанием вычислений.

Выводы

• Теория (что огибающая достаточногоразмера может быть использована для поиска аудио) работает на практике, что и требовалось доказать.

Неожиданные моменты

• При подключенииблютус наушников и проигрывании трековв таком режиме, качество распознаванияаудио треков резко падало,чего не наблюдалось при выводе звукачерез обычные колонки или HDMI-разъёмтелевизора. Этот момент совершенно непонятен, т. к. захват звука от приложений осуществляется с помощью устройств ввода, а не вывода.

• При конвертированииMP3-файлов в WAV или DAT формат, программа SOX генерирует каждый раз различные файлы. Разница есть лишь для небольшого процента отсчётов и значения отличаются где-то на единицу. Т.е. на слух, звук практически неотличим. Тем не менее файлы получаются различными (хэш суммы разные), что меня в какой то момент сильно сбивало с толку. Между тем, конвертирование с помощью FFMPEGиз MP3 в WAV стабильно даёт одинаковый результат!

• При работе с базой данныхSQLite столкнулся с проблемойхранения (чтение и запись) целых значений размером более 2^31. К счастью, поиск проблемы в Интернет далрезультат. Решениепроблемы с AsLargeInt (дляразмера исходного файла > 2ГБ)

• Некоторое время спустя, работая над следующей версией программы«Аудио Поиск» пытаясь повысить скоростьработы с потоками случайно наткнулся на статью на Хабре «Невидимыйвраг многопоточности: False Sharing и кэш-линиипроцессора» которая мне очень помогла понять почему скорость поиска ниже того, что я ожидал.

Вопросы

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

• Сколько памяти требуется Shazam для храненияиндексной информации одного аудиочаса?

• А сколько памяти нужно для решения аналогичной задачи Яндексу? Вот, есть информация по, скажем, 15 песням суммарной длительностью 1 час. Сколько памяти нужно для хранения информации, используемой во время поиска?

• Сколько запросов поступает на сервера гигантов индустрии вроде Shazam, SoundHound, Яндекс, AHAMusic, AudD, Musixmatch и сколько серверов их обрабатывают?

• Неужели релама на сайте окупает затраты, необходимые для обработки аудио треков, хранения информации на серверах, необходимое обслуживание и Интернет трафик?

• А есть ли приложения для создания своих баз данных со своимконтентом? Например, теле или радио компания индексирует свои эфиры и понеобходимости слушает эфиры других компаний на предмет плагиата. У Google в YouTube давно реализована функция проверки на использование в публикуемых видео роликах музыки исполнителей. Но есть ли что то подобное для небольших компаний, по доступной цене?

• А есть ли в открытом доступе базы данных проиндексированного аудио, доступного для скачивания и использования в коммерческих целях?

• Есть ли сервисы, где по хэшу (MD5 или SHA или любому другому) можно получить информацию о файле? Например, есть MP3 файл с музыкой или аудио книгой. Посчитав хэшсумму и обратившись к нужному серверу в ответ получаем имена исполнителей,название трека и т. п. Ну или хотя быссылку или несколько ссылок на страничку, где эту информацию можно получить.Планы на будущее

Планы на будущее

• Оптимизировать размер индексной информации, чтобы база данных со 100 000 — 1 000 000 часамипроиндексированного аудио могла бы быть запущенной на обычном современномкомпьютере.

• Улучшить алгоритмы поиска для того, чтобы поисковый запрос мог быть выполнен за несколько секунд.

• Попробовать отказаться от использования огибающей и осуществлятьпоиск только за счёт ключевых точек иих спектров.