Matlab Huffman code

This Matlab code generates a Huffman codebook for a specified set of symbol probabilities.

Copyright © 2010 Robert G. Maunder. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

68 Responses to “Matlab Huffman code”

  1. hugo Says:

    thank you very much

  2. saman Says:

    i need this realy.
    thx for help

  3. mahmoudawney Says:

    thank you very much.real i want this code.

  4. sandeepreddy Says:

    thank you very much sir

  5. neha Says:

    thnk you :)

  6. Michael Says:

    Thank you

  7. Liangjun Says:

    Thanks for your help

  8. Unknown Says:

    Thank you for the code. It’s awesome!

  9. Pooja shah Says:

    Can you plz tell me how to write Huffman code in matlab with user entering the probabilities and asking the user to enter the base for getting the huffman code.

  10. Rob Says:

    Hi Pooja Shah,

    The Matlab code that you can download from this page will generate a Huffman codebook for you, when you provide it with the symbol probabilities. Here is some code a Huffman encoder and decoder…
    http://users.ecs.soton.ac.uk/rm/wp-content/HuffmanEncoder.m
    http://users.ecs.soton.ac.uk/rm/wp-content/HuffmanDecoder.m

    Take care, Rob.

  11. divya Says:

    repeat accumulate code i need

  12. Rajesh N Says:

    Easy to understand. Very useful. Optimum coding

  13. Andrew Says:

    Hi Rob,

    Your program gives out Huffman Codes which are of a minimum length 2 bits for the highest probability. But the highest probability symbol should have a binary Huffman Code of only 1 bit. Could you please verify this?

  14. Andrew Says:

    Please ignore my previous question. I did not know the Huffman Code\’s algorithm properly. The code is perfect.

  15. kiyeob Says:

    I used this to make an dictionary but it failed the prefix free condition for long text files though it works for short text file.

  16. kiyeob Says:

    Actually I found it is not…I draw a tree from the codewords and found it is prefix-free code but somehow matlab recognizes this as prefix code…
    Thanks,

  17. Rob Says:

    Hi Kiyeob,

    I hope you got this working - I can’t tell from your messages if you solved the problem or not…

    Take care, Rob.

  18. tiha Says:

    please i need a huffman code ^^

  19. Rob Says:

    Hello Tiha,

    You can download the code from…
    http://users.ecs.soton.ac.uk/rm/wp-content/huffman.m

    Take care, Rob.

  20. liberte Says:

    i was no to use matlab very well and traduces all the code in telecommunication. thank you for all you are doing to make the technologies growing

  21. liberte Says:

    please can i have huffman code that return (valeur moyenne, entrepie et l\’efficacité ) and binary code, and the user will enter any probability that he need , the probability can be above one . thank you

  22. liberte Says:

    thank you rob for all you are doing for us

  23. Rob Says:

    Hello Liberte,

    You can download my Matlab tools for Huffman codes from…
    http://www.edshare.soton.ac.uk/5293/

    Take care, Rob.

  24. manju singh Says:

    sir plz give me idea of how to store Huffman encoded bits for image in matlab

  25. Rob Says:

    Hi Manju,

    It is easy to store these bits in Matlab by using the ’save’ command.

    Take care, Rob.

  26. abhikalp sharma Says:

    Hello Sir,

    sir please provide me matlab code for huffman image compression with single bit error.

  27. Rob Says:

    Hello Abhikalp,

    I’m afraid that I don’t have any Matlab code for image compression, but it should be possible to apply my Huffman code to this application.

    Take care, Rob.

  28. manju singh Says:

    Thankyou sir,
    Sir I used the command huff_code= huffmanenco(sig,dict) to encode the signal in Huffman jpeg image compression. Sir now I want to calculate Huffman binary file what will be the procedure for this. And one more thing sir will reconstructed image size be the same as compressed image size or it will be different?

  29. manju singh Says:

    Thankyou sir,
    Sir I used the command huff_code= huffmanenco(sig,dict) to encode the signal in Huffman jpeg image compression. Sir now I want to calculate Huffman binary file what will be the procedure for this. And one more thing sir will reconstructed image size be the same as compressed image size or it will be different?

  30. Rob Says:

    Hello Manju,

    I suspect that you can do this by taking eight bits at a time and converting to a decimal number in the range 0 to 255, then using fwrite to write this into a binary file. If you are applying Huffman coding to a file that has already been jpeg encoded, then I would not expect you to achieve any compression. However, I suspect that the resultant binary file would have a different file size to the original jpeg file, albeit only slightly.

    Take care, Rob.

  31. manju singh Says:

    Thankyou sir,
    Sir I applied jpeg compression using Huffman on a image that is in bmp format not in jpeg. Sir I want to know that compressed image or reconstructed image will be same or different.

  32. Rob Says:

    Hi Manju,

    JPEG compression is lossy, so the reconstructed image will be different to the original image.

    Take care, Rob.

  33. abhikalp sharma Says:

    hello sir,
    Sir I want to introduce error in huffman binary file and then decoded this binary file.what will be the procedure for this?Is differnt decoding technique used for this error phenomena or same as we use for huffman without error..

  34. Rob Says:

    Hi Abhikalp,

    If errors are introduced into the Huffman-encoded bit sequence, the decoding procedure is the same, although there is one thing that you need to think about.

    Suppose that we have the codebook 1, 00, 010, 011 and we have the transmitted bit sequence 0001110101001010. If the tenth bit has a transmission error then the received bit sequence will be 0001110100001010. This decodes to the following sequence of codewords, 00, 011, 1, 010, 00, 010, 1, 0. However, that final 0 does not give a complete codeword - you need to write your Huffman decoder so that it doesn’t crash when it encounters this problem. The simple thing you can do is just have the Huffman decoder ignore that final 0 and output only the 7 complete codewords that precede it.

    Take care, Rob.

  35. abhikalp sharma Says:

    hello sir,
    sir plz tell me in JPEG image compression there is a command i.e. y = blkproc(x, [8 8], ‘P1 * x * P2′, t, t’); here what is the P1 * x * P2′..

  36. Rob Says:

    Hello Abhikalp,

    It seems to me that you are using the following version of the blkproc command…
    B = blkproc(A,[m n],fun,P1,P2)

    You can read more about this command at…
    https://nf.nci.org.au/facilities/software/Matlab/toolbox/images/blkproc.html

    I suspect that ‘P1 * x * P2′ will return the value of t*x*t’, where x is each 8×8 sub-block of A and t’ is the transpose of whatever t is.

    Take care, Rob.

  37. abhikalp sharma Says:

    thank you sir,
    sir i am doing jpeg image compression using huffman coding here is my code
    clc
    clear all
    I=imread(\’C:\\Users\\my-computer\\Pictures\\newlena.bmp\’)

    [row col]=size(I)

    %Quantization matrix for quality factor Q=10
    Q= [80 60 50 80 120 200 255 255;
    55 60 70 95 130 255 255 255 ;
    70 65 80 120 200 255 255 255 ;
    70 85 110 145 255 255 255 255 ;
    90 110 185 255 255 255 255 255 ;
    120 175 255 255 255 255 255 255 ;
    245 255 255 255 255 255 255 255 ;
    255 255 255 255 255 255 255 255 ];

    % dct transform
    dct=dctmtx(8)
    idct=(dct\’);
    Im=double(I);
    for i=1:8:row
    for j=1:8:col
    b=Im(i:i+7,j:j+7);
    temp_b1=dct*b*idct;
    Im_dctq(i:i+7,j:j+7)=round(temp_b1./Q);
    end
    end

    % Huffman coding

    temp=1
    temp2=0
    pixel_count = row*col;
    symbol = reshape(Im_dctq,[1,row*col]);

    symbol1 = unique(symbol)
    len = length(symbol1)
    for i = 1:len
    k = Im_dctq==symbol1(i);
    count(temp) = sum(k(:));
    prob_pix(temp) = double(count(temp)/pixel_count)
    temp2 = temp2 + prob_pix(temp);
    prob_cum(temp) = temp2;
    temp = temp+1
    end
    [dict,avg_len] = huffmandict(symbol1,prob_pix).
    sir is this procedure right??I m getting average length of the huffmancode less than 2.I think which is not correct it can\’t be so much less.Sir plz guide me

  38. Rob Says:

    Hi Abhikalp,

    Your code seems reasonable to me. I suspect that the vast majority of your symbols have a value of 0, which is why your average codeword length is so short. If your source image has 8 bits per pixel and your compression is reducing this to less than 2 bits per pixel, then your compression ratio is around 4, which seems reasonable to me.

    Take care, Rob.

  39. Dan Says:

    Very good stuff, Keep up the good job please.

  40. parul Says:

    hello sir….. m doing image compression using huffman coding sir plz tell me how to calculate probablility of each pixel..

    %clearing all variableas and screen
    clear all;
    close all;
    clc;

    %Reading image
    a=imread(’ab.jpg’);
    figure,imshow(a)

    %converting an image to grayscale
    I=rgb2gray(a);
    imshow(I);

    %size of the image
    [m,n]=size(I);
    Totalcount=m*n;

    %variables using to find the probability
    cnt=1;
    sigma=0;

    %computing the cumulative probability.
    for i=0:255
    k=I==i;
    count(cnt)=sum(k(:))

    %pro array is having the probabilities
    pro(cnt)=count(cnt)/Totalcount;
    sigma=sigma+pro(cnt);
    cumpro(cnt)=sigma;
    cnt=cnt+1;
    end;

    %Symbols for an image
    symbols = [0:255];

    %Huffman code Dictionary
    dict = huffmandict(symbols,pro);

    %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
    %converting image from grayscale to rgb
    [deco, map] = gray2ind(back,256);
    RGB = ind2rgb(deco,map);
    imwrite(RGB,’pa.JPG’);

    this is a code for image compression bt it is not working properly…this code provide output a gray image instead of color…sir plzzz check it…

  41. abhikalp sharma Says:

    hello sir,
    thanks for previous help..
    sir now i m doing jpeg image compression using huffman coding with single bit error.But sir from this code i m note getting correct picture.Final picture should be half part or less part decoded n rest should be the gray or black.Sir in my code with single bit error ,another problem is the size of input signal and huffman decoded signal is not same.here is my code please check this and provide me suitable correction…
    clc
    clear all
    I=imread(’C:\Users\Manju-Sharma\Pictures\aerial.tiff’)

    [row col]=size(I)
    %[row col]=size(Im1)
    %Qunatization matrix for chrominance
    %Q =[ 17 18 24 47 99 99 99 99;
    %18 21 26 66 99 99 99 99;
    %24 26 56 99 99 99 99 99;
    %47 66 99 99 99 99 99 99;
    %99 99 99 99 99 99 99 99;
    %99 99 99 99 99 99 99 99;
    %99 99 99 99 99 99 99 99;
    %99 99 99 99 99 99 99 99];
    %quantization matrix for quality factor Q=50
    Q= [ 16 11 10 16 24 40 51 61;
    12 12 14 19 26 58 60 55;
    14 13 16 24 40 57 69 56;
    14 17 22 29 51 87 80 62;
    18 22 37 56 68 109 103 77;
    24 35 55 64 81 104 113 92;
    49 64 78 87 103 121 120 101;
    72 92 95 98 112 100 103 99];
    %Quantization matrix for quality factor Q=10
    %Q= [80 60 50 80 120 200 255 255;
    % 55 60 70 95 130 255 255 255 ;
    % 70 65 80 120 200 255 255 255 ;
    % 70 85 110 145 255 255 255 255 ;
    %90 110 185 255 255 255 255 255 ;
    %120 175 255 255 255 255 255 255 ;
    %245 255 255 255 255 255 255 255 ;
    %255 255 255 255 255 255 255 255 ];

    % dct transform
    dct=dctmtx(8)
    idct=(dct’);
    Im=(double(I))-128;
    for i=1:8:row
    for j=1:8:col
    b=Im(i:i+7,j:j+7);
    temp_b1=dct*b*idct;
    Im_dctq(i:i+7,j:j+7)=temp_b1./Q;
    end
    end

    % Huffman
    % coding—————————————————————-
    Im_dctq=round(Im_dctq)
    temp=1
    temp2=0
    pixel_count = row*col;
    symbol = reshape(Im_dctq,[1,row*col]);

    symbol1 = unique(symbol)
    len = length(symbol1)
    for i = 1:len
    k = Im_dctq==symbol1(i)
    count(temp) = sum(k(:));
    prob_pix(temp) = count(temp)/pixel_count
    temp2 = temp2 + prob_pix(temp);
    prob_cum(temp) = temp2;
    temp = temp+1
    end

    [dict,huff_len] = huffmandict(symbol1,prob_pix);

    temp = 1;
    for i= 1:row
    for j = 1:col
    Im_huff(temp) = Im_dctq(i,j);
    temp = temp+1;
    end
    end

    huff_code = huffmanenco(Im_huff,dict);

    s=[huff_code(6181)]
    s=[huff_code(6181)]
    s=xor(1,s)
    huff_code(6181) = s;

    huff_decode=huffmandeco(huff_code,dict);
    Means the size of Im_huff and size of huffmandeco is not same…
    sir plzzzzzzzzz provide be correct way…

  42. abhikalp sharma Says:

    I insert error in the 6181 position or it can be another.Sir for inserting random error what should I do???

  43. abhikalp sharma Says:

    hello sir,
    sir after introducing single bit in the encoded bit stream as discussed above what changes should I do in huffman decoder so that i can get correct result.here is the code for huffman decoding

    function deco = huffmandeco(comp, dict)

    % Error checking ——————

    msg=nargchk(2,2, nargin);
    if ( msg )
    error(\’comm:huffmandeco:InputArgumentCount\’, msg)
    end

    [m,n] = size(comp);
    if ( m ~= 1 && n ~= 1)
    error(\’comm:huffmandeco:VectorInputSignal\’, \’The input signal must be a vector.\’);
    end

    checkDictValidity(dict);

    if ( strcmp(class(comp), \’double\’) == 0 )
    error(\’comm:huffmandeco:InvalidCodeType\’, …
    \’The encoded signal has to be a vector of type double.\’)
    end

    % End of error checking ———————-

    % isSigNon Numeric is used to later convert the decoded signal from cell
    % array format to a double vector.
    isSigNonNumeric = max(cellfun(\’isclass\’, {dict{:,1}}, \’char\’) );

    deco = {};

    i = 1;
    while(i <= length(comp))
    tempcode = comp(i);
    found_code = is_a_valid_code(tempcode, dict);
    while(isempty(found_code) && i < length(comp))
    i = i+1;
    tempcode = [tempcode, comp(i)];
    found_code = is_a_valid_code(tempcode, dict);
    end
    if( i == length(comp) && isempty(found_code) )
    error(\’comm:huffmanenco:CodeNotFound\’, …
    \’The encoded signal contains a code which is not present in the dictionary.\’);
    end
    deco{end+1} = found_code;
    i=i+1;
    end

    if( n == 1 ) % if input was a column vector
    deco = deco\’; % the decoded output should also be a column vector
    end

    if ( ~isSigNonNumeric )
    decoMat = zeros(size(deco));
    decoMat = feval(class(dict{1,1}), decoMat); % to support single precision
    for i = 1 : length(decoMat)
    decoMat(i) = deco{i};
    end
    deco = decoMat;
    end

    %————————————————————————–
    % This functions does a reverse lookup for a signal. This function will
    % compare the code with the entries in the codebook and return the signal
    % if there is a match
    function found_code = is_a_valid_code(code, dict)
    found_code = [];
    m = size(dict);
    for i=1:m(1)
    if ( isequal(code, dict{i,2}) )
    found_code = dict{i,1};
    return;
    end
    end

  44. Shashi Says:

    Hi sir, I wanted to do a Project on Huffman Coding in Image Processing where in I need to compress the original .tiff or .jpg image file. What do you suggest in order to start it.?

  45. Rob Says:

    Hi Parul,

    It seems to me that your ‘pro’ variable is giving you the probabilities that you need to design your Huffman code.

    Take care, Rob.

  46. Rob Says:

    Hi abhikalp,

    As you have found, a single bit error can cause the number of received symbols to become different to the number of transmitted symbols. This is a problem that you should expect and that you should design a solution for. It is not indicative of a bug in your code.

    To insert the error in a random position, you can use something like

    random_number = randi(length(bit_vector);
    bit_vector(random_number) = ~bit_vector(random_number);

    You can’t expect to get the correct decoding result when there are bit errors in your Huffman-encoded bit vector. The Huffman code is unable to detect and correct these errors.

    Take care, Rob.

  47. Rob Says:

    Hi Shashi,

    I would advise you to look at what Abhikalp and Parul are doing here.

    Take care, Rob.

  48. parul Says:

    Thanku sir…..but this code outputs the compressed gray image….i want RGB image….sir plz tell wht is the error…???

  49. Rob Says:

    Hi Parul,

    This is because you are using the rgb2gray function to throw away the colour information. Normally, colour image compression is achieved by converting to the YUV format and then encoding each of the Y, U and V channels separately. Often, more compression is applied to the U and V channels because the human eye is less sensitive to these.

    Take care, Rob.

  50. parul Says:

    thanku sir…..
    i found a code for rgb to YUV image conversion..is this code is useful for my problem???….sir plzz suggest me….
    RGB = imread(\’life.jpg\’);
    R = RGB(:,:,1);
    G = RGB(:,:,2);
    B = RGB(:,:,3);
    Y = 0.299 * R + 0.587 * G + 0.114 * B;
    U = -0.14713 * R - 0.28886 * G + 0.436 * B;
    V = 0.615 * R - 0.51499 * G - 0.10001 * B;
    YUV = cat(3,Y,U,V);
    imshow(YUV);

  51. blaze Says:

    Hello Sir, do you have a code for huffman decoder without using the built in function in matlab? thank you

  52. Rob Says:

    Hi Parul,

    That looks right to me.

    Take care, Rob.

  53. Rob Says:

    Hi Blaze,

    You can download my Huffman decoder from…
    http://www.edshare.soton.ac.uk/5293/

    Take care, Rob.

  54. parul Says:

    thanku sir….bt sir i hv used imwrite funcn bt still my compressed image is not saved.?????plz help me…my code is not working

  55. Rob Says:

    Hello Parul,

    I’m afraid that I haven’t used imwrite before, so I can’t think what might be wrong with your code.

    Take care, Rob.

  56. parul Says:

    thanku sir….Now m done with imwrite funcn and i hv save my compressed image…bt sitll there is a problm with dis code again give gray compressed image…plz help me

  57. Rob Says:

    Hi Parul,

    I’m very sorry but I don’t have enough experience with image compression in Matlab to be able to suggest where you might be going wrong.

    Take care, Rob.

  58. abhikalp sharma Says:

    Hello sir,
    Sir can u tell me what will be generator matrix for (13,5,3) fixed length code

  59. Anusha Says:

    hello sir,iam doing my project in video processing i want code how to generate codebook using kmeans

  60. Rob Says:

    Hi Abhikalp,

    I’m afraid that I don’t have any generator matrices for block codes, so I can’t help you with this.

    Take care, Rob.

  61. Rob Says:

    Hello Anusha,

    I assume that you want to design a Max-Lloyd quantiser using the kmeans algorithm. You can do this using

    [~, quantisation_levels] = kmeans(samples_from_the_source, number_of_quantisation_levels);

    Take care, Rob.

  62. Anusha Says:

    hi sir thaq fr ur ans….sir how to get training frames from a video

  63. Anusha Says:

    or a block

  64. Rob Says:

    Hi Anusha,

    I would suggest finding a selection of standard video sequences (such as those used by the Video Quality Expert Group) and using them for training.

    Take care, Rob.

  65. lukman Says:

    Hello Sir,
    I’m bit confused about huffman tree which has generated. How do I store the huffman tree for decompresn another time ?

  66. manju Says:

    I=imread(\’C:\\Users\\my-computer\\Pictures\\newlena.bmp\’)

    [row col]=size(I)

    %Quantization matrix for quality factor Q=10
    Q= [80 60 50 80 120 200 255 255;
    55 60 70 95 130 255 255 255 ;
    70 65 80 120 200 255 255 255 ;
    70 85 110 145 255 255 255 255 ;
    90 110 185 255 255 255 255 255 ;
    120 175 255 255 255 255 255 255 ;
    245 255 255 255 255 255 255 255 ;
    255 255 255 255 255 255 255 255 ];

    % dct transform
    dct=dctmtx(8)
    idct=(dct\’);
    Im=double(I);
    for i=1:8:row
    for j=1:8:col
    b=Im(i:i+7,j:j+7);
    temp_b1=dct*b*idct;
    Im_dctq(i:i+7,j:j+7)=round(temp_b1./Q);
    end
    end

    % Huffman coding

    temp=1
    temp2=0
    pixel_count = row*col;
    symbol = reshape(Im_dctq,[1,row*col]);

    symbol1 = unique(symbol)
    len = length(symbol1)
    for i = 1:len
    k = Im_dctq==symbol1(i);
    count(temp) = sum(k(:));
    prob_pix(temp) = double(count(temp)/pixel_count)
    temp2 = temp2 + prob_pix(temp);
    prob_cum(temp) = temp2;
    temp = temp+1
    end
    [dict,avg_len] = huffmandict(symbol1,prob_pix).
    temp = 1;
    for i= 1:row
    for j = 1:col
    Im_huff(temp) = Im_dctq(i,j);
    temp = temp+1;
    end
    end

    huff_code = huffmanenco(Im_huff,dict)

    Hello sir,
    Sir in JPEG image compression is compressed size of image is size of binary file after huffmanenco??and sir in this code please tell me the size format of binary file(output of huffmanenco) is this in bit form or in byte form??

  67. Rob Says:

    Hi Lukman,

    The transmitter and receiver will both need to have knowledge of the Huffman codebook (or equivalently, the Huffman tree) so that they can work together. In practice, this knowledge could be hard-coded into the transmitter and receiver, preventing it from ever changing. Alternatively, the transmitter could somehow transmit the codebook to the receiver, before using it.

    Take care, Rob.

  68. Rob Says:

    Hello Manju,

    If the encoder is creating a binary file, then yes - the compressed image size will be equal to the file size. I’m not sure what you mean by bit form or byte form - any binary file can be written or read one bit at a time or one byte at a time - binary files are not bit or byte, they are both.

    Take care, Rob.

Leave a Reply

Security Code: