Гаарів вейвлет

Гаарів вейвлет

У математиці Га́арів вейвле́т (Шаблон:Lang-en) — це послідовність перемасштабованих функцій «квадратної» форми, які разом утворюють вейвлетне сімейство або базис. Вейвлетний аналіз подібний до аналізу Фур'є тим, що дозволяє цільовій функції над інтервалом бути поданою в термінах ортонормованого базису. Гаарову послідовність тепер визнають як перший відомий вейвлетний базис, та широко використовують як навчальний приклад.

Га́арову послідо́вність (Шаблон:Lang-en) запропонував 1909 року Шаблон:Нп.Шаблон:Sfn Він використав ці функції, щоби навести приклад ортонормованої системи для простору Шаблон:Нп на одиничному інтервалі [0, 1]. Дослідження вейвлетів і навіть сам термін «вейвлет» з'явилися набагато пізніше. Як окремий випадок вейвлетів Добеші, гаарів вейвлет відомий також як Db1.

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

Материнську функцію гаарового вейвлета $\psi (t)$ можливо описати як

$\psi (t)=\{\begin{array}{cc}1& 0\le t<\frac{1}{2},\\ -1& \frac{1}{2}\le t<1,\\ 0& \text{інакше.}\end{array}$

Його масштабну функцію $\phi (t)$ можливо описати як

$\phi (t)=\{\begin{array}{cc}1& 0\le t<1,\\ 0& \text{інакше.}\end{array}$

Гаарові функції та гаарова система

Для кожної пари цілих чисел n, k із $\mathbb{Z}$ га́арову фу́нкцію (Шаблон:Lang-en) ψ_n,k визначають на дійсній прямій $ℝ$ формулою

${\psi }_{n,k}(t)=2^{n/2}\psi (2^{n}t-k),t\in ℝ.$

Носієм цієї функції є напіввідкритий праворуч проміжок Шаблон:Nowrap Шаблон:Nowrap, тобто вона перетворюється на нуль за його межами. Вона має інтеграл 0 та норму 1 у гільбертовому просторі L²($ℝ$),

$\underset{ℝ}{\int }{\psi }_{n,k}(t)dt=0,\Vert {\psi }_{n,k}{\Vert }_{L^2(ℝ)}^2=\underset{ℝ}{\int }{\psi }_{n,k}(t{)}^{2}dt=1.$

Гаарові функції попарно ортогональні,

$\underset{ℝ}{\int }{\psi }_{n_1,k_1}(t){\psi }_{n_2,k_2}(t)dt={\delta }_{n_1{n}_2}{\delta }_{k_1{k}_2},$

де ${\delta }_{ij}$ подає дельту Кронекера. Причина ортогональності тут така: коли два інтервали-носії $I_{n_1,k_1}$ та $I_{n_2,k_2}$ не рівні, то вони або не перетинаються, або менший із двох носіїв, скажімо, $I_{n_1,k_1}$, міститься в нижній або верхній половині іншого інтервалу, на якому функція ${\psi }_{n_2,k_2}$ лишається сталою. Тоді виходить, що добуток цих двох гаарових функцій кратний першій гаарової функції, тож цей добуток має інтеграл 0.

Га́арова систе́ма (Шаблон:Lang-en) на дійсній прямій — це множина функцій

$\{1\}\cup \{{\psi }_{n,k}(t):n\in \mathbb{Z},k\in \mathbb{Z}\}.$

Вона повна в L²($ℝ$): Гаарова система на прямій це ортонормований базис в L²($ℝ$).

Властивості гаарового вейвлета

Гаарів вейвлет має декілька визначних властивостей:

Гаарова система на одиничному інтервалі, та пов'язані системи

У цьому розділі обговорення обмежено одиничним інтервалом [0, 1] та гааровими функціями, відмінними від нуля на [0, 1]. Система функцій, розглянута Гааром 1910 року,Шаблон:Sfn звана в цій статті га́аровою систе́мою на [0, 1], складається з підмножини гаарових вейвлетів, визначених як

$\{t\in [0,1]\mapsto {\psi }_{n,k}(t):n\in \mathbb{N}\cup \{0\},0\le k<2^n\},$

з додаванням сталої функції 1 на [0, 1].

В термінах гільбертового простору ця гаарова система на [0, 1] є повною ортонормованою системою, тобто, ортонормованим базисом для простору L²([0, 1]) квадратично інтегровних функцій на одиничному інтервалі.

Гаарова система на [0, 1] — зі сталою функцією 1 як першим елементом, за яким слідують гаарові функції, впорядковані за лексикографічним порядком пар Шаблон:Nowrap, — є також Шаблон:Нп Шаблон:Нп для простору L^p([0, 1]), коли Шаблон:Nowrap. Цей базис Шаблон:Нп, коли Шаблон:Nowrap.

Існує пов'язана Шаблон:Нп, яка складається з сум гаарових функцій,

$r_n(t)=2^{-n/2}\sum _{k=0}^{2^n-1}{\psi }_{n,k}(t),t\in [0,1],n\ge 0.$

Зауважте, що |r_n(t)| = 1 на [0, 1). Це ортонормована система, але не повна. Мовою теорії ймовірностей, послідовність Радемахера — це примірник послідовності незалежних випадкових величин Бернуллі з середнім 0. Шаблон:Нп виражає той факт, що в усіх просторах L^p([0, 1]), Шаблон:Nowrap, послідовність Радемахера Шаблон:Нп базису одиничного вектора в ℓ². Зокрема, Шаблон:Нп послідовності Радемахера в L^p([0, 1]), Шаблон:Nowrap, Шаблон:Нп з ℓ².

Система Фабера — Шаудера

Систе́ма Фа́бера — Ша́удера (Шаблон:Lang-en) — це система неперервних функцій на [0, 1], яка складається зі сталої функції 1, та кратних невизначених інтегралів функцій гаарової системи на [0, 1], обраних так, щоби мати норму 1 в максимум-нормі. Ця система починається з s₀ = 1, тоді Шаблон:Nowrap — невизначений інтеграл, який сходить на 0 функції 1, першого елемента гаарової системи на [0, 1]. Далі для кожного цілого Шаблон:Nowrap функції Шаблон:Nowrap визначено формулою

$s_{n,k}(t)=2^{1+n/2}\underset{0}{\overset{t}{\int }}{\psi }_{n,k}(u)du,t\in [0,1],0\le k<2^n.$

Ці функції Шаблон:Nowrap неперервні, відтинково лінійні, відмінні від нуля на інтервалі Шаблон:Nowrap, на якому також відмінні від нуля Шаблон:Nowrap. Функція Шаблон:Nowrap дорівнює 1 у серединній точці Шаблон:Nowrap інтервалу Шаблон:Nowrap, лінійна на обох половинах цього інтервалу. Вона всюди набуває значень між 0 та 1.

Система Фабера — Шаудера це Шаблон:Нп для простору C([0, 1]) неперевних функцій на [0, 1]. Для кожної f з C([0, 1]) частинна сума

$f_{n+1}=a_0{s}_0+a_1{s}_1+\sum _{m=0}^{n-1}\left(\sum _{k=0}^{2^m-1}{a}_{m,k}{s}_{m,k}\right)\in C([0,1])$

розкладу f Шаблон:Нп у системі Фабера — Шаудера — це неперервна відтинково лінійна функція, яка збігається з f в Шаблон:Nowrap точках Шаблон:Nowrap, де Шаблон:Nowrap. Далі, формула

$f_{n+2}-f_{n+1}=\sum _{k=0}^{2^n-1}(f(x_{n,k})-f_{n+1}(x_{n,k}))s_{n,k}=\sum _{k=0}^{2^n-1}{a}_{n,k}{s}_{n,k}$

пропонує спосіб покрокового обчислення розкладу f. Оскільки f рівномірно неперервна, послідовність {f_n} рівномірно збігається до f. Звідси випливає, що розклад f у ряд у системі Фабера — Шаудера збігається в C([0, 1]), а сума цього ряду дорівнює f.

Система Франкліна

Систе́му Фра́нкліна (Шаблон:Lang-en) отримують із системи Фабера — Шаудера ортонормувальною процедурою Грама — Шмідта. Оскільки система Франкліна має таку же лінійну оболонку, як і система Фабера — Шаудера, ця оболонка щільна в C([0, 1]), а отже й у L²([0, 1]). Тому система Франкліна є ортонормальним базисом для L²([0, 1]), який складається з неперервних відтинково лінійних функцій. Ф. Франклін довів 1928 року, що ця система є базисом Шаудера для C([0, 1]). Система Франкліна є також безумовним базисом Шаудера для простору L^p([0, 1]), коли Шаблон:Nowrap. Система Франкліна забезпечує базис Шаудера в Шаблон:НпШаблон:Уточнити термін A(D). Це довів 1974 року Бочкарев після того, як існування базису для кругової алгебри залишалося відкритим питанням протягом понад сорока років.

Побудова Бочкарева базиса Шаудера в A(D) відбувається так: нехай f — комплекснозначна ліпшицева функція на [0, π]; тоді f — сума косинусного ряду з абсолютно сумовними коефіцієнтами. Нехай T(f) — елемент A(D), визначений комплексним степеневим рядом з такими же коефіцієнтами,

$\{f:x\in [0,\pi ]\to \sum _{n=0}^{\mathrm{\infty }}{a}_n\cos (nx)\}⟶\{T(f):z\to \sum _{n=0}^{\mathrm{\infty }}{a}_n{z}^n,|z|\le 1\}.$

Базис Бочкарева для A(D) утворюють образи під T функцій системи Франкліна на [0, π]. Еквівалентний опис Бочкарева для відображення T починається з розширення f до парної ліпшицевої функції g₁ на [−π, π], ототожнюваної з ліпшицевою функцією на одиничному колі T. Далі, покладімо, що g₂ — Шаблон:Нп g₁, і визначмо T(f) як функцію в A(D), чиє значення на межі T круга D дорівнює Шаблон:Nowrap.

Маючи справу з 1-періодичними неперервними функціями, а точніше з такими неперервними функціями f на [0, 1], що Шаблон:Nowrap, можливо вилучити функцію Шаблон:Nowrap з системи Фабера — Шаудера, щоб отримати періоди́чну систе́му Фа́бера — Ша́удера (Шаблон:Lang-en). Періоди́чну систе́му Фра́нкліна (Шаблон:Lang-en) отримують з періодичної системи Фабера — Шаудера шляхом ортонормування. Результат Бочкарева на A(D) можливо довести, довівши, що періодична система Франкліна на [0, 2π] є базисом для банахового простору A_r, ізоморфного A(D). Простір A_r складається з комплексних неперервних функцій на одиничному колі T, чиї Шаблон:Нп також неперервні.

Гаарова матриця

Пов'язана з гааровим вейвлетом гаарова матриця (Шаблон:Lang-en) 2×2 має вигляд

$H_2=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right].$

Використовуючи Шаблон:Нп, можливо перетворити будь-яку послідовність $(a_0,a_1,\dots ,a_{2n},a_{2n+1})$ парної довжини на послідовність двоскладових векторів $((a_0,a_1),(a_2,a_3),\dots ,(a_{2n},a_{2n+1}))$. Якщо кожен вектор домножити праворуч на матрицю $H_2$, буде отримано результат $((s_0,d_0),\dots ,(s_n,d_n))$ одного етапу швидкого гаарово-вейвлетного перетворення (Шаблон:Lang-en). Зазвичай послідовності s та d розділяють, і продовжують перетворювати послідовність s. Послідовність s часто називають частиною усереднень, тоді як d відома як частина деталей.

Якщо мають послідовність довжини, кратної чотирьом, то можливо побудувати блоки з 4 елементів та перетворювати їх подібним чином за допомогою гаарової матриці 4×4

$H_4=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& -1& -1\\ 1& -1& 0& 0\\ 0& 0& 1& -1\end{array}\right],$

яка поєднує два етапи швидкого гаарово-вейвлетного перетворення.

Порівняйте з Шаблон:Нп, яка є нелокалізованою матрицею 1/−1.

Загалом, гаарову матрицю 2N×2N можливо вивести наступним рівнянням.

$H_{2N}=\left[\begin{array}{c}{H}_N\otimes [1,1]\\ I_N\otimes [1,-1]\end{array}\right]$

де $I_N=\left[\begin{array}{cccc}1& 0& \dots & 0\\ 0& 1& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & 1\end{array}\right]$, а $\otimes$ — добуток Кронекера.

Добуток Кронекера $A\otimes B$, де $A$ це матриця m×n, а $B$ — матриця p×q, виражають як

$A\otimes B=\left[\begin{array}{ccc}{a}_{11}B& \dots & a_{1n}B\\ ⋮& \ddots & ⋮\\ a_{m1}B& \dots & a_{mn}B\end{array}\right].$

Нижче показано невнормовану 8-точкову гаарову матрицю $H_8$

$H_8=\left[\begin{array}{cccccccc}1& 1& 1& 1& 1& 1& 1& 1\\ 1& 1& 1& 1& -1& -1& -1& -1\\ 1& 1& -1& -1& 0& 0& 0& 0& \\ 0& 0& 0& 0& 1& 1& -1& -1\\ 1& -1& 0& 0& 0& 0& 0& 0& \\ 0& 0& 1& -1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& -1& 0& 0& \\ 0& 0& 0& 0& 0& 0& 1& -1\end{array}\right].$

Зауважте, що наведена вище матриця це невнормована гаарова матриця. Гаарову матрицю, якої вимагає гаарове перетворення, потрібно унормовувати.

З визначення гаарової матриці $H$ можливо побачити, що, на відміну від перетворення Фур'є, $H$ має лише дійсні елементи (тобто, 1, -1 та 0), і не симетрична.

Візьмімо 8-точкову гаарову матрицю як приклад. Перший рядок $H_8$ вимірює усереднене значення, а другий рядок $H_8$ вимірює низькочастотну складову вхідного вектора. Наступні два рядки чутливі до першої та другої половини вхідного вектора відповідно, що відповідає середньочастотним складовим. Решта чотири рядки чутливі до чвертинних ділянок вхідного вектора, що відповідає високочастотним складовим.

Гаарове перетворення

Га́арове перетво́рення (Шаблон:Lang-en) — це найпростіше вейвлетне перетворення. Це перетворення перехресно множить функцію на гаарів вейвлет з різними зміщеннями та розтягуваннями, як перетворення Фур'є перехресно множить функцію на хвилю синусоїди з двома фазами та багатьма розтягуваннями.Шаблон:Прояснити

Введення

Гаарове перетворення — це одна з найстаріших функцій перетворень, запропонована 1910 року угорським математиком Шаблон:Нп. Вона ефективна в таких застосуваннях як стискання сигналів та зображень в електричній та комп'ютерній інженерії, оскільки пропонує простий та обчислювально ефективний підхід для аналізу локальних аспектів сигналу.

Гаарове перетворення похідне від гаарової матриці. Нижче показано приклад матриці гаарового перетворення 4×4.

$H_4=\frac{1}{2}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& -1& -1\\ \sqrt{2}& -\sqrt{2}& 0& 0\\ 0& 0& \sqrt{2}& -\sqrt{2}\end{array}\right]$

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

Порівняйте з перетворенням Уолша, яке також 1/−1, але не локалізоване.

Властивості

Гаарове перетворення має наступні властивості

1. Відсутність потреби в множеннях. Воно вимагає лише додавань, і в гааровій матриці багато елементів з нульовим значенням, тож обчислення є нетривалим. Воно швидше за перетворення Уолша, чия матриця складається з +1 та −1.
2. Довжини входу та виходу однакові. Проте ця довжина повинна бути степенем 2, тобто $N=2^k,k\in \mathbb{N}$.
3. Його можливо використовувати для аналізу локалізованої ознаки сигналів. Завдяки ортогональній властивості гаарової функції можливо аналізувати частотні складові вхідного сигналу.

Гаарове та обернене гаарове перетворення

Гаарове перетворення y_n n-входової функції x_n це

$y_n=H_n{x}_n$

Матриця гаарового перетворення дійсна та ортогональна. Тож обернене гаарове перетворення (Шаблон:Lang-en) можливо отримати наступними рівняннями.

$H=H^{*},H^{-1}=H^T$, тобто $H{H}^T=I$

де $I$ — одинична матриця. Наприклад, коли n = 4

$H_4^T{H}_4=\frac{1}{2}\left[\begin{array}{cccc}1& 1& \sqrt{2}& 0\\ 1& 1& -\sqrt{2}& 0\\ 1& -1& 0& \sqrt{2}\\ 1& -1& 0& -\sqrt{2}\end{array}\right]\cdot \frac{1}{2}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& -1& -1\\ \sqrt{2}& -\sqrt{2}& 0& 0\\ 0& 0& \sqrt{2}& -\sqrt{2}\end{array}\right]=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right]$

Тож обернене гаарове перетворення це

$x_n=H^T{y}_n$

Приклад

Коефіцієнти гаарового перетворення n=4-точкового сигналу $x_4=[1,2,3,4{]}^T$ можливо знайти як

$y_4=H_4{x}_4=\frac{1}{2}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& -1& -1\\ \sqrt{2}& -\sqrt{2}& 0& 0\\ 0& 0& \sqrt{2}& -\sqrt{2}\end{array}\right]\left[\begin{array}{c}1\\ 2\\ 3\\ 4\end{array}\right]=\left[\begin{array}{c}5\\ -2\\ -1/\sqrt{2}\\ -1/\sqrt{2}\end{array}\right]$

Цей вхідний сигнал можливо ідеально відтворити оберненим гааровим перетворенням

$\widehat{x_4}=H_4^T{y}_4=\frac{1}{2}\left[\begin{array}{cccc}1& 1& \sqrt{2}& 0\\ 1& 1& -\sqrt{2}& 0\\ 1& -1& 0& \sqrt{2}\\ 1& -1& 0& -\sqrt{2}\end{array}\right]\left[\begin{array}{c}5\\ -2\\ -1/\sqrt{2}\\ -1/\sqrt{2}\end{array}\right]=\left[\begin{array}{c}1\\ 2\\ 3\\ 4\end{array}\right]$

Див. також

• Знижування розмірності
• Шаблон:Нп
• Перетворення Уолша
• Вейвлет
• Шаблон:Нп
• Сигнал
• Гаароподібна ознака
• Шаблон:Нп
• Шаблон:Нп

Література

• Шаблон:Citation Шаблон:Ref-de
• Charles K. Chui, An Introduction to Wavelets, (1992), Academic Press, San Diego, Шаблон:ISBN Шаблон:Ref-en
• Англомовний переклад засадничої праці Гаара: [1] Шаблон:Ref-en

Посилання

• Шаблон:Springer
• Free Haar wavelet filtering implementation and interactive demo
• Free Haar wavelet denoising and lossy signal compression

Гаарове перетворення

• Шаблон:Cite web Шаблон:Ref-en
• Шаблон:Cite web Шаблон:Ref-en
• Шаблон:Cite web Шаблон:Ref-en
• Шаблон:Cite web Шаблон:Ref-en
• Шаблон:Cite web Шаблон:Ref-en