%% Measures:  Entropy and Huffman Coding
%
% *Wavelets Workshop*
%
% June 2 - 5, 2009
%
% University of South Florida
%
% *Catherine Beneteau*, *Caroline Haddad*, *David Ruch*, *Patrick Van Fleet*

%% Huffman Codes
%
% The DiscreteWavelets Toolbox includes two functions that are useful for
% creating and analyzing Huffman codes.
%

%% MakeHuffmanCodes
%
% The DiscreteWavelets function |MakeHuffmanCodes| can be used to generate 
% Huffman codes for a list of integers, a string, or a matrix of integers. 
% Note that integer input must be nonnegative.
%
% The routine returns five pieces of information.  The first is a list of 
% unique integers or characters that appeared in the input, the second is
% list of the relative frequencies of each unique value, and the third is 
% a list of Huffman codes for each unique value.  The fourth output is the
% original bitstream length of the input and the last return value is the
% new bitstream length.
%

[uniq, freq, codes, origlen, newlen] = MakeHuffmanCodes('pitterpatter')

%%
% We can also find the Huffman codes of an image:

img = ImageNames('ImageType', 'GrayScale', 'ListThumbnails', 'True');
A = ImageRead(img{1});
ImagePlot(A);
[uniq, freq, codes, origlen, newlen] = MakeHuffmanCodes(A);
str=sprintf('The original bitstream length is %i and the new bistream length is %i.',origlen,newlen);
disp(str);

%% HuffmanTree
%
% For small input, we can use |HuffmanTree| to visualize the output of
% |MakeHuffmanCodes|.  The input of |HuffmanTree| is the first three 
% outputs of |MakeHuffmanCodes|.  There are several graphics options for 
% |HuffmanTree|.  See Help for more information.

[uniq, freq, codes, origlen, newlen] = MakeHuffmanCodes('tennessee');
figure;
HuffmanTree(uniq,freq,codes);

%% Exercises
%
% *Exercise 1*
%
% Load the surfer image (small version) from the DiscreteWavelets package
% and find the bits per pixel that results from the Huffman coded version
% of the image.

%%
% Place your answer here.  To type an answer, start a line with %.  Matlab
% commands are entered as usual.

%%
%
% *Exercise 2 (Challenge)
%
% Suppose you pass a string |s| to |MakeHuffmanCodes|.  Write a function 
% that will take the codes returned by |MakeHuffmanCodes| and |s| and 
% return the new bitstream.  Call the function |MakeBitstream|.  You will 
% have to add this m-file to the MyFiles folder.
%
% For example:

s = 'boohoo';
figure;
[uniq, freq, codes, origlen, newlen] = MakeHuffmanCodes(s);
HuffmanTree(uniq, freq, codes);

%%
%
% Using the tree above and |s|, we see that the new bitstream for 
% "boohoo" is 01110011.

%% Entropy
%
% The DiscreteWavelets command for entropy is |Entropy|.  The function 
% takes either a vector or matrix as input.  Here are some example calls:

v = 1:16
str=sprintf('The entropy of vector v is %f.', Entropy(v));
disp(str);
A = eye(8);
str=sprintf('The entropy of the 8x8 identity matrix is %f.', Entropy(A));
disp(str);

%% Exercises
%

%% 
% *Exercise 1 (Challenge)*
%
% Under the MyFiles folder, open the m-file MyEntropy.m.  In this file,
% create a function that computes the entropy of either a vector or a
% matrix.  Useful Matlab commands are |histc|, |uniq|, |length|, and
% |log2|.
%
% Use the cell below to test your code.

v = round(rand(1,10)*10);
Entropy(v)
MyEntropy(v)

A = round(rand(8,8)*10);
Entropy(A)
MyEntropy(A)

%%
close all;
displayEndOfDemoMessage(mfilename)