Вейвлетный кратномасштабный анализ

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:43, 17 ноября 2016.


Кратномасштабный анализ (КМА) является инструментом построения базисов всплесков. Он был разработан в 1988/89 гг. Малла и И. Мейром. Идея кратномасштабного анализа заключается в том, что разложение сигнала производится по ортогональному базису, образованному сдвигами и кратномасштабными копиями вейвлетной функции. Свертка сигнала с вейвлетами позволяет выделить характерные особенности сигнала в области локализации этих вейвлетов.

Введение

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

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

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

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

Понятие кратномасштабного анализа (Multiresolution analyses) является фундаментальным в теории вейвлетов. Это определяется тем, что для кратномасштабного анализа разработан быстрый каскадный алгоритм вычислений, подобный быстрому преобразованию Фурье.

Принцип кратномасштабного анализа

Дискретные ортогональные преобразования

Непрерывное вейвлет-преобразование, равно как и его прямой дискретный аналог с произвольным шагом по масштабу и сдвигу, несет огромное количество информации о сигнале, но обладает сильной избыточностью. Интуитивно понятно, что если какая-либо информация заключена в отсчетах сигнала, то при любых преобразованиях сигнала для отображения этой информации без потерь в новом представлении (новом базисном пространстве) должно быть необходимо и достаточно то же самое количество отсчетов . С учетом принципа неопределенности Гейзенберга это означает, что для точного восстановления сигнала достаточно знать его вейвлет-преобразование на некоторой довольно редкой решетке частотно-временной области, густой в области высоких частот сигнала, и редкой в области низких частот. Идея КМА заключается в том, чтобы масштабировать вейвлет в некоторое постоянное (например, 2) число раз, и при скольжении по сигналу сдвигать его во времени с шагом, равным интервалу носителя масштабированного вейвлета. Если обозначить количество масштабных строк индексом m, и принять , то при решетка вейвлетного спектра будет иметь всего масштабных строк с количеством отсчетов в первой строке 16, во второй 8, в третьей 4, в четвертой 2, и в пятой 1, с общим количеством отсчетов 32, как и в исходном сигнале. При этом все сдвиги одного масштаба будут попарно ортогональны (нет перекрытия сдвигов), равно как и вейвлеты разных масштабов в силу их нулевого первого момента.

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

Простейшие методы КМА, без всякой теоретической базы, использовались при обработке числовых данных уже достаточно давно. Рассмотрим один из таких методов на практическом примере анализа гистограмм, который обычно выполняется функцией Хаара (Haar), в дальнейшем получившей название вейвлета Хаара (рис. 1.1).

Рис. 1.1.

Допустим, что мы анализируем определенную зависимость на интервале , показанную на рис. 1.2. Функция нецентрированная, и для использования вейвлет-преобразования с последующим восстановлением исходного сигнала требует применения как вейвлета, так и его скейлинг-функции. На основе базовых функций вейвлета и скайлинг-функции Хаара, приведенных на рис. 1.1, записываем масштабированные функции:

Рис. 1.2.

Эти функции образуют нормированные взаимно ортогональные базисы пространства вейвлетных коэффициентов, на которые может быть разложен анализируемый сигнал. Ортогональность базисных функций является обязательным условием КМА, обеспечивающим возможность обратной реконструкции сигнала. Для коротких и достаточно гладких кривых нет смысла устанавливать много уровней декомпозиции сигнала. Примем максимальное значение , равным 4, при этом с интервалом дискретизации данных, соответственно, . В принципе, можно применять и задание исходного значения с последующим определением количества уровней разложения.

При сдвиговой ортогональности прямоугольных базисных функций прямое преобразование (проекции сигнала на базис ) для непрерывных сигналов выполняется по формуле:

Значения коэффициентов при :

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0.774 2.996 7.384 11.596 11.65 7.733 4.471 5.355 10.615 17.721 22.048 20.246 13.711 6.848 2.522 0.684

Восстановление сигнала с четвертого уровня декомпозиции соответственно выполняется по формуле реконструкции:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3.095 11.984 29.536 46.385 46.599 30.933 17.884 21.418 42.462 70.883 88.193 80.983 54.846 27.391 10.086 2.738

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

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3.095 11.984 29.536 46.385 46.599 30.933 17.884 21.418 42.462 70.883 88.193 80.983 54.846 27.391 10.086 2.738

то нетрудно убедиться, что (числовые отсчеты на рис. 1.2 отнесены к середине интервалов ).

В принципе, гистограмма может представлять собой непосредственные исходные дискретные данные (результаты измерений и т.п.). Сравнением выражений и нетрудно убедиться, что нулевой уровень разложения () может быть получен непосредственно из дискретных данных:

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

Рис. 1.3.

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

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

которые называют детализирующими коэффициентами.

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

Рис. 1.4.

Отсюда следует также, что ряды коэффициенты и (количество точек в каждом ряде) содержат полную информацию, адекватную информации в предшествующего уровня (количество точек ), что позволяют полностью восстановить значения коэффициентов более высокого уровня :

а, следовательно, и восстановить исходный дискретный сигнал. Для восстановления значений в исходных интервалах при , значение аппроксимирующего коэффициента на первой половине интервала при складывается с детализирующим коэффициентом, а на второй – вычитается. Для математического отображения этой операции введем функцию y , форма которой приведена на рис. 3.1.1, и обеспечим ее сдвиг по координате синхронно со скейлинг-функцией. Эта функция является ортонормированным базисом разложения детализирующих коэффициентов. Именно она в связи со своей формой и получила название вейвлета (вейвлетной или детализирующей функции). С ее использованием уравнение с входящими в него уравнениями приводятся к следующей форме (с уровня ):

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

Свойства преобразования

Отметим на этом примере характерные и очевидные особенности нового представления сигнала:

  • Общее количество коэффициентов разложения равно количеству отсчетов исходного сигнала (условие необходимости и достаточности сохранения в новом математическом представлении исходного объема информации).
  • Вейвлет и его скейлинг-функция должны иметь однозначную связь. Это определяется тем, что разложение сигнала может быть выполнено с использованием только скейлинг-функции, а детализирующие коэффициенты определяться по разности и уровней аппроксимации, и наоборот.
  • Значение представляет собой среднее значение исходного сигнала по интервалу его задания. Для центрированных сигналов это значение равно нулю. При выполнении разложения без скейлинг-функции (с вейвлетом в ) картина детальных особенностей нецентрированных сигналов остается без изменений, но полная реконструкция сигнала невозможна. Без значения при полном разложении сигнал центрируется, при реконструкции с других масштабов декомпозиции искажается за счет отсутствия соответствующих коэффициентов .
  • Увеличение масштабного значения m разложения соответствует возрастанию временного разрешения сигнала . Коэффициенты вейвлет-преобразования вскрывают флюктуационную структуру сигнала на разных масштабах и в разных временных точках. Приведенный простой пример нетрудно расширить на любой произвольный сигнал с произвольной длительностью и с произвольным временным разрешением, разложение которого может осуществляться до определенного уровня аппроксимации сигнала по низкочастотным составляющим и с детализацией локальных высокочастотных особенностей сигнала на разных масштабных уровнях. В областях "гладких" значений сигнала коэффициенты детализации близки к нулевым и ими можно пренебречь, что позволяет весьма эффективно осуществлять сжатие информации для хранения.
  • Реконструкция сигнала возможна с любого масштабного уровня декомпозиции, причем, как это следует из и может быть легко проверено, все особенности сигнала сохраняются без искажений с временным разрешением первого вейвлета (с минимальной шириной окна).

При вейвлет-анализе произвольных сигналов выбор анализирующего вейвлета не определен заранее и во многом зависит от поставленных задач.

Математические основы кратномасштабного анализа

Разложение сигнала на сумму аппроксимирующих и детализирующих составляющих производится с использованием ортогональных и биортогональных вейвлетов, которые отличаются возможностью реконструкции, как локальных особенностей сигналов, так и сигналов в целом. Именно на таких вейвлетах выполняется быстрое вейвлет-преобразование. При выполнении КМА пространство сигналов представляется в виде системы вложенных подпространств , отличающихся друг от друга перемасштабированием независимой переменной.

Исходные условия

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

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

Под ортогональным кратномасштабным анализом понимается описание пространства через иерархические вложенные подпространства которые не пересекаются и объединение которых в пределе дает . Эта система подпространств должна удовлетворять следующим условиям.

1. Условие вложенности:

Все пространство сигналов в целом может быть представлено в виде последовательности вложенных друг в друга замкнутых подпространств соответствующих уровней декомпозиции сигнала:

"Размеры" подпространств непрерывно расширяются по мере роста значения , а объединение всех подпространств в пределе дает пространство .

2. Условие полноты и плотности разбиения:

3. Условие ортогональности подпространств:

4. Условие сохранения в подпространстве при сдвигах функций:

5. Для любой функции ее масштабное преобразование по аргументу в 2 раза перемещает функцию в соседнее подпространство:

6. Для пространства существует phi-функция , целочисленные сдвиги которой по аргументу образуют ортонормированный базис пространства :

Функция называется скейлинг-функцией (scaling function). Условие нормирования скейлинг-функции:

Из этих условий следует, что если подпространство имеет ортонормированный базис , то и все остальные подпространства также имеют ортонормированные базисы, которые образуются масштабным преобразованием базиса :

Стандартное значение параметра 'а' в кратномасштабном анализе равно 2. Так, например, если на интервале и вне этого интервала, то целочисленные сдвиги этой функции попарно ортогональны, и пространство состоит из функций, имеющих постоянные значения на интервалах вида , – из функций, постоянных на интервалах , – из функций, постоянных на интервалах , и т.д.

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

На рис. 2.1 чисто в условном виде показано разбиение пространства на систему вложенных подпространств. Сигнал внутри каждого подпространства (ограниченного на рисунке окружностью) представляет собой произвольный вектор числовых значений . Все подпространства не пересекаются и вложены друг в друга таким образом, что объем каждого последующего (меньшего по номеру) подпространства , вложенного в подпространство , при в два раза меньше объема подпространства , при этом четные числовые отсчеты вектора входят в подпространство , а нечетные отсчеты остаются в подпространстве, ограниченном границами (отмечены на рисунке индексами ).

Рис. 2.1.

Все условия в совокупности позволяют разложить произвольный сигнал по подпространствам , т.е. на множество последовательных разномасштабных и ортогональных друг другу функций , объединение которых дает исходный сигнал , или аппроксимирует сигнал с определенной точностью в зависимости от ограничения количества значений масштабирующего коэффициента (и, соответственно, количества подпространств ). Функции являются ортогональными проекциями сигнала на подпространства . Отсюда появляется возможность анализа функции или сигнала на различных уровнях разрешения, или масштаба. Переменная m называется масштабным коэффициентом, или уровнем анализа. Если значение мало, то функция есть грубая аппроксимация , в которой отсутствуют детали. При увеличении значений точность аппроксимации повышается.

Кратность КМА, равную 2, в принципе, можно заменить любым целым числом, большим 1, но использование двоичной кратности оптимально, как и использование двоичного представления чисел в ЭВМ, и позволяет использовать быстрое вейвлет-преобразование. Выбор функции также достаточно произволен, но желательно стремиться к тому, чтобы спектр функций подпространства был сконцентрирован в интервале .

Масштабирующая функция

Для того чтобы задать КМА, достаточно знать только одно из подпространств , остальные определятся уравнением (2.5). Допустим, что это подпространство , состоящее из сигналов, заданных "с разрешением 1". Тогда в пространстве задаются сигналы с разрешением , и оно отличается от только перемасштабированием базисной функции в соответствии с (3.2.5). Так, если пространство имеет скейлинг-функцию , то соответствующее уравнение для скейлинг-функции пространства определяется выражением .

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

или, в эквивалентной форме:

Это уравнение называется масштабирующим. Решение этого уравнения и дает скейлинг-функцию, которую иногда называют "отцовским" вейвлетом. Уравнение масштабирования может иметь и несколько иные формы записи. В частности, в пакете Wavelet Toolbox Matlab оно используется в виде:

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

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

откуда следует:

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

Решение этого функционального уравнения:

где – функция Хевисайда: при , при .

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

На рис. 2.2 приведено отображение такой операции в частотной области представления пространств , которое, в отличие от рис. 2.1, имеет вполне конкретный физический смысл разделения спектров сигналов (и самих сигналов при их восстановлении из спектров) на низкочастотную и высокочастотную части.

Рис. 2.2.

Для исключения потерь высокочастотной информации, которая может потребоваться при восстановлении сигнала, она должна "переводиться" и сохраняться в новые подпространства , ортогональные подпространствам , такие, что

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

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

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

Базисный вейвлет

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

Уравнение , по существу, представляет собой нормированное уравнение свертки, где представляет собой оператор низкочастотного фильтра:

При переходе в частотную область:

Уравнение является масштабирующим уравнением в частотной области и полностью определяется периодической функцией . Отсюда следует, что в пространстве должна сохраняться высокочастотная часть информации сигнала, что может выполняться квадратурным обращением низкочастотного фильтра:

Фурье-образ искомого вейвлета:

При переходе во временную область:

При этом значения могут быть вычислены и непосредственно во временной области соответствующим квадратурным обращением оператора :

где – реверсированный массив оператора , записанный в обратном порядке. Соответственно, для вейвлета Наара эти коэффициенты равны: , . Именно этот вейвлет и известен, как вейвлет Хаара (рис. 1.1). В функциональном анализе он применяется с 1910 года. Масштабированные и смещенные версии скейлинг-функции и вейвлета:

Вейвлет Хаара знакопеременен, при этом

Условие знакопеременности является общим условием для всех "материнских" вейвлетов, которое обеспечивает безусловную устойчивость базиса при восстановлении исходного сигнала.

Разложение функций на вейвлетные ряды

Разложение функций на вейвлетные ряды на заданном уровне разрешения m выполняется по формуле:

Значения коэффициентов (которые обычно называют суммами и разностями):

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

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

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

Вычисление вейвлетных рядов

Допустим, что сигнал известен с разрешением 1, т.е. задан числовым рядом в пространстве с масштабом , который можно рассматривать, как результат его разложения по сдвигам скейлинг-функции:

Версия масштаба ортогональной проекции на подпространство будет задаваться набором скалярных произведений с функциями из базиса :

Из уравнения и условий ортогональности следует:

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

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

Или, с использованием уравнения :

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

Быстрое вейвлет-преобразование

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

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

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

Алгоритм Малла

Кратномасштабный анализ при последовательном увеличении значений приводит к естественной форме быстрых итерационных вычислений:

Эти уравнения обеспечивают пирамидальный алгоритм вычисления вейвлет-коэффициентов (алгоритм Малла), приведенный на рис. 3.1. Явный вид вейвлета требуется только для расчета коэффициентов и , при самом преобразовании он не используется, используются значения коэффициентов и . Уравнение применяется при известной аналитической форме функции . Для цифровых данных в качестве значений обычно принимаются исходные значения данных, т.е. .

Рис. 3.1.

Сущность операций, выполняемых формулами и , заключается в следующем. С учетом спектров коэффициентов и (рис. 3.1), на первом этапе преобразования первый цифровой фильтр hn из сигнала sk = C0,k выделяет низкие частоты , а другой (октавный) фильтр выделяет верхние частоты . Поскольку на выходе фильтра hn отсутствует верхняя половина частот, то частота дискретизации выходного сигнала может быть уменьшена в 2 раза, т.е. выполнена децимация выходного сигнала, что и производится в формуле сдвигами через 2 отсчета по входному сигналу. Соответственно, на выходе фильтра gn освобождается место в области низких частот, и аналогичное прореживание выходного сигнала приводит к транспонированию верхних частот на освободившееся место. Таким образом, каждый из выходных сигналов несет информацию о своей половине частот, при этом выходная информация представлена таким же количеством отсчетов, что и входная.

Реконструкция сигналов

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

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

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

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

Разновидностью вейвлетов являются койфлеты, обладающие набором нулевых моментов:

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

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

Пакетные вейвлеты

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

которые тоже локализованы в пространстве, но на вдвое более широком интервале, чем исходный вейвлет. Бинарное дерево разложения (рис. 3.1) "расщепляется" и для коэффициентов 'D' любого уровня. Такое расщепление является адаптивным и легко приспосабливается к индивидуальным особенностям сигналов. Функции адаптивного преобразования называют вейвлет-пакетом.

Фильтры дальной декомпозиции и реконструкции сигналов

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

Идеальные фильтры

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

Рис. 4.1.

Передаточная функция низкочастотного фильтра , удовлетворяющего условию , концентрируется в интервале . При разделении сигнала на два частотных поддиапазона с полным сохранением исходной информации должно выполняться условие (рис. 4.2):

Отсюда следует, что передаточная функция высокочастотного фильтра , сосредоточена на и . Соответственно, идеальные фильтры и в пределах главного частотного диапазона задаются выражениями:

Коэффициенты фильтров (обратное преобразование Фурье, рис. 4.2):

Связь значений коэффициентов:

Разложение сигнала на низкочастотную и высокочастотную части в спектральной и временной области:

Так как носитель функции находится на интервале , то можно разложить в ряд Фурье, как - периодическую функцию с частотой Найквиста :

т.е. функция избыточна по количеству отсчетов и может быть децимирована. Соответственно, не требуется вычислять свертку по всем нечетным значениям . Двукратная децимация обычно обозначается индексом :

где – последовательная нумерация четных отсчетов .

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

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

что обеспечивает восстановление исходного сигнала:

Реальные фильтры

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

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

где – комплексная переменная.

Отфильтрованные низкочастотный и высокочастотный сигналы:

Децимация сигналов в z-области выполняется простыми выражениями:

Обозначим фильтры реконструкции сигналов индексами . Уравнение реконструкции:

Подставляя в это выражение функции и , получаем:

Отсюда следует, что искомые фильтры должны удовлетворять системе уравнений:

В матричной форме:

Решение системы существует, если определитель отличен от нуля всюду на единичной окружности :

Сопряженные квадратурные фильтры

Дополнительной практической задачей при определении комплекта фильтров декомпозиции и реконструкции сигналов является задание такого фильтра с соответствующими коэффициентами оператора , из которого следует определение всех других фильтров в форме:

при этом выполняется второе условие , а первое принимает вид:

Поскольку коэффициенты вещественные, то при значениях и , имеем:

При этом условие и функции принимают вид:

Тем самым система сводится к одному уравнению .

Ортогональные и биортогональные вейвлеты

Коэффициенты вейвлета

Значения коэффициентов и в рамках КМА определяются на основании общих свойств скейлинг-функций и вейвлетов. Уравнения функций:

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

Из условий нормировки скейлинг-функции следует второе уравнение:

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

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

откуда следует:

Пример расчета

Пример расчета коэффициентов выполним при . Запишем уравнения в явном виде:

Решение этой системы уравнений:

Примем для коэффициента знак минус в скобках, при этом:

Соответственно, значения коэффициентов , вычисленные по :

Спектры коэффициентов и приведены на рис. 5.1.

Рис. 5.1.

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

Вейвлет Добеши

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

Рис. 5.2.

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

Рис. 5.3.

Вид скейлинг-функции и вейвлета Добеши вычисляются методом итераций (можно посмотреть в Matlab), а в практических приложениях используются только вейвлет-коэффициенты и без вычисления конкретной формы вейвлетов. На рис. 5.4 приведены три вектора коэффициентов Добеши из системы Matlab (db2, db4 и db8) и спектры коэффициентов. Как видно из рисунка, по мере увеличения порядка векторов крутизна среза их частотных характеристик увеличивается, а, соответственно, качество разложения сигналов и их реконструкции также будут улучшаться.

Рис. 5.4.

За исключением вейвлетов Хаара, все вещественные ортогональные вейвлеты асимметричны. Наиболее близкую к симметричной форму имеет вейвлет Коифлетса, форма которого приведена на рис.5.5. Частотная характеристика коэффициентов вейвлета по сравнению с коэффициентами Добеши такого же порядка имеет более высокую крутизну среза полосы пропускания.

Рис. 5.5.

Биортогональные вейвлеты

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

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

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

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

При этом:

Двумерные вейвлеты

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

При двумерном КМА двумерный ортонормальный базис пространства имеет четыре порождающих функции, которые строится на основе одномерного ортонормального вейвлет-базиса и скейлинг-функции . Для скейлинг-функции:

Тензорное произведение для вейвлетных функций:

Если масштабирование по обеим переменным производится синхронно, то все остальные функции двумерных базисов определятся выражением:

где функция Ф(х,у) – соответствующие выражения .

Если система является ортонормированным базисом в , то прямое вейвлет-преобразование сигнала соответственно выполняется по формулам:

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

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

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

Литература

  1. Дремин И.Л. и др. Вейвлеты и их использование. / Успехи физических наук, 2001, т.171, № 5, стр. 465-501.
  2. Дьяконов В., Абраменкова И. MATLAB. Обработка сигналов и изображений. Специальный справочник. – СПб.: Питер, 2002, 608 с.
  3. Петухов А.П. Введение в теорию базисов всплесков. – СПб.: Изд. СПбГТУ, 1999, 132 с.
  4. Смоленцев Н.К. Основы теории вейвлетов. Вейвлеты в Matlab. М.: LVR Пресс, 2005. – 304 с.
  5. Переберин А.В. О систематизации вейвлет-преобразований. – Вычислительные методы и программирова-ние, 2001, т.2.
  6. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. – СПб, ВУС, 1999. 204 с.

См. также