2. КОНЦЕПЦИИ ДАКТИЛОСКОПИРОВАНИЯ ЗВУКА

2.1 Определение звукового отпечатка

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

Здесь можно провести аналогию с так называемыми хэш-функциями (в дактилоскопической литературе иногда также называется как устойчивое или перцептуальное хэширование [5]), которые хорошо известны в криптографии. Криптографическая хэш-функции H связана с (обычно большим) объектом X с (обычно небольшим) хэш-значением (так называемый дайджест сообщения). Криптографическая хэш-функция позволяет сравнение двух крупных объектов X и Y, простым сравнением их соответствующих хэш-значений H(X) и H(Y). Строгое математическое равенство последней пары подразумевает равенство первой лишь с очень малой вероятностью ошибки. Для правильно разработанной криптографической хэш-функции эта вероятность равна 2-N, где n равно числу бит в этом хэш-значении. При использовании криптографических хэш-функций существует эффективный метод, чтобы проверить, содержится или нет элемент данных X в заданном и большом наборе данных Y={Yi}. Вместо хранения и сравнения со всеми данными в Y, достаточно сохранить набор хэш-значений {hi = H(Yi)}, и сравнить H(X) с таким набором хэш-значений.

Сначала можно подумать, что криптографические хэш-функции являются хорошим кандидатом для функций отпечатков. Однако, вспомните из введения, что вместо строгого математического равенства мы заинтересованы в сходстве восприятия. Например, оригинальная версия с качеством компакт-диск 'Rolling Stones - Angie' и звук MP3 версии на 128 Кб/сек в человеческой слуховой системе одинаковы, но форма их сигналов может быть совершенно разной. Хотя две версии воспринимаются одинаково, математически они совершенно отличны. Поэтому криптографические хэш-функции не могут принимать решение о воспринимаемом равенстве этих двух версий. Ещё хуже, криптографические хэш-функции, как правило, чувствительны к битам: разница в один бит в оригинальном объекте приводит к совершенно другому значению хэша.

Другой законный вопрос, который может задать читатель: "Разве невозможно разработать функцию дактилоскопирования, которая создаёт математически равные отпечатки для объектов, воспринимаемых одинаково"? Вопрос правильный, но ответ в том, что такое моделирование сходства восприятия принципиально не представляется возможным. Чтобы быть более точными: известный факт, что сходство восприятия не является транзитивным. Воспринимаемое сходство пары объектов X и Y и другой пары объектов Y и Z не обязательно подразумевает сходство восприятия объектов X и Z. Однако, моделирование сходства восприятия путём математического равенства отпечатков могло бы привести к таким отношениям.

Учитывая приведённые выше аргументы, мы предлагаем построить функцию дактилоскопирования таким образом, чтобы воспринимаемые одинаково звуковые объекты приводили к одинаковым отпечаткам. Кроме того, для того, чтобы быть в состоянии различать различные звуковые объекты, должна быть очень высокая вероятность того, что непохожие звуковые объекты создают непохожие отпечатки. Подробнее математически, для правильно разработанной функции дактилоскопирования F должен быть такой порог T, чтобы с очень высокой вероятностью ||F(X)-F(Y)||≤Т, если объекты X и Y являются похожими, и ||F(X)-F(Y)||>Т, когда они непохожи.

2.2 Параметры системы дактилоскопирования звука

Имея соответствующее определения аудио отпечатка, сосредоточимся теперь на различных параметрах системы дактилоскопирования звука. Основными параметрами являются:

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

•Достоверность: как часто песня идентифицируется неправильно? Например "Rolling Stones - Angie" идентифицируется как "Beatles - Yesterday". Частота, с которой это происходит, обычно называется частотой ложных срабатываний.
 

•Размер отпечатка: сколько памяти необходимо для отпечатка? Чтобы сделать возможным быстрый поиск, отпечатки обычно хранятся в оперативной памяти. Поэтому размер отпечатка, обычно выражаемый в битах в секунду или битах на песню, в значительной степени определяет ресурсы памяти, которые необходимы для сервера базы данных отпечатков.
 

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

•Скорость поиска и масштабируемость: Сколько необходимо времени, чтобы найти отпечаток в базе данных отпечатков? Что делать, если база данных содержит тысячи и тысячи песен? Для коммерческого развёртывания систем дактилоскопирования звука скорость поиска и масштабируемость является ключевым параметром. Скорость поиска должна быть порядка миллисекунд для базы данных, содержащей более 100,000 песен, используя лишь ограниченные вычислительные ресурсы (например, несколько ПК высокого класса).

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