How can I encode a message into an image using Huffmanenco?

I am trying to encode a message into an image, and then decode that image to reveal the message.

message = 'I do not enjoy MATLAB';

ascii_message = double(message);

x = 32;
letter_freq = [];
key = [];

%Finding the letter frequency in the message
while x >= 32 && x <= 126
    count = length(find(ascii_message(1,:) == x));
    letter_freq(length(letter_freq) + 1) = count;
    character = char(x);
    key(length(key) + 1) = character;
    x = x + 1;

end

%For loop calculating probability vector from letter frequency

probability = [];
symbol = [];
ascii_list = [32:126];
count = 0;
for i = 1:length(letter_freq)
    if letter_freq(i) > 0
        prob = letter_freq(i) / length(message);
        count = count + 1;
        symbol(count) = ascii_list(i);
        probability(count) = prob;
    end

end



%Creating the histogram
for i = 1:length(message)
    c_arr{i} = char(message(i));
end

categ_arr = categorical(c_arr);

histogram(categ_arr)

%Creation of the huffman dictionary
[dict,avglen] = huffmandict(symbol,probability)

image = imread('color.jpg');
vecImg = reshape(image,1,[]);
Data = vecImg;

comp=huffmanenco(Data,dict)

I think it is pretty clear from my code that I don't know exactly what I'm doing. The current error I am getting is "The Huffman dictionary provided does not have the codes for all the input signals."

Answer 1

[Walter Roberson]

[dict,avglen] = huffmandict(symbol,probability)

Up to there looks acceptable. A bit inefficient in places, but work-able.

image = imread('color.jpg');
vecImg = reshape(image,1,[]);
Data = vecImg;

Those lines are okay as far as they go, in isolation.

comp=huffmanenco(Data,dict)

There you are asking to do a huffman encoding of the data in the image. The data in the image will have integer values between 0 and 255, but the dictionary you constructed is only defined for the unique letters in your message 'I do not enjoy MATLAB' . For example pure white in an image has intensity 255, 255, 255, but 255 is not an encoding of any of the characters 'I do not enjoy MATLAB' so your dictionary would not have any notion of the probability to use for that symbol.

[Walter Roberson]

The approach to encoding a message into an image goes like follows:

1. Locate the text message to be encoded -- read it from a file, ask the user for it, get it from a parameter, whatever is appropriate for your situation
2. convert the message to a stream of bits. This could plausibly involve creating a huffman dictionary from it and using the dictionary to encode message as a stream of bits. If you do use huffman encoding, it is recommended that you add one extra symbol that is the "end of message" symbol: during the decoding stage when you see that symbol come up in decoding you will know that the rest of the decoding buffer should be ignored.
3. convert the image to bits as well (not necessarily strictly necessary, but it makes it easier to explain the process.) This stream of bits is not processed through the huffman dictionary.
4. Now, "hide" the message bits somewhere inside the image bits. You can choose any deterministic hiding order that can fit the complete message bits somewhere in the image bits. For example you might chose to insert one message bit every 40 image bits (every 5 bytes). Or you might choose to insert the message bits at the prime-numbered image bits. Or you might choose to use a Linear Congruential random number generator to scatter the message bits around the image hopping all over. Choose some order that you can reproduce during decoding. An order in which an algorithm calculates where the next bit will be would tend to be more compact to implement than (for example) an order chosen by processing the lyrics to some song, but if you want to use the lyrics to AC/DC's All Screwed Up to determine where to put the bits, then that is perfectly acceptable.
5. To hide message bits in the image bits, just set an image bit to be the corresponding message bit, throwing away the information about what the existing image bit was.
6. Once all of the message bits have been stored, convert the modified image bits back into an image array the same size as the original image.
7. Now save the new image array as an image file. If you want to be able to save as a standard .jpg file then you would need to take more care in how you stored the message bits, as standard JPEG is a lossy image compression system that discards information sometimes. There are ways to make embedding message bits more resiliant to the loss that JPEG causes.
8. For decoding, read in the modified image file, and convert it to bits.
9. Now using the same hiding order that you used above, pull out selected bits from the modified image array that you pulled in from the file. If you used an algorithm to determine the locations to store at, then unless you used a process that had a fixed number of storage locations (which would be a problem for larger messages) then you might end up with more message bits than you actually stored, with the remaining bits being nonsense.
10. Now use huffman dictionary to decode that message bits. Examine the decoded message, and at the point you see the end-of-message symbol, throw it away and everything else in the message.

Where are good places to store the message bits in the image bits? Well, ideally you would like to store the message bits ways that will hardly be noticable to people looking at the modified image. That tends to mean storing the message bits as the "least significant bit" of pixels... but that is not the only possibility.

[Roger]

Thank you for the response. So if there are codes that do not exist in my dictionary, what would I add to the dictionary to fill in the missing spots? I plan on simply using the huffmanenco() and huffmandeco() functions for this.

[Walter Roberson]

Sigh. Since you seem determined to do the completely wrong thing, I will show you how to do completely the wrong thing so you can test it to determine that in fact it doesn't help you at all.

message = 'I do not enjoy MATLAB';
image_filename = 'flamingos.jpg';

end_of_message = 256;
ascii_message = [double(message), end_of_message];

letter_freq = ones(end_of_message + 1,1);
key = char(zeros(end_of_message + 1, 1));

key = [];
%Finding the letter frequency in the message
for x = 0 : end_of_message
    count = length(find(ascii_message(1,:) == x));
    letter_freq(x + 1) = letter_freq(x+1) + count;
    character = char(x);
    key(x+1) = character;
end

total_count = sum(letter_freq);

%For loop calculating probability vector from letter frequency
probability = [];
symbol = [];
ascii_list = 0:end_of_message;
count = 0;
for i = 1:length(letter_freq)
    if letter_freq(i) > 0
        prob = letter_freq(i) / total_count;
        count = count + 1;
        symbol(count) = ascii_list(i);
        probability(count) = prob;
    end
end


%Creating the histogram
for i = 1:length(message)
    c_arr{i} = char(message(i));
end
categ_arr = categorical(c_arr);
histogram(categ_arr)

%Creation of the huffman dictionary
[dict,avglen] = huffmandict(symbol,probability);

image = imread(image_filename);
vecImg = reshape(image,1,[]);
Data = [vecImg, end_of_message];
comp=huffmanenco(Data,dict);

The dictionary was constructed with missing keys filled in. All missing entries have a count of 1 (because probabilities must be positive for huffman encoding purposes); the entries that actually occur have 1 plus the actual count. The end-of-message marker was added to the message, and gets included in the huffman encoding.

The dictionary is now something that can be used to huffman encode the image itself.

Now what?

How does this help you to hide a message in the image? When you do the huffman decoding of comp using that dictionary, then what you get back will be exactly the same as the vecImg (except with end_of_message added to it so you know when to stop decoding.) The only way you would even be able to tell you had not done a plain huffman encoding is by analysis of the bit pattern to observe that some of the encoding symbol lengths are a different size than you would expect if the probabilities were equal... and you would not be able to deduce the message (at most you would be able to deduce the unique letters involved in the message, and possibly their relative probabilities.) You would be lucky, with a bunch of analysis, to be able to more or less get back the Scrablle Tile version of the input message.

This is not going to be usable.

To be usable you need to use a process similar to what I discussed, in which you apply the huffman encoding to the message not to the image, giving you a stream of bits that you have to somehow hide in the file.