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

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

История

Вейвлеты были введены венгерским математиком Альфредом Хааром в 1909 году в его докторской диссертации. Хаар предложил систему функций, которая представляла собой ортонормированный базис в пространстве \( L^2([0,1]) \) — пространстве функций с интегрируемым квадратом на единичном отрезке. В отличие от тригонометрических рядов Фурье, которые используют гладкие синусоидальные функции, вейвлеты Хаара являются разрывными и кусочно-постоянными, что позволяет лучше аппроксимировать резкие перепады сигнала.

Первоначально работа Хаара не получила широкого признания и оставалась в основном математическим курьёзом. Интерес к вейвлетам возродился в 1980-х годах, когда исследователи в области обработки сигналов (в частности, Ингрид Добеши) разработали теорию вейвлетов и их практические приложения. Вейвлеты Хаара стали отправной точкой для создания более сложных вейвлетов (например, вейвлетов Добеши, симлетов, койфлетов), которые обладают гладкостью и лучшими частотными характеристиками.

Определение и математическое описание

Материнский вейвлет и скейлинг-функция

В основе вейвлетов Хаара лежат две базовые функции:

1. Скейлинг-функция (масштабирующая функция) \(\phi(x)\), которая задаётся как:

\[ \phi(x) = \begin{cases} 1, & 0 \le x < 1, \\ 0, & \text{иначе}. \end{cases} \]

1. Материнский вейвлет \(\psi(x)\), определяемый как:

\[ \psi(x) = \begin{cases} 1, & 0 \le x < \frac{1}{2}, \\ -1, & \frac{1}{2} \le x < 1, \\ 0, & \text{иначе}. \end{cases} \]

Эти функции обладают нулевым средним значением (интеграл от \(\psi(x)\) равен нулю) и единичной энергией (интеграл от квадрата функции равен 1).

Ортогональный базис

С помощью сдвигов и масштабирований материнского вейвлета и скейлинг-функции строится ортонормированный базис в \(L^2(\mathbb{R})\). Для любого целого \(j\) (масштаб) и целого \(k\) (сдвиг) определяются функции: \[ \phi_{j,k}(x) = 2^{j/2} \phi(2^j x - k), \quad \psi_{j,k}(x) = 2^{j/2} \psi(2^j x - k). \]

Семейство \(\{\phi_{j,k}, \psi_{j,k}\}\) образует ортонормированный базис. Любая функция \(f(x) \in L^2(\mathbb{R})\) может быть представлена в виде суммы аппроксимирующей (низкочастотной) и детализирующей (высокочастотной) компонент: \[ f(x) = \sum_{k} a_{j_0,k} \phi_{j_0,k}(x) + \sum_{j=j_0}^{\infty} \sum_{k} d_{j,k} \psi_{j,k}(x), \] где \(a_{j_0,k}\) — коэффициенты аппроксимации на уровне \(j_0\), а \(d_{j,k}\) — детализирующие коэффициенты.

Свойства

• Ортогональность: Функции \(\psi_{j,k}\) и \(\phi_{j,k}\) ортогональны друг другу при разных масштабах и сдвигах.
• Компактный носитель: Каждая функция отлична от нуля только на интервале длины \(2^{-j}\).
• Разрывность: Вейвлеты Хаара являются разрывными функциями, что ограничивает их применение для гладких сигналов.
• Простота вычислений: Преобразование Хаара требует только операций сложения и вычитания, что делает его быстрым и эффективным.

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

Прямое преобразование

Для дискретного сигнала длины \(N = 2^n\) (степень двойки) преобразование Хаара выполняется рекурсивно. На каждом шаге сигнал разбивается на пары соседних отсчётов. Для каждой пары \((x_{2i}, x_{2i+1})\) вычисляются:

• среднее (аппроксимация): \(s_i = (x_{2i} + x_{2i+1}) / \sqrt{2}\),
• разность (деталь): \(d_i = (x_{2i} - x_{2i+1}) / \sqrt{2}\).

Процесс повторяется для полученных средних значений, пока не останется одно среднее (глобальное среднее сигнала). В результате получается иерархическая структура коэффициентов: один аппроксимирующий коэффициент и \(N-1\) детализирующих.

Обратное преобразование

Восстановление сигнала из коэффициентов выполняется в обратном порядке: по паре \((s_i, d_i)\) восстанавливаются исходные отсчёты: \[ x_{2i} = (s_i + d_i) / \sqrt{2}, \quad x_{2i+1} = (s_i - d_i) / \sqrt{2}. \]

Пример

Для сигнала \([1, 2, 3, 4]\):

• Первый уровень: средние: \((1+2)/\sqrt{2} = 3/\sqrt{2}\), \((3+4)/\sqrt{2} = 7/\sqrt{2}\); детали: \((1-2)/\sqrt{2} = -1/\sqrt{2}\), \((3-4)/\sqrt{2} = -1/\sqrt{2}\).
• Второй уровень: среднее от средних: \((3/\sqrt{2} + 7/\sqrt{2})/\sqrt{2} = 10/2 = 5\); деталь: \((3/\sqrt{2} - 7/\sqrt{2})/\sqrt{2} = -4/2 = -2\).
• Итоговые коэффициенты: аппроксимация \([5]\), детали \([-2, -1/\sqrt{2}, -1/\sqrt{2}]\).

Применение

Сжатие изображений

Вейвлеты Хаара используются в алгоритмах сжатия изображений, в частности, в формате JPEG 2000 (хотя в нём применяются более сложные вейвлеты). Благодаря свойству концентрировать энергию сигнала в небольшом числе коэффициентов, многие детализирующие коэффициенты оказываются близкими к нулю и могут быть отброшены без значительной потери качества. Это позволяет достигать высоких степеней сжатия.

Обработка сигналов

Вейвлеты Хаара применяются для шумоподавления, обнаружения разрывов и выделения особенностей сигналов. Например, в геофизике и медицине (анализ ЭКГ) они позволяют выделять резкие изменения, такие как зубцы R на кардиограмме.

Численные методы

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

Компьютерное зрение

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

Ограничения и критика

Основным недостатком вейвлетов Хаара является их разрывность, что приводит к плохой аппроксимации гладких функций и появлению артефактов (эффект «ступенек») при сжатии изображений. Кроме того, вейвлеты Хаара не обладают свойством симметрии (кроме тривиального случая), что может быть важно для некоторых приложений, например, для обработки изображений без фазовых искажений.

Для преодоления этих ограничений были разработаны более гладкие вейвлеты (например, вейвлеты Добеши, которые имеют компактный носитель и произвольную гладкость), а также биортогональные вейвлеты, которые допускают симметричные фильтры.

Интересные факты

• Вейвлеты Хаара являются единственными вейвлетами, которые одновременно являются ортогональными, симметричными и имеют компактный носитель, но только для тривиального случая (симметрия отсутствует).
• Преобразование Хаара может быть реализовано с вычислительной сложностью \(O(N)\), что делает его одним из самых быстрых вейвлет-преобразований.
• Вейвлеты Хаара лежат в основе многих учебных примеров по теории вейвлетов благодаря своей наглядности.

Источники

1. Haar, A. (1910). Zur Theorie der orthogonalen Funktionensysteme. Mathematische Annalen, 69(3), 331–371.
2. Daubechies, I. (1992). Ten Lectures on Wavelets. SIAM.
3. Mallat, S. (2009). A Wavelet Tour of Signal Processing: The Sparse Way. Academic Press.
4. Strang, G., & Nguyen, T. (1996). Wavelets and Filter Banks. Wellesley-Cambridge Press.
5. Гонсалес, Р., Вудс, Р. (2012). Цифровая обработка изображений. Техносфера.