Description
1) Scalar Quantization
Suppose that a random variable X has the two-sided exponential pdf
fX(x) = λ
2
e
−λ|x|
A three level quantizer q for X has the form
q(x) =
+b for x > a
0 for −a ≤ x ≤ +a
−b for x < −a
(a) Find a simple expression for b as a function of a so that the centroid condition is met. You may
use that:
Z ∞
c
xe−λxdx =
ce−λc
λ
+
e
−λc
λ
2
(b) For what value of a will the quantizer satisfy the nearest neighbor condition for optimality (using
b chosen as above, so the centroid condition is satisfied too)? Give specific values for a and b in
terms of λ.
2) Lloyd Algorithm for Quantizer Design
A 3-level quantizer is to be designed to minimize mean squared error using the Lloyd algorithm
with the training set
T = {1, 2, 3, 4, 8, 9, 12}
If we start with the initial codebook C0 = {2.0, 6.0, 10.0} what does it converge to? You will
find you need to enunciate a tie-breaking rule, that is, if a training point is exactly on a decision
boundary, then does it belong to the partition region on the left, or to the one on the right? Try it
both ways.
Show the sets of transition (decision) levels and the sets of quantization (reproduction)
level for all steps of the Lloyd Algorithm. Final answer within one decimal place of precision is
adequate. A computer is not needed.
3) Comparing quantization for images
a) Write a function that takes as inputs an 8-bit image and a scalar s ∈ [1, 7] and performs
uniform quantization so that the output is quantized to a s-bit image.
b) The m-file lloyds.m is found in the communications toolbox in MATLAB. It performs Lloyd
Max quantization, attempting to minimize mean square error through an iterative algorithm
(just as you did in the previous problem) by alternating between optimizing the quantization
levels for the given partition (decision levels) and optimizing the partition for the current
quantization levels.
If you don’t have this toolbox lloyds.m (and quantiz.m which is called by
lloyds) are provided on Piazza. You can use lloyds in various ways:
[partition,codebook] = lloyds(training set,initcodebook)
where you give it an initial codebook, or
[partition, codebook] = lloyds(training set, len)
where len is the size of the codebook desired.
The input training set is a vector of training
data (which is used as an empirical measure of the probability mass function), so you will
have to reshape an image into a vector to use it as the training data for lloyds:
>> [N,M] = size(image);
>> training_set = reshape(image,N*M,1);
You are given three images: vase.tif, testpattern512.tif, and astronaut.tif. For each image,
calculate the mse values for s = 1, . . . , 7 using both your uniform quantizer and lloyds.m.
Plot the results. Show one plot for vase (with both uniform and Lloyd Max quantization),
a second plot for testpattern512, and a third plot for astronaut. Compare the results for the
different quantizers/images and explain them. (It will help to examine the histograms of the
three images to understand the performance of the quantizers.) In particular, you should answer
the following questions:
• Which quantizer does better in general, and why?
• At the low end (1 or 2 bits for the quantization), if you look at the ratio of the performance
between the two types of quantization, for which image is that ratio largest, and for which
image is it smallest, and why?
c) Here we consider whether quantizers can get worse distortion with increasing bit rate.
• In the plots, the MSE for the Lloyd quantizer decreases as expected with increasing bit rate.
But for the uniform quantizer, for one of the images, the quantizer gets worse at one point
when it is given an increase in bits. Why does this happen?
• Although for these images we don’t see the Lloyd quantizer getting worse with increasing
bit rate, is it possible that this could happen with the Lloyd algorithm?