10446

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

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

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

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

Русский

2013-03-26

1003 KB

51 чел.

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

В настоящее время сжатие изображения на основе вейвлет – преобразования получает все более широкое распространение. Так, новый стандарт сжатия изображений 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

СКО


 

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

76882. Комиссуральные и проекционные волокна полушарий головного мозга (мозолистое тело, свод, спайки, внутренняя капсула) 183.45 KB
  Комиссуральные волокна являясь длинными отростками корковых нейронов соединяют между собой правое и левое полушария большого мозга образуя мозолистое тело свод спайки: ростральную переднюю сводчатую. В мозолистом теле они формируют лучистость в которой находятся волокна соединяющие новые высшие корковые центры. Части мозолистого тела: клюв начало внизу прилежит к терминальной пластинке; колено переход к среднему отделу; ствол средний отдел; валик задний округленный отдел; В полушариях комиссуральные волокна образуют:...
76883. Боковые желудочки мозга 181.62 KB
  Стенки центральной части бокового желудочка: верхняя стенка поперечные волокна мозолистого тела; нижняя дно тело хвостатого ядра часть задней поверхности таламуса и терминальная полоска; медиальная стенка тело свода; с латеральной стороны мозолистое тело и хвостатое ядро соединяются под острым углом как бы исключающим латеральную стенку. Стенки переднего рога: медиальная прозрачная перегородка; латеральная и нижняя головка хвостатого ядра; передняя верхняя и часть нижней стенки волокна мозолистого тела. Стенки нижнего...
76884. Обонятельный мозг, его центральный и периферический отделы 182.63 KB
  По современным представлениям в процессе эволюции позвоночных обоняние на основе обонятельного мозга выступило в качестве организатора целостных функций связанных с формированием всех безусловно рефлекторных реакций инстинктов: ориентировочных оборонительных пищевых сексуальных и др. Благодаря обонятельному мозгу сформировалось новое морфофункциональное объединение лимбическая система или висцеральный мозг обеспечивающие человеку следующие свойства: эмоциональномотивационное поведение; сложное поведение связанное со сменой фаз...
76885. Промежуточный мозг – отделы, внутреннее строение, третий желудочек 187.06 KB
  Границы промежуточного мозга проходят: по основанию головного мозга то есть по вентральной поверхности: спереди по зрительному перекресту сзади по краю заднего продырявленного мозгового вещества и ножек мозга; по дорзальной поверхности обращенной к своду черепа по поперечной борозде между верхними холмиками и таламусом и по эпиталамической спайке; латерально по терминальной пластинке что соответствует разграничительной линии между таламусом и внутренней капсулой. Анатомические отделы промежуточного мозга: таламическая область ...
76886. Средний мозг 183.11 KB
  Средний мозг состоит из крыши покрышки и основания водопровода акведуктус церебри полости среднего мозга. Анатомической основой мозга являются четверохолмие и парные ножки мозга водопровод. Крыша среднего мозга представлена пластиной четверохолмия которая имеет: верхние холмики правый и левый куполообразные парные возвышения с подкорковыми центрами зрения; ручки верхних холмиков продольные валики лежащие позади таламуса и направляющиеся к латеральным коленчатым телам; нижние холмики и ручки нижних холмиков правые и левые...
76887. Задний мозг 181.2 KB
  Ядра и волокна моста на поперечном срезе: Переднее и заднее ядро трапециевидного тела в середине моста. Двигательное ядро лицевого нерва в покрышке между трапециевидным телом и волокнами средней ножки мозжечка. Двигательное и чувствительное мостовое ядра тройничного нерва в покрышке между волокнами верхних и средних ножек мозжечка. Верхнее слюноотделительное парасимпатическое ядро в покрышке между ядрами отводящего и тройничного нервов; Ядро одиночного пути чувствительное в покрышке между волокнами верхних и нижних...
76888. Мозжечок 186.15 KB
  Параметры мозжечка составляют: масса в 120-150 г поперечный размер 910 см длина 35 см. От большого мозга отделен поперечной щелью в которой находится отросток твердой мозговой оболочки намет палатки мозжечка закрывающий нижние затылочные ямки в задней черепной яме. Рельеф на поверхностях мозжечка возникает благодаря глубоким поперечным щелям разделяющим верхнюю заднюю и нижнюю доли. Менее глубокие поперечные щели делят доли на дольки а по поверхности долек проходят мелкие бороздки отграничивающие листки мозжечка.
76889. Продолговатый мозг 180.62 KB
  Внутреннее строение мозга на фронтальном разрезе: ядра нижние оливные: правое и левое в оливах; ретикулярная формация лежит над оливами; сердечный и дыхательный центры функциональные объединения на основе ядер ретикулярной формации и блуждающего нерва; ядра IX X XI и XII пары черепных нервов: двигательное двойное ядро IX X черепных пар заднее ядро X пары парасимпатическое двигательные ядра XI и XII черепных пар; глотательнорвотный центр на основе функционального объединения ретикулярной формации и ядер IX X XII пары;...
76890. Ромбовидная ямка, её рельеф, проекция на нее ядер черепных нервов 183.14 KB
  В ней различают мало заметные но важные структуры: треугольник подъязычного нерва узкая часть медиального возвышения в нижнем углу с проекцией двигательного ядра этого нерва; треугольник блуждающего нерва кнаружи от треугольника подъязычного нерва в нем проекция парасимпатического заднего ядра данного нерва; мозговые полоски IV желудочка проходящие поперечно между латеральными углами ямки и содержащие отростки клеток улитковых ядер. На ромбическую поверхность ямки в направлении спереди назад проецируются все ядра черепных нервов с...