10455

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

Реферат

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

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

Русский

2013-03-26

192.5 KB

53 чел.

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

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

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

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

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


 

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

79406. Понятие социализации как процесса формирования личности. Этапы, виды и механизмы социализации 28.33 KB
  Этапы виды и механизмы социализации Социальная роль как элемент структуры личности задаётся тем что попадая в определённую систему отношений с другими людьми в том или ином качестве человек сталкивается с определёнными требованиями которые неизбежно и неминуемо предъявляются тому кто попадает на это место с системой ожиданий что в определённой ситуации он будет вести себя соответствующим образом. Ролевая теория личности это подход к изучению личности согласно которому личность описывается посредством усвоенных и принятых ею или...
79407. Проблема индивидуальности в психологии личности. Специфика индивидуального бытия человека 28.25 KB
  Специфика индивидуального бытия человека В психологии существует несколько традиций понимания индивидуальности. Первая традиция связана с пониманием индивидуальности как единичности. Описание индивидуальности с этой точки зрения это определение линии потенциальных патологических изменений личности.
79408. Понятия и психологические образования индивидуальности 29.21 KB
  Психологические образования личности обеспечивающие человеку возможность совершать поступки позволяющие ему осуществить акт свободного самостоятельного и ответственного выбора отстаивать собственную позицию составляют особый уровень и особую структуру субъективности. С этой точки зрения субъектность человека способности и механизмы его душевной жизни входят в психологические образования личности в качестве их особых предпосылок. Характер также неотделим от личности поскольку реализует главные жизненные устремления человека.
79409. Мотивация развития индивидуальности 24.51 KB
  Преобладание формального чисто динамического описания движущих сил развития личности над содержательным их анализом и отсутствие адекватного подхода к изучению их общественно-исторической обусловленности постулирование положения о подчиненности активности субъекта некоторой конечной заранее предустановленной цели а тем самым и понимание человека как преимущественно адаптивного существа. На принципиально иных позициях строится подход к изучению движущих сил развития личности в советской психологии. Методологические...
79410. Жизненный путь личности 24.74 KB
  Сознание активность зрелось личности рассматриваются Рубинштейном как высшие личностные образования которые выполняют функции организации регуляции обеспечения целостности жизненного пути человека как субъекта деятельности. Рубинштейна выступает активность и творчество личности как организатора и преобразователя своей жизни. Ему принадлежит самое крупное лонгитюдное исследование личности и ее жизненного пути на основе которого была определена возрастная периодизация и онтогенез развития личности: детство юность выбор профессии...
79411. Смысл жизни личности в концепции Франкла 25.84 KB
  Смыслы не являются универсальными они уникальны для каждого человека в каждый момент его жизни. Однако существенным отличием Франкла является идея о том что обретение и реализация смысла всегда связана с внешним миром с творческой активностью человека в нем и его продуктивными достижениями. При этом он как и другие экзистенциалисты подчеркивал что отсутствие смысла жизни или невозможность его реализовать приводит к неврозу порождая у человека состояния экзистенциального вакуума и экзистенциальной фрустрации. Он выделяет три класса...
79412. Движущие силы и условия развития личности. Развитие как способ существования личности в представлениях отечественных исследователей 44.04 KB
  Развитие как способ существования личности в представлениях отечественных исследователей. Проблема постоянства и изменчивости личности Асмолов: Факторы развития личности: органические предпосылки среда сама личность. Двухфакторная детерминация развития личности наследственность среда определяет постановку проблемы о соотношении биологического и социального в человеке.
79413. Психологический возраст и социальная зрелость личности. Подходы к определению критериев социальной зрелости личности 34.66 KB
  Следует отметить что и проблема хронологического возраста имеет большое значение для психологии при исследовании жизненного пути личности выделения его основных этапов т. Вместе с тем в современной науке все большее распространение приобретает полиизмерительный подход к изучению возраста как дифференцированной меры времени человеческой жизни. ^ Самооценка возраста. При постановке проблемы возраста которая принята в психологии практически неисследованным остается вопрос о субъективном отношении человека к собственному возрасту о том...
79414. Категория «личность» в системе наук. Междисциплинарный статус проблемы 26.59 KB
  Междисциплинарный статус проблемы Первое отличие познавательной ситуации исследования психологических закономерностей становления и развития личности состоит в том что в психологии до сих пор возникают серьезные затруднения при попытках очертить сферу эмпирических фактов относящихся к предмету психологического изучения личности. Многогранность феноменологии личности отражающая объективно существующее многообразие проявлений человека в истории развития общества и его собственной жизни превращает исходный вопрос любого познания вопрос об...