Система сжатия звукового сигнала

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Алгоритм сжатия сегмента сигнала

1.1 Дискретное вэйвлет-преобразование

1.2 Дискретное преобразование Фурье

1.3 Преобразование и оценка коэффициентов

1.4 Кодирование с предсказыванием по частичному совпадению

1.5 Стерео соединение

1.6 Битовые потоки

1.7 Общая схема

1.8 Устранение помех на границах сегментов

2. Деление сигнала на сегменты

2.1 Статическая реализация

2.2 Адаптивная реализация

2.3 Динамическая реализация

3. Программная реализация и вычислительный эксперимент

3.1 Программная реализация

3.2 Вычислительный эксперимент

Заключение

Список литературы

Приложение. Введение в вэйвлет-анализ

Введение

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

· MP3 (MPEG-1 layer 3);

· Ogg Vorbis;

· WMA (Windows Media);

· RealAudio.

Безусловно, MP3 сейчас является самым распространённым форматом сжатия аудио. Но вовсе не потому, что он - лучший по качеству звучания или компрессии. Просто исторически сложилось так, что он появился на рынке намного раньше других форматов. Еще одна весомая причина - это инертность производителей разнообразной мультимедийной техники, не желающих вводить новые аудиоформаты. Если судить по проведенным тестам независимых исследователей, то выявляется другой лидер - Ogg Vorbis [1,2]. Мы исследовали этот формат кодирования, и учли тенденции его развития при постановке задачи.

И MP3 и Vorbis основаны на разбиении сигнала на сегменты и применении к каждому сегменту дискретного преобразования Фурье с использованием психоаккустического фильтра и алгоритмов кодирования (Huffman, VQ), но отличаются реализацией. В перспективе развития разработчики кодека Ogg Vorbis планируют привлечь вэйвлет-технологию сжатия цифровых аудиоданных.

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

Для сжатия звука, можно использовать следующие методы или их комбинации.

1) Трешолдинг - отбрасывание близких к нулю коэффициентов в разложении сигнала.

2) Округление коэффициентов. Естественно, за сжатие надо aплатитьu потерей качества, которая возникает из-за округления. Желательно, чтобы восстановленный сигнал как можно меньше отличался от исходного. Поэтому, одной из главных задач становится оценка значимости того или иного коэффициента в разложении относительно остальных и, соответственно, определение точности его хранения.

3) Подбор преобразования, обеспечивающего наименьший суммарный объем хранимого числа разрядов.

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

Таким образом, в данной работе рассмотрен способ сжатия сигнала, основанный на различных вариантах дискретного вэйвлет-преобразования (Discrete Wavelet Transform, DWT), а также дискретного преобразования Фурье (Discrete Fourier Transform, DFT), оценке разрядности коэффициентов, PPM-кодировании, битовой упаковке и динамическом программировании.

1. Алгоритм сжатия сегмента сигнала

Рассмотрим процедуру сжатия одного сегмента сигнала. В зависимости от количества каналов в исходном звуковом файле, на вход подается один (моно) или два (стерео) массива чисел длины N. Эти числа будем называть сэмплами (от англ. sample). На выходе, после обработки, мы получаем Nb байтов закодированного сигнала. Сама же обработка массивов состоит из последовательности шагов, каждый из которых рассмотрим отдельно.

сигнал стерео битовой вэйвлет

1.1 Дискретное вэйвлет-преобразование

Для понимания техники вэйвлет-разложения введем некоторые понятия. С более подробным изложением основных понятий вэйвлет-анализа можно ознакомиться в приложении или в [7]. Рассмотрим две функции f и y из L2(R), удовлетворяющие некоторым свойствам, описанным в приложении, где f - масштабирующая функция, а y - вэйвлет. Каждую функцию f из L2(R) можно приблизить функциями {f (2 p - k ) : k О Z} с любой наперед заданной точностью, выбрав достаточно большое значение

p: f ( x) = е

kОZ

A pf (2 px - k ) .

Коэффициенты {A p} называются аппроксимирующими коэффициентами.

Будем называть функции f (2 p -1 x - k ) , соответствующие фиксированному p функциями p-го уровня.

Функции f и y обладают таким свойством, что масштабирующие функции р-го уровня выражаются через масштабирующие функции и вэйвлет-функции р-1-го уровня и наоборот:

f (2 p x - l ) = е[a

f (2 p -1 x - k ) + b

y (2 p -1 x - k )] , l, p О Z,

f (2 p -1 xl -2 k- l ) = е

pk + 2 l

l -2 k

f (2 p x -k ) , l, p О Z,

y (2 p -1 x- l )= е q

k + 2ly (2 x- k ) , l, p О Z,

где последовательности {ak} и {bk} называются последовательностями разложения, а {pk} и {qk} - последовательности восстановления.

Следовательно, используя (1.1.2) мы можем переписать (1.1.1) как

= е pp - = е

p -1

p -1 -+ е p -1

p -1 -

f p ( x)

kОZ

Ak f (2 x k )

Ak

kОZ

f (2x k )

Dk

kОZ

y (2x k ) .

p -1

k

= е al - k Al ,

п l

н p -1 p

пDk

= еbl - k Al ,

м A p -1 = A p -1 ,

п k 2 k

пD p -1 = D p -1 ,

2 k

где коэффициенты {D p -1} называются детализирующими коэффициентами. Отметим, что коэффициенты Ap-1 и коэффициенты Dp-1 можно получить из коэффициентов Ap, используя (1.1.5) и (1.1.6), причем применение (1.1.6) называется сгущающей выборкой, то есть, применив (1.1.5), мы оставляем лишь те коэффициенты, которые имеют четный индекс. Продолжая этот процесс, получаем следующую схему расчетов коэффициентов:



В итоге мы получили вэйвлет-разложение, то есть набор последовательностей коэффициентов Dp-1, Dp-2, …, Dp-q, Ap-q.

Используя обратные соотношения между функциями f и y (1.1.3) и (1.1.4) мы можем построить обратный процесс:

Условимся называть аппроксимирующие и детализирующие коэффициенты Aj и Dj коэффициентами j-го уровня. Следуя теории вэйвлетов, для вэйвлет-разложения, сначала необходимо аппроксимировать сигнал с требуемой точностью на верхнем уровне. Пусть этот уровень имеет индекс 0. Предположим, нам дано N сэмплов, и необходимо получить N аппроксимирующих коэффициентов для дальнейшего разложения по алгоритму, описанному выше. Аппроксимировав сигнал на нулевом уровне, мы получим аппроксимирующие сигнал коэффициенты нулевого уровня {A0 }. Предположим для простоты, что N = 2q, qОN. В соответствии с алгоритмом разложения, описанным выше, получаем A-1 и D-1. Заметим, что в алгоритме используется сгущающая выборка (берутся коэффициенты с четными номерами), поэтому в массивах A-1 и D-1 содержится по N/2 элементов. Аналогично, массивы A-2 и D-2 будут содержать по N/4 элементов. На последнем шаге A-q и D-q содержат по одному элементу. Таким образом, мы получили вэйвлет-разложение A-q, D-q, D-q+1, …, D-2, D-1, в котором по-прежнему N элементов (1+1+2+4+8+…+2q-1 = 2q = N).

Заметим, что последовательности разложения {ak} и {bk} могут иметь более двух элементов, и в процессе вычисления коэффициентов нижестоящего уровня соответственно (1.1.5) и (1.1.6) они могут aвыходитьu за пределы массива A-j j = 0, 1, …, q-1 (рис 1.1):

Рис. 1.1. Алгоритм разложения.

Один из способов разрешения ситуации - это замыкание массива A- j в кольцо. Для этого достаточно взять остаток от деления индекса на длину массива. Так, для получения последнего элемента массива A- j -1 будут использованы два последних и два первых элемента массива A- j . Этот метод позволяет взаимно-однозначно преобразовывать j = 0, 1, …, j-1. A- j в A- j -1 и D- j -1 , и обратно, Мы рассмотрели тот случай, когда N = 2q. Если же N нечетное, то на первом же шаге у нас не будет взаимно-однозначного соответствия между A0 , где N элементов и ( A-1 , D-1 ) где N-1 элемент. Решение следующее: Если на каком-то шаге j массив A- j имеет нечетное число элементов, то расширим массив путем добавления в конец одного элемента с произвольным значением, например, равным значению последнего элемента A- j для обеспечения непрерывного расширения. Здесь возникает избыточность информации, но она минимальна, так как число дополнительных коэффициентов не превышает log2(N).

Отметим также, что трудоемкость алгоритмов вэйвлет-разложения и вэйвлет-восстановления равна O(N). Даже по сравнению с быстрым преобразованием Фурье (БПФ), трудоемкость которого равна O(Nlog2N), описанный алгоритм работает значительно быстрее.

1.2 Дискретное преобразование Фурье

Определение 1.1. Дана конечная последовательность x0, x1, x2, ..., xN-1 комплексных чисел. Дискретное преобразование Фурье (ДПФ) заключается в поиске последовательности X0, X1, X2, ..., XN-1, элементы которой вычисляются по формуле:

Определение 1.2. Дана конечная последовательность X0, X1, X2, ..., XN-1 комплексных чисел. Обратное дискретное преобразование Фурье заключается в поиске последовательности x0, x1, x2, ..., xN-1, элементы которой вычисляются по формуле:

При помощи дискретного преобразования Фурье можно получить спектр сигнала, то есть коэффициенты при синусах и косинусах в разложении Фурье. Основным свойством преобразования Фурье (см., например, [7]) является обратимость, то есть если из последовательности {xk} при прямом преобразовании получается последовательность {Xk}, то при обратном преобразовании из {Xk} получится исходная последовательность {xk}.

Отметим, что данное преобразование имеет трудоемкость O(N2) для набора чисел длины N, однако его можно оптимизировать так, что трудоемкость составит M22T + NT, где N = M2T (см. [8]).

1.3 Преобразование и оценка коэффициентов

Пусть мы имеем массив коэффициентов {ck}, k = 0, 1, …, N-1, и этот массив нормализован, в том смысле, что |ck| < 2, k = 0, 1, …, N-1. Преобразуем этот массив в два новых массива {ek} и {mk} так, что - ek +ck = mk Ч 2 , где mk О [1,2), ek О Z, k = 0, 1, …, N-1.Заметим, что на ЭВМ стандартное представление числа с плавающей точкой в виде мантиссы и экспоненты, аналогично (1.3.1) с той лишь разницей, что в (1.3.1) экспонента берется со знаком `-`.Теперь нам нужно оценить точность хранения коэффициентов. Отметим во-первых, что коэффициенты с большим значением ek можно отбросить, как близкие к нулю. Во-вторых, при огрублении массива экспонент {ek} на n бит мы можем получить ошибку, равную ck2n. Ясно, что при больших ck, мы получаем неприемлемую ошибку, то есть массив экспонент необходимо хранить точно. А вот при округлении мантиссы mk на n бит мы получаем ошибку

2n - (e k + l ) , где l - это исходная разрядность мантиссы.

Будем оценивать разрядность хранения каждого элемента mk во-первых, в зависимости от совокупности значений {ek}, и во-вторых, от порядкового номера k в массиве. Поясним это на примере:

BitCount(k ) := [K Ч exp{P Ч emin - Q Ч ek } Ч F(k )] , где emin

0 Ј k Ј N -1

Здесь функция BitCount(k) определяет разрядность хранения мантиссы mk. Параметр K задает верхнюю границу разрядности хранения (например K = 16), а функции exp и F, могут уменьшить разрядность, т.к. 0ЈPЈQ, 0ЈF(k)Ј1, где P и Q - константы.

Отметим некоторые моменты. Чем больше максимальный коэффициент, тем меньше у него emin, следовательно, тем меньше бит для хранения будет выделено для остальных коэффициентов. Это отражает тот факт, что на фоне доминирующей частоты, остальные частоты менее слышны, нежели в ее отсутствие. Функция F отражает зависимость разрядности коэффициента от его положения в разложении, например, если рассматриваемые коэффициенты - это спектр разложения Фурье, то мы можем применить частотную фильтрацию. Допустим, если мы a priori знаем, что исходный сигнал содержит только низкие частоты, а остальные не важны или являются помехами, то положив мы зададим тем самым низкочастотный фильтр (low-pass filter), то есть фильтр, пропускающий только низкочастотную составляющую сигнала, это позволит существенно сократить объем выходных данных. Отметим, что описанная оценка разрядности называется психоакустическим фильтром.

1.4 Кодирование с предсказыванием по частичному совпадению

В ходе экспериментов было выявлено, что для обоих используемых преобразований (DWT, DFT) величины {ek} имеют стабильное распределение, близкое к нормальному. Это натолкнуло на мысль использовать какой-либо вероятностный метод кодирования. Мы провели анализ методов кодирования и выбрали контекстный метод, основанный на предсказывании по частичному совпадению (Prediction by Partial Matching, PPM), который является надстройкой над методом арифметического кодирования. Описание арифметического кодирования можно найти в [9]. Описание PPM можно найти в [10].

1.5 Стерео соединение

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

Итак, пусть мы имеем два массива коэффициентов { cl } и { cr }, k = 0, 1,k k…, N-1. Преобразуем каждую пару ( cl ,cr ) в другую пару (ck, ak) при помощи полярного преобразования координат. Далее, применим рассмотренную в пункте 1.3 схему для преобразования коэффициентов ck. А для ak применим следующий прием: мы масштабируем интервал изменения ak к интервалу [1,2), и теперь ak в записи (mk, ek) имеет значение (ak, 0), где 0 нам вовсе не обязательно хранить. То есть в итоге мы получили три массива величин - {ek}, {mk} и {ak} - это массив экспонент, массив мантисс и массив фаз.

1.6 Битовые потоки

ЭВМ позволяет эффективно манипулировать данными разрядности 8, 16, 32 бита, но этот формат невыгоден для хранения коэффициентов разложения, так как у нас появляются не используемые разряды. Например, если функция оценки разрядности коэффициента mk выдает значение 10, то записывая этот коэффициент в 16-разрядную ячейку, мы не используем оставшиеся 6 разрядов. Проблема решается путем введения битовых потоков, в которых числа разной разрядности хранятся aбез зазоровu. Это достигается при помощи арифметических сдвигов и логических операций.

1.7 Общая схема

Итак, рассмотрев по отдельности все шаги, поясним общую схему алгоритма сжатия сегмента звукового сигнала.

· На вход процедуры сжатия подается два массива {xl } и {xr }, k = 0,k k1, …, N-1 (рассмотрим случай со стерео сигналом).

· Применяем к каждому из массивов выбранное нами преобразование (будь то DWT или DFT) и получаем массивы коэффициентов {cl } и {cr } .k k

· Применяем стерео соединение коэффициентов получаем три массива {ek}, {mk} и {ak}.{cl } и {cr }

· Оцениваем разрядность хранения величин {mk} и {ak}, используя массив экспонент {ek} (см. пункт 1.3).

· Выполняем PPM-кодирование массива {ek}.

· Выполняем битовую упаковку массивов {mk} и {ak} с нужным числом разрядов.

В результате получается блок, состоящий из 3-х подблоков.



Алгоритм восстановления сигнала симметричен алгоритму сжатия, но с использованием обратных преобразований.

1.8 Устранение помех на границах сегментов

Так как в качестве базиса, как правило, берутся непрерывные функции, то, несмотря на округление коэффициентов, при восстановлении сегмента мы получаем непрерывную функцию. Но между сегментами может возникнуть aскачекu, т.к. в конце текущего сегмента восстановленный сигнал является суперпозицией одних компонент, а в начале следующего сегмента - суперпозицией других компонент. Под компонентами здесь понимаются базисные функции, умноженные на соответствующие коэффициенты разложения. И если значения сигнала на стыке двух сегментов совпадали до округления, то после округления они могут не совпадать. Таким образом, непрерывность исходного сигнала может быть утеряна.

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

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

w( x) О C[0,1] , такую, что w(0) = 0, w(1) = 1.

Пусть область перекрывания на временной оси - есть интервал [a, b]. Будем умножать амплитуду сигнала текущего сегмента в области перекрывания на чего, эти амплитуды складываются. Этот процесс называется кроссфэйдингом (crossfading).

Рис. 1.2. Кроссфэйдинг в области перекрывания сегментов.

На рисунке 1.2 изображен восстановленный сигнал, который был сжат с использованием метода перекрывания сегментов; сигнал представляет собой синусоидальную волну, а в качестве w(x) взята линейная функция. Таким образом, возможный разрыв устраняется, так как сигнал сегмента теперь представляет собой непрерывную функцию на временной оси, а восстановленный сигнал является композицией сигналов сегментов.

2. Деление сигнала на сегменты

2.1 Статическая реализация

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

2.2 Адаптивная реализация

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

2.3 Динамическая реализация

Третий способ заключается в подборе такого разбиения, которое минимизирует суммарное количество байтов закодированного сигнала, то есть предоставление программе возможности aадаптироватьсяu к структуре сигнала. Это возможно в случае, если преобразование aчувствительноu к разбиению сигнала на сегменты. Поясним это свойство на примере.



Рис. 2.1. Разбиение на сегменты.

На рисунке 2.1 изображена часть сигнала, разбитая на сегменты. Отметим, что для преобразования Фурье этот вариант разбиения будет самым эффективным среди всех возможных с точки зрения сжатия, так как сегмент C будет иметь всего один ненулевой коэффициент разложения, в A и E будут нули, и лишь сегментах B и D будут присутствовать разные составляющие спектра. Чтобы определить наиболее эффективное с точки зрения сжатия разбиение, можно использовать динамическое программирование.

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

Введем некоторые обозначения:

h - длина минимально возможного сегмента.

n - количество шагов в сегменте максимальной возможной длины. Таким образом, мы получили равномерную сетку на сигнале с шагом h:

Введем понятие пути Pk из x0 в xk:

где M = |Pk| - 1 - число сегментов в пути Pk. Обратим внимание на то, что в определении пути присутствуют три свойства: длина каждого сегмента (pj-1, pj) пути Pk кратна шагу h, не равна нулю и не превышает длины максимально возможного сегмента nh.

Пусть вес сегмента (хi, xj) - это количество байт после сжатия сегмента сигнала, ограниченного этими точками, обозначим вес сегмента за d(хi, xj).

Тогда вес пути Pk равен сумме весов всех его сегментов:

Путь Pm из x0 в конечную точку xm можно интерпретировать как разбиение исходного сигнала. Отметим, что путь из x0 в xm минимального веса и будет искомым разбиением. Итак, можно ввести эквивалентную задачу на следующем графе:

Рис. 2.2. Граф состояний.

На рисунке 2.2 изображен граф состояний, соответствующий конкретной задаче сжатия, в которой число шагов m = 10, количество шагов в максимально возможном сегменте n = 4.

Каждая вершина графа (xk, t) характеризует множество путей из x0 в xk, которые состоят из t сегментов. Вес любого ребра

 в графе определим как вес сегмента

Нам необходимо найти путь минимального веса до любой из вершин (x10, t). Можно ввести фиктивные ребра, вес которых равен нулю (изображены пунктиром) до фиктивной вершины T, тогда задача сводится к нахождению пути минимального веса на графе (рис. 2.2) из S в T.

Вес ребер не зависит от числа сегментов t, и, по сути, нам не важно, сколько сегментов в пути, а важен его вес, поэтому все состояния, соответствующие фиксированному xk и разным t можно считать тождественными, таким образом, можно рассматривать проекцию графа (рис. 2.2) на ось x:

Рис. 2.3. Проекция графа состояний на ось x.

Задача сводится к нахождению пути минимального веса на графе (рис. 2.3) из x0 в xm. Будем решать задачу методом динамического программирования. Разобьем задачу на этапы. На k-м этапе необходимо найти путь минимального веса из x0 в xk, обозначим его через P k * , при условии, что P k -1* уже найдены. Запишем уравнение Бэллмана:



На k-м этапе у нас имеется n управлений, где i-е управление отвечает за выбор пути

Выбор оптимального управления осуществляется очевидным образом, в соответствии с уравнением Бэллмана, то есть i = arg min{d ( Pj =1,...,nk-j*) d ( xk-j ,xk )} .

Для определения величин d(xk-j, xk), где j = 1, 2, …, n, нам необходимо провести сжатие n сегментов (xk-1, xk), (xk-2, xk), …, (xk-n, xk).

Заметим, что на каждом шаге алгоритма Дейкстры при добавлении вершны xk мы также должны сжать n сегментов (xk, xk+1), (xk, xk+2), …, (xk, xk+n).

Следовательно, так как количество шагов алгоритма Дейкстры и описанного алгоритма равно m, то трудоемкости этих алгоритмов совпадают. Но описанный алгоритм более удобен в реализации, так как в алгоритме Дейкстры вершины могут добавляться непоследовательно.

Сделаем несколько замечаний относительно реализации описанного алгоритма динамического программирования:

1. При сжатии сегментов, на каждом шаге формируются n блоков, содержащих сжатые сегменты сигнала, из которых выбирается один, а остальные удаляются.

2. В пути, фактически, не содержится точек разбиения, а содержится несколько таких блоков, связанных указателями, и мы храним только указатели на последние блоки путей.

3. При формировании нового пути, нам не нужно копировать все блоки из k-j-го пути, нам достаточно установить указатель i-го блока, на последний блок k-j-го пути, а указатель k-го пути на j-й блок.

4. На k-м шаге нам уже не нужны пути P0* ,P1* , …,P k - n -1* , и после k-го шага, путь P k - n* уже не понадобится. Удалим те его блоки, на которые нет ссылок из других путей. Следовательно, на k-м шаге можно хранить только указатели на последние блоки последних n путей.

5. На каждом шаге блоки со ссылками образуют дерево и являются его узлами.

3. Программная реализация и вычислительный эксперимент

3.1 Программная реализация

В ходе решения поставленной задачи, были разработаны две библиотеки на C++.

· WaveLib - библиотека, позволяющая работать с файлами формата WAV. Реализована загрузка, сохранение, проигрывание, отображение контура волны и навигация.

· ComprLib - библиотека, предоставляющая набор средств для сжатия WAV-файлов, а также позволяющая разрабатывать собственные алгоритмы и совершенствовать имеющиеся, используя наследование и полиморфизм объектно-ориентированного программирования.

Библиотека WaveLib.

Файл “Wave.h”:

CWave - класс обеспечивающий манипуляцию с WAV-файлами.

Файл “Player.h”:

CPlayer - абстрактный класс, характеризующий интерфейс проигрывателя.

Файл “WavePlay.h”:

CWavePlayer(CPlayer) - класс, реализующий проигрывание объектов типа CWave средствами DirectSound 8.0.

Файл “WaveView.h”:

CWaveView(CView) - класс, производный от класса MFC-библиотеки, спроектированный для одновременного отображения нескольких объектов класса CWave, навигации, масштабирования и редактирования.

Файл “PeakData.h”:

CPeakData - вспомогательный класс, который используется в реализации CWaveView, предназначен для быстрого отображения (за логарифмическое время) звуковых файлов большого объема, основан на построении дополнительной информации об объекте класса CWave.

Библиотека ComprLib.

Файл “compression.h”:

CDecomposition - класс, хранящий сжатый сигнал в виде списка блоков, каждый из которых является прообразом сегмента при восстановлении.

CCompressManager - класс, отвечающий за разбиение сигнала на сегменты при сжатии.

CCompressor - абстрактный класс, отвечающий за сжатие и восстановление одного сегмента сигнала.

CBuffCompressor(CCompressor) - абстрактный класс поддерживающий рабочий буфер.

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

CTransformCompressor(CBuffCompressor) - класс, поддерживающий сжатие с помощью преобразования описанного в виде класса, реализующего интерфейс абстрактного класса CTransform, как это описано в пункте 1.7.

CStaticOverlapCompressor(CTransformCompressor) - класс, поддерживающий перекрывание сегментов, описанного в пункте 1.8.

Файл “FourierTransform.h”:

CFourierTransform(CTransform) - класс поддерживающий оптимизированное преобразование Фурье (см. пункт 1.2).

Файл “WaveletTransform.h”:

CWaveletTransform(CTransform) - абстрактный класс, характеризующий вэйвлет-преобразование и оценку разрядности вэйвлет-коэффициентов.

COrthoWaveletTransform(CWaveletTransform) - класс, оптимизированный под ортогональное вэйвлет-разложение.

CEBiorWaveletTransform(CWaveletTransform) - класс, оптимизированный под биортогональное вэйвлет-разложение, учитывающий симметрию последовательностей разложения и восстановления с четным числом элементов.

COBiorWaveletTransform(CWaveletTransform) - класс, оптимизированный под биортогональное вэйвлет-разложение, учитывающий симметрию последовательностей разложения и восстановления с нечетным числом элементов.

Файл “Managers.h”:

CLinearCompressManager(CCompressManager) - класс, обеспечивающий разбиение сигнала на сегменты по методу, описанному в пункте 2.1.

CDynamicCompressManager(CCompressManager) - класс, обеспечивающий разбиение сигнала на сегменты по методу, описанному в пункте 2.3.

Файл “PPMCoder.h”:

CPPMCoder - класс, реализующий PPM-кодирование последовательности целых чисел.

Файл “RangeCoder.h”:

CRangeCoder - класс, реализующий арифметическое кодирование целых чисел.

Файл “bitstream .h”:

bitstream - класс, реализующий битовую упаковку целых чисел.

Как было сказано ранее, библиотека ComprLib допускает расширение за счет

· введения новых преобразований - классов, производных от CTransform

· введения новых компрессоров - классов, производных от CCompressor, CBuffCompressor, CTransformCompressor или CStaticOverlapCompressor

· введение новых классов, отвечающих за разбиение сигнала на егменты (производных от CCompressManager).

Можно также получать разные способы сжатия, комбинируя нововведения с возможностями, предоставляемыми библиотекой, так как любая тройка объектов классов, производных соответственно от CTransformCompressor, CCompressManager и CTransform может быть использована для сжатия объектов класса CWave в объекты класса CDecomposition и восстановления объектов класса CDecomposition до объектов класса CWave.

Разработана программа, которая имеет удобный пользовательский интерфейс, реализованный средствами библиотеки WaveLib, и позволяет сжимать WAV-файлы с помощью библиотеки ComprLib (см. рис. 3.1).

Рис. 3.1. Программа, реализующая интерфейс средствами библиотеки WaveLib.

3.2 Вычислительный эксперимент

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

В первом эксперименте был взят сильно насыщенный сигнал, в том смысле, что в спектре сигнала присутствуют частоты широкого диапазона (часть композиции Inside - Sting (2003) Sacred Love) . В таблице приведены результаты проведенного эксперимента:

Преобразование	Динамическое программирование	Коэффициент сжатия (от исходного объема)
DWT	не использовалось	22.1%
DWT	использовалось	22.0%
DFT	не использовалось	23.7%
DFT	использовалось	21.5%

Во втором эксперименте был взят несильно насыщенный сигнал, в том смысле, что в спектре сигнала присутствует только узкий диапазон частот. (часть композиции Falling - Alicia Keys (2001) Songs in A minor).

Преобразование	Динамическое программирование	Коэффициент сжатия (от исходного объема)
DWT	не использовалось	19.9%
DWT	использовалось	19.8%
DFT	не использовалось	20.7%
DFT	использовалось	18.9%

Как видно из экспериментов, для вэйвлет-разложения динамическое программирование не дает большого выигрыша в объеме и качестве, так как сама структура вэйвлет-преобразования такова, что осцилляции сигнала локализуются независимо от разбиения на сегменты. Разложение Фурье, как это было описано в пункте 2.3, зависит от разбиения сигнала на сегменты; поэтому динамическое программирование дает некоторый выигрыш, как в объеме, так и в качестве звучания.

Укажем некоторые замечания относительно реализации:

· Массив экспонент достаточно хранить с точностью 3-4 бита. Если отводить под элемент массива 4 бита и хранить массив экспонент несжатым, то его объем составляет 17.5% от объема исходного сигнала. Однако PPM-код массива занимает в среднем 8% от объема исходного сигнала. Следовательно, мы добились сжатия массива экспонент aбез потерьu более чем в два раза.

· Заметим, что можно подобрать такие допустимые оценки точности элементов массивов мантисс и фаз, что суммарный объем, занимаемый этими массивами составит 16-17% от исходного. Причем эти массивы хранятся в несжатом виде, а подвергаются лишь битовой упаковке. Если мы допустим, что эти массивы можно сжать каким-либо алгоритмом кодирования в два раза, как и массив экспонент, то сжатый сигнал будет занимать около 15% от исходного объема. Этот результат близок к результатам сжатия лучших кодировщиков на сегодняшний день, таких, как Ogg Vorbis и MPEG Layer-3. Например, если сжать WAV-файл в MP3 с качеством 192kbps, то объем MP3-файла составит 14% от исходного.

Заключение

В данной работе проведен обзор основных концепций вэйвлет-анализа, запрограммированы алгоритмы разложения и восстановления, исследованы особенности вэйвлет-разложений.

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

Разработаны программные библиотеки для манипуляции с WAV-файлами и их сжатия, а также Windows-приложение, реализующее возможности этих библиотек. Достигнутый коэффициент сжатия при допустимой потере качества составляет 20-25% от исходного объема.

Список литературы

1) Нагорный А. Vorbis против всех? Или какой кодек выбрать для сжатия аудио // портал Hardvision, 2010 (http://www.hardvision.ru/?dir=soft&doc=ogg_vorbis).

2) Alexander C., Strauss N., The Ogg Vorbis CODEC project, Xiph.Org., 2003 (http://www.xiph.org/ogg/vorbis/).

3) Hardle W., Kerkyacharian G., Picard D., Tsybakov. A. Wavelets, Approximation, and Statistical Applications (Lecture Notes in Statistics, Vol 129). New York: Springer-Verlag, 1997.

4) Алексеев К.А. Теория и практика шумоподавления в задаче обработки сейсмоакустических сигналов // Обработка сигналов и изображений. Wavelet Toolbox, Консультационный центр Matlab, 2010. ( http://matlab.exponenta.ru/wavelet/book5/index.php).

5) Алексеев К.А. Вейвлеты, аппроксимация и статистические приложения // Обработка сигналов и изображений. Wavelet Toolbox, Консультационный центр Matlab, 2010. (http://matlab.exponenta.ru/wavelet/book6/index.php).

6) Таха Х. Введение в исследование операций. М.: изд. дом “Вильямс”, 2001.

7) Чуи К. Введение в вейвлеты М. aМирu, 2001.

8) Войнаровский М. Психологика // Быстрое преобразование Фурье, 2002-2003 (http://psi-logic.narod.ru/fft/fft.htm).

9) Кантор И. Алгоритмы и методы (http://algolist.manual.ru/compress/standard).

10) Смирнов М. Введение в PPM (http://www.compression.ru/download/articles/ppm/smirnov_2000_ppm_faq.htm l).

Приложение

Введение в вэйвлет-анализ

Обозначим через L2(0,2p) множество всех интегрируемых с квадратом измеримых функций, определенных на интервале (0,2p). Любую функцию из L2(0,2p) можно представить рядом Фурье

где константы cn, называемые коэффициентами Фурье, определяются формулой

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

образуют ортонормированный (о.н.) базис в L2(0,2p). Ортогональность означает, что



Вторая особенность разложения в ряд Фурье (П.1) состоит в том, что о.н. базис {wn} порождается растяжением единственной функции wn ( x) := w (nx) для всех целых n. Это будет называться в дальнейшем целочисленным растяжением.

Подводя итог, можно сказать, что каждая функция из L2(0,2p) порождается uсуперпозицией† целочисленных растяжений базисной функции

w ( x) = eix .

Обратим внимание на то, что базисная функция является синусоидальной волной. Чем больше абсолютная величина n, тем более высокую частоту имеет волна

wn ( x) := w(nx) .

Таким образом, каждая функция из L2(0,2p) состоит из волн различных частот. Далее рассмотрим пространство L2(R) интегрируемых с квадратом измеримых функций, определенных на вещественной оси R. Ясно, что два пространства L2(0,2p) и L2(R) совершенно различны. В частности, каждая функция (ее локальное среднее значение) из L2(R) должна aзатухатьu до нуля при x, стремящемся к ±Ґ, но синусоидальные aволныu функции wn(x) не принадлежат L2(R). В сущности, если мы хотим использовать aволныu, порождающие L2(R), то эти волны должны были бы затухать до нуля при x ®±Ґ, и из всех практических соображений это затухание должно быть очень быстрым. Так, мы приходим к рассмотрению малых волн, или вэйвлетов, для порождения L2(R). Так же, как и в случае с L2(0,2p), где одна функция w ( x) = eix порождает целое пространство, мы предпочитаем иметь одну функцию для порождения всего L2(R) и будем обозначать ее через y. Но если вэйвлет y имеет очень быстрое затухание, то как он может покрыть всю вещественную ось? Очевидным способом является сдвиг y вдоль R.

Простейший способ для y покрыть все множество R состоит в рассмотрении целочисленных сдвигов y, а именно, y ( x - k ) , kОZ.

Затем, так же как и в синусоидальном случае, мы должны рассматривать волны различных частот. Ради вычислительной эффективности мы будем использовать для частотного разбиения целые степени 2. В результате мы рассматриваем малые волны Заметим, что y (2 j x - k )

y (2 j x - k ) , j, kОZ.

получена из одной aвэйвлет-функцииu y в результате двоичного растяжения (т.е. растяжения в 2 jраз) и двухпараметрического сдвига (на k / 2 j ). Итак, нас интересуют aвэйвлет-функцииu y, двоичные растяжения и двухпараметрические сдвиги которых достаточны для представления любой функции из L2(R).

Далее будем использовать следующие обозначения для скалярного произведения и нормы в пространстве L2(R):



где f, g О L2(R). Заметим, что для любых j, k О Z мы имеем

Следовательно, если функция y О L2(R) имеет единичную норму, то все функции yj,k, определенные формулой

также имеют единичную норму, то есть

||y j ,k ||2 =||y ||2 = 1, j, k О Z,

Определение 1.1. Функция y О L2(R) называется R-функцией, если {yj,k}, как это определено в (П.3), является базисом Рисса в L2(R), в том смысле, что линейная оболочка yj,k, j, k О Z, плотна в L2(R) и что существуют положительные константы A и B, 0 < A Ј B < Ґ такие, что

для всех бесконечных суммируемых с квадратом последовательностей {cj,k}

Определение 1.2. Пусть y О L2(R) является R-функцией, которая порождает {yj,k}, определенное формулой (П.3). Тогда y называется ортогональным вэйвлетом (или о.н. вэйвлетом), если семейство {yj,k}, удовлетворяет условию ортогональности:

бy j , k ,y l ,m с = d j ,l Ч d k ,m , j, k, l, m О Z;

это означает, что любая f О L2(R) может быть представлена как

где ряд (П.4) сходится в L2(R), а именно

Простейшим примером ортогонального вейвлета является функция Хаара yH, определенная формулой

Ряды, представляющие функции f в (П.4), называются вэйвлет-рядами. Аналогично обозначению коэффициентов Фурье в (П.2) вэйвлет-коэффициенты определяются формулой

Однако чтобы получить вэйвлет-ряд функции f, условие ортогональности вэйвлета y не обязательно.

Определение 1.3. R-функция y О L2(R) называется R-вэйвлетом (или вэйвлетом), если существует функция y~ О L2(R) такая, что соответствующие семейства {yj,k} и {y~ j,k} удовлетворяют условию биортогональности:

Если y - R-вэйвлет, то y~ называют двойственным вэйвлетом, соответствующим y.

Заметим, что если y - ортогональный вэйвлет, то он является двойственным самому себе, в том смысле, что y~ = y. Если y - вэйвлет с двойственным y~ , то по определению базиса Рисса, каждая f О L2(R) может быть записана как

Эти вэйвлет-ряды сходятся в L2(R). Из условия биортогональности следует, что

Пусть y - любой вэйвлет, рассмотрим порожденный им базис Рисса {yj,k}. Для каждого j О Z обозначим через Wj замыкание линейной оболочки {yj,k : k О Z}, а именно:

Очевидно, L2(R) может быть разложено в прямую сумму подпространств Wj:

в том смысле, что любую f О L2(R) можно единственным образом представить в виде суммы

f ( x) = ... + g -1 ( x) + g0 ( x) + g1 ( x) + ...,

где gi О Wj для всех j О Z. Точки над знаком суммирования указывают на то, что берутся aпрямые суммыu.

Если y - ортогональный вэйвлет, то подпространства Wj из L2(R) взаимно ортогональны и прямая сумма в (П.7) становится ортогональной суммой. Однако, любой вэйвлет, ортогональный или нет, порождает разложение L2(R) в прямую сумму подпространств (П.7). Для каждого j О Z будем рассматривать замкнутые подпространства

в L2(R). Ясно, что эти пространства обладают следующими свойствами:

Следовательно, в противоположность пространствам Wj, которые удовлетворяют соотношению

подпространства Vj вложены друг в друга, как это описано в условии (1°) и обладают тем свойством, что любая функция f из L2(R) может быть приближена с произвольной точностью ее проекциями Pjf на Vi, что следует из условия (2°). С другой стороны, с уменьшением j проекции Pjf могут иметь сколь угодно малую норму в L2(R), что обусловлено условием (3°).