|
Раздел "Обработка сигналов и изображений\Wavelet Toolbox" "Вейвлеты, аппроксимация и статистические приложения" (перевод К.А.Алексеева)
\ \
12.3 Алгоритм дискретного вейвлет-преобразования
С целью построения алгоритма дискретного вейвлет-преобразования введем некоторые линейные преобразования. Прежде всего, обозначим для всех сумму чисел по модулю s следующим образом: , а также положим, что есть некоторый вектор, в котором s четно. Тогда вводимые преобразования положим имеющим вид:
,

для всех . Очевидно, данные выражения являют собой аналоги высокочастотного и низкочастотного фильтров (12.1), (12.2) с учетом периодического дополнения данных при помощи суммирования по модулю. Ясно, что преобразования , осуществляют разделение исходного вектора длиной s на два вектора половинной длины.
Итак, алгоритм вейвлет-преобразования сводится к реализации итеративной процедуры - и -преобразований, применяемых к вектору . Результатом таких преобразований служат векторы , коэффициентов аппроксимации и детализации.
Иначе говоря, рекурсивно данный алгоритм выглядит следующим образом:
, | (12.12) |
. | (12.13) |
Отметим, введенные обозначения для коэффициентов разложения являются весьма схожими с обозначениями коэффициентов , тогда как рекурсии (12.12), (12.13) - с каскадным алгоритмом. Дело в том, что построение алгоритма дискретного преобразования полностью основывается на теории дискретного преобразования в базисе вейвлет-функций (см. предыдущий параграф). Основным отличием здесь является то обстоятельство, что в статистических приложениях коэффициенты лишь приближенно соответствуют коэффициентам разложения .
Отметим, рекурсии (12.12), (12.13) могут см успехом применяться к расчету коэффициентов аппроксимации и детализации также для случаев : дело в том, что дополненные последовательности являются периодическими, причем
,
.
Алгоритм обратного дискетного преобразования сводится к реализации выражения (12.11) также при условии периодизации данных. Алгоритм начинается с восстановления векторов
,

и продолжается до восстановления вектора , пока не станет . Рекурсивное выражение для восстановления данных в этом случае имеет вид:
. | (12.14) |
Очевидно, что промежуточные векторы коэффициентов содержат данные, также являющиеся периодическими:
. | (12.15) |
12.4 Статистический дискретный вейвлет-анализ
Разбиение данных
Итак, расчет вейвлет-оценок основывается на дискретном вейвлет-преобразовании, описанном выше. Как было показано, такой анализ подразумевает работу с данными, длина которых равна , где К - некоторое целое. Однако на практике длина исследуемых данных весьма часто оказывается не равной степени числа 2, в связи с чем возникает необходимость натяжения таких данных на эквидистантную сетку с числом узлов . Сказанное при этом является справедливым как для задач оценивания плотности распределения, так и для задач регрессионного сглаживания данных.
Процедуры деления данных на интервалы для оценивания плотности и регрессионного анализа введены в параграфах 10.2, 10.8 соответственно. В данном месте обсуждается эффект, вносимый подобным разбиением на качество синтезируемых оценок. Примеры, используемые для обсуждения эффекта, взяты из гл. 10, рис. 10.1 - 10.11.
Для взятых в качестве примера данных длиной исследован эффект деления на интервалы, состоящие из точек. Интегральные среднеквадратичные ошибки построения оценок приведены в таблице 12.1.
Таблица 12.1
Интегральные среднеквадратические ошибки
для интервалов разбиения различной длины
m
|
S8 жесткий
|
S8 мягкий
|
H жесткий
|
H мягкий
|
8
|
1
|
1,4157
|
1
|
1,4335
|
16
|
0,29267
|
1,0596
|
0,13811
|
0,55132
|
32
|
0,054237
|
0,26103
|
0,047822
|
0,41557
|
64
|
0,053587
|
0,23887
|
0,029666
|
0,22516
|
128
|
0,068648
|
0,27802
|
0,057907
|
0,29147
|
256
|
0,15012
|
0,37995
|
0,1348
|
0,37757
|
512
|
0,19506
|
0,53409
|
0,18746
|
0,55368
|
Как видно из таблицы, интегральная СКО достигает своего минимума при . График данной ошибки показан на рис. 12.1.
Несмотря на тот факт, что для подобных оценок можно определить оптимальный размер интервала, следует быть весьма осторожным в его статистической интерпретации. Дело в том, что разбиение данных на интервалы есть своего рода предварительное сглаживание, которое в теории достаточно часто в расчет не принимается. Очевидно, с ростом числа интервалов разбиения теряется большая часть вычислительной эффективности быстрого алгоритма. Точки, показывающие значения СКО на рис. 12.1 представляют собой компромисс между скоростью вычисления оценки и качеством предварительного сглаживания.
Приближенное построение вейвлет-оценок
Алгоритм реализации дискретного вейвлет-преобразования для целей построения статистических оценок (12.6) - (12.8) выглядит следующим образом:
-
Границы преобразований и начальные условия. Здесь вместо начального уровня разложения данных целесообразно использовать уровень . Начальные значения коэффициентов устанавливаются равными , .
-
Прямое преобразование. Прямое разложение данных (12.12), (12.13) происходит в пределах , , при этом результирующий вектор коэффициентов разложения имеет вид:
.
Векторы имеют длину, равную , тогда как вектор - длину, равную .
-
3. Обратное преобразование. Обратное преобразование (восстановление данных) (12.14), (12.15) происходит в пределах , -1, причем исходными данными для преобразования являются данные , прошедшие процедуру трешолдинга:
,
,
. | (12.16) |
Результат обратного преобразования обеспечивает значений вектора . Иначе говоря, результат восстановления представляет собой вектор , в котором
.
Другими словами, значения используются в качестве аппроксимаций значений функции .

Рис. 12.1
Интегральная СКО, построенная для симмлета S8
Сделаем в данном месте несколько замечаний по поводу приведенного алгоритма. Во-первых, определение дискретного преобразования подразумевает использование данных, периодически дополняемых на каждом шаге алгоритма. Иначе говоря, данные представляют собой результат диадического суммирования, в котором исходные данные дополняются периодически на Z таким образом, что для .
Во-вторых, как было подчеркнуто ранее, верхний уровень разложения в приводимом алгоритме не участвует: на практике полагается , причем процедуры пороговой обработки применяют к коэффициентам разложения всех уровней за исключением уровня K, содержащего лишь коэффициенты аппроксимации. Однако если предполагается исключение коэффициентов разложения уровней, старших , как это сделано в примере с линейной вейвлет-оценкой, определение (12.6) дополняется условием:
.
Подобно (12.3) действия 1 - 3 алгоритма могут быть представлены в матричной форме. С этой целью вектор исследуемых данных обозначим через . Тогда прямое преобразование примет вид:
, | (12.17) |
в котором представляет собой оператор размерностью . Легко показать, что данный оператор является ортогональным, поскольку содержит произведения конечного числа ортогональных матриц-операторов, соответствующих различным шагам алгоритма Малла [101].
Пусть оператор обозначает процедуру трешолдинга вектора :
,
тогда как оператор обратного преобразования - , или в силу ортогональности . Следовательно, результат последовательного приложения действий 1 - 3, выражаемый вектором , может быть получен следующим образом:
.
В том случае, если решаемой задачей является построение линейной вейвлет-оценки и в качестве уровня принимается уровень , трешолдинг сводится к преобразованию идентичности, обеспечивающему в итоге . Дело в том, что сохранение коэффициентов разложения на каждом из уровней в данном случае позволяет итоговой оценке лишь повторить исходные данные.
Далее, алгоритм, представленный действиями 1 - 3, является общим правилом построения вейвлет-оценок. Отметим, данный алгоритм является более быстрым по сравнению с БПФ, поскольку требует выполнения лишь операций. Вообще говоря, алгоритм позволяет скорее строить аппроксимацию данных, нежели их оценку. Исключением здесь является разложение данных в базис Хаара. К сожалению, данный факт не обсуждается в литературе.
Остановимся на данном вопросе несколько подробнее. Рассмотрим с этой целью линейную оценку, положив для любых и k. Предположим также, что исходные данные удовлетворяют требованию:
. | (12.18) |
Известно, что рекурсии (12.9), (12.10) позволяют рассчитать оценки коэффициентов , тогда как выражения рекурсии (12.12), (12.13) - примерно те же коэффициенты в предположении, что исходные данные для рекурсии абсолютно те же. Однако в том случае, если требование (12.18) выполняется, исходные данные для (12.12), (12.13) в действии 3 алгоритма становятся отличными от аналогичных им данных обратной рекурсии (12.9), (12.10) на некоторый множитель . Следовательно, линейность алгоритма влечет за собой необходимость введения в прямое преобразование поправку:
,
.
Более того, поправке подвергается основное выражение для прямого преобразования:
, | (12.19) |
причем оператор приобретает вид:
.
Объединяя выражения (12.17) и (12.19), можно записать, что теперь
.
Итак, для линейных оценок теперь можно полагать

при любых и

при . Кроме того, оператор трешолдинга можно определить как идемпотентную матрицу , в которой при и в других случаях. Следовательно, итоговое выражение для аппроксимации можно записать в виде:
. | (12.20) |
Назовем полученное выражение желаемой аппроксимацией данных.
Теперь остается лишь объяснить, почему выражение (12.18) имеет смысл существовать. Дело в том, что
.
Для вейвлетов Хаара выражение (12.18) имеет смысл при наличии поправки . Для койфлетов коэффициенты с точностью, определяемой как , где является достаточно большим в силу того обстоятельства, что скейлинг-функция имеет ряд вырожденных моментов (правда, сказанное справедливо для достаточно гладких функций f(t)). Далее, указанное обстоятельство можно распространить также на эмпирические коэффициенты , обеспечивая справедливость (12.18).
Для прочих вейвлет-базисов справедливость выражения (12.18) не гарантируется. В работах [30, 33] данный вопрос обсуждается более детально, причем даже приводятся базисы, которые обеспечивают справедливость поправки с точностью для больших значений .
Замечание 12.1. Вообще говоря, базисы вейвлет-функций с компактным носителем могут быть заданы посредством коэффициентов для всех (см. главы 6, 7). Однако при программировании алгоритмов прямого и обратного преобразования осуществляют сдвиг нумерации коэффициентов таким образом, чтобы . Иначе говоря, коэффициенты фильтров нумеруются таким образом, что . Правда, результирующая вейвлет-оценка в итоге несколько отличается от первоначальной, полученной до введения новой нумерации. Между тем, для вейвлетов Добеши , и вопрос о перенумерации и, следовательно, сдвиге оценки не возникает.
Интересен также тот факт, что при построении линейных вейвлет-оценок условия, накладываемые на вырожденные моменты функций, остаются в силе при сдвиге номеров коэффициентов . Важные отличия в условиях появляются лишь при приближении к границам реализации и точкам разрыва.
В случае использования трешолдинга вейвлет-оценки, построенные для исходной последовательности коэффициентов и последовательности с перестроенной нумерацией, оказываются также различными.
\ \
|