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

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

Таким образом, при применении данного алгоритма для вычисления дискретного преобразования Фурье последовательности из N точек требуется выполнить операций сложений и самое большее умножений. Для сравнения напомним, что при использовании обычной формулы дискретного преобразования Фурье необходимо выполнить арифметических операций. Применение быстрого преобразования Фурье при позволяет сократить объем вычислений более чем в 100 раз. [10]

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

а) деление исходного сигнала из n отсчётов на m равных малых групп;

б) вычисление дискретного преобразования Фурье для каждой из групп, причём в целях оптимизации проводится вычисление только первых отсчётов ввиду симметричности спектра вещественного сигнала;

в) визуализация всех m спектров одновременно (пример спектрограммы показан на рисунке 4: светлым точкам соответствуют малые значения модулей коэффициентов Фурье, а тёмным – большие).

Рисунок 4 – Спектрограмма звукового сигнала

Число отсчётов в группе определяет ширину спектрограммы в пикселях, а число групп – её длину. Очевидно, что при меньшем числе отсчётов в группе будет меньше число отсчётов в каждом спектре-столбце, а самих групп (или столбцов) станет больше.

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

Спектрограммы, кроме более информативного визуального представления звука, позволяют контролировать процесс записи звука, используются в светомузыке, а также для выделения шума в сигнале и распознавания речи [11].

На следующем шаге в каждом спектр-столбце мы ищем значение частоты с наибольшим модулем коэффициента Фурье, и устраняем амплитудную компоненту (рисунок 5). Таким образом, сложная спектрограмма, такая, как показанная на рисунке 4, может быть уменьшена до редкого набора координат.

Рисунок 5 – “Карта созвездия”

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

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

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

3 Разработка программного средства

Основная цель программного средства – про­анализировать короткий звуковой образец и определить фрагментом какого аудиофайла в базе данных он является. Задачи, решаемые программным средством:

а) анализ аудиофайлов для составления базы данных “отпечатков”;

б) анализ звукового образца для составления “отпечатка” и выявление соответствий в базе;

в) настройка параметров для выполнения анализа.

3.1 Режимы работы программы

При запуске, программа предложит выбрать один из режимов работы:

Settings – показывает текущие настройки и позволяет их изменить;

Create base – режим создания базы данных «отпечатков» с максимальной частотой дискретизации, указанной в настройках;

Change the sampling frequency – данный режим позволяет изменить частоту дискретизации базы данных;

Recognition – режим анализа и распознавания звукового образца.

3.2 Режим Settings

Включает в себя настройки которые хранятся в файле “settings.txt”:

Music_base_dir – имя каталога музыкальной базы данных;

Full_base_dir – имя каталога базы данных с максимальной частотой дискретизации;

Max_freq – максимальная частота дискретизации (по умолчанию 1000 Гц);

Imp_base_dir – имя каталога отпечатков с текущей частотой дискретизации;

Curr_freq – текущая частота дискретизации (по умолчанию 1000 Гц).

3.3 Режим Create base

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

3.4 Режим Change the sampling frequency

На основании базы Full_base_dir строит базу в папке Imp_base_dir c с выбранной пользователем частотой дискретизации меньше Max_freq. Файл базы Full_base_dir делится на группы по значений частот и амплитуд. В каждой группе частота с наибольшей амплитудой записывается в файл базы Imp_base_dir. Данный режим позволяет быстро сменить частоты дискретизации без необходимости воспроизведения аудиофайлов.

3.5 Режим Recognition

Режим распознавания пользователю выбрать звуковой файл, время начала распознавания отрывка, а также его длительность. Выбранный отрывок подвергается анализу с частотой дискретизации Curr_freq. И далее сравнивается на совпадение с базой Imp_base_dir. На экран выводится следующий результат: имя аудиофайла, частью которого является звуковой образец, процент совпадения частот и время распознавания.

3.6 Результаты предварительных тестов

Для выбора оптимальных параметров распознавания, таких как частота дискретизации и длинна звукового образца, создадим тестовую выборку из различных аудиофайлов. В выборке будут присутствовать образцы как входящие в базу данных программы, так и не принадлежащие ей. Тесты будут проводится для образцов длинной 2/5/10 секунд с частотой дискретизации 1000/500/100/50/10 Гц.

По результатам тестов, в качестве оптимальных параметров распознавания для данной базы звуковых файлов выбраны звуковые образцы длиной 5 секунд и с частотой дискретизации 50 Гц. Выбор обусловлен тем, что при частоте 10 Гц было выявлено значительное количество ложных распознаваний, в то время как при частоте 50 Гц небольшая доля ложных распознаваний была выявлена только на образцах длиной 2 секунды. В таблице 1 указано среднее время распознавания для тестовых параметров.

Таблица 1 – Среднее время распознавания, мс

Частота дискретизации, Гц	Длина образца
	2 с	5 с	10 с
10	28	33	36
50	129	153	219
100	285	408	734
500	2381	5276	7166
1000	12542	18679	45903

Программа работает достаточно быстро относительно небольших баз данных (порядка нескольких тысяч “отпечатков”) и занимают мало места для хранения, что полезно рекламодателям, которые могут отслеживать реальные выходы своих рекламных роликов.

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

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

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

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

Рисунок 6 – Генерация комбинаторного хэша

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

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

Рисунок 7 – Детали хэша

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

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

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