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

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

Todays QR codes usually contain only address - nearly nobody uses them because its simpler and quicker just to google or store/remember it. The situation should change if they would look attractively and have much larger capacity - even just out of curiosity motivating to get closer to make a clear shot to find out what interesting contents it hides. Todays phones have about 8Mpixels, so a well designed QR codes could contain hundreds of kilobytes - a ring tone, an application, a wallpaper ... even a huge poster could by the way be a QR code - we could imagine a marketing campaign where you need to collect some of them to get a prize ...
Todays QR codes are industrial standard - it's time to adjust them to everyday life ... increasing capacity and improving visual aspect is a natural direction of evolution.

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?

update: fresh discussion http://www.thenakedscientists.com/forum/index.php?topic=46597

update: presentation http://dl.dropbox.com/u/12405967/qrsem.pdf

well the first thing you need to think about is price. How expensive are these going to be? most QR codes as you said are industrial standard mainly i guess because its cheaper to make them like that. You also need to be looking at your market a large percentage of people do not have phones with fancy cameras also the information on the code has to be interpreted by phones and most dont have huge processing power so the simpler you make QR codes the better. Another problem that may arise is color your image may have 40 different versions of blue in one pixel but how will your phone know how to order the colors?? Then there is your printer which is going to have to be expensive to accomodate for all the different versions of blue in your picture and also to not make mistakes in printing. There is some advantages that i can see though which is product traceability. Say if you worked for a clothing manufacturer, you sell expensive clothes but a large number of people sell fakes of your products. You could create QR codes based on a function and a database linked to the cashier at a retailer to say that handbag 2113etc has been sold. Then when a customer scans their QR code they would be able to tell if it was a fake or not they just scan the code and if it says this handbag was sold to h&m in Berlin 3 months ago then you know that the product is a fake and somebody has attempted to copy your designs etc. You would then be able to ask your customer where they purchased the item in the hopes of catching the copycats in the act.

The only requirement would be having a modern smartphone (with good optics and flash) - then you just get a free software, e.g. updates of current QR readers.
I disagree with "the simpler you make QR codes the better" - to make people just want to scan them, they have to be able to expect some interesting content - they need to have large capacity and should be visually attractive, making you intrigued, curious ...
Printing is also standard, the only difference here is that such nice looking high capacity codes should be rather better protected, like laminated or printed on plastic.

Yeah i am curious, i think it can be done. But you do need to be asking yourself about the costs of doing this. Also if you were to go off and make these what is to stop somebody else from making them cheaper than you or copying your software and taking a large percentage of your profits?? Also you have to be thinking about your customer base, you would largely be appealing to companies to invests large amounts of money so they have to be persuaded that the risks and costs associated with the production of these will be merited by the potential for profit.

The cost of the technology of customized high capacity QR codes is just to create new standards and update software - as for technology influencing the whole world, the cost is completely negligible.
I think you are referring to the costs of marketing businesses to adapt to it? They quickly adapted to current QR codes - the new generations will give them much more possibilities at cost of learning how to use them.

ps. here is a more developed discussion on this subject: Embedding grayscale halftone pictures in QR Codes - Dev Shed

I think Nilpo has a point. As for the images not looking like a QR code you could just maintain the squares on the corners that look like QR then people would get the point. Then you could make them look like logos and pretty soon QR codes could replace conventional logos

Leaving obvious redundancy is completely not a problem and e.g. can be gradually removed. For recognition issues, Lena above looks suspicious enough and pixels emerge when getting closer.
What is technically difficult is not using it, but I think it is also achievable.

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 [1211.1572] Embedding grayscale halftone pictures in QR Codes using Correction Trees ).
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.
For example to store picture like below using only a bit more bits than the number of fixed bits of the pattern (p_f bits/pixel, like 125B for the middle one):


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

Just create an image compression algorithm. once you have the algorithm and its easy to use who cares?? Most people dont wont to know how the program works onces it fast reliable , cheap and easy to use. Nobody cares if you have the best fastest program ever nobody cares they will want something that makes sense to them. That can easily be explained to investers and normal people that does its job every single time. Show your investors its a product that they can use themselves without any understanding of programming.

The only real direct applications I can see are nice looking 2D codes and it is a matter of large companies, standards etc. - I would gladly help if asked, but it's not for a solitary work.
The value is feeling these theoretical possibilities and be able to apply them if needed.
As a rare specie among engineers: theoretician, it's just nice and interesting problem for me - I don't feel a need to implement it, I'm good at simulations and analysis not at practical programing and honestly I should work on different problems now ... there are still so many nice ones waiting to analyze and understand ;D ...

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/glasses could be hidden in music you hear ...
...

There are already used some basic applications like to identify a printer, or watermarking a picture to identify digital camera (in a bit primitive way):
Printer steganography - Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Digital...arking#Cameras
for example printer steganography uses yellow dots (in most of color laser printers) to encode printer serial number. As this primitive technique requires additional color, it can be used only in color printers. It also looks simple to fake - just scan the dots from some printer, place them on your document, and it would seem that it was printed on that printer.
In methods based on Kuznetsov-Tsybakov information can be hidden in much more subtle way e.g. in dot positioning/grayness realization:
- no additional color required,
- virtually impossible to detect or fake without cryptographic key,
- muuuch higher information capacity...
For example imagine a printer with built in microphone - even if out of network and electromagnetically screened, it can still store information hidden in precise dot positioning of documents it prints ...

What other applications could you think of?

Is this anything new?
Form Meets Function: Extreme Makeover QR Code Edition | 360i Blog
http://mashable.com/2011/04/18/qr-code-design-tips/

Strange, indeed there are already some primitive methods to make QR codes prettier - by using fancy pixels, or modifying the pattern basing on included error correction.
I call the second way as "damaged ECC" approach and it turns out to be extremely ineffective (because the receiver can recover the used constrains - we unnecessarily attach them) - in capacity graphs they are the lowest ones, far from the optimum.
For example on page 8 of the presentation there are examples of used today looking-like-pictures codes - containing about 50 bits of message in 1681 pixels: about 0.03 bits/pixel ... while approachable theoretical limit for Lena-like codes above is 0.82 bits/pixel ...