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

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

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

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

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

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

$\psi (t)={\begin{cases}1\quad &0\leq t<{\frac {1}{2}},\\-1&{\frac {1}{2}}\leq t<1,\\0&{\mbox{інакше.}}\end{cases}}$

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

$\varphi (t)={\begin{cases}1\quad &0\leq t<1,\\0&{\mbox{інакше.}}\end{cases}}$

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

Для кожної пари цілих чисел n, k із $\mathbb {Z}$ га́арову фу́нкцію (англ. Haar function) ψ_n,k визначають на дійсній прямій $\mathbb {R}$ формулою

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

Носієм цієї функції є напіввідкритий праворуч проміжок I_n,k = [k2⁻ⁿ, (k+1)2⁻ⁿ), тобто вона перетворюється на нуль за його межами. Вона має інтеграл 0 та норму 1 у гільбертовому просторі L²($\mathbb {R}$),

$\int _{\mathbb {R} }\psi _{n,k}(t)\,dt=0,\quad \|\psi _{n,k}\|_{L^{2}(\mathbb {R} )}^{2}=\int _{\mathbb {R} }\psi _{n,k}(t)^{2}\,dt=1.$

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

$\int _{\mathbb {R} }\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.

Га́арова систе́ма (англ. Haar system) на дійсній прямій — це множина функцій

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

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

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

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

1. Будь-яку неперервну дійснозначну функцію з компактним носієм можливо рівномірно наблизити лінійними комбінаціями $\varphi (t),\varphi (2t),\varphi (4t),\dots ,\varphi (2^{n}t),\dots$ та їхніх зміщених функцій. Це поширюється на ті функційні простори, будь-яку функцію в яких можливо наблизити неперервними функціями.
2. Будь-яку неперервну дійсну функцію на [0, 1] можливо рівномірно наблизити на [0, 1] лінійними комбінаціями сталої функції 1, $\psi (t),\psi (2t),\psi (4t),\dots ,\psi (2^{n}t),\dots$ та їхніх зміщених функцій.
3. Ортогональність вигляду

   $\int _{-\infty }^{\infty }2^{(n+n_{1})/2}\psi (2^{n}t-k)\psi (2^{n_{1}}t-k_{1})\,dt=\delta _{nn_{1}}\delta _{kk_{1}}.$

   Тут $\delta _{ij}$ подає дельту Кронекера. Двоїста функція ψ(t) — це сама ψ(t).
4. Вейвлетні/масштабні функції з різним масштабом n мають функційний взаємозв'язок: оскільки

   ${\begin{aligned}\varphi (t)&=\varphi (2t)+\varphi (2t-1)\\[.2em]\psi (t)&=\varphi (2t)-\varphi (2t-1),\end{aligned}}$

   то виходить, що коефіцієнти масштабу n можливо обчислювати через коефіцієнти масштабу n+1:
   Якщо $\chi _{w}(k,n)=2^{n/2}\int _{-\infty }^{\infty }x(t)\varphi (2^{n}t-k)\,dt$
   та $\mathrm {X} _{w}(k,n)=2^{n/2}\int _{-\infty }^{\infty }x(t)\psi (2^{n}t-k)\,dt$
   то

   $\chi _{w}(k,n)=2^{-1/2}{\bigl (}\chi _{w}(2k,n+1)+\chi _{w}(2k+1,n+1){\bigr )}$

   $\mathrm {X} _{w}(k,n)=2^{-1/2}{\bigl (}\chi _{w}(2k,n+1)-\chi _{w}(2k+1,n+1){\bigr )}.$

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

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

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

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

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

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

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

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

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

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

Систе́ма Фа́бера — Ша́удера (англ. Faber–Schauder system) — це система неперервних функцій на [0, 1], яка складається зі сталої функції 1, та кратних невизначених інтегралів функцій гаарової системи на [0, 1], обраних так, щоби мати норму 1 в максимум-нормі. Ця система починається з s₀ = 1, тоді s₁(t) = t — невизначений інтеграл, який сходить на 0 функції 1, першого елемента гаарової системи на [0, 1]. Далі для кожного цілого n ≥ 0 функції s_n,k визначено формулою

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

Ці функції s_n,k неперервні, відтинково лінійні, відмінні від нуля на інтервалі I_n,k, на якому також відмінні від нуля ψ_n,k. Функція s_n,k дорівнює 1 у серединній точці x_n,k інтервалу  I_n,k, ліінйна на обох половинах цього інтервалу. Вона всюди набуває значень між 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}{\Bigl (}\sum _{k=0}^{2^{m}-1}a_{m,k}s_{m,k}{\Bigr )}\in C([0,1])$

розкладу f у ряд у системі Фабера — Шаудера — це неперервна відтинково лінійна функція, яка збігається з f в 2ⁿ + 1 точках k2⁻ⁿ, де 0 ≤ k ≤ 2ⁿ. Далі, формула

$f_{n+2}-f_{n+1}=\sum _{k=0}^{2^{n}-1}{\bigl (}f(x_{n,k})-f_{n+1}(x_{n,k}){\bigr )}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.

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

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

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

$\left\{f:x\in [0,\pi ]\rightarrow \sum _{n=0}^{\infty }a_{n}\cos(nx)\right\}\longrightarrow \left\{T(f):z\rightarrow \sum _{n=0}^{\infty }a_{n}z^{n},\quad |z|\leq 1\right\}.$

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

Маючи справу з 1-періодичними неперервними функціями, а точніше з такими неперервними функціями f на [0, 1], що f(0) = f(1), можливо вилучити функцію s₁(t) = t з системи Фабера — Шаудера, щоб отримати періоди́чну систе́му Фа́бера — Ша́удера (англ. periodic Faber–Schauder system). Періоди́чну систе́му Фра́нкліна (англ. periodic Franklin system) отримують з періодичної системи Фабера — Шаудера шляхом ортонормування. Результат Бочкарева на A(D) можливо довести, довівши, що періодична система Франкліна на [0, 2π] є базисом для банахового простору A_r, ізоморфного A(D). Простір A_r складається з комплексних неперервних функцій на одиничному колі T, чиї спряжені функції також неперервні.

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

Пов'язана з гааровим вейвлетом гаарова матриця (англ. Haar matrix) 2×2 має вигляд

$H_{2}={\begin{bmatrix}1&1\\1&-1\end{bmatrix}}.$

Використовуючи дискретне вейвлетне перетворення, можливо перетворити будь-яку послідовність $(a_{0},a_{1},\dots ,a_{2n},a_{2n+1})$ парної довжини на послідовність двоскладових векторів $\left(\left(a_{0},a_{1}\right),\left(a_{2},a_{3}\right),\dots ,\left(a_{2n},a_{2n+1}\right)\right)$. Якщо кожен вектор домножити праворуч на матрицю $H_{2}$, буде отримано результат $\left(\left(s_{0},d_{0}\right),\dots ,\left(s_{n},d_{n}\right)\right)$ одного етапу швидкого гаарово-вейвлетного перетворення (англ. fast Haar-wavelet transform). Зазвичай послідовності s та d розділяють, і продовжують перетворювати послідовність s. Послідовність s часто називають частиною усереднень, тоді як d відома як частина деталей.

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

$H_{4}={\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&0&0\\0&0&1&-1\end{bmatrix}},$

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

Порівняйте з матрицею Уолша, яка є нелокалізованою матрицею 1/−1.

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

$H_{2N}={\begin{bmatrix}H_{N}\otimes [1,1]\\I_{N}\otimes [1,-1]\end{bmatrix}}$

де $I_{N}={\begin{bmatrix}1&0&\dots &0\\0&1&\dots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\dots &1\end{bmatrix}}$, а $\otimes$ — добуток Кронекера.

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

$A\otimes B={\begin{bmatrix}a_{11}B&\dots &a_{1n}B\\\vdots &\ddots &\vdots \\a_{m1}B&\dots &a_{mn}B\end{bmatrix}}.$

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

$H_{8}={\begin{bmatrix}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{bmatrix}}.$

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

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

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

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

Га́арове перетво́рення (англ. Haar transform) — це найпростіше вейвлетне перетворення. Це перетворення перехресно множить функцію на гаарів вейвлет з різними зміщеннями та розтягуваннями, як перетворення Фур'є перехресно множить функцію на хвилю синусоїди з двома фазами та багатьма розтягуваннями.^{[прояснити: ком.]}

Введення

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

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

$H_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\{\sqrt {2}}&-{\sqrt {2}}&0&0\\0&0&{\sqrt {2}}&-{\sqrt {2}}\end{bmatrix}}$

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

Порівняйте з перетворенням Уолша, яке також 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}$

Матриця гаарового перетворення дійсна та ортогональна. Тож обернене гаарове перетворення (англ. inverse Haar transform) можливо отримати наступними рівняннями.

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

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

$H_{4}^{T}H_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&{\sqrt {2}}&0\\1&1&-{\sqrt {2}}&0\\1&-1&0&{\sqrt {2}}\\1&-1&0&-{\sqrt {2}}\end{bmatrix}}\cdot \;{\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\{\sqrt {2}}&-{\sqrt {2}}&0&0\\0&0&{\sqrt {2}}&-{\sqrt {2}}\end{bmatrix}}={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}}$

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

$x_{n}=H^{T}y_{n}$

Приклад

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

$y_{4}=H_{4}x_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\{\sqrt {2}}&-{\sqrt {2}}&0&0\\0&0&{\sqrt {2}}&-{\sqrt {2}}\end{bmatrix}}{\begin{bmatrix}1\\2\\3\\4\end{bmatrix}}={\begin{bmatrix}5\\-2\\-1/{\sqrt {2}}\\-1/{\sqrt {2}}\end{bmatrix}}$

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

${\hat {x_{4}}}=H_{4}^{T}y_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&{\sqrt {2}}&0\\1&1&-{\sqrt {2}}&0\\1&-1&0&{\sqrt {2}}\\1&-1&0&-{\sqrt {2}}\end{bmatrix}}{\begin{bmatrix}5\\-2\\-1/{\sqrt {2}}\\-1/{\sqrt {2}}\end{bmatrix}}={\begin{bmatrix}1\\2\\3\\4\end{bmatrix}}$

Див. також

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

Література

• Haar, Alfréd (1910), Zur Theorie der orthogonalen Funktionensysteme, Mathematische Annalen, 69 (3): 331—371, doi:10.1007/BF01456326, hdl:2027/uc1.b2619563, S2CID 120024038 (нім.)
• Charles K. Chui, An Introduction to Wavelets, (1992), Academic Press, San Diego, ISBN 0-585-47090-1 (англ.)
• Англомовний переклад засадничої праці Гаара: [1] (англ.)

Посилання

• Hazewinkel, Michiel, ред. (2001), Haar system, Математична енциклопедія, Springer, ISBN 978-1-55608-010-4
• Free Haar wavelet filtering implementation and interactive demo
• Free Haar wavelet denoising and lossy signal compression

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

• Kingsbury, Nick. The Haar Transform. Архів оригіналу за 19 квітня 2006. (англ.)
• Eck, David (31 січня 2006). Haar Transform Demo Applets. (англ.)
• Ames, Greg (7 грудня 2002). Image Compression (PDF). Архів оригіналу (PDF) за 25 січня 2011. (англ.)
• Aaron, Anne; Hill, Michael; Srivatsa, Anand (6/1/2000). MOSMAT 500. A photomosaic generator. 2. Theory. Архів оригіналу за 18 березня 2008. (англ.)
• Wang, Ruye (4 грудня 2008). Haar Transform. Архів оригіналу за 21 серпня 2012. (англ.)