Типы и свойства компактных волн

В этом разделе дано подробное описание формализма компактно-волновых преобразований, как непрерывных, так и дискретных, а также обсуждается тесная связь аппроксимационных свойств этих преобразований и представлений функций искусственными нейронными сетями.

Непрерывное W-преобразование (CWT)

Во веденном формально в Теореме 1 предыдущей главы непрерывное W-преобразование (CWT - Continuous Wavelet Transform) требование конечности значения интеграла от Фурье-преобразования вейвлета и масштабирующей функции является принципиально важным для существования обратного преобразования (синтеза)

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

Коэффициенты разложения могут быть наглядно представлены графически (примеры представлений приведены во вводном разделе на Рис.2 и Рис.4). Как уже отмечалось, максимумы иллюстрируют локальные изменения частоты колебаний сигнала с течением времени. Для описания структуры сигнала в целом, достаточно в коэффициентах разложения сохранить только эти пики, при этом при обратном преобразовании сигнал будет воспроизведен с высокой точностью. Таким образом достигается очень компактное и информативное описание функции (см. ниже раздел о сжатии информации при помощи вейвлет-преобразования).

Выбор конкретного семейства компактных волн диктуется прикладными потребностями и типом информации о сигнале, который требуется максимально проявить. Так, применение G2-волн (см Рис.1) удобно для анализа временного поведения экстремумов сигнала, а применение G1-волны - для представления нулей функции. При этом функция G1 выполняет, в качественном смысле, вычисление "первой производной" функции на разных масштабах приращения аргумента, а G2, соответственно, "второй производной".

Принцип неопределенности для W-преобразований

Вейвлет-представления не позволяют получить информацию об изменениях колебательных свойствах сигналов с произвольной степенью локализации. Локализация во временном представлении и в частотном представлении взаимоисключается4. Легко установить, что если ненулевая функция мала вне временного интервала длины T и ее Фурье-преобразование мало вне некоторого диапазона частот , то выполняется соотношение T > a для некоторой положительной константы a ~ 1. Точное значение a определяется способом вычисления и T. Так, для гаусова нормированного сигнала

можно вычислить характерную дисперсию сигнала по времени и по частоте

При таком определении константа неопределенности равна a = 1/4.

В случае компактно-волнового преобразования - свертки сигнала с функцией характерные аргументы , дающие вклад в интеграл, определяются характерной шириной вейвлета . Поэтому если сигнал доступен для наблюдений в течение отрезка времени 0 < (t-T) < T, то достоверно вычисленными (информативными) будут W-коэффициенты только для периодов < T/a, где a - характерная ширина компактной волны. Соотношение неопределенности в данном случае имеет вид T/ > a.

Соотношение неопределенности не позволяет, например, сделать в точном смысле утверждение типа "спектр сигнала в момент t равен ...", хотя функция , разумеется, определена и однозначна для каждого значения своих аргументов, и существует однозначное обратное преобразование.

Дискретное W-преобразование (DWT)

Непрерывное W-преобразование может быть проведено аналитически лишь для простейших функций, а вычисление его на ЭВМ при помощи квадратур является весьма трудоемким. Поэтому в приложениях обычно используется дискретный вариант, который при специальном выборе базисных функций может быть выполнен крайне эффективно и без дополнительных затрат памяти (вектор коэффициентов рекурсивно замещает вектор исходных значений). Дискретное W-преобразование может выполняться аппаратно на специализированных процессорах, как и быстрое преобразование Фурье.

Для построения дискретного разложения по компактным волнам необходимо выполнение следующих четырех условий [Daubechies88]:

Определение. Для целого m под компактной волной класса m понимается функция одного действительного переменного s(x), такая, что:
  1. Функция s(x) имеет m ограниченных производных, определенных почти везде;
  2. Функция s(x) равна нулю вне некоторого интервала (a,b);
  3. Первые m моментов функции s(x) равны нулю;
  4. Семейство , где j, k - целые, образует ортонормированный базис для функций, интегрируемых с квадратом на действительной оси;

Существование таких компактных волн было показано И.Добечи [Daubechies88]. Согласно свойству 4), базис строится рекуррентно, что удобно для программных и аппаратных реализаций. Необходимо отметить, что хотя речь идет об аппроксимации непрерывных интегрируемых функций, базисные функции имеют весьма сложный вид (в частности, для функций Добечи нет явных выражений, лишь рекуррентные, см. также Рис. 6).

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

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


Рис.5. Вейвлет и масштабирующая функция Хаара (вверху) и Добечи (внизу).

Рассмотрим основные идеи дискретного W-преобразования на примере компактной волны Хаара. Пусть некоторый сигнал задан дискретной последовательностью отсчетов Sn. Выберем два последовательных отсчета, a = Sk и b = Sk+1, и перейдем к их среднему и разности:

p = (a + b)/2,     q = b - a

Полезность такого представления состоит в том, если в сигнале присутствуют значительные корреляции между последовательными отсчетами, то величина разности q мала (в пределе a=b, q=0), и может быть представлена в ЭВМ меньшим числом бит. При этом не происходит потери информации, поскольку имеется обратное преобразование:

a = p - q/2,     b = p + q/2

Если выполнить описанное преобразование для всех последовательных пар6 отсчетов сигнала Sn = {Sn,m | m < 2n} длины 2n, то он распадается на два сигнала половинной длины:

Sn-1,m = ( Sn,2m + Sn,2m+1 ) / 2

Dn-1,m = Sn,2m+1 - Sn,2m

Вектор средних значений Sn-1,m можно рассматривать, как огрубленное (но сжатое!) представление исходного вектора Sn,m, а вектор разностей Dn-1,m - как детализирующую информацию, необходимую для перехода из сжатого представления к исходному. Далее, такое же преобразование можно применить к сжатому сигналу Sn-1,m, переходя к еще более компактному и огрубленному представлению. Рекурсивно выполняя преобразование n раз, мы получаем из исходного сигнала n его версий с огрублением на разных масштабах. Самое грубое представление S0,0 - это просто среднее от всего сигнала.

Процедура Хаара для конкретного вида функции была предложена Хааром (Alfred Haar) в 1910. Сам Хаар не называл свою функцию вейвлетом - термин появился гораздо позднее. Функция Хаара обладает важной особенностью - это единственный вейвлет с компактным носителем (отрезок [0,1]), имеющий явное выражение формулой. Подробный пример применения преобразования Хаара имеется на сервере Стэнфордского университета URL: http://robotics.stanford.edu/~scohen/lect02/lect02.html

Описанная процедура и есть дискретное преобразование Хаара. Полное число коэффициентов разложения равно исходному числу отсчетов - 2n, однако информационная нагрузка их (и, соответственно, требуемая точность представления) различна. Обратное преобразование выполняется также рекуррентно, по обратным формулам. Полное число операций пропорционально n (что эффективнее, чем быстрое преобразование Фурье, требующее O(n log n) операций). Имеются удобные схемы проведения вычислений (аналогичные методу прогонки), при которых все коэффициенты преобразования размещаются на месте хранения исходного сигнала, т.е. не требуется дополнительной памяти для ЭВМ или для специализированного процессора.

Необходимо отметить, что описанная схема вычислений эквивалентна разложению кусочно-постоянного аналога дискретного сигнала по базису , где s - изображенный на Рис. 5 (вверху) вейвлет Хаара.

В качестве иллюстрации приведем для вектора из 4 компонент разложение по базисным векторам Хаара:

Рекуррентное W-преобразование Хаара имеет по меньшей мере два ценных практических свойства, определяющие перспективность применения компактных волн для телекоммуникаций и архивов видеоинформации (см. также раздел 3):

Преобразования высоких порядков

Вернемся к формулам преобразования Хаара. В рассматриваемой паре отсчетов a и b значение a может рассматриваться, как прогноз для следующего отсчета b, для уточнения которого используется коэффициент разложения q. В случае преобразования Хаара прогноз b по a оказывается точным для постоянных сигналов (полиномов нулевой степени). Однако формулы прогноза и коррекции (т.е. вычисления p и d) могут быть усложнены и сделаны точными для полиномов более высоких степеней7. В этом случае получаются W-преобразования высоких порядков, которые при одинаковом числе незануленных коэффициентов могут давать более точное представление сигнала, чем формулы Хаара нулевого порядка.

В литературе имеются формулы различных порядков для дискретных вычислений (и соответствующие непрерывные аналоги для производящих функций s(x), например волна Добечи 2-го порядка на Рис.5). Выбор формулы диктуется особенностями конкретных приложений (гладкостью сигнала, требуемым уровнем сжатия, стоимостью вычислений, которая растет с ростом порядка). Многообразие типов дискретных W-преобразований в каком-то смысле соответствует многообразию квадратурных формул для численных методов интегрирования.


Рис.6 Фрактальная структура вейвлета Добечи.

Рассмотрим процесс построения преобразований высоких порядков подробнее [Press97]. Для этого отметим, что преобразование Хаара от некоторого вектора соответствует умножению его на матрицу:

1 10
1 -1
1 1
1 -1
...
1 1
01 -1

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

Более общий случай преобразования может быть получен в форме Добечи:

C0 C1C2 C3
C3 -C2C1 -C0
C0 C1C2 C3
C3 -C2C1 -C0
......
C0 C1C2 C3
C3 -C2C1 -C0
C2 C3C0 C1
C1 -C0C3 -C2

Каждая строка матрицы соответствует свертке вектора сигнала с локализованным вейвлет-фильтром. При этом нечетные строки "сглаживают", а соответствующие четные фильтры вычисляют поправки к сглаживанию, обеспечивая обратимость преобразования. Коэффициенты C0 .. C3 могут быть выбраны так, чтобы поправки обращались в ноль для гладких функций (в преобразовании Хаара поправка равнялась нулю только для постоянных функций). Зануление свертки с постоянной и линейной функциями дает два условия на неизвестные коэффициенты:

C3 -C2 + C1 -C0 = 0
0 x C3 - 1 x C2 + 2 x C1 - 3 x C0 = 0

Кроме того, потребуем, чтобы преобразование было ортогональным - обратное преобразование получалось простым транспонированием. Из условия равенства произведения матриц прямого и обратного преобразований единичной матрице получаем еще два условия:

C02 + C12 + C22 + C32 = 1
C2C0 + C3C1 = 0

Откуда:

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



Главная страница   |   Наверх   |   Содержание   |   Литература

Hosted by uCoz