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

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

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

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

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

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

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

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

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 ^[5] составил 98.5%, а точность определения начала — около 1 с. Как и ожидалось, большая часть ошибок была на коротких (4-5 с) роликах. Но основной вывод лично для меня — что в таких задачах решение, написанное самостоятельно, часто работает лучше чем уже готовое (например из EchoPrint, про который уже писали ^[6] на хабре, получалось выжать не более 50-70% из-за коротких роликов) просто потому, что у всех задач и данных есть своя специфика, и когда в алгоритме много вариаций и большой произвол по выбору параметров, то понимание всех этапов работы и визуализация на реальных данных очень способствует хорошему результату.

Fun facts:

• На спектрограмме одного из треков группы Aphex Twin есть человеческое лицо ^[7]
• Автор статьи, который воспроизвел алгоритм Shazam на Java, получил от их юристов письма с угрозами ^[8]

Литература:

• An Industrial-Strength Audio Search Algorithm ^[9] (pdf)
• Краткое описание алгоритма Shazam ^[10] и перевод ^[11]
• Воспроизведение алгоритма Shazam на Java ^[12]

Автор: kostialopuhin

Источник ^[13]