|
Раздел "Обработка сигналов и
изображений\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). Однако при программировании алгоритмов
прямого и обратного преобразования осуществляют сдвиг нумерации
коэффициентов таким образом, чтобы . Иначе говоря, коэффициенты фильтров нумеруются таким
образом, что . Правда, результирующая вейвлет-оценка в итоге несколько
отличается от первоначальной, полученной до введения новой нумерации.
Между тем, для вейвлетов Добеши , и вопрос о перенумерации и, следовательно, сдвиге оценки
не возникает.
Интересен также тот факт, что при построении линейных вейвлет-оценок
условия, накладываемые на вырожденные моменты функций, остаются в силе при
сдвиге номеров коэффициентов . Важные отличия в условиях появляются лишь при
приближении к границам реализации и точкам разрыва.
В случае использования трешолдинга вейвлет-оценки, построенные для
исходной последовательности коэффициентов и последовательности с перестроенной нумерацией,
оказываются также различными.
\ \ |