|
Раздел "Обработка сигналов и изображений\Wavelet Toolbox" "Вейвлеты, аппроксимация и статистические приложения" (перевод К.А.Алексеева)
\ \
12.1 Введение.
В настоящей главе обсуждается вычислительный аспект построения вейвлет-оценок, а также приводится краткий обзор программного обеспечения, используемого для статистического вейвлет-анализа.
В настоящее время существует целый набор программных средств: здесь можно отметить и Wavelab 600, и тулбоксы MatLab, предназначенные для вейвлет- и время-частотного анализа. Последнее программное обеспечение написано Букхатом, Ченом, Донохо, Джонстоном, Скаргом (Buckhut, Chen, Donoho, Johnstone, Scargh) и распространяется через Интеренет (wavelab@playfair.stanford.edu).
Большое место занимают вейвлет-модули для StatLib. Модули содержат описание правил использования, вейвлет-функции. Модули работают как под Windows, так и под UNIX. Предназначены для инженеров, ученых, специалистов в области обработки сигналов.
Не так давно в MatLab появился Wavelet Toolbox, позволяющий осуществлять выбор базисов, цветовой гаммы трешолдинга одно- и двумерных данных.1
12.2 Каскадный алгоритм
В настоящем параграфе собраны рекурсивные выражения для расчета коэффициентов вейвлет-разложения, позволяющие рассчитывать коэффициенты разложения более низкого уровня на основании коэффициентов более высокого уровня и наоборот. Данные рекурсии имеют название каскадного (или пирамидального) алгоритма.
Прежде всего, построим каскадный алгоритм для коэффициентов разложения, полученных посредством скалярного произведения , . Будем полагать далее, что в качестве базисных функций, участвующих в разложении, используются функции с компактным носителем, построенные из тригонометрического полинома (см. главы 5-7). Напомним, что коэффициенты здесь представляют собой коэффициенты фильтров такие, что только ограниченное их число имеет ненулевые значения. Сказанное предполагает использование в качестве упомянутых функций базис Добеши, коифлеты, симлеты.
Лемма 5.4, доказанная ранее, показывает, что коэффициенты разложения удовлетворяют для всех соотношениям:
, |
(12.1) |
, |
(12.2) |
в которых . Действительно,


.
Как видно, простейшие выкладки приводят к выражению (12.2). Очевидно, выражение (12.1) может быть получено аналогично.
Итак, выражения (12.1), (12.2) представляют собой каскадный алгоритм, причем первое из них реализует низкочастотный фильтр, тогда как второе - высокочастотный [28].
Предположим, что исследуемая функция имеет компактный носитель. Тогда, вследствие того обстоятельства, что базисные функции также компактны, ненулевыми в разложении окажется лишь конечное число коэффициентов на каждом из уровней. Следовательно, для вектора , состоящего из коэффициентов разложения, взятых на начальном уровне , можно восстановить коэффициенты аппроксимации и детализации на уровнях , используя рекурсивные формулы каскадного алгоритма. Здесь достаточно лишь запомнить, что с увеличением глубины уровня разложения, число коэффициентов будет уменьшаться в 2k раз. В том случае, если процедура расчета коэффициентов останавливается на некотором конечном уровне , результирующий вектор коэффициентов принимает вид:
,
тогда как сама процедура выглядит следующим образом:
. |
(12.3) |
Здесь представляет собой оператор вейвлет-преобразования, имеющий вид матрицы.
Вполне возможной представляется также обратная процедура расчета коэффициентов по имеющимся коэффициентам . Обратный алгоритм сводится к использованию выражения
+ . |
(12.4) |
Получить данное выражение достаточно просто: для этого необходимо вспомнить, что , где есть оператор ортогональной проекции функции на пространство . Следовательно, можно заключить, что
+ . |
(12.5) |
Интересен тот факт, что
,
.
Обратимся теперь к случаю использования эмпирических коэффициентов разложения. Каскадный алгоритм в данном случае также является справедливым. Правда, в данном случае представляется целесообразным использовать некоторые его модификации, к обсуждению которых мы переходим.
Во-первых, заметим, что в контексте статистического оценивания (см. главу 10) целью задачи является не столько расчет коэффициентов разложения, сколько построение оценки функции плотности на сетке, т.е. вектора
,
в котором
, |
(12.6) |
, |
(12.7) |
. |
(12.8) |
Здесь представляют собой данные, разбитые на неперекрывающиеся интервалы такие, что , тогда как - функцию трешолдинга. Как видно, различие между оцениванием плотности и регрессионным оцениванием проявляется в данном случае лишь в разделении данных на группы: действительно, в случае оценивания плотности совокупность представляет собой гистограмму, тогда как в случае регрессионного оценивания - регрессограмму. Таким образом, оценки (12.6) - (12.8) могут быть использованы для решения задач параметрического оценивания при условии правильного построения данных в группах.
Между тем, расчет коэффициентов (12.7), (12.8) на практике представляет собой весьма нелегкую задачу: функции , как известно, не имеют аналитического выражения, в связи с чем использование рекурсивного алгоритма является единственно возможным путем расчета. Вопрос эффективного построения оценки функции в точках временной сетки более изящен. Однако рассмотрение данного вопроса отложим на следующий параграф, в котором вместе с тем представим также некоторые быстрые приближающие способы расчета, используемые на практике.
С целью построения эмпирического каскадного алгоритма отметим, что эмпирические вейвлет-коэффициенты есть ни что иное как внутреннее произведение:
,
,
в котором
,
- дельта-функция Дирака, характеризующая массу в точке, тогда как . Подобно выражению (12.1), можно получить следующие рекурсивные формулы для эмпирического каскадного алгоритма:
, |
(12.9) |
, |
(12.10) |
Иными словами, расчет эмпирических коэффициентов разложения происходит следующим образом: вычисляются коэффициенты аппроксимации на наивысшем уровне с использованием выражения
, |
(12.10a) |
после чего рассчитываются коэффициенты с использованием выражений (12.9), (12.10) на каждом из уровней. Коэффициенты фильтров, имеющих место под знаком суммы в упомянутых выражениях, можно отыскать в [28]. Весьма важно помнить, что число таких коэффициентов в выражениях не превышает 10-20.
Опять же, как видно, стартовой проблемой оказывается расчет начальных коэффициентов (12.10а): аналитическое выражение для функции является, по-прежнему, неизвестным.
Итак, выражения (12.9), (12.10), определяющие эмпирический каскадный алгоритм, оказываются полностью аналогичными выражениям (12.4), (12.5), определяющим теоретический алгоритм. По аналогии с процедурой обратного алгоритма можно составить также рекурсию
+ . |
(12.11) |
Однако здесь расчет таких коэффициентов уже не является проблемой: алгоритм оперирует с мерой вместо функции исходной .
В заключение имеет смысл сказать несколько слов о том, что прямой и обратный эмпирический каскадный алгоритм оперирует с финитным набором коэффициентов, в связи с чем, скажем откровенно, не является полным повторением теоретического алгоритма. Его получение подразумевает простейшее распространение эмпирического алгоритма на множество .Более того, данный алгоритм реализует ни что иное, как дискретное вейвлет-преобразование [101], которое будет описано в следующем параграфе.
Использование трешолдинга разрывает дискретное преобразование: после последовательного разложения данных на каждом из уровней разложения к коэффициентам применяется процедура трешолдинга, после чего данные восстанавливаются. Результирующая оценка представляет собой разложение функции в ряд по вейвлет-функциям.
1 Более подробно о Wavelet Toolbox, его функциях и возможностях можно найти здесь же, www.matlab.ru
\ \
|