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

СКО


 

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

28337. Основания освобождения от гражданско-правовой ответственности. Случай и непреодолимая сила 14.98 KB
  Основания освобождения от гражданскоправовой ответственности. Правило о вине как условии ответственности предусмотренное в ст. В сфере предпринимательской деятельности обстоятельством освобождающим от ответственности является непреодолимая сила т. Еще одним общим условием освобождения от гражданскоправовой ответственности является умысел потерпевшего при наличии которого согласно п.
28339. Понятие и виды сроков в гражданском праве. Порядок исчисления сроков 16.84 KB
  Сроки в гражданском праве являются юридическими фактами порождающими возникновение изменение или прекращение гражданских прав и обязанностей. По способу установления сроки делятся на сроки установленные: законом; иными правовыми актами; сделкой или судом. По характеру определения сроки делятся на: императивные и диспозитивные; определенные и неопределенные общие и частные. Императивные сроки не могут быть изменены соглашением участников правоотношений например сроки исковой давности.
28340. Сроки исковой давности в гражданском праве. Приостановление, перерыв и восстановление сроков исковой давности 17.14 KB
  Сроки исковой давности в гражданском праве. Приостановление перерыв и восстановление сроков исковой давности. Особое значение в гражданском праве имеют сроки исковой давности. Общий срок исковой давности установлен в три года.
28341. Право собственности: понятие, содержание и виды 14.48 KB
  Право собственности: понятие содержание и виды. Право собственности представляет собой разновидность вещных прав которые закрепляют принадлежность вещей субъектам гражданских правоотношений. Право собственности в объективном смысле – это совокупность правовых норм закрепляющих и охраняющих принадлежность материальных благ конкретным лицам возникновение осуществление прекращение защиту прав собственника а также их возможность владеть пользоваться и распоряжаться этими материальными благами. Право собственности в субъективном смысле –...
28343. Право частной собственности граждан 14.32 KB
  Право частной собственности граждан. Субъектами частной собственности являются гражд. В собственности граждан может находиться любое имущество за исключением отдельных видов имущества кот в соответствии с законом не м. В собственности м.
28344. Право собственности хозяйственных товариществ и обществ 14.59 KB
  товариществами и обществами признаются коммерческие организации с разделенными на доли учредителей уставным капиталом. товарищами или обществами в процессе его деятельности принадлежит ему на праве собственности. общества могут создаваться в форме акционерного общества общества с ограниченной или дополнительной ответственности. Участники ООО не отвечают по его обязательствам и несут риск убытков общества лишь в пределах стоимости внесенных ими вкладов.
28345. Понятие, субъекты, объекты и содержание права собственности кооперативов 14.75 KB
  Субъектом права собственности кооператива является каждая кооперативная организация признаваемая юр. лицом независимо от вида кооператива. К производственным кооперативам относятся кооперативы в сферах производства и оказания услуг и сельскохозяйственные кооперативы. Примером потребительского кооператива является и потребительское общество осуществляющее в интересах пайщиков заготовительную торговую и др.