• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Стиск зображень з використанням методу дерев нулів хвилькового перетворення

Хвильковий розклад зображення можемо мислити собі як просторову множину коефіцієнтів, яка складається з дерев. Дерево коефіцієнтів хвилькового перетворення означається як множина коефіцієнтів із різних областей, що описують ту саму просторову ділянку в зображенні.

На рис.8.11. показано трирівневий хвильковий розклад зображення Lena та структуру дерева хвилькових коефіцієнтів, які відповідають за ділянку ока в зображенні. Стрілки на рис. (б) показують співвідношення батьківські вершини – дочірні вершини в дереві; H позначає високу частоту, L - низьку частоту, 1,2,3 - рівні частот. Найбільш низькочастотна компонента хвилькового розкладу представляється кореневими вершинами дерева, які знаходяться у верхньому лівому куті. Найбільш високочастотна компонента хвилькового розкладу представляється кінцевими вершинами дерева, які знаходяться у нижньому правому куті. За винятком кореневої вершини, яка має лише три дочірніх вершини, кожна батьківська вершина має чотири дочірніх вершини, а саме ділянку розміру 2х2 з тим самим просторовим розташуванням у більш високочастотній компоненті.

(а) (б)

Рис. 8.11. (а) Трирівневе хвилькове перетворення зображення. (б) Дерево коефіцієнтів

Методи стиску зображень з використанням дерев нулів (EZW, SPIHT) ґрунтуються на ідеї використання багатьох проходів для кодування дерев нулів, щоб передати найбільші хвилькові коефіцієнти спочатку.

Дерева нулів переглядаємо, користуючись змінними порогами.

Множина коефіцієнтів дерева називається суттєвою, якщо значення найбільшого коефіцієнта в цій множині не менше від певного порога (наприклад, поріг може бути степенем двійки). В іншому випадку ця множина є несуттєвою. Аналогічно, коефіцієнт називається суттєвим, якщо його значення не менше від певного порога. В іншому випадку цей коефіцієнт є несуттєвим.

У кожному проході суттєвість більшої множини в дереві аналізується спочатку. Якщо множина несуттєва, вона кодується відповідним символом, і при відтворенні всі множина заповнюється нулями. В іншому випадку множина розбивається на підмножини (дочірні множини) для подальшого аналізу на суттєвість. Після того, як в поточному проході проаналізовано всі коефіцієнти, поріг перед черговим проходом зменшується вдвоє.

Основне припущення при кодуванні за допомогою дерев нулів полягає в тому, що більшість зображень можуть бути змодельовані як такі, що мають спадаючі спектральні значення. Це конкретно означає: якщо батьківська вершина дерева коефіцієнтів хвилькового пертворення несуттєва, то дуже висока ймовірність, що її дочірні вершини також будуть несуттєвими. У цьому разі дуже ефективно працює для стиску кодовий символ для дерева нулів.

Далі детально розглядаємо як приклад алгоритм EZW на підставі дерев нулів коефіцієнтів хвилькового перетворення. Цей метод запропонований Шапіро в роботі, опублікованій у 1993р. Метод SPIHT є розвитком методу EZW.

Позначення EZW утворене від слів Embedded Zerotree Wavelet. Пояснимо значення кожного із слів у цьому методі.

Слово wavelet (хвилькове) означає, що метод працює з коефіцієнтами хвилькового перетворення.

Слово embedded (вкладене) означає, що кодер стискає зображення, утворюючи потік бітів із зростаючою точністю. Тобто, коли до потоку додати більше бітів, відтворене зображення буде точнішим.

Слово zerotree (дерево нулів) означає, що метод використовує поняття дерева нулів. Хвилькове перетворення дає представлення зображення, структуроване на дерева. Дерево нулів – це четвіркове (кожна вершина розгалужується на чотири дочірніх вершини) дерево, усі коефіцієнти якого менші від поточного порогу. Це дерево кодується одним символом, а декодер відтворює його як заповнене нулями четвіркове дерево.

Ми проходимо коефіцієнти хвилькового перетворення у порядку, який називається порядком Мортона. Цей порядок схематично наведений нижче.

На кожному етапі виконують головний та підрядний проходи.

Головний прохід.

Якщо коефіцієнт додатній і більший від порогу, то він кодується символом p.

Якщо коефіцієнт від’ємний і за абсолютною величиною більший від порогу, то він кодується символом n.

Символом t кодується корінь дерева нулів.

Символом z кодується ізольований нуль, тобто коефіцієнт менший за абсолютною величиною від порогу, але не є коренем дерева нулів.

Якщо коефіцієнт закодовний як p або n, то ми заміняємо його для подальших проходів нулями. Крім того, вносимо його в список для підрядного проходу.

Підрядний прохід.

Поріг для підрядного проходу отримується зменшенням порогу для відповідного головного проходу вдвоє.

Якщо коефіцієнт більший від порогу, то він кодується значенням 1, а якщо менший – значенням 0.

Коефіцієнти кодуються в послідовних проходах. Для кожного проходу вибирається поріг, з яким порівнюються коефіцієнти. Якщо коефіцієнт більший за абсолютною величиною від порогу, то він кодується та заміняється нулем. У протилежному випадку коефіцієнт залишається для чергового проходу. Коли ми пройшли всі коефіцієнти, поріг зменшується і ми знову проходимо коефіцієнти, щоб додати більше деталей до вже закодованого зображення.

Розглянемо просте трирівневе хвилькове перетворення зображення розміру 8Х8 елементів. Матриця значень цього хвилькового перетворення наведена нижче.

Оскільки найбільше абсолютне значення коефіцієнтів у цій матриці рівне 63, ми можемо вибирати початковий поріг з проміжку (31,5;63]. Нехай початковий поріг дорівнює 32. Табл.8.1 описує опрацювання коефіцієнтів на першому основному проході.

Таблиця 8.1 Опрацювання коефіцієнтів на першому основному проході з порогом рівним 32.

Використовуються такі кодуючі символи: p – суттєвий додатній коефіцієнт, n – суттєвий від’ємний коефіцієнт, z – ізольований нуль, t – корінь дерева нулів.

Якщо маємо несуттєвий коефіцієнт без дочірніх коефіцієнтів, то в цьому разі ситуації t чи z не розрізняються. Ми ставимо символ t.

Далі наведені коментарі до табл.8.1.

1) Коефіцієнт має значення 63, яке більше від порогу 32 і додатнє. Тому використовується символ p. При декодуванні цього символа декодер замінить його на серднє значення проміжку [32,64), тобто на 48.

2) Хоча коефіцієнт 31 є несуттєвим відносно порогу 32, він має суттєве дочірнє значення на дві рівні нижче в смузі LH1 рівне 47. Тому цей коефіцієнт заміняється на символ z ізольованого нуля.

3) Величина 23 менша від 32 і всі дочірні значення (3,-12,-14,8) у смузі HH2 і всі коефіцієнти у смузі HH1 несуттєві. Коефіцієнт 23 заміняється на символ t дерева нулів, а для всіх коефіцієнтів у смугах HH2 та HH1 під час першого основного проходу не утворюються ніякі символи.

4) Величина 10 менша від 32 і всі її дочірні значення (-12,7,6,-1) також менші від порогу 32. Отже, утворюється символ t дерева нулів.

Зауважимо, що в цьому дереві порушується гіпотеза про “спадаючий спектр”, бо коефіцієнт –12 в підсмузі HL1 більший за абсолютною величиною від свого батьківського коефіцієнта 10. Проте ціле дерево має значення менші від порогу 32, а тому ще є деревом нулів.

5) Величина 14 несуттєва порівняно з 32. Її дочірні значення рівні (-1,47,-3,2). Оскільки її дочірнє значення 47 суттєве, то утворюється символ ізольованого нуля.

6) Зауважимо, що ніякі символи не були утворені для підсмуги HH2, яка при проходженні коефіцієнтів передує підсмузі HL1. Також зауважимо, що оскільки підсмуга HL1 не має дочірніх вершин, то між символами t чи z немає різниці. Ми використовуємо символ t.

7) Величина 47 суттєва порівняно з 32. Зауважимо, що для подальших основних проходів цей коефіцієнт буде замінений значенням 0; так що при черговому основному проході з порогом 16 батьківське значення 14 цього коефіцієнта буде замінене символом кореня дерева нулів.

Під час першого основного проходу, який використовує поріг 32, знайдено чотири суттєвих коефіцієнти. Ці коефіцієнти уточнюються під час першого підрядногопроходу. Перед першим підрядним проходом проміжок для всіх суттєвих коефіцієнтів – це проміжок [32,64). Перший підрядний прохід уточнить ці величини і віднесе їх до проміжку [32,48), що кодується символом 0, або до проміжку [48,64), що кодується символом 1. Тобто, межею для прийняття рішення є число 48. Порядок дій при першому підрядному проході ілюструється в табл.8.2.

Таблиця 8.2. Опрацювання коефіцієнтів на першому підрядному проході.

Перший коефіцієнт рівний 63 і розміщується у верхньому проміжкому, центр якого дорівнює 56. Другий коефіцієнт рівний 34 і розміщується в нижньому проміжку. Третій коефіцієнт 49 є у верхньому проміжку, а четвертий коефіцієнт 47 – у нижньому проміжку.

Матриця, яка може бути відтворена декодером, виходячи з даних першого основного та підрядного проходів наведена далі.

Опрацювання продовжується на другому основному проході з новим зменшеним вдвоє порогом 16. Під час цього проходу проглядаються лише ті коефіцієнти, які ще не були ідентифіковані як суттєві на першому проході. Крім того, ті коефіцієнти, які раніше були ідентифіковані як суттєві, заміняються нулями.

Видозмінена матриця значень хвилькового перетворення перед другим основним проходом наведена нижче

Таким чином, на другому основному проході коефіцієнт –31 у підсмузі LH3 кодується як суттєвий від’ємний, коефіцієнт 23 у підсмузі HH3 як суттєвий додатній, три коефіцієнти у підсмузі HL2, які раніше не були ідентифіковані як суттєві, всі кодуються як корені дерев нулів. Так само кодуються як корені дерев нулів усі чотири коефіцієнти у підсмузі LH2 та всі чотири коефіцієнти у підсмузі HH2. На цьому другий основний прохід завершується.

Список для другого підрядного проходу містить коефіцієнти (63,34,49,47,31,23), які перед цим проходом представляли три проміжки [48,64), [32,48) [16,32) кожен з шириною рівною 16.

Опрацювання уточнить кожне значення, утворивши два нових проміжки для кожного з трьох вказаних проміжків. Використовуючи середні значення проміжків як значення для відтворення, декодер утворить такі величини (60,36,52,44,28,20).

Матриця, яка може бути відтворена декодером, виходячи з даних першого та другого основного та підрядного проходів наведена далі.

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

Усі етапи кодування та декодування ілюструються далі.

Етапи роботи EZW кодера

поріг = 32

D = pnztpttttztttttttptt

S = 1 0 1 0

поріг = 16

D = ztnptttttttt

S = 1 0 0 1 1 0

поріг = 8

D = zzzzzppnppnttnnptpttnttttttttptttptttttttttptttttttttttt

S = 1 0 0 1 1 1 0 1 1 1 1 0

1 1 0 1 1 0 0 0

поріг = 4

D = zzzzzzztztznzzzzpttptpptpnptntttttptpnpppptttttptptttpnp

S = 1 1 0 1 1 1 1 1 0 1 1 0

0 1 0 0 0 0 0 1 1 1 0 1

1 0 1 0 0 0 1 0 0 1 0 1

0 1 1 0 0

поріг = 2

D = zzzzztzzzzztpzzzttpttttnptppttptttnppnttttpnnpttpttppttt

S = 1 0 1 1 1 1 0 0 1 1 0 1

0 0 0 1 0 1 1 1 1 1 0 1

0 1 1 0 1 1 0 0 1 0 0 0

0 0 0 0 0 1 1 0 1 1 0 1

1 0 0 1 1 0 0 0 1 1 1

поріг = 1

D = zzzttztttztttttnnttt

Етапи роботи EZW декодера

поріг = 16

рівень = 1

XX =

56 -40 56 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 40 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

поріг = 8

рівень = 2

XX =

60 -36 52 0 0 0 0 0

-28 20 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 44 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

поріг = 4

рівень = 3

XX =

62 -34 50 10 0 14 -14 0

-30 22 14 -14 0 0 0 0

14 14 0 -14 0 0 0 10

-10 0 -14 10 0 0 0 0

0 10 0 46 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 10 0 0 0 0 0 0

поріг = 2

рівень = 4

XX =

63 -35 49 11 7 13 -13 7

-31 23 15 -13 0 5 7 0

15 15 0 -13 5 -7 0 9

-9 -7 -15 9 5 0 0 0

-5 9 0 47 5 7 0 0

0 0 0 0 0 0 0 5

0 0 7 -5 0 7 0 7

5 11 5 7 0 0 -5 5

поріг = 1

рівень = 5

XX =

63 -34 49 10 7 13 -12 7

-31 23 14 -13 3 4 6 0

15 14 3 -12 5 -7 3 9

-9 -7 -14 8 4 -2 3 2

-5 9 0 47 4 6 -2 2

3 0 -3 2 3 -2 0 4

2 -3 6 -4 3 6 3 6

5 11 5 6 0 3 -4 4

поріг = 0.5

рівень = 6

XX =

63 -34 49 10 7 13 -12 7

-31 23 14 -13 3 4 6 -1

15 14 3 -12 5 -7 3 9

-9 -7 -14 8 4 -2 3 2

-5 9 -1 47 4 6 -2 2

3 0 -3 2 3 -2 0 4

2 -3 6 -4 3 6 3 6

5 11 5 6 0 3 -4 4

початкове зображення =

63 -34 49 10 7 13 -12 7

-31 23 14 -13 3 4 6 -1

15 14 3 -12 5 -7 3 9

-9 -7 -14 8 4 -2 3 2

-5 9 -1 47 4 6 -2 2

3 0 -3 2 3 -2 0 4

2 -3 6 -4 3 6 3 6

5 11 5 6 0 3 -4 4

відтворене зображення =

63 -34 49 10 7 13 -12 7

-31 23 14 -13 3 4 6 -1

15 14 3 -12 5 -7 3 9

-9 -7 -14 8 4 -2 3 2

-5 9 -1 47 4 6 -2 2

3 0 -3 2 3 -2 0 4

2 -3 6 -4 3 6 3 6

5 11 5 6 0 3 -4 4

різниця =

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

Наведений вище процес кодування продовжується з одного проходу до наступного, і може бути зупинений на будь-якому етапі. Для кращого представлення кодування може бути застосоване кодування Хафмена для подальшого стиску потоку на виході EZW шифратора.

Рис. нижче показує початкові зображення Lena та Barbara. Вони були стиснуті до 0,25 бітів/піксель (коефіцієнт стиску 32:1) за допомогою методів JPEG (з використанням дискретних косинусних перетворень) та EZW. Порівняємо відповідні відтворені зображення.

Для цього слід використати певні міри спотворення, які характеризують відхилення відтвореного зображення від початкового зображення.

Переважно в області опрацювання зображень використовують такі міри спотворення:

1) середньоквадратична похибка (mean square error - MSE)

2) відношення максимальний рівень сигналу -шум

(peak signal –to- noise ration PSNR) .

Одиницею вимірювання для міри PSNR є децибели.

У верхній частині рисунку наведені початкові зображення Lena та Barbara.

Посередині рисунку даються відтворені після стиску методом JPEG зображення:

- PSNR=31,6 дБ для зображення Lena

- PSNR=25,2 дБ для зображення Barbara

У нижній частині рисунку даються відтворені після стиску методом EZW зображення:

- PSNR=34,1 дБ для зображення Lena

- PSNR=27,6 дБ для зображення Barbara

Як бачимо, метод EZW дає кращі характеристики для відтворених зображень.

Читайте також:

1. D) методу мозкового штурму.
2. А. Розрахунки з використанням дистанційного банкінгу.
3. Адаптивні хвилькові перетворення : Хвилькові пакети.
4. Алгоритми побудови дерев екстремальної ваги
5. Апаратура методу природного магнітного поля
6. АРХІТЕКТУРНІ ТРАДИЦІЇ УКРАЇНСЬКИХ ДЕРЕВ‘ЯНИХ ЦЕРКОВ
7. Аудиторські ризики, пов’язані з використанням комп’ютерних інформаційних систем
8. Аутентифікація з використанням односторонніх функцій
9. Безпосереднє обчислення з використанням формули Ньютона-Лейбніца.
10. Біокомпозити та композиційні матеріали на основі відходів переробки деревини
11. Біотичні фактори та їх вплив на деревні рослини
12. Бухгалтерській облік валютних операцій банку з використанням платіжних карток

Переглядів: 1253