8 / 14
Частотно-временн´ое дерево.
Такое дерево еще называют сба-
лансированным. Частотно-временн´ое дерево имеет структуру квадро-
дерева. Каждый родительский узел содержит две пары потомков: вре-
менн ´ые и частотные сегменты.
Для кодирования изображений алгоритм частотно-временн ´ого де-
рева несложно перенести на двумерный случай. Тогда получается
пространственно-частотное дерево.
Для одномерного сигнала длиной
N
и дерева максимальной глу-
биной
d
вычислительная сложность алгоритма частотно-временн ´ого
дерева составит
O N
2
d
.
Недостаток рассмотренного алгоритма — принципиальное ограни-
чение двоичной сегментацией во времени и, как следствие, чувстви-
тельность временн´ой сегментации к сдвигам исходного сигнала. Для
ликвидации этой чувствительности применяется алгоритм, основан-
ный на динамическом программировании — дерево гибкой простран-
ственной сегментации. Этот алгоритм включает в себя как частные
случаи все рассмотренные выше алгоритмы, основным его недостат-
ком является невозможность простого перенесения алгоритма на дву-
мерный случай для кодирования изображений.
Число базисов вейвлет-пакета.
Число различных ортогональных
базисов вейвлет-пакета для пространства
V
L
равно числу допустимых
двоичных деревьев. Существует более чем
2
2
J
−
1
различных ортонор-
мированных базисов вейвлет-пакета, содержащихся во всем двоичном
дереве вейвлет-пакета глубиной
J
=
d
.
Число
B
d
базисов вейвлет-пакета во всем двоичном дереве вейвлет-
пакета удовлетворяет неравенству
2
2
d
−
1
≤
B
d
≤
2
5
4
2
d
−
1
. Этот резуль-
тат доказывается индукцией по параметру
d
(глубина дерева вейвлет-
пакета). Число
B
d
различных ортонормированных базисов равно чи-
слу различных допустимых двоичных деревьев наибольшей глубины
d
, узлы которых имеют либо 0, либо 2 рожденных узла. При
d
= 0
дерево уменьшается до своего корня, отсюда
B
0
= 1
.
Отметим, что множество деревьев глубиной, не большей
d
+ 1
, со-
стоит из деревьев глубиной самое меньшее 1 и самое большее
d
+ 1
, а
также из одного дерева глубиной 0, что соответствует корню. Дерево
глубиной самое меньшее 1 имеет левое и правое поддеревья, кото-
рые представляют собой допустимые деревья глубиной не больше
d
.
Априори конфигурация этих деревьев произвольна, и существует та-
кое число
B
d
допустимых деревьев глубиной
d
, что
B
d
+1
=
B
2
d
+ 1
.
Поскольку
B
1
= 2
и
B
d
+1
≥
B
2
d
, то по индукции доказываем следу-
ющее:
B
d
≥
2
2
d
−
1
. Кроме того,
log
2
B
d
+1
= 2 log
2
B
d
+ log
2
1 +
B
−
2
d
.
Если
d
≥
1
, то
B
d
≤
2
и
log
2
B
d
+1
≤
2 log
2
B
d
+
1
4
. Поскольку
B
1
= 2
,
82 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1