Vector Quantization - Introduction to Data Compression - page 314

to quantize a single input vector would require over four billion vector comparisons to find
the closest output point. Obviously, neither the storage requirements nor the computational
requirements are realistic. Because of this problem, most vector quantization applications
operate at low bit rates. In many applications, such as low-rate speech coding, we want to
operate at very low rates; therefore, this is not a drawback. However, for applications such as
high-quality video coding, which requires higher rates, this is definitely a problem.
There are several approaches to solving these problems. Each entails the introduction
of some structure in the codebook and/or the quantization process. While the introduction
of structure mitigates some of the storage and computational problems, there is generally a
trade-off in terms of the distortion performance. We will look at some of these approaches in
the following sections.
10.5 Tree-Structured Vector Quantizers
One way we can introduce structure is to organize our codebook in such a way that it is easy
to pick which part contains the desired output vector. Consider the two-dimensional vector
quantizer shown in Figure 10.17 . Note that the output points in each quadrant are the mirror
image of the output points in neighboring quadrants. Given an input to this vector quantizer,
we can reduce the number of comparisons necessary for finding the closest output point by
using the sign on the components of the input. The sign on the components of the input vector
will tell us in which quadrant the input lies. Because all the quadrants are mirror images of the
neighboring quadrants, the closest output point to a given input will lie in the same quadrant
as the input itself. Therefore, we only need to compare the input to the output points that lie
in the same quadrant, thus reducing the number of required comparisons by a factor of four.
This approach can be extended to L dimensions, where the signs on the L components of the
input vector can tell us in which of the 2 L hyperquadrants the input lies, which in turn would
reduce the number of comparisons by 2 L .
This approach works well when the output points are distributed in a symmetrical manner.
However, it breaks down as the distribution of the output points becomes less symmetrical.
Example10.5.1:
Consider the vector quantizer shown in Figure 10.18 . This is different from the output points
in Figure 10.17 ; we have dropped the mirror image requirement of the previous example. The
output points are shown as filled circles, and the input point is the X. It is obvious from the figure
that while the input is in the first quadrant, the closest output point is in the fourth quadrant.
However, the quantization approach described above will force the input to be represented by
an output in the first quadrant.
The situation gets worse as we lose more and more of the symmetry. Consider the situation
in Figure 10.19 . In this quantizer, not only will we get an incorrect output point when the input
is close to the boundaries of the first quadrant, but also there is no significant reduction in the
amount of computation required.