10455

Вейвлет-преобразование. Алгоритмы Лифтинга и Маллата

Реферат

Математика и математический анализ

Вейвлетпреобразование. Алгоритмы Лифтинга и Маллата. Вейвлет компрессия в последнее время стала передовой технологией среди методов представления и сжатия сигналов и изображений. Методы сжатия с вейвлет преобразованием можно отнести к классу методов с исполь

Русский

2013-03-26

192.5 KB

52 чел.

Вейвлет-преобразование. Алгоритмы Лифтинга и Маллата.

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

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

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

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

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

Рисунок 5.1.

Пусть L2(R) – гильбертово пространство функций, имеющих конечную норму .

Пусть , тогда Tf(a,b) называют непрерывным вейвлет-преобразованием.

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

КМА естественным образом приводит к иерархической и быстрой схеме вычисления вейвлет-коэффициентов, названной каскадным алгоритмом.

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

,

,         (5.1)

где , .

Уравнения (5.1) называются соотношениями декомпозиции. Таким образом, операцию вычисления соотношений декомпозиции можно представить как дискретную фильтрацию входной последовательности {am,n} при помощи набора из двух фильтров.

В цифровой обработке сигналов схема, описываемая (2.3.6), называется схемой субполосной фильтрации. В двухканальной схеме анализа субполосной фильтрации берется свертка входной последовательности с двумя фильтрами, низкочастотным и высокочастотным. Затем обе выходные последовательности фильтров прореживаются в два раза путем отбрасывания четных или нечетных компонентов – этот процесс также называется децимацией. Поэтому на выходе получается последовательность такой же размерности, что на входе. Схема фильтров декомпозиции изображена на рис. 5.2. Обозначение «2» используется для операции прореживания

Рисунок 5.2. Схема фильтров декомпозиции

Рассмотрим теперь обратную задачу – восстановление функции по известным коэффициентам разложения по вейвлет-базису. Для этого используется формула композиции:

,        (5.2)

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


Рисунок 5.3. Схема фильтров композиции

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

Рисунок 5.4.

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

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

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

,

,          (5.3)

и, кроме того, kZ       (5.4)
Тогда фильтры для биортогонального вейвлет-преобразования могут быть однозначно определены по двум наборам коэффициентов {
} и { }.

В настоящее время общепризнанным лидером, обеспечивающим высокий коэффициент сжатия при относительно низких вычислительных затратах, является базис биортогональный базис вейвлетов “CDF 9/7” с вещественными коэффициентами. Коэффициенты фильтров для преобразования “CDF 9/7” следующие:

h0=0.85699

h±1=0.377402

h±2=-0.110624

h±3=-0.023849

h±4=0.037828

=0.788486

=0.418092

=-0.040689

=-0.064539

Среди фильтров с целочисленными коэффициентами лидером является фильтр (5,3) со следующими коэффициентами:

h0=3/4

h±1=1/4

h±2=-1/8

=1

=1/2

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

а три двумерных вейвлета:

H(x,y)=(x)(y),

V(x,y)=(x)(y),

D(x,y)=(y)(x).

На практике это означает, что сначала двумерная матрица дискретного изображения построчно подвергается одномерной фильтрации по схеме декомпозиции (отклик ФНЧ с ИХ H записывается в левую половину вектора-строки, отклик ФВЧ с ИХ G – в правую), а затем одномерная фильтрация проводится вдоль столбцов (отклик ФНЧ h записывается в верхнюю половину вектора-столбца, отклик ФВЧ с ИХ g – в нижнюю). В результате получаем из матрицы изображения 4 группы коэффициентов разложения. Соответствующие блоки коэффициентов будем называть LL, HL, LH, HH (low-low, high-low, low-high, high-high) саббэндами. На рисунке 5.5 приведена схема декомпозиции двумерного изображения.

Рисунок 5.5

Процедура декомпозиции может быть продолжена над левой верхней четвертью полученных коэффициентов (LL-саббэнд), которые соответствуют двумерным масштабирующим функциям. Коэффициенты, лежащие в оставшихся трех наборах, относятся к функциям двумерных вейвлетов и далее не обрабатываются. Три вейвлет-саббэнда, которые могут быть получены на следующем шаге, представляют «более грубый» уровень пространственного (т.е. в области изображения) разрешения. Выполненное «на всю глубину» вейвлет-преобразование дает спектр, в котором единственный коэффициент, стоящий в левом верхнем углу, является коэффициентом при масштабирующей функции. Для простоты будем полагать, что размер обрабатываемого изображения – 2n2n пикселей, соответственно максимальное число шагов при выполнении преобразования на всю глубину равно n. Результат выполнения двух шагов вейвлет-декомпозиции приведен на рисунке 5.6.

Рисунок 5.6.

Теорема лифтинга. Любое ВП с КИХ фильтрами может быть получено из разделения сигнала на четные и нечетные компоненты с помощью конечного числа шагов лифтинга и масштабирования.

,   (5.5)

где .

Рис.5.7.

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

Рис.5.7.

Алгоритм вычисления ВП одномерного сигнала по лифтинг-схеме будет выглядеть следующим образом:

Алгоритм вычисления одного шага обратного ВП с использованием лифтинг-схемы.

Рассмотрим пример вычисления ВП CDF 9/7 с использованием лифтинг-схемы.

Схема вычисления одного шага ВП приведена на рисунке 5.8.

Рис. 5.8.

Здесь введены следующие обозначения:

p1=-1.5861343

u1=-0.0529801

p2=0.88298011

u2=0.44350685

K1=1.1496043

Алгоритм вычисления одного шага ВП по лифтинг-схеме приобретает вид:


 

А также другие работы, которые могут Вас заинтересовать

32778. ИЗУЧЕНИЕ ЗАКОНОВ ВРАЩАТЕЛЬНОГО ДВИЖЕНИЯ С ПОМОЩЬЮ МАЯТНИКА ОБЕРБЕКА 3.8 MB
  Определить момент инерции системы тел. Исследовать зависимость углового ускорения от величины момента приложенных сил с учётом сил трения. 2 Угловая скорость и угловое ускорение для всех точек тела одинаковы в данный момент времени однако для различных точек тела линейные скорости движения по окружности разные так как зависят от расстояния R точки до оси вращения. Сила равнодействующая внешних и внутренних сил приложенных к iму элементарному объему телу создаёт относительно произвольно взятой точки на оси вращения момент силы ...
32779. Определение коэффициентов трения качения и скольжения методом наклонного маятника 201 KB
  Северодвинске ФАКУЛЬТЕТ: IV КАФЕДРА: ФИЗИКИ Лабораторная работа Определение коэффициентов трения качения и скольжения методом наклонного маятника Северодвинск 2007 Лабораторная работа ФМ 16 Наклонный маятник Ι. Цель работы Цель работы: определение коэффициентов трения качения и трения скольжения. Основные теоретические положения При относительном перемещении двух соприкасающихся тел или при попытке вызвать такое перемещение возникают силы трения. Различают три вида трения возникающего при контакте твердых тел: трение скольжения покоя и...
32780. Изучение законов сохранения импульса 538.5 KB
  Определить коэффициенты восстановления скорости и энергии для случая частично упругого удара. Существует два предельных вида удара: абсолютно упругий и абсолютно неупругий. Абсолютно упругим называется такой удар при котором механическая энергия тел не переходит в другие немеханические виды энергии а размеры и форма тел полностью восстанавливаются после удара. Абсолютно неупругим ударом называется такой удар при котором размеры и форма тел не восстанавливаются после удара.
32781. Определение коэффициентов восстановления скорости и энергии шаров 150.23 KB
  Схема лабораторной установки схема проведения эксперимента Установка включает в свой состав: 1 основание; 2 вертикальную стойку; 3 верхний кронштейн; 4 корпус; 5 электромагнит; 6 нити для подвески металлических шаров; 7 провода для обеспечения электрического контакта шаров с клеммами 10. Основание снабжено тремя регулируемыми опорами 8 и зажимом 9 для фиксации вертикальной стойки 2 выполненной из металлической трубы ; на верхнем кронштейне 3 предназначенном для подвески шаров расположены узлы регулировки обеспечивающие...
32782. ОПРЕДЕЛЕНИЕ ПЛОТНОСТИ ЖИДКОСТИ ПРИ ПОМОЩИ КАТЕТОМЕТРА 1.2 MB
  ЦЕЛЬ И МЕТОД РАБОТЫ научиться работать с катетометром В 630; определить плотность жидкости с помощью катетометра используя метод сообщающихся сосудов. ТЕОРЕТИЧЕСКОЕ ВВЕДЕНИЕ Плотность жидкости можно определить с помощью сообщающихся сосудов. 1 поверх жидкости известной плотности  наливают в оба колена исследуемую жидкость неизвестной плотности .
32783. ОПРЕДЕЛЕНИЕ УНИВЕРСАЛЬНОЙ ГАЗОВОЙ ПОСТОЯННОЙ 532 KB
  ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ На базе экспериментальных законов БойляМариотта ГейЛюссака Шарля Клапейрон установил что для разреженных газов выполняется соотношение 1 где P давление газа Па V объем газа м3 T абсолютная температура К C газовая постоянная зависящая от массы газа.=1013105 Па и T=273 К один моль любого газа занимает один и тот же объем равный =224 литра=224102 м3 поэтому для одного моля газа из соотношения 1 получаем: или 2 где величина R=831 одинакова для всех...
32784. ОПРЕДЕЛЕНИЕ ОТНОШЕНИЯ ТЕПЛОЁМКОСТЕЙ ДЛЯ ВОЗДУХА 256.5 KB
  Избыток давления воздуха в Рис. Пусть при состоянии 1 в баллоне объемом V масса воздуха равна m. Масса воздуха m занимала перед открытием крана К2 объем V1 где V1 V.
32785. Определение ускорения свободного падения при помощи машины Атвуда 569.5 KB
  Северодвинске Факультет: № 4 Кафедра: № 12 Лабораторная работа Определение ускорения свободного падения при помощи машины Атвуда г. Северодвинск 2007 Лабораторная работа ФМ 11 Определение ускорения свободного падения при помощи машины Атвуда 1. Цель и метод: С помощью машины Атвуда исследовать законы кинематики и научиться экспериментально определять ускорение свободного падения. Законы свободного падения тел открыл итальянский физик Галилео Галилей 1564 ― 1642.
32786. Изучение законов колебания математического и физического маятников 251.5 KB
  Определить положение центра масс физического маятника. Отклонение маятника от положения равновесия будем характеризовать углом образованным нитью с вертикалью рис. При отклонении маятника от положения равновесия возникает вращательный момент силы тяжести равный по модулю произведению силы mg на её плечо = l sin : M = mgl sin где m масса; l длина маятника. 1 Напишем для маятника уравнение динамики вращательного движения обозначив угловое...