Дискретне вейвлет перетворення

ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНЙ ЗАКЛАД

«ЗАПОРІЗЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»

МІНІСТЕРСТВА ОСВІТИ І НАУКИ УКРАІНИ

КАФЕДРА МАТЕМАТИЧНОГО МОДЕЛЮВАННЯ

КУРСОВА РОБОТА

ДИСКРЕТНЕ ВЕЙВЛЕТ ПЕРЕТВОРЕННЯ ЗОБРАЖЕНЬ

Спеціальність 8.080202 – Прикладна математика

                                                                   Науковий керівник –

                                                                   ст. викладач Мухін В.В.

Запоріжжя - 2010

Зміст

Вступ

1. Дискретне вейвлет перетворення

1.1 Дискретне вейвлет перетворення одновимірного сигналу

1.2 Дискретне вейвлет перетворення зображень

2 Застосування дискретного вейвлет перетворення

2.1 Стиснення зображень. JPEG 2000

2.2 Пошук зображень за зразком

3.3 Багатомасштабне редагування

Висновки

Список використаних джерел.

Вступ

Вейвлети (від англ. wavelet), сплески - це математичні функції, що дозволяють аналізувати різні частотні компоненти даних. Слово «вейвлет» є калькою з англійського «wavelet», що означає в перекладі «маленька хвиля», або «хвилі, що йдуть один за одним». І той і інший переклад підходить до визначення вейвлетов. Вейвлети - це сімейство функцій, які локальні в часі і по частоті («маленькі»), і в яких всі функції виходять з однієї за допомогою її зсувів і розтягувань по осі часу (отже вони «йдуть один за одним»). Іноді вейвлети називають сплесками. Всі вейвлет-перетворення розглядають функцію (узяту будучи функцією від часу) в термінах коливань, локалізованих за часом і частоті. Вейвлет-перетворення звичайно ділять на дискретне вейвлет-перетворення (ДВП) і неперервне вейвлет-перетворення

(НВП).

Якщо розглядати застосування, то ДВП звичайно використовується для кодування сигналів тоді як НВП для аналізу сигналів. В результаті, ДВП широко застосовується в інженерній справі і комп'ютерних науках, а НВП в наукових дослідженнях. Вейвлет-перетворення в даний час прийняті на озброєння для величезного числа різноманітних застосувань, нерідко замінюючи звичайне перетворення Фурьє в багатьох застосуваннях. Ця зміна парадигми спостерігається в багатьох областях фізики, включаючи молекулярну динаміку , астрофізику сейсмічну геофізику, оптику турбулентність

квантову механіку обробку зображень аналізи кров'яного тиску, пульсу і ЕКГ, аналіз ДНК, дослідження білків , дослідження клімату загальну обробку сигналів розпізнавання мови ,комп'ютерну графіку і мультифрактальный аналіз .

В чисельному аналізі і функціональному аналізі дискретні вейвлет перетворення (ДВП) відносяться до вейвлет-перетворень, в яких вейвлети представлені дискретними сигналами (вибірками).

Перше ДВП було придумане угорським математиком Альфредом Хааром. Для вхідного сигналу, представленого масивом 2n чисел, вейвлет-перетворення Хаара просто групує елементи по 2 і утворює від них суми і різниці. Угрупування сум проводиться рекурсивно (у разі парної довжини послідовності сум) для утворення наступного рівня розкладання. У результаті виходить 2n - 1 різниця і 1 загальна сума.

Це просте ДВП ілюструє загальні корисні властивості вейвлетів. По-перше, перетворення (один рівень) можна виконати за О(n) операцій. По-друге, воно не тільки розкладає сигнал на деяку подібність частотних смуг (шляхом аналізу його в різних масштабах), але і представляє тимчасову область, тобто моменти виникнення тих або інших частот в сигналі. Разом, ці властивості характеризують швидке вейвлет-перетворення - альтернативу звичайному швидкому перетворенню Фурьє .

Найпоширеніший набір дискретних вейвлет-перетворень був сформульований бельгійським математиком Інгрід Добеши в 1988 році. Він заснований на використовуванні рекурентних співвідношень для обчислення все більш точних вибірок неявно заданої функції материнського вейвлета, з подвоєнням дозволу при переході до наступного рівня (масштабу).

В своїй основоположній роботі Добеши виводить сімейство вейвлетів, перший з яких є вейвлетом Хаара. З тих пір інтерес до цієї області швидко зріс, що привело до створення численних нащадків початкового сімейства вейвлетів Добеши. Інші форми дискретного вейвлет-перетворення включають непроріджене вейвлет-перетворення (де не виконується проріджування сигналів), перетворення Ньюленда (де ортонормированный базис вейвлетів виводиться із спеціальним чином побудованих фільтрів типу "top-hat" в частотній області). Пакетні вейвлет-перетворення також пов'язані з ДВП. Інша форма ДВП - комплексне вейвлет-перетворення.

1. Дискретне вейвлет перетворення

1.1 Дискретне вейвлет перетворення одновимірного сигналу

Цифрова обробка сигналу вимагає його дискретизації. Існує дискретна форма вейвлет перетворення. В даному розділі нами використовуватиметься

один з найпростіших вейлвет базисів – базис Хаара. Розглянемо дискретизирований і квантований сигнал (сигнал 1.1) – малюнок 1.1 (а).

Поступово усереднюватимемо даний сигнал, усереднюючи попарно його відліки. Таким чином, кожний крок усереднювання скорочуватиме дозвіл сигналу в 2 рази (тобто для його уявлення буде потрібен в два рази менше число відліків). Проте при такому усереднюванні ми втрачаємо частину інформації про сигнал, для того, щоб відновити сигнал після усереднювання нам буде потрібно додаткова інформація. Зберігатимемо різниці між усередненим відліком і відліками, з яких усереднений відлік полягає при більш високому дозволі. Дані різниці показують деталі сигналу – його флуктуації навкруги середнього при даному рівні дозволу. На малюнку 1.1 деталізуюче коефіцієнти показані в правій частині малюнків 1.1 (б, в, г, д).

Тепер скориставшися деталізуючими коефіцієнтами ми зможемо відновити колишньою форму сигналу.

Малюнок 1.1 – Усереднювання дискретизированного сигналу 1.1

Таким чином, для того, щоб перейти від одного, більш низького рівня дозволу до рівня, що більш деталізується, нам потрібно знати усереднені від

ліки сигналу і деталізуючі коефіцієнти. Помітимо, що сигнал 1.1, зображений на малюнку 1.1 (а), може бути представлений таким чином - ,

де - деякі базисні функції, а - координати сигналу 1.1 в цьому базисі. Очевидно, що якщо ми виберемо в якості одиничну сходинку, зображену на малюнку 1.2 (а), то, зсовуючи необхідне число раз, ми зможемо представити сигнал 1.1 за допомогою суми таких одиничних сходинок. Таким чином, ми ввели базис, в якому ми можемо представити сигнал 1.1.    Відзначимо, що оскільки функції , зображені на малюнку 1.2, не перетинаються між собою, то побудований нами базис є ортогональним. Функції називаються масштабуючими функціями.

                                                 Малюнок 1.2

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

Розглянемо конкретний сигнал, заданий наступним вектором значень – [9 7 3 5]. За допомогою масштабуючої функції Хаара ми можемо представити сигнал так, як це зображено на малюнку 1.3.

Малюнок 1.3 – Представлення початкового сигналу в базисі Хаара

Проведемо процедуру декомпозиції сигналу на дві частини – усереднений сигнал з двоє зменшеним дозволом і деталізуючі коефіцієнти.

Отримаємо наступний вектор - = [8 4 | 1 –1] представлення якого в базисі Хаара за допомогою масштабуючої функції і вейвлетов зображено на малюнку 1.4.

Малюнок 1.4 – Представлення усередненого сигналу в базисі Хаара

Виділимо у векторі [8 4 | 1 –1] частину, що представляє усереднений сигнал (перша половина вектора), і проведемо щодо неї повторне усереднювання і знаходження деталізуючих коефіцієнтів. Отримаємо наступний вектор – [6 | 2 1 –1] представлення якого в базисі Хаара за допомогою масштабуючої функції і вейвлетов зображено на малюнку 1.5.

Малюнок 1.5 - Представлення двічі усередненого сигналу в базисі Хаара

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

            Малюнок 1.6 – Представлення сигналу в базисі Хаара

Відзначимо, що якщо ми відновлюватимемо сигнал після його розкладання в базис Хаара, то ми можемо зупинити процес відновлення «на півдорозі» і отримати представлення сигналу із заданим дозволом. Іншими словами нами отриманий математичний інструмент зміни дозволу сигналу.

1.2 Дискретне вейвлет перетворення зображень

Розглянемо вейвлет перетворення зображень. Загальна ідея вейвлет перетворення багатовимірних сигналів полягає в декомпозиції багатовимірного сигналу до одновимірних сигналів і, подальшого їх вейвлет перетворення з композицією результатів. Існують два методи такого перетворення - неперервне і дискретне вейвлет перетворення. Ці методи розрізняються порядком застосування вейвлет перетворення до декомпозованих одновимірних сигналів. Нижче розглянуто дискретне вейвлет перетворення.

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

Нижче приведен алгоритм дискретного стиснення. 

procedure NonstandardDecomposition(c:array[1..2j,1..2k] of reals)

  c c/2j (нормалізуємо вихідні коефіцієнти)

g  2j

while g≥2 do

   for row1 to g do

     DecompositionStep(c[row,1…g])

end for

for col  1 to g do

        DecompositionStep(c[1…g,col])

end for

gg/2

end while

end procedure.

procedure DecompositionStep(c:array[1…2j] of reals)

  for i1 to 2j/2 do

   c’[i]  (c[2i-1]+c[2i])/

  c’[2j/2+i]  (c[2i-1]+c[2i])/

end for

c c’

end procedure.

Ілюстрація цього методу представлена на малюнку 1.7.

Малюнок 2.7 - Дискретне вейвлет перетворення зображення

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

На малюнку 1.7 показаний також псевдокод рекурсивного застосування DWT до зображення. При цьому на кожному кроці перетворення зручно представляти зображення не як матрицю, а як вектор.

Псевдокодова процедура виконання дискретного відновлення:

procedure NonstandardReconstruction(c:array[1…2j,1…2k] of reals)

g2

while g≤2j do

   for col1 to g do

  ReconstructionStep(c[1…g,col])

end for

for row1 to g do

  ReconstructionStep(c[row,1…g])

end for

g2g

end while

c2jc

end procedure.

procedure ReconctructionStep(c:array[1…2j] of reals)

for i  1 to 2j/2 do

c’[2i-1]  (c[i]+c[2j/2+i])/

c’[2i]  (c[i]-c[2j/2+i]/

end for

c  c’

end procedure.

2 Застосування дискретного вейвлет перетворення

2.1 Стиснення зображень. JPEG 2000

Основна ідея, що використовується при стисненні сигналів за допомогою вейвлет перетворення, полягає в тому, щоб відкидати деталізуючі коефіцієнти, значення яких близькі до нуля. В 1999 році був розроблений новий стандарт стиснення зображень, названий JPEG 2000 і покликаний замінити стандартний алгоритм стиснення JPEG. Однією з основних відмінностей JPEG 2000 від JPEG є зміна основної процедури перетворення зображення. Тоді як в JPEG використовувалося перетворення Фурье і в

JPEG 2000 використовується вейвлет перетворення, що дозволило не тільки поліпшити візуальну якість зображення, що демонструє малюнок 2.1, але і додати деяку цікаву функціональність, принципово не досяжну в JPEG.

Малюнок 2.1 - Порівняння візуальної якості зображень стислих по алгоритмах JPEG і JPEG 2000

Однією з таких додаткових функції є ROI (Region Interest). ROI дозволяє динамічно в просторі і в часі підвищувати дозвіл зображення. Під динамічним підвищенням дозволу зображення в просторі розуміється те, що ми можемо підвищити дозвіл тільки виділеної області зображення.