Embedding grayscale halftone pictures in QR Codes - encoding information in freedom of grayness realization

[Duda Jarek]

What is this 512x512 picture?

 

 

Bad Quality Lena indeed, but the trick is that it's black&white - can be directly seen as length 512x512=32kB bit sequence.

It occurs that making bit sequence "looking like Lena" reduces the capacity only to about 0.822, what is about 26kB in this case - the visual aspect costs only about 6kB.

It has rather too high resolution for practical applications, but here are examples of lower resolution codes looking like a chosen black and white picture:

 

 

for example the central noisy code contains 800*3/4=600 bytes - making it look like the picture costs only 200 bytes.

Here is fresh paper about obtaining it (generalization of Kuznetsov and Tsybakov problem - for constrains known to the sender only): http://arxiv.org/abs/1211.1572

 

What do you think of replacing today QR codes with nicer looking and more visually descriptive ones?

What other applications could you think of for this new steganography for which two colors is finally enough?

[Duda Jarek]

I've recently realized that this method is extremely close to the base of lossy compression: rate distortion problem - they are kind of dual: while searching for the code, we just need to switch essential bits with the discarded ones. So the rate for rate distortion application is "1-rate" of the original one (last version of http://arxiv.org/abs/1211.1572 ).
For example to store distorted/halftone above plane pictures, we need correspondingly 1/8, 1/4 and 1/2 bits/pixel. Intuition is that while the bitmap requires e.g. 1 bit/pixel, such small part of bit stores the "visual aspect", while the rest can be used to store a message (but don't have to be). Correction Trees are perfect for such purposes - can cheaply work about 1% from the theoretical channel limit.

Additionally, there appears probably new(?) applications:
- extremely cheap storing of halftone pictures, like about 0.18 bits/pixel for Lena above (about 6kB),
- dual version of Kuznetsov and Tsybakov problem (gets out of standard nomenclature of rate distortion) - we want to send n bits, but such that only k<n of them are fixed by us - the receiver don't know which, the rest of bits can be random - it occurs it is enough to send a bit more than k bits.

Where could we use it - e.g. extremely cheap storing of halftone pictures?

 

ps. Some more devaloped discussion: http://forums.devshed.com/dev-shed-lounge-26/embedding-grayscale-halftone-pictures-in-qr-codes-933694.html

[Duda Jarek]

If someone is interested in this subject, I have recently created presentation with new pictures, explanations:

https://dl.dropboxusercontent.com/u/12405967/qrsem.pdf

Picture-like QR codes is only one of many new possibilities of these extensions of Kuznetsov-Tsybakov problem - when the receiver doesn't need to know the constrains (picture/music/noise characteristics/...), for example there are plenty of new steganograpic applications:
- if we would like to encode information in exchanging the least significant bits (LSB) of a picture, but (to be more discrete) would like to change only the least possible amount of bits and the receiver doesn't know the original picture,
- if we cannot just manipulate LSB because there is only e.g. 1bit/pixel, we can recreate local grayness by statistics of distribution like in the Lena-like codes above. We could also use more advances dithering methods: getting better picture quality, but at cost of reduced data capacity and algorithm will become more complex (probability for a pixel should depend on already chosen its neighbors). For example e.g. inkjet printers use just 3 colors of nearly identical dots - there are already hidden some basic informations like serial number there, but in a casually looking print we could hide really huge amount of information in precise dot positioning (would require a microscopic precision scanner to decode),
- if there is a device producing some noise, we could send information in faking this noise - Kuznetsov-Tsybakov would be required e.g. if the noise characteristics are varying in time,
- there are also new possibilities of hiding information in sound, for example to reduce EM noise and target only those e.g. in given public place, some information for your smartphone could be hidden in music you hear ...
...

What other applications could you think of?