2 Основной принцип работы

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

В следующих разделах представлены 3 основных компонента.

2.1 Надёжные оценки

В целях решения проблемы надёжной идентификации в присутствии весьма значительного шума и искажений, мы экспериментировали с различными характеристиками кандидата, которые могут выжить при GSM кодировании в присутствии шума. Мы остановились на пиках спектрограммы из-за их надёжности в присутствии шума и приблизительно линейной совпадаемости (superposability) [1]. Частотно-временная точка является пиком кандидата, если она имеет более высокое содержание энергии, чем все её соседи в области вокруг данной точки. Пики кандидата выбираются в зависимости от критерия плотности, чтобы гарантировать, что частотно-временная полоса для звукового файла имеет достаточно равномерное покрытие. Пики в каждой частотно-временной области также выбираются в зависимости амплитуды, на основании того, что самые высокие по амплитуде пики, скорее всего, переживут вышеперечисленные искажения.

Таким образом, сложная спектрограмма, такая, как показанная на Рисунке 1A, может быть уменьшена до редкого набора координат, как показано на Рисунке 1B. Обратите внимание, что в этой точке амплитудная компонента была устранена. Это сокращение имеет преимущество достаточной нечувствительности к эквалайзеру, так как обычно пик в спектре по-прежнему остаётся пиком с теми же координатами в профильтрованном спектре (при условии, что производная функции передачи фильтра разумно мала - пики в окрестности резкого перехода в передаточной функции имеют небольшой сдвиг по частоте). Мы называем список разрежённых координат "картами созвездий", так как разбросанные координатные точки часто напоминают звёздное поле.

Рис. 1A, Спектрограмма

Рис. 1B, Карта созвездий

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

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

Yang также рассматривал использование пиков спектрограмм, но использовал их по-другому [10].

2.2 Быстрое комбинаторное хэширование

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

Хэши отпечатков формируются из карты созвездий, в которой пара частотно-временных точек комбинаторно связаны. Выбираются опорные точки, каждая опорная точка имеет целевую зону, связанную с ней. Каждая опорная точка последовательно спарена с точками в пределах своей целевой зоны, каждая пара даёт две частотных компоненты плюс разница во времени между точками (Рисунки 1C и 1D). Такие хэши вполне воспроизводимы даже в присутствии шума и при сжатии голосовым кодеком. Кроме того, каждый хэш может быть упакован в 32-х разрядное беззнаковое целое число. Каждый хэш также связан со смещением во времени от начала соответствующего файла до опорной точки, хотя абсолютное значение времени само по себе не является частью хэша.

Рис. 1C Генерация комбинаторного хэша

Рис. 1D Детали хэша

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

Количество обработанных хэшей аудио-записи в секунду примерно равно плотности точек созвездий в секунду умноженному на коэффициент разветвления в целевой зоне. Например, если каждая точка созвездия берётся как базовая точка и если целевая зона имеет коэффициент разветвления равный F=10, то количество хэшей примерно равно F=10 умножить на число точек созвездия, извлечённых из файла. Ограничивая число точек, выбранных в каждой целевой зоне, мы стремимся ограничить быстрый комбинаторный рост числа пар. Коэффициент разветвления приводит непосредственно к фактору стоимости с точки зрения места для хранения.

Формируя пары вместо поиска совпадений с отдельными точками созвездия мы получаем огромное ускорение процесса поиска. Например, если каждая частотная компонента имеет 10 бит и компонент Δt также 10 бит, то соответствующая пара точек даёт 30 бит информации, по сравнению с только 10 для одной точки. Тогда отличие такого хэша было бы примерно в миллион раз больше, в связи с 20-ю дополнительными битами, и, следовательно, скорость поиска для одного маркера хэша увеличена аналогично. С другой стороны, в связи с комбинаторной генерацией хэшей, предполагая симметричную плотность и коэффициент разветвления для генерации хэша базы данных и образца, есть в F раз больше комбинаций маркеров неизвестного образца для поиска и в F раз больше маркеров в базе данных, таким образом, общее ускорение является фактором около 1000000/F2, или около 10000, выше скорости поиска маркера на основе отдельных точек созвездия.

Обратите внимание, что комбинаторное хэширование это квадрат вероятности выживания точки, то есть если р является вероятностью выживания пика спектрограммы на пути от оригинального исходного материала до захваченного записанного образца, то вероятность хеша из пары выживших точек приблизительно p2. Это уменьшение живучести хэша является компромиссом в сравнении с огромным предоставляемым увеличением скорости. Снижение вероятности выживания отдельного хэша смягчено комбинаторной генерацией большего количества хэшей, чем исходных точек созвездия. Например, если F=10, то вероятность, что по крайней мере один хэш выживет для данной точки привязки была бы объединённой вероятностью такой опорной точки и по меньшей мере одной целевой точки в своей целевой зоне выживания. Если упрощённо посчитать вероятность выживания р для IID (уникального идентификатора) для всех участвующих точек, то вероятность выживания по крайней мере одного хэша в опорной точке равна р*[1-(1-р)F]. Для достаточно больших значений F, например, F>10, и разумных значений р, например, р>0.1, получаем примерно

p ≈ p*[1-(1-p)F]

так что мы на самом деле не сильно проигрываем тому, что было до этого.

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

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

2.3 Поиск и подсчёт

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

После того, как все хэши кусочка были использованы для поиска в базе данных, чтобы сформировать совпадающие временнЫе пары, коробочки проверяются на наличие совпадений. Внутри каждой коробочки такой набор временнЫх пар представляет график рассеяния, связанный с этим кусочком и звуковыми файлами базы данных. Если эти файлы совпадают, соответствующие характерные моменты должны находиться в аналогичных относительных смещениях от начала файла, то есть последовательность хэшей в таком файле должна также встречаться и в совпадающем файле с такой же последовательностью относительного времени. Проблема принятия решения о том, было  ли найдено совпадение, сводится к выявлению значительного скопления точек, образующих диагональную линию в пределах графика рассеяния. Для выполнения обнаружения могут быть использованы разные методы, например, преобразование Хафа (Hough transform) или другие надёжные регрессионные методы. Такие методы являются слишком общими, требующими больших вычислительных ресурсов и восприимчивыми к выбросам.

Из-за жёстких ограничений задачи, следующая методика решает эту проблему примерно за время N*log(N), где N - число точек, появляющихся на диаграмме рассеяния. Для целей этого обсуждения можно считать, что наклон диагональной линии имеет 1.0. Тогда соответствующие моменты времени совпадающих характерных моментов между совпадающими файлами находятся в отношении

tk’=tk+offset,

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

δtk=tk’-tk.

Затем вычисляем гистограмму этих значений δtk и сканируем на пик. Это может быть сделано сортировкой множества значений δtk и быстрым сканированием кластера значений. Диаграммы рассеяния обычно очень редкие из-за специфики хэшей, использующих комбинаторный метод генерации, как говорилось выше. Так как количество пар времени в каждой коробочке мало, процесс сканирования занимает порядка нескольких микросекунд на коробочку или меньше. Число баллов совпадения представляет собой количество совпадающих точек на пике гистограммы. Наличие статистически значимого кластера указывает соответствие. Рисунок 2A показывает рассеяние в базе данных времени при сравнении со временем кусочка для трека, который не соответствует этому кусочку. Есть несколько случайных совпадений, но линейное соответствие не появляется. Рисунок 3A показывает случай, когда на диагональной линии появляется значительное число совпадающих пар времени. Рисунки 2B и 3B показывают гистограммы значений δtk, соответствующих Рисункам 2A и 3A.

Рис. 2A Рассеяние положений совпадающих хэшей: Диагонали нет

Рис. 2B Гистограмма разницы смещений во времени: сигналы совпадают

Рис. 3A Рассеяние положений совпадающих хэшей: Диагональ присутствует

Рис. 3B Гистограмма разницы смещений во времени: сигналы совпадают

Этот процесс сканирования коробочек повторяется для каждого трека в базе данных пока не найдено значительное совпадение.

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

2.3.1 Значимость

Как описано выше, оценка - просто количество совпадающих и выровненных во времени маркеров хэша. Распределение баллов неправильно совпадающих треков представляет интерес в определении доли ложных срабатываний, а также долю корректного распознавания. Коротко говоря, собирается гистограмма оценок неправильно совпадающих треков. Учитывается количество треков в базе данных и создаётся функция плотности вероятности наивысших оценок неправильно сопоставленных треков. Затем выбирается приемлемая вероятность ложных срабатываний (например, 0.1% ложных срабатываний или 0.01%, в зависимости от приложения), затем выбирается порог баллов, соответствующий или превосходящий критерий ложного срабатывания.