Как работает Shazam? Простое объяснение алгоритма распознавания аудио

Способность наших телефонов распознавать любую песню, которая звучит рядом — это настоящая технологическая магия. В этой статье я расскажу вам, как одно из самых популярных приложений, Shazam, справляется с этой задачей. Основатели Shazam в 2003 году опубликовали документ, в котором они описали принцип его работы. Я, со своей стороны, озадачился реализацией этого процесса на Python в проекте под названием abracadabra.

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

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

Оглавление

• Почему распознавать песни сложно?
• Схема работы Shazam
• Построение спектрограммы
• Создание отпечатка
• Сопоставление
• Заключение
  

Shazam — это приложение, которое распознает песни, играющие вокруг вас. Когда играет музыка, вы открываете приложение, Shazam делает запись звука длиной в несколько секунд и использует её для поиска в собственной базе данных. Как только он определяет играющую песню, результат отображается на экране.

Прежде чем стать приложением, Shazam был телефонным номером. Чтобы определить песню, нужно было позвонить по этому номеру и поднести микрофон телефона к источнику музыки. Через 30 секунд Shazam завершал звонок и присылал вам СМС с информацией о песне, которую вы слушали. Если у вас был мобильный телефон в 2002 году, вы понимаете, что качество телефонной связи в те времена делало эту задачу весьма непростой!

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

График выше изображает, как выглядит песня "Like a Stone" Криса Корнелла, когда она хранится в компьютере. Теперь рассмотрим небольшой фрагмент песни:

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

Это займёт какое-то время, но сработает. Теперь представьте, что вы не знаете, из какой песни взят этот фрагмент, а в вашей базе данных 10 миллионов песен. Поиск соответствия таким способом потребует намного больше времени!

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

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

Если Shazam не использует метод передвигания, описанный выше, что же он делает? Взгляните на следующую схему:

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

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

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

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

В следующих разделах вы узнаете больше о каждом из этих этапов.

Первый шаг для обоих потоков — получить спектрограмму аудио, которое сохраняется или распознаётся. Чтобы разобраться в спектрограммах, сначала стоит познакомиться с преобразованиями Фурье.

Преобразование Фурье

Преобразование Фурье позволяет нам понять, какие частоты присутствуют в аудиофрагменте. Например, если взять синусоидальную волну частотой 20 Гц и применить к ней преобразование Фурье, мы получим следующую картину:

На изображении выше вы видите большой пик на уровне 20 Гц, а на других частотах ничего. Синусоидальные вольны поэтому часто называют чистыми тонами — они содержат только одну частоту.

Результат преобразования Фурье называется частотным спектром. Мы говорим, что, когда вы применяете к сигналу преобразование Фурье, вы переносите его из временного представления в частотное. Это красивый способ сказать, какой параметр расположен на графике по горизонтали, т.е. по оси X: время или частота.

Ось Y частотного спектра обозначает амлитуду (т.е. относительную громкость) каждого частотного компонента. Если амплитуда какого-то частотного компонента больше, то он будет слышнее в песне.

Если добавить к синусоидальной волне частотой 20 Гц синусоидальную волну частотой 50 Гц с вдвое меньшей амплитудой, полученный частотный спектр покажет пик на уровне 20 Гц и меньший пик на уровне 50 Гц:

Как видите, сложение звуковых волн вместе объединяет присутствующие в них частоты. Любой аудиосигнал можно восстановить из такого отображения волн. Более подробно об этом можно узнать, посмотрев видео 3Blue1Brown о преобразовании Фурье.

Ценность частотного представления заключается в том, что оно позволяет нам видеть то, что может быть неочевидным во временном представлении. Например, если взять сигнал с двумя частотами, который мы рассмотрели выше, и добавить к нему шум, во временном представлении он станет выглядеть совсем иначе. Тем не менее, в частотном представлении два пика будут по-прежнему чётко видны:

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

До сих пор наши примеры содержали всего одну или две частоты, но что произойдет, если вы примените преобразование Фурье к более сложному сигналу? Давайте посмотрим на наш фрагмент аудио из "Like a Stone":

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

Спектрограммы

Если применить преобразование Фурье к целой песне, мы увидим амплитуды присутствующих в ней частот на всём её протяжении. Однако, на разных участках песни набор частот может различаться — ведь вступление песни часто непохоже на середину или финал, не правда ли? Чтобы лучше представить изменение частот по времени, лучше сначала разбить песню на небольшие секции, а потом выполнить преобразование Фурье. Это и называется созданием спектрограммы.

Вот упрощенная анимация того, как получается спектрограмма:

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

Давайте взглянем на спектрограмму "Like a Stone":

Спектрограмма может показаться двухмерным графиком, но на самом деле она содержит три измерения:

• Время (ось X)
• Частота (ось Y)
• Амплитуда (ось Z/цвет)

Ось Z представлена цветом на приведённой выше спектрограмме. Светло-зелёный означает большую амплитуду для определенного частотного компонента, а тёмно-синий — меньшую.

Рассматривая спектрограмму выше, можно заметить, что самые светлые точки (громкие частоты) почти исключительно находятся ниже 5000 Гц. Это довольно типично для музыки: например, у большинства фортепиано диапазон частот лежит в интервале от 27 Гц до 4186 Гц.

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

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

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

В следующем разделе вы узнаете еще немного о том, почему для создания отпечатков песен мы используем именно пики на спектрограмме.

Почему мы используем пики спектрограммы?

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

В музыке это будут самые громкие ноты. Например, во время гитарного соло ноты, которые играет гитара, могут стать пиками спектрограммы, так как они, вероятнее всего, будут самыми громкими нотами на своём отрезке песни.

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

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

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

Однако, прежде чем мы сможем использовать частотные пики в нашем отпечатке, мы должны их найти. В следующем разделе вы узнаете, как.

Поиск пиков

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

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

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

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

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

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

• Применить фильтр максимумов для выделения пиков на спектрограмме.
• Найти выделенные пики, сравнив их с исходной спектрограммой.
• (Опционально) Отбросить некоторые пики.

Давайте последовательно рассмотрим эти шаги, но сначала разберёмся, как работает фильтр максимумов.

Шаг 1: Фильтр максимумов

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

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

Применение фильтра максимумов к спектрограмме песни Like a Stone даёт следующий результат:

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

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

Шаг 2: Восстановление исходных пиков

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

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

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

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

Если отметить все найденные таким образом пики на графике, убрав всё остальное, мы получим визуализацию, называемую картой созвездий. Вот карта созвездий для Like a Stone:

Эти графики называются картами созвездий, потому что они напоминают изображение ночного неба. Кто сказал, что информатика не может быть романтичной?

Шаг 3: Отбрасывание пиков (опционально)

После того как мы получили карту созвездий, следующим шагом может быть отбрасывание некоторых из них. Размер нашего отпечатка зависит от количества пиков, которые мы используем в нём. Когда в базе данных миллионы песен, размер отпечатков имеет значение.

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

Есть пара вариантов для уменьшения количества пиков в нашем отпечатке:

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

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

Хеширование

Чтобы понять, зачем нужен этап хеширования, давайте представим, что отпечаток — это просто коллекция пиков спектрограммы. Каждая частота в этом случае кодировалась бы определённым числом бит, например, 10. Десятью битами мы можем закодировать 2^10=1024 уникальных значения частотных компонентов (т.е. наших пиков). Учитывая, что в одной песне этих точек могут быть тысячи, мы неизбежно получим большое количество повторов.

Уникальность отпечатка — критически важное качество, поскольку это позволяет существенно ускорить поиск и правильно идентифицировать большее количество песен. Shazam решает эту проблему, создавая хэши из пар пиков:

Диаграмма выше отображает приближенный фрагмент спектрограммы. Каждый кружочек здесь — это пик, а пунктирный прямоугольник — хеш. На диаграмме видно, что хеш состоит из двух пиков. В хеше записываются частоты обоих пиков (fA и fB) и временной интервал между ними (𝚫T).

Создание хешей на основе пар пиков позволяет достичь большей уникальности. Давайте посчитаем: если каждая точка кодируется 10 битами, то 3 точки = 30 бит информации. 2^30 = 1073741824 возможных значения, что значительно больше, чем 1024, которые даёт нам одна точка.

Алгоритм Shazam для создания пар включает в себя следующие шаги:

• Выбор якорной точки: выбор пика на спектрограмме в качестве точки, с которой будут создаваться пары.
• Расчёт целевой зоны: определение зоны в спектрограмме для создания пар с якорной точкой.
• Создание пар: для каждой точки в целевой зоне создание пары с якорной точкой.

Этот алгоритм проиллюстрирован в следующей анимации:

Оригинальная статья Shazam не описывает принцип выбора целевой зоны, но иллюстрации показывают, что она расположена с небольшим сдвигом по времени от якорной точки и центрирована на её частоте.

После создания пары, в базу данных в виде хеша записывается следующая информация:

Первые три столбца (fA, fB и 𝚫T) формируют хеш. "Доп. информация" используется для того, чтобы определить положение хеша по времени в конкретной песне. Эта информация пригодится при распознавании.

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

Как Shazam определяет, какой песне из огромной базы данных отпечатков соответствует конкретный образец аудио? Здесь на сцену выходит часть системы, отвечающая за сопоставление. Вспомним диаграмму системы, представленную в начале статьи:

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

Алгоритм сопоставления включает в себя следующие шаги:

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

Давайте рассмотрим каждый из этих шагов по очереди.

Шаг 1: Извлечение совпадающих хешей

Первый шаг — найти в базе данных каждый хеш, совпадающий с каким-либо хешем из отпечатка, который мы только что создали. Несмотря на то, что для создания хеша использованы три элемента (fA, fB, 𝚫T), хеш-функция возвращает одно значение. Это позволяет искать только одно значение на каждый хеш вместо трёх.

Шаг 2: Группировка хешей по песне

Напомним формат хеша в базе данных:

Дополнительная информацияЧастота точки A (fA)Частота точки B (fB)Временной интервал (𝚫T)Время точки AID песни

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

Шаг 3: Сопоставление последовательности хешей

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

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

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

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

Более того, иногда хеши могут совпасть с неправильной песней! Чтобы решить эту проблему, применяется проверка на последовательность хешей.

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

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

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

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

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

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

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

Поздравляю всех, кто дочитал до конца! На протяжении этой статьи я постарался кратко рассказать, как Shazam извлекает отпечатки из аудио и как он сравнивает их с теми, что уже хранятся в его БД.

Подытожим. Так выглядит запись песни в БД Shazam:

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

А так выглядит распознавание аудиофрагмента:

• Создание отпечатка аудиофрагмента
• Поиск хешей, совпадающих с отпечатками в БД
• расчёт разницы во времени звучания для каждого совпавшего хеша по каждой песне
  
• Создание гистограммы на основе полученных значений
• Ранжирование песен на основе максимального значения на гистограмме
• Отображение песни с максимальным рейтингом в качестве результата поиска

Подписывайтесь на мой телеграм канал, чтобы не упускать актуальные новости с Hacker News в русском переводе!

Переведено проектом Russian Hacker News. Оригинал статьи

#shazam #технологии #аудио #python