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

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


 

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

83800. Общие положения об ответственности за совершение налоговых правонарушений: понятие, лица подлежащие ответственности за их совершение. Условия привлечения к ответственности за совершение налогового правонарушения 39.43 KB
  Условия привлечения к ответственности за совершение налогового правонарушения. Ответственность за совершение налоговых правонарушений несут организации и физические лица. Физическое лицо может быть привлечено к ответственности за совершение налоговых правонарушений с шестнадцатилетнего возраста.
83801. Формы вины при совершении налогового правонарушения. Обстоятельства, исключающие, смягчающие и отягчающие вину. Налоговые санкции 40.83 KB
  Виновным в совершении налогового правонарушения признается лицо совершившее противоправное деяние умышленно или по неосторожности. Вина организации в совершении налогового правонарушения определяется в зависимости от вины ее должностных лиц либо ее представителей действия бездействие которых обусловили совершение данного налогового правонарушения. К ним относятся: 1 отсутствие события налогового правонарушения; 2 отсутствие вины лица в совершении правонарушения; 3 совершение деяния физическим лицом не достигшим шестнадцатилетнего...
83802. Виды налоговых правонарушений и ответственность за их совершение. Характеристика налоговых правонарушений 42.44 KB
  Нарушение срока постановки на учет в налоговом органе установленного НК РФ срока подачи заявления о постановке на учет в налоговом органе при отсутствии признаков налогового правонарушения влечет взыскание штрафа в размере 5 тыс. Ведение деятельности организацией или индивидуальным предпринимателем без постановки на учет в налоговом органе влечет взыскание штрафа в размере 10 от доходов полученных в течение указанного времени в результате такой деятельности но не менее 20 тыс. Нарушение срока представления сведений об открытии и закрытии...
83803. Характеристика иных видов нарушения законодательства о налогах и сборах. Соотношение налоговых правонарушений с административными проступками и преступлениями 41.46 KB
  Ответственность за налоговые правонарушения предусмотрена не только налоговым законодательством но и в Кодексе РФ об административных нарушениях в Таможенном и Уголовном кодексах РФ. Данный кодекс ввел ответственность организаций должностных лиц и граждан за правонарушения в сферах производства и оборота алкогольной продукции наличноденежного обращения государственной регистрации юридических лиц и индивидуальных предпринимателей за неприменение контрольнокассовой техники; а также дополнительно к Налоговому кодексу ответственности...
83804. Виды нарушений банком обязанностей, предусмотренных законодательством о налогах и сборах, и ответственность за их совершение 40.85 KB
  Открытие банком счета организации индивидуальному предпринимателю нотариусу занимающемуся частной практикой или адвокату учредившему адвокатский кабинет счета инвестиционного товарищества без предъявления этим лицом свидетельства уведомления о постановке на учет в налоговом органе а равно открытие счета при наличии решения налогового органа о приостановлении операций по счетам этого лица влекут взыскание штрафа в размере 20 тысяч рублей. Нарушение срока исполнения поручения о перечислении налога сбора авансового платежа пеней...
83805. Защита прав налогоплательщиков. Право на обжалование. Порядок обжалования 39.88 KB
  Статья 137 НК РФ предоставляет каждому налогоплательщику или налоговому агенту право обжаловать акты налоговых органов ненормативного характера действия или бездействие их должностных лиц если по мнению налогоплательщика или налогового агента такие акты действия или бездействие нарушают их права. Вместе с тем административный порядок не отрицает возможности обращения в последствии за защитой в суд либо предоставляется альтернативный порядок защиты прав субъектов налоговых правоотношений. Вместе с тем НК РФ устанавливает два условия...
83806. Рассмотрение жалобы и принятие решения по ней. Последствия подачи жалобы 39.84 KB
  Вышестоящий орган или вышестоящее должностное лицо в месячный срок со дня получения жалобы обязаны ее рассмотреть и принять одно из сле6дующих решений: – оставить жалобу без удовлетворения; – отменить акт налогового органа и назначить дополнительную проверку; – отменить решение и прекратить производство по делу о налоговом правонарушении; изменить решение или вынести новое решение по суще6ству обстоятельств дела. Законодательством РФ предусмотрены следующие способы судебной защиты прав налогоплательщиков: – признание неконституционным...
83807. Административный порядок защиты нарушенных прав налогоплательщиков 40.72 KB
  Вместе с тем административный порядок не отрицает возможности обращения в последствии за защитой в суд либо предоставляется альтернативный порядок защиты прав субъектов налоговых правоотношений. Вместе с тем НК РФ устанавливает два условия соблюдение которых необходимо для защиты нарушенных прав налогоплательщиков или налоговых агентов: – ненормативные акты налоговых органов а также действия бездействие должностных органов этих органов должны по мнению налогоплательщика или налогового агента нарушать их права; – нормативные правовые...
83808. Судебный порядок защиты нарушенных прав налогоплательщиков 39.8 KB
  Законодательством РФ предусмотрены следующие способы судебной защиты прав налогоплательщиков: – признание неконституционным законодательного акта полностью или в части Конституционным Судом РФ; – признание арбитражными судами или судами общей юрисдикции недействительным нормативного либо ненормативного акта налогового органа иного государственного органа или органа местного самоуправления противоречащего закону и нарушающего право и законные интересы налогоплательщика; – отмена арбитражными судами или судами общей юрисдикции не...