Problem Solving

Lossless Encoding of Secret Image and Text into Carrier Images

Hiding a secret message in plain sight is the kind of thing that tickles my fancy in espionage. I used to hide my password in a detailed Ancient Roman naval map. Perhaps a silly idea in retrospect. When I first learned there was a way a hide a whole image inside another image, I was thrilled to find out how.

The method posterizes the secret image so it contains much fewer tones. Commonly there are 256 tonal levels per RGB channel. If posterized to 8 levels, then every 32 tonal levels will be flattened to 1. The method then takes the level numbers (0-7) and adds them to (or subtracts them from, in boundary cases) the RGB values of the carrier image. After that, the secret image is hidden inside the carrier image.

To recover the secret image at destination, the receiver needs a copy of the original carrier image. Comparing the copy with the encoded image will reveal the level numbers. Multiplying them by 32 restores the secret image. (It doesn't have to be 32, but simply 256 divided by posterization level.)

 My lucky encounter with a squirrel in Arizona desert. Posterized to 8 levels.

My lucky encounter with a squirrel in Arizona desert. Posterized to 8 levels.

For instance, to hide a secret pixel (RGB = 122, 242, 63) inside a carrier pixel, the secret pixel will first be posterized (RGB = 96, 224, 32 | Level = 3, 7, 1). The level number will be embedded in the carrier image pixel (RGB = 4, 143, 92), changing it to (RGB = 4+3, 143+7, 92+1). At the destination, comparing the original carrier pixel and the encoded carrier pixel will yield the difference (3, 7, 1), multiplying which by 32 will restore the posterized secret pixel (RGB = 96, 224, 32). There is no way to restore it to (RGB = 122, 242, 63).

This kind of encryption has a name: steganography. A key feature of steganography is that it not only encrypts the message, it also hides the existence of encryption.

But there are three drawbacks with the posterization method:

  1. It corrupts the secret image's quality drastically.
  2. The sender cannot use a new carrier image without pre-placing a destination copy.
  3. Depending on the posterization level and visual complexity of the carrier, sometimes a "ghost" of the secret image is vaguely visible on the encoded carrier. (Why is it visible: This method essentially overlays a low bit-depth image onto another image. It actually preserves the secret image's composition.)

Problem - Finding a Lossless, No-Destination-Copy, Invisible Solution:

Process:  To find the answer, the three requirements can be expanded to a list of necessary choices.

Lossless encryption means the colors of the secret image cannot be modified, and must recorded in their full tonal range (0-255).

Having no destination copy means that in the carrier image, information cannot be encoded as a difference to the original, because there is no way to find the original.

Invisibility means the encoding must disintegrate the composition of the secret image, and the color changes to the carrier image must be extremely limited.

Convergence of above necessities points to two core issues:

  1. How to hide a number of such a big range (0-255) in another set of numbers without changing them too much?
  2. When the decoding program looks at an encoded value, how can it know which part is the secret value and which part is the non-secret value?

The upside of having many requirements is that their intersection of possible solutions gets smaller and smaller.

For question 2, if the non-secret value can be anything between 0 and 255, there is no way to isolate the secret value. An idea came to me. What if the secret value is not actually encoded as a value, but as a numerical property, such as, being an odd number, ending with a 5, or being a prime number, etc?

In turn, this inspired a solution to question 1: write the secret value in binary form, then encode it using the true or false state of a numerical property to represent the 0 or 1.

It take 8 bits to represent each RGB value in binary form, thereby 24 bits for a whole pixel. If each carrier RGB value only encodes 1 bit, it will take 8 carrier pixels to encode 1 secret pixel. But we can halve that by having each carrier RGB value encode 2 bits.

Solution:  In every packet of 2 bits from a secret value, if the first bit is 0, ensure the encoded carrier value is divisible by 2; otherwise, ensure it is not. If the second bit is 0, ensure the same value is divisible by 3; otherwise, ensure it is not.

To decode the secret values, rebuild their binary expressions by checking the divisibilities of encoded carrier values in sequence.

 Flowchart of encoding process. A secret pixel is broken into 3 primary colors, each transformed into its binary form. Each packet of 2 bits of binary expression is encoded into 1 primary color of 1 carrier pixel.

Flowchart of encoding process. A secret pixel is broken into 3 primary colors, each transformed into its binary form. Each packet of 2 bits of binary expression is encoded into 1 primary color of 1 carrier pixel.

Alternative Solution:  Label the four possible combinations of every 2 bits (00, 01, 10, 11) from 0 to 3. First, floor the carrier value to the nearest multiple of 4, then add the label number on top of it. To decode, divide the encoded carrier value by 4 and use the remainder to identify the bit combination.

Results:

The two solutions are slightly different in approach but effectively the same.

It takes 4 carrier pixels to encode 1 secret pixel. To fully encode a secret image, it requires a carrier image with 4 times the pixel count (plus 4-6 pixels to record width and height).

For any original carrier value, the numerical tweak needed to meet any encoding combination is only between 0 to 3. The color changes are barely visible to the eye.

This method completely avoids the "ghost" image problem, because encoding no long explicitly represents tonal values nor retains any composition. Whereas in the old method, the encoded area on the carrier image is a direct match with the secret image, the new method encodes the width and height of secret image first, then exhausts the carrier pixels line by line.

It is also lossless, and it requires no destination copy to decode.

Text can be encoded as well using a similar method. In my case, I used a library of 64 characters, including English alphabets, numbers, common punctuation marks, and end-of-line/end-of-all signs. Since each carrier pixel can encode 6 bits, one pixel can encode one character.

 Original carrier image(1920 x 1080): blank.

Original carrier image(1920 x 1080): blank.

 Encoded carrier image (1920 x 1080): containing 50 copies of a 20-page college paper I wrote.

Encoded carrier image (1920 x 1080): containing 50 copies of a 20-page college paper I wrote.

As one additional benefit to lossless encoding, image and text encoding can be nested. You can hide a text inside an image and then hide that image inside another image.

 Original carrier image (3550 x 2360): blank.

Original carrier image (3550 x 2360): blank.

 Encoded carrier image (3550 x 2360): containing the squirrel image which contains a 1000-page paper.

Encoded carrier image (3550 x 2360): containing the squirrel image which contains a 1000-page paper.

Can this method be used to bundle texture maps too? I think that's an interesting question.

Mai Ao