Принцип работы алгоритма Шазам — подробное описание программного уровня, этапы обработки аудиосигнала и поиск соответствий

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

Работа алгоритма Шазам начинается с предобработки аудиофайла. Вначале он преобразует звуковую волну в спектрограмму — график зависимости интенсивности звука от времени и частоты. Для этого применяется оконное преобразование Фурье, которое разбивает массив данных на короткие участки, называемые фреймами, и преобразует каждый из них из временной области в частотную.

Полученная спектрограмма разбивается на прямоугольные блоки, называемые атомами. Каждый атом описывается набором нескольких значений — адресом, временным и спектральным содержимым. Адресом является комбинация частоты и времени, по которой можно идентифицировать атом. Спектральное содержимое представляет собой массив значений спектра звука, а временное содержимое — длину фрагмента аудиофайла, соответствующего данному атому.

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

Предобработка аудио

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

Первым шагом предобработки является дискретизация аудиофайла. Это процесс приведения непрерывного сигнала аудиозаписи к дискретным значениям. Европейский стандарт для аудиофайлов — 44,1 кГц, что означает, что аудиофайл разбит на 44100 отсчетов в секунду. Более высокая частота дискретизации обеспечивает более точное представление аудиосигнала, но требует большего объема памяти и вычислительных ресурсов.

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

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

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

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

Создание спектрограммы

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

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

Для визуализации спектра используется цветовая гамма или градиент, где каждая точка на спектрограмме соответствует определенной частоте и времени. Яркость или цвет точки определяется амплитудой или энергией соответствующего спектрального компонента.

Созданная спектрограмма позволяет визуально оценить спектральные характеристики аудиофайла и выделить уникальные особенности, которые будут использоваться в последующих этапах алгоритма Шазам.

Создание хэшей

1. Разделение аудиозаписи на сегменты.

Аудиозапись разделяется на небольшие сегменты фиксированной длительности. Обычно сегменты имеют длину 2-5 секунд. Малая длительность сегмента позволяет более точно характеризовать уникальные особенности звукового сигнала.

2. Преобразование сегментов в спектрограмму.

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

3. Создание отпечатков сегментов.

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

4. Сравнение и запись хэшей.

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

5. Индексирование хэшей.

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

Построение таблицы хэшей

Для построения таблицы хэшей необходимо выполнить следующие шаги:

1. Разделить входной аудиофайл на несколько коротких сегментов фиксированной длительности. Обычно это делается с помощью оконных функций, таких как Хэмминг или Ханнинг.
2. Применить преобразование Фурье к каждому сегменту, чтобы получить спектрограмму, которая показывает распределение энергии различных частот во времени.
3. Разделить спектрограмму на бины, которые представляют собой участки спектра, соответствующие небольшим интервалам частот.
4. Вычислить спектральные пики для каждого бина, которые являются наиболее выраженными точками энергии в спектрограмме.
5. Создать хэш для каждого спектрального пика, объединив его частотный индекс в бине и временную позицию в сегменте.
6. Сохранить хэши в таблице хэшей, осуществляя сортировку и индексацию для ускорения последующего поиска.

Построение таблицы хэшей позволяет эффективно и быстро находить соответствия между хэшами семплов аудио и базой данных.

Таблица хэшей является важным компонентом алгоритма Шазам и представляет собой основу для успешного распознавания музыки и других аудиозаписей.

Поиск совпадений и идентификация аудиозаписей

Для этого алгоритм проходит через несколько этапов:

1. Разделение на под-дорожки: Аудиофайл разделяется на небольшие под-дорожки, как правило, продолжительностью несколько секунд.
2. Вычисление спектрограмм: Для каждой под-дорожки вычисляется спектрограмма, которая представляет собой двумерное представление сигнала в частотно-временной областях.
3. Формирование отпечатков: Исходя из спектрограммы каждой под-дорожки, формируются уникальные отпечатки, которые представляют собой набор значений характеристик сигнала, таких как высота и громкость.
4. Индексирование: Отпечатки добавляются в базу данных, где они индексируются для более эффективного поиска.
5. Поиск совпадений: При поступлении новой аудиозаписи алгоритм вычисляет ее отпечаток и сравнивает с отпечатками в базе данных. Если найдены совпадения, то алгоритм возвращает информацию об идентифицированной аудиозаписи.

Таким образом, алгоритм Шазам позволяет эффективно идентифицировать аудиозаписи на основе их уникальных характеристик, таких как высота и громкость. Это делает его незаменимым инструментом в таких областях, как музыкальное распознавание и поиск аудиофайлов.