7 / 14
С каждым узлом
(
j, p
)
связывается пространство
W
p
j
, которое до-
пускает ортонормированный базис
ψ
p
j
(
t
−
2
j
n
)
n
∈
Z
при движении
вниз по дереву. На корне имеем
W
0
L
=
V
L
и
ψ
0
L
=
ϕ
L
. Предпо-
ложим, что уже построено пространство
W
p
j
и его ортонормиро-
ванный базис
B
p
j
=
ψ
p
j
(
t
−
2
j
n
)
n
∈
Z
в узле
(
j, p
)
. Два вейвлет-
пакета ортогональных базисов в порожденных узлах описываются
соотношениями расщепления:
ψ
2
p
j
+1
(
t
) =
+
∞
X
n
=
−∞
h
[
n
]
ψ
p
j
t
−
2
j
n
и
ψ
2
p
+1
j
+1
(
t
) =
+
∞
X
n
=
−∞
g
[
n
]
ψ
p
j
t
−
2
j
n
. Поскольку пространство
ψ
p
j
(
t
−
2
j
n
)
n
∈
Z
ортонормировано, то
h
[
n
] =
ψ
2
p
j
+1
(
u
)
, ψ
p
j
(
u
−
2
j
n
)
,
g
[
n
] =
ψ
2
p
+1
j
+1
(
u
)
, ψ
p
j
(
u
−
2
j
n
)
.
Доказано
B
2
p
j
+1
=
ψ
2
p
j
+1
(
t
−
2
j
+1
n
)
n
∈
Z
и
B
2
p
+1
j
+1
=
=
ψ
2
p
+1
j
+1
(
t
−
2
j
+1
n
)
n
∈
Z
— ортонормированные базисы двух орто-
гональных пространств
W
2
p
j
+1
и
W
2
p
+1
j
+1
таких, что [7]
W
2
p
j
⊕
W
2
p
+1
j
=
W
p
j
+1
.
(6)
Рекурсивное расщепление (6) определяет двоичное дерево пространств
вейвлет-пакета, где каждый узел-родитель делится на два ортогональ-
ных подпространства.
Вычислительная сложность алгоритма для одномерного сигнала
длиной
N
и максимальной глубиной
d
одиночного дерева составит
O
(
Nd
)
.
Допустимое дерево.
Допустимым деревом называется любое дво-
ичное дерево, каждый узел которого имеет либо 0, либо 2 рожденных
узла (рис. 3,
б
). Пусть
{
j
i
, p
i
}
1
≤
i
≤
I
— листья допустимого двоичного
дерева. Применяя рекурсивное расщепление (6) вдоль ветвей допусти-
мого дерева, убеждаемся, что пространства
W
p
i
j
i
1
≤
i
≤
I
взаимно ор-
тогональны и в сумме дают
W
0
L
:
W
0
L
=
I
⊕
i
=1
W
p
i
j
i
. Поэтому объединение
соответствующих базисов вейвлет-пакетов
ψ
p
i
j
i
(
t
−
2
j
i
n
)
n
∈
Z
,
1
≤
i
≤
I
определяет ортогональный базис
W
0
L
=
V
L
. Таким образом, полу-
чается базис, адаптированный к сигналу. Отметим, что адаптация
не требует обучения или знания статистических свойств сигнала.
Вейвлет-преобразование — частный случай этого базиса. Адаптив-
ность достигается за счет увеличения вычислительной стоимости.
Для одномерного сигнала длиной
N
и дерева максимальной глуби-
ной
d
вычислительная сложность алгоритма допустимого двоичного
дерева составляет
O
(
Nd
2
)
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1 81