Digital Signal Processing Reference
In-Depth Information
Lloyd's algorithm [14]). The algorithm divides the set of training vectors into
L
clusters
C
i
in such a way that the two necessary conditions for optimality
are satisfied.
K-means Algorithm
Given that
m
is the iteration index and
C
i
m
is the
i
th
cluster at iteration
m
with
y
i
m
its centroid:
1. Initialization: Set
m
=
0 and choose a set of initial codebook vectors
y
i
0
,
L
.
2. Classification: Partition the set of training vectors
x
n
,
1
1
≤
i
≤
≤
n
≤
M
,intothe
clusters
C
i
by the nearest neighbour rule,
x
C
i
m
if
d
[
x
,
y
i
m
]
≤
d
[
x
,
y
j
m
]
for all
j
=
i.
3. Codebook updating:
m
1. Update the codebook vector of every
cluster by computing the centroid of training vectors in each cluster.
4. Termination test: If the decrease in the overall distortion at iteration
m
relative to
m
→
m
+
−
1 is below a certain threshold, stop; otherwise go to step 2.
Any other reasonable termination test may be used for step 4.
The above algorithm converges to a local optimum [14, 15]. Furthermore,
any such solution is in general not unique [16]. Global optimality may
be achieved approximately by initializing the codebook vectors to different
values and repeating the above algorithm for several sets of initializations and
then choosing the codebook that results in the minimum overall distortion.
3.4.3 CodebookTypes
Vector quantization can offer substantial performance over scalar quantiza-
tion at very low bit-rates. However, these advantages are obtained at con-
siderable computational and storage costs. In order to compromise between
the computation and storage costs, and quantizer performance, a number
of codebook types have been developed. Some codebooks are precomputed
and do not change while being used; others may be updated during quanti-
zation. Here, we will briefly explain some of the widely-used codebooks in
speech coding.
Full Search Codebook
A full search codebook is one where during the quantization process each
input vector is compared against all of the candidate vectors in the codebook.
This process is called full search or exhaustive search. The computation and
Search WWH ::
Custom Search