11 / 14
ось на интервалы размерами, соответствующими структуре сигнала.
Косинусные базисы — наиболее применяемые блочные базисы.
Допустимое поддерево для локального косинусного квадратного
дерева имеет узлы, порождающие 0 или 4 узла. Применяя свойство
разложения
W
p,q
j
=
W
2
p,
2
q
j
+1
⊕
W
2
p
+1
,
2
q
j
+1
⊕
W
2
p,
2
q
+1
j
+1
⊕
W
2
p
+1
,
2
q
+1
j
+1
вдоль
ветвей допустимого квадратного дерева, получаем, что расположен-
ные в листьях пространства
W
p
i
,q
i
j
i
раскладывают пространство
W
0
,
0
0
на ортогональные подпространства. Ввиду этого объединение соответ-
ствующих двумерных локальных косинусных базисов
B
p
i
,q
i
j
i
— ортого-
нальный базис
W
0
,
0
0
. Пусть есть больше чем
2
4
J
−
1
= 2
N
2
/
16
η
2
различ-
ных допустимых деревьев максимальной глубиной
d
= log
2
N
2
η
. Эти
базисы разбивают плоскость изображения на квадраты различных раз-
меров. Этот локальный косинусный базис выбран с помощью лучшего
базисного алгоритма. Число базисов, перебираемых различными ал-
горитмами, приведено ниже:
Дерево:
одиночное . . . . . . . . . . . . . . . . . . .
B
=(
B
(
N/
2))
2
+1
,
B
(2)=2
S
(
N
)=[
S
(
N/
2)]
2
+1
,
S
(2) = 2
двоичное . . . . . . . . . . . . . . . . . . . .
D
(
N
) = (
D
(
N
/2))
2
+
B
(
N
)
− B
(
N
/2)
частотно-временн´ое . . . . . . . . . .
B
t
f
(
N
) = 2
B
t
f
(
N
/2)
2
− B
t
f
(
N
/4)
4
гибкой временн´ой сегментации
B
F
(
N
) =
b
log
2
N
c
X
i
=0
B
2
i
− B
2
i
−
1
B
F
N
−
2
i
Следовательно, для одномерного сигнала длиной
N
и дерева мак-
симальной глубиной
d
вычислительная сложность алгоритма оди-
ночного, двоичного и частотно-временн´ого дерева будет составлять
O
(
Nd
)
,
O
(
Nd
2
)
и
O N
2
d
соответственно. Вычислительная слож-
ность алгоритма гибкой сегментации равна
O
(
NMd
)
, где
M
— макси-
мальное число сегментов
(
N
=
ML
)
. Разложение изображения
f
[
n
]
по сепарабельному локальному косинусному семейству
B
p,q
j
требу-
ет
O
(2
−
2
j
N
2
log
2
(2
−
j
N
))
операций при сепарабельном выполнении
быстрого одномерного локального косинусного преобразования. Для
всего локального косинусного квадратного дерева глубиной
d
эти вы-
числения выполняются при
0
≤
p, q <
2
j
и
0
≤
j
≤
d
, что требует
O
(
N
2
d
log
2
N
)
умножений и сложений. Исходное изображение вос-
станавливается по локальным косинусным коэффициентам в листьях
любого допустимого поддерева за число
O
(
N
2
log
2
N
)
вычислений.
Заключение.
Рассмотренные алгоритмы позволяют выполнять
адаптацию в частотной области (вейвлет-пакеты — алгоритм одиноч-
ного дерева); сначала во временн´ой, а затем в частотной (алгоритм
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1 85