Huffman coding and decoding for image(JPEG, BMP)

I have to implement huffman encoding and decoding for a '.bmp' image without using the inbuilt matlab function like huffmandict, huffmanenco and huffmandeco.

Can anybody help me by sending me the source code?

Moreover, I have done the encoding part but I am not able to do the decoding. I have no idea as how to reconstruct the image through decoding.

[Dimple Anandpara]

i implement given code of huffman encoding for a .bmp file but the encode string size more then actual size of file can u explain why?

[Walter Roberson]

That is possible. You need to store the code dictionary as well as the encoding. With 256 different symbols possible, unless at least half of them are never used, you can be sure that some of the encodings will be at least 8 bits, the original length. When the probabilities are about equally distributed each of the symbols would come out as 8 bits, so saving nothing for the encoded part. But you need to save the dictionary as well and that takes room.

Huffman encoding is a lossless encoding, so you need to have as much "information" stored in the encoded version as in the unencoded version. It doesn't begin to save space on the encoding until some of the symbols are at least twice as probable as some of the others or at least half the potential symbols are never unused, which are situations that would allow it to save 1 bit per occurrence. Those bits saved have to add up to the size of the saved dictionary before you get any net savings on the storage.

Efficient storage of the dictionary takes some thought since each of the entries is a variable number of bits -- the bit pattern and the symbol it decodes to. And remember to account for the end-of-stream marker or some other method of indicating where the end of the stream of bits is, since it will not generally be at a byte boundary so you can't tell by end-of-file.

[Jasmina Vanasiwala]

I have to implement huffman encoding and decoding for a 'jpeg' image using C or C++. Please anyone help me by sending the source code?

[Walter Roberson]

1. this is a resource for MATLAB questions not C or C++
2. there are already a lot of public sources for that task including libjpeg
3. if we send you source then you would not have implemented it. Would we get the academic credit or would you?

Answer 1

[Paulo Silva]

There are good examples on the matworks file exchange, for example this presentation with source code and good explanation

[Manisha Mehra]

Thanks..

It worked awesome.

[fateh]

how could i run this example

Answer 2

[Falak]

Try this one... just change to your required image

%Author Name:Falak Shah
%Target: To huffman encode and decode user entered string
%--------------------------------------------------------------------------
string=input('enter the string in inverted commas');         %input string
symbol=[];                                %initialise variables
count=[];
j=1;
%------------------------------------------loop to separate symbols and how many times they occur
for i=1:length(string)                   
  flag=0;    
  flag=ismember(symbol,string(i));      %symbols
      if sum(flag)==0
      symbol(j) = string(i);
      k=ismember(string,string(i));
      c=sum(k);                         %no of times it occurs  
      count(j) = c;
      j=j+1;
      end 
end    
ent=0;
total=sum(count);                         %total no of symbols
prob=[];                                         
%-----------------------------------------for loop to find probability and
%entropy
for i=1:1:size((count)');                   
prob(i)=count(i)/total;
ent=ent-prob(i)*log2(prob(i));            
end
var=0;
%-----------------------------------------function to create dictionary
[dict avglen]=huffmandict(symbol,prob);    
% print the dictionary.
         temp = dict;
         for i = 1:length(temp)
         temp{i,2} = num2str(temp{i,2});
         var=var+(length(dict{i,2})-avglen)^2;  %variance calculation
         end
         temp
%-----------------------------------------encoder  and decoder functions           
sig_encoded=huffmanenco(string,dict)
deco=huffmandeco(sig_encoded,dict);
equal = isequal(string,deco)
%-----------------------------------------decoded string and output
%variables
str ='';
for i=1:length(deco)    
str= strcat(str,deco(i));
end
str
ent
avglen
var

[sailaja]

its not working for an image

[sailaja]

how to use this code for an image

[Walter Roberson]

Change the input() call to,

filename = input('enter the image file name', 's');
string = imread(filename);
string = string(:);

[projecte]

hi how can i decode a image from a secret image in the same format

[juveria fatima]

filename = input('enter the image file name', 's');

what is 's' here

[satyendra kumar]

they not work properly.....how can solve it?

%Target: To huffman encode and decode user entered string
%--------------------------------------------------------------------------
filename = input('enter the image file name', 's');
string = imread('cameraman.tif');
string = string(:);
symbol=[];                                %initialise variables
count=[];
j=1;
%------------------------------------------loop to separate symbols and how many times they occur
for i=1:length(string)                   
  flag=0;    
  flag=ismember(symbol,string(i));      %symbols
      if sum(flag)==0
      symbol(j) = string(i);
      k=ismember(string,string(i));
      c=sum(k);                         %no of times it occurs  
      count(j) = c;
      j=j+1;
      end 
end    
ent=0;
total=sum(count);                         %total no of symbols
prob=[];                                         
%-----------------------------------------for loop to find probability and
%entropy
for i=1:1:size((count)');                   
prob(i)=count(i)/total;
ent=ent-prob(i)*log2(prob(i));            
end
var=0;
%-----------------------------------------function to create dictionary
[dict avglen]=huffmandict(symbol,prob);    
% print the dictionary.
         temp = dict;
         for i = 1:length(temp)
         temp{i,2} = num2str(temp{i,2});
         var=var+(length(dict{i,2})-avglen)^2;  %variance calculation
         end
         temp
%-----------------------------------------encoder  and decoder functions           
sig_encoded=huffmanenco(string,dict)
deco=huffmandeco(sig_encoded,dict);
equal = isequal(string,deco)
%-----------------------------------------decoded string and output
%variables
str ='';
for i=1:length(deco)    
str= strcat(str,deco(i));
end
str
ent
avglen
var

[Walter Roberson]

What leads you to say that it does not work?

[Harshil Patel]

I ran the code in matlab 2020a, and it generated some otput with some values for str, ent, avglen and var for an image input. So, how do I know if it's correct?

Answer 3

[slama najla]

Hello please is that you can help me? is that you can send me your registration code files before you get the picture compressed as I encounter the same problem as let go of compressed image is a very superior picture framer and my original remark that the fault is in the recording files. thank you in advance

[Walter Roberson]

The dictionary is dependent on the image being encoded. Having the dictionary for a different image would not help you.

[SS]

Can we use huffman coding for both lossy and lossless image compression??

[Walter Roberson]

Yes. After you derive your symbols and remove the ones with sufficiently low probability or merge them with the nearest higher probability symbol, you can do Huffman encoding on what is left.

[SS]

Thank you

[SS]

how to create huffman tree diagram for lossless image compression?

[Walter Roberson]

huffmandict()

[SS]

i have compressed an image with lossless compression using huffman coding algorithm....i want to draw huffman tree for this process in matlab....can you please tell me how can i show the tree in matlab???

[Walter Roberson]

https://www.mathworks.com/help/stats/dendrogram.html

[SS]

rng('default') % For reproducibility

X = rand(10,3);

In this code, what will be the value of X for my image..???