Information Technology Reference
In-Depth Information
Mu
()
=−
p
log
p
(2)
j
j
j
M
({
u
})
=
Mu
(
)
The cost function should have additivity, namely
M
(0)
=
0
,
, and
j
j
j
values of
Mu
should reflect the concentration of the coefficient.
( )
Definition 2
: let
Mu
be the cost function,
( )
uu
=
{}
j
is a vector in space
V
,
B
is
an orthogonal basis selected from the library,
B
is expansion coefficients of
u
with
basis B.
∀∈
u
V
, if
MB
is the smallest, then
B
is the optimal basis.
(
)
u
This orthogonal basis library is a binary tree structure if it meet the following
conditions. First, subset of basis vectors is equivalent to a interval of non-negative
integer set
N
, namely
. Second, each
basis in the library corresponds to a disjoint covering composed of
I
=
2,2( )
k
n
k
n
+
, where
kZ
∈
,
nN
∈
nk
,
I
in
N
.
nk
Thirdly, if
V
is equivalent to
I
, then
VVV
+
=⊕
. If the library is a tree,
nk
nk
nk
,
1
2,
nk
2 ,
n
+
k
optimal basis can be found by induction of
k
. Let
B
be a basis of corresponding
nk
vector
I
,
A
is the optimal basis of
u
subject to
B
. To
k
=
0
, there exists a
nk
nk
single basis, namely
I
, to be the optimal one, and formula
A
=
B
holds for all
n
, 0
n
, 0
n
, 0
, we can use the following formula to generate
u
's
optimal orthogonal basis related with cost function
M
.
n
≥
0
. Let
k
≥
0
,
n
≥
0
,
VI
=
0,
k
B
if
M
(
B
(
u
))
<
MA
(
(
u
))
+
MA
(
(
u
))
nk
,
+
1
2,
nk
2 ,
n
+
k
nk
,
+
1
A
=
(3)
nk
,
+
1
A
⊕
A
otherwise
2,
nk
2 1,
n
+
k
As to real-time video traffic sequence, using the bottom-up search algorithm, we can
find a wavelet packet sequence which makes the cost function minimum, and then we
can find the optimal basis. This algorithm is shown as follows:
─
Step 1: calculate each node's cost function
M u
()
in every step of the wavelet
packet decomposition;
─
Step 2: mark all nodes from the lowest layer, take their cost value as an initial
value and calculate the sum of pair wise, then compare with parent node' value in
upper layer;
─
Step 3: if cost value of parent node is lower than that of child node, parent node
should be marked. Otherwise, calculate the sum of two child nodes' cost function
value and replace the cost value of parent node, and so forth, until the top level;
─
Step 4: check and record all the marked nodes. When the upper node is marked,
the mark of corresponding child nodes is deleted, after
oN N
operations, all
marked nodes of top level is selected, these marked nodes compose of non-
overlapping coverage in
( og)
LR
space, then coefficients are extracted from the op-
2
()
timal basis and output.
