Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Систематизація вейвлет-перетворень
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2004
Тип роботи:
Курсовий проект
Предмет:
Методи, алгоритми та засоби цифрової обробки сигналів та зображень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Курсовий проект
з курсу: „Методи, алгоритми та засоби цифрової обробки сигналів та зображень”
на тему:
“Систематизація вейвлет-перетворень”
Львів – 2004 Анотація
В роботі проводиться спроба систематизувати найбільш розповсюджені на сьогоднішній день різновиди вейвлет-перетворень. Пропонується систематизація по наступних ознаках: по типу (дискретному або неперервному) оброблюваного сигналу, за розміром сигналу, по наявності або відсутності надлишкової інформації, наявності або відсутності властивості збереження норми і ін. Проводиться порівняння прийнятих способів обробки сигналів, визначених на кінцевих інтервалах, а також відомих форм запису перетворень. А також наводиться приклад застосування вейвлет-перетворень сучасною наукою.
Зміст
Вступ.................................................................................................................................
5
1.
Два “класичні” перетворення....................................................................................
7
1.1. Неперервне вейвлет-перетворення....................................................................
7
1.2. Ортогональне діадне (“дискретне”) вейвлет-перетворення.........................
8
1.3. Ортогональний багатомасштабний аналіз......................................................
9
1.4. Задачі, що вимагають і не вимагають зворотнього перетворення.............
12
2.
“Неперервні” і “дискретні” перетворення...............................................................
12
2.1. Аналог неперервного перетворення для дискретних сигналів...................
13
2.2. Діадне перетворення дискретних сигналів......................................................
13
3.
Перетворення з надмірною інформацією. Вейвлет-фрейми................................
16
4.
Неортогональні вейвлети............................................................................................
18
4.1. Необхідність послаблення вимоги ортогональності......................................
18
4.2. Неортогональний багатомасштабний аналіз...................................................
19
4.3. Біортогональні перетворення..............................................................................
19
4.4. Напівортогональні перетворення.......................................................................
21
5.
Перетворення, що зберігають і не зберігають норму............................................
22
6.
Перетворення сигналів, визначених на кінцевих інтервалах ............................
23
7.
Способи запису вейвлет-перетворень.......................................................................
27
7.1. Матрична форма запису.......................................................................................
27
7.2. Порівняння форм запису. Особливості реалізації алгоритмів....................
29
8.
Багатовимірні і багатоканальні перетворення......................................................
30
8.1. Найпростіші багатовимірні перетворення.......................................................
30
8.2. Загальний вигляд розбиття простору................................................................
32
8.3. Загальний вигляд d-вимірного M-канального перетворення.....................
33
8.4. Деякі окремі випадки перетворень....................................................................
34
9.
Підходи до аналізу нестаціонарних сигналів..........................................................
35
9.1. Методи обробки нестаціонарних сигналів.......................................................
35
9.2. Короткий огляд перетворення Фурє..................................................................
35
9.3. Основні положення вейвлет-аналізу.................................................................
36
9.3.1. Методи обчислення неперервного вейвлет-перетворення..................
39
9.3.1.1. В часовій області......................................................................................
39
9.3.1.2. В частотній області..................................................................................
39
9.3.2. Вибір материнського вейвлета...................................................................
40
10.
Визначення вузлових точок ЕКГ на основі неперервного вейвлет-перетворення...................................................................................................................
41
10.1. Стандарти опису і позначення ЕКГ.................................................................
41
10.2. Постановка задачі ідентифікації.......................................................................
41
10.3. Побудова моделі ідеального ЕКГ......................................................................
42
10.4. Аналіз моделі ЕКГ................................................................................................
42
10.4.1. В системі “Matlab”.......................................................................................
42
10.4.2. З використанням “Vision”.........................................................................
43
10.4.3. Порівняльний аналіз отриманих результатів.......................................
44
Висновок..........................................................................................................................
45
Список використаної літератури...............................................................................
46
Додаток 1..........................................................................................................................
47
Додаток 2..........................................................................................................................
48
Вступ
Під вейвлет-перетворенням (wavelet transform), або сплеск-перетворенням, розуміють розкладання сигналу за системою вейвлетів (wavelet), або сплесків, — функцій, кожна з яких є зсунутою і масштабованою (стислою або розтягнутою) копією однієї функції — породжуючого вейвлета (mother wavelet) [1-3, 5, 7, 11, 16, 18, 19, 22]. При цьому в найбільш загальній постановці не конкретизується не тільки сам породжуючий вейвлет, але і це, які саме його копії беруть участь в розкладанні. Звідси очевидно, що термін "вейвлет-перетворення" є позначенням цілого класу розкладань, або навіть надкласу, оскільки існуючі види вейвлет-перетворень часто досить сильно відрізняються один від одного і визначеннями, і наявними властивостями, і колом додатків.
На жаль, в численній літературі, присвяченій вейвлетам, до питання термінології, структуризації і систематизації автори часто відносяться досить недбало, а робіт з детально і акуратно викладеною теоретичною базою не так вже багато. До прикладу такої недбалості можна віднести, наприклад, той факт, що термін "дискретне вейвлет-перетворення" історично використовується для позначення декількох різних конструкцій. У ряді робіт, націлених в першу чергу на прикладні задачі (наприклад [19]), для кожного окремого випадку описується який-небудь конкретний тип перетворення. В результаті читач одержує достатньо докладний опис для рішення визначеного кола задач, проте спробувати узагальнити цю інформацію і вийти за рамки запропонованого кола на основі такого викладу непросто. З другого боку, є і роботи, присвячені строгому викладенню теорії вейвлет-аналізу (наприклад [22]), але, переобтяжені формулами і теоремами, вони навряд чи представляють інтерес для фахівців в прикладних областях.
Крім того, в різних джерелах зустрічаються різні форми запису перетворень. Перехід від однієї форми до іншої може показатися неочевидним, тим паче, що форми запису перетворень, взагалі кажучи, не еквівалентні в тому значенні, що існують різновиди перетворень, які можуть бути описані в термінах однієї форми і не описуються в термінах іншої форми запису.
В даній роботі робиться спроба усунути деякі існуючі неоднозначності в термінології. Запропоновано систематизувати існуючі перетворення по ряду ознак: по типу оброблюваного сигналу (неперервному або дискретному) і по наявності або відсутності надлишкової інформації — така класифікація пропонується замість умовного розподілу перетворень на неперервні і дискретні; по типу базисів у функціональних просторах для перетворень без надлишкової інформації (ортогональний, напівортогональний, біортогональний) — це, мабуть, єдина загальноприйнята класифікація; по наявності і відсутності властивості збереження норми; по розмірності перетворення і по числу каналів — дана систематизація грунтується на розширенні класу перетворень без надлишкової інформації, запропонованому в роботі [17].
Окрім цього, описуються і порівнюються дві відомі форми запису вейвлет-перетворень, обговорюються особливості реалізації алгоритмів обчислення вейвлет-перетворень, які можуть бути побудовані на основі цих записів. Також описуються і порівнюються два підходи по обчисленню вейвлет-перетворень на обмежених інтервалах.
Систематизація перетворень має не тільки теоретичний, але і практичний інтерес. Вона дозволяє реально оцінити різноманіття конструкцій вейвлетів, виділити (а можливо, і сконструювати новий) тип перетворення, переважний для вирішення конкретної прикладної задачі, у тому числі і в значенні ефективності реалізовуючого його алгоритму.
Робота включає в себе викладення найважливіших елементів базової теорії вейвлет-аналізу, тому вона доступна як фахівцю, так і читачу, що не має достатньої підготовки в цій області, але виявляє до неї цікавість.
Для ряду основних понять вейвлет-аналізу дається загальноприйнятий англомовний еквівалент.
На сьогоднішній день одним з найпоширеніших методів діагностики і розпізнавання серцево-судинних захворювань є електрокардіографія. Сигнал ЕКГ характеризується набором зубців, по часових і амплітудних параметрах по яких ставиться діагноз. До недавнього часу процедуру знаходження характеристик зубців виконував лікар-кардіолог, використовуючи при цьому тільки креслярські обладнання. Така схема достатньо проста і надійна, але вимагає багато часу, і вона працювала напротязі великого періоду часу за відсутності альтернативних підходів до рішення даної задачі.
З розвитком комп'ютерів стали з'являтися спеціалізовані комплекси, що дозволяють виявляти серцеві захворювання, на основі автоматизованого аналізу часових параметрів ЕКГ. Аналіз основних характеристик електрокардіограми людини проводиться на базі алгоритму неперервного вейвлет-перетворення.
Також в цій роботі розглядається питання ідентифікації особливостей ЕКГ, як одного з кроків комплексного аналізу сигналу. Це вельми важливий етап оскільки допущення помилки тут сильно позначається на лікарському висновку.
Два "класичні" перетворення.
На початку розглянемо два види перетворень, які утворюють фундамент теорії вейвлет-аналізу. Переважна більшість існуючих видів вейвлет-перетворень в тому або іншому ступені є або узагальненнями, або окремими випадками цих об'єктів.
1.1. Неперервне вейвлет-перетворення.
Неперервним вейвлет-перетворенням (continious wavelet transform) функції f(x) є L2(R) називають функцію двох змінних
(1)
де вейвлети ψа,b(х)≡ ψ(а,Ь,х) є масштабованими і зсунутими копіями породжуючого вейвлета ψ(х) є L2(R):
(2)
Якщо для породжуючого вейвтета виконується умова
(3)
(ψ(х) — образ Фурьє вейвлета ψ(х)), то перетворення (1) оборотнє, тобто існує зворотнє неперервне вейвлет-перетворення
(4)
Таким чином, неперервне вейвлет-перетворення — це розкладання сигналу по всіх можливих зсувах і стисках (розтягуваннях) деякої функції.
Часто вейвлет-аналіз розглядають в порівнянні з аналізом Фурьє. Пригадаємо, що перетворення Фурьє — це розкладання сигналу по зсувах і стисках (розтягуваннях) гармонійної функції. Сигналу f(x) ставиться у відповідність комплекснозначна функція f(ω). Для кожної частоти ω аргумент цієї функції визначає фазовий зсув, а модуль — амплітуду відповідної гармонічної складової.
Змінна a у виразах (1). (2) і (4) визначає масштаб вейвлета і є аналогом частоти в аналізі Фурьє. Змінна b визначає величину зсуву вейвлета. Таким чином, для кожної пари а і b функція W(а,b) визначає амплітуду відповідного вейвлета.
На відміну від аналізу Фурьє, конкретний вид вейвлета не обговорюється. Проте, як правило, у випадку вейвлета беруться неперіодичні, локалізовані в просторі функції, наприклад функції, що мають один або два близько розташованих глобальних екстремуми і швидко затухаючі (або що перетворюються в 0) на нескінченності. Мінімальною вимогою до таких функцій звичайно є наявність одного нульового моменту (vanishing moment), тобто рівність нулю інтегралу від цієї функції по всій області її визначення.
Поширений приклад вейвлета — друга похідна гауссиана (функції густини нормального розподілу), яка отримала назву "мексиканський капелюх":
(5)
У разі аналізу Фурьє кожній частоті відповідає всього одна гармонійна складова. У разі вейвлет-аналізу кожній частоті відповідає безліч зсунутих один відносно одного функцій. Якщо сигнал має особливість, наприклад розрив, то на наявність цього розриву вкажуть відносно високі значення амплітуд при високих частотах образу Фурьє цього сигналу. В той же час у вейвлет-образу високі амплітуди будуть тільки у тих вейвлетів, екстремуми яких виявляться поблизу точки розриву. Отже, можна не тільки визначити наявність особливості, але і точку, в якій вона має місце.
Таким чином, можна сказати, що аналіз Фурьє є частотним, а вейвлет-аналіз — частотно-просторовим аналізом сигналу.
1.2. Ортогональне діадне ("дискретне") вейвлет-перетворення.
Кількість копій породжуючого вейвтета, необхідних для оберненого розкладання, можна істотно скоротити. При цьому, однак, вимагається накладати додаткові умови на породжуючий вейвлет.
Поширений випадок — обчислення значень W(a,b) тільки для а і b вигляду
Замість безперервної функції (1) виходить скінченна кількість значень:
(6)
де
(7)
Зворотнє перетворення виглядає таким чином:
(8)
Помітимо, що значення, обчислювані по формулі (6), є узагальненими коефіцієнтами Фурьє розкладання сигналу f(x) за системою функцій (7), а вираз (8) є узагальнений ряд Фурьє f(x) відносно системи (7). Отже, щоб представлення (8) мало сенс, вейвлет ψ(х) повинен бути таким, щоб породжена ним система (7) була ортонормованим базисом в L2(R).
Формули (6), (7) і (8) визначають відоме діадне (dyadic) ортогональне вейвлет-перетворення. Іноді в літературі воно називається дискретним, що викликає певну неоднозначність, оскільки так само іменуються і вейвлет-перетворення дискретних сигналів (див. п. 3).
З одного боку, діадне перетворення є окремим випадком неперервного перетворення. З другого боку, це абсолютно інший об'єкт з особливою структурою і специфічними властивостями. Якщо продовжувати порівняння з аналізом Фурьє, то діадне перетворення є аналогом не дискретного перетворення Фурьє (це ще один аргумент на користь того, що називати це вейвлет-перетворення дискретним потрібно з відомою обережністю), а ряду Фурьє.
Представлення (8) має чітко виражену багаторівневу ієрархічну структуру. При фіксованому індексі i (назвемо його рівнем дозволу або дозволом) масштаб вейвлетів не міняється (тобто всі вейвлети для кожного дозволу є зсунутими копіями один одного). При збільшенні дозволу на 1 величина зсуву зменшується вдвічі і вдвічі стискаються вейвлети (саме тому перетворення називається діадним). Схожу структуру має і ряд Фурьє, але в ряді Фурьє кожному рівню дозволу відповідає лише пара гармонійних функцій, зсунутих один щодо одного на половину періоду.
Будь-яку часткову суму ряду Фурьє можна вважати огрубленим (низькочастотним) наближенням початкового сигналу. Найгрубішим початковим наближенням є перший член — константна функція.
У представленні (8) немає початкового наближення. Але як таку можна взяти будь-яку часткову суму, наприклад, суму по і від -∞ до -1:
Існує функція φ(х), така, що безліч її зсувів утворює ортонормовану систему, і сигнал f(0)(x) можна точно представити у вигляді розкладання по цій системі, тобто
де
і
Крім того, ця система ортогональна системі вейвлетів, відповідних рівню дозволу від 0 і вище і утворює з нею ортонормований базис в L2(R). Якщо функції φj(x) задовольняють всім цим умовам, то вони називаються скейлінг-функціями (scaling function) або масштабними функціями, а φ(х) — породжуючою скейлінг-функцією (father scaling function). Більш строго скейлінг-функції, вейвлети і співвідношення між ними розглядаються в п. 1.3.
За допомогою скейлінг-функцій замість представлення (8) було отримано еквівалентне йому представлення:
(9)
По структурі це представлення вже істотно відрізняється від структури неперервного вейвлет-перетворення, оскільки містить вже два види функцій.
Найпростішим прикладом ортогональної системи вейвлетів є система Хаара, що породжують скейлінг-функції і вейвлет який задається наступними формулами:
(10)
Діадне вейвлет-перетворення на основі системи Хаара називається перетворенням Хаара.
1.3. Ортогональний багатомасштабний аналіз.
Діадне вейвлет-перетворення можна вивести не тільки як окремий випадок неперервного перетворення, але і за допомогою конструкції, що називається багатомасштабним аналізом (multiresolution analysis) або короткомасштабним аналізом.
Ортогональним багатомасштабним аналізом в L2(R) називається послідовність замкнутих підпросторів Vi є L2(R), і є Z, таких, що:
інтеграл якого не рівний нулю, такий, що послідовність {φ(х-j)}jєZ є ортонормованим базисом в V(0): елемент φ(х) називається породжуючою скейлінг- функцією.
Розглянемо деякі властивості багатомасштабного аналізу, витікаючі безпосередньо з даного визначення.
1. З підпунктів 1 і 4-6 визначення виходить, що знайдуться такі числа , що
(11)
Цей вираз називається масштабним співвідношенням (refinement relation) для скейлінг-функцій.
2. Для будь-кого і є Z послідовність де, є ортонормованим базисом в просторі V(i). Функції називаються скейлінг-функціями.
3. Якщо породжуюча скейлінг-функція, φ(x) належить множині L1(R) і нормалізована, тобто
то з точністю до значень на множині міри нуль ця функція єдиним чином визначається рівнянням подрібнення (11), тобто набором значень {hk}kєK (як відомо значення на множині міри нуль не впливає на результат інтегрування, тому така точність визначення функції являється достатньою).
Для кожної пари підпросторів , багатомасштабного аналізу повинен існувати підпростір Wі таке, що
Такі підпростори можна назвати уточнюючими або деталізуючими в тому значенні, що вони містять уточнюючу інформацію, необхідну для переходу від рівня дозволу i до рівня і +1. Справедливо наступне:
Якщо існує елемент φ(х)є W(0) такий, що послідовність {ψ(х — j)}jєZ єортонормованим базисом в W(0), то цей елемент називається породжуючим вейвлетом.
Якщо ψ(х)є W(0) — породжуючий вейвлет, то набір функцій утворює ортонормований базис в L2(R). Тут. Функції з цього набору називаються вейвлетами. Деталізуючі підпростори , прийнято також називати вейвлет-просторами.
Очевидно, що породжуючий вейвлет ψ(х), є елементом простору V(1). Отже, знайдуться такі числа , що
(12)
Це співвідношення є масштабним співвідношенням для вейвлетів. Воно схоже на масштабне співвідношення для скейлінг-функцій (11), але має важливу відмінність: перше є рівнянням (в лівій і правій частині знаходиться одна і та ж функція), друге — вираженням однієї функції через іншу. Таким чином, породжуючий вейвлет ф(х), з точністю до значень на множині міри нуль визначається коефіцієнтами {gl}l є L, якщо була визначена породжуюча скейлінг-функція φ(x), а вона в свою чергу, визначається коефіцієнтами {hk}kєK співвідношення (11). Отже, система скейлінг-функцій і вейвлетів може бути повністю визначена двома наборами коефіцієнтів: {hk}kєK і {gl}l є L .
Скорочено надалі використовуватимемо наступні позначення для наборів коефіцієнтів:
Зауваження. Завжди можна вважати, що K=Z і L=Z, тобто коефіцієнти в наборах h і g були визначені для будь-якого цілого індексу. Якщо це не так, то набори довизначаються на всій множині цілих індексів нульовими елементами.
Приклад. Системі Хаара (10) відповідають наступні коефіцієнти:
(13)
Інший приклад можна знайти в кінці п. 3.2.
Оскільки набір функцій є ортонормованным базисом в L2(R), то будь-яку функцію f(x) є L2(R) можна єдиним чином представити у вигляді розкладання
де
що в точності відповідає формулам (8), (6) і (7).
Значення , називаються деталізуючими коефіцієнтами або вейвлет-коэффициентами.
Помітимо, що для будь-якого
отже
В просторі існує базис скейлінг-функцій, отже, набір функцій
також є ортонормованим базисом в (називатимемо такий базис комбінованим). Тоді справедливо наступне представлення:
(14)
де
Поклавши і0 = 0 і позначивши , одержуємо в точності формулу (9).
Представлення (14) можна розглядати як розкладання сигналу f(x) на дві проекції — проекцію на простір (перший доданок формули) і проекцію на ортогональне доповнення до L2(R) (другий доданок). Структура просторів така, що проекція сигналу на перший простір є огрубленим (або, користуючись термінологією аналізу Фурьє, низькочастотним) представленням цього сигналу, а другий — високочастотним, тобто що містить уточнюючу (деталізуючу) інформацію про сигнал, втрачену при проектуванні на простір . Очевидно, що чим вище значення і0, тим більше інформації, що міститься в другому доданку формули (14), "перетікає" в перший.
Проекцію сигналу на простір називатимемо представленням (або наближенням) сигналу з дозволом і0 . Окрім власне проекції, так можна називати набір коефіцієнтів розкладання цієї проекції по базисних скейлінг-функціях, оскільки при фіксованому базисі скейлінг-функцій коефіцієнти однозначно визначають таке наближення.
Таким чином, за допомогою ортогонального багатомасштабного аналізу були не тільки виведені формули ортогонального діадного вейвлет-перетворення, але і дані більш строгі визначення базисними функціями цього перетворення — скейлінг-функціями і вейвлетами, встановлені співвідношення між цими функціям, була отримана достатньо наочна інтерпретація перетворення як послідовності проекцій на вкладені підпростори.
Надалі скорочено будуть використані наступні позначення для послідовностей підпросторів і функцій:
1.4. Задачі, що вимагають і не вимагаючі зворотнього
перетворення.
У перетворень (1) і (6) є ше одна важлива відмінність, яку варто розглянути окремо.
Неперервне перетворення містить в собі дуже великий об'єм інформації. Дійсно, сигналу, визначеному на R, ставиться у відповідність функція, визначена на R×R. Неперервне перетворення застосовується в задачах, де потрібен аналіз сигналів, виявлення особливостей, періодичної залежності, локальних обурень і т.д. Обчислення ж цього перетворення є достатньо трудомістким. Крім того, в додатках обчислюється не вся функція W(а, b), а лише її значення в певних діапазонах. Очевидно, що про оборотність у такому разі говорити дуже важко. Але в задачах, де неперервне перетворення застосовується, необхідне тільки отримання вейвлет-образу або його частини, виконувати зворотнє перетворення не вимагається.
Діадне перетворення, навпаки, містить відносно мало інформації. Неперервному сигналу ставиться у відповідність дискретна функція, тобто не більше ніж злічена безліч чисел. Проте, цієї інформації достатньо, щоб перетворення було зворотнім (при накладенні певних умов на вейвлети). В задачах, де відновлення сигналу необхідне (обробка сигналів, стиснення інформації та ін.), використовується саме це перетворення або його модифікації. Можливості ж даного перетворення в області аналізу сигналів істотно нижчі, ніж у неперервного перетворення.
2. "Неперервні" і "дискретні" перетворення.
Щоб уникнути неоднозначності, є сенс говорити не про неперервне або дискретне перетворення, а про перетворення безперервних або дискретних сигналів (нагадаємо, що визначення неперервності для функцій і сигналів відрізняються — неперервним сигналом називається функція з неперервною областю визначення).
Вейвлет-перетворення, задані формулами (1) і (6), були визначені для функцій з L2(R), тобто для неперервних сигналів. Проте в обох перетворень є аналоги для дискретних сигналів.
2.1. Аналог неперервного перетворення для дискретних сигналів.
Будь-який дискретний сигнал можна представити у вигляді неперервного сигналу — шматково-постійної функції
Застосуємо до такого сигналу неперервне вейвлет-перетворення (1)-(2).
Розпишемо скалярний вираз з (1), підставивши в нього (2):
Підставляючи вираз для s(х), одержуємо
(15)
Формально можна обчислити значення Ws(а,b) для будь-яких вагомих а (окрім 0) і b. Реально інтерес представляють тільки цілочисельні зсуви b і раціональні позитивні масштабуючі коефіцієнти а.
Якщо ж s — кінцевий сигнал довжини N, тобто, то вираз (15) перетворюється на кінцеву суму. Розглядаються тільки цілочисельні зсуви від 0 до N-1. Масштабний коефіцієнт може бути будь-яким, відмінним від 0, проте інтерес представляє діапазон від 1 до N, причому для додатків достатньо розглядати тільки цілі коефіцієнти. Одержуємо:
(16)
Таким чином, сигналу довжини N була поставлена у відповідність матриця розміру N× N.
Перетворення (15) і (16) є по суті чисельною реалізацією неперервного перетворення (1) і не використовуються для задач, що вимагають відновлення сигналу, тому питання про оборотність цих перетворень тут не розглядається.
2.2. Діадне перетворення дискретних сигналів.
Діадне перетворення дискретних сигналів є, мабуть, найпоширенішим перетворенням. Саме воно частіше всього і називається в літературі дискретним. Це перетворення можна розглядати як окремий випадок перетворення (6) -(7) для спеціального типу сигналів, аналогічно тому, як це було зроблено в п. 3.1. Але існує інший підхід, заснований на властивостях багатомасштабного аналізу.
З масштабного співвідношення (11) виходить, що будь-яка скейлінг-функція рівня дозволу i передставлена у вигляді лінійної комбінації скейлінг-функцій рівня і + 1. Дійсно,
(17)
Отже,
Аналогічно, з масштабного співвідношення для вейвлетів (12) одержуємо вираз
(18)
звідки витікає, що
Таким чином, коефіцієнти при скейлінг-функціях і вейвлет-коефіцієнти будь-якого рівня дозволу і виражаються через коефіцієнти при скейлінг-функціях рівня дозволу і + 1:
(19)
Були отримані рекурсивні формули обчислення коефіцієнтів при скейлінг-функціях і вейвлетах рівня і по коефіцієнтах при скейлінг-функціях рівня і+1. Виникає питання про перший крок, тобто про обчислення коефіцієнтів при скейлінг-функціях деякого початкового рівня дозволу i1(помітимо, що в даному випадку під „початковим” розуміється не найнижчий (грубий), а навпаки, високий рівень дозволу).
Для неперервних сигналів найвищий рівень дозволу в загальному випадку рівний +∞. Тому як початковий крок доводиться брати коефіцієнти представлення сигналу з деяким кінцевим дозволом і1. Очевидно, що точність представлення тим вища, чим більше було вибрано значення і1 . Коефіцієнти початкового представлення знаходяться за визначенням:
Якщо вхідний сигнал дискретний, то як коефіцієнти при скейлінг-функціях рівня дозволу i1, можна узяти власне компоненти цього сигналу. Зрозуміло, що в цьому випадку значенням i1 може бути довільне ціле число, на точність представлення воно не впливає.
Коефіцієнти при скейлінг-функціях дозволу i1 були визначені, і по формулах (19) можна обчислити коефіцієнти розкладання для будь-якого дозволу, меншого i1. Очевидно, що на практиці виконується кінцеве число кроків. Якщо перервати обчислення на деякому рівні i0<i1, то в результаті буде отримано представлення сигналу з дозволом i0 (тобто коефіцієнти при скейлінг-функціях ), а також деталізуючі коефіцієнти.
Отримаємо наступну модифікацію формул (19):
(20)
Формули (19) і (20) визначають пряме дискретне діадне вейвлет-перетворення.
Тепер отримаємо формули для відновлення сигналу (зворотнього перетворення). Підставимо (17) і (18) в очевидну тотожність
(21)
Отримаємо:
Зсунемо в правій частині індекс k на 2j і змінимо порядок сумування:
Поміняємо в правій частині позначення індексів k і j:
Таким чином, був отриманий вираз для коефіцієнтів при скейлінг-функціях рівня дозволу i+1 через коефіцієнти при скейлінг-функціях і вейвлет-коефіцієнти рівня дозволу i:
(22)
Маючи представлення сигналу з дозволом i0 і набір вейвлет-коефіцієнтів, отриманих по формулах (20), можна за допомогою рекурсивної формули (22) відновити сигнал з будь-яким дозволом від i0 + 1 до i1:
(23)
Формули (22) і (23) визначають зворотнє дискретне діадне вейвлет-перетворення.
Введемо дещо іншу форму запису для прямого і зворотнього дискретного діадного перетворень. Ця форма достатньо поширена в літературі, присвяченій додаткам вейвлет-аналізу в області обробки сигналів. Скористаємося наступними позначеннями:
Введемо оператори і , визначені для цілих невід’ємних значень п. Перший оператор з вхідного сигналу s залишає тільки елементи з індексами типу . Другий оператор додає після кожного елемента вхідного сигналу п-1 нульових елементів. Припустимо, що при п = 0 і п = 1 обидва оператори не змінюють сигнал. Введемо також операцію s* перенумерації елементів сигналу s в зворотньому порядку (якщо сигнал нескінченний і визначений на всій множині індексів Z, то операція еквівалентна зміні знака індексу кожного елемента сигналу на протилежний).
Тепер формули (19) і (22) можна записати відповідно таким чином:
(24)
(25)
Тут символ * позначає операцію згортки. (Читачу пропонується самостійно перевірити еквівалентність формул (24), (25) і (19), (22) відповідно.)
В такій постановці набори коефіцієнтів h і g називаються фільтрами. Фільтр h використовується для виділення огрубленої (низькочастотної) частини сигналу, а фільтр g — для виділення деталізуючої інформації. Тому справедливо називати перший фільтр низькочастотним, а другий — високочастотним.
Часто формули (24) і (25) записують за допомогою так званого Z-перетворення. Z- перетворенням дискретного сигналу називається поліном
(як видно, цей поліном може містити члени як з позитивними, так і з негативними ступенями аргументу; такий поліном носить назву поліном Лорана). Очевидно, що якщо сигнал має кінцеве число відмінних від нуля елементів, то і його Z-перетворення буде поліномом з кінцевим числом членів.
Z-перетворення володіють наступною важливою властивістю: згортка двох дискретних сигналів еквівалентна перемножуванню їх Z-перетворень, тобто для будь-яких сигналів q, r і s справедливо наступне:
(як відомо, аналогічною властивістю володіє перетворення Фурьє).
Надалі для Z-перетворення деякого сигналу s замість позначення Ps{z) будемо використовувати скорочення s(z).
Використання Z-перетворень в записі вейвлет-перетворень за допомогою фільтрів робить її більш зручною і наочною. Зокрема, щоб показати, що компоненти сигналу s потрібно брати в зворотньому порядку, не вимагається вводити нове позначення s*. Якщо s(z) — Z-перетворення сигналу s, то Z- перетворенням сигналу s* є s(z-1). Крім того, якщо фільтр був виписаний у вигляді Z-перетворення, то відразу стає видно, які індекси мають його елементи (індекс елемента рівний ступеню відповідного члена, узятому з протилежним знаком).
От як виглядають формули (24) і (25) в термінах Z-перетворення:
(26)
(27)
Відзначимо деякі властивості отриманих формул.
Перш за все, в них ніде в явному вигляді не фігурують ні скейлінг-функції, ні вейвлети. Замість них використовуються фільтри h і g (або h(z) і g(z)), елементами яких є коефіцієнти відповідних масштабних співвідношень.
Приклад. Є ціле сімейство ортогональних вейвлетів, які взагалі не мають аналітичного виразу і визначаються тільки фільтрами. Це сімейство носить назву вейвлетів Добеши. Скейлінг-функції і вейвлети Добеши — це неперервні функції, не тотожні нулю на кінцевому відрізку і ніде на цьому відрізку не диференціюються. Приведемо коефіцієнти фільтрів для скейлінг-функції і вейвлетів Добеши D4(число 4 позначає кількість ненульових коефіцієнтів у фільтрах):
Оскільки у формулах (24), (25) і в еквівалентних їм формулах (26), (27) замість базисних функцій використовуються фільтри, то умову оборотності перетворення також має сенс виразити через ці ж фільтри (нагадаємо, що умовою оборотності в термінах функцій була вимога ортонормованості базису).
Очевидно, що перетворення буде оборотне тоді і тільки тоді, коли при підстановці виразів (26) у формулу (27) остання перетвориться на вірну тотожність для будь-якогоvi+1(z). Читачу пропонується самостійно перевірити, що для цього достатньо виконання наступних умов:
(28)
В літературі була прийнята наступна термінологія. Обчислення перетворення по формулах (19) - (22) або (20) - (23) називається швидким вейвлет-перетворенням (ШВП) (fast wavelet transform (FWT)). Схему розкладання, записану з допомогою формул (24)-(25) (або (26)-(27)) називають субсмуговим перетворенням (subband transform).
В п. 6 показано, що, при дотриманні ряду умов, діадне перетворення дискретного сигналу кінцевої довжини N містить рівно N елементів. Тобто таке перетворення не збільшує об'єм даних для представлення сигналу.
3. Перетворення з надмірною інформацією.
Вейвлет-фрейми.
В п. 1.4 говорилося про два типи задач, для вирішення яких можуть бути використані неперервне і діадне перетворення. Тепер розглянемо цю проблему з дещо іншої сторони.
Діадне вейвлет-перетворення (6)-(7), як показав багатомасштабний аналіз, є розкладанням за системою вейвлетів, яка є базисом в деякому функціональному просторі, тобто є мінімальною, що породжує цей простір системою. Це значить, що якщо з перетворення виключити хоча б один елемент, то знайдеться сигнал, який не можна буде повністю відновити за допомогою подібного перетворення. Перетворення, які є розкладаннями по базису в даному функціональному просторі, називатимемо перетвореннями, що не містять надлишкової інформації.
Якщо ж перетворення виконується за системою функцій, яка містить базис, але не співпадає з ним, то таке перетворення називатимемо перетворенням, що містить надмірну інформацію. До таких перетворень відноситься неперервне вейвлет-перетворення (1)-(2). До цієї ж групи віднесемо і різні модифікації неперервного перетворення для дискретних сигналів, наприклад ті, які обговорювалися в п. 2.1.
Перетворення, що не містять надлишкової інформації, запропоновано називати так тому що в них міститься рівно стільки інформації, щоб перетворення було оборотним. Проте цієї інформації може виявитися недостатньо для вирішення тих задач, де зворотнє перетворення може бути і не потрібне, зате необхідний детальний аналіз сигналу по його образу. Наприклад, діадне ортогональне перетворення не інваріантне зсуву сигналу. Як приклад читачу пропонується знайти два кроки перетворення Хаара двох дискретних сигналів s1(z)= z + z-1 і s2(z)= z-1 + z-2 і переконатися, що вони істотно відрізняються один від одного, хоча s2 є лише зсунута на 1 копія s1. Подібна властивість суттєво обмежує можливості перетворення в задачах розпізнавання, класифікації, пошуку за шаблоном, сегментації і ін.
З другого боку, неважко помітити, що для неперервного перетворення справедливо наступне:
(29)
тобто образ зсунутого на будь-яке дійсне число сигналу співпадає із зсувом на те ж число образу незсунутого сигналу.
Тією ж властивістю (але для цілочисельних зсувів) володіють і аналоги неперервного перетворення для дискретних сигналів (15) і (16).
Прикладом перетворення, що володіє надлишковою інформацією і представляючого практичний інтерес, є так звані вейвлет-фрейми (wavelet frames). Цю конструкцію можна вважати своєрідним компромісом між безперервним і діадним перетворенням: від неперервного перетворення вона успадковує властивість (29), від діадного перетворення — відносно малий об'єм інформації.
Вейвлет-фрейми —це перетворення, обчислюване по формулах (1)-(2) для а і b вигляду
тобто рівні дозволу вибираються так само, як і для діадного перетворення (вейвлети сусідніх рівнів є стислими (розтягнутими) в два рази копіями один одного), але на кожному рівні дозволу розкладання сигналу ведеться по всіх зсувах вейвлета, як і в разі неперервного перетворення.
Для випадку дискретних сигналів розкладання на кожному рівні дозволу ведеться, зрозуміло, по всіх цілочисельних зсувах.
Строго кажучи, дане перетворення є сенс розглядати тільки застосовуючи до дискретних сигналів, оскільки; по-перше, в протилежному випадку воно нічим не відрізняється від неперервного перетворення (тільки обчислення проводяться для спеціально вибраних значень масштабу а), а по-друге, з практичної точки зору це перетворення цікаво саме як "спрощений'' аналог неперервного перетворення для дискретних сигналів.
Отримаємо для вейвлет-фреймів формули, аналогічні формулам (26). Неважко помітити, що якщо для рекурсивних формул (26) був визначений початковий крок, відповідний максимальному дозволу i1, то першу формулу можна переписати таким чином:
Для другої формули подібного виразу скласти не можна, оскільки вейвлет-коефіцієнти виражаються через коефіцієнти при скейлінг-функціях, а не через вейвлет-коефіцієнти більш низького рівня. Справедливо наступний вираз:
В цих формулах оператор ↑ "розтягує" фільтри, тобто за допомогою цього оператора виконується перехід з одного рівня дозволу на іншій. Оператор ↓ вилучає з вже перетвореного сигналу частину елементів, що відповідає вилученню з перетворення "зайвих" зсувів. Оскільки у вейвлет-фреймів рівні дозволу співпадають з рівнями дозволу діадного перетворення, але використовуються всі можливі зсуви, то для реалізації перетворення достатньо виключити з вищенаведених формул, відповідних діадному перетворенню, оператор ↓. Виходить формула, що реалізовує вейвлет-фрейми:
(30)
Зворотнє перетворення в даному випадку навряд чи представляє практичний інтерес, якщо ж по якихось причинах його необхідно було б реалізувати, то достатньо помітити, що вейвлет-фрейми — це діадне перетворення, до якого була додана додаткова інформація. Отже, з представлення вимагається лише виділити ті коефіцієнти, які відповідають діадному перетворенню і виконати відновлення сигналу по формулах зворотнього діадного перетворення.
Оцінимо об'єм даних, необхідний для представлення сигналу за допомогою вейвлет-фреймів. Нагадаємо, що якщо початковий сигнал має кінцеву довжину N, то аналог неперервного перетворення, виконаний по формулах (16), міститиме N×N елементів, а діадне перетворення N — елементів. Представлення, отримане за допомогою вейвлет-фреймів. матиме К рівнів дозволу, на кожному рівні буде по N елементів (кількість можливих зсувів). В результаті виходить К×N елементів.
Подальший виклад в основному буде присвячений перетворенням, що не містять надлишкової інформації.
4. Неортогональні вейвлети.
В цьому розділі розглядається можливість зняття вимоги ортогональності з вейвлет-базисів і приводит...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора