Вейвлет Хаара

Вейвлет Хаара Две итерации двумерного вейвлета Хаара на изображении Ленна. Исходное изображение подвергается высокочастотной фильтрации, что дает три субизображения с коэффициентами детализации (вверху справа: по горизонтали, внизу слева: по вертикали и внизу справа: по диагонали). Затем оно подвергается фильтрации нижних частот и масштабируется с уменьшением, в результате чего получается фрагмент изображения с коэффициентами аппроксимации (вверху слева); процесс фильтрации повторяется еще раз на этом приближенном изображении.

В математике вейвлет Хаара представляет собой последовательность масштабированных «прямоугольных» функций, которые вместе образуют семейство вейвлетов или основание. Вейвлет-анализ аналогичен анализу Фурье в том, что он позволяет представить целевую функцию на интервале в терминах ортонормированного базиса. Последовательность Хаара теперь признана первой известной основой вейвлетов и широко используется в качестве обучающего примера.

Последовательность Хаара была предложена в 1909 году Альфредом Хааром. Хаар использовал эти функции, чтобы дать пример ортонормированной системы для пространства квадратично интегрируемых функций на единичном интервале [0, 1]. Изучение вейвлетов и даже термина «вейвлет» появилось гораздо позже. Как частный случай вейвлета Добеши, вейвлет Хаара также известен как Db1 .

Вейвлет Хаара также является самым простым из возможных вейвлетов. Технический недостаток вейвлета Хаара заключается в том, что он не непрерывный и, следовательно, не дифференцируемый. Это свойство, однако, может быть преимуществом для анализа сигналов с внезапными переходами, таких как мониторинг отказа инструмента в станках.

Материнская функция вейвлета вейвлета Хаара $\psi \; (t)\; \{\backslash \; displaystyle\; \backslash \; psi\; (t)\}$можно описать как

Его функция масштабирования $\phi \; (t)\; \{\backslash \; displaystyle\; \backslash \; varphi\; (t)\}$можно описать как

• 1 Функции Хаара и система Хаара
• 2 Свойства вейвлетов Хаара
• 3 Система Хаара на единичном интервале и родственные системы
  • 3.1 Система Фабера – Шаудера
  • 3.2 Система Франклина
• 4 Матрица Хаара
• 5 Преобразование Хаара
  • 5.1 Введение
  • 5.2 Свойство
  • 5.3 Преобразование Хаара и обратное преобразование Хаара
  • 5.4 Пример
  • 5.5 Приложение
• 6 См. Также
• 7 Примечания
• 8 Ссылки
• 9 Внешние ссылки
  • 9.1 Преобразование Хаара

Для каждой пары n, k целых чисел в Z, функция Хаара ψ n, k определяется на вещественной прямой Rформулой

$\psi \; n,\; k\; (t)\; =\; 2\; n\; /\; 2\; \psi \; (2\; n\; t\; -\; k),\; t\; \in \; R.\; \{\backslash \; displaystyle\; \backslash \; psi\; \_\; \{n,\; k\}\; (t)\; =\; 2\; ^\; \{n\; /\; 2\}\; \backslash \; psi\; (2\; ^\; \{n\}\; tk),\; \backslash \; quad\; t\; \backslash \; in\; \backslash \; mathbf\; \{R\}.\}$

Эта функция поддерживается на правом открытом интервале I n, k = [k 2, (k + 1) 2), то есть исчезает вне этого интервала. Он имеет интеграл 0 и норму 1 в гильбертовом пространстве L(R),

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

Функции Хаара попарно ортогональны,

$\int \; R\; \psi \; n\; 1,\; k\; 1\; (t)\; \psi \; n\; 2,\; k\; 2\; (t)\; dt\; =\; \delta \; n\; 1,\; n\; 2\; \delta \; k\; 1,\; к\; 2,\; \{\backslash \; displaystyle\; \backslash \; int\; \_\; \{\backslash \; mathbf\; \{R\}\}\; \backslash \; psi\; \_\; \{n\_\; \{1\},\; k\_\; \{1\}\}\; (t)\; \backslash \; psi\; \_\; \{n\_\; \{2\},\; k\_\; \{2\}\}\; (t)\; \backslash ,\; dt\; =\; \backslash \; delta\; \_\; \{n\_\; \{1\},\; n\_\; \{2\}\}\; \backslash \; delta\; \_\; \{k\_\; \{1\},\; k\_\; \{2\}\},\}$

где δ i, j представляет Дельта Кронекера. Вот причина ортогональности: когда два поддерживающих интервала $I\; n\; 1,\; k\; 1\; \{\backslash \; displaystyle\; I\_\; \{n\_\; \{1\},\; k\_\; \{1\}\}\}$и $I\; n\; 2,\; k\; 2\; \{\backslash \; displaystyle\; I\_\; \{n\_\; \{2\},\; k\_\; \{2\}\}\}$не равны, то они либо не пересекаются, либо меньшая из двух опор, скажем $I\; n\; 1,\; k\; 1\; \{\backslash \; displaystyle\; I\_\; \{n\_\; \{1\},\; k\_\; \{1\}\}\}$, содержится в нижней или верхней половине другого интервала, на котором функция $\psi \; N\; 2,\; k\; 2\; \{\backslash \; displaystyle\; \backslash \; psi\; \_\; \{n\_\; \{2\},\; k\_\; \{2\}\}\}$остается постоянным. В этом случае следует, что произведение этих двух функций Хаара кратно первой функции Хаара, следовательно, произведение имеет интеграл 0.

Система Хаара на действительной прямой является набор функций

$\{\psi \; n,\; k\; (t);\; n\; \in \; Z,\; k\; \in \; Z\}.\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; psi\; \_\; \{n,\; k\}\; (t)\; \backslash \; ;;\; \backslash ;\; n\; \backslash \; in\; \backslash \; mathbf\; \{Z\},\; \backslash ;\; k\; \backslash \; in\; \backslash \; mathbf\; \{Z\}\; \backslash \}.\}$

Это завершено в L (R ): система Хаара на линии является ортонормированным базисом в L (R ).

Вейвлет Хаара имеет несколько примечательных свойств:

1. Любая непрерывная вещественная функция с компактной опорой может быть равномерно аппроксимирована линейными комбинациями из $\phi \; (T),\; \phi \; (2\; T),\; \phi \; (4\; T),\dots ,\; \phi \; (2\; nt),\dots \; \{\backslash \; displaystyle\; \backslash \; varphi\; (t),\; \backslash \; varphi\; (2t),\; \backslash \; varphi\; (4t),\; \backslash \; dots,\; \backslash \; varphi\; (2\; ^\; \{n\}\; t),\; \backslash \; dots\}$и их смещенные функции. Это распространяется на те функциональные пространства, где любую функцию в нем можно аппроксимировать непрерывными функциями.
2. Любая непрерывная действительная функция на [0, 1] может быть аппроксимирована равномерно на [0, 1] линейными комбинациями постоянной функции 1, $\psi \; (t),\; \psi \; (2\; t),\; \psi \; (4\; t),\dots ,\; \psi \; (2\; nt),\dots \; \{\backslash \; displaystyle\; \backslash \; psi\; (t),\; \backslash \; psi\; (2t),\; \backslash \; psi\; (4t),\; \backslash \; dots,\; \backslash \; psi\; (2\; ^\; \{n\}\; t),\; \backslash \; dots\}$и их смещенные функции.
3. Ортогональность в виде

$\int \; -\; \infty \; \infty \; 2\; (n\; +\; n\; 1)\; /\; 2\; \psi \; (2\; nt\; -\; k)\; \psi \; (2\; n\; 1\; t\; -\; k\; 1)\; dt\; =\; \delta \; n,\; n\; 1\; \delta \; k,\; k\; 1.\; \{\backslash \; displaystyle\; \backslash \; int\; \_\; \{-\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; 2\; ^\; \{(n\; +\; n\_\; \{1\})\; /\; 2\}\; \backslash \; psi\; (2\; ^\; \{n\}\; tk)\; \backslash \; psi\; (2\; ^\; \{n\_\; \{1\}\; \}\; t-k\_\; \{1\})\; \backslash ,\; dt\; =\; \backslash \; delta\; \_\; \{n,\; n\_\; \{1\}\}\; \backslash \; delta\; \_\; \{k,\; k\_\; \{1\}\}.\}$

Здесь δ i, j представляет дельту Кронекера. Двойственная функция к ψ (t) - это сама функция ψ (t).

1. Функции вейвлета / масштабирования с различным масштабом n имеют функциональную взаимосвязь: поскольку

$\phi \; (t)\; =\; \phi \; (2\; t)\; +\; \phi \; (2\; t\; -\; 1)\; \psi \; (t)\; =\; \phi \; (2\; t)\; -\; \phi \; (2\; T\; -\; 1),\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; varphi\; (t)\; =\; \backslash \; varphi\; (2t)\; +\; \backslash \; varphi\; (2t-1)\; \backslash \backslash \; [.\; 2em]\; \backslash \; psi\; (t)\; =\; \backslash \; varphi\; (2t)\; -\; \backslash \; varphi\; (2t-1),\; \backslash \; end\; \{align\}\}\}$

следует, что коэффициенты шкалы n могут быть вычислены с помощью коэффициентов шкалы n + 1:

Если $\chi \; вес\; (К,\; N)\; знак\; равно\; 2\; N\; /\; 2\; \int \; -\; \infty \; \infty \; Икс\; (T)\; \phi \; (2\; NT\; -\; К)\; dt\; \{\backslash \; Displaystyle\; \backslash \; чи\; \_\; \{ш\}\; (к,\; п)\; =\; 2\; ^\; \{п\; /\; 2\; \}\; \backslash \; int\; \_\; \{-\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; x\; (t)\; \backslash \; varphi\; (2\; ^\; \{n\}\; tk)\; \backslash ,\; dt\}$

и $X\; w\; (k,\; n)\; =\; 2\; n\; /\; 2\; \int \; -\; \infty \; \infty \; Икс\; (T)\; \psi \; (2\; NT\; -\; К)\; dt\; \{\backslash \; Displaystyle\; \backslash \; mathrm\; \{X\}\; \_\; \{w\}\; (к,\; п)\; =\; 2\; ^\; \{п\; /\; 2\}\; \backslash \; int\; \_\; \{-\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; x\; (t)\; \backslash \; psi\; (2\; ^\; \{n\}\; tk)\; \backslash ,\; dt\}$

, тогда

$\chi \; w\; (k,\; n)\; =\; 2\; -\; 1/2\; (\chi \; w\; (2\; k,\; п\; +\; 1)\; +\; \chi \; вес\; (2\; к\; +\; 1,\; п\; +\; 1))\; \{\backslash \; Displaystyle\; \backslash \; чи\; \_\; \{ш\}\; (к,\; п)\; =\; 2\; ^\; \{-\; 1/2\}\; \{\backslash \; bigl\; (\}\; \backslash \; чи\; \_\; \{\; w\}\; (2k,\; n\; +\; 1)\; +\; \backslash \; chi\; \_\; \{w\}\; (2k\; +\; 1,\; n\; +\; 1)\; \{\backslash \; bigr)\}\}$

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

В этом разделе обсуждение ограничено единичным интервалом [0, 1] и функциям Хаара, которые поддерживаются на [0, 1]. Система функций, рассмотренная Хааром в 1910 году и называемая в этой статье системой на [0, 1], состоит из подмножества вейвлетов Хаара, определенных как

с добавлением постоянной функции 1 на [0, 1].

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

Система Хаара на [0, 1] - с постоянной функцией 1 в качестве первого элемента, за которой следуют функции Хаара, упорядоченные в соответствии с лексикографическим упорядочением пар (n, k) - далее монотонный базис Шаудера для пространства L ([0, 1]), когда 1 ≤ p < ∞. This basis is безусловный при 1 < p < ∞.

Имеется связанная система Радемахера, состоящая из сумм функций Хаара,

$rn\; (t)\; =\; 2\; -\; n\; /\; 2\; \sum \; k\; =\; 0\; 2\; n\; -\; 1\; \psi \; n,\; К\; (T),\; T\; \in \; [0,\; 1],\; N\; \ge \; 0.\; \{\backslash \; Displaystyle\; r\_\; \{n\}\; (т)\; =\; 2\; ^\; \{-\; n\; /\; 2\}\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{2\; ^\; \{n\; \}\; -1\}\; \backslash \; psi\; \_\; \{n,\; k\}\; (t),\; \backslash \; quad\; t\; \backslash \; in\; [0,1],\; \backslash \; n\; \backslash \; geq\; 0.\}$

Обратите внимание, что | r n (t) | = 1 на [0, 1). Это ортонормированная система, но не полная. На языке теории вероятностей последовательность Радемахера является экземпляром последовательности независимых Бернулли случайных величин со средним значением . 0. Неравенство Хинчина выражает тот факт, что во всех пространствах L ([0, 1]), 1 ≤ p < ∞, the Rademacher sequence is эквивалентно базису единичного вектора в ℓ. В частности, замкнутая линейная оболочка последовательности Радемахера в L ([0, 1]), 1 ≤ p < ∞, is , изоморфна.

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

Система Фабера – Шаудера - это семейство непрерывных функций на [0, 1], состоящее из постоянной функции 1, и кратных неопределенных интегралов функций в системе Хаара на [0, 1], выбранных с нормой 1 в максимальной норме. Эта система начинается с s 0= 1, затем s 1 (t) = t - неопределенный интеграл, равный нулю в 0 функции 1, первого элемента системы Хаара на [0, 1]. Далее, для любого целого числа n ≥ 0 функции s n, k определяются формулой

Эти функции 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]) частичная сумма

$fn\; +\; 1\; =\; a\; 0\; s\; 0\; +\; a\; 1\; s\; 1\; +\; \sum \; m\; =\; 0\; n\; -\; 1\; (\sum \; k\; =\; 0\; 2\; m\; -\; 1\; am,\; ksm,\; k)\; \in \; C\; ([0,\; 1])\; \{\backslash \; displaystyle\; f\_\; \{n\; +\; 1\}\; =\; a\_\; \{0\}\; s\_\; \{0\}\; +\; a\_\; \{1\}\; s\_\; \{1\}\; +\; \backslash \; sum\; \_\; \{m\; =\; 0\}\; ^\; \{n-1\}\; \{\backslash \; Bigl\; (\}\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{2\; ^\; \{m\}\; -1\}\; a\_\; \{m,\; k\}\; s\_\; \{m,\; k\}\; \{\backslash \; Bigr)\}\; \backslash \; in\; C\; (\; [0,1])\}$

разложения в ряд функции f в системе Фабера – Шаудера является непрерывной кусочно-линейной функцией, которая согласуется с f в 2 + 1 точках k 2, где 0 ≤ k ≤ 2. Далее формула

$fn\; +\; 2\; -\; fn\; +\; 1\; =\; \sum \; k\; =\; 0\; 2\; n\; -\; 1\; (f\; (xn,\; k)\; -\; fn\; +\; 1\; (xn,\; k))\; sn,\; k\; =\; \sum \; k\; Знак\; равно\; 0\; 2\; n\; -\; 1\; an,\; ksn,\; k\; \{\backslash \; displaystyle\; f\_\; \{n\; +\; 2\}\; -f\_\; \{n\; +\; 1\}\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{2\; ^\; \{n\}\; -1\}\; \{\backslash \; bigl\; (\; \}\; f\; (x\_\; \{n,\; k\})\; -\; f\_\; \{n\; +\; 1\}\; (x\_\; \{n,\; k\})\; \{\backslash \; bigr)\}\; s\_\; \{n,\; k\}\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{2\; ^\; \{\; n\}\; -1\}\; a\_\; \{n,\; k\}\; s\_\; \{n,\; k\}\}$

позволяет шаг за шагом вычислять расширение f. Поскольку f является равномерно непрерывным, последовательность {f n } равномерно сходится к f. Отсюда следует, что разложение f в ряд Фабера – Шаудера сходится в C ([0, 1]), и сумма этого ряда равна f.

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

Система Франклина получается из системы Фабера – Шаудера с помощью процедуры ортонормировки Грама – Шмидта. Поскольку система Франклина имеет ту же линейную оболочку, что и система Фабера – Шаудера, эта оболочка плотна в C ([0, 1]), следовательно, в L ([0, 1]). Таким образом, система Франклина является ортонормированным базисом для L ([0, 1]), состоящим из непрерывных кусочно-линейных функций. П. Франклин доказал в 1928 г., что эта система является базисом Шаудера для C ([0, 1]). Система Франклина также является безусловным базисом Шаудера для пространства L ([0, 1]), когда 1 < p < ∞. The Franklin system provides a Schauder basis in the дисковая алгебра A (D). Это было доказано в 1974 году Бочкаревым, после того как существование базиса дисковой алгебры оставалось открытым более сорока лет.

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

$\{f:\; x\; \in \; [0,\; \pi ]\; \to \; \sum \; n\; =\; 0\; \infty \; an\; cos\; \; (nx)\}\; ⟶\; \{T\; (f):\; z\; \to \; \sum \; n\; =\; 0\; \infty \; anzn,\; |\; z\; |\; \le \; 1\}.\; \{\backslash \; Displaystyle\; \backslash \; влево\; \backslash \; \{е:\; х\; \backslash \; в\; [0,\; \backslash \; пи]\; \backslash \; вправо\; \backslash \; сумма\; \_\; \{п\; =\; 0\}\; ^\; \{\backslash \; infty\}\; а\_\; \{п\}\; \backslash \; соз\; (пх)\; \backslash \; вправо\; \backslash \}\; \backslash \; longrightarrow\; \backslash \; влево\; \backslash \; \{T\; (f):\; z\; \backslash \; rightarrow\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\backslash \; infty\}\; a\_\; \{n\}\; z\; ^\; \{n\},\; \backslash \; quad\; |\; z\; |\; \backslash \; leq\; 1\; \backslash \; right\; \backslash \}.\}$

Базис Бочкарева для A (D) образуют образы под T функций из системы Франклина на [0, π]. Эквивалентное описание Бочкарева для отображения T начинается с расширения f до четной липшицевой функции g 1 на [−π, π], отождествляемой с липшицевой функцией на единичной окружности T. Затем, пусть g 2 будет сопряженной функцией для g 1, и определим T (f) как функцию в A (D), значение которой на Граница T области D равна g 1 + ig 2.

При работе с 1-периодическими непрерывными функциями или, скорее, с непрерывными функциями f на [0, 1], такими что f (0) = f (1), удаляют функцию s 1 (t) = t из системы Фабера – Шаудера, чтобы получить периодическую систему Фабера – Шаудера . Периодическая система Франклина получается ортонормировкой из периодической системы Фабера – Шаудера. Можно доказать результат Бочкарева о A (D), доказав, что периодическая система Франклина на [0, 2π] является базисом для банахова пространства A r, изоморфного A (D). Пространство A r состоит из сложных непрерывных функций на единичной окружности T, чья сопряженная функция также непрерывна.

Матрица Хаара 2 × 2, связанная с вейвлетом Хаара, равна

$H\; 2\; =\; [1\; 1\; 1\; -\; 1].\; \{\backslash \; displaystyle\; H\_\; \{2\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 1\; \backslash \backslash \; 1\; -1\; \backslash \; end\; \{bmatrix\}\}.\}$

Используя дискретное вейвлет-преобразование, можно преобразовать любую последовательность $(a\; 0,\; a\; 1,\dots ,\; a\; 2\; n,\; a\; 2\; n\; +\; 1)\; \{\backslash \; displaystyle\; (a\_\; \{0\},\; a\_\; \{1\},\; \backslash \; dots,\; a\_\; \{2n\},\; a\_\; \{2n\; +\; 1\})\}$четной длины в последовательность двухкомпонентных векторов $((a\; 0,\; a\; 1),\dots ,\; (a\; 2\; n,\; a\; 2\; n\; +\; 1))\; \{\backslash \; displaystyle\; \backslash \; left\; (\; \backslash \; left\; (a\_\; \{0\},\; a\_\; \{1\}\; \backslash \; right),\; \backslash \; dots,\; \backslash \; left\; (a\_\; \{2n\},\; a\_\; \{2n\; +\; 1\}\; \backslash \; right)\; \backslash \; right)\}$. Если умножить каждый вектор вправо на матрицу $H\; 2\; \{\backslash \; displaystyle\; H\_\; \{2\}\}$, получится результат $((s\; 0,\; d\; 0),\dots ,\; (sn,\; dn))\; \{\backslash \; displaystyle\; \backslash \; left\; (\backslash \; left\; (s\_\; \{0\},\; d\_\; \{0\}\; \backslash \; right),\; \backslash \; dots,\; \backslash \; left\; (s\_\; \{n\},\; d\_\; \{n\}\; \backslash \; right)\; \backslash \; right)\}$одной стадии быстрого вейвлет-преобразования Хаара. Обычно разделяют последовательности s и d и продолжают преобразовывать последовательность s. Последовательность s часто называют частью средних значений, тогда как последовательность d известна как часть деталей.

Если длина последовательности кратна четырем, можно построить блоки из 4 элементов и преобразовать их в аналогично с матрицей Хаара 4 × 4

$H\; 4\; =\; [1\; 1\; 1\; 1\; 1\; 1\; -\; 1\; -\; 1\; 1\; -\; 1\; 0\; 0\; 0\; 0\; 1\; -\; 1],\; \{\backslash \; displaystyle\; H\_\; \{4\}\; =\; \{\backslash \; begin\; \{\; bmatrix\}\; 1\; 1\; 1\; 1\; \backslash \backslash \; 1\; 1\; -1\; -1\; \backslash \backslash \; 1\; -1\; 0\; 0\; \backslash \backslash \; 0\; 0\; 1\; -1\; \backslash \; end\; \{bmatrix\}\},\}$

, которое объединяет два этапа быстрого вейвлет-преобразования Хаара.

Сравните с матрицей Уолша, которая является нелокализованной матрицей 1 / –1.

Как правило, матрицу Хаара 2N × 2N можно получить с помощью следующего уравнения.

$H\; 2\; N\; =\; [HN\; \otimes \; [1,\; 1]\; IN\; \otimes \; [1,\; -\; 1]]\; \{\backslash \; displaystyle\; H\_\; \{2N\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; H\_\; \{N\}\; \backslash \; otimes\; [1,1]\; \backslash \; \backslash \; I\_\; \{N\}\; \backslash \; otimes\; [1,\; -1]\; \backslash \; end\; \{bmatrix\}\}\}$

где $IN\; =\; [1\; 0\dots \; 0\; 0\; 1\dots \; 0\; ⋮\; ⋮\; \ddots \; ⋮\; 0\; 0\dots \; 1]\; \{\backslash \; displaystyle\; I\_\; \{N\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 0\; \backslash \; dots\; 0\; \backslash \backslash \; 0\; 1\; \backslash \; dots\; 0\; \backslash \backslash \backslash \; vdots\; \backslash \; vdots\; \backslash \; ddots\; \backslash \; vdots\; \backslash \backslash \; 0\; 0\; \backslash \; dots\; 1\; \backslash \; end\; \{bmatrix\}\}\}$и $\otimes \; \{\backslash \; displaystyle\; \backslash \; otimes\}$- это произведение Кронекера.

произведение Кронекера из $A\; \otimes \; B\; \{\backslash \; displaystyle\; A\; \backslash \; otimes\; B\}$, где $A\; \{\backslash \; displaystyle\; A\}$- это матрица m × n, а $B\; \{\backslash \; displaystyle\; B\}$- Матрица ap × q, выражается как

$A\; \otimes \; B\; =\; [a\; 11\; B\dots \; a\; 1\; n\; B\; ⋮\; \ddots \; ⋮\; am\; 1\; B\dots \; amn\; B].\; \{\backslash \; displaystyle\; A\; \backslash \; otimes\; B\; =\; \{\backslash \; begin\; \{bmatrix\}\; a\_\; \{11\}\; B\; \backslash \; dots\; a\_\; \{1n\}\; B\; \backslash \backslash \backslash \; vdots\; \backslash \; ddots\; \backslash \; vdots\; \backslash \backslash \; a\_\; \{m1\}\; B\; \backslash \; dots\; a\_\; \{mn\}\; B\; \backslash \; end\; \{bmatrix\}\}.\}$

Ненормированная матрица Хаара из 8 точек $H\; 8\; \{\backslash \; displaystyle\; H\_\; \{8\}\}$показана ниже

$H\; 8\; =\; [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\; 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].\; \{\backslash \; Displaystyle\; Н\_\; \{8\}\; =\; \{\backslash \; BEGIN\; \{bmatrix\}\; 1\; 1\; 1\; 1\; 1\; 1\; 1\; 1\; \backslash \backslash \; 1\; 1\; 1\; 1\; -1\; -1\; -1\; -1\; \backslash \backslash \; 1\; 1\; -1\; -1\; 0\; 0\; 0\; 0\; \backslash \backslash \; 0\; 0\; 0\; 0\; 1\; 1\; -1\; -1\; \backslash \backslash \; 1\; -1\; 0\; 0\; 0\; 0\; 0\; 0\; \backslash \backslash \; 0\; 0\; 1\; -1\; 0\; 0\; 0\; 0\; \backslash \backslash \; 0\; 0\; 0\; 0\; 1\; -1\; 0\; 0\; \backslash \backslash \; 0\; 0\; 0\; 0\; 0\; 0\; 1\; -1\; \backslash \; end\; \{bmatrix\}\}.\}$

Обратите внимание, что приведенная выше матрица является ненормализованной матрицей Хаара. Матрица Хаара, требуемая преобразованием Хаара, должна быть нормализована.

Из определения матрицы Хаара $H\; \{\backslash \; displaystyle\; H\}$можно заметить, что, в отличие от преобразования Фурье, $H\; \{\backslash \; displaystyle\; H\}$имеет только действительные элементы (например, 1, -1 или 0) и не является симметричным.

В качестве примера возьмем 8-точечную матрицу Хаара $H\; 8\; \{\backslash \; displaystyle\; H\_\; \{8\}\}$. Первая строка $H\; 8\; \{\backslash \; displaystyle\; H\_\; \{8\}\}$измеряет среднее значение, а вторая строка $H\; 8\; \{\backslash \; displaystyle\; H\_\; \{8\}\}$измеряет низкочастотную составляющую входного вектора. Следующие две строки чувствительны к первой и второй половине входного вектора соответственно, что соответствует умеренным частотным компонентам. Остальные четыре строки чувствительны к четырем частям входного вектора, которые соответствуют высокочастотным компонентам.

Преобразование Хаара является самым простым из вейвлет-преобразование. Это преобразование выполняет перекрестное умножение функции на вейвлет Хаара с различными сдвигами и растяжениями, подобно тому, как преобразование Фурье перекрестно умножает функцию на синусоидальную волну с двумя фазами и многими отрезками.

Введение

Преобразование Хаара - одна из старейших функций преобразования, предложенная в 1910 году венгерским математиком Альфредом Хааром. Он оказался эффективным в таких приложениях, как сжатие сигналов и изображений в электротехнике и вычислительной технике, поскольку обеспечивает простой и эффективный с вычислительной точки зрения подход к анализу локальных аспектов сигнала.

Преобразование Хаара выводится из матрицы Хаара. Пример матрицы преобразования Хаара 4x4 показан ниже.

$Ч\; 4\; =\; 1\; 2\; [1\; 1\; 1\; 1\; 1\; 1\; -\; 1\; -\; 1\; 2\; -\; 2\; 0\; 0\; 0\; 0\; 2\; -\; 2]\; \{\backslash \; displaystyle\; H\_\; \{4\}\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 1\; 1\; 1\; \backslash \backslash \; 1\; 1\; -1\; -1\; \backslash \backslash \; \{\backslash \; sqrt\; \{2\}\}\; -\; \{\backslash \; sqrt\; \{2\}\}\; 0\; 0\; \backslash \backslash \; 0\; 0\; \{\backslash \; sqrt\; \{2\}\}\; -\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; end\; \{bmatrix\}\}\}$

Преобразование Хаара можно рассматривать как процесс выборки, в котором строки матрицы преобразования действуют как выборки все более и более высокого разрешения.

Сравните с преобразованием Уолша, которое также равно 1 / –1, но не локализовано.

Свойство

Преобразование Хаара имеет следующие свойства

1. Нет необходимости в умножении. Для этого требуются только дополнения, а в матрице Хаара много элементов с нулевым значением, поэтому время вычислений невелико. Это быстрее, чем преобразование Уолша, матрица которого состоит из +1 и -1.

2. Длина входа и выхода одинакова. Однако длина должна быть степенью двойки, то есть $N\; =\; 2\; k,\; k\; \in \; N\; \{\backslash \; displaystyle\; N\; =\; 2\; ^\; \{k\},\; k\; \backslash \; in\; \backslash \; mathbb\; \{N\}\}$.

3. Его можно использовать для анализа локализованных характеристик сигналов. Благодаря свойству ортогональности функции Хаара можно анализировать частотные компоненты входного сигнала.

Преобразование Хаара и обратное преобразование Хаара

Преобразование Хаара y n функции ввода n x n равно

$yn\; =\; H\; nxn\; \{\backslash \; displaystyle\; y\_\; \{n\}\; =\; H\_\; \{n\}\; x\_\; \{n\}\}$

Матрица преобразования Хаара является действительной и ортогональные. Таким образом, обратное преобразование Хаара может быть получено с помощью следующих уравнений.

$H\; =\; H\; *,\; H\; -\; 1\; =\; HT,\; т.е.\; HHT\; =\; I\; \{\backslash \; displaystyle\; H\; =\; H\; ^\; \{*\},\; H\; ^\; \{-\; 1\}\; =\; H\; ^\; \{T\},\; \{\backslash \; text\; \{ie\}\}\; HH\; ^\; \{T\}\; =\; I\}$

где $I\; \{\backslash \; displaystyle\; I\}$- единичная матрица. Например, когда n = 4

$H\; 4\; TH\; 4\; =\; 1\; 2\; [1\; 1\; 2\; 0\; 1\; 1\; -\; 2\; 0\; 1\; -\; 1\; 0\; 2\; 1\; -\; 1\; 0\; -\; 2]\; \cdot \; 1\; 2\; [1\; 1\; 1\; 1\; 1\; 1\; -\; 1\; -\; 1\; 2\; -\; 2\; 0\; 0\; 0\; 0\; 2\; -\; 2]\; =\; [1\; 0\; 0\; 0\; 0\; 1\; 0\; 0\; 0\; 0\; 1\; 0\; 0\; 0\; 0\; 1]\; \{\backslash \; displaystyle\; H\_\; \{4\}\; ^\; \{T\}\; H\_\; \{4\}\; =\; \{\; \backslash \; frac\; \{1\}\; \{2\}\}\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 1\; \{\backslash \; sqrt\; \{2\}\}\; 0\; \backslash \backslash \; 1\; 1\; -\; \{\backslash \; sqrt\; \{2\}\}\; 0\; \backslash \backslash \; 1\; -1\; 0\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \backslash \; 1\; -1\; 0\; -\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; end\; \{bmatrix\}\}\; \backslash \; cdot\; \backslash ;\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 1\; 1\; 1\; \backslash \backslash \; 1\; 1\; 1\; -1\; -1\; \backslash \backslash \; \{\backslash \; sqrt\; \{2\}\}\; -\; \{\backslash \; sqrt\; \{2\}\}\; 0\; 0\; \backslash \backslash \; 0\; 0\; \{\backslash \; sqrt\; \{2\}\}\; -\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 0\; 0\; 0\; \backslash \backslash \; 0\; 1\; 0\; 0\; \backslash \backslash \; 0\; 0\; 1\; 0\; \backslash \backslash \; 0\; 0\; 0\; 1\; \backslash \; end\; \{bmatrix\}\}\}$

Таким образом, обратное преобразование Хаара равно

$xn\; =\; HT\; yn\; \{\backslash \; displaystyle\; x\_\; \{n\}\; =\; H\; ^\; \{T\}\; y\_\; \{n\}\}$

Пример

Коэффициенты преобразования Хаара = 4-точечный сигнал $x\; 4\; =\; [1,\; 2,\; 3,\; 4]\; T\; \{\backslash \; displaystyle\; x\_\; \{4\}\; =\; [1,2,3,\; 4]\; ^\; \{T\}\}$можно найти как

$y\; 4\; =\; H\; 4\; x\; 4\; =\; 1\; 2\; [1\; 1\; 1\; 1\; 1\; 1\; -\; 1\; -\; 1\; 2\; -\; 2\; 0\; 0\; 0\; 0\; 2\; -\; 2]\; [1\; 2\; 3\; 4]\; =\; [5–2–1\; /\; 2–1\; /\; 2]\; \{\backslash \; displaystyle\; y\_\; \{4\}\; =\; H\_\; \{4\}\; x\_\; \{4\}\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \{\; \backslash \; begin\; \{bmatrix\}\; 1\; 1\; 1\; 1\; \backslash \backslash \; 1\; 1\; -1\; -1\; \backslash \backslash \; \{\backslash \; sqrt\; \{2\}\}\; -\; \{\backslash \; sqrt\; \{2\; \}\}\; 0\; 0\; \backslash \backslash \; 0\; 0\; \{\backslash \; sqrt\; \{2\}\}\; -\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; end\; \{bmatrix\}\}\; \{\backslash \; begin\; \{bmatrix\}\; 1\; \backslash \backslash \; 2\; \backslash \backslash \; 3\; \backslash \backslash \; 4\; \backslash \; end\; \{bmatrix\}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; 5\; \backslash \backslash \; -\; 2\; \backslash \backslash \; -\; 1\; /\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \backslash \; -\; 1\; /\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; end\; \{bmatrix\}\}\}$

Входной сигнал может затем можно полностью восстановить с помощью обратного преобразования Хаара

$x\; 4\; ^\; =\; H\; 4\; T\; y\; 4\; =\; 1\; 2\; [1\; 1\; 2\; 0\; 1\; 1\; -\; 2\; 0\; 1\; -\; 1\; 0\; 2\; 1\; -\; 1\; 0\; -\; 2]\; [5\; -\; 2\; -\; 1/2\; -\; 1/2]\; =\; [1\; 2\; 3\; 4]\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{x\_\; \{4\}\}\}\; =\; H\_\; \{4\}\; ^\; \{T\}\; y\_\; \{4\}\; =\; \{\backslash \; frac\; \{1\}\; \{\; 2\}\}\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 1\; \{\backslash \; sqrt\; \{2\}\}\; 0\; \backslash \backslash \; 1\; 1\; -\; \{\backslash \; sqrt\; \{2\}\}\; 0\; \backslash \backslash \; 1\; -1\; 0\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \backslash \; 1\; -1\; 0\; -\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; end\; \{bmatrix\}\}\; \{\backslash \; begin\; \{bmatrix\}\; 5\; \backslash \backslash \; -\; 2\; \backslash \backslash \; -\; 1\; /\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \backslash \; -\; 1\; /\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; end\; \{bmatrix\; \}\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; 1\; \backslash \backslash \; 2\; \backslash \backslash \; 3\; \backslash \backslash \; 4\; \backslash \; end\; \{bmatrix\}\}\}$

Приложение

Современные камеры способны создавать изображения с разрешением в диапазоне десятков мегапикселей. Эти изображения необходимо сжать перед сохранением и передачей. Преобразование Хаара можно использовать для сжатия изображений. Основная идея состоит в том, чтобы передать изображение в матрицу, в которой каждый элемент матрицы представляет пиксель изображения. Например, матрица 256 × 256 сохраняется для изображения 256 × 256. JPEG Сжатие изображений включает разрезание исходного изображения на фрагменты изображения 8 × 8. Каждое суб-изображение представляет собой матрицу 8 × 8.

Требуется двумерное преобразование Хаара. Уравнение преобразования Хаара: $B\; n\; =\; H\; n\; A\; n\; H\; n\; T\; \{\backslash \; displaystyle\; B\_\; \{n\}\; =\; H\_\; \{n\}\; A\_\; \{n\}\; H\_\; \{n\}\; ^\; \{T\}\}$, где $A\; n\; \{\backslash \; displaystyle\; A\_\; \{n\}\}$- матрица × n, а $H\; n\; \{\backslash \; displaystyle\; H\_\; \{n\}\}$- n- точечное преобразование Хаара. Обратное преобразование Хаара: $A\; n\; =\; H\; n\; TB\; n\; H\; n\; \{\backslash \; displaystyle\; A\_\; \{n\}\; =\; H\_\; \{n\}\; ^\; \{T\}\; B\_\; \{n\}\; H\_\; \{n\}\}$

• Уменьшение размеров
• Матрица Уолша
• Преобразование Уолша
• Вейвлет
• Сигнал
• Функция, подобная Хаару
• Вейвлет Стрёмберга
• Диадическое преобразование

• Хаар, Альфред (1910), «Zur Theorie der orthogonalen Funktionensysteme», Mathematische Annalen, 69(3): 331–371, doi : 10.1007 / BF01456326, hdl : 2027 / uc1.b2619563
• Чарльз К. Чуи, Введение в вейвлеты, (1992), Academic Press, Сан-Диего, ISBN 0-585-47090-1
• Английский перевод основополагающей статьи Хаара: https://www.uni-hohenheim.de/~gzim/Publications/haar.pdf

Викискладе есть средства массовой информации, связанные с вейвлетом Хаара.

• , Энциклопедия математики, EMS Press, 2001 [1994]
• Бесплатная реализация фильтрации вейвлетов Хаара и интерактивная demo
• Бесплатный шумоподавление Хаара и сигнал с потерями l сжатие

Преобразование Хаара

• [1 ]
• [2 ]
• [3 ]
• [4 ]
• [5 ]