Лесных (1219169), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

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

Для достаточно больших значений F, например, F>10, и разумных значений , например, , получаем примерно

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

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

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

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

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

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

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

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

Р исунок 7 – Рассеяние положений совпадающих хэшей: Диагонали нет

Рисунок 8 – Гистограмма разницы смещений во времени: сигналы совпадают

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

Р исунок 10 – Гистограмма разницы смещений во времени: сигналы совпадают

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

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

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

Алгоритм хорошо работает при значительных уровнях шума и даже нелинейных искажениях. Он может правильно определить музыку в присутствии голоса, шума транспорта, выпадениях и даже другой музыки. Чтобы дать представление о силе этой техники, из сильно повреждённого 15-ти секундного сэмпла статистически значимое совпадение может быть определено с помощью выживших на самом деле только лишь около 1-2% порождённых хэш-маркеров и способствующих созданию смещения кластера. Свойство метода гистограммирования рассеяния в том, что разрывы не имеют значения, что позволяет иметь невосприимчивость к выпадениям и маскировке из-за помех. Один несколько неожиданный результат состоит в том, что даже с большой базой данных мы можем правильно определить каждый из нескольких смешанных вместе треков, в том числе нескольких версий одного и того же фрагмента, свойство, которое мы называем "прозрачность".

На рисунке 11 показан результат выполнения распознавания 250 сэмплов различной длительности и разным уровнем шума с помощью тестовой базы данных из 10000 треков, содержащей популярную музыку. Сэмпл шума был записан в шумном пабе для имитации условий "реальной жизни". Отрывки звука длительностью 15, 10 и 5 секунд были взяты из середины каждого тестового трека, каждый из которых был взят из тестовой базы данных. Относительная мощность шума каждого тестового кусочка была нормирована до требуемого отношения сигнал/шум, а затем линейно добавлена к сэмплу. Видно, что скорость распознавания падает до 50% для 15, 10 и 5 секундных сэмплов при отношении сигнал/шум примерно -9, -6 и -3 дБ, соответственно. Рисунок 12 показывает тот же анализ, за исключением того, что результирующая смесь музыка + шум далее подвергнута сжатию GSM 6.10, а затем снова сконвертирована в звук с PCM. В этом случае 50% уровень скорости распознавания для 15, 10 и 5 секундных сэмплов имеет место примерно при отношении сигнал/шум -3, 0 и +4 дБ. Выборка звука и обработка проводились с использованием сэмплов 8 кГц, моно, 16-бит.

Рисунок 11– Скорость распознавания - добавлен шум

Рисунок 12 – Скорость распознавания - добавлен шум + GSM компрессия

Для базы данных имеющей около 20 тысяч треков, реализованной на ПК, время поиска имеет порядок 5 - 500 миллисекунд, в зависимости от параметров настройки и приложения. Служба может найти соответствующий трек для сильно повреждённых звуковых сэмплов в течение нескольких сотен миллисекунд основного времени поиска. Для звука с "качеством радио" можно найти совпадение менее чем за 10 миллисекунд [12].

Характеристики

Список файлов ВКР