Что такое шазам перевод

shazam

1 shazam

2 Shazam!

См. также в других словарях:

Shazam — Shazam это коммерческий кроссплатформенный проект (ранее был доступен только для мобильных устройств, в данный момент существует приложение для Windows 8), осуществляющий поиск информации о песнях. Штаб квартира располагается в Лондоне.… … Википедия

Shazam — steht für: einen Musik Identifikationsdienst für Mobiltelefone und Smartphones, siehe Shazam (Dienst) eine Figur der Comicserie Captain Marvel, siehe Captain Marvel #Shazam ein Album der britischen Rockband The Move Diese … Deutsch Wikipedia

shazam — ☆ shazam [shə zam′ ] interj. Slang used to signify, or seemingly command as if by magic, a sudden and surprising change or occurrence * * * … Universalium

shazam — invented word from Captain Marvel comics, 1940 … Etymology dictionary

shazam — ☆ shazam [shə zam′ ] interj. Slang used to signify, or seemingly command as if by magic, a sudden and surprising change or occurrence … English World dictionary

Shazam! — Captain Marvel (engl.) ist eine fiktive Figur im Besitz des US amerikanischen Unterhaltungskonzerns Time Warner. Der Charakter wurde ursprünglich 1939/1940 von den Amerikanern Bill Parker und C.C. Beck als Held einer gleichnamigen Comicserie… … Deutsch Wikipedia

Shazam — Sur les autres projets Wikimedia : « Shazam », sur le Wiktionnaire (dictionnaire universel) Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Shazam peut faire référence à : Captain… … Wikipédia en Français

shazam — [ʃə zam] exclamation used to introduce something extraordinary. Origin 1940s: an invented word, used by conjurors … English new terms dictionary

shazam — sha·zam … English syllables

shazam — shəˈzam, ˈzaa(ə)m interjection Etymology: incantation used by the comic strip hero Captain Marvel, from Solomon, Hercules, Atlas, Zeus, Achilles, and Mercury, on whom he called used to indicate an instantaneous transformation or appearance … Useful english dictionary

Источник

Почему Shazam называется Shazam?

Jun 9, 2016 · 4 min read

Сегодня в это сложно поверить, но еще два десятилетия назад получить информацию с помощью мобильного телефона было несколько сложнее, чем сейчас. Не было ни App Store, чтобы за полминуты скачать любое приложение, ни Siri, которая и будильник настроит, и о звонке родителям напомнит, ни “Окей, Google”, готового ответить на любой вопрос.

В те времена для того, чтобы сделать запрос, нужн о было (кто помнит?) “отправить сообщение на короткий номер” (к примеру, 411 — это код адресного справочника в США). Для того, чтобы поразить оппонента в ходе дискуссии своими знаниями, нужно было отправить СМС с текстом GOOGL на номер 46645 (да, и Google с этого начинал).

В (далеком) 1999 году короткий номер 2580 был лишь одним из множества, но у этого кода была особая миссия: с его помощью совершались магические превращения. Выбор цифр тоже не случаен: они составляют вертикальную линию на клавиатуре телефона, — именно эти цифры и стали ключом к музыкальной империи Shazam.

Изначально Shazam базировался в Лондоне, и любой житель Великобритании, услышав незнакомую песню, мог набрать 2580 и записать 30 секунд аудио. После этого звонок автоматически обрывался и пользователь получал СМС с названием песни и указанием исполнителя, а иногда (если песня была доступна в базе Shazam) — гиперссылку для скачивания рингтона.

Для основателей стартапа — Криса Бартона, Филиппа Ингельбрехта, Эйвери Ванга и Дхиража Мукерджи — этот процесс и являлся магией в чистом виде. Несмотря на то, что изначально пользователи знали только цифры 2580, сервис назывался Shazam с самого момента основания. И если для любителей комиксов это слово ассоциировалось с капитаном Marvel, а для фанатов баскетбола — с Шакилом о’Нилом в фильме Kazaam, для основателей стартапа оно сразу означало волшебство.

Почему Shazam?

На фестивале Pioneer’s Festival-2013 в Вене Бартон рассказал: «Слово Shazam реально существует в словаре. Это восклицание, означающее «когда ты колдуешь красивые вещи». Например, если бы мне нужно было телепортироваться на фестиваль из Сан-Франциско и я мгновенно оказался здесь, то сказал бы «Shazam! Вот я и в Вене!»

“Мы решили, что смысл слова Shazam идеально подходит для описания магического процесса распознавания музыки. И (на удивление) даже сегодня, после многих лет, он остается основой всей линейки Shazam. Компания стремится показать этот магический процесс на экране смартфона каждого пользователя”.

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

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

“Мы столкнулись с множеством препятствий перед запуском Shazam, — рассказывает Крис Бартон. — И главным из них было создание масштабного (и реально работающего) алгоритма, способного идентифицировать песню даже в шумной обстановке. Затем нужно было рассказать о нем широкому кругу пользователей. Еще одно препятствие — собрать и расшифровать достаточное количество музыки, чтобы сервис заработал; создать собственный мини-Google, собственную поисковую систему и собственный кластер параллельно работающих компьютеров, десятков компьютеров, которые хранили бы на своих жестких дисках акустические отпечатки каждой песни”.

Помощь пришла от профессора электротехнического факультета Стэнфордского университета Юлиуса Смита, который был известен созданием алгоритмов для синтезаторов Yamaha. Смит очень скоро стал советником Shazam и познакомил команду со своим тогдашним аспирантом Эйвери Вангом, единственным из основателей, кто до сих пор работает в компании — он занимает должность Главного научного советника.

Когда алгоритм был создан и сервис начал работу, настал черед полноценной программы. Став в 2008 году одним из первых приложений для App Store, через пять лет Shazam занял почетное место в ТОП-10 приложений мира.

Изначально пользователи сервиса платили за звонки на короткий номер, если Shazam удавалось определить нужную песню. Сегодня же приложение творит чудеса в рамках условно бесплатной модели работы. Базовую версию можно скачать, а ее старшего брата Shazam Encore — приобрести в США, чтобы получать эксклюзивную информацию о телевизионных передачах (например, состав съемочной группы, ссылка на официальный сайт, знаменитости, используемая в шоу музыка, Twitter-каналы, детали на IMDB и многое другое). А после того, как приложение стало доступно для использования на смарт-часах, информацию о любой песне можно получить, просто коснувшись своего запястья.

Что можно сказать? Пожалуй, это действительно магия.

Источник

Shazam: что это за приложение?

Содержание статьи

История Shazam: название и развитие приложения

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

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

Но для того, чтобы приложение стало таким, как сейчас, потребовалось 14 лет работы и исследований. В этом разработчикам помогал профессор Смит, создатель алгоритмов для синтезаторов фирмы Yamaha, и его аспирант Эйвери Ванг. Под их руководством был разработан не только сложный алгоритм распознавания звуков, но и создана огромная база спектрограмм, куда входило более 15 миллиардов треков.

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

Как работает Shazam?

В основе приложения лежит алгоритм, использующий спектрограммы – изображения, которые отображают, как мощность звукового сигнала зависит от времени. Такой алгоритм активно применяется в сейсмологии, гидро- и радиолокации, обработке речи и т.д. А спектрограммы, по сути, представляют собой «отпечатки» звуков, на которых и основана работа Shazam.

Если смотреть пошагово, то распознавание музыки в приложении происходит таким образом:

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

Создавая график для песни, приложение выявляет частоту «пика интенсивности»: берет несколько пиковых значений за 10 секунд звучания образца, после чего переводит получивший «отпечаток» в хэш-таблицу, где ключами являются значения частоты. Первое значение – первый ключ – программа и использует, когда ищет в базе данных соответствия.

А если совпадений получилось несколько, программа ищет соответствие частот по времени.

Главный экран Shazam

После установки программы, пользователь, открыв ее, увидит в центре главного экрана большую кнопку. Она предназначена для запуска распознавания музыки, и через 10 секунд после ее нажатия приложение выдаст результат. Но лишь в том случае, если посторонних шумов вокруг – минимум.

Если же этих шумов много, поиск усложняется: Shazam требуется больше времени на распознавание песни. Для этого в правом верхнем углу главного экрана есть кнопка-переключатель – она выводит программу в автоматический режим. И после ее нажатия приложение в течение 4 следующих часов будет распознавать музыку, даже если пользователь из него выйдет.

Настройки

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

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

Нижняя часть экрана

Нажав на кнопку «Теги», пользователь попадет в раздел, содержащий списки всей распознанной музыки. Эти списки разграничены на две категории: «мои теги» и «авто». В первой категории находятся те песни, которые пользователь распознал самостоятельно, во второй – те, что программа нашла в автоматическом режиме.

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

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

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

Вкладка «Пульс» открывает пользователю самую популярную, «топовую», музыку в реальном времени. А «Открытие» позволяет отслеживать, где и какая песня была распознана за определенный промежуток времени. Отслеживание же происходит на карте.

Как получить Shazam?

Приложение рассчитано на устройства, работающие на платформе Android, скачать его можно через Play Market. Однако существуют разные версии шазам:

Shazam доступен и пользователям Windows Phone, хотя их значительно меньше. В этом случае программа загружается через фирменный магазин.

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

Источник

Как работает Shazam: принцип работы алгоритма по идентификации песен

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Shazam: алгоритмы распознавания музыки, сигнатуры, обработка данных

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

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

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

Как же всё это работает?
Описание базового алгоритма Shazam в 2003-м году опубликовал его создатель, Эвери Ли Чунь Вонг (Avery Li-Chung Wang). В данном материале мы в деталях разберём основы алгоритма распознавания музыки Shazam.

От аналоговых сигналов к цифровым: дискретизация

Что такое, на самом деле, звук? Может быть, это некая таинственная бестелесная субстанция, которая проникает в наши уши и позволяет слышать?

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

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

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

Аналоговый (непрерывный) и цифровой (дискретный) сигналы

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

А именно, человек может слышать звуки в диапазоне примерно от 20 Гц до 20000 Гц. В результате звук чаще всего записывают с частотой дискретизации 44100 Гц. Именно эта частота дискретизации используется в компакт-дисках. Она же чаще всего применяется для кодирования звука в группе стандартов MPEG-1 (VCD, SVCD, MP3).

Широкому использованию частоты дискретизации в 44100 Гц мы обязаны, преимущественно, корпорации Sony. В своё время звуковые дорожки, закодированные таким способом, удобно было совмещать с видео в стандартах PAL (25 кадров в секунду) и NTSC (30 кадров в секунду), работать с ними, используя существующее оборудование. Весьма важно и то, что эта частота достаточна для качественной передачи звука в диапазоне до 20000 Гц. Цифровое звуковое оборудование, использующее эту частоту дискретизации, вполне соответствовало по качеству аналоговому оборудованию тех времён, когда происходило становление стандартов цифрового звука. В итоге, выбирая частоту дискретизации звука при записи, вы, вероятнее всего, остановитесь на 44100 Гц.

Запись: захват звука

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

Временная и частотная области

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

В 19 веке Жан Батист Джозеф Фурье сделал выдающееся открытие. Заключается оно в том, что любой сигнал во временной области эквивалентен сумме некоторого количества (возможно, бесконечного) простых синусоидальных сигналов, при условии, что каждая синусоида имеет определённую частоту, амплитуду и фазу. Набор синусоид, которые формируют исходный сигнал, называют рядом Фурье.

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

Сигналы, развёрнутые во времени, и их частотные характеристики

Вот как выглядит анимированное представление Ряда Фурье для прямоугольной волны частотой 1 Гц. Здесь же показана аппроксимация исходного сигнала на основе набора синусоид. На верхнем графике сигнал показан в амплитудно-временной области, на нижнем дано его представление в амплитудно-частотном виде.

Преобразование Фурье в действии. Источник: Rene Schwarz

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

Дискретное преобразование Фурье

Итак, нужно найти способ получения частотных характеристик сигналов, развёрнутых во времени. В этом нам поможет дискретное преобразование Фурье (ДПФ, DFT, Discrete Fourier Transform). ДПФ – это математический метод анализа Фурье для дискретных сигналов. С его помощью можно преобразовать конечный набор образцов сигнала, взятых с равными промежутками времени, в список коэффициентов конечной комбинации комплексных синусоид, упорядоченных по частоте, принимая во внимание, что эти синусоиды были дисретизированы с одной и той же частотой.

Один из самых популярных численных алгоритмов для вычисления ДПФ называется быстрое преобразование Фурье (БПФ, FFT, Fast Fourier Transformation). На самом деле, БПФ представлен целым набором алгоритмов. Среди них чаще всего используются варианты алгоритма Кули-Тьюки (Cooley-Tukey). В основе этого алгоритма лежит принцип «разделяй и властвуй». В ходе вычислений используется рекурсивное разложение исходного ДПФ на мелкие части. Прямое вычисление ДПФ для некоторого набора данных n требует O(n 2 ) операций, а использование алгоритма Кули-Тьюки позволяет решить ту же задачу за O(n log n) операций.

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

Вот пример сигнала до и после БПФ-анализа.

Сигнал до и после БПФ-анализа

Распознавание музыки: сигнатуры песен

Один из неприятных побочных эффектов БПФ заключается в том, что проведя анализ, мы теряем информацию о времени. (Хотя, теоретически, подобного можно избежать, но на практике для этого понадобится огромная вычислительная мощность.) Например, для трёхминутной песни мы можем видеть звуковые частоты и их амплитуды, но вот где именно в произведении эти частоты встречаются, не знаем. А это – важнейшая характеристика, которая делает музыкальное произведение тем, что оно есть! Нам нужно как-то узнать точные значения времени, когда появляется каждая из частот.

Именно поэтому мы будем пользоваться чем-то вроде скользящего окна, или блока данных, и подвергать трансформации лишь ту часть сигнала, которая в это «окно» попадает. Размер каждого блока можно определить с использованием различных подходов. Например, если мы записываем двухканальный звук с размером образца равным 16 бит и с частотой дискретизации 44100 Гц, одна секунда такого звука займёт 176 Кб памяти (44100 образцов * 2 байта * 2 канала). Если мы установим размер скользящего окна, равный 4 Кб, то каждую секунду нам нужно будет проанализировать 44 блока данных. Это – довольно высокое разрешение для детального анализа композиции.

Вернёмся к программированию.

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

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

Однако, в одной песне диапазон «сильных» частот может варьироваться, скажем, от ноты «до» контроктавы (32,70 Гц), до ноты «до» пятой октавы (4186,01 Гц). Это – огромный интервал. Поэтому, вместо того, чтобы за сразу проанализировать весь частотный диапазон, мы можем выбрать несколько более мелких интервалов. Выбор можно сделать, основываясь на частотах, которые обычно присущи важным музыкальным компонентам, и проанализировать их по отдельности. Например, можно воспользоваться интервалами, которые вот этот программист использовал для своей реализации алгоритма Shazam. А именно, это 30 Гц – 40 Гц, 40 Гц – 80 Гц и 80 Гц – 120 Гц для низких звуков (сюда попадает, например, бас-гитара). Для средних и более высоких звуков применяются частоты 120 Гц – 180 Гц и 180 Гц – 300 Гц (сюда входит вокал и большинство других инструментов).

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

Заметьте, что мы должны учитывать то, что запись выполнена не в идеальных условиях (то есть, не в звукоизолированном помещении). Как результат, надо предусмотреть наличие в записи посторонних шумов и возможное искажение записываемого звука, зависящее от характеристик помещения. К этому вопросу стоит подойти очень серьёзно, в реальных системах стоит реализовать настройку анализа возможных искажений и посторонних звуков (fuzz factor) в зависимости от условий, в которых проводится запись.

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

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

Поиск совпадений

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

Но не всё так просто. Дело в том, что у многих фрагментов различных произведений хэш-тэги совпадают. Например, может оказаться так, что какой-то фрагмент песни A звучит точно так же, как некий участок песни E. И тут нет ничего удивительного. Музыканты и композиторы постоянно «заимствуют» друг у друга удачные музыкальные фигуры.

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

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

Однако если найдено несколько совпадений, можно проанализировать относительный тайминг совпадений, и, таким образом, повысить достоверность поиска.

Например, если взглянуть в вышеприведенную таблицу, можно обнаружить, что хэш-тег 30 51 99 121 195 относится и к песне A, и к песне E. Если секундой спустя мы будем проверять хэш-тег 34 57 95 111 200, то обнаружим ещё одно совпадение с песней A, к тому же, в подобном случаем мы будем знать о том, что совпадают и хэш-теги и их распределение во времени.

Пусть i1 и i2 – это отметки времени в записанной песне, j1 и j2 – отметки времени в песне из базы данных. Мы можем говорить о том, что имеются два совпадения, с учётом совпадения разницы во времени, если выполняется следующее условие:

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

И, наконец, маловероятно, что каждый обработанный фрагмент записанной в «диких» условиях песни совпадёт с аналогичным фрагментом из базы данных, построенной на основе студийных записей. Запись, на основе которой мы хотим найти название произведения, будет включать в себя много шума, что приведёт к неким расхождениям при сравнении. Поэтому, вместо того, чтобы пытаться исключить из списка совпадений всё, кроме единственной верной композиции, в конце процедуры сопоставления с базой данных мы отсортируем записи, в которых нашлись совпадения. Сортировать будем в убывающем порядке. Чем больше совпадений – тем вероятнее то, что мы нашли нужную композицию. Соответственно, она окажется на вершине списка.

Обзор процедуры распознавания музыки

Вот обзор всей процедуры распознавания музыкальных композиций. Пройдёмся по нему от начала до конца.

Обзор процедуры распознавания музыки

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

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

Shazam!

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

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

Возможно, хорошим экспериментом станет заполнение базы данных классикой – сочинениями Баха, Бетховена, Вивальди, Вагнера, Шопена и Моцарта и поиск схожего в их работах. Так вполне можно выяснить, что даже Боб Дилан, Элвис Пресли и Роберт Джонсон не прочь были что-нибудь позаимствовать у других!

Но можем ли мы их за это винить? Уверен, что нет. Ведь музыка – это всего лишь звуковая волна, которую человек слышит, запоминает и повторяет у себя в голове. Там она развивается, меняется – до тех пор, пока её не запишут в студии и не выпустят на волю, где она вполне может вдохновить очередного гения от музыки.

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

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

Источник