10455

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

Реферат

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

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

Русский

2013-03-26

192.5 KB

51 чел.

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

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

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

Первый и самый очевидный состоит в том, чтобы подвергать разложению не все изображение целиком, а разбить последнее на небольшие фрагменты или блоки, покрывающие области, внутри которых изображение можно считать реализацией стационарного двумерного сигнала. Именно такой подход использует 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

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


 

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

41827. Система питания двигателя Зил-138 от газаоболонной установки 218.85 KB
  В цилиндрическом корпусе 24 редуктора размещены камера А первой ступени камера Б второй ступени и кольцеобразная камера В вакуумного разгружателя.Одна из стенок камеры первой ступени образована резиновой диафрагмой 5 края которой зажаты между корпусом редуктора и крышкой 4.В камере второй ступени находится зажатая по окружности между верхней частью корпуса и крышкой 36 диафрагма 37. Ее центральная часть соединена рычагом 29 с клапаном 9 второй ступени.
41828. Проведение исследования на основе готовой компьютерной модели 163.07 KB
  LINE х1 у1х2 у2 c–оператор изображающий отрезок прямой х1 у1 начало отрезка х2 y2 конец отрезка c номер цвета. LINE х1 у1х2 у2 c B– оператор изображающий прямоугольник со сторонами параллельными осями координат. LINE х1 у1х2 у2 c BF– оператор изображающий закрашенный прямоугольник c номер цвета.146 6 Перемещение начала координат в центр экрана LINE 3.
41829. Работа с запросами в MS Access 117.5 KB
  Порядок выполнения задания Создание запросавыборки Создать запрос содержащий поля: Идент.Для этого необходимо выполнить следующую последовательность действий: При выбранной вкладке Запросы выполнить щелчок по кнопке . Открывается окно Новый запрос в котором выбрать режим создания запроса Конструктор затем ; Открывается окно Запрос1: запрос на выборку а затем активизируется окно Добавление таблицы в котором выбрать из списка таблиц таблицу Сотрудник щелчком мыши по имени таблицы а затем выполнить щелчок по кнопке после чего...
41830. Создание и форматирование таблиц. Использование логических и математических функций в табличных вычислениях 178.5 KB
  Использование логических функций необходимо, когда для выбора правильного решения нужно проверить выполнение одного или нескольких условий. Наиболее часто используемые функции этой категории
41831. Создание архива данных. Извлечение данных из архива. Атрибуты файла и его объем 27.83 KB
  Атрибуты файла и его объем Цель: изучение принципов архивации файлов функций и режимов работы наиболее распространенных архиваторов приобретение практических навыков работы по созданию архивных файлов и извлечению файлов из архивов. Теоретические сведения к лабораторной работе Архивация упаковка помещение загрузка исходных файлов в архивный файл в сжатом или несжатом виде. Архивация предназначена для создания резервных копий используемых файлов на случай потери или порчи по какимлибо причинам основной копии невнимательность...
41832. Художественные средства. Инструмент rtistic Mediа 217.5 KB
  Примеры рисования инструментом rtistic Medi Художественные средства Инструмент rtistic Medi Художественные средства входит в состав группы инструментов Curve Кривая рис. Инструмент rtistic Medi Художественные средства включает в себя пять отличных друг от друга режимов работы. Инструмент rtistic Medi Художественные средства может работать в следующих режимах: Preset Заготовка заготовка для живописи; Brush Кисть художественная кисть; Spryer Распылитель распылитель; Clligrphic Каллиграфический ...
41833. ИССЛЕДОВАНИЕ ТИПОВОЙ СХЕМЫ УПРАВЛЕНИЯ ЭЛЕКТРОПРИВОДОМ ПОСТОЯННОГО ТОКА ПОДЪЁМНО КРАНОВОГО МЕХАНИЗМА 247 KB
  Изучить принцип действия и исследовать работу одной из типовых схем управления электроприводом подъёмно кранового механизма с ДПТ независимого возбуждения. Ознакомиться с электрооборудованием типового шкафа управления. Исследовать работу схемы управления электроприводом подъёмно – кранового механизма.
41834. Решение бухгалтерских задач с помощью пакета Excel 286.36 KB
  Решение бухгалтерских задач с помощью пакета Excel Цель работы Познакомиться с работой пакета Excel как инструмента для решения задач бухгалтерского учета. Научиться правильно задавать имена переменным определять ссылки на ячейки использовать функции при вводе формул работать с массивами данных в Excel. Должна быть установлена программа Microsoft Excel.
41835. ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ И СХЕМЫ 238.57 KB
  Данная работа посвящена изучению простейших комбинационных логических устройств реализующих логические функции сложения умножения и отрицания. В результате функции отображающие информацию принимают в каждый момент времени только значения 0 или 1. Такие функции называют логическими а сигналы входные и выходные переменные – двоичными бинарными. Рассматривая входные сигналы х1 х2 хп в качестве аргументов можно соответствующие выходные сигналы представлять в виде функции уi = fх0 х1 х2 хп с помощью...