how to code max & min values in "Huffman coding" ?

Actually it's my first time using Matlab &I'm trying to compress Image by Huffman coding without using inbuilt function so any help will be appreciated.

brief of Huffman :

1. I had an image of 0:255 intensities(gray scale), which means that we have 256 probabilities
2. I ordered them in descending order.
3. then sum the values of the lowest 2 probabilities & order it again in descending order with the rest of the probabilities.
4. I made node for each step.
5. until we had only 2 probabilities.
6. then gave the maximum value (0) code & the minimum value (1) code

My question is:

I know how to detect the maximum & minimum value but I don't know how to gave it the code (0 or 1)& how to store it ??

Also I want to know if there is any mistake in the code

My code till now :

clc;
clear all;
close all;
x=imread('Ducks.jpg');
figure ,imshow(x);
title('Original')
NewDucks=rgb2gray(x);
figure ,imshow(NewDucks);
title('Gray');
count=imhist(NewDucks);       %calculate the histogram of the image
pdf = count / numel(NewDucks);      %calculate the probability density funcation
plot (pdf);
pdf= pdf(:);         % arrange the values of pdf in descending order
k=length(pdf);
for k=1:256
    if numel(k)> 2        %if length(pdf)> 2 please do this operation
        pdf= -1*sort(-pdf)             % sort pdf in descending order
        m=min (k)                      % find the minimum value in the pdf 
        out = min(setdiff(pdf(:),min(pdf(:))))     % find the second minimum value 
        out = out+m;                 %sum the 2 minimum values (the lowest 2 probabilites)
        pdf(end+1) = out               % adding the summation element to the pdf vector
        pdf= -1*sort(-pdf)             %sort the vector after adding the new element
        pdf(i)=pdf(length(pdf))        %will make nodes to coding it back
        i=i+1
        z=pdf(i)
        if numel(z)=2
            M= max (z)
      end
end

I stopped at this point ?!

I will appreciate any help

thanks,

Answer 1

[Walter Roberson]

As you go through the tree you are creating, use 0 as the prefix for the subtree that has the lower probability, and 1 for the subtree that has the higher probability. For example if you developed the subtree {{'A', {'B', 'C}}, 'D'} then the left subtree is {'A', {'B', 'C'}} and would be assigned the prefix 0. Within that 0 prefix encompassing {'A', {'B', 'C'}} the left subtree would get the prefix 0, and that subtree is for 'A' -- so 'A' is associated with [0 0], being the left subtree of a left subtree. {'B', 'C'} would be associated with the local prefix 1, which would go after the prefix 0 from its parent, so you are looking at [0 1] {'B', 'C'} . The 'B' is the left of it so it gets 0 and the 'C' is the right so it gets 1, which together gives you [0 1 0] for 'B' and [0 1 1] for 'C' . Having finished the subtrees on the left you are back to the parent to the right and find that 1 should be associated with 'D' . This is the end of your subtrees, and you now have overall

 [0 0] - 'A'
 [0 1 0] - 'B'
 [0 1 1] - 'C'
 [1] - 'D'

An obvious way to build these is by recursion.

Once you have the code for each symbol, then when you go through your source and find a particular symbol, you look up its associated vector of values and put them at the end of a list you are building. After each append, you look to see if you have accumulated at least 8 values in the list, and if you have then you turn the first 8 of those values into an unsigned 8 bit integer and "emit" that (store it in memory, write it to a file, whatever is appropriate) and remove the 8 values from your list. At the very end, you will to append the code for end of file, which is an extra symbol you should have added to the list with very low probability (yes, if you had 256 original values you should be building your tree for 257 original values, the 257'th being EndOfFile.) If you still have a few bits in your buffer, append enough 0 to get a buffer of 8, convert that buffer, emit it.

Whether you use 0 for the higher probability branch or use 1 for the higher probability branch is not specified by Huffman coding, and does not matter. The decoding needs a copy of the symbol table, and the symbol table is going to be in terms of lists of specific bit values to compare against, so the decoding is exactly the same whether 0 was used for low probability or for high probability.