A Lecture Series on

DATA COMPRESSION
Lossy Compression | Quantization

Abdou Youssef (Speaker)

Anastase Nakassis (MDVTG Manager)

1
 Motivation
 Need for low bitrate
{ Less than 0.2 bit per pixel for video
 Inadequacy of lossless compression
{ Achievable compression ratio hardly above 2
{ Achievable bitrate hardly below 4 bits per pixel
 Presence of visual redundancy that can be greatly exploited

2
 General Scheme of Lossy Compression
 Approach
1. Transform: Convert the data to the frequency domain
2. Quantize: Under-represent the high frequencies
3. Losslessly compress the quantized data
 Properties of transforms
{ Decorrelation of data
{ Separation of data into
 vision-sensitive data (low-frequency data)
 vision-insensitive data (high-frequency data)
 Various transforms achieve both properties
{ Fourier Transform
{ Discrete Cosine Transform (DCT)
{ Other Fourier-like transforms: Haar, Walsh, Hadamard
{ Wavelet transforms

3
 Properties of quantization
{ Progressive under-representation of higher-frequency data
{ Conversion of visual redundancy to symbol-level redun-
dancy that leads to high compression ratios
{ Minimum and controlled distortion: more errors in less
sensitive regions

 Examples of quantizers
{ Uniform scalar quantization
{ Non-uniform scalar quantization
{ Vector quantization (VQ)

4
Illustration of the Eects of Transforms
and the Need for Quantization

5
 Scalar Quantization
 Denition of Quantization/Dequantization:
{ A k-level quantizer is typically characterized by k + 1
decision levels d0; d1; : : : ; dk , and by k reconstruction
levels r0; r1; : : : rk,1.
{ The di's divide the range of data under quantization into
k consecutive intervals [d ; d ) [d ; d ) : : : [dk, ; dk ).
0 1 1 2 1

{ Each ri is in [di; di ), and can be viewed as the \centroid"

+1
of its interval.

{ Quantizing a number a means locating the interval [di; di ) +1

that contains a, and replacing a by index i.
{ Dequantization (in reconstruction) is the process of re-
placing each index i by the value ri. This approximates
every original number that was in interval [di; di+1) by the
centroid ri.
 A few quantizers assume that d = ,1 and dk = 1. But
0
in the majority of quantizers d0 and dk are nite numbers
representing the minimum and maximum value of the data
being quantized.
6
 Types of Scalar Quantizers
 Uniform Quantizers
{ All the decision intervals are of equal size
= dk,k d
0

 di = d + i

0

{ The reconstruction levels ri's are the centers of the inter-

vals
 ri = di +
2
di+1

 Non-Uniform Quantizers
{ Either the decision intervals are not of equal size
{ Or the reconstruction levels are not the centers of their
intervals
 Semi-Uniform Quantizers
{ Equal intervals
{ The reconstruction levels are not necessarily the interval
centers

7
Illustration of Quantizers

8
 Optimal Non-Uniform Quantizers
(Max-Lloyd Quantizers)
 Assume the data under quantization follows a probability
distribution p(x)

 The mean-square error (MSE) is

,1 Z dl+1
kX
E =
l=0 d l
( x , rl )2
p (x)dx

 To minimize the MSE, compute the partial derivatives of E

with respect to each di and each ri, and set them to 0
 Notation: The partial derivative of E with respect to a vari-
able u is denoted Eu

9
 Optimal Non-Uniform Quantizers (Cont.)
 Eri = 2 Rddii (ri,x)p(x)dx = 2[ri Rddii p(x)dx,Rddii xp(x)dx]
+1 +1 +1

 Eri = 0 implies
R di+1
ri = di xp(x)dx ; for all i = 0; 1; : : : k , 1
R di+1
di p(x)dx
 This means that the optimal ri is the probabilistic centroid
of its interval
 Edi = ,(ri , di) p(di) + (ri, , di) p(di)
2
1
2

 Edi = 0 implies that (ri, , di) = (ri , di) p(di), that is,
1
2 2

di , ri, = ri , di. Hence,

1

di = ri, 2+ ri ; for all i = 1; 2; : : : ; k , 1

1

 Remark: If p(x) is not known theoretically, treat

r
ri as the
r
statistical centroid of its interval, and di still as i,1+ i
2

10
 Max-Lloyd Quantizers (Cont.)
 The k centroid equations for the ri's, and the k , 1 decision
level equations for the di's form 2k , 1 equations of 2k , 1
unknowns
 Unfortunately, these equations are non-linear, and thus hard
to solve directly.
 The Max-Lloyd technique is an iterative algorithm for deriv-
ing very accurate approximations of di's and ri's
 Max-Lloyd Algorithm (for designing an optimal k-level quan-
tizer)
1. Start with arbitrary initial estimate for the di's
2. Repeat
R di+1
{ For all i, compute ri = Rddi i xpp xx dxdx
+1
( )

di ( )

{ For all i, compute di == ri, ri 1+

2

Until (the error between successive estimates of the di's

are less than a set tolerance)

11
 Optimal Semi-Uniform Quantizers
 The decision levels di's are known constants (di = d + i
)
0

 The reconstruction levels ri are the probabilistic (or statisti-

cal) centroids of their intervals [di; di+1).

12
Uniform vs. Non-Uniform vs. Semi-Uniform Quantizers
Advantages Disadvantages
 Very simple
Uniform  Fast to de-/quantize  The quality of recon-
Quan-  Stores the di 's & ri 's structed data is not
tizers optimal
 Leads to good symbol re-
dundancy

Non-  Costly to compute the di's

The quality of recon- & ri's
Uniform 
Quan- structed data is optimal  Costly to de-/quantize
tizers  Stores the di's & ri's

 Trivial di's and fast to com-

pute ri's  The quality of recon-
Semi-  Fast to de-/quantize structed data is less than
Uniform optimal
Quan-  No storage of the di's
tizers  Still requires the storage of
 good symbol redundancy the ri's
 The quality is very good

13
 Vector Quantization
 Scalar quantization is insensitive to inter-pixel correlations
 Scalar quantization not only fails to exploit correlations, it
also destroys them, thus hurting the image quality
 Therefore, quantizing correlated data requires alternative quan-
tization techniques that exploit and largely preserve correla-
tions
 Vector quantization (VQ) is such a technique
 VQ is a generalization of scalar quantization: It quantizes
vectors (contiguous blocks) of pixels rather than individual
pixels
 VQ can be used as a standalone compression technique op-
erating directly on the original data (images or sounds)
 VQ can also be used as the quantization stage of a gen-
eral lossy compression scheme, especially where the trans-
form stage does not decorrelate completely, such as in certain
applications of wavelet transforms

14
 The Main Technique of VQ
 Build a dictionary or \visual alphabet", called codebook, of
codevectors. Each codevector is a (1D or 2D) block of n
pixels
 Coding
1. Partition the input into blocks (vectors) of n pixels
2. For each vector v, search the codebook for the best match-
ing codevector v^, and code v by the index of v^ in the
codebook
3. Losslessly compress the indices
 Decoding (A simple table lookup)
1. Losslessly decompress the indices
2. Replace each index i by codevector i of the codebook
 The codebook has to be stored/transmitted
 The codebook can be generated on an image-per-image basis
or a class-per-class basis

15
 VQ Issues
 Codebook size (# of codevectors) Nc | how big or small?
 Codevector size n | how big or small?
 Codebook construction | what codevectors to include?
 Codebook structure | for faster best-match searches
 Global or local codebooks | class- or image-oriented VQ?

16
 Sizes of Codebooks and Codevectors
(Tradeos)

 A large codebook size Nc allows for representing more fea-

tures, leading to better reconstruction quality
 But a large Nc causes more storage and/or transmission
 A small Nc has the opposite eects
 Typical values for Nc: 2 ; 2 ; 2 ; 2 ; 2
7 8 9 10 11

 A larger codevector size n exploits inter-pixel correlations

better
 But n should not be larger than the extent of spatial corre-
lations

17
 Codevector Size Optimization

 Optimal codevector size n for minimum bitrate and constant

Nc
{ Consider N  N images with r bits per pixel, and let
n = p  p be the block size
{ Size S of the compressed image: Np log Nc + p rNc bits
2
2
2

{ The bitrate R = NS = p Nc + rNN c p

2
log
2 2
2

{ For minimum bitrate R, the derivative dRdp = 0

{ Since dRdp = ,2 p Nc + 2 rNN c p, we have
log
3 2

p = N rN
log N
2 31
2
6
6 c 77 4
4 5
c

 Concrete gures of optimal n for N = 512

Nc 26 27 28 29 210 211
p 7.4 6.5 5.6 4.9 4.2 3.6

18
 Codevector Size Optimization (Cont.)
 Therefore, optimal 2D codevector sizes are 4  4 and 8  8
for powers-of-2 sizes
 Interestingly, statistical studies on natural images have shown
that there is little correlation between pixels more than 8 po-
sitions apart, and in fact, most of the correlations ar among
pixels that are within 4 positions away.
 Therefore, 44 and 88 codewords are excellent choices from
both the bitrate standpoint and the correlation-exploitation
standpoint

19
 Construction of Codebooks
(The Linde-Buzo-Gray Algorithm)
 Main idea
1. Start with an initial codebook of Nc vectors;
2. Form Nc classes from a set of training vectors: put each
training vector v in Class i if the i-th initial codeword is
the closest match to v;
Note: The training set is the set of all the blocks of the im-
age being compressed. For global codebooks, the training
set is a the set of all the blocks of a representative subset
of images selected from the class of images of the applica-
tion.
3. Repeatedly restructure the classes by computing the new
centroids of the recent classes, and then putting each
training v vector in the class of v's closest new centroid;
4. Stop when the total distortions (dierences between the
training vectors and their centroids) ceases to change much;
5. Take the most recent centroids as the codebook.

20
The Linde-Buzo-Gray (LBG) Algorithm (Cont.)
 The algorithm in detail
1. Start with a set of training vectors and an initial code
book X^ 1(1), X^ 2(1), ..., X^ N(1)c . Initialize the iteration index l
to 1 and the initial distortion D(0) to 1.
2. For each training vector v, nd the closest X^ i(l):
d(v; X^ i(l)) = min1kNcd(v; X^ k(l));
where d(v; w) is the (Eucledian or MSE) distance between
the vectors v and w.
Put v in class i.
3. Compute the new total distortion
N
= X X d(v; X^ i(l)):
c
D l
( )

i=1 v2Class i
l,1)
If j D D l,,D j  TOLERANCE, the convergence is reached;
( l
( )
( 1)

stop and take the most recent X^ 1(l), X^ 2(l),..., X^ N(lc) to be the
codebook.
Else, goto step 4.
4. Compute the new class centroids (vector P
means):
l := l + 1; and for all i, X^ i(l) := sizev2ofClassClass
iv .
i
Goto 2.
21
 Initial Codebook
 Three methods for constructing an initial codebook
{ The random method
{ Pairwise Nearest Neighbor Clustering
{ Splitting
 The random method:
{ Choose randomly Nc vectors from the training set
 Pairwise Nearest Neighbor Clustering:
1. Form each training vector into a cluster
2. Repeat the following until the number of clusters becomes
Nc: merge the 2 clusters whose centroids are the closest
to one another, and recompute their new centroid
3. Take the centroids of the Nc clusters as the initial code-
book

22
 Splitting
1. Compute the centroid X1 of the training set
2. Perturb X1 to get X2, (e.g., X2 = :99  X1)
3. Apply LBG on the current initial codebook to get an op-
timum codebook
4. Perturb each codevector to double the size of the code-
book
5. Repeat step 3 and 4 until the number of codevectors
reaches Nc
6. In the end, the Nc codevectors are the whole desired code-
book

23
 Codebook Structure
(m-ary Trees)
 Tree design and construction
1. Start with codebook as the leaves
2. Repeat until you construct the root
{ cluster all the nodes of the current level into m-node
clusters
{ create a parent node for each cluster of m nodes
 Searching for a best match of a vector v in the tree
{ Search down the tree, always following the branch that
incurs the least MSE
{ The search time is logarithmic (rather than linear) in the
codebook size
 Rened Trees
{ Tapered trees: The number of children per node increases
as one moves down the tree
{ Pruned Tress: Eliminate the codevectors that contribute
little to distortion reduction

24
 Advanced VQ
 Prediction/Residual VQ
{ Predict vectors
{ compute the residual vectors,
{ VQ-Code the residual vectors
 Mean/Residual VQ (M/R VQ)
{ Compute the mean of each vector and subtract it from
the vector
{ VQ-code the residual vectors
{ Code the means using DPCM and scalar quantization
{ Remark: Once the means are subtracted from the vectors,
many vectors become very similar, thus requiring fewer
codevectors to represent them
 Interpolation/residual VQ (I/R VQ)
{ subsample the image by choosing every l-th pixel
{ code the subsampled image using scalar quantization
{ Upsample the image using bilinear interpolation
{ VQ-code the residual (original-upsampled) image
{ remark: residuals have fewer variations, leading to smaller
codebooks

25
 Gain/Shape VQ (G/S VQ)
{ Normalize all vectors to have unit gain (unit variance)
{ Code the gains using scalar quantization
{ VQ-code the normalized vectors

26