Naked Science Forum
Non Life Sciences => Geek Speak => Topic started by: Jarek Duda on 11/01/2013 16:47:54
-
There is a nontrivial possibility of creating QR-like codes resembling chosen grayscale picture: such that grayscale of picture's pixel defines probability of using "1"in the corresponding position of the code.
Here are examples of 512x512 Lena-like codes: the left one would contain 32kB without constrains, while making it look like Lena costs about capacity 20% informational capacity reduction (about 26kB remains to store information, 3 times more for the color one):
(https://www.thenakedscientists.com/forum/proxy.php?request=http%3A%2F%2Fdl.dropbox.com%2Fu%2F12405967%2Flen.gif&hash=e994feeda9499ae5510e8004648dbc75)
Such large resolutions might be technically difficult to operate on, so here are smaller resolution simpler examples:
(https://www.thenakedscientists.com/forum/proxy.php?request=http%3A%2F%2Fdl.dropbox.com%2Fu%2F12405967%2Fex.gif&hash=451c441c1060ad0f9d4fc72afaf7b83b)
For example the central one may contain about 3/4*800B=600B of information.
Obtaining such codes is generalized Kuznetsov and Tsybakov problem: sending information with constrains known only to the sender. In the original problem there are used strong constrains: some bits are fixed. Here we need to take it to weaker: statistical constrains - here is a paper about it: http://arxiv.org/abs/1211.1572
What do you think about such natural step of evolution of QR-like codes - to make them more informative and visually attractive?
They would rather require larger resolutions and so much larger capacities - what new applications would you think of? ... like picture of a singer containing music sample, OS logo containing small app, some interactive brochure about given place/item in store/museum ...
How to use them? ... like perforated sheets to cover a flat lamp - cheap and well visible in darkness advertisement and QR code simultaneously ...
What other advances of QR-like codes would you expect?
How to stimulate introducing such better suited to human world codes?
-
...They would rather require larger resolutions and so much larger capacities - How to use them? ...
As the detail in the "code" increases the optical margin of error to read it successfully decreases, e.g. try taking a picture of an entire page of a newspaper with a phone camera (https://itunes.apple.com/gb/app/qr-reader-for-iphone/id368494609?mt=8) and see how much is readable in the photo.
For the same size as current QR codes (typically postage-stamp) people would need cameras similar to slide-copiers to obtain an image of the Lena-like code with sufficient resolution ...
[ Invalid Attachment ]
Note: 35mm slide plane orthogonal to the camera "film" plane so its image is kept in focus, as the depth of field (https://en.wikipedia.org/wiki/Depth_of_field) when photographing something the size of a postage stamp is only a few millimetres even when using a small aperture.
I'd put the odds of producing a adequately sharp copy of a 35mm slide with a handheld camera at less than 1%.
-
Modern smartphones have optical autofocus and flash. The lens is very small so the depth of field is relatively large - I don't think it is a problem to get a really sharp picture of a flat surface(?)
They have about 10MP so there would be about 40 pixels per bit of 512x512 code - shouldn't it be completely enough to determine with high probability if it is black or white?
Eventual errors, deformations, should be correctable by built in error correction, which is rather required.
It is far nontrivial to do it well, but I think that using more colors, we should be able to get a few hundred kilobyte message from close photo with built in flash...
We can also make low resolution codes more informative and visually attractive - recognizable face would require about 150x150 ... maybe use more colors ...
There are more complex, but also doable multi-level codes - that you need a good photo to get the whole information, but you can get its essential part from a weak photo - this level treats blocks as single pixels...
ps. this constrained coding appears to be kind of dual to the rate distortion problem (the base of lossy compression). For example we could encode the halftone version of Lena above using only about 0.18 bits/pixel.
Very interesting is dual version of Kuznetsov and Tsybakov problem, which gets out of standard rate distortion theory - that if we want to send a long bit sequence, in which only some k of bits are in fact fixed by us (the receiver don't know which, the rest of bits can be random), it is enough to send a bit more than k bits.
-
I think that to conform to the QR standard, you would need to retain the Position symbols in 3 corners, plus the Alignment symbol towards the lower right, as shown in http://en.wikipedia.org/wiki/QR_Code#Storage
This would be similar to the the convention of giving hyperlinks a blue underline, in that it tells people that there is more here than meets the eye, and inviting them to investigate further (eg by clicking on the hyperlink, or scanning the QR code with their smartphone).
I agree that this would make the QR codes more visually attractive (but less distinctive - the smartphone software would need to be upgraded to interpret these QR codes with reduced contrast and blurry edges to the pixels).
On a web page, you may as well use a JPEG image with a hyperlink, rather than a QR code.
The QR codes are most useful on a printed medium (or a printed web page), where the hyperlink is via the smartphone.
-
Of course we can add the distinctive corners, which main purpose is positioning - what is technically more difficult is removing them, but it is also doable.
I don't think they are needed to make people recognize that it is a code - above Lena already looks suspicious from a distance, while getting closer you start seeing single pixels/bits ... and wonder what interesting they store ...
This time it can be something much larger than a hyperlink - which you can usually easily get by remembering company name and googling it later, so there is no point to scan the code ... this time these nice looking bits you can distinguish may themselve contain some interesting content - a text, midi song, animated gif, small app ... which for example you can easily get only in this specific place ...
-
Modern smartphones have optical autofocus and flash. The lens is very small so the depth of field is relatively large - I don't think it is a problem to get a really sharp picture of a flat surface(?)
Typically lenses designed to objects 1-2 meters away, (e.g. to photograph people), perform poorly when they are used for macro (close-up) photography. When used for very close-up (~10cm) their curvature of field becomes apparent : it becomes impossible to have all of a flat close surface in focus at once, either the centre is in focus, or the corners of the frame, but not both simultaneously ...
(https://www.thenakedscientists.com/forum/proxy.php?request=http%3A%2F%2Fwww.dvinfo.net%2Farticles%2Foptics%2Fcurve.gif&hash=8b675c604e327fcbe7649cef2b6a9f36)
Eventual errors, deformations, should be correctable by built in error correction, which is rather required.
Yes geometric distortions (https://en.wikipedia.org/wiki/Distortion_%28optics%29) can be corrected, but not blur, if the image is blurred beyond a threshold the data is lost.
Before progressing with your project I’d suggest you experiment with current phone cameras to see how much detail you can cram into a QR code and still have the phone-camera read it reliably.
http://www.bealecorner.org/red/test-patterns/
[ some phone cameras even have trouble reading with current bold blocky QR codes , upping the detail in the code will increase the odds of failure to read ]
Currently the QR code typically conveys an internet URL from which you could quickly download Mb of data, the only advantage of a QR code with more data in it, ( if it was practically possible ), was if you didn’t have internet access.
-
You are saying that they cannot be very small and I completely agree with that - here is an article (http://www.qrstuff.com/blog/2011/01/18/what-size-should-a-qr-code-be) suggesting to use at least 0.4mm per data dot. Such 512x512 code could be a part of a billboard, what we often see now.
But this possibility can be also used with current small resolution codes, especially the Kuznetsov-Tsybakov case in which we fix some part of bits (p_f of them) and the rest can be random - the informational capacity can be nearly the number of not fixed bits:
(https://www.thenakedscientists.com/forum/proxy.php?request=http%3A%2F%2Fdl.dropbox.com%2Fu%2F12405967%2Fktt.png&hash=676bca27a9b70eefc3f80d3c640e3778)
In dual formulation, we could encode such pictures using a bit more than p_f bits/pixel.
Additionally, we can add more colors to make them look nicer and have more informational capacity (both visual and encoded). Of course we would need to be careful because color perception depends on the illumination. It shouldn't be a problem while using three basic colors like the right Lena above. For more bits/color it would need good billboard illumination or flash and calibrating-ECC software I think I know how to make.
Finally, I completely agree that large capacity codes can be easily replaced by link to web address ... beside security issues of accessing unknown sites, the only real argument I have now (?) to use pictures instead is psychological: we live in a digital world, but these digits are usually invisible - these pictures would make you can directly see all the digits: they look nice and still contain some hidden valuable content, making you curious what is it this time - in this digital world art piece ...
ps. There appeared here some unknown/new but looking quite basic possibilities of information theory: encoding with constrains known only to the sender (some is already used in current steganography) or a different view on rate distortion problem, like cheaply encoding such halfotne pictures or probably new: dual version of Kuznetsov and Tsybakov problem - maybe you could think of different applications for them?
-
You are saying that they cannot be very small and I completely agree with that - here is an article (http://www.qrstuff.com/blog/2011/01/18/what-size-should-a-qr-code-be) suggesting to use at least 0.4mm per data dot.
If 0.4mm is the minimum reliably-readable data-dot size then your lena-like-code (https://dl.dropbox.com/u/12405967/len.gif) would have to be reproduced at least 20cm X 20cm, so most of an A4-size magazine page.
-
Indeed, so I have written that such large resolution and capacity code could be a part of a billboard. Even a large part as they can be visually attractive. For example looking like singer face and containing a sample of the new song (e.g. for phone ring).
-
If someone is interested in this subject, I have recently created presentation with new pictures, explanations:
https://dl.dropboxusercontent.com/u/12405967/qrsem.pdf (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?
-
I think , apply colour level value for a background that does not interfere with the pictorial effect(background / foreground colour difference) that is the same grey scale when converted to cause "pictorial subject colouring to be different to reading colour(converted by electronic visual device to grey scale)".
Alike light primary colour filter sheets.
-
I have finally implemented some very basic version (without dithering, error correction): https://dl.dropboxusercontent.com/u/12405967/PRcodes.zip
here are some examples of increasing contrast at cost of capacity:
(https://dl.dropboxusercontent.com/u/12405967/PRcodes.bmp)
-
I have placed the (very basic!) implementation here: https://github.com/JarekDuda/PRcodes
I will eventually add error correction and maybe dithering, but I don't have much time to work on it now - feel free to expand it.
To imagine rate=1-F/N and contrast tradeoffs for different resolutions (code capacity = "number of pixels * rate" bits):
(https://dl.dropboxusercontent.com/u/12405967/lincodes.png)