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

Глобальный обзор

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

Прежде чем идти глубже, вот упрощенная схема того, как идентифицирует песню Shazam. Я не работаю в Shazam, так что это всего лишь предположение (из документа 2003 года от соучредителя Shazam):



На стороне сервера:

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

На стороне клиента:

• Когда пользователь использует Shazam, приложение сначала записывает текущую музыку с помощью микрофона телефона.
• Телефон применяет тот же алгоритм снятия слепка с песни, что и Shazam при добавлении слепка в свою базу данных.
• Телефон отправляет аудио слепок в Shazam.
• Shazam проверяет, совпадает ли этот слепок хотя бы с одним из базы данных:
  • Если нет, он сообщает пользователю, что трек не найден;
  • Если да, то он ищет метаданные, связанные с этим слепком (название песни, URL песни в iTunes, Amazon и т.д.) и возвращает его пользователю.

Ключевыми особенностями алгоритма по снятию слепков в Shazam являются:

• Устойчивость к шуму/ошибкам:
  • Музыка, записанная телефоном в баре/на открытом воздухе, имеет плохое качество.
  • Из-за неидеальности оконных функций.
  • Из-за дешевого микрофона внутри телефона, который создает шум/искажения.
• Слепки должны быть неизменными во времени: слепок полной песни должен соответствовать ее 10-секундной записи.
• Сопоставление слепков должно быть быстрым: кто будет ждать минуты/часы, чтобы получить ответ от Shazam?
• Отсекать ложные срабатывания: кто хочет получить ответ, который не соответствует правильной песне?

Фильтрация спектров

Звуковые слепки отличаются от стандартных компьютерных контрольных сумм, таких как SSHA или MD5, потому что два разных файла (с точки зрения битов), которые содержат одну и ту же музыку, должны иметь один и тот же аудио слепок. Например, песня в формате ACC 256 Кбит (iTunes) должна давать тот же слепок, что и та же песня в формате 256 Кбит (Amazon), или в формате WMA 128 Кбит (Microsoft). Чтобы решить эту проблему, алгоритмы автоматического снятия слепков используют спектрограмму аудиосигналов для получения слепков.

Я уже говорил вам, для того, чтобы получить спектрограмму цифрового звука, нужно применить БПФ. Для алгоритма снятия аудио слепка нам нужно хорошее частотное разрешение (например, 10.7 Гц), чтобы уменьшить спектральную утечку и иметь хорошее представление о самых важных нотах, играемых внутри песни. В то же время, нам необходимо максимально сократить время вычислений и, следовательно, использовать минимально возможный размер окна. В исследовательской работе Shazam они не объясняют, как они получают спектрограмму, но вот возможное решение:

На стороне сервера (Shazam) звук с частотой дискретизации 44.1 кГц (с CD, MP3 и любых других носителей и форматов) должен переводиться от стерео к моно. Мы можем сделать это, взяв среднее значение левого и правого звукового канала. Перед понижающей дискретизацией нам необходимо отфильтровать частоты выше 5 кГц, чтобы избежать сглаживания звука, и после этого частоту дискретизации можно понизить до 11.025 кГц.

На стороне клиента (телефон) частота дискретизации микрофона, записывающего звук, должна составлять 11.025 кГц.

Затем, в обоих случаях нам нужно применить функцию окна к сигналу (например, окно с 1024 выборками) и провести БПФ для каждых 1024 выборок. Таким образом, каждый БПФ анализирует 0.1 секунду музыки. Это дает нам спектрограмму:

• От 0 Гц до 5000 Гц;
• С частотным разрешением 10.7 Гц;
• 512 возможных частот;
• Единицу времени в 0.1 секунду.

На этом этапе у нас есть спектрограмма песни. Поскольку Shazam должен работать в условиях шума, сохраняются только самые громкие ноты. Но вы не можете просто брать Х самых громких частот каждые 0.1 секунды. Вот несколько причин этого:

• В первой части статьи я рассказывал о психоакустических моделях. Человеческим ушам труднее слышать низкий звук (<500 Гц), чем средний звук (500 Гц - 2000 Гц) или высокий звук (> 2000 Гц). В результате громкость низких частот многих «сырых» песен искусственно увеличивают перед выпуском. Если вы возьмете только самые громкие частоты, вы получите только низкие, и если в двух песнях будет одинаковый барабанный ритм, они могут иметь очень близкую фильтрованную спектрограмму, тогда как в первой песне, к примеру, есть еще и флейты, а во второй — гитары.
• Мы видели в главе о функциях окна, что, если у вас есть очень мощная частота, другие частоты, близкие к ней, появятся в спектре, тогда как в реальности они не существуют (это происходит из-за спектральной утечки). Нам же нужно уметь брать только настоящую частоту.

Вот простой способ сохранить только самые мощные частоты при одновременном снижении влияния других проблем:

Шаг 1: для каждого результата БПФ вы помещаете 512 бинов в 6 логарифмических диапазонов:

• Очень низкий звуковой диапазон (от 0 до 10 бина);
• Низкий звуковой диапазон (от 10 до 20 бина);
• Средне-низкий звуковой диапазон (от 20 до 40 бина);
• Средний звуковой диапазон (от 40 до 80 бина);
• Средне-высокий звуковой диапазон (от 80 до 160 бина);
• Высокий звуковой диапазон (от 160 до 511 бина).

Шаг 2: для каждой группы вы сохраняете самый сильный бин частот.

Шаг 3: вы вычисляете среднее значение этих 6 мощных бинов.

Шаг 4: вы сохраняете те бины (из этих шести), которые выше этого среднего значения.

Шаг 4 очень важен, потому что у вас может быть:

• А капелла, где поют только сопрано со средними или средне-высокими частотами.
• Джаз или рэп, где преобладают только низкие частоты.
• Другие жанры, где есть только определенные частоты.

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

Но этот алгоритм имеет ограничение: в большинстве песен некоторые части очень тихие (например, начало или конец песни). Если вы проанализируете эти части, то вы получите ложные сильные частоты, потому что среднее значение (вычисленное на шаге 3) этих частей очень низкое. Чтобы избежать этого, вместо того, чтобы брать среднее значение из шести диапазонов текущего БПФ (который представляет только 0.1 секунду песни), можно взять среднее значение для самых мощных бинов полной песни.

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

Эта картинка взята из исследовательской статьи о Shazam. В этой спектрограмме вы можете видеть, что некоторые частоты более мощные, чем другие. Если вы примените предыдущий алгоритм на этой спектрограмме, то вы получите следующую картину:

Эта картинка представляет собой фильтрованную спектрограмму, где сохраняются только самые сильные частоты предыдущего рисунка. Некоторые части песни тут вообще не имеют частот (например, их нет в промежутке от 4 до 4.5 секунд).

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

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

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

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