Как найти песню по напеву на яндекс

Помогла ли Вам статья?

Как Яндекс распознаёт музыку с микрофона

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

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

Технически задача формулируется следующим образом: на сервер поступает десятисекундный фрагмент записанного на смартфон аудиосигнала (мы его называем запросом), после чего среди известных нам треков необходимо найти ровно тот один, из которого фрагмент был записан. Если фрагмент не содержится ни в одном известном треке, равно как и если он вообще не является музыкальной записью, нужно ответить «ничего не найдено». Отвечать наиболее похожими по звучанию треками в случае отсутствия точного совпадения не требуется.

База треков

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

Малоперспективные подходы

Как лучше сравнивать фрагмент с треками? Сразу отбросим заведомо неподходящие варианты.

1. Побитовое сравнение. Даже если принимать сигнал напрямую с оптического выхода цифрового проигрывателя, неточности возникнут в результате перекодирования. А на протяжении передачи сигнала есть много других источников искажений: громкоговоритель источника звука, акустика помещения, неравномерная АЧХ микрофона, даже оцифровка с микрофона. Всё это делает неприменимым даже нечёткое побитовое сравнение.
2. Водяные знаки. Если бы Яндекс сам выпускал музыку или участвовал в производственном цикле выпуска всех записей, проигрываемых на радио, в кафе и на дискотеках — можно было бы встроить в треки звуковой аналог «водяных знаков». Эти метки незаметны человеческому уху, но легко распознаются алгоритмами.
3. Нестрогое сравнение спектрограмм. Нам нужен способ нестрогого сравнения. Посмотрим на спектрограммы оригинального трека и записанного фрагмента. Их вполне можно рассматривать как изображения, и искать среди изображений всех треков самую похожую (например, сравнивая как векторы с помощью одной из известных метрик, таких как L²):
   
   Но в применении этого способа «в лоб» есть две сложности:
   а) сравнение с 6 млн картинок — очевидно, дорогая операция. Даже огрубление полной спектрограммы, которое в целом сохраняет свойства сигнала, даёт несколько мегабайт несжатых данных.
   б) оказывается что одни различия более показательны, чем другие.

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

Каким признакам не страшны искажения?

Основные проблемы возникают из-за шума и искажений на пути от источника сигнала до оцифровки с микрофона. Можно для разных треков сопоставлять оригинал с фрагментом, записанным в разных искусственно зашумлённых условиях — и по множеству примеров найти, какие характеристики лучше всего сохраняются. Оказывается, хорошо работают пики спектрограммы, выделенные тем или иным способом — например как точки локального максимума амплитуды. Высота пиков не подходит (АЧХ микрофона их меняет), а вот их местоположение на сетке «частота-время» мало меняется при зашумлении. Это наблюдение, в том или ином виде, используется во многих известных решениях — например, в Echoprint. В среднем на один трек получается порядка 300 тыс. пиков — такой объём данных гораздо более реально сопоставлять с миллионами треков в базе, чем полную спектрограмму запроса.

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

Нам нужно найти во всей базе отрезок трека, наиболее похожий на наш запрос. То есть:

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

Для этого строим гистограмму: для каждой частоты пика, которая присутствует и в запросе, и в треке, откладываем +1 по оси Y в том смещении, где нашлось совпадение:

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

Борьба за точность поиска

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

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

Разнообразие по частотам: чтобы отдавать предпочтение наиболее разнообразным частотам, мы поднимаем лезвие не только в само́й частоте очередного пика, но и (в меньшей степени) в соседних с ней частотах.

Отбор по частотам: затем, внутри одного временно́го интервала, среди всех частот, выбираем самые контрастные пики, т.е. самые большие локальные максимумы среди срезанных «верхушек».

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

Ускорение поиска

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

Повышение уникальности ключей: Можно было бы построить индекc
    Частота пика → (Трек, Местоположение в нём).
Увы, такой «словарь» возможных частот слишком беден (256 «слов» — интервалов, на которые мы разбиваем весь частотный диапазон). Большинство запросов содержит такой набор «слов», который находится в большинстве из наших 6 млн документов. Нужно найти более отличительные (discriminative) ключи — которые с большой вероятностью встречаются в релевантных документах, и с малой в нерелевантных.

Для этого хорошо подходят пары близко расположенных пиков. Каждая пара встречается гораздо реже.
У этого выигрыша есть своя цена — меньшая вероятность воспроизведения в искажённом сигнале. Если для отдельных пиков она в среднем P, то для пар — P² (т.е. заведомо меньше). Чтобы скомпенсировать это, мы включаем каждый пик сразу в несколько пар. Это немного увеличивает размер индекса, но радикально сокращает число напрасно рассмотренных документов — почти на 3 порядка:

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

Двухэтапный поиск: для дополнительного уменьшения объёма расчётов мы разбили поиск на два этапа:

1. Делаем предварительный отбор (pruning) треков по очень разреженному набору наиболее контрастных пиков. Параметры отбора подбираются так, чтобы максимально сузить круг документов, но сохранить в их числе наиболее релевантный результат
2. Выбирается гарантированно наилучший ответ — для отобранных треков считается точная релевантность по более полной выборке пиков, уже по индексу с другой структурой:
       Трек → (Пара частот, Местоположение в треке).

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

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

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

Ничего не найдено?

Случается, что для запрошенного фрагмента либо нет подходящего трека в нашей базе, либо фрагмент вообще не является записью какого-либо трека. Как принять решение, когда лучше ответить «ничего не найдено», чем показать «наименее неподходящий» трек? Отсекать по какому-нибудь порогу релевантности не удаётся — для разных фрагментов порог различается многократно, и единого значения на все случаи просто не существует. А вот если отсортировать отобранные документы по релевантности, форма кривой её значений даёт хороший критерий. Если мы знаем релевантный ответ, на кривой отчётливо видно резкое падение (перепад) релевантности, и напротив — пологая кривая подсказывает, что подходящих треков не найдено.

Что дальше

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

Кроме того, мы планируем инкрементальное распознавание, т.е. давать ответ уже по первым секундам фрагмента.

Другие задачи аудиопоиска по музыке

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

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

Что почитать

• Avery Wang: «An Industrial-Strength Audio Search Algorithm», Proc. 2003 ISMIR International Symposium on Music Information Retrieval, Baltimore, MD, Oct. 2003. Эта статья впервые (насколько нам известно) предлагает использовать пики спектрограммы и пары пиков как признаки, устойчивые к типичным искажениям сигнала.
• D. Ellis (2009): «Robust Landmark-Based Audio Fingerprinting». В этой работе даётся конкрентый пример реализации отбора пиков и их пар с помощью «decaying threshold» (в нашем вольном переводе — «опускающегося лезвия»).
• Jaap Haitsma, Ton Kalker (2002): «A Highly Robust Audio Fingerprinting System». В данной статье предложено кодировать последовательные блоки аудио 32 битами, каждый бит описывает изменение энергии в своем диапазоне частот. Описанный подход легко обобщается на случай произвольного кодирования последовательности блоков аудиосигнала.
• Nick Palmer: «Review of audio fingerprinting algorithms and looking into a multi-faceted approach to fingerprint generation». Основной интерес в данной работе представляет обзор существующих подходов к решению описанной задачи. Также описаны этапы возможной реализации.
• Shumeet Baluja, Michele Covell: «Audio Fingerprinting: Combining Computer Vision & Data Stream Processing». Статья, написанная коллегами из Google, описывает подход на основе вейвлетов с использованием методов компьютерного зрения.
• Arunan Ramalingam, Sridhar Krishnan: «Gaussian Mixture Modeling Using Short Time Fourier Transform Features For Audio Fingerprinting» (2005). В данной статье предлагается описывать фрагмент аудио с помощью модели Гауссовых смесей поверх различных признаков, таких как энтропия Шеннона, энтропия Реньи, спектрольные центроиды, мэлкепстральные коэффициенты и другие. Приводятся сравнительные значения качества распознавания.
• Dalibor Mitrovic, Matthias Zeppelzauer, Christian Breiteneder: «Features for Content-Based Audio Retrieval». Обзорная работа про аудио-признаки: как их выбирать, какими свойствами они должны обладать и какие существуют.
• Natalia Miranda, Fabiana Piccoli: «Using GPU to Speed Up the Process of Audio Identification». В статье предлагается использование GPU для ускорения вычисления сигнатур.
• Shuhei Hamawaki, Shintaro Funasawa, Jiro Katto, Hiromi Ishizaki, Keiichiro Hoashi, Yasuhiro Takishima: «Feature Analysis and Normalization Approach for Robust Content-Based Music Retrieval to Encoded Audio with Different Bit Rates.» MMM 2009: 298-309. В статье акцентируется внимание на повышении робастности представления аудиосигнала на основе мел-кепстральных коэффициентов (MFCC). Для этого используется метод нормализации кепстра (CMN).

Все знают, что такое Shazam. Это сервис, который позволяет определить песню по её словам. Достаточно запустить Шазам на одном смартфона и поднести его достаточно близко к другому, на котором воспроизводится трек, как он без проблем поймёт, что это за композиция и кто её исполняет. Это очень удобно. Другое дело, что Шазам распознаёт только песни в оригинале. Он разбирает полученные звуки на слова и ноты, синтезирует их и выдаёт результат. А что делать, если оригинала песни под рукой нет, а максимум, что вы можете — это напеть мотив искомой композиции? Выход есть.

Защита смартфонов: какая лучше в чём разница между ними

Какие варианты найти трек у вас есть, если вы знаете только слова или мотив? В принципе, можно попробовать поискать в Гугле строки песни. Зачастую ему бывает довольно легко обнаружить нужную композицию. Но ведь не во всех песнях так просто различить слова. Поэтому всё, чем многие располагают, — это всего-навсего мотив. Но даже по нему можно найти нужный вам трек.

Как найти песню по звуку в гугле

Это можно сделать с помощью Google Ассистента. С некоторых пор он поддерживает такую возможность. Она состоит в том, что вы просто вызываете голосового помощника и напеваете ему песню. Можно со словами, а можно без. Вот, попробуйте сами:

• Запустите Google Ассистента у себя на смартфоне;
• Дайте Ассистенту команду по-русски: «Определи песню»;

• Когда на экране появится надпись «Распознавание», начните напевать песню или просто мотив, если не знаете слов;
• Напевайте до тех пор, пока Ассистент не выдаст результаты по вашему поиску.

Я пробовал искать песни таким образом несколько раз, каждый раз усложняя Ассистенту задачу. Сначала я спел песню «Конь» вполголоса, с наполовину закрытым ртом. Так что в целом определить, что за композицию я исполнял, было возможно, но только если совершенно точно знать её. Ассистент без труда решил эту задачу.

Как обойти Гугл-аккаунт? Вот самые лучшие способы

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

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

Поиск песен по ритму

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

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

Как разблокировать телефон, если забыл пароль. Всё, что нужно знать

Сейчас же могу сказать, что Google Ассистент определяет правильно 8 песен из 10, напетых подобным образом. Причём на моём опыте помощник ещё ни разу не сдался. Но пару раз допустил оплошность и выдал мне совершенно не те композиции, что я искал, хотя, на мой взгляд, уж их-то определить не составляло никакого труда.

В целом мне такая методика поиска песен нравится намного больше, чем то, что предлагает Shazam. По сути, сервис Apple не напрягается, определяя композиции в чистом виде. А, если предоставить ему ремикс, то может и сбиться. У Google Ассистента всё по-другому. Он реально распознаёт даже самый немелодичный напев, позволяя вам быстро и беспроблемно получить название песни здесь и сейчас.