Databases Reference
In-Depth Information
may be available for the encoding operation. However, if the decoding is to be done in software,
the amount of computational resources available to the decoder may be quite limited.
The subject of vector quantization is a broad one. In this chapter we will try to introduce
you to as much of this fascinating area as we can. If your appetite is whetted by what is
available here and you wish to explore further, there is an excellent topic by Gersho and Gray
[
136
] devoted to the subject of vector quantization.
Our approach in this chapter is as follows: First, we try to answer the question of why
we would want to use vector quantization over scalar quantization. There are several answers
to this question, each illustrated through examples. In our discussion, we assume that you
are familiar with the material in Chapter 9. We will then turn to one of the most important
elements in the design of a vector quantizer, the generation of the codebook. While there are
a number of ways of obtaining the vector quantizer codebook, most of them are based on one
particular approach, popularly known as the Linde-Buzo-Gray (LBG) algorithm. We devote a
considerable amount of time to describing some of the details of this algorithm. Our intent here
is to provide you with enough information so that you can write your own programs for design
of vector quantizer codebooks. In the software accompanying this topic, we have also included
programs for designing codebooks that are based on the descriptions in this chapter. If you
are not currently thinking of implementing vector quantization routines, you may wish to skip
these sections (Sections
10.4.1
and
10.4.2
). We follow our discussion of the LBG algorithm
with some examples of image compression using codebooks designed with this algorithm,
and then with a brief sampling of the many different kinds of vector quantizers. Finally, we
describe another quantization strategy, called trellis-coded quantization (TCQ), which, though
different in implementation from vector quantizers, also makes use of the advantage to be
gained from operating on sequences.
Before we begin our discussion of vector quantization, let us define some of the terminology
we will be using. The amount of compression will be described in terms of the rate, which will
be measured in bits per sample. Suppose we have a codebook of size
K
, and the input vector is
of dimension
L
. In order to inform the decoder of which code-vector was selected, we need to
use
bits. For example, if the codebook contained 256 code-vectors, we would need
8 bits to specify which of the 256 code-vectors had been selected at the encoder. Thus, the
number of bits
per vector
is
log
2
K
bits. As each code-vector contains the reconstruction
values for
L
source output samples, the number of bits
per sample
would be
log
2
K
log
2
K
L
. Thus,
the rate for an
L
-dimensional vector quantizer with a codebook of size
K
is
log
2
K
L
. As our
measure of distortion we will use the mean squared error. When we say that in a codebook
C
,
containing the
K
code-vectors
{
y
i
}
, the input vector
x
is closest to
y
j
, we will mean that
x
y
j
2
2
−
x
−
y
i
for all
y
i
∈
C
(1)
where
x
=
(
x
1
x
2
···
x
L
)
and
L
2
x
i
x
=
(2)
i
=
1
The term
sample
will always refer to a scalar value. Thus, when we are discussing com-
pression of images, a sample refers to a single pixel. The output points of the quantizer are
often referred to as
levels
. Thus, when we wish to refer to a quantizer with
K
output points
