Digital Signal Processing Reference
In-Depth Information
initial vectors. After the optimization of each of the two initial vectors
v
1
[
v
21
,v
22
,v
23
, ... ,v
2
N
] with dimensions
N
, each is split into two further vectors as,
=
[
v
11
,v
12
,v
13
, ... ,v
1
N
]and
v
2
=
=
−
ε
1
,
=
+
ε
1
,
=
−
ε
2
,
=
+
ε
2
,
v
3
v
1
v
4
v
1
v
5
v
2
v
6
v
2
where
ε
1
=
[
e
11
,e
12
,e
13
, ... ,e
1
N
]and
ε
2
=
[
e
21
,e
22
,e
23
, ... ,e
2
N
]. In most
cases
ε
1
ε
2
.
The vectors from the second stage are again optimized using the K-
means algorithm and split into further vectors and so on until the number
of optimized vectors is equal to the desired number. The optimization
process can also be terminated by comparing the overall quantization
noise performance of the codebook against a threshold.
During the optimization of a full search codebook using the above method,
it is important to check that all of the optimized vectors are in the densely-
populated areas and do not diverge into outer areas where their use will
be wasted. In such cases the perturbation vector
ε
is modified to change
the direction of the resultant vector.
=
•
Method 2:
The second method of optimization starts with randomly-
selected vectors from the training database. The number of initial vectors is
larger than the final desired number of vectors in the codebook. Using theK-
means algorithm these vectors are optimized. After the first optimization
process, the least used vectors are discarded from the codebook. The
remaining vectors are then optimized and the least used vectors are again
discarded from the optimized codebook. This process continues until the
final size of the codebook is reached. Here, the number of vectors discarded
at each stage and the number of optimization iterations may vary with the
application but the initial size of the codebook should at least be 1.5 times
the final size and the number of discarding stages should not be fewer
than five or six. The number of vectors discarded in each stage should be
reduced to increase the accuracy of optimization.
Binary Search Codebook
Binary search [17], known in the pattern recognition literature as hierarchical
clustering [14], is a method for partitioning space in such a way that the search
for the minimum distortion code-vector is proportional to log
2
L
rather than
L
. In speech coding literature, binary search codebooks are also called tree
codebooks or tree search codebooks.
In a binary search codebook,
N
dimensional space is first divided into two
regions (using the K-means algorithm with two initial vectors), then each of
the two regions is further divided into two subregions, and so on, until the
space is divided into
L
regions or cells. Here,
L
is restricted to be a power
Search WWH ::
Custom Search