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

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


 

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

8326. Китайская миграция 39 KB
  Китайская миграция - процесс движения населения Китая внутри страны и за рубеж. В данной работе мы коснемся, в основном, последнего. Это явление имеет длительную историю развития и определенную структуру. Историю китайской миграции и форм...
8327. Китай - Россия, геостратегическая политика 47 KB
  Китай - Россия, геостратегическая политика. Китай - социалистическая страна с плановой экономикой. Политическая и экономическая системы КНР стабильны и приток иностранных капиталов с каждым годом растет. С середины первого десятилетия нынешнего...
8328. 72 искусства монастыря Шаолинь 1.07 MB
  72 искусства монастыря Шаолинь. Базовые упражнения, которые формируют основу для развития 72х искусств: 1. Удержание золотой монеты Главный смысл данного упражнения в усилении слуха и зрения для развития защитной ре...
8329. Анализ экономической целесообразности либерализации торговли с Китайской Народной Республикой, выявление основных товарных ниш 336.24 KB
  Анализ экономической целесообразности либерализации торговли с Китайской Народной Республикой, выявление основных товарных ниш Введение Китайская Народная Республика является крупнейшим после Российской Федерации и Европейского союза торговым...
8330. Гиноцид, или китайское бинтование ног 139.5 KB
  Гиноцид, или китайское бинтование ног Инструкции перед чтением текста. Возьмите кусок материи примерно трех метров длиной и пяти сантиметров шириной. Возьмите пару детских туфель. Подогните пальцы ног, кроме большого, внутрь стопы. Оберните ма...
8331. Расцвет философии (античность) 66.5 KB
  Расцвет философии (античность). Золотой век человечества. Философия в чистом виде появилась у древних греков. Самое слово философия, как говорилось выше, греческого происхождения. Поэтому можно утверждать, что философию как таковую придумали...
8332. Редуплікація в китайській мові 283.5 KB
  Редуплікація У китайській мові є слова, утворені шляхом повторення. Наприклад, поглянути, послухати. Такого роду стилістичне явище у китайській мові прийнято називати редуплікацією. Проте редуплікація має місце не лише в китайській,...
8333. Философия как форма общественного сознания 194 KB
  Философия как форма общественного сознания. Понятие, происхождение философии. Ее роль в жизни человека и общества (вопрос 1) Ф - форма общественного сознания. - учение о принципах бытия и познания, об отношении человека к миру. - наука о...
8334. Проблема определения философии в истории философии. Предмет философии. Структура философского знания 140.66 KB
  Проблема определения философии в истории философии. Предмет философии. Структура философского знания. Философия - это, прежде всего, слово, происходящее из древнегреческого языка и обозначающее любовь к мудрости, стремление к познанию,...