Previous Page  11 / 14 Next Page
Information
Show Menu
Previous Page 11 / 14 Next Page
Page Background

ось на интервалы размерами, соответствующими структуре сигнала.

Косинусные базисы — наиболее применяемые блочные базисы.

Допустимое поддерево для локального косинусного квадратного

дерева имеет узлы, порождающие 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