To Implement Huffman Code Using the Matlab.

Hello readers!!!

Today we’ll talk about the implementation of the huffman coding using the Matlab. As you all guys are familiar with the programming language Matlab and it’s various uses in the various fields.

I’ve been working on the Image Processing section of the Matlab and Found out that Image compression using the Matlab can be done only by eliminating the three basic types of redundancies which are stated as follows:-

  1. coding redundancy : It is present when less than the optimal code words are used to represent any image.
  2. Interpixel redundancy : It arises due to the correlation between the pixels of an Image.
  3. PsychoVisual redundancy : It is due to the data ignored by the human visual system.

For more details about the Compression techniques and redundancies found in the image. You can follow this link Compression techniques and redundancies.

Now we’ll move ahead with our topic that is about implementing the huffman coding using the Matlab. Here i assume that you have a sufficient knowledge of Matlab prgramming. Because in this post we’re goin’ to cover the coding part of implementing huffman code with only brief and necessary theory.

Huffman Code:

When coding the grey level(intensity) of an image or the output of the grey-level mapping operation, Huffman codes contains the smallest  possible number of code symbols(e.g. bits) per source symbol(e.g grey-level) subject to the constraint.

The first step in Huffman approach is to create a series of source reductions by ordering the probabilities of the symbols under consideration and combining the lowest probability symbols into a single symbol that replaces them in the next source reduction.The figure shown below illustrates the process for the gray level distributions. This figure shows the process of source reductions.

image

The second step in Huffman approach is to code each reduced source, starting with smallest source and working back to the original source. The minimum length binary code for a two-symbol source, of course , consists of the symbols 0 and 1.The figure below illustrates the second step of the Huffman’s procedure. The figure below show the process involved in coding the reduced source.

image

The huffman code represented in the figure above is an instantaneous uniquely decodable block code. It is block code because each source symbol has been mapped into a fixed sequence of code symbols. It is instantaneous because each code word in a string of code symbols can be decoded without referencing succeeding symbols.For the 4 X 4 image, a top-to-bottom, left-to-right encoding based on the figure second would yield the 29 bit string of 0 and 1.

If You found the above text insufficient for learning the huffman algorithm. You can follow this link Huffman coding and Algorithm. But for the time being I hope that you guys are familiar with the huffman coding and we’ll proceed with making a Matlab program which implements the huffman coding for the given input vector.

The source reduction and code assignment procedures just described are implemented by using the following M function.

function CODE = huffman(p)
%HUFFMAN Builds a variable-lenght Huffman code for a symbol source.
%CODE = HUFFMAN(P) returns a huffman code as binary strings in cell
%array CODE for input symbol probability vector P. Each word in CODE
%corresponds to a symbol whose probability is at the corresponding index
% of P.
%
%check the input arguments for reasonableness.
error(nargchk(1,1,nargin));
if (ndims(p) ~= 2) | (min(size(p))>1) | ~isreal(p) | ~isnumeric(p)
error(‘P must be a real numeric vector.’);
end
% Global variable surviving all recursions of function ‘makecode’
global CODE
CODE = cell(length(p),1);             % Init the global cell array
if length(p) > 1                     % When more than one symbol…
p = p/sum(p);                     % Normalize the input probabilities
s = reduce(p);                    % Do Huffman source symbol reductions
makecode(s, []);                  % Recursively generate the code
else
CODE = {’1′};                    % Else, trivial one symbol case!
end
%……………………………………………………………….%
function s = reduce(p);
%Create a Huffman source reduction tree in a MATLAB cell structure by
%performing source symbol reductions until there are only two reduced
%symbols remaining.
s =  cell(length(p),1);
%Generate a starting tree with symbol nodes 1,2,3,.. to reference the
%symbol probabilities.
for i = 1:length(p)
s{i} = i;
end
while numel(s) > 2
[p,i] = sort(p);             % Sort the symbol probabilities
p(2) = p(1) + p(2);          % Merge the 2 lowest probabilities
p(1) = [];                  % and prune the lowest one
s = s(i);                    % Reorder tree for new prbabilities.
s{2} = {s{1},s{2}};          % and merge & prune its nodes
s(1) = [];                  % to match the probabilities
end

%……………………………………………………………….%
function makecode(sc, codeword)
% Scan the nodes of a Huffman source reduction tree recursively to
% generate the indicated variable length code words.
% Global variable surviving all the recursive calls
global CODE
if isa(sc,’cell’)                                          % For cell array nodes,
makecode(sc{1},[codeword 0]);         % add 0 if the 1st element,
makecode(sc{2}, [codeword 1]);        % or a 1 if the 2nd
else                                                            % For leaf (numeric) nodes,
CODE{sc} = char(’0′ + codeword);     % create a char code string
end

Just save this above code as “huffman.m” file.

After creating the M file for implementing the huffman code. Now we’ll test this huffman function. we’ll do it by making another M file named as example.m

clc
% provide the input vector to create the huffman code
f = [0.1875 0.5 0.125 0.1875];
c = huffman(f) %calling the huffman function

Just save and run the above code and output will b shown.

This function efficiently produce the huffman code for a given input vector. If any of the step in the coding is not clear to you. You can simply provide your comment to my blog and i’ll try to resolve it as soon as possible.

Will meet you guys next time with more on Image processing using the Matlab.

Have a good day!!!!

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: