10446

Использование вейвлет - преобразования для сжатия изображений

Лабораторная работа

Информатика, кибернетика и программирование

Использование вейвлет преобразования для сжатия изображений В настоящее время сжатие изображения на основе вейвлет преобразования получает все более широкое распространение. Так новый стандарт сжатия изображений JPEG2000 использует вейвлет преобразование. В совр

Русский

2013-03-26

1003 KB

50 чел.

Использование вейвлет - преобразования для сжатия изображений

В настоящее время сжатие изображения на основе вейвлет – преобразования получает все более широкое распространение. Так, новый стандарт сжатия изображений JPEG2000 использует вейвлет – преобразование.

В современных космических системах дистанционного зондирования земли широко используются те или иные алгоритмы сжатия изображений, предназначенные для уменьшения информационного потока, передаваемого на землю. В настоящее время широко используется алгоритм дифференциально-импульсной кодовой модуляции (ДИКМ). Данный алгоритм обладает многими достоинствами, прежде всего, простотой реализации и нетребовательностью к ресурсам аппаратуры, а также возможностью сжатия видеоинформации "на проходе". Однако данный алгоритм не может сохранять качество изображения на приемлемом уровне при степенях сжатия более чем 2,5 раза. Поэтому, наряду с ним применяются и более сложные алгоритмы, обеспечивающие более высокую степень сжатия. Как правило, такие алгоритмы основаны на использовании дискретного косинусного преобразования (ДКП, алгоритм JPEG) и вейвлет - преобразования. Такие алгоритмы ориентированы на покадровую обработку поступающей видеоинформации при помощи, прежде всего, цифровых сигнальных процессоров.

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

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

.

Сигнал y= получается “локальным усреднением” сигнала x с помощью набора “весов” :

В дальнейшем нам понадобятся следующие понятия.

  •  Дискретное преобразование Фурье (ДПФ) сигнала: (формальная сумма).
  •  z-преобразование сигнала: (формальная сумма).
  •  Преобразование Фурье функции имеет вид .

В этих терминах применение фильтра записывается так:

,      (1)

или

    (2)

(если сигнал конечен, его обычно доопределяют периодическим образом для всех целых значений индекса).

характеризует распределение “энергии” сигнала по частотам . Иногда бывает полезно разложить сигнал на компоненты, энергия которых сосредоточена в различных частотных поддиапазонах (т.е. существенно отлична от нуля на различных подотрезках отрезка ), и кодировать их с разной степенью детальности (например, в зависимости от чувствительности человеческого уха к звукам различной частоты). Задолго до создания вейвлет - анализа для этого использовалась схема, которую мы сейчас опишем.

Мы хотим найти два фильтра, h (подавляющий высокие частоты) и g (подавляющий низкие частоты), которые позволяли бы разложить сигнал на две компоненты, и , вдвое их проредить (половина значений становится лишней – ведь частотный диапазон сократился вдвое!), а затем, с помощью транспонированных фильтров, точно восстановить по этим данным исходный сигнал (эту операцию можно применять рекурсивно). Условия на искомые фильтры удобно записать в терминах z-преобразования.

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

z-преобразования транспонированных фильтров имеют вид и . Сигнал восстановится с их помощью точно, если:

Получаем условия точного восстановления:

В матричной форме они записываются так:

,

где

Подставив , получим условия на ДПФ искомых фильтров:

  •  (1.2)
  •  

Допустим, что мы нашли h такой, что

   (3)

Тогда, положив

,    (4)

мы видим, что (4) выполняется. Задача свелась к нахождению тригонометрического многочлена , удовлетворяющего (4). Фильтры h и g, удовлетворяющие (4), называются квадратурными зеркальными фильтрами.

На рис.1, (a) и (b), показаны ДПФ такой пары фильтров h и g, а также исходный сигнал до и после фильтрации (без прореживания).

Рисунок 1a.

Рисунок 1b.

Точно такую же операцию можно применить к одной или обеим из полученных компонент, и т.д., добиваясь нужной локализации по частоте. Это позволяет адаптироваться к особенностям сигнала за счет выбора подходящего “дерева разложения”. Оно может выглядеть, например, так:

Рисунок 2.

Фильтр представляет собой набор коэффициентов, с которыми производится свёртка. Так как есть 2 фильтра (высоких и низких частот), то, чтобы преобразованное изображение было того же размера, профильтрованные коэффициенты прореживают. А так как изображение двумерно, фильтры применяют поочерёдно по горизонтали и по вертикали.

Обратное преобразование (при восстановлении изображения) делается по таким же формулам, но с использованием восстанавливающих фильтров.

Пример изображения, профильтрованного по горизонтали и по вертикали, приведен на рисунке 4.

Рисунок 4.

Как видно из рисунка, низкочастотная часть изображения является уменьшенной копией исходного изображения. Но низкочастотную часть изображения можно рассматривать как новое полноценное изображение и применить процедуру фильтрования к нему отдельно. Результат второго шага вейвлет – преобразования показан на рисунке 5.

Рисунок 5.

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

Самый простой подход к сжатию изображений при помощи вейвлет - преобразования состоит в следующем:

  •  Выполнить вейвлет - преобразование.
  •  Упорядочить коэффициенты.
  •  Отбросить “хвост” упорядоченного массива, энергия которого равна допустимой (по условиям задачи) величине.
  •  Запомнить сохраненные коэффициенты и их положение в массиве исходных коэффициентов.
  •  При восстановлении заменять отброшенные коэффициенты нулями.

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

  •  Коэффициенты вейвлет - преобразования квантуются и записываются целыми числами.
  •  Строится упорядоченная таблица коэффициентов: сначала идут те, у которых в старшем двоичном разряде 1, затем – те, у которых в старшем разряде 0, но в следующем – 1, и т.д. В битовом представлении таблица выглядит так:

s

s

s

s

s

s

s

s

s

s

1

1

0

0

0

0

0

0

0

0

>>>>>

1

1

1

1

1

0

0

0

>>>>>>>>>>>>>>>>>>>>>>>>

1

1

1

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Рисунок 6.

В первой строке стоят знаки коэффициентов, во второй – старшие биты, и т.д. Ясно, что для воспроизведения исходного изображения достаточно запомнить (передать) только те биты, которые стоят в клетках, помеченных стрелками, а также длину стрелок и положение самих коэффициентов в исходном двумерном массиве коэффициентов. При передаче битов в таком порядке сначала передается самая существенная информация (старшие биты самых больших коэффициентов), потом менее существенная, и т.д. Этот процесс можно оборвать, дойдя до той части таблицы, где стоят “маленькие” коэффициенты. Проблема в том, как компактно передать таблицу положений сохраненных коэффициентов. Заметим, что полностью упорядочивать массив коэффициентов (по абсолютной величине) не надо, достаточно найти разбиение на группы, показанные в таблице, т. е. на такие группы, что для фиксированного n

     (7)

Пусть все множество коэффициентов разбито на некоторые подмножества .

Фиксируем n, и начинаем по очереди просматривать на наличие значимых коэффициентов – т.е., удовлетворяющих (3). Если в есть значимые коэффициенты, это множество разбивается на некоторые подмножества, и они опять проверяются на значимость, и т.д. Хорошо было бы построить разбиение так, чтобы значимые множества состояли (почти всегда) из единственного элемента, а незначимые были большими.

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

Рисунок 7. Структура деревьев, на которые распадается множество вейвлет - коэффициентов.

Верхний левый квадрант распадается на четверки коэффициентов. В каждой четверке три коэффициента (кроме закрашенного черным) имеют “отпрысков” – четверки коэффициентов на нижних уровнях; каждый из коэффициентов в этих четверках имеет своих отпрысков, и т.д. Узлу (i,j) соответствуют отпрыски с координатами (2i,2j), (2i,2j+1), (2i+1,2j), (2i+1,2j+1). В качестве изначального разбиения берется именно этот набор поддеревьев. Многие из них действительно состоят только из несущественных коэффициентов, так как малые значения на верхних уровнях почти всегда соответствуют малым значениям на нижних уровнях (если двигаться по направлению стрелок на рис. 5). Не углубляясь в дальнейшие подробности, отметим еще одну особенность этого красивого алгоритма: передается (запоминается) не таблица положений коэффициентов, а ключевые шаги процесса сортировки, что существенно компактнее (при декодировании этот процесс фактически воспроизводится в обратном порядке). Так как обычно многие поддеревья оказываются “нулевыми”, шагов сортировки будет не очень много.

Для начала работы необходимо.

  1.  Запустить MATLAB 6.х.
  2.  В закладке Launch Pad открыть пункт Wavelet Toolbox.
  3.  Запустить Wavelet Toolbox Main Menu.
  4.  Нажать кнопку Wavelet Packet 2-D.

Появится окно, приведенное на рисунке 8.

  1.  В меню File выбрать Example Analysis, (Demo Analysis) а затем выбрать изображение по заданию преподавателя.

Рисунок 8.

  1.  Выбрать тип вейвлета, порядок разложения и нажать кнопку Analyze. На экране появится дерево разложения, матрицы коэффициентов и одна матрица коэффициентов в укрупненном виде, которую можно выбрать в дереве коэффициентов. Следует отметить, что в используемой программе происходит автоматический выбор, для каких квадрантов будет производиться вейвлет – преобразование следующего этапа. В приведенной ниже иллюстрации вейвлет преобразование проводилось на всех шагах и для каждого квадранта. Поэтому на рисунке 9 поучилось 64 массива коэффициентов, в отличие от примера, приведенного на рисунке 3.

Рисунок 9.

  1.  Нажать кнопку Compress. Экран примет вид, показанный на рисунке 10. Порог отсечения (желтая вертикальная пунктирная линия) можно изменять при помощи мыши, а можно выбирать автоматически, выбрав соответствующий метод (Select Threshold Method). При этом отображается доля нулей (коэффициентов, ежащих ниже порога отсечения) и остаточная "энергия" изображения (квадрат дисперсии).

Рисунок 10.

  1.  Нажать кнопку Compress. При этом появится сжатое изображение. После этого нажать кнопку Residuals. Появится окно, показанное на рисунке 11. В нем показана разность между исходным и сжатым изображениями, а также СКО этой разности, ее максимальное и минимальное значения, медиану и ряд других параметров.

Рисунок 11.

Целью работы является исследование реализованного алгоритма вейвлет – преобразования и поиск оптимальных параметров вейвлет – преобразования, а именно:

Выбор оптимального семейства вейвлетов и конкретного вейвлета.

Выбор оптимального числа шагов вейвлет – преобразования.

Выбор оптимального порога отсечения и/или алгоритма его определения.


Задание для лабораторной работы.

1.

Для заданных исходных данных

  •  Изображение,
  •  Тип (тип и порядок) вейвлета,
  •  Количество шагов преобразования (1-5),
  •  Метод выбора значения порога.

Выполнить шаги 1-8 и определить СКО (standart devation) исходного и сжатого изображений и долю нулевых коэффициентов вейвлет – преобразования. Построить график зависимости СКО от доли нулевых коэффициентов при различных значениях порога.

Вариант

Изображение

Тип вейвлета

Число шагов

Метод выбора значения порога

1

Detail

Coif ( 3 )

5

Balance sparsity-norm

2

Facets

Sym ( 5 )

4

Remove near 0

3

Belmont 1

Haar

3

Balance sparsity-norm (sqrt)

4

Tire

Db ( 8 )

4

Balance sparsity-norm

5

Sinsin

Rbio (5,5)

3

Balance sparsity-norm (sqrt)

6

Geometry

Bior (3,9)

4

Remove near 0

7

Woman

Dmey

5

Balance sparsity-norm

8

Tire

Sym ( 7 )

3

Remove near 0

9

Fasets

Coif ( 5 )

3

Balance sparsity-norm

10

Detfingr

Rbio (6,8)

3

Balance sparsity-norm (sqrt)

% нулевых коэффициентов

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

СКО

2.

Повторить пункт 1 для фиксированного значения порога, которое должно выбираться одним из методов, но для различного числа шагов вейвлет преобразования.

Число шагов

1

2

3

4

5

СКО

3.

Повторить пункт 1 для фиксированного значения порога, которое должно выбираться одним из методов, но для различных вейвлетов.

Вариант

Тип вейвлета

1,6

Db (1-10)

2,7

Coif (1-5)

3,8

Sym (2-8)

4,9

Bior (1,1-3,3)

5,10

Rbio (1,1-3,3)

Порядок вейвлета

1

N

СКО


 

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

36480. Динамика развития цивилизации, этапы ее развития на историческом примере 46.5 KB
  В истории человечества выделяют следующие глобальные цивилизации: неолитическую раннеклассовую античную средневековую индустриальную и наконец постиндустриальную цивилизации. Условия формирования античной цивилизации. Безусловно их наследие оказало определенное влияние на становление античной цивилизации тем не менее античный период в истории человечества дал рождение совершенно новым экономическим политическим и духовным институтам.
36481. Механизм смены цивилизации. Переход между цивилизациями 35 KB
  Механизм смены цивилизации Основные причины: внутренние противоречия в которых центральное место занимают потребности человека. Для производства материальных и духовных благ цивилизации приходится привлекать новые ресурсы средства труда источники энергии реализовывать новые экономические и политические схемы подавлять социальные конфликты и предлагать новый духовный продукт. Попытки удовлетворения потребностей нарушают сложившийся в цивилизации баланс и она не может удовлетворить потребности всех. Духовный мир чутко реагирует на эти...
36482. Переходный этап в развитии цивилизации на историческом примере перехода от раннеклассовой к античной 27.5 KB
  Переход между цивилизациями происходит в четыре этапа: латентный этап обвального хаоса патовая ситуация завершающий этап. На первом этапе происходит падение эффективности старого общества: возникают социальные противоречия разногласия между управленцами и исполнителями экономической функции и непрерывные войны которые с одной стороны истощали материальные ресурсы а с другой обогащали правящую элиту. Происходит возращение к родоплеменному типу отношений формирование общинного строя предполагающего управление общества вождем советом...
36483. Основные особенности и достижения неолитической цивилизации 32 KB
  Начало неолитической цивилизации связывают с неолитической революцией. Достижения неолитической цивилизации: Возникла первая форма собственности общинная собственность на землю; Появляется объекты собственности сельскохозяйственные земли пастбища охотничьи и рыболовные угодья; Возникает частная собственность при необходимости защита частной собственности; Формирование первых политических институтов крупные межобщинные объединения; Духовный мир выходит на новый уровень возрастает уровень познания окружающего мира;...
36484. Основные особенности и достижения раннеклассовой цивилизации 32.5 KB
  Если в неолитическую эпоху основные изменения были связаны с технологиями то для раннеклассовой цивилизации характеры значительные изменения в экономическом способе производства и социальнополитические отношения. Происходит городская революция создания центров локальной цивилизации в сети крупных городов. Города не только служили центрами ремесла но и позволяли сконцентрировать материальные и духовные ресурсы цивилизации для ее развития.
36485. Цивилизации Древнего Египта: развитие и основные достижения 38.5 KB
  Экономика Древнего Египта в основном базировалась на земледелии. Хорошие плодородные почвы Египта и мастерство земледельцев позволяли не только обеспечивать сельское население продуктами питания но и создавать избыточный продукт. Еще в период Древнего царства сложились торговые пути из Египта в Нубию на Синай в Палестину и Сирию.
36486. Духовный мир человека древних обществ 36.5 KB
  В Египте в отличие от всех существовавших цивилизаций сакрализация достигла максимально возможного уровня. Высокого уровня в Древнем Египте достигли различные виды искусства которые были прежде всего составной частью заупокойного ритуала. В Египте появился уникальный литературный жанр книги мертвых религиозные тексты которые помещали в гробницу. В Древнем Египте все специальные знания концентрировались в небольшой группе жрецов.
36487. Древняя Греция – основные достижения в экономической, политической и духовной сферах 42 KB
  Формируется теоритеческая база науки. Процесс становления древнегреческой науки шел через отделение научного элемента от фантастического. Итак появление науки в Древней Греции способствовал ряд предпосылок: У греков отсутствовала каста жрецов и поэтому научные знание были доступны любому гражданину; Демократическая форма правления в государстве что гарантировало гражданские права и необходимость их отстаивания с помощью риторики основанной на аргументации и убеждении оппонента. Развиваются такие науки как математика геометрия...
36488. Українська мова. Відповіді на екзаменаційні питання 5.99 MB
  рикметники, у яких є закінчення, називаються повними: добрий, вільна, славне, зелені, батькового, материна. Ці форми є звичайними для сучасної української мови.У народній творчості та в поезії вживаються також нестягнені повні прикметники: вірная (замість: вірна), вечірнюю (замість: вечірню), синєє (замість: синє), молодії (замість: молоді).