2010-10-11

Угадай мелодию: как работает Shazam?

Технологии способны удивлять. Помню, как мне показали распознавание музыки на айфоне. Про Shazam тогда ещё ничего не знал, впечатления были на уровне американского wow-эффекта. А на днях набрёл на материал, где доступно и понятно рассказано о таинстве фокуса. Есть подозрение, что сеанс разоблачения будет интересен и вам, уважаемые читатели.


Существует клёвый сервис под названием Shazam, который по короткому музыкальному отрывку идентифицирует песню. Есть несколько способов, чтобы пользоваться им, но удобнее всего с помощью бесплатного приложения для iPhone (и не только, Symbian и Android не оставили в стороне). Просто нажмите "tag now", держите микрофон телефона возле динамиков, и Shazam, как правило, определит песню, предоставив информацию об исполнителе, а также ссылки для покупки альбома.


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

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

Вот основные шаги:
  1. В Shazam заранее создали картотеку отпечатков музыки и сохранили её в базе данных.
  2. Пользователь „отмечает“ услышанную песню, для которой генерируется отпечаток на основе десятисекундного образца звука.
  3. Приложение отправляет отпечаток сервису Shazam, который ищет соответствия в базе данных.
  4. Если соответствие найдено, информация о песне отображается у пользователя, в противном случае возвращается ошибка.

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

Алгоритм Shazam делает отпечаток песни путём создания этого трёхмерного графика и выявляет частоты „пика интенсивности“. Для каждого из этих пиковых значений он отслеживает частоту и промежуток времени от начала трека. В примере из статьи, я предполагаю, они находят около трёх подобных точек в секунду. [Обновление: комментатор отмечает, что в его собственной реализации ему нужно больше 30 точек в секунду.] Таким образом, отпечаток десятисекундного образца может быть следующим:
Частота в герцах Время в секундах
823.44 1.054
1892.31 1.321
712.84 1.703
. . . . . .
819.71 9.943

Shazam строит свой каталог отпечатков в виде хэш–таблицы, в которой роль ключа исполняет значение частоты. Когда Shazam получает отпечаток, как показано выше, он использует первый ключ (в данном случае 823.44) для поиска подходящих песен. Их хэш–таблица может выглядеть следующим образом:
Частота в герцах Время в секундах, информация о песне
823.43 53.352, “Song A” by Artist 1
823.44 34.678, “Song B” by Artist 2
823.45 108.65, “Song C’ by Artist 3
. . . . . .
1892.31 34.945, “Song B” by Artist 2

[Некоторые дополнительные подробности: Они не просто отмечают точку в спектрограмме, они отмечают пары точек: „пик интенсивности“ плюс вторую „опорную точку“. Поэтому их ключ содержит не только одиночную частоту, это хэш частот обеих точек. Что, в свою очередь, ведёт к меньшему числу коллизий (когда хэш двух различных ключей совпадает) и ускоряет поиск по каталогу на несколько порядков, позволяя им в большей степени использовать среднее время выполнения . Есть много увлекательных вещей, связанных с хэшированием, но я не собираюсь вдаваться в подробности, так что просто изучите ссылки в этом пункте, если вы заинтригованы.]

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

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

Original by Bryan Jacobs.

12 комментариев: ответить

11.10.2010, 10:56   virens комментирует...

Занятно, спасибо Акулович.

По теме алгоритма. Это Time-Frequency Analysis, то есть это мгновенное Фурье-преобразование. БПФ берётся не по всему сигналу, а скользящим окном - то есть получается свёртка участка сигнала и функции окна. Это на пальцах и есть спектрограмма - фурье-преобразование сигнала в небольшом участке по времени. Получается такой бегущий фурье-спектр. Замечательный инструмент для анализа нестационарных сигналов.

Я эпизодически ковырял Time-Frequency Analysis на предмет того, можно ли его использовать для предсказания турбулентности при распространении света в атмосфере. И, хотя сейчас проект несколько сместился в сторону теории управления (интересна динамика компонентов системы), знакомство с Time-Frequency расширило мой кругозор весьма основательно.

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

17.10.2010, 13:33   Dr.AKULAvich комментирует...

> Занятно, спасибо Акулович.
You are welcome :-)

Специально подождал недельку, будут ли новые комменты. Предположение подтвердилось. После комментария virens'а нечего добавить :-) Миша "задавил" всех мгновенным Фурье-преобразованием.

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

22.10.2010, 12:55   virens комментирует...

@Dr.AKULAvich
Миша "задавил" всех мгновенным Фурье-преобразованием.
Никого я не давил. Просто твой пост настроил меня на волну радиостанции "Юность" и песню "Как молоды мы были" :-) Кстати, может быть мне ещё придётся Time-Frequency применять в моём проекте.

Мне приглянулась эта статья своими переплетениями с математикой, технологиями
Нету там технологий - это применение алгоритма анализа сигналов для увеселения праздношатающейся публики.

Так намного интереснее постигать научные знания.
Чтобы было веселее постигать, можно начать отсюда. Далее - matlab и tfkmvphdproject. И хотя тема моего Ph.D. другая, дела это не меняет. Если заинтересует, могу выслать тебе книжку несравненного Patrick Flandrin - он отец и бог этой области. Книжка у него просто классная.

25.10.2010, 21:03   Dr.AKULAvich комментирует...

Книжку скачал на всякий случай. Если по учёбе займусь сигналами плотнее, возможно, прибегну к твоим наработкам. Спасибо.

19.08.2011, 11:36   Анонимный комментирует...

Спасибо за понятное разъяснение работы программы!

10.06.2012, 11:00   lyops комментирует...

Спасибо! Но интересно, как раз, откуда у них отпечаток песни какого-нибудь Миши Круга :)

18.10.2012, 0:00   Анонимный комментирует...

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

17.06.2013, 22:01   karandash267 комментирует...

аноним,там много песен нет,и я немного не соглашусь со сказанным в статье "шазам работает с малоизвестными песнями"
половину моего плейлиста он не узнают,это хеви-метал 70-80х,только известные группы у которых альбомов продано больше, чем у нас в стране спичек выпущено за прошлый год

10.11.2013, 10:53   Анонимный комментирует...

ну с технологией боль-менее понятно. Но , возникает вопрос: звук из колонок передается на микрофон телефона, а не по проводам.Частоты приходящие на микрофон будут сильно зависить от положения регулятора тембра, находящийся до колонок и до усилителя тока. О каких сотых долях частот идет речь? Может через пропорции?

17.02.2014, 17:53   Дарья Кораблева комментирует...

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

04.12.2014, 18:59   Денис Чесноков комментирует...

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

10.02.2015, 3:01   Анонимный комментирует...

Shazam привязан к iTunes. Следовательно все что там есть и распознается. Был вопрос как "научить" - записывайте музыку и размещайте ее в iTunes.

Отправить комментарий