Lab 2: Lossless compression of real world signals

Task

The goal of the lab is to compress some real world signals (audio and images), using simple prediction and Huffman coding.

The work should be done in groups of 1 or 2 students.

Examination of the lab is by written report.

Audio signals

The audio signals consist of two music signals and one speech signal. The music signals are mono, sampled with 44.1 kHz sampling frequency and quantized to 8 bits/sample (256 levels). The speech signal is mono, sampled with 8 kHz sampling frequency and quantized to 8 bits/sample (256 levels).

• hey04_8bit.wav
• nuit04_8bit.wav
• speech.wav

In Matlab, WAV files can be easily read using the function audioread. It will return a vector of samples, scaled so that they take values between -1 and 1. To get integers between -128 and 127 just multiply the signal by 128.

Memoryless Huffman coding

Calculate what data rate is achieved when simple Huffman coding of individual samples is done, independent of earlier samples.

You do not have to write your own Huffman coder, although I’m not going to stop you from trying. You can use this function (read the help text and program code to understand how it works).

Simple predictive coding

In order to take advantage of the memory (dependance) between neighbouring audio samples, you should do simple predictive coding. First you do a prediction p_i and then Huffman coding of the prediction error d_i = x_i-p_i, where x_i are the audio samples.

Try the following two predictors:

• p_i = x_i-1
• p_i = 2*x_i-1-x_i-2

Imagined samples before the the first sample in the test signals can be assumed to be 0.

Compare to lab 1

In lab 1 you estimated entropies as theoretical limits for compression. Compare your data rates to your entropies. Which predictor can be compared to which entropy?

Also listen to the audio signals and comment on how the character of the audio affects the data rate.

Still images

The images are greyscale images quantized to 8 bits/pixel, ie each pixel can take values between 0 (black) and 255 (white). There are three images to test:

• baboon.png
• boat.png
• woodgrain.png

You can read images in Matlab using the function imread. It will return a two dimensional matrix of the type uint8. In order to be able to properly manipulate data, it can be a good idea to convert to the data type double (eg x=double(x);).

Memoryless Huffman coding

Calculate what data rates are achieved when simple Huffman coding of individual pixels is done, independent of surrounding pixels.

Simple predictive coding

In order to take advantage of the memory (dependance) between neighbouring pixels, you should do simple predictive coding. First you do a prediction p_ij and then Huffman coding of the prediction error d_ij = x_ij-p_ij, where x_ij are the pixel values.

Try the following three predictors:

• p_i,j = x_i-1,j
• p_i,j = x_i,j-1
• p_i,j = x_i-1,j+x_i,j-1-x_i-1,j-1

Pixels outside the edges of the image can be assumed to be middle grey, ie have the value 128.

Compare to lab 1

In lab 1 you estimated entropies as theoretical limits for compression. Compare your data rates to your entropies. Which predictor can be compared to which entropy?

Comment on how the content of the images affect the rates and entropies.

Comparison to PNG

The three image files as given are compressed using the PNG standard. You can thus compare the rate of your three predictive coders to the rates from PNG coding (just divide the file size in bits with the size of the image).

Bonus problem: MED prediction of images (not mandatory)

If you are interested, you can also try the Median Edge Detector (MED) predictor used in JPEG-LS and see how it compares to the three simple linear predictors above.

See the course material to see how MED prediction works.

Examination

Examination of the lab is by a short written report. Describe how you solved the problems and what your results are. Also include any program code you’ve written.

Send an electronic version of your report (in PDF format) to Harald. Give the name, person number and email adress of every group member.

Deadline

No hard deadline. I would prefer if you send in your reports before the exam period. If you are late, you might have to wait until the next exam period for your points to be reported into Ladok.

Questions?

If you have any questions about the lab, contact Harald.