Вейвлет-анализ и его применение для сжатия мультимедийной информации

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

Вейвлет-анализ и его применение для сжатия мультимедийной информации

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

Вейвлет-анализ как таковой появился сравнительно недавно. Термин «вейв-лет» (wavelet - дословно переводится как «маленькая волна») был введен Гроссманом и Морле (Grossman and Morlet) в середине 80-х годов [1]. И хотя в настоящее время математический аппарат вейвлет-анализа развит достаточно хорошо, его применение пока еще только получает заслуженное распространение среди исследователей.

Собственно вейвлеты появились при анализе нестационарных процессов и сигналов. Фурье-анализ таких сигналов дает лишь перечисление его характерных частот (масштабов), но не содержит никакой информации о локальных координатах, при которых эти частоты себя проявляют. Однако в подавляющем большинстве изданий, посвященных вейвлетам, вейвлет-анализ вводится из аналогии с анализом Фурье. В данной работе проводится схожее сравнение, но лишь на качественном уровне. Более детальную информацию о математических основах вейвлет-анализа можно получить из [2, 3, 6]. В русскоязычной литературе вейвлеты также получили название «всплесков».

От анализа Фурье к вейвлет-анализу

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

Рис. 1. Сигнал вида a1sin(?1t) + a2sin(?2t) и его Фурье-спектр

Рис. 2. Сигнал со скачкообразным изменением частоты и его Фурье-спектр

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

.

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

Здесь - материнский вейвлет. Функции же получены из материнского вейвлета путем применения операций сжатия и сдвига к материнскому вейвлету

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

Итак, основные свойства вейвлета:

1) конечная энергия (норма);

2) локализация во времени (пространстве). Чем быстрее вейвлет пакет затухает, тем, в общем-то, лучше, поскольку локализуется область анализа сигнала [2, 3];

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

Примеры вейвлетов приведены на рис. 3 [2].

Рис. 3. Примеры вейвлетов: WAVE, MHAT и Daubechies

Система полученных функций (3) является полной, что позволяет выполнить обратное преобразование.

На сегодняшний день областей, в которых применяется вейвлет-анализ довольно много. Это физика, техника, медицина и биология [3]. В общем случае вейвлет-анализ удобно применять для сигналов, имеющих флуктуации на фоне общей однородности (отклонения от среднего значения). Наиболее интересно применение вейвлет-преобразования в области информационных технологий, а именно для сжатия (архивации) информации. Именно данному использованию вейвлет-анализа посвящено дальнейшее изложение.

Использование вейвлетов для представления мультимедийной информации

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

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

Сжатие статических изображений

Статические изображения являются двумерным сигналом, который представляется в оцифрованном и дискретизованном виде как массив точек (цветов и их яркостей). Для сжатия изображений пользуются тем фактом, что присутствие в нем мелких деталей весьма незначительно. Так, алгоритм JPEG-компресии для выявления мелких незначительных деталей использует дискретное косинусное преобразование [4] (аналог дискретного преобразования Фурье). Из полученного спектра откидываются высокочастотные гармоники, которые и представляют мелкие детали исходного изображения.

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

Рис. 4. Погрешность восстановления изображения, сжатого JPEG

Сжатие видеоинформации

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

Сжатие аудиоинформации

При сжатии аудиоинформации базируются в основном на особенностях вос-приятия звука человеком. Используя эффекты частотного и временного маскирования, из спектра исходного сигнала можно отбросить гармоники, которые заведомо не будут слышны. Для достижения высокой степени сжатия также отбрасываются высокочастотные гармоники (которые обычно незначительны). Опять же, при восстановлении сигнала после процедуры сжатия высокой степени исходный сигнал искажается. В него добавляется периодический шум, наподобие того, что наблюдается при сжатии изображений JPEG-компрессором. Такой периодический шум придает звуку характерную «металлическую» окраску и «улюлюканье» при воспроизведении высокочастотных сигналов. Опять же, эффект здесь кроется в периодических незатухающих функциях базиса разложения сигнала. Локализируя коэффициенты Фурье-спектра в частотной области, мы тем самым «размазываем» сигнал в его временном представлении.

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

И действительно, двумерное вейвлет-преобразование было успешно использовано для сжатия статических изображений [4, 5]. Как уже упоминалось, вейвлет-анализ позволяет выделить флуктуации сигнала относительно его среднего значения. Поскольку реальные изображения содержат сравнительно мало мелких деталей (флуктуаций), т.е. являются довольно стационарным сигналом, то вейвлет-представление позволяет достичь высокой степени сжатия при намного лучшем (чем у JPEG) качестве восстановления изображения (рис. 5). Процесс преобразования изображения заключается в последовательном его масштабировании с усреднением значений яркостей точек. Усреднение выполняется с помощью вейвлет-функций. В выходной поток записываются лишь отклонения яркостей точек от средних значений (это и есть коэффициенты вейвлет-разложения). Этот процесс итерационный, и продолжается до достижения границы масштабируемости изображения: до одного пикселя, яркость которого в результате будет соответствовать усредненной яркости по всему изображению. На рис. 6 показано, что получаемые коэффициенты вейвлет-разложения весьма незначительны по своей величине (величины коэффициентов показаны соответствующими яркостями точек; нулевое значение соответствует серому цвету, отрицательные - темнее, положительные - светлее).

Рис. 5. Изображение (см. рис. 4), сжатое вейвлет преобразованием до аналогичной степени

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

компрессия аудио статистический

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

Рис. 8. Изображение, сжатое с помощью вейвлет-преобразования, оказывается намного качественнее JPEG при аналогичной степени сжатия

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

Рис. 9. Заметная потеря качества изображения при высокой степени сжатия с помощью вейвлет-преобразования (использовались вейвлеты Добеши)

Использование вейвлетов для сжатия аудиосигнала

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

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

Рис. 10. Распределение по значениям выборок для реальных сигналов

В данном конкретном случае , а значения лежат в диапазоне от 0 до 255 соответственно. На рис. 10 видно, что большинство значений выборок лежит в области нулевого (среднего, равного 127) значения, и лишь очень небольшое число отсчетов имеют значения, существенно отличающиеся от среднего. Для второго сигнала прослеживается острый пик в области нулевого значения. Это говорит о том, что сигнал содержит большое число пауз (т.е. на некоторых временных интервалах звуковые колебания попросту отсутствуют). Подобные распределения получаются практически для всех реальных аудиосигналов.

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

Рис. 11. Дискретный вейвлет Хаара и его масштабные трансформации (сжатие и сдвиг)

Материнский вейвлет для нашего преобразования записывается в виде

Пользуясь преобразованием (2) можно получить вейвлет-спектр. Пример такого спектра тестового сигнала для вейвлета Хаара приведен на рис. 12. Как можно заметить, при этом использовался размер буфера сигнала, равный 1024. Полученный спектр оказывается весьма непохожим на привычный спектр Фурье. В вейвлет-спектре можно выделить характерные области, которые соответствуют различным масштабам анализа сигнала. Так, последние 512 значений в спектре соответствуют самому высокочастотному вейвлету. Предыдущие 256 значений - вейвлету с частотой в два раза меньшей и т.д.

Рис. 12. Тестовый сигнал и его вейвлет-спектр в базисе Хаара. Размер буфера равен 1024

компрессия аудио статистический

Для сравнения на рис. 13, приведен Фурье-спектр того же фрагмента сигнала.

Рис. 13. Фурье-спектр сигнала, приведенного на рис.12

Итак, различные области вейвлет-спектра соответствуют различным масштабам анализа входного сигнала. Естественно, в сигнале могут доминировать те или иные частоты, и соответственно в вейвлет-спектре будут выделяться те или иные области. В нашем случае сигнал состоит в основном из низкочастотных гармоник (~1кГц), и выделяется соответствующая область в спектре. На рис. 14 приведен вейвлет-спектр Хаара для высокочастотного гармонического сигнала.

Рис. 14. Вейвлет-спектр Хаара для высокочастотного гармонического сигнала

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

Рис. 15. Вейвлет-спектр Хаара сигнала со скачкообразным изменением частоты

Интересным так же оказывается спектр импульсного сигнала (типа меандра). Если при этом Фурье-спектр широкий, то вейвлет-спектр наоборот предельно дискретный (рис. 16). Это и понятно, ведь вейвлеты выделяют резкие отклонения сигнала от стационарного значения (это свойство легло в основу русскоязычного названия вейвлетов - «всплески»).

Рис. 16. Импульсный сигнал и его Фурье- и вейвлет-спектры

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

Рис. 17. Восстановление исходного сигнала из его вейвлет-спектра (использовались 2, 4, 8, 16, 32, 64, 128 и 1024 коэффициента соответственно)

Сам вид вейвлет-спектра наводит на мысль об использовании его для компрессии сигнала. Разобьем спектр на области, соответствующие различным масштабам вейвлетов. Внутри каждой такой области коэффициенты спектра приблизительно одного порядка (не считая всплесков, как на рис. 16). Для каждой такой области установим двоичную точность задания коэффициентов и необходимое минимальное количество битов для сохранения коэффициентов. Выходной поток соответственно строится блоками: в каждом своя точность представления коэффициентов. Такие действия позволят нам использовать намного меньше битов для записи сигнала, поскольку для большинства масштабов величины коэффициентов близки к нулю. Дополнительного эффекта сжатия можно достичь, отбрасывая высокочастотные компоненты спектра. Присутствие в вейвлет-спектре всплеска (рис. 16) резко снижает коэффициент сжатия, т.к. амплитуда всплеска весьма высока. Однако в реальном аудиосигнале подобные скачки амплитуды практически не встречаются, а если и встречаются, то чаще всего являются шумом. Поэтому, погасив соответствующие коэффициенты спектра, мы получим дополнительный положительный эффект фильтрации сигнала от импульсных помех (что кстати уже используется в цифровой обработке сигналов). Формат выходного кадра приведен на рис. 18.

Рис. 18. Выходной кадр вейвлет-компрессора

Здесь M - заголовок кадра, b0 - информация о точности представления блока 0, #0 - коэффициенты нулевого блока, b1 - информация о точности представления блока 1, #1 - коэффициенты блока 1 и т.д.

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

Обсуждение результатов

Итак, был разработан компрессор/декомпрессор аудиосигналов, функционирующий согласно вышеприведенной схеме. Входными данными компрессора является аудиопоток, сохраненный в формате RIFF (использовались только одноканальные сигналы). Для формирования кадров (рис. 18) используется предварительная обработка спектра, заключающаяся в фильтрации резких всплесков и преобразования числовой формы записи коэффициентов (загрубление точности при округлении и перенос знака в младший бит), с целью уменьшения битовой записи. При этом спектр приобретает вид, показанный на рис. 19.

Рис. 19. Преобразованный для выходного потока вейвлет-спектр

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

Рис. 20. Выходной поток, являющийся последовательностью кадров

компрессия аудио статистический

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

Таблица 1. Сравнение различных компрессоров, применительно к музыкальному сигналу

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

Таблица 2. Результаты сжатия различных аудиосигналов

Таким образом, использование дискретного вейвлет-спектра позволяет получить большую скорость сжатия аудиопотока при приемлемом коэффициенте компрессии. Особенно хорошие результаты получаются для низко и среднечастотных сигналов, поскольку при этом в разложении участвуют крупномасштабные вейв-леты. Также анализ на малых масштабах позволяет отфильтровывать импульсные помехи в сигнале (что невозможно осуществить, оперируя Фурье-спектром сигнала). При отбрасывании большого числа высокочастотных коэффициентов вейвлет-спектра, заметно искажается форма восстановленного сигнала (рис. 17), она приобретает «гистограммный» вид (это объясняется формой вейвлета Хаара). Использование «гладкого» вейвлета (например, Добеши) в качестве базиса позволяет обойти этот факт, в результате чего сигнал получается гладким, однако снижается скорость работы компрессора из-за повышения сложности вычислений. Загрубление точности представления коэффициентов вейвлет-спектра позволяет достичь приемлемых степеней сжатия даже для высокочастотных сигналов. Так как величины коэффициентов при этом относительно большие, загрубление точности не вносит существенных искажений в сигнал.

Литература

компрессия аудио статистический

1.Grossmann A. Morlet J. SIAM // J. Math. Anal. - 1984.

2.Астафьева Н.М Вейвлет-анализ: основы теории и примеры применения // УФН. - 1996. - Т. 166, № 11. - С. 1145-1170.

3.Демин И.М., Иванов О.В., Нечитайло В.А. Вейвлеты и их использование // УФН. - 2001. - Т. 171, № 5. - С. 465-501.

4.Donoho D.L., Vetterli M., DeVore R.A. and Daubechies I. Data Compression and Harmonic Analysis. - 1998, July 9.

5.Shapiro J.M. Embedded Image Coding Using Zerotrees of Wavelet Coefficients // IEEE Trans-action on Signal Processing. - 1993. - Vol. 41, N. 12. - Р. 3445-3462.

6.Robi Polikar. The Engineer's Ultimate Guide to Wavelet Analysis. The Wavelet Tutorial. [http://www.public.iastate.edu/~rpolikar/WAVELETS/WTtutorial.html].

Размещено на Allbest.ru