Göm meny

Lab 1: Lossless coding of audio and still images

The goal of the lab is to make simple random models for some different signals (audio and images), calculate entropies for the models and calculate data rates given Huffman coding of the signals. You don't have to find the actual codewords in the Huffman codes, only the resulting rates are important.

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).

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.

Entropy estimation

To get an idea of what theoretical performance can be expected, you should estimate some entropies. The entropies to be estimated are H(Xi), H(Xi,Xi+1) (pair entropy) and H(Xi+1 | Xi) (conditional entropy), assuming that the signal can be viewed as a stationary process Xi.

Memoryless Huffman coding

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

If you don't want to write your own Huffman coder, you can use this function (read the 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 pi and then Huffman coding of the prediction error di = xi-pi, where xi are the audio samples. Try the following two predictors:
• pi = xi-1
• pi = 2*xi-1-xi-2
Imagined samples before the the first sample in the test signals can be assumed to be 0.

Compare your data rates with the estimated entropies.

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: 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, you should convert the images to the data type double (eg x=double(x);).

Entropy estimation

To get an idea of what theoretical performance can be expected, you should estimate some entropies. The entropies to be estimated are H(Xi,j), H(Xi,j,Xi+1,j), H(Xi,j,Xi,j+1) (pair entropy horizontally and vertically), H(Xi+1,j | Xi,j) and H(Xi,j+1 | Xi,j) (conditional entropy horizontally and vertically).

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 pij and then Huffman coding of the prediction error dij = xij-pij, where xij are the pixel values. Try the following three predictors:
• pi,j = xi-1,j
• pi,j = xi,j-1
• pi,j = xi-1,j+xi,j-1-xi-1,j-1
Pixels outside the edges of the image can be assumed to be middle grey, ie have the value 128.

Compare the data rates with the estimated entropies.

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

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.