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

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

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

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

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

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

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

Спеціальність 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 дозволяє динамічно в просторі і в часі підвищувати дозвіл зображення. Під динамічним підвищенням дозволу зображення в просторі розуміється те, що ми можемо підвищити дозвіл тільки виділеної області зображення.

Під динамічним підвищенням дозволу зображення в часі розуміється те, що ми можемо підвищувати дозвіл виділеної області зображення поступово, крок за кроком.

Приклад використовування ROI показаний на малюнку 2.2.

Малюнок 2.2 - Приклад використовування ROI

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

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

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

Малюнок 2.4 - Ескіз, намальований користувачем, і оригінал, який

користувач хоче знайти

Очевидно, для вирішення подібної задачі необхідно ввести деяку метрику, яка дозволяла б здійснювати пошук зображення в базі даних за зразком. Тобто метрику, яка була б мірою схожості зразка і зображень в базі даних. В якості таких метрик можливо використовування L1 і L2 норм, формули яких записані нижче:

Очевидно, проте, що обчислення подібних метрик є украй трудомістким процесом. Так, зокрема, при пошуку зображення серед 20000 зображень тривалість роботи методу, заснованого на L1 нормі, в середньому складає 14 хвилин тоді як описуваний нижче метод, заснований на DWT, знаходить зображення в середньому за 0,5 секунди .

Основна ідея методу полягає в описі кожного зображення за допомогою 20 найбільших деталізуючих коефіцієнтів його вейвлет розкладання. Ці двадцять коефіцієнтів називаються ярликом зображення («ключовими словами» зображення в базисі вейвлетів) і саме по них ведеться пошук в базі даних.

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

Малюнок 2.5 - Ілюстрація роботи алгоритму пошуку

зображення за зразком

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

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

Малюнок 2.6 ілюструє ідею багатомасштабного редагування.

Малюнок 2.6 - Багатомасштабне редагування тривимірної моделі

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

Висновки

В курсовій роботі досліджувалося дискретне вейвлет перетворення зображень.

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

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

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

1.                      Столниц Э., ДеРоуз Т., Салезин Д. Вейвлеты в компьютерной графике. Теория и приложения. – Ижевск 2002

2.                      И.М. Дремин, О.В. Иванов, В.А. Нечитайло. Вейвлеты и их использование. – Успехи физических наук, 2001

3.                      Добеши И. Десять лекций по вейвлетам. - Ижевск 2001

4.                      Петров Александр. Вейвлеты и их приложения - Рыбинск, РГАТА 2007 - http://gmdidro.blogspot.com/2007/06/blog-post_16/

5.   Вадим Грибунин. Теория и практика вейвлет-преобразования - http://www.autex.spb.ru/wavelet/

6.                      Смоленцев Н.К. Основы теории вейвлетов. М.:ДМК Пресс, 2008. 448 с

7.                      Яковлев А.Н. Введение в вейвлет-преобраования:Учеб. пособие – Новосибирск:Изд-во НГТУ, 2003,-104с.

8.                      Н.М.Астафьева "Вейвлет - анализ: основы теории и примеры применения". : Успехи физических наук, том 1, 11 - 1996.

2