2

© 2000 by CRC Press LLC

Quantization

After the introduction to image and video compression presented in Chapter 1, we now address
several fundamental aspects of image and video compression in the remaining chapters of Section I.
Chapter 2, the first chapter in the series, concerns quantization. Quantization is a necessary com-
ponent in lossy coding and has a direct impact on the bit rate and the distortion of reconstructed
images or videos. We discuss concepts, principles and various quantization techniques which
include uniform and nonuniform quantization, optimum quantization, and adaptive quantization.

2.1 QUANTIZATION AND THE SOURCE ENCODER

Recall Figure 1.1, in which the functionality of image and video compression in the applications
of visual communications and storage is depicted. In the context of visual communications, the
whole system may be illustrated as shown in Figure 2.1. In the transmitter, the input analog
information source is converted to a digital format in the A/D converter block. The digital format
is compressed through the image and video source encoder. In the channel encoder, some redun-
dancy is added to help combat noise and, hence, transmission error. Modulation makes digital data
suitable for transmission through the analog channel, such as air space in the application of a TV
broadcast. At the receiver, the counterpart blocks reconstruct the input visual information. As far
as storage of visual information is concerned, the blocks of channel, channel encoder, channel
decoder, modulation, and demodulation may be omitted, as shown in Figure 2.2. If input and output
are required to be in the digital format in some applications, then the A/D and D/A converters are
omitted from the system. If they are required, however, other blocks such as encryption and
decryption can be added to the system (Sklar, 1988). Hence, what is conceptualized in Figure 2.1
is a fundamental block diagram of a visual communication system.
In this book, we are mainly concerned with source encoding and source decoding. To this end,

Hence, quantization is essentially discretization in magnitude, which is an important step in
the lossy compression of digital image and video. (The reason that the term lossy compression is
used here will be shown shortly.) The input and output of quantization can be either scalars or
vectors. The quantization with scalar input and output is called

scalar
quantization

, whereas that
with vector input and output is referred to as

vector
quantization

. In this chapter we discuss scalar
quantization. Vector quantization will be addressed in Chapter 9.
After quantization, codewords are assigned to the many finitely different values from the output
of the quantizer. Natural binary code (NBC) and variable-length code (VLC), introduced in
Chapter 1, are two examples of this. Other examples are the widely utilized entropy code (including
Huffman code and arithmetic code), dictionary code, and run-length code (RLC) (frequently used
in facsimile transmission), which are covered in Chapters 5 and 6.

FIGURE 2.1



This subsection concerns several basic aspects of uniform quantization. These are some fundamental
terms, quantization distortion, and quantizer design.

2.2.1.1 Definitions

Take a look at Figure 2.4. The horizontal axis denotes the input to a quantizer, while the vertical
axis represents the output of the quantizer. The relationship between the input and the output best
characterizes this quantizer; this type of configuration is referred to as the input-output characteristic
of the quantizer. It can be seen that there are nine intervals along the

x

-axis. Whenever the input
falls in one of the intervals, the output assumes a corresponding value. The input-output charac-
teristic of the quantizer is staircase-like and, hence, clearly nonlinear.

FIGURE 2.3

Block diagram of a source encoder and a source decoder.

© 2000 by CRC Press LLC

The end points of the intervals are called

decision levels

, denoted by

d

step
size

of the quantizer, denoted by

D

. With the above terms defined, we
can now mathematically define the function of the quantizer in Figure 2.4 as follows.
(2.1)
where

i

= 1,2,

L

,9 and

Q

(

x

) is the output of the quantizer with respect to the input


midrise

quantizer, in which the reconstructed levels do not include the value of zero. A
midrise quantizer having step size

D

= 1 is shown in Figure 2.5. Midtread quantizers are usually
utilized for an odd number of reconstruction levels and midrise quantizers are used for an even
number of reconstruction levels.

FIGURE 2.4

Input-output characteristic of a uniform midtread quantizer.
yQx if xdd
iii
=
()
Œ
()
+
,
1

© 2000 by CRC Press LLC

Note that the input-output characteristic of both the midtread and midrise uniform quantizers
as depicted in Figures 2.4 and 2.5, respectively, is odd symmetric with respect to the vertical axis



N

is odd, on the other hand, then the reconstruction level

y

(

N

+1)/2

= 0. This convention is
important in understanding the design tables of quantizers in the literature.

2.2.1.2 Quantization Distortion

The source coding theorem presented in Chapter 1 states that for a certain distortion

D

, there exists
a rate distortion function

R

(

D


Input-output characteristic of a uniform midrise quantizer.

© 2000 by CRC Press LLC

annoying false contours. In other words, more reconstruction levels are required in relatively
uniform regions than in relatively nonuniform regions.
In terms of objective evaluation, in Section 1.3.2 we defined mean square error (

MSE

) and root
mean square error (

RMSE

), signal-to-noise ratio (

SNR

), and peak signal-to-noise ratio (

PSNR

). In
dealing with quantization, we define quantization error,

e

q

)

f

x

(

x

). Mean square quantization error,

MSE

q

, can thus be expressed
as
(2.3)
where

N

is the total number of reconstruction levels. Note that the outer decision levels may be
–

•

or



x

, is equal to zero, i.e.,

E

(

x

) = 0. Therefore the mean square quantization error

MSE

q

is the variance of the quantization
noise equation, i.e.,

MSE

q

=

s

q


i
i
=-
()
()
()
+
Ú
Â
=
2
1
1

© 2000 by CRC Press LLC

intervals are unbounded as the input

x

approaches either –

•

or

•

. This type of quantization noise
is called

N

(hence, the number of decision levels,

N

+1), and selecting the values of decision
levels and reconstruction levels (deciding where to locate them). In other words, the design of a
quantizer is equivalent to specifying its input-output characteristic.
The

optimum

quantizer design can be stated as follows. For a given probability density function
of the input random variable,

f

X
(

x

), determine the number of reconstruction levels,

N



L

,

N

} such
that the mean square quantization error,

MSE

q

, defined in Equation 2.3, is minimized.
In the uniform quantizer design, the total number of reconstruction levels,

N

, is usually given.
According to the two features of uniform quanitzers described in Section 2.2.1.1, we know that the
reconstruction levels of a uniform quantizer can be derived from the decision levels. Hence, only
one of these two sets is independent. Furthermore, both decision levels and reconstruction levels
are uniformly spaced except possibly the outer intervals. These constraints together with the
symmetry assumption lead to the following observation: There is in fact only one parameter that
needs to be decided in uniform quantizer design, which is the step size

D

. As to the optimum

2.2.2.1 Uniform Quantizer with Uniformly Distributed Input

Let us return to Figure 2.4, where the input-output characteristic of a nine reconstruction-level
midtread quantizer is shown. Now, consider that the input

x

is a uniformly distributed random
variable. Its input-output characteristic is shown in Figure 2.7. We notice that the new characteristic
is restricted within a finite range of

x

, i.e., –4.5

£
x
£

4.5. This is due to the definition of uniform
distribution. Consequently, the overload quantization noise does not exist in this case, which is
shown in Figure 2.8.
MSE MSE MSE
qqgqo

()
()
()
Ú
2
2
1
2
© 2000 by CRC Press LLC
The mean square quantization error is found to be
(2.7)
FIGURE 2.7 Input-output characteristic of a uniform midtread quantizer with input x having uniform
distribution in [-4.5, 4.5].
FIGURE 2.8 Quantization noise of the quantizer shown in Figure 2.7.
MSE N x Q x
N
dx
MSE
q
d
d
q
=-
()
()
=
Ú
2
2
1

, we then have
(2.10)
The interpretation of the above result is as follows. If we use the natural binary code to code
the reconstruction levels of a uniform quantizer with a uniformly distributed input source, then
every increased bit in the coding brings out a 6.02-dB increase in the SNR
ms
. An equivalent statement
can be derived from Equation 2.7. That is, whenever the step size of the uniform quantizer decreases
by a half, the mean square quantization error decreases four times.
2.2.2.2 Conditions of Optimum Quantization
The conditions under which the mean square quantization error MSE
q
is minimized were derived
(Lloyd, 1982; Max, 1960) for a given probability density function of the quantizer input, f
X
(x).
The mean square quantization error MSE
q
was given in Equation 2.3. The necessary conditions
for optimum (minimum mean square error) quantization are as follows. That is, the derivatives of
MSE
q
with respect to the d
i
and y
i
have to be zero.
(2.11)
(2.12)
The sufficient conditions can be derived accordingly by involving the second-order derivatives

dy fd dy fd i N
ii xi ii xi
-
()
()
--
()()
==
-1
2
2
02,,L
--
()
()
==
+
Ú
xyfxdx i N
ix
d
d
i
i
01
1
,,L