Databases Reference
In-Depth Information
Weight (lb)
180
x
x
4
x
160
x
140
3
120
x
x
x
100
x
x
2
80
60
1
x
40
4
5
6
7
Height (in)
F I GU R E 10 . 9
Final state of the vector quantizer.
T A B L E 10 . 3
An alternate initial set of
output points.
Height
Weight
75
50
75
117
75
127
80
180
10.4.1 Initializing the LBG Algorithm
The LBGalgorithmguarantees that the distortion fromone iteration to the next will not increase.
However, there is no guarantee that the procedure will converge to the optimal solution. The
solution to which the algorithm converges is heavily dependent on the initial conditions. For
example, if our initial set of output points in Example
10.4.1
had been those shown in Table
10.3
instead of the set in Table
10.2
, by using the LBG algorithm we would get the final codebook
shown in Table
10.4
.
The resulting quantization regions and their membership are shown in Figure
10.10
.This
is a very different quantizer than the one we previously obtained. Given this heavy dependence
on initial conditions, the selection of the initial codebook is a matter of some importance. We
will look at some of the better-known methods of initialization in the following section.
Linde, Buzo, andGray described a technique in their original paper [
137
] called the
splitting
technique
for initializing the design algorithm. In this technique, we begin by designing a vector
quantizer with a single output point; in other words, a codebook of size one, or a one-level
