## 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?