6 ms·

QR error correction helps and hinders scanning

72 points by dbaupp 5y ago

iudqnolq 5y ago
TLDR: Assuming a fixed qr code size, more resiliency to noise (mud on image, etc) requires putting more information in the code. To fit this the boxes need to be smaller, so that's harder to read. But if you're in a noisy environment and actually need the error correction it's still worth it.
kazinator 5y ago
Has someone made a QR code that is a random dot stereogram and which encodes something useful? Like the source code of the program which generates it or something. :)
- codebeaker 5y ago
  Something like a quine? https://www.quaxio.com/qrquine/ https://www.quaxio.com/qrquine/
  - kazinator 5y ago
    This is in the same area of exploration, except that my main requirement is that, visually, the QR code is a random-dot stereogram. If you align your eyes the right way while staring at it, a 3D image appears. Other requirements, like that it decodes to something that is meaningful, are secondary. Alok's quine work is interesting. The actual quining is trivial because the program pulls out its own image using Location.href. (The trick seems to be that when JS code is embedded in a literal "data:" URL, then the Location.href can pull out that URL itself. I'm not a JS person, though.) It looks like the hard work in this project was developing the QR code encoder using a verbose OOP approach, and then code golfing it through 25 steps to make it small.
- rebane2001 5y ago
  import qrcode with open(__file__) as f: img = qrcode.make(f.read()) img.show() Could be improved upon, but works as an example :)
- Y_Y 5y ago
  The obvious best-tool-for-the-job language here is blazon. Here's a rough POC: checky argent and sable 5 square voided in saltire palewise argent 12 square inverted sable in dexter chief a square voided fesswise argent on a plain cross escartelly checky sable and argent 3 square voided fesswise inverted argent in third quarter 3 square voided in bend sinister argent in first quarter 3 square voided in bend argent I used the interpreter at drawshield.net.
sschueller 5y ago
What also makes scanning harder is people adding logos in the center "using up" some of the error correction.
- Y_Y 5y ago
  My company's logo is a small black square.
  - stronglikedan 5y ago
    My company's logo is three black squares, encased in black rectangles, arranged at the first three corners, in reading order, of an imaginary square with four times the height of one of the black rectangles.
    - nayuki 5y ago
      Your company's name must be Finder. ;-)
looperhacks 5y ago
One thing that really annoys me with the use of qr codes (which are more often used due to the pandemic) is that many qr codes don't include the quiet zone required to scan the code. Instead they expect that the app the code is displayed in has a white background. But this doesn't work if you get a qr code via email and have dark mode active. In the first year of the pandemic I often had to fiddle with my mail app because of it, now I just have my app set to light mode. Generate correct QR codes, people!
- lifthrasiir 5y ago
  Well, the very concept of the quiet zone is rather unworkable for mass uses. QR code in particular has a relatively large quiet zone (8/29 = ~28% at the smallest size) in spite of also having multiple large finder patterns. If QR code can't function without that large quiet zone, I think it should have extended timing patterns so that the "quiet" zone actually has some pixels (modules in the QR terminology) set so users are expected not to cut the corner. A similar strategy has been used by EAN-13 where the quiet zone is indicated with a placeholder character `>` underneath.
  - amelius 5y ago
    If you are transferring information from one device to another, perhaps a QR code (or barcode) is not the right way to do it to begin with.
    - lifthrasiir 5y ago
      I mostly agree, but we can't easily change the fact that people are using two-dimensional barcodes for transferring a small amount of information anyway.
  - dbaupp 5y ago
    You’re even understating the impact of the quiet zone: at version 1, the QR code itself is only 52% of the code + quiet zone area (21**2 modules out of 29**2). Almost twice as bad! :) That said, in practice, a quiet zone of one module or even only partial quiet zones (around the position patterns) seems to work: https://qrworld.wordpress.com/2011/08/09/the-quiet-zone/ https://qrworld.wordpress.com/2011/08/09/the-quiet-zone/
matharmin 5y ago
Another interesting effect: If you have a version 1 code (the smallest size), there is no "alignment" block in the lower-right corner - only the main three positional blocks. Some scanning algorithms (such as the popular zxing library) struggle with this, and it actually works better to use a version 2 code.
- dbaupp 5y ago
  Cool, nice tip.
dhsysusbsjsi 5y ago
On URL Versions: I find it odd that governments (eg Australia) that mandate QR codes to check-in to places have such complex information and detailed codes. This makes scanning the QR code more difficult due to the smaller dot size. This results in people huddling around a single point at a door for longer and closer proximity. A little tech love such as using short URL’s with an intermediate backend that redirects to the complex site URL with a dozen query parameters would allow much lower resolution (lower version) QR codes that can be scanned faster and/or from a further distance away resulting in better health outcomes. Or at least minimise the negative health outcome from the scanning process.
- baybal2 5y ago
  it will not work on devices without internet
  - HPsquared 5y ago
    They could have a local copy of the database, perhaps.
    - baybal2 5y ago
      Why having a database if you can go without it?
      - cyberge99 5y ago
        A PWA (web app) can queue it up until it has connectivity at a latter point in time.
        baybal2 5y ago
        To load the pva the device needs to have the internet to load it to begin with
- dbaupp 5y ago
  That’s actually exactly the topic of my next post, and the reason I even started looking at this. :) As the sibling says, there’s some data that is useful to store in every code to enable user-friendly offline check-ins, but they could indeed be much easier to scan and still retain this property.
leokennis 5y ago
What I always hate is: at a bus stop I see a poster for, let's say, a museum which includes a QR code to visit their site: https://i.imgur.com/SHEmEPn.gif https://i.imgur.com/SHEmEPn.gif I already know this is a URL with tracking parameters etc. As it encodes so much data and I am in a hurry, it takes my phone forever to scan. Meanwhile, this QR code would have led me to their site as well: https://i.imgur.com/IyxYyZN.gif https://i.imgur.com/IyxYyZN.gif
- bellyfullofbac 5y ago
  It's even better when the super-complicated QR code is the size of a printed page pasted on the side of a car or truck, gee I wonder how hard those would be to scan when I'm a passenger in a car dozens of feet away, and both me and the truck are moving around.
  - stronglikedan 5y ago
    > I'm a passenger in a car dozens of feet away, and both me and the truck are moving around. That's the least common use case. They actually work well for their intended use cases, which are (a) a passenger scanning it from a care a few feet away moving at relatively the same speed (such as on the highway), and (b) the code being scanned while waiting at a stop light (maybe dozens of feet away).
- PaulHoule 5y ago
  It seems to be obscure that QR codes have an "alphanumeric" character set that includes everything you need to make URLs IF you use only uppercase characters. This increases the data density considerably. I make URLs that look like https://gen5.info/$/XQ*42RXF-TLY:$B.8/ https://gen5.info/$/XQ*42RXF-TLY:$B.8/ (That is the digital twin of an installation on the wall behind me as I type, each square is 8 by 8 inches; the barcodes on the back of the cards are NOT high density, three-sided cards from that generation that link to external sites link directly to low density URLs. New generation three-sided cards use "QRLs" that redirect to external links.) which are "version 2" QR codes that are larger only than "version 1" QR codes which don't have the little alignment dot in the lower right and don't scan as well. The URL above uses M level error correction, with L level error correction I can make URLs that are a bit longer. I manage either length of code much like a type 4 UUID and in the later case the space is large enough that I (you and 8 billion of my closest friends) could make every URL unique and be perfectly able to track people at the expense of keeping a database entry for every unique code. My take is that the degree of compression doesn't matter much in my case because with high density QR codes you can print them large enough that barcode readers have no problem with them. My experience is that the QR code reading experience on iPhones is night-and-day better than that on cheap Android devices. I think a lot of people are testing barcodes on iOS and have no idea that they scan poorly or not at all for other uses. For one thing, any camera has a minimum depth that it focuses at and if you print a QR code too small you have to hold the camera close to the code to read it and the camera can't focus. Another problem is that most QR code reading programs just don't read white-on-black codes even if the standard allows them. For that matter, many QR code readers require much higher contrast than the standard specifies, and even the standard is conservative compared to what is possible with a generously sized code.
rebane2001 5y ago
The lowest level EC is the best for when you are building a QR code generator in Minecraft, trust me
theden 5y ago
Nice post, learned new things about QR codes. I noticed in the wild when doing check-ins, unreliable QR codes have been due to glossy paper and/or their placement, either being too high or low causing distortion. https://datagenetics.com/blog/november12013/index.html https://datagenetics.com/blog/november12013/index.html illustrates the impact of different destruction cases I'm surprised I haven't seen NFC tags being used for covid check-ins as a secondary option to QR codes
- dbaupp 5y ago
  Thanks! Yeah, glossy paper (or glass) leading to reflections can be bad. The worst one I’ve seen is printed at A5 size (on an A4 page…) and then placed behind glass, outside. Basically useless! I would imagine that NFC requires too much actual hardware, whereas printing is cheap and common.
tinus_hn 5y ago
Note that there are some areas that may not be damaged or the code is unreadable. The author avoided the big squares that are obvious to the eye and are required for positioning but there are also timing lines and metadata areas that are required for decoding.
- nayuki 5y ago
  The timing lines are not critical; timing can be derived from the data itself. Metadata areas (mask, error correction level, version) are stored twice and protected with error detection bits.
  - tinus_hn 5y ago
    I did not know that there was that much redundancy in the metadata but there is. Still, I think damaging the timing areas causes problems. All the ‘creatively damaged’ QR codes I’ve seen avoid these as well as the positioning areas. Of course it’s not too useful to speculate about what’s required beyond adherence to the specification, it depends on what the scanners your users use accept.

72 points by dbaupp 5y ago

TLDR: Assuming a fixed qr code size, more resiliency to noise (mud on image, etc) requires putting more information in the code. To fit this the boxes need to be smaller, so that's harder to read. But if you're in a noisy environment and actually need the error correction it's still worth it.

kazinator 5y ago

Has someone made a QR code that is a random dot stereogram and which encodes something useful? Like the source code of the program which generates it or something. :)

codebeaker 5y ago
Something like a quine? https://www.quaxio.com/qrquine/ https://www.quaxio.com/qrquine/
- kazinator 5y ago
  This is in the same area of exploration, except that my main requirement is that, visually, the QR code is a random-dot stereogram. If you align your eyes the right way while staring at it, a 3D image appears. Other requirements, like that it decodes to something that is meaningful, are secondary. Alok's quine work is interesting. The actual quining is trivial because the program pulls out its own image using Location.href. (The trick seems to be that when JS code is embedded in a literal "data:" URL, then the Location.href can pull out that URL itself. I'm not a JS person, though.) It looks like the hard work in this project was developing the QR code encoder using a verbose OOP approach, and then code golfing it through 25 steps to make it small.
rebane2001 5y ago
import qrcode with open(__file__) as f: img = qrcode.make(f.read()) img.show() Could be improved upon, but works as an example :)
Y_Y 5y ago
The obvious best-tool-for-the-job language here is blazon. Here's a rough POC: checky argent and sable 5 square voided in saltire palewise argent 12 square inverted sable in dexter chief a square voided fesswise argent on a plain cross escartelly checky sable and argent 3 square voided fesswise inverted argent in third quarter 3 square voided in bend sinister argent in first quarter 3 square voided in bend argent I used the interpreter at drawshield.net.

sschueller 5y ago

What also makes scanning harder is people adding logos in the center "using up" some of the error correction.

Y_Y 5y ago
My company's logo is a small black square.
- stronglikedan 5y ago
  My company's logo is three black squares, encased in black rectangles, arranged at the first three corners, in reading order, of an imaginary square with four times the height of one of the black rectangles.
  - nayuki 5y ago
    Your company's name must be Finder. ;-)

looperhacks 5y ago

One thing that really annoys me with the use of qr codes (which are more often used due to the pandemic) is that many qr codes don't include the quiet zone required to scan the code. Instead they expect that the app the code is displayed in has a white background. But this doesn't work if you get a qr code via email and have dark mode active. In the first year of the pandemic I often had to fiddle with my mail app because of it, now I just have my app set to light mode. Generate correct QR codes, people!

lifthrasiir 5y ago
Well, the very concept of the quiet zone is rather unworkable for mass uses. QR code in particular has a relatively large quiet zone (8/29 = ~28% at the smallest size) in spite of also having multiple large finder patterns. If QR code can't function without that large quiet zone, I think it should have extended timing patterns so that the "quiet" zone actually has some pixels (modules in the QR terminology) set so users are expected not to cut the corner. A similar strategy has been used by EAN-13 where the quiet zone is indicated with a placeholder character `>` underneath.
- amelius 5y ago
  If you are transferring information from one device to another, perhaps a QR code (or barcode) is not the right way to do it to begin with.
  - lifthrasiir 5y ago
    I mostly agree, but we can't easily change the fact that people are using two-dimensional barcodes for transferring a small amount of information anyway.
- dbaupp 5y ago
  You’re even understating the impact of the quiet zone: at version 1, the QR code itself is only 52% of the code + quiet zone area (21**2 modules out of 29**2). Almost twice as bad! :) That said, in practice, a quiet zone of one module or even only partial quiet zones (around the position patterns) seems to work: https://qrworld.wordpress.com/2011/08/09/the-quiet-zone/ https://qrworld.wordpress.com/2011/08/09/the-quiet-zone/

matharmin 5y ago

Another interesting effect: If you have a version 1 code (the smallest size), there is no "alignment" block in the lower-right corner - only the main three positional blocks. Some scanning algorithms (such as the popular zxing library) struggle with this, and it actually works better to use a version 2 code.

dbaupp 5y ago
Cool, nice tip.

dhsysusbsjsi 5y ago

On URL Versions: I find it odd that governments (eg Australia) that mandate QR codes to check-in to places have such complex information and detailed codes. This makes scanning the QR code more difficult due to the smaller dot size. This results in people huddling around a single point at a door for longer and closer proximity. A little tech love such as using short URL’s with an intermediate backend that redirects to the complex site URL with a dozen query parameters would allow much lower resolution (lower version) QR codes that can be scanned faster and/or from a further distance away resulting in better health outcomes. Or at least minimise the negative health outcome from the scanning process.

baybal2 5y ago
it will not work on devices without internet
- HPsquared 5y ago
  They could have a local copy of the database, perhaps.
  - baybal2 5y ago
    Why having a database if you can go without it?
    - cyberge99 5y ago
      A PWA (web app) can queue it up until it has connectivity at a latter point in time.
      - baybal2 5y ago
        To load the pva the device needs to have the internet to load it to begin with
dbaupp 5y ago
That’s actually exactly the topic of my next post, and the reason I even started looking at this. :) As the sibling says, there’s some data that is useful to store in every code to enable user-friendly offline check-ins, but they could indeed be much easier to scan and still retain this property.

leokennis 5y ago

What I always hate is: at a bus stop I see a poster for, let's say, a museum which includes a QR code to visit their site: https://i.imgur.com/SHEmEPn.gif https://i.imgur.com/SHEmEPn.gif I already know this is a URL with tracking parameters etc. As it encodes so much data and I am in a hurry, it takes my phone forever to scan. Meanwhile, this QR code would have led me to their site as well: https://i.imgur.com/IyxYyZN.gif https://i.imgur.com/IyxYyZN.gif

bellyfullofbac 5y ago
It's even better when the super-complicated QR code is the size of a printed page pasted on the side of a car or truck, gee I wonder how hard those would be to scan when I'm a passenger in a car dozens of feet away, and both me and the truck are moving around.
- stronglikedan 5y ago
  > I'm a passenger in a car dozens of feet away, and both me and the truck are moving around. That's the least common use case. They actually work well for their intended use cases, which are (a) a passenger scanning it from a care a few feet away moving at relatively the same speed (such as on the highway), and (b) the code being scanned while waiting at a stop light (maybe dozens of feet away).
PaulHoule 5y ago
It seems to be obscure that QR codes have an "alphanumeric" character set that includes everything you need to make URLs IF you use only uppercase characters. This increases the data density considerably. I make URLs that look like https://gen5.info/$/XQ*42RXF-TLY:$B.8/ https://gen5.info/$/XQ*42RXF-TLY:$B.8/ (That is the digital twin of an installation on the wall behind me as I type, each square is 8 by 8 inches; the barcodes on the back of the cards are NOT high density, three-sided cards from that generation that link to external sites link directly to low density URLs. New generation three-sided cards use "QRLs" that redirect to external links.) which are "version 2" QR codes that are larger only than "version 1" QR codes which don't have the little alignment dot in the lower right and don't scan as well. The URL above uses M level error correction, with L level error correction I can make URLs that are a bit longer. I manage either length of code much like a type 4 UUID and in the later case the space is large enough that I (you and 8 billion of my closest friends) could make every URL unique and be perfectly able to track people at the expense of keeping a database entry for every unique code. My take is that the degree of compression doesn't matter much in my case because with high density QR codes you can print them large enough that barcode readers have no problem with them. My experience is that the QR code reading experience on iPhones is night-and-day better than that on cheap Android devices. I think a lot of people are testing barcodes on iOS and have no idea that they scan poorly or not at all for other uses. For one thing, any camera has a minimum depth that it focuses at and if you print a QR code too small you have to hold the camera close to the code to read it and the camera can't focus. Another problem is that most QR code reading programs just don't read white-on-black codes even if the standard allows them. For that matter, many QR code readers require much higher contrast than the standard specifies, and even the standard is conservative compared to what is possible with a generously sized code.

rebane2001 5y ago

The lowest level EC is the best for when you are building a QR code generator in Minecraft, trust me

theden 5y ago

Nice post, learned new things about QR codes. I noticed in the wild when doing check-ins, unreliable QR codes have been due to glossy paper and/or their placement, either being too high or low causing distortion. https://datagenetics.com/blog/november12013/index.html https://datagenetics.com/blog/november12013/index.html illustrates the impact of different destruction cases I'm surprised I haven't seen NFC tags being used for covid check-ins as a secondary option to QR codes

dbaupp 5y ago
Thanks! Yeah, glossy paper (or glass) leading to reflections can be bad. The worst one I’ve seen is printed at A5 size (on an A4 page…) and then placed behind glass, outside. Basically useless! I would imagine that NFC requires too much actual hardware, whereas printing is cheap and common.

tinus_hn 5y ago

Note that there are some areas that may not be damaged or the code is unreadable. The author avoided the big squares that are obvious to the eye and are required for positioning but there are also timing lines and metadata areas that are required for decoding.

nayuki 5y ago
The timing lines are not critical; timing can be derived from the data itself. Metadata areas (mask, error correction level, version) are stored twice and protected with error detection bits.
- tinus_hn 5y ago
  I did not know that there was that much redundancy in the metadata but there is. Still, I think damaging the timing areas causes problems. All the ‘creatively damaged’ QR codes I’ve seen avoid these as well as the positioning areas. Of course it’s not too useful to speculate about what’s required beyond adherence to the specification, it depends on what the scanners your users use accept.