0,0
рейтинг
12 марта 2015 в 21:49

Разработка → Звуковые отпечатки: распознавание рекламы на радио из песочницы

Из этой статьи вы узнаете, что распознавание даже коротких звуковых фрагментов в зашумленной записи — вполне решаемая задача, а прототип так вообще реализуется за 30 строчек кода на Python. Мы увидим, как тут помогает преобразование Фурье, и наглядно посмотрим, как работает алгоритм поиска и сопоставления отпечатков. Статья будет полезна, если вы сами хотите написать подобную систему, или вам интересно, как она может быть устроена.

Для начала зададимся вопросом: кому вообще нужно распознавать рекламу на радио? Это полезно рекламодателям, которые могут отслеживать реальные выходы своих рекламных роликов, ловить случаи обрезки или прерывания; радиостанции могут мониторить выход сетевой рекламы в регионах, и т.п. Та же задача распознавания возникает, если мы хотим отследить проигрывание музыкального произведения (что очень любят правообладатели), или по небольшому фрагменту узнать песню (как делают Shazam и другие подобные сервисы).

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

Как это работает


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

image

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



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

Построить такую спектрограмму при помощи Python можно так:
Для загрузки данных из wav файла можно использовать библиотеку SciPy, а для построения спектрограммы использовать matplotlib. Все примеры даны для версии Python 2.7, но вероятно должны работать и для 3-ей версии. Предполагаем что в file.wav содержится запись звука с частотой дискретизации 8000 Гц:

import numpy
from matplotlib import pyplot, mlab
import scipy.io.wavfile
from collections import defaultdict

SAMPLE_RATE = 8000 # Hz
WINDOW_SIZE = 2048 # размер окна, в котором делается fft
WINDOW_STEP = 512 # шаг окна

def get_wave_data(wave_filename):
    sample_rate, wave_data = scipy.io.wavfile.read(wave_filename)
    assert sample_rate == SAMPLE_RATE, sample_rate
    if isinstance(wave_data[0], numpy.ndarray): # стерео
        wave_data = wave_data.mean(1)
    return wave_data

def show_specgram(wave_data):
    fig = pyplot.figure()
    ax = fig.add_axes((0.1, 0.1, 0.8, 0.8))
    ax.specgram(wave_data,
        NFFT=WINDOW_SIZE, noverlap=WINDOW_SIZE - WINDOW_STEP, Fs=SAMPLE_RATE)
    pyplot.show()

wave_data = get_wave_data('file.wav')
show_specgram(wave_data)


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

Вот как получить отпечаток звукового фрагмента
def get_fingerprint(wave_data):
    # pxx[freq_idx][t] - мощность сигнала
    pxx, _, _ = mlab.specgram(wave_data,
        NFFT=WINDOW_SIZE, noverlap=WINDOW_OVERLAP, Fs=SAMPLE_RATE)
    band = pxx[15:250]  # наиболее интересные частоты от 60 до 1000 Hz
    return numpy.argmax(band.transpose(), 1)  # max в каждый момент времени

print get_fingerprint(wave_data)


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



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



Построить такую замечательную гистограмму можно так:
def compare_fingerprints(base_fp, fp):
    base_fp_hash = defaultdict(list)
    for time_index, freq_index in enumerate(base_fp):
        base_fp_hash[freq_index].append(time_index)
    matches = [t - time_index  # разницы времен совпавших частот
        for time_index, freq_index in enumerate(fp)
        for t in base_fp_hash[freq_index]]
    pyplot.clf()
    pyplot.hist(matches, 1000)
    pyplot.show()

Файлы, на которых можно потренироваться в распознавании, лежат тут.

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

Результаты


На тех записях, что были у нас, F-score составил 98.5%, а точность определения начала — около 1 с. Как и ожидалось, большая часть ошибок была на коротких (4-5 с) роликах. Но основной вывод лично для меня — что в таких задачах решение, написанное самостоятельно, часто работает лучше чем уже готовое (например из EchoPrint, про который уже писали на хабре, получалось выжать не более 50-70% из-за коротких роликов) просто потому, что у всех задач и данных есть своя специфика, и когда в алгоритме много вариаций и большой произвол по выбору параметров, то понимание всех этапов работы и визуализация на реальных данных очень способствует хорошему результату.

Fun facts:

Литература:
Константин Лопухин @kostialopuhin
карма
9,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

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

  • 0
    Баловался с голосовым управлением для «умного дома».

    Сделал примитивный скрипт, который записывал 3-секундные ролики и отправлял их на сервера Google. Все работает… но бесплатно декларируется около 50 распознаваний в день. При этом мой скрипт долго и упорно крутится до получения «кодового слова» (после которого, собственно, и идет команда). Надо будет попробовать прикрутить описанное для оффлайн-декодирования «кодовой последовательности» (а потом уже можно реальную команду на сервера Google отправлять на распознавания).

    Должно получиться довольно компактно и «прозрачно»,
    • +2
      Мне кажется то, что описано в статье, вряд лм — тут распознавание основано на том, что в записи с помехами/фоном/искажениями все равно сохраняются частоты и тайминг, а в голосе вряд ли это так?
      Могу посоветовать использовать движок Sphinx, он работает offline, в том числе для русского, и на небольшом словаре у него хорошая точность.
      • 0
        В домашних условиях, думаю, помехи/фоновые звуки/искажения — тоже присутствуют… а частоты и тайминги — да, плавают, наверняка… но в целом, сохраняются.

        За дополнительную наводку — спасибо, тоже попробую.
  • 0
    Я так понял, что данный подход позволяет найти заданный отрезок в зашумленной записи?

    Будет ли это работать если я хочу просто найти похожие записи?
    • 0
      Да, все правильно.
      По поводу поиска похожих записей — это зависит от того, чем определяется похожесть. Если это например ремиксы или разные версии одной песни, то да, на них у нас как раз было много «ложных» срабатываний. Но допустим одну и ту же песню исполненную немного в разном темпе такой алгоритм не найдет, нужно уже усложнять.
      • 0
        >Если это например ремиксы или разные версии одной песни, то да, на них у нас как раз было много «ложных» срабатываний.

        не понял, вы же вроде искали рекламу.

        Насчёт похожести, да, это вопрос как определить, какие есть подходы?

        В идеале хотелось бы систему которая использует не колаборативную фильтрацию(рекомендательная система) аля last.fm, а использует data-driven подход, т.е. по самому контенту музыкальному.

        Из более реального, то что приходит на ум в первую очередь это типа нечеткие дубликаты: например студийная запись песни и запись песни с концерта, второе это одна и та же музыка, но слова разные, типа переделка как пример:
        www.youtube.com/watch?v=DW5icEb5nk4
        www.youtube.com/watch?v=6PDmZnG8KsM
        • 0
          > не понял, вы же вроде искали рекламу

          Да, в этом посте больше про рекламу, но песни мы тоже искали.

          data-driven подход к рекомендациям звучит очень заманчиво, да! Интересно, как это можно сделать.
          Про студийную/концертную запись сходу не отвечу, нужно попробовать — сложно сказать насколько они в плане темпа точно совпадать будут.

          В целом то подход который описан очень ограничен, зато простой.
        • +1
          Вот тут кратко перечислены методы events.yandex.ru/lib/talks/1809/
          Описанный в статье не подойдет — он полагается на частоты и временной интервал между ними, которые в разных исполнениях будут слегка разные, а нужно полагаться на ноты.
  • 0
    Не уверен, что здесь (в задаче про рекламу на радио) переход к частотному представлению вообще к месту. Попробуйте погонять мой скрипт, который основан на скалярных произведениях во временном представлении. Он всегда «находит» искомый звук в анализируемом, но сообщает уровень зашумленности. Если SNR мало, то следует считать, что звук на самом деле не найден. Недостаток — сбивается на малейшем растяжении времени, но на радио это вроде как просто не может быть.

    Скрипт можно гонять в трех режимах. Режим --this ищет фрагмент, который имеет минимальную сумму квадратов отличий от искомого. --similar = поиск фрагмента, который после домножения на определенную константу будет иметь минимальную сумму квадратов отличий от искомого (т.е. игнорируется изменение амплитуды). --like = поиск фрагмента, который имеет максимальное скалярное произведение с искомым (т.е. игнорируется аддитивный шум и изменение амплитуды).
    • 0
      Попробовал сам — в вашем примере мой скрипт находит рекламу правильно, но с плохим SNR. Если оставить от нее только первую секунду — работает лучше. Т.е. похоже, что раcтяжение таки есть.

      Еще добавил графики correlation_at, cos2phi_at и difference_norm_at, и видно, что вторая метрика (квадрат косинуса угла между векторами из семплов) в вашем случае является наиболее надежной.
      • 0
        Очень интересно, спасибо! Насколько я понял, существенную часть работы делает scipy.signal.fftconvolve — но я пока не смог понять интуитивно, как и почему он работает при анализе двух звуковых фрагментов. Не знаете, где про это можно почитать?
        • 0
          Это просто свертка. Прочитать про нее можно в Википедии.

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

          Теперь почему это работает (в варианте --like).

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

          Варианты --this и --similar так интуитивно не объяснить, но соответствующие критерии довольно просто переписываются через всякие скалярные произведения сдвинутых сигналов и скалярные квадраты фрагментов сигнала, т.е. через быстрые операции.
          • 0
            Да, теперь ясно, спасибо за объяснение!
    • +3
      Если образец один, то особых проблем нет — ищи себе взаимную корреляцию как вы, и все довольны — устойчивее сложно придумать на самом деле. Но когда образцов тысячи, то сложность O(n) уже не подходит и нужна индексация, которую с корреляцией не построишь. И тут подход с поиском «интересных точек» и обратным индексом {частота_интересной_точки => имя_файла} позволяет ускорить поиск до приемлемых величин. То есть мы находим «интересные частоты» в звуковом потоке и ищем файлы, которые эти частоты содержат, в индексе, а далее выбираем файл, содержащий наибольшее число интересных точек.

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

      Такую штуку легко построить на основе Echoprint, отредактировав его python api в части отбора лучших кандидатов.
      Там в качестве поиска по индексу используется банальный текстовый поиск с помощью Apache Solr. Чем больше «интересных точек», тем выше Solr ранжирует «документ». Solr выдает большой список кандидатов, содержащих интересные точки. Далее в github.com/echonest/echoprint-server/blob/master/API/fp.py#L143 из этих кандидатов выбирается лучший. Каким образом? Таким github.com/echonest/echoprint-server/blob/master/API/fp.py#L262 — то ли строится гистограмма как в статье, то ли еще как, нужно читать код, я уже не помню. Но это не важно. Ничто не мешает или самому делать запросы к Solr или же переписать best_match_for_query, добавив туда «временную» корреляцию, доставая wav образца откуда-нибудь из базы (так как сам echoprint хранит только отпечатки). В итоге поменяв сотню строчек отбора кандидатов, и без написания своего codegen и API, можно получить систему, удобную лично для себя.
  • 0
    Именно так и работает шазам и другие подобные серсисы поиска музыки, да и похожая статья с описанием этого алгоритма уже была (вроде) на хабре
  • 0
    Полезно, спасибо.
    Думаю, что если развить алгоритм до состояния, которое позволяет еще и сопоставлять отпечатки, растянутые по времени, то так можно дойти и до распознавания напетых мелодий. Но в любом случае скорость распознавания уже не будет такой высокой и будет много ложных срабатываний.
  • 0
    Кстати, в большинстве программ для ведения радийного эфира, есть подобная функция распознавания рекламной аудиометки. Используется это в основном на региональных радиостанциях, которые ретранслируют эфир своего партнёра ( к примеру какой-нибудь столичной радиостанции).
    По этим аудиометкам, во время рекламных блоков происходит автоматическое переключение ретрансляции на свой эфир, для запуска уже своей региональной рекламы.
  • 0
    Задавался как-то вопросом автоматического переключения ТВ на другой канал в начале рекламного блока путём анализа характерного повышения громкости с участием Arduino. Идея так и осталась идеей. Интересно, а есть ли в ТВ эфире подобные радио метки?
    • 0
      Да, для ТВ эфира это тоже есть. Работает аналогично тому, что я писал выше о FM эфирах.
      • 0
        Я немного не корректно выразился. Интересует даже не эфирное, а спутниковое ТВ. А также интересно, как выявить такие метки (эталонные аудио фрагменты), если они заранее не известны. Визуальный анализ спектра, строить предположения? Есть ли какой-то единый стандарт для всех ТВ операторов и регламентируется ли его соблюдение? Читал также, что иногда используются метки видеоряда, а значит аудио метки могут отсутствовать. Наверняка это служебная информация без публичного доступа?
        • 0
          Насчёт выявления таких меток — как обстоит дело с ТВ, я не знаю (хотя подозреваю, что всё-таки аналогично радиоэфиру). А что касается меток на радио — единого стандарта не существует. Это может быть как характерный короткий «пик», так и целая звуковая отбивка. Принцип такой: та станция, которую вы будете ретранслировать, присылает вам свои сэмплы аудиометок и вы уже у себя заливаете эти сэмплы в базу программы-ретранслятора.
          • 0
            Ну да, это если я собираюсь ретранслировать. А если мне просто хочется избавить себя от каких-либо рекламных блоков? :) Тогда, получается, только визуальный анализ…
            • 0
              Да, остаётся только анализировать аудио или видео ряд перед рекламным блоком. И ещё нюанс: актуальных меток может быть несколько и они периодически меняются.
  • 0
    Однажды делали для оператора приблуду для контроля и подсчета рекламных роликов по тв и радио. Было требование, чтобы дешево и сердито. Сошлись на варианте, что во всех роликах будут тональные сигналы, а их распознавание — тривиальная задача.
  • 0
    Аналог tophit.ru для песен (ну и moskva.fm, как же без неё) и admonitor.ru для рекламы?
  • 0
    Подобная функция уже была реализована уже в некоторых программах для радио, в частности — в вещательной программе Synadyn питерской компании Digiton.

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