LOSSY COMPRESSION III
Introduction
Compression in all the lossy schemes is achieved
through quantization.
The process of representing a large possibly
infinite set of values with a much smaller set is
called quantization
Example: Source generates numbers between -10.0
and +10.0 Simple scheme is to represent each
output of the source with the integer value closer to
it.
Introduction
Two types of quantization
Scalar Quantization.
Vector Quantization.
The design of the quantizer has a significant
impact on the amount of compression (i.e.,
rate) obtained and loss (distortion) incurred in
a lossy compression scheme
Scalar Quantization
Many of the fundamental ideas of quantization and
compression are easily introduced in the simple
context of scalar quantization.
Any real number x can be rounded off to the nearest
integer, say
Q(x) = round(x)
Maps the real line R (a continuous space) into a
discrete space.
Scalar Quantization
Quantizer: encoder mapping and decoder
mapping.
Encoder mapping
The encoder divides the range of source into a number
of intervals
Each interval is represented by a distinct codeword
Decoder mapping
For each received codeword, the decoder generates a
reconstruct value
Scalar Quantization
Encoder mapping: Divides the range of values that the
source generates into a number of intervals. Each interval is
then mapped to a codeword. It is a many-to-one irreversible
mapping. The code word only identifies the interval, not the
original value.
Codes
000 001
-3.0
010
-2.0
-1.0
011
100 101 110
0
1.0
2.0
111
3.0
input
Scalar Quantization
Decoder: Given the code word, the decoder
gives an estimated value that the source might
have generated.
Usually, it is the midpoint of the interval but a
more accurate estimate will depend on the
distribution of the values in the interval.
Mapping of a 3-bit Decoder
Input Codes
Output
000
001
010
011
100
101
110
111
-3.5
-2.5
-1.5
-0.5
0.5
1.5
2.5
3.5
Encoder Decoder Example
Scalar Quantization
Quantization operation:
Let M be the number of reconstruction levels
Q( x) y j
iff
bi 1 x bi
where the decision boundaries are
and the reconstruction levels are
bi
M
i 0
M
i i 1
Scalar Quantization
MSQE (mean squared quantization error)
If the quantization operation is Q
Q( x) y j
iff
bi 1 x bi
Suppose the input is modeled by a random variable X
with pdf fX(x). The MSQE is
M bi
i 1 b
q 2 ( x Q( x))2 f X ( x) dx ( x yi ) 2 f X ( x) dx
i 1
Scalar Quantization
Rate of the quantizer
The average number of bits required to represent a
single quantizer output
For fixed-length coding, the rate R is:
For variable-length coding, the rate will depend on the
probability of occurrence of the outputs
M
R li
i 1
bi
f X ( x)dx
bi1
Scalar Quantization
Quantizer Design Problem:
Given an input pdf fX(x) and the number of levels M in
the quantizer, find the decision boundaries {bi} and the
reconstruction levels {yi} so as to minimize the MSQE
(Mean Square Quantization Error)
q 2 ( x Q( x))2 f X ( x) dx
bi
( x yi ) 2 f X ( x) dx
i 1 bi 1
Scalar Quantization
Find the optimum partitions, codes and representation
levels
Given a distortion constraint, find the decision boundaries,
reconstruction levels, and binary codes that minimize the
rate, while satisfying the distortion constraint given above.
Given a rate constraint find the decision boundaries,
reconstruction levels, and binary codes that minimize the
distortion.
Uniform Quantizer
Simplest Quantizer
All intervals are of the same size say , except
for the two outer intervals.
ie., the decision boundaries are spaced evenly.
The reconstruction values are also spaced evenly,
with the same spacing as decision boundaries.
They are the midpoints of the decision
boundaries except in the outer intervals
Uniform Quantization of a Uniformly
Distributed Source
Uniform Quantization of a Uniformly
Distributed Source
Uniform Quantization of a Uniformly
Distributed Source
Summary:
If the distortion constraint is given as D*, then step size can
be calculated directly, since
2
D* = 12
M = (xmax xmin)/
If the rate constraint is given as R*, then M can be calculated,
hence can be calculated.
2
Then distortion is D = 12
Example Image compression
Assume Image pixels are uniformly distributed between 0
& 255.
1 bit/pixel [0,255] is divided into two intervals [0,127]
and [128,255]
Reconstruction levelsmidpoints of intervals {64, 196}.
2 bits/pixel Four intervals [0,64,128,196,255]
boundaries
Reconstruction levels {32,96,160,224}
UNIFORM QUANTIZATION EXAMPLE
UNIFORM QUANTIZATION EXAMPLE
