how can i do huffman encoding in image compression

hi,i am doing lossy image compression using discrete cosine transform i had done all the steps of the compression(dct then quantization then zigzag scan) now i have a vector and i want to do huffman encoding i know that the code as follows

 [dict,avglen] = huffmandict(symbols,p) 
 comp = huffmanenco(sig,dict)

i am asking now how to get the symbol and p(probability) from the large vector that i have to do the encoding

[shabu sathyadhas]

%function which converts array to vector
vec_size = 1;
for p = 1:m
for q = 1:n
newvec(vec_size) = I(p,q);
vec_size = vec_size+1;
end
end

%Huffman Encodig
hcode = huffmanenco(newvec,dict);

%Huffman Decoding
dhsig1 = huffmandeco(hcode,dict);

%convertign dhsig1 double to dhsig uint8
dhsig = uint8(dhsig1);

%vector to array conversion
dec_row=sqrt(length(dhsig));
dec_col=dec_row;

%variables using to convert vector 2 array
arr_row = 1;
arr_col = 1;
vec_si = 1;

for x = 1:m
for y = 1:n
back(x,y)=dhsig(vec_si);
arr_col = arr_col+1;
vec_si = vec_si + 1;
end
arr_row = arr_row+1;
end

Answer 1

[Walter Roberson]

If your vector is uint8() then one way of doing it is

symbols = unique(YourVector(:));
counts = hist(YourVector(:), symbols);
p = double(counts) ./ sum(counts);

This is not the only way.

[juveria fatima]

how to get compressed image from huffman

[Walter Roberson]

The compressed image is the output of huffmanenco.

[Nikolo]

Sir how do I get the compressed size of the Image and I want to show it? and I want to show the compressed image also. This is my code. I am not sure how will I do it.

% This will be the second part of the code it will contain the Huffman part of
% the project plus its statistics like the compression ratio the size gain
% and the differences between the orignal image and decompressed image


% uigetfile command opens a GUI to select an image notice the formats and
% the other input is to select an image. it outputs three outputs: 
% N which is file name 
% P the path and 
% Filter contains the index of selected format its value is 
% [1- bmp] [2- jpg]  [3- tif] [4- gif]

Classes = {'*.bmp'; '*.jpg'; '*.tif'; '*.gif'}; 
[N, P, Filter] = uigetfile(Classes, 'Select an image');
                
% Read the image
Aorg = imread(strcat(P, '\', N));

% Aorg = imresize(Aorg, [50 50]);
% Store the image size for retrieval by the decoder
[m, n, d] = size(Aorg);


% Calculating the unique enteries which will be used on the creation of
% the dictionary 

tic = now; % As earler on the LZW to save the start time

% Calculating the unique enteries which will be used on the creation of
% the dictionary 
uA = unique(Aorg);

% The Huffman coding needs a dictionary which must contain the intensity
% occurances so the hist command is used for that. The second entry is the
% histogram unique value, generally, the hist command will output histogram
% values with some zeros if the inbetween values was zeros. Thus why
% inputting the unique entries as a second input to confine the histogram
% values for histogram creation.
[D, N] = hist(Aorg(:), double(uA));

% Normalizing the occurences (This was needed due to an occuring error actually)
Dn = D / sum(D(:));

% Actual Huffman dictionary creation 
Dict = huffmandict(N, Dn);

% Huffman Encoding step it takes the image as a vector thus why the (:) and
% the dictionary created byb Huffmandict command and will produce the
% compressed in comp
Comp = huffmanenco(Aorg(:), Dict);
toc = now; % To store the time after encoding completes

%
% Decoder =========================c===========
% Huffman decoding step which take the earlier created dictionary and the
% compressed data to produce the reconreuced image
Dec = huffmandeco(Comp, Dict);

% This reshaping as the LZW to restore the original image dimensions 
DecR = reshape(Dec, [m, n, d]);
toc2 = now; % To store the time of the overall process

% Results and statistics
%====================================
%%
close all
figure, imshow(Aorg)
figure, imshow(uint8(DecR))


% Calculate the compression ratio
% The image this time is given by MxNxK which is the matrix dimensions
% multiplied by the number of intensity levels, We can fuse the MxN by the
% numel operation. However, the dictionary is already binary so it doesn't
% require (x8)
SZimg = numel(Aorg) * 8;
SZcod = numel(Comp);
CR = SZimg / SZcod;

% To calculate the computation time
EncTime = toc - tic;  % Encoding time
oaTime = toc2 - tic;  % overall time
clc
fprintf('The algorithm has finished execution CR = %xs The image class was %s\nThe computation time was %x for encoding and overall time %xs\n', CR, Classes{Filter}(3:end),  EncTime, oaTime)

[Walter Roberson]

Compressed size of the image is the number of elements in Comp times the number of bytes per element in Comp, plus the size occupied by Dict, which is going to be a cell array. You can use whos() to find the size of the cell array in bytes.

Note that this is not going to be the same as the theoretical compressed size of the image, which is something that deals with how few bits you could pack the information in to, and therefore depends upon the number of occupied bits per byte in Comp and Dict. The difference can be quite large as Comp is probably going to end up being a double array (64 bits per element) in which only 1 bit per element (0 or not 0) is significant.

[Walter Roberson]

A question for you:

Suppose you had an image that is uint8() whose values are exclusively 17 or 240. Only two different values. So you could encode that as 0 (representing 17) or 1 (representing 240):

Z = zeros(size(YourImage));
Z(YourImage == 240) = 1;

Now, what is the compression ratio between YourImage (uint8) and Z (which has only values 0 and 1)?

Now consider

X = (YourImage == 240);

Now what is the compression ratio between YourImage (uint8) and X (which has only values false and true) ?

[merr LAMINe]

% Actual Huffman dictionary creation 
Dict = huffmandict(N, Dn);
% Huffman Encoding step it takes the image as a vector thus why the (:) and
% the dictionary created byb Huffmandict command and will produce the
% compressed in comp
Comp = huffmanenco(Aorg(:), Dict);
toc = now; % To store the time after encoding completes
%
% Decoder =========================c===========
% Huffman decoding step which take the earlier created dictionary and the
% compressed data to produce the reconreuced image
Dec = huffmandeco(Comp, Dict);
% This reshaping as the LZW to restore the original image dimensions 
DecR = reshape(Dec, [m, n, d]);

Mr.nikolo you encoded by huffman then decoded to obtain compressed image(matrix) , my question where the compression. I think that " Dec = Aorg(:) ) !!!

[Walter Roberson]

There is compression provided that the memory required for Comp plus the memory required for Dict is less than the memory required for Aorg .

However, as I discussed above, the values returned in Comp are all double precision 0 or double precision 1, so if you were careful when you wrote to a file you could use 1 bit for each element instead of 8 bytes, which would be 64 times less memory for that part. When Huffman encoding is being discussed in theory, the discussion is about how few bits you could write the data to in a file and still read it back perfectly, rather than about how much memory in core is used due to weak Quality of Implementation.

[Walter Roberson]

Search also for tag:"compression ratio", such as https://www.mathworks.com/matlabcentral/answers/433311-how-to-compute-number-of-dedicated-bits-in-arithmetic-coding-in-matlab#answer_350087

[Basit Shah]

Hi. Why does the vector have to be uint8 for your answer to work?

[Walter Roberson]

At the moment I do not recall why I indicated uint8 years ago.

The steps I outlined should work for any numeric type or categorical, but perhaps might not work for char... I would need to check that.

[Basit Shah]

ah right, thanks for the clarification.

[Basit Shah]

when i use huffmanenco after generating the dictionary it produces an output larger than the original input. Any reasons why this could be happening? I've zigzag scanned and run length enocded the input before passing it to huffmanenco.

[Walter Roberson]

Each element of the output is logically 1 bit of information, whereas the input was (probably) 8 bits. So you should be comparing the length of the encoding to 8 times the length of the original.

[Basit Shah]

Thank you for the clarification again. Just read the documentation properly after reading your comment and it shows the correct way to compare lengths. Sorry should have read the documentation before asking but thank you nonetheless

[NAGA PAVAN KALYAN KUMAR TENTU]

Sir I need whole source code of this question. From starting image to gray,DCT, quantization and application of Huffman encoding to end.

[Walter Roberson]

@NAGA PAVAN KALYAN KUMAR TENTU

If you look around long enough in MATLAB Answers, you can probably find the entire source code (though you might have to piece it together from a couple of postings.)

But we are unlikely to take the time to find it and post it for you, or to write the code for you, as you are obviously working on a school project. http://www.mathworks.com/matlabcentral/answers/6200-tutorial-how-to-ask-a-question-on-answers-and-get-a-fast-answer

[NAGA PAVAN KALYAN KUMAR TENTU]

Ok sir.thank you sir.

[NAGA PAVAN KALYAN KUMAR TENTU]

I = imread('cameraman.tif');
I = im2double(I);
T = dctmtx(8);
dct = @(block_struct) T * block_struct.data * T';
B = blockproc(I,[8 8],dct);
mask = [1   1   1   1   0   0   0   0
      1   1   1   0   0   0   0   0
      1   1   0   0   0   0   0   0
      1   0   0   0   0   0   0   0
      0   0   0   0   0   0   0   0
      0   0   0   0   0   0   0   0
      0   0   0   0   0   0   0   0
      0   0   0   0   0   0   0   0];
B2 = blockproc(B,[8 8],@(block_struct) mask .* block_struct.data);
symbols = unique(B2(:));
counts = hist(B2(:), symbols);
p = double(counts) ./ sum(counts);
[dict,avglen] = huffmandict(symbols,p); 
comp = huffmanenco(I,dict);

Sir there is error in above code in last command sir. sir could you help in fixing that error? Or Is that above code is for write for Huffman encoding in image compression sir.?

[Walter Roberson]

You are applying huffman dictionary to floating point numbers, and those are only going to be bit-for-bit identical mostly by coincidence.

You then try to do a huffman encoding of the image, instead of based upon a vector of B2 values.

... Are you sure you want to use floating point numbers as your symbols ?