Компания
510,13
рейтинг
28 мая 2013 в 12:54

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

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

image

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

О достигнутом уровне качества
Базовым качеством мы называем процент валидных запросов, на которые дали релевантный ответ — сейчас около 80%. Релевантный ответ — это трек, в котором содержится запрос пользователя. Валидными считаем лишь те запросы из приложения Яндекс.Музыки, которые действительно содержат музыкальную запись, а не только шум или тишину. При запросе неизвестного нам произведения считаем ответ заведомо нерелевантным.

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

База треков


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

Раз мы — зеркало интернета, мы собрали ID3-теги и дескрипторы каждого популярного в Сети трека, чтобы опознавать и те произведения, которых нет в базе Яндекс.Музыки. Хранить достаточно только эти метаданные — по ним мы показываем музыкальные видеоклипы, когда нашлись только записи из интернета.

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


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


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

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


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

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

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

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

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


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

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

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

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

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


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

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

Для этого хорошо подходят пары близко расположенных пиков. Каждая пара встречается гораздо реже.
У этого выигрыша есть своя цена — меньшая вероятность воспроизведения в искажённом сигнале. Если для отдельных пиков она в среднем P, то для пар — P2 (т.е. заведомо меньше). Чтобы скомпенсировать это, мы включаем каждый пик сразу в несколько пар. Это немного увеличивает размер индекса, но радикально сокращает число напрасно рассмотренных документов — почти на 3 порядка:
Оценка выигрыша
Например, если включать каждый пик в 8 пар и «упаковать» каждую пару в 20 бит (тогда число уникальных значений пар возрастает до ≈1 млн), то:
  • число ключей в запросе растёт в 8 раз
  • число документов на ключ уменьшается в ≈4000 раз: ≈1 млн/256
  • итого, число напрасно рассмотренных документов уменьшается в ≈500 раз: ≈4000/8


image

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

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

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

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

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


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

Что дальше


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

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

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


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

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

Что почитать


  • 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).
Автор: @yurkennis
Яндекс
рейтинг 510,13

Комментарии (113)

  • +59
    Ребят, уважаю вас за такие статьи. Спасибо!
    • +4
      Спасибо вам за отзыв, очень приятно!
    • 0
      Поддерживаю на все 100%! Совсем недавно задумался, как оно там внутри таких сервисов работает всё (предполагал, что перебирает по частотам каким-то образом, но вот как именно – оставалось загадкой :) ), а тут такая статья прекрасная! Спасибо огромное!
    • +1
      Гениальная статья. Снимаю шляпу!
  • +29
    Я не могу не оставить это здесь www.yaplakal.com/pics/pics_original/2/6/5/38562.jpg
    • +5
      Спасибо — отлично подходит к нашему разделу «Малоперспективные подходы» :-)
  • 0
    Правильно я понял, что можно отрывок не только с микрофона предлагать, но и из своего файла?
    • +1
      Нет, такой возможности не предусматривали — на первый взгляд кажется, что это совсем не массовая потребность.
      • +4
        Не согласен. Например, друг перекинул рингтон, но мне интересно, откуда он. Или была запись ещё до установки вашей программы. Или человек хочет сделать данную конкретную запись, и потом только узнать, что же он записал.
      • +3
        В дополнение к предыдущему комментатору: или нет доступа в интернет на данный момент, поэтому записал на диктофон смартфона.
        • +1
          Насчёт Я.Музыки не знаю, а конкуренты позволяют отложить распознавание до того времени, когда интернет появится. Именно поэтому не стал включать этот пункт.
          • 0
            Мы будем работать над тем, чтобы функция распознавания становилась удобнее. Это один из вариантов, который будем рассматривать.
        • 0
          в тех же шазамах, трейайди, саундхаундах клиент может записать в оффлайне и при появлении интернета надо нажать что то типа «отправить сохраненный трек»
          • 0
            Как я понял они не пишут сам трек, а всё же производят сразу предварительную обработку, в принципе так же, как это делается когда надо распознать сразу.
          • 0
            А больше одного трека можно?
            • 0
              Да.
    • +3
      Воспроизвести запись через другое устройство и поднести телефон с Яндекс.Музыкой?
  • +1
    Интересно насколько востребована эта фича? кто-нибудь оценивал?
    • +12
      Количество инсталляций Shazam, TrackId, SoundHound и иже.
    • +1
      Пока мы не очень её продвигали, ей попробовали воспользоваться порядка 20% пользователей мобильного приложения Яндекс.Музыка.
      Со временем планируем сделать её более заметной — это тоже должно повлиять на популярность этой функции.
  • +1
    Большое спасибо за описание метода, пытался решать подобную проблему через сравнение спектограмм, успеха не достиг.
    Отдельное спасибо за список литратуры!
    • +1
      Мы рады что вам понравилось :-)
      • 0
        Небольшая просьба немного не по теме — было бы здорово, если бы в Яндекс.Музыку вернулись те треки, соглашение на использование которых у вас истекло. У меня уже год половина плейлиста недоступна :(

        Конечно, можно скачать их с торрентиков и залить в яндекс.диск, но это как-то не совсем хорошо :)

        Желаю вам дорасти и перерасти iTunes! :)
        • +1
          Ну так это значит соглашение надо продлевать, видимо, тут и порылась собака.
        • +1
          Просьба действительно совсем не по теме статьи — но в порядке исключения отвечу, цитирую коллегу:

          Мы делаем все возможное, чтобы наша база пополнялась новым и актуальным контентом. К сожалению, не все правообладатели готовы сотрудничать с нами, и на некоторые песни нам не удается получить лицензию. В других случаях, правообладателя бывает трудно отыскать, чтобы заключить с ним договор. Чаще всего контент появляется и пропадает на сервисе в том случае, если у рекорд компании, которая лицензировала нам песни, заканчивается срок действия договора с артистом, а новый договор между ними не подписывается. В этом случае контент может появиться в каталоге другой рекорд компании, и тогда контент остается на сервисе или очень быстро снова становится доступен. Или же артист может решить оставить все права у себя, и для получения контента нам потребуется идти договариваться к артисту напрямую, что не всегда удается сделать.
  • 0
    Очень интересно. Спасибо, что поделились.
    У меня только один вопрос есть: нет ли у вас статистики релевантности по стилям музыки? Ведь многие жанры (ambient, noize, shoegazing и др.) практически полностью состоят из различного рода шумов. Интересно бы было посмотреть, процент релевантных запросов по таким жанрам.
    • +4
      Всему что не распозналось приписывается рандомно жанр из списка (ambient, noize, shoegazing и др.)
    • 0
      Спасибо, интересный вопрос, такое исследование мы пока не проводили. На первый взгляд, оно потребует некоторой ручной работы по разметке жанра для нераспознанных треков.
  • +2
    Во-вторых, мы собрали подборку музыкальных треков, выложенных в интернете.


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

    Если же к базе треков вы присоедините, например, вконтакте или soundcloud-подобные вещи, то будет вообще здорово!

    *мечтательно вздыхаю* а было бы такое у Last.fm…
    • +2
      Зато как копирасты возрадуются возможности поиска копий контента в тех же вконтактах не только по имени.
      • +4
        В ютубе уже радуются вовсю
    • +1
      Спасибо!
      Мы планируем увеличивать полноту поиска — и в этих направлениях, конечно, тоже думаем :-)
  • +4
    а когда вы перестанете игнорировать windows phone?
    • +27
      Кому он нужен?
      • +1
        мне. вообще много кому.

        А что есть альтернативы кроме айфона?
        • –1
          Samsung Galaxy S3|4, например?
          Не холивара ради.
          • –6
            NO… был у меня андроид. больше не хочу.
            • +6
              *Очень хотел расписать, как пользовался месяц Windows Phone, но пересилил себя и удержался*
              Ваше право.
      • 0
        Мне.
    • +8
      Приложение под платформу Windows Phone уже находится в разработке, следите за анонсами.
      • 0
        спасибо.
      • –1
        отлично! Будем следить!
    • 0
      Сегодня, кстати, появился Диск для WP. Не игнорируем :)

      www.windowsphone.com/ru-ru/store/app/%D0%B4%D0%B8%D1%81%D0%BA/dde791fc-a577-49b0-8e64-6d7d653592f5
  • +2
    Всегда было интересно узнать, как работает! :)
  • +1
    А разве это не запатентовано?

    Один программист написал нечто похожее на Java и опубликовал:
    www.redcode.nl/blog/2010/06/creating-shazam-in-java/

    На что получил гневное письмо из Shazam с требованием удалить всё, т.к. оно нарушает их патент.
    • 0
      A Яндексу есть дело до американских патентов?
      Хотя и купить могут конечно…
      • 0
        Учитывая, что Я.Музыка только для СНГ — пока дела точно нет.
    • 0
      На их зарубежные патенты в эрэфии можно класть болт с таёжным прибором.
    • +4
      Спасибо, мы отдельно исследовали этот вопрос. На наши рынки патент Shazam не распространяется.
    • 0
      Странно, здесь — musicbrainz.org/doc/Fingerprinting — перечислены опенсорсные реализации муз. фингерпринтинга.
  • +1
    Спасибо, очень интересно, давно думал, как же реализованы подобные сервисы.
    Остался вопрос — как решается проблема с несколькими похожими треками (например, живая версия, исполненная очень близко к студийной) — ведь в изначальной постановке задачи требуется вернуть только один ответ.
    • +2
      По нашему опыту, с точки зрения алгоритмов распознавания живое исполнение всегда отличается от студийного.

      А если речь идёт о нескольких студийных записях, которые совсем неотличимы — то какая разница, какой из нескольких идентичных треков мы отдадим пользователю? :-)
      • 0
        У вас отдается всегда один трек или список из нескольких, наиболее подходящих может быть? Например трек может быть включен в разные сборники, ремиксы.
        • 0
          Да, всегда один — самый релевантный. В ремиксах он, скорее всего, не идентичен оригиналу. А если в сборники — какая разница, из какого сборника показать этот трек?
  • +5
    вот бы открытый и бесплатный API для этого :)
    • 0
      В ближайшее время точно не получится. Со временем — может быть, следите за анонсами.
  • 0
    Я могу ошибаться, но вроде в первых версиях Яндекс.Музыки (для iOS) вы использовали SoundHound? В последней версии уже никакого упоминания об этом нет. Чем вас не устроил этот сервис и вы решили сделать всё своё?
    • +5
      Да, действительно раньше использовали технологии SoundHound — и совсем недавно перешли на собственное решение в мобильном приложении Яндекс.Музыка (и на iOS, и на Android). Причин перехода несколько:
      1) нам удобнее самим контролировать качество продукта и развивать его в тех направлениях, которые важны для наших пользователей
      2) так появляется больше возможности применять наши наработки к смежным областям (классификация жанров, склейка дублей и т.п.)
  • +1
    А планируете ли добавить возможность распознавать музыку с микрофона в music.yandex.ru/? Что бы с компьютера можно было распознавать с микрофона, без приложений для телефона. Очень нужно)
    • +1
      Думаем про это :-)
  • –1
    только мы с друзьями сделали прототип и отправили его в startfellows на грант, как тут и яндекс музыка подоспела =)
  • +5
    Просто здорово, потихоньку начинаю переезжать с гугла на яндекс. Только не теряйте темпа :-)
    • +2
      и голову :) (с учетом недавних гуглоисторий)
  • 0
    А классические произведения типа Гайдн, Моцарт оно не знает? Тестировал на sky.fm, канал Israeli Hits конечно наивно было надеяться, канал Mostly Classical не распознало ни разу, рэп и рок узнает с первого раза, кантри через раз.

    Кроме того через раз очень долго крутится «анализ» потом сообщает об ошибке загрузки, хотя соединение wi-fi.
    Платформа iphone 4s.
    • 0
      Про первую часть: а можете назвать конкретные треки, которые не удалось распознать? (в идеале — сразу ссылками на треки на Яндекс.Музыке, так будет чуть проще разбираться)
      • 0
        Конечно тех треков уж не припомню, попробовал на sky.fm снова, из классики ничего не распознает, вот примеры треков:

        Francesco Geminiani — Concerto Grosso in D Major, Op. 3, No. 1, mvmt. IV. Allegro (Jaroslav Krecek, Capella Istropolitana)

        Vivaldi — Concerto for Flute, Strings and Basso Continuo in F Major No. 5, Op. 10, RV 434, mvmt. III. Allegro

        Bach — Keyboard Concerto No. 7 in G Minor, BWV 1058, mvmt. I. (Without Indication) (Trevor Pinnock, English Concert)

        На Я.Музыке довольно много вариантов BWV 1058, но конкретно при поиске данного исполнения яндекс отсылает на youtube www.youtube.com/watch?v=OibctIudG2k

        Из Israeli Hits вот пример:

        Yoram Gaon — nigun atik

        На Я. Музыке точно такого трека не находит, но при поиске поиске по названию Я.Музыка выдает ссылки на youtube www.youtube.com/watch?v=H7FraPrWlyM

        Конечно если включить любой трек непосредственно с яндекс музыки он распознается без проблем.
        • +2
          Спасибо за примеры.

          С классикой — похоже, ключевая причина в том, что даже несколько записей одного и того же произведения, исполненные одним и тем же коллективом — это разные записи. Даже небольшие изменения темпа, тембра — оказываются критичными. Такая проблема гораздо реже случается для популярной музыки, там исполнитель гораздо реже варьируется, да и для одного исполнителя гораздо реже случаются повторные записи одного произведения.
          • 0
            Тогда напрашивается следующее решение — если не удалось распознать конкретную запись, то можно сделать второй этап — распознавание «по нотам». Вероятно, потребуется отрывок большей длительности.
    • 0
      По второй проблеме — скиньте мне пожалуйста ваш email-адрес в личку. Я передал вашу проблему коллегам в поддержку полоьзователей, они свяжутся с уточнениями.
  • 0
    Я раньше думал, что это как раз делается с помощью взаимно корреляционной функции. Правда затраты были бы сумасшедшие
    • 0
      Если находится несколько вариантов (чем грешит SoundHound), можно делать второй этап анализа через взаимную корреляцию.
      Заодно можно расслабить ограничения на этапе сравнения спектра.
  • +2
    «И мы подобрали такую их [пиков] комбинацию, при которой остаётся минимальное число пиков, но почти все они устойчивы к искажениям.»


    А вы не пробовали «воспроизводить» (делать обратное преобразование) эти самые найденные пики, очистив их от остальных данных на диаграмме «частота-время»? Интересно, что будет слышно.
    • 0
      Тут есть довольно много нюансов, но если совсем кратко — нет, пока не пробовали :-)
  • +1
    Расскажите пожалуйста по-подробнее, как вы конвертируете амплитуду\время в амплитуду\частоту.

    В этой статье читал www.redcode.nl/blog/2010/06/creating-shazam-in-java/?, что используется быстрое преобразование Фурье, но въехать, как этот алгоритм работает пока не получилось. Если-бы Вы смогли объяснить человекопонятным языком, было-бы совсем супер
    • +1
      Если совсем на пальцах:
      = любую периодическую функцию можно приблизить рядом Фурье
      = музыкальную запись можно разрезать на множество временных интервалов, и на каждом интервале приближать её своим рядом Фурье — тогда длину этого интервала можно считать периодом (и тогда слово «периодической» в предыдущем пункте уже не важно)
      = быстрое преобразование Фурье — просто вычислительно недорогой алгоритм получения первых N коэффициентов для такого разложения

      Вы об этом спрашивали?
      • 0
        Не совсем, но чувствую, что то, что я не понимаю такая простятина, нужно просто сдуть пыль с учебников по математике и скачать MathLab
      • +3
        Мне кажется, что эта картинка более точно описывает суть преобразования
        image

        Взято из Википедии
        • 0
          Действительно, очень хорошая картинка.
  • 0
    Гений программист, создатель известной программы goldwave в 2008 году на форуме мне ответил ссылкой на этот алгоритм.
    en.wikipedia.org/wiki/Autocorrelation
  • +1
    Новая забава — покричать/пропеть что-нибудь в смартфон и посмотреть что выдаст яндекс.
  • 0
    Всегда было любопытно — а нельзя ли эту задачу решать комбинацией двух алгоритмов. Сначала применить набор из N вейвлет для каждого фрагмента трека, где N это достаточно большое число. Под вейвлетами я подразумеваю не совсем классическое определение, а просто коротенькие фрагменты звука. Они могут быть от нескольких миллисекунд до секунд, могут представлять собой нарезку инструментов, могут быть нарезкой постоянной частоты, а могут классические, такие как Хаар, Шляпа, Гаусс. Эта операция спозиционирует фрагмент в N-мерное пространство. При этом устойчивость к шумам и инвариантность должна быть значительно выше классического Фурье-спектра: спектральный шум не сильно влияет на вейвлет, а за счёт большой базы сэмплов даже пара полностью выпадших вейвлетов не будет критична.
    Ну а потом произвести поиск ближайшего вектора в N-мерном пространстве. Там есть много хороших и быстрых алгоритмов. Тот же SVM наверняка можно приспособить.
    Просто аналогичные способы периодически использую в распознавании объектов на изображениях. Возможно есть какая-то их применимость и к аудиопотоку.
    • +1
      Мы недаром привели в списке литературы статью, подробно разбирающую применение вейвлетов для этого класса задач :-)

      Shumeet Baluja, Michele Covell: «Audio Fingerprinting: Combining Computer Vision & Data Stream Processing»

      Наверняка вам будет любопытно прочесть, если ещё не успели.
      • 0
        Проморгал, спасибо:)
        Статья интересная, хотя, конечно, подход не тот что я выше описал, а с другой стороны. Всё же я предлагал использовать больше вайвлетов и применять их вместо построения спектрограммы, напрямую к сигналу. Любопытно, что одни и те же методы машинного зрения приводят к разной версии алгоритма.

        Да, ещё сегодня вспомнилось, возможно вам будет любопытно. Когда вы ищите похожую на сэмпл картину пиков в базе то это очень похоже на две классические задачи для которых придумано огромное количество методов. Первая — привязка снимка к звёздному небу. Вторая — сравнение отпечатков пальцев. Может быть пригодится.
        • 0
          Спасибо — действительно любопытно.
  • –1
    Хмм, выглядит прикольно, сидя в клубе или ресторане, нажать кнопку и узнать что играет, НО…
    Ребята, вы в реальной жизни это проверяли?
    ИМХО хорошо работать это будет лишь при условии отсутствия какой-либо динамической обработки, транспозиции, реверберации, что уже совсем не так интересно.
    Кроме того специфические, особенности «прогрессивной» электронной музыки, говнорока и попсы наложат таки свой отпечаток :-)

    Да-да, три простых и правильных аккорда, Yamaha PSR — мама российской (и не только) эстрады, да и современные библиотечные грувы, и синтаки кочующие из аранжировки в аранжировку…
    • 0
      Если это вопрос, можете его переформулировать? Пока мы не очень поняли, о чём в точности вы спрашиваете.
    • +1
      Ребята, вы в реальной жизни это проверяли?

      За крайне редким исключением пользуюсь распознаванием музыки в шумных местах (кафе, бары, улица). Не Яндексом, но soundhound. Распознавание работает в 90% случаев.
  • –1
    Пока Гугл чистится от продуктов, размывающих фокус и яростно разрабатывает самоуправляемые машины и google glass, Яндекс запускает конкурента Шазаму и Саундханду.

    Ребята, без обид, но может быть примените свои без сомнения талантливые ресурсы на что-то более инновационное, а не на копирование (как бы это ни было увлекательно)? :)
    • 0
      Мне кажется Яндекс никогда не был про инновации, он про продукты для пользователей (уже существующих). Это заявлялось неоднократно на многих конференциях и в том числе подкрепляется тем фактом, что Яндекс несравнимо мало покупает продукты/компании в отличии от зарубежных коллег. Хотя мне как гику ближе ваша позиция :)
      • +2
        Скорее так: при том что у Яндекса алгоритмическая, технологическая, математическая часть продуктов на самом приличном уровне («инновационном», как бы я не ненавидел этот термин:), тем не менее (1) мы почти никогда не попадаем в фокус западной технопрессы из-за культурного и языкового барьера и (2) собственно «продуктовая инновация» (когда из кусков хорошо известного «технологического старого» лепится и четко подается «продуктовое новое») — не самая сильная сторона отечественной разработческой культуры.

        Но мы учимся (1) «говорить по английски» и (2) активнее лепить «продуктовое новое». Совсем-совсем новое.

        (Кстати, вы почти буквально процитировали товарища Роберта Скобла: он как-то, пару лет назад, высказался, что, мол, такие компании («треш-холдинги» :) как Яндекс и Baidu не способны на инновацию в принципе :)
        • 0
          Илья, приятно видеть ваш комментарий, спасибо. В данном случае я имел в виду сознательно выбранную стратегию Яндекса, которая, как мне кажется, заключается в создание уже проверенных и очевидно необходимых продуктов для конкретных людей (не в вакууме, как часто делают стартапы). Это не исключает высокий уровень реализации. Просто меньше риски = прогнозируемый результат. Так конечно труднее попасть в «западный фокус», но экономическую эффективность такого подхода Яндекс уже доказал.

          Что касается способностей Яндекса на инновации, то кажется даже изначально критически настроенный комментатор выше в них не сомневается.
    • 0
      Мы как раз наоборот уверены, что фокусирование на поиске — это хорошо и правильно. Ведь поиск музыки по фрагменту — это тоже вид поиска. И нам важно, чтобы его качество росло с такой скоростью, которая бы нас устраивала — поэтому планируем развивать его сами. И инновации стараемся создавать, прежде всего, на ниве поиска же. Вот недавно Острова анонсировали, например — немаленькая штука.
  • 0
    Спасибо, интересно. API планируется или есть какие-то проблемы с этим (коммерческие, юридические)?
  • 0
    Как разработчик аналогичного решения для несколько иной задачи (контроль музыкального контента радиостанций) задам пару технических вопросов:

    1. Сколько вы в среднем генерируете ключей (хэшей) в секунду?

    2. Правильно ли я понял, что Вы используете 2-звездные созвездия (в терминологии Шазама)?

    3. Если я правильно понял и хэш у Вас 20-битный (т.е. довольно короткий), то в скольких в среднем записях из базы (вернее в какой доле записей) находится этот хэш? Также интересует максимальное значение этого параметра.

    Как-то очень настораживает, что у Вас получается 80% успешного распознавания, тогда как даже бесхитростная реализация алгоритма Шазама с (с 32-битным хэшем и 2-звездными созвездиями) сразу дает более 95% успешных распознаваний. Дальше идет борьба за приближение к 99.9% и за то, чтобы сделать хэш максимально уникальным и тем самым уменьшить нагрузку на базу.

    В нашем случае дополнительной проблемой было требование обрабатывать кучу каналов, распознавать композицию в реальном времени с задержкой не более 5 секунд от момента начала проигрывания и определять моменты начала и конца композиции в аудиопотоке, но у нас сейчас база на порядок меньше вашей.
    • 0
      Попробую ответить:
      1. Сейчас под рукой нет точной цифры по большому числу треков; по нескольким трекам (первым попавшимся) цифра порядка 60 хешей в секунду.

      2. Мы используем пары пиков. Если это и есть двузвёздные созвездия в терминологии Шазама, то ответ «да».

      3. В статье есть все исходные для этой цифры: 6 млн / 2^20 ≈ 6 документов на пару. Максимального значения под рукой сейчас нет, а как оно может помочь с вашими вопросами?

      Как нам кажется, разница в точности с вашим решением вызвана тремя причинами:
      а) вы имеете дело с сильно более чистым сигналом — у вас нет ни посторонних шумов бара/кафе, ни акустики помещения, ни искажений АЧХ микрофона.
      б) я правильно понимаю, что у вас база заведомо содержит все треки, которые играются на радио — и отсутствие трека в базе не считается результатом «не найдено»? В нашем случае считается — а наши пользователи спрашивают, вообще говоря, не только треки из нашей базы. Т.е. в наши 20% нераспознанного входят оба случая — и «треки, которых мы не знаем», и «алгоритм не смог найти» (например, из-за шумов).
      в) вы сами написали, что ваша база на порядок меньше нашей. В общем случае с ростом базы точность падает (растёт вероятность «зацепить» что-то похожее, но другое)
      • 0
        порядка 60 хешей в секунду


        Это значительно меньше, чем у нас. Мы начинали с примерно 200 хэшей в секунду, потом увеличили ограничение до 600 (иначе у нас были проблемы с «нехарактерными» кусками композиций, особенно во вступлениях). Причем это именно искусственное ограничение, хэши сортируются по некоему условному «качеству» и отбирается не более заданного количества лучших. А у Вас количество хэшей ограничено жестко, или их получается так мало за счет фокуса с «подвижным ножом»? Я не вполне понял его смысл, но мне показалось, что использование такой схемы не подходит для обработки в реальном времени.

        6 млн / 2^20 ≈ 6 документов на пару. Максимального значения под рукой сейчас нет, а как оно может помочь с вашими вопросами?


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

        я правильно понимаю, что у вас база заведомо содержит все треки, которые играются на радио — и отсутствие трека в базе не считается результатом «не найдено»?


        Конечно же нет. «Начало нераспознанного участка» и «Конец нераспознанного участка» — обычные события для нашей системы. Для типичной радиостанции в среднем 30% времени вещания распознать не удается либо из-за немузыкального контента, либо из-за отсутствия композиций в базе.
        • 0
          Количество хешей — функция от нескольких параметров прореживания (они приведены в статье).

          Опускающееся лезвие (и все остальные приёмы для выбора пиков), на первый взгляд, вполне может работать и для real-time определения — почему нет?

          Про среднее число вхождения ключей — давайте тогда уточним, что называть средним. А максимальное — это же просто выброс, как он поможет? Допустим есть один (или даже несколько) ключей, которые встречаются почти во всех треках — но разве это может помочь сделать какой-либо вывод? Кажется, нет.

          30% времени вещания распознать не удается
          Тогда непонятно, как это соотносится с цифрами 95..99.9% в вашем первоначальном комментарии.
          • 0
            давайте тогда уточним, что называть средним. А максимальное — это же просто выброс, как он поможет? Допустим есть один (или даже несколько) ключей, которые встречаются почти во всех треках


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

            как это соотносится с цифрами 95..99.9% в вашем первоначальном комментарии


            Нашей задачей было не максимально полно распознавать то, что играется на радиостанции, а с близкой к единице вероятностью опознавать ситуацию, когда играется композиция из базы. Соответственно, при оценке качества не учитывался случай, когда не опознается композиция, отсутствующая в базе.
            • 0
              при оценке качества не учитывался случай, когда не опознается композиция, отсутствующая в базе
              Ну вот и разобрались с причиной (б) в расхождении наших показателей качества — мы такие случаи учитываем как нераспознанное.
              • 0
                Ну т.е. Ваша оценка является оценкой качества сервиса для конечного пользователя и вообще ничего не говорит о качестве используемого алгоритма.
                • 0
                  Да, именно совокупного качества сервиса — и считаем это правильным для наших задач. Потому что алгоритм распознавания — лишь одна его часть; вторая, полнота базы, ведь тоже практически полностью в наших руках.
                  • 0
                    Но статья все же именно про алгоритм, так что и оценивать следовало бы качество алгоритма, а не сервиса. Тем более, что он от классического Шазама (подробно описанного в первой же статье из списка) отличается только несколькими минорными модификациями.
                    • 0
                      Наша статья — гораздо больше про подход «как вообще решаются такие задачи», чем про конкретный алгоритм. И цифры в ней — прежде всего чтобы дать представление о том, какими они в такой задаче бывают, на примере нашего сервиса.

                      Про методику оценки качества. Согласитесь, что не совсем корректно измерять точность такого алгоритма в отрыве от конкретной базы треков и конкретного потока запросов на распознавание. Условно, если алгоритм показывает прекрасное качество на потоке совершенно незашумлённых запросов и на базе в 10 тыс треков — это ведь не значит, что качество будет таким же на 10 млн треков и на потоке очень шумных запросов?

                      Да, нам важно «совокупное счастье пользователя» — и для этого, согласитесь, наша метрика подходит лучше, чем изолированное качество алгоритма. Тем более, что и полнота базы в наших руках, и экстенсивное увеличение объёма базы вовсе не линейно конвертируется в рост процента успешных распознаваний — вы ведь понимаете почему.
                      • 0
                        Ok, мне вполне понятен Ваш подход, хотя и совершенно не близок.

                        В статье про Шазам есть вполне корректные оценки качества алгоритма распознавания безотносительно базы. Качество алгоритма при работе с базой также без особых проблем тестируется независимо.
  • 0
    rm
  • +1
    А нет случайно такого он-лайн сервиса? Вот есть у меня аудиозапись в mp3(записанная с эфира радио много лет назад на кассету, и позднее перегнанная в mp3) — как её в интернете поискать?
    • 0
      Или загрузите её в Аудиотаг, или проиграйте её при включённом микрофоне для Мидоми.
  • 0
    Интересен вопрос, рассматривали ли вы использование аудио-дескрипторов, аналогичным тем, что имеются в стандарте MPEG-7, в качестве дополнения к распознаванию по пикам? Если да, то почему отказались?

    P.S. Как я только мог прослоупочить такую интересную статью :)
    • +1
      Да, мы считаем это интересным направлением для развития, но пока на эту тему у нас нет результатов, которыми можно было бы поделиться.
  • 0
    Вопрос скорее из параллельной плоскости, однако также про поиск музыки по звуку.
    Всегда интересовало, как яндекс находит песни по словесному описания?
    Например запрос «у а а у песня» отсылает к clck.ru/9UQaU ( music.yandex.ru/#!/track/17213160/album/2042296 ) и угадывает.

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

Самое читаемое Дизайн