Databases Reference
In-Depth Information
71,176 (3)
71,176 (3)
69,168 (5)
69,168 (5)
72,180
72,175
65,120
44,41
59,119
62,114
64,150
60,110
65,162
56,91
57,88
70,172
72,180
71,174 (2)
65,120
44,41
61,117 (2)
65,120
44,41
61,117 (2)
65,120
44,41
60,114 (3)
65,120
44,41
60,114 (3)
62,116 (4)
44,41
65,156 (2)
60,110
65,156 (2)
60,110
65,156 (2)
57,90 (2)
57,90 (2)
57,90 (2)
57,90 (2)
57,90 (2)
F I GU R E 10 . 13
Obtaining initial output points using the PNN approach.
where
n
i
is the number of elements in the cluster
C
i
, and
y
i
is the corresponding output point.
In the PNN algorithm, we combine clusters that cause the smallest increase in the distortion.
Example10.4.4:
Using the PNN algorithm, we combine the elements in the training set as shown in Figure
10.13
.
At each step we combine the two clusters that are closest in the sense of Equation (
5
). If we
use these values to initialize the LBG algorithm, we get a vector quantizer shown with output
points (70, 172), (60, 107), (44, 41), and (64, 150), and a distortion of 104.08.
Although it was a relatively easy task to generate the initial codebook using the PNN
algorithm in Example
10.4.4
, we can see that, as the size of the training set increases, this
procedure becomes progressively more time-consuming. In order to avoid this cost, we can
use a fast PNN algorithm that does not attempt to find the absolute smallest cost at each step
(see [
139
] for details).
Finally, a simple initial codebook is the set of output points from the corresponding scalar
quantizers. In the beginning of this chapter we saw how scalar quantization of a sequence of
inputs can be viewed as vector quantization using a rectangular vector quantizer. We can use
this rectangular vector quantizer as the initial set of outputs.
Example10.4.5:
Return once again to the quantization of the height-weight data set. If we assume that the
heights are uniformly distributed between 40 and 180, then a two-level scalar quantizer would
have reconstruction values 75 and 145. Similarly, if we assume that the weights are uniformly
distributed between 40 and 80, the reconstruction values would be 50 and 70. The initial
reconstruction values for the vector quantizer are (50, 75), (50, 145), (70, 75), and (70, 145).
