Наверно многие знают о существовании такого замечательного сервиса под названием Shazam, который по короткому музыкальному отрывку идентифицирует песню. Есть несколько способов, чтобы пользоваться им, но удобнее всего с помощью бесплатного приложения для iPhone, Android, Symbian и других. Просто нажмите «Tag now», держите микрофон телефона возле динамиков, и Shazam, как правило, определит песню, предоставив информацию об исполнителе, а также ссылки для покупки альбома или прослушивания на YouTube.
Что примечательно в сервисе, он работает с малоизвестными песнями и определяет их даже в присутствии посторонних шумов. У меня получилось распознать трек, сидя в переполненном кафе и пиццерии.
Мне стало любопытно, как же это работает, и, к счастью, нашлась статья, написанная одним из разработчиков с объяснениями процесса. Конечно, там исключены некоторые детали, но основной идеей является то, что вы и предполагали: алгоритм сравнивает «отпечатки» музыки, основанные на спектрограммах (для удобства ко многим терминам была добавлена ссылка на статью в Wikipedia).
Вот основные шаги:
- В Shazam заранее создали картотеку отпечатков музыки и сохранили её в базе данных.
- Пользователь «отмечает» услышанную песню, для которой генерируется отпечаток на основе десятисекундного образца звука.
- Приложение отправляет отпечаток сервису Shazam, который ищет соответствия в базе данных.
- Если соответствие найдено, информация о песне отображается у пользователя, в противном случае возвращается ошибка.
Вот как работает снятие отпечатков:
Вы можете представить музыкальное произведение как частотно-временной график, называемый спектрограммой. На одной оси откладывают время, на другой — частоту, на третьей — интенсивность. Каждая точка на графике представляет интенсивность конкретной частоты в данный момент времени. Располагая временную шкалу на оси х, а частотную — на оси у, получаем горизонтальную линию, которая представляет собой непрерывный чистый тон и вертикальную линию, иллюстрирующую мгновенный всплеск белого шума. Вот пример того, как может выглядеть песня:
Спектрограмма отрывка песни с пиками интенсивности, отмеченными красным цветом.
Алгоритм Shazam делает отпечаток песни путём создания этого трёхмерного графика и выявляет частоты „пика интенсивности“. Для каждого из этих пиковых значений он отслеживает частоту и промежуток времени от начала трека. В примере из статьи, я предполагаю, они находят около трёх подобных точек в секунду. Таким образом, отпечаток десятисекундного образца может быть следующим:
Shazam строит свой каталог отпечатков в виде хэш–таблицы, в которой роль ключа исполняет значение частоты. Когда Shazam получает отпечаток, как показано выше, он использует первый ключ (в данном случае 823.44) для поиска подходящих песен. Их хэш–таблица может выглядеть следующим образом:
Некоторые дополнительные подробности: Они не просто отмечают точку в спектрограмме, они отмечают пары точек: «пик интенсивности» плюс вторую «опорную точку». Поэтому их ключ содержит не только одиночную частоту, это хэш частот обеих точек. Что, в свою очередь, ведёт к меньшему числу коллизий (когда хэш двух различных ключей совпадает) и ускоряет поиск по каталогу на несколько порядков, позволяя им в большей степени использовать среднее время выполнения . Есть много увлекательных вещей, связанных с хэшированием, но я не собираюсь вдаваться в подробности, так что просто изучите ссылки в этом пункте, если вы заинтригованы.
Верхний график: Песня и отрывок имеют много совпадений частот, но они не совпадают во времени, так что нет соответствия. Нижний график: совпадающие частоты наблюдают в одно время, значит песни идентичны.
Если у песни выявили несколько совпадений (на основе примеров в статье, я думаю, необходимо около одного совпадения в секунду), тогда проверяют соответствие частот по времени. У них есть продуманный способ. Создаётся двумерный участок частот, на которых наблюдались совпадения. На одной оси откладывают время появления частоты в треке, на другой — аналогичное время для образца. Если между множеством точек наблюдается корреляция, точки образуют диагональ. Они используют другой метод обработки сигнала, чтобы найти эту линию, и если она существует, с определённой вероятностью песни соотносятся.
Оригинал: Брайан Джейкобс
