How a QR code works(typefully.com)
typefully.com
How a QR code works
https://typefully.com/DanHollick/qr-codes-T7tLlNi
121 comments
Well played.
If there's any silver lining to COVID, it's QR codes being normalized.
I remember trying to use a QR code in 2015 at a crypto meetup so I could buy a beer with Bitcoin (they organized with the bar that they'd get cash at the end if they played ball). After downloading a QR reader app, taking a picture with my phone, uploading the picture to the app, then realizing there was too much glare and trying again, they eventually just gave me a beer and put a tally mark on a notepad.
Just a few weeks ago I used a QR code to join a WiFi network and it took like 2 seconds (it found the network and entered the password for me). We've come a long way.
I remember trying to use a QR code in 2015 at a crypto meetup so I could buy a beer with Bitcoin (they organized with the bar that they'd get cash at the end if they played ball). After downloading a QR reader app, taking a picture with my phone, uploading the picture to the app, then realizing there was too much glare and trying again, they eventually just gave me a beer and put a tally mark on a notepad.
Just a few weeks ago I used a QR code to join a WiFi network and it took like 2 seconds (it found the network and entered the password for me). We've come a long way.
> QR codes being normalized
I also became aware of the possibility of people putting their own QR code sticker over another. Quite easy to send people to a phishing site... enter your credit card to "buy" that beer...
I also became aware of the possibility of people putting their own QR code sticker over another. Quite easy to send people to a phishing site... enter your credit card to "buy" that beer...
This has been a problem with NYC's bike share program, CitiBike. The solution was to add an alert when your phone's location is far from the location of the bicycle you are trying to unlock.
> Citi Bike says it is aware of a scam in New York City in which thieves are switching the QR code stickers on rental bicycles in order to steal bikes unwittingly unlocked by customers. The scammers wait for a renter to unlock a bicycle using the QR code, then ride away on the bike to which the code actually belongs, officials said.
https://apnews.com/article/lifestyle-nyc-state-wire-34d4ecd5...
> Citi Bike says it is aware of a scam in New York City in which thieves are switching the QR code stickers on rental bicycles in order to steal bikes unwittingly unlocked by customers. The scammers wait for a renter to unlock a bicycle using the QR code, then ride away on the bike to which the code actually belongs, officials said.
https://apnews.com/article/lifestyle-nyc-state-wire-34d4ecd5...
Easy (conceptually) solution: a button on the dock that you need to press to complete the unlock. When you scan the QR code, CitiBike looks up which dock it thinks the bike is in, then waits for you to press that dock's button before releasing the bike.
What about geolocating the customer's phone and blocking the transaction if the customer's phone is more than, say, 10 meters from the bike?
The thief would just press the button.
Assuming that there is no feedback during this process coming from the bike, what is the thief going to do? Sit there for an hour constantly pressing the button?
The thief would just observe, from a distance, and wait for someone trying to scan the fake qr code. When he sees the victim, he pushes the button and steals the bike.
This is why Toronto's bike share requires Bluetooth to be turned on. At worst, you might end up unlocking another bike at the same station. (And you'll hear it!)
A possible solution could be to use small e-ink displays showing single-use QR codes that change every 2 minutes or so. I don't know if it would be feasible though or it would drain the battery of the bike too quickly.
Yes, that's where I heard about this problem. Sketchy indeed.
The best solution would be a QR mode with a standardized cryptographic signature.
Can you explain more what you're thinking here? I don't see how that would solve anything.
QR codes generally are just a bit of data, like a link to a website. If I cover up an existing QR code with my own link to my own website... what would a signature do to help here?
Even if the original QR code had the link printed on it, do you think someone reaching for their 3rd beer would even notice it?
Humans are not conditioned (yet) to validate QR codes. We scan them without thinking twice. Phishing is pretty sophisticated and it is easy to duplicate a website.
QR codes generally are just a bit of data, like a link to a website. If I cover up an existing QR code with my own link to my own website... what would a signature do to help here?
Even if the original QR code had the link printed on it, do you think someone reaching for their 3rd beer would even notice it?
Humans are not conditioned (yet) to validate QR codes. We scan them without thinking twice. Phishing is pretty sophisticated and it is easy to duplicate a website.
This is an authorization issue. You need a signing authority of some kind to verify the QR code.
A literal JWT (JSON Web Token) could be used, but a binary format could save TONS of space (30-50% smaller) which matters for a QR code.
QR would contain: binary data, datetime it was issued, QR creator ID, URL of signing authority (or a code from an approved list of authorities representing a know URL), a code for the algorithm used, and a signature that signs everything else.
When a user scans the QR, the software recognizes that it uses authorization mode.
It looks up the signing authority based on the ISO code for that authority and sends an API request for the public key sending the datetime and creator ID.
The signing authority returns the public key based on company and time (or a message if the private key has been revoked. If the key checks out, the user visits the URL.
All of this would take a fraction of a second and be entirely transparent to the user (barring revoked permissions or the signature being incorrect).
A literal JWT (JSON Web Token) could be used, but a binary format could save TONS of space (30-50% smaller) which matters for a QR code.
QR would contain: binary data, datetime it was issued, QR creator ID, URL of signing authority (or a code from an approved list of authorities representing a know URL), a code for the algorithm used, and a signature that signs everything else.
When a user scans the QR, the software recognizes that it uses authorization mode.
It looks up the signing authority based on the ISO code for that authority and sends an API request for the public key sending the datetime and creator ID.
The signing authority returns the public key based on company and time (or a message if the private key has been revoked. If the key checks out, the user visits the URL.
All of this would take a fraction of a second and be entirely transparent to the user (barring revoked permissions or the signature being incorrect).
Thanks.
What prevents me from just signing my own QR code though? I could register a very similar domain, sign it, make it look all official and then siphon funds.
A third party could revoke my signature, but then we are dependent on that third party for everything, which isn't ideal either.
What prevents me from just signing my own QR code though? I could register a very similar domain, sign it, make it look all official and then siphon funds.
A third party could revoke my signature, but then we are dependent on that third party for everything, which isn't ideal either.
This is the difference between a self-signed SSL cert and one that is issued by a trusted company.
An argument in trusting trust is meaningless. The whole point is that they can be trusted. If you don't believe you can trust them, then nothing is going to change that.
The goal isn't to make such scams impossible, but instead to make them too risky and expensive.
If you're going to do a scam like that on a business level, there's a lot of logistics involved. A mom and pop shop isn't going to be a suitable target, so you're going to be targeting a franchise where you can easily move operations to reduce costs. You have to spend a bunch of time building out a fake website. You have to put multiple boots on the ground to go around changing hundreds of QR codes to improve hit rates.
QR certification means you have to create a new business to apply that makes a paper trail. Creating something very close to an actual franchise is also going to run the risk of setting off alarm bells and getting busted by the FBI. It doesn't make this scam impossible, but adds a big enough hurdle to reduce profitability and increase risk to the point where there are easier scams to pull off.
The other kind of attack is one-off scammers hoping to trap people. In this "QRL" certification scheme (sorry for the bad pun), their scam would never get off the ground because it wasn't certified.
An argument in trusting trust is meaningless. The whole point is that they can be trusted. If you don't believe you can trust them, then nothing is going to change that.
The goal isn't to make such scams impossible, but instead to make them too risky and expensive.
If you're going to do a scam like that on a business level, there's a lot of logistics involved. A mom and pop shop isn't going to be a suitable target, so you're going to be targeting a franchise where you can easily move operations to reduce costs. You have to spend a bunch of time building out a fake website. You have to put multiple boots on the ground to go around changing hundreds of QR codes to improve hit rates.
QR certification means you have to create a new business to apply that makes a paper trail. Creating something very close to an actual franchise is also going to run the risk of setting off alarm bells and getting busted by the FBI. It doesn't make this scam impossible, but adds a big enough hurdle to reduce profitability and increase risk to the point where there are easier scams to pull off.
The other kind of attack is one-off scammers hoping to trap people. In this "QRL" certification scheme (sorry for the bad pun), their scam would never get off the ground because it wasn't certified.
> If you're going to do a scam like that on a business level, there's a lot of logistics involved. A mom and pop shop isn't going to be a suitable target, so you're going to be targeting a franchise where you can easily move operations to reduce costs. You have to spend a bunch of time building out a fake website. You have to put multiple boots on the ground to go around changing hundreds of QR codes to improve hit rates.
They emailed my finance department, said the account number had changed, even used the same bank, and got us to send a payment for an invoice to that new account. Bank happily paid them out. Nuts. Now we have to try to claw the money back, but I don't think we can get it without long legal proceedings against the bank. Imagine though, having the balls to open a bank account after having broken into a company.
The people in the finance department felt awful and surprised that this could even happen to them. Since then, they've now increased the security 1000x and require voice verification and what not...
My point is, just like you say, you can't trust the trust. The only way this would have worked is if QR codes could only be generated by a trusted third party for all QR codes. Even still, it wouldn't work because I could fake the trusted third party.
You have a nice dream, and it gets me thinking that a "LetsEncrypt for QR codes" might be an interesting business service, but it would require a huge amount of convincing people to use you as well as marketing dollars to get the word out. I still don't think it'll stop everything.
[deleted]
> If there's any silver lining to COVID, it's QR codes being normalized
I'm not sure if I would call this a "silver lining". In parts of Europe (I noticed it especially in Germany and Austria) they were normalized to a point were a lot of non-techsavvy people now think "QR codes" are kind of synonym to successful "digitalisation".
It's now even more painful to watch misguided attempts to digitalize shitty (business/administrative...) processes. QR codes just feel like the poor man's blockchain.
I'm not sure if I would call this a "silver lining". In parts of Europe (I noticed it especially in Germany and Austria) they were normalized to a point were a lot of non-techsavvy people now think "QR codes" are kind of synonym to successful "digitalisation".
It's now even more painful to watch misguided attempts to digitalize shitty (business/administrative...) processes. QR codes just feel like the poor man's blockchain.
My child's daycare uses a cell phone app for checking in and out the children. It requires one to scan a QR code, then enter a PIN, and scribble a signature.
I am not able to get over this seeming like security theater, not to mention being somewhat indignant to the presumptive ownership of a smart phone to go through this song and dance when a piece of paper would suffice as a record.
I've captured the qr code and found that it's not geo-fenced or time-locked so I can check the child in and out in the comfort of my home, but haven't probed the application further.
I am not able to get over this seeming like security theater, not to mention being somewhat indignant to the presumptive ownership of a smart phone to go through this song and dance when a piece of paper would suffice as a record.
I've captured the qr code and found that it's not geo-fenced or time-locked so I can check the child in and out in the comfort of my home, but haven't probed the application further.
Yes, this is very true, _in the US_. In other parts of the world, QR Codes have been ubiquitous for many years. In China, Alipay, WechatPay, UnionPay, etc have made QR codes for payment expected and common, to the point that many places don't take cash or credit cards, but you can pay with the right phone app and account.
Which is also annoying, since it’s pretty hard for a foreigner to set up WeChat and AliPay in China. Before covid, I had to repeatedly ask friends to pay for me, and give them cash in return.
Why do we think emulating China is a good thing? The covid response showed that it was probably the worst possible thing to do.
I didn't say that the emulating China is what should be done in this case. I much prefer the UX of Apple Pay with my watch - it still feels magical.
It is interesting how much cheaper the QR based payment schemes are in China. Payment processors in the west charge 2-3% typically for tap/dip/swipe. In China, the QR transaction fee is a fraction of that. Also, a bunch of the infrastructure for printing, displaying, and reading the QR codes is pretty cheap.
It is interesting how much cheaper the QR based payment schemes are in China. Payment processors in the west charge 2-3% typically for tap/dip/swipe. In China, the QR transaction fee is a fraction of that. Also, a bunch of the infrastructure for printing, displaying, and reading the QR codes is pretty cheap.
Imagine how much more magical a chip implanted under your skin would feel.
Did covid really do that? The iPhone camera app has been able to read QR codes out of the box since iOS 11 (released in 2017)
To my memory: the timing was off. QR codes (in the consumer-facing context) kind of peaked and died out before the iPhone camera app would scan them in large part because non-techies would not download an app just to scan a code. Apple added support, but there didn't seem to be enough emphasis to revisit them until COVID.
I had seen them in museums before 2015… the fact that you specifically didn't manage to work them means nothing.
My symbian phone could read them in 2010.
My symbian phone could read them in 2010.
Yes they were out there and readable by lots of phones in 2010, and very few people used them. They weren't convenient to use and didn't tend to direct you anywhere useful to begin with.
The running joke for a decade (here in the US anyway) was that nobody had ever actually used one.
The running joke for a decade (here in the US anyway) was that nobody had ever actually used one.
I've looked into this a couple of years ago and the problem was that you just couldn't assume people would be able to scan a qr code without downloading an extra app.
iPhones could scan them with the default camera app, but on Android it really depended on the manufacturer.
So you couldn't just say: "point your camera app at the code and open the url that appears.", which made using QR codes pretty much useless unless you had an app where you could build in an scanner for these codes.
iPhones could scan them with the default camera app, but on Android it really depended on the manufacturer.
So you couldn't just say: "point your camera app at the code and open the url that appears.", which made using QR codes pretty much useless unless you had an app where you could build in an scanner for these codes.
I attach QR codes to all my invoices and I encourage every business entity I interact with to start doing the same. I had a few successes actually, though the big businesses are more reluctant.
An old investor once told me: "Make it really easy for your customers to pay you, and you won't regret it." QR codes make it really easy to do a wire transfer and they prevent random errors from being introduced.
An old investor once told me: "Make it really easy for your customers to pay you, and you won't regret it." QR codes make it really easy to do a wire transfer and they prevent random errors from being introduced.
By the end of the month all national non-qr invoices will be deprecated in Switzerland, making proprietary readers obsolete.
I think there is still a lot to improve. See [1] or [2]
Things that become a utility / must-have for daily life (say QR to order food) should have better discoverability and accessibility
1. https://discussions.apple.com/thread/253350496
2. https://discussions.apple.com/thread/250694589
Things that become a utility / must-have for daily life (say QR to order food) should have better discoverability and accessibility
1. https://discussions.apple.com/thread/253350496
2. https://discussions.apple.com/thread/250694589
> they eventually just gave me a beer and put a tally mark on a notepad
oof
oof
I wouldn't say that is a silver lining, quite the opposite. A step toward a digital gulag.
I still don't like them; http://www.sheldoncomics.com/archive/120618.html
Lately in advertisements there have been a lot of circular QR codes[1]. Which often apparently present data outside of the alignment patterns. Is that merely an artistic device, or is there some standard permitting information extending beyond the square region?
[1] https://www.google.com/search?tbm=isch&q=circular%20qr%20cod...
[1] https://www.google.com/search?tbm=isch&q=circular%20qr%20cod...
I think most of them are merely artistic, probably all data outside of the alignment patterns is just random stuff. It looks good though. [0]
Some of them however are implemented to be read by a specific non-standard reader, something such as the snap chat codes.
[0]: https://stackoverflow.com/questions/66837985/damaging-qr-cod...
Some of them however are implemented to be read by a specific non-standard reader, something such as the snap chat codes.
[0]: https://stackoverflow.com/questions/66837985/damaging-qr-cod...
I ended up using a QR code in my (Electron) app: the app runs a server, and you take a photo of the QR code on your phone to open the localhost (accessible only over WiFi). The app lets you browse videos you have on your computer through your phone, and when you click on the video image, the video plays on your computer from the frame you clicked on. It turns your phone into a "remote". Cheers: https://videohubapp.com/ & https://github.com/whyboris/Video-Hub-App & https://github.com/whyboris/Video-Hub-App-remote
Nice. I used them in a poll creator. You create a poll and the app generates a QR code for you to display. People can use the QR code to go to the poll's site and vote.
This python package makes it super easy: https://pypi.org/project/qrcode/
This python package makes it super easy: https://pypi.org/project/qrcode/
For JS I used the npm package an-qrcode https://www.npmjs.com/package/an-qrcode :)
That's actually similar to the method Nintendo used when they finally added an option to send photos and videos to your smartphone from the Switch, with the addition of a first step where the Switch acts as a wifi hotspot and shows a QR code to quickly connect you to it. Then you scan another QR code that jumps you into a simple webapp running on localhost where you can download the photos/videos
What I'd like to see is an explanation of the algorithm that can take a crappy, noisy photo of the QR code, and reliably read it on underpowered hardware.
I second this. Any QR code explainer has a bit of the "draw the rest of the fucking owl" vibe to them. The interesting part is the image processing to actually detect those features and translate them into something recognizable by the machine.
Third. I’m not even tech side and this stopped short just when it was getting interesting. The global cumulative IQ is melting :(
A long time ago I had this question so I looked through some Android code for this. To me, the most expensive part is doing the search through the image given that you don't know where the qr code is or its orientation.
The key is in the finder patterns (mentioned in the article). If you imagine a line cutting through the center area of one and the series of pixel values you get along the line you'll notice that you get a simple symmetric (mostly)White(mostly)BlackWBBBWBW series. These sequences are easy to search for to get a list of finder pattern candidate locations. Rejecting the false positives is a relatively straightforward and local operation, as is refining exactly where the pattern is centered.
With the cleaned up (hopefully short) list of candidate corners you can propose an orientation/scale (technically a homography) to do the necessary sampling to get the rest of the bits. If none of these work out, you ask the user to try take another picture.
The key is in the finder patterns (mentioned in the article). If you imagine a line cutting through the center area of one and the series of pixel values you get along the line you'll notice that you get a simple symmetric (mostly)White(mostly)BlackWBBBWBW series. These sequences are easy to search for to get a list of finder pattern candidate locations. Rejecting the false positives is a relatively straightforward and local operation, as is refining exactly where the pattern is centered.
With the cleaned up (hopefully short) list of candidate corners you can propose an orientation/scale (technically a homography) to do the necessary sampling to get the rest of the bits. If none of these work out, you ask the user to try take another picture.
Convert to grayscale > find the tracking markers > rotation to turn it upright > normalize for variable brightness > threshold at the median pixel value overlay a grid and have pixel values come to consensus for the value of each cell.
All pretty cheap, so it's probably do-able depending on your definition of underpowered. This is assuming they take an orthogonal shot and there's no need for homographic projection (which would make it a lot more difficult to find the tracking markers).
All pretty cheap, so it's probably do-able depending on your definition of underpowered. This is assuming they take an orthogonal shot and there's no need for homographic projection (which would make it a lot more difficult to find the tracking markers).
In fact, the distinct tracking markers are designed so that at any angle there is some line that contains a sequence of black-white segments in the 1:1:3:1:1 length ratio. Find three such markers, look at alignment and timing patterns at the expected place, and voila, you can infer a matrix of pixels ("modules" in a jargon). And masks are designed so that at least one mask will obscure naturally occuring patterns that look like tracking markers (the evaluation process even mentions the aforementioned 1:1:3:1:1 ratio and penalizes it).
I would like more detail on this. I think for most people, once you know what the light and dark patches are, the rest follows (Reed-Solomon, etc). But how do you take an image that contains an imperfect QR and identify
a) There's enough of a QR there
b) The orientation is {coords}
c) The contents are {contents}
a) There's enough of a QR there
b) The orientation is {coords}
c) The contents are {contents}
As I alluded in a sibling comment, it might help to look at one-dimensional barcodes first, specifically the pervasive Universal Product Code (UPC). Maybe a sensor in a reader can only see a single pixel and a user moves it, or a reader itself has a row of sensors, but the input is always a scanline worth of pixels. The barcode starts with on-off-on-off pattern and ends with off-on-off-on pattern, so we first look at two 1:1:1:1 patterns. Since we know each segment of these patterns is a single unit ("module") in the barcode, we can extrapolate and infer where all other units would be. This can be never accurate---people rarely move their hand that accurately---but those patterns give a good deal of information about the barcode.
Finder patterns in the QR code can be recognized in the same way as long as your scanline actually hits those patterns. Since it's two dimensional you would need multiple scanlines to recognize all of them, but once you've got three finder patterns and they are not coplanar then there is a good chance that the alignment pattern in the fourth position; again, this can be recognized with a 1:1:1:1:1 pattern and you can make a good guess about its size. This gives the orientation [1], and timing patterns between two pairs of finder patterns finally give a transformation you need to apply to convert pixels into a matrix of modules. You read the version and format info (which has its own error correction codes), unapply a mask, read the actual data and ECC, correct any recoverable error and you are done. The very purpose of masking is to prevent those patterns accidentally occurring in the data section, and the standard defines a set of scoring criteria for masks; if 1:1:3:1:1 pattern occurs in the data after masking the mask is scored so low that it won't be chosen.
As you can imagine, while the concept is fairly simple the actual implementation might be complex. I should note that a large enough QR code can have multiple alignment patterns, because as your QR code gets larger it has a larger chance to be warped, and they help detecting where the warp has occurred. Also most barcodes including QR code have a concept of quiet zone that clearly separates a barcode from surrounding environment, mostly because otherwise you might be unable to recognize the beginning and end of the barcode (or in 2D barcodes, its bounding rectangle).
[1] Exercise: Now thinking about that, how can a UPC reader see whether the barcode is upside down or not?
Finder patterns in the QR code can be recognized in the same way as long as your scanline actually hits those patterns. Since it's two dimensional you would need multiple scanlines to recognize all of them, but once you've got three finder patterns and they are not coplanar then there is a good chance that the alignment pattern in the fourth position; again, this can be recognized with a 1:1:1:1:1 pattern and you can make a good guess about its size. This gives the orientation [1], and timing patterns between two pairs of finder patterns finally give a transformation you need to apply to convert pixels into a matrix of modules. You read the version and format info (which has its own error correction codes), unapply a mask, read the actual data and ECC, correct any recoverable error and you are done. The very purpose of masking is to prevent those patterns accidentally occurring in the data section, and the standard defines a set of scoring criteria for masks; if 1:1:3:1:1 pattern occurs in the data after masking the mask is scored so low that it won't be chosen.
As you can imagine, while the concept is fairly simple the actual implementation might be complex. I should note that a large enough QR code can have multiple alignment patterns, because as your QR code gets larger it has a larger chance to be warped, and they help detecting where the warp has occurred. Also most barcodes including QR code have a concept of quiet zone that clearly separates a barcode from surrounding environment, mostly because otherwise you might be unable to recognize the beginning and end of the barcode (or in 2D barcodes, its bounding rectangle).
[1] Exercise: Now thinking about that, how can a UPC reader see whether the barcode is upside down or not?
I would pay to read a more in depth explanation from you (and pay more if there was an annoted code example) - your comment gave me a better understanding than I have managed in the past. In all seriousness, where can I pre-order a copy of "Reading QR code: a programmatic approach" by lifthrasiir?
I probably know this only because back in time I wrote a QR code generator in JavaScript [1] which was also one of such libraries reviewed by Nayuki [2], and as I haven't actually implemented a decoder my knowledge stops there. Sorry :-)
[1] https://github.com/lifthrasiir/qr.js
[2] https://www.nayuki.io/page/qr-code-generator-library
[1] https://github.com/lifthrasiir/qr.js
[2] https://www.nayuki.io/page/qr-code-generator-library
I see, fair enough. I've used your library in the past (i think, it seems familiar anyway), so thanks for that, and also thanks for the insight that writing my own toy qr generator might help me understand the reading process. :)
You first need to figure out the orientation first, no? Or do they just throw down several lines until they find the 1:1:3:1:1 ratio?
Either way, incredible design, it's mind-blowing to learn more about the elegance and level of sophistication.
Either way, incredible design, it's mind-blowing to learn more about the elegance and level of sophistication.
> Or do they just throw down several lines until they find the 1:1:3:1:1 ratio?
Essentially yes. If you are aware of how one-dimensional barcodes are read, it's the same. You would need to check multiple scanlines, but you don't need the full image analysis. It might be the case that modern QR decoders actually look at the full image, but this is hardly necessary.
Essentially yes. If you are aware of how one-dimensional barcodes are read, it's the same. You would need to check multiple scanlines, but you don't need the full image analysis. It might be the case that modern QR decoders actually look at the full image, but this is hardly necessary.
Ok i understand:
* how to convert to grayscale
* how to rotate
The rest of this makes abstract sense, but not any sense wrt "i can write code to do it". As another poster said - its "draw the rest of the owl". It would be nice if someone knows about a nice annotated bit of code that starts from picture and ends at "return data;".
* how to convert to grayscale
* how to rotate
The rest of this makes abstract sense, but not any sense wrt "i can write code to do it". As another poster said - its "draw the rest of the owl". It would be nice if someone knows about a nice annotated bit of code that starts from picture and ends at "return data;".
Here's a link that shows how to normalize (python/ openCV is great for image processing): https://www.delftstack.com/howto/python/opencv-normalize/
If you want to dive into computational photography/ computer vision some more, here's a great class for it: https://www.udacity.com/course/introduction-to-computer-visi...
If you want to dive into computational photography/ computer vision some more, here's a great class for it: https://www.udacity.com/course/introduction-to-computer-visi...
Oh cool - thanks!
It really is draw the rest of the owl, here's a good place to start https://en.wikipedia.org/wiki/Feature_(computer_vision)#Dete...
In computer vision there is no magic bullet, you will have to sink deep into the details.
In computer vision there is no magic bullet, you will have to sink deep into the details.
Here's an idea - instead of assuming I'm being lazy and looking for a magic bullet why don't you consider this: I think this QR code thing might be a great example of a tractable, relatively small problem that lets me sink my teeth into the computer vision stuff that usually is presented in a very abstract way.
In order to do that efficiently, a nice annotated codebase would help a lot. So back to the question:
Do you know of any such codebases?
In order to do that efficiently, a nice annotated codebase would help a lot. So back to the question:
Do you know of any such codebases?
This paper (https://link.springer.com/chapter/10.1007/978-3-030-57058-3_...) might help and is available on github (https://github.com/nimiq/qr-scanner).
It's not a small problem, I'm just warning you. Check the chromium source for their shape detection API: https://source.chromium.org/chromium/chromium/src/+/main:ser...
Sure you can write your own QR and other bar code processing code, but it makes as much sense as rolling your own crypto, and for many of the same reasons.
I've done something similar back in university (a course about signal processing); we were reading some kind of 2d pattern which had alignment marks like a QR code. There was also some (artificial) distortion done on the image so we had to handle that as well.
IIRC the process goes something like this:
Preparation:
- Make your image grayscale
- Clean up your pic somewhat (we did an Fourier analysis on the data to find any repeating distortion like a moiré pattern, plus some averaging of completely white or black pixels)
- Adjust brightness so you have reasonable values throughout
- Somewhere in there you reduce the size to 512x512 or similar to make your life a bit easier in terms of computing power.
Finding the anchor points:
- You create a "mask" of what you're looking for
- You "move" that mask over your whole image, pixel-by-pixel
- For each pixel position, you compute the difference between the image and your mask (this should give you a single value for each position)
- The position with the lowest difference value is probably where your pattern is
Our images were flat, but were rotated a random angle. Our alignment marks were circular, though, which makes the thing a bit a bit simpler. I imagine the actual QR code algorithm skews and rotates its "candidate" mask so it can find codes in a skewed image.
Also, it might just make a first pass looking at big contrasting spots and seeing if they match what a finder pattern should look like. There's tons of ways this can be optimized to run fast on a limited device.
Anyway, once you have the 3 finder "cubes", you can try and see if the alignment mark is where you expect it, and at this point I guess you have your QR position in the original image. What I'd probably do then is go back to the original image, extract the relevant portion of it and then rotate and skew it so it's "square" (there's a matrix transform you can use for this, IIRC). Then you can cut it up into "pixels" by following the timing marks, and the rest is explained in TFA.
IIRC the process goes something like this:
Preparation:
- Make your image grayscale
- Clean up your pic somewhat (we did an Fourier analysis on the data to find any repeating distortion like a moiré pattern, plus some averaging of completely white or black pixels)
- Adjust brightness so you have reasonable values throughout
- Somewhere in there you reduce the size to 512x512 or similar to make your life a bit easier in terms of computing power.
Finding the anchor points:
- You create a "mask" of what you're looking for
- You "move" that mask over your whole image, pixel-by-pixel
- For each pixel position, you compute the difference between the image and your mask (this should give you a single value for each position)
- The position with the lowest difference value is probably where your pattern is
Our images were flat, but were rotated a random angle. Our alignment marks were circular, though, which makes the thing a bit a bit simpler. I imagine the actual QR code algorithm skews and rotates its "candidate" mask so it can find codes in a skewed image.
Also, it might just make a first pass looking at big contrasting spots and seeing if they match what a finder pattern should look like. There's tons of ways this can be optimized to run fast on a limited device.
Anyway, once you have the 3 finder "cubes", you can try and see if the alignment mark is where you expect it, and at this point I guess you have your QR position in the original image. What I'd probably do then is go back to the original image, extract the relevant portion of it and then rotate and skew it so it's "square" (there's a matrix transform you can use for this, IIRC). Then you can cut it up into "pixels" by following the timing marks, and the rest is explained in TFA.
Not to be all "I am so smart" but I'm presuming that orienting and figuring out the dimensions of the grid isn't super hard because of the three (as opposed to four) corners have the easily recognizable "target" pattern, which give both orientation and "pixel" size. From there you just do like weighted thresholds.
I know there's some number magic that happens even if you get some of these wrong, but I imagine it's kind of some kind of reverse checksumming thing going on.
I know there's some number magic that happens even if you get some of these wrong, but I imagine it's kind of some kind of reverse checksumming thing going on.
This explainer goes into the math: https://atcm.mathandtech.org/EP2021/invited/21891.pdf
Or an explainer for Reed-Solomon codes: https://sidewords.files.wordpress.com/2007/12/thesis.pdf
Or an explainer for Reed-Solomon codes: https://sidewords.files.wordpress.com/2007/12/thesis.pdf
FWIW, QR isn't the best option for the real world - it's extremely fragile and susceptible to damage compared to DataMatrix, the other commonly used 2D symbology. DoD uses DataMatrix for marking all aircraft and other components for traceability, for instance.
I've used it on oilfield prototypes just printed on weatherpoof laser labels, and they're still readable even with big gouges and divots missing. By contrast, despite the redundancy, you can scrog a QR code with a single unfortunately placed scratch. (As I reconfirmed out this week trying to read the wiki/docs link for a secondhand laser cutting module I picked up: a screw on the rail had dragged through the QR code in a horizontal line - not through the timing section, but enough to make it unreadable. Fortunately, the model is identifiable visually on the mfr's site, so I can be sure what kind of safety goggles I need!)
I've used it on oilfield prototypes just printed on weatherpoof laser labels, and they're still readable even with big gouges and divots missing. By contrast, despite the redundancy, you can scrog a QR code with a single unfortunately placed scratch. (As I reconfirmed out this week trying to read the wiki/docs link for a secondhand laser cutting module I picked up: a screw on the rail had dragged through the QR code in a horizontal line - not through the timing section, but enough to make it unreadable. Fortunately, the model is identifiable visually on the mfr's site, so I can be sure what kind of safety goggles I need!)
Yeah datamatrix, IMHO, is superior: more density and you got options for rectangular rather than just square symbols.
The finder and alignment patterns in QR-code just take up space and don't seem to help very much, but I can't back that up. Maybe some scanners can really do better with QR?
The finder and alignment patterns in QR-code just take up space and don't seem to help very much, but I can't back that up. Maybe some scanners can really do better with QR?
> [...] a screw on the rail had dragged through the QR code in a horizontal line - not through the timing section, but enough to make it unreadable.
Given that two timing patterns are perpendicular to each other, how is that possible? Did the line come from the rightmost boundary and stop before the vertical timing pattern? Then there should be no real difficulty in reading that and it might well be a decoder problem.
Given that two timing patterns are perpendicular to each other, how is that possible? Did the line come from the rightmost boundary and stop before the vertical timing pattern? Then there should be no real difficulty in reading that and it might well be a decoder problem.
Very interesting but since (my) iPhones can't use / read them, out of the box, there is very little change I will be using them anytime soon.
"Creating a QR Code step by step" https://www.nayuki.io/page/creating-a-qr-code-step-by-step
> The way this works is actually really really complex so I'll leave that out.
Bruh that's the whole reason I read the article. That's what I wanted to know.
Bruh that's the whole reason I read the article. That's what I wanted to know.
In Dan Hollick's article:
> There is still a bunch of left over space after our data. This is where the error correction information is stored so that it can be read if partially obscured. The way this works is actually really really complex so I'll leave that out.
I find myself guilty of leaving it out of my page too, writing:
> (Note: The math behind computing the Reed-Solomon error correction codes is omitted because it is long, tedious, and not very interesting.)
Since there is some interest, let me try to explain a bit. Conceptually, it's simple. Put the data bytes (e.g. [A, B, C, D]) into polynomial coefficients (e.g. Ax^3 + Bx^2 + Cx^1 + Dx^0). Compute the Reed-Solomon generator polynomial, which is just a bunch of (x - a_i) terms multiplied together. Then divide your data polynomial by the generator polynomial, keep only the remainder (not the quotient), and that is your ECC polynomial. The catch is that all the polynomial coefficients take place over a finite field, which is a second layer of difficulty when it comes to explaining the math.
> There is still a bunch of left over space after our data. This is where the error correction information is stored so that it can be read if partially obscured. The way this works is actually really really complex so I'll leave that out.
I find myself guilty of leaving it out of my page too, writing:
> (Note: The math behind computing the Reed-Solomon error correction codes is omitted because it is long, tedious, and not very interesting.)
Since there is some interest, let me try to explain a bit. Conceptually, it's simple. Put the data bytes (e.g. [A, B, C, D]) into polynomial coefficients (e.g. Ax^3 + Bx^2 + Cx^1 + Dx^0). Compute the Reed-Solomon generator polynomial, which is just a bunch of (x - a_i) terms multiplied together. Then divide your data polynomial by the generator polynomial, keep only the remainder (not the quotient), and that is your ECC polynomial. The catch is that all the polynomial coefficients take place over a finite field, which is a second layer of difficulty when it comes to explaining the math.
> Barcodes were proving inadequate - they can only be read at certain angles and didn't store much data relative to their size
It's the scanner that dictates what angles a barcode can be read at. A 2D barcode scanner (which you need to read QR codes AT ALL -- or even a smart phone running Cognex's barcode scanner app) can read regular 1D barcodes from absolutely any orientation.
You can reduce the size of 1D barcodes to increase data density:
http://www.barcodebootcamp.com/labels/barcode-density.html
It's rarely done because easy decoding is usually the priority.
Plus, you can make 1D barcodes extremely small vertically, as commonly seen on the edge of USPS envelopes:
https://www.wsel.com/sites/default/files/IntelligentMailBarc...
...and that way store several lines of 1D codes holding much more information in the space of one QR code.
2D codes are useful in some circumstances, but they're not better than 1D barcodes.
It's the scanner that dictates what angles a barcode can be read at. A 2D barcode scanner (which you need to read QR codes AT ALL -- or even a smart phone running Cognex's barcode scanner app) can read regular 1D barcodes from absolutely any orientation.
You can reduce the size of 1D barcodes to increase data density:
http://www.barcodebootcamp.com/labels/barcode-density.html
It's rarely done because easy decoding is usually the priority.
Plus, you can make 1D barcodes extremely small vertically, as commonly seen on the edge of USPS envelopes:
https://www.wsel.com/sites/default/files/IntelligentMailBarc...
...and that way store several lines of 1D codes holding much more information in the space of one QR code.
2D codes are useful in some circumstances, but they're not better than 1D barcodes.
I used this tech from denso wave to create a neat service which provides an easy way to create qr codes which lead to a pdf file you upload, and the file can be later replaced/updated while retaining the same qr code, which comes in handy for printed qr codes (brochures, posters, manuals etc): https://pdf2qrcode.com/
QR codes just embed a url, so as long as you can change what you get when you open a url any service can do this, or even any old hosting service.
The only annoying thing with QR codes is that they're limited to text formats, so I came up with a little tweak to support encoding ad-hoc hierarchical binary data into QR codes awhile back: https://www.technicalsourcery.net/posts/qr-superpowers/
QR codes do support arbitrary binary data in 8 bit mode. Programs such as qrencode also allow the creation of 8 bit QR codes. It's almost always the QR decoder that's limited to text formats because they assume the data is text.
I submitted some patches to ZBar to improve this. See also my answer to this stack overflow question:
https://stackoverflow.com/a/60518608/512904
I don't understand what you mean by this:
> Although the QR format does have an encoding called “byte mode”, each byte in this mode represents an ISO 8859-1 character, not binary data.
I've read the standard but I didn't get the impression that the 8 bit encoding mode was assumed to be text. Can you cite the part that says this?
I submitted some patches to ZBar to improve this. See also my answer to this stack overflow question:
https://stackoverflow.com/a/60518608/512904
I don't understand what you mean by this:
> Although the QR format does have an encoding called “byte mode”, each byte in this mode represents an ISO 8859-1 character, not binary data.
I've read the standard but I didn't get the impression that the 8 bit encoding mode was assumed to be text. Can you cite the part that says this?
base45 is preferred (it was used for the EU COVID certificates) as the binary mode isn't reliable.
It seems okay at least to me.
I looked up what the standard says:
> The default interpretation for QR Code is ECI 000020 representing the JIS8 and Shift JIS character sets.
> 8.3.4 8-bit Byte Mode
> The 8-bit byte mode handles the 8-bit Latin/Kana character set in accordance with JIS X 0201 (character values 00HEX to FFHEX).
> In this mode data is encoded at a density of 8 bits/character.
> 8.4.4 8-bit Byte Mode
> In this mode, one 8 bit codeword directly represents the JIS8 character value of the input data character as shown in Table 6, i.e. a density of 8 bits/character.
> In ECIs other than the default ECI, it represents an 8-bit byte value directly.
So it's just an 8 bit value that may or may not represent a JIS8 character. The referenced table 6 is a lot like the table in the article linked above but for JIS8 instead. There are reserved/unused characters but I didn't get the impression that they were invalid. It seems contradictory to me to prohibit the use of bytes which may be in use in the future. Is this incorrect?
https://en.wikipedia.org/wiki/JIS_X_0208#Unassigned_code_poi...
Gives me the same impression. Plenty of "should not"s and even historical examples where people did something with those characters anyway. So it didn't seem like a big deal to me that binary data might contain those bytes. It even says many unassigned characters were assigned in newer standards which also happens often in Unicode.
The RFC for base 45 is interesting too:
https://datatracker.ietf.org/doc/rfc9285/
> Even in Byte mode, a typical QR code reader tries to interpret a byte sequence as text encoded in UTF-8 or ISO/IEC 8859-1.
> Thus, QR codes cannot be used to encode arbitrary binary data directly.
The implication being that it would work if only we could fix those decoders so they stop trying to convert data to text.
That's been my exact experience. The binary decoding problems in zbar were due to character encoding conversion attempts. I just made it output the bytes unchanged and it worked perfectly with arbitrary binary data. I also studied zxing-cpp and it does both: it converts the binary data to text and keeps a copy of the original bytes. There's even comments saying the standard isn't clear.
I looked up what the standard says:
> The default interpretation for QR Code is ECI 000020 representing the JIS8 and Shift JIS character sets.
> 8.3.4 8-bit Byte Mode
> The 8-bit byte mode handles the 8-bit Latin/Kana character set in accordance with JIS X 0201 (character values 00HEX to FFHEX).
> In this mode data is encoded at a density of 8 bits/character.
> 8.4.4 8-bit Byte Mode
> In this mode, one 8 bit codeword directly represents the JIS8 character value of the input data character as shown in Table 6, i.e. a density of 8 bits/character.
> In ECIs other than the default ECI, it represents an 8-bit byte value directly.
So it's just an 8 bit value that may or may not represent a JIS8 character. The referenced table 6 is a lot like the table in the article linked above but for JIS8 instead. There are reserved/unused characters but I didn't get the impression that they were invalid. It seems contradictory to me to prohibit the use of bytes which may be in use in the future. Is this incorrect?
https://en.wikipedia.org/wiki/JIS_X_0208#Unassigned_code_poi...
Gives me the same impression. Plenty of "should not"s and even historical examples where people did something with those characters anyway. So it didn't seem like a big deal to me that binary data might contain those bytes. It even says many unassigned characters were assigned in newer standards which also happens often in Unicode.
The RFC for base 45 is interesting too:
https://datatracker.ietf.org/doc/rfc9285/
> Even in Byte mode, a typical QR code reader tries to interpret a byte sequence as text encoded in UTF-8 or ISO/IEC 8859-1.
> Thus, QR codes cannot be used to encode arbitrary binary data directly.
The implication being that it would work if only we could fix those decoders so they stop trying to convert data to text.
That's been my exact experience. The binary decoding problems in zbar were due to character encoding conversion attempts. I just made it output the bytes unchanged and it worked perfectly with arbitrary binary data. I also studied zxing-cpp and it does both: it converts the binary data to text and keeps a copy of the original bytes. There's even comments saying the standard isn't clear.
You probably want to learn about base45 [1] instead, which is exactly designed for the alphanumeric mode of QR code.
[1] https://www.rfc-editor.org/rfc/rfc9285.html
[1] https://www.rfc-editor.org/rfc/rfc9285.html
Base45 is an inefficient way to store binary data, as are all of the BaseXYZ encodings that by all rights should already be relegated to the dustbin of history in the 21st century...
Unlike many baseXX encodings, base45 has an advantage of actually being undone by the alphanumeric mode. Granted, it is still unfortunate that base45 has its uses (because many QR decoders do not properly handle 8-bit data) but inefficiency is not its deficiency.
Oh yes sorry you're right. When using alphanumeric mode you only get a small amount of binary encoding bloat (3%) with base45.
But even with binary data encoded to baseXX, you still need to decide what the byte stream means. I was mainly looking at how to efficiently encode a hierarchical document containing the most common data types (that anyone can decode and inspect) into a QR code.
But even with binary data encoded to baseXX, you still need to decide what the byte stream means. I was mainly looking at how to efficiently encode a hierarchical document containing the most common data types (that anyone can decode and inspect) into a QR code.
> because many QR decoders do not properly handle 8-bit data
We should fix that! Which QR decoders still lack support for binary data decoding?
I submitted patches to zbar to add a binary decoding mode, it's already available in new versions. ZXing and zxing-cpp also have support.
Maybe it's the camera apps that lack support for this.
We should fix that! Which QR decoders still lack support for binary data decoding?
I submitted patches to zbar to add a binary decoding mode, it's already available in new versions. ZXing and zxing-cpp also have support.
Maybe it's the camera apps that lack support for this.
Check out PagedOut! issue #2, page 19 (https://pagedout.institute/download/PagedOut_002_beta2.pdf)
I knew they would skimp on explaining the Reed-Solomon code... :^)
Had to build a barcode scanner for smartphone cameras, and I can tell you, QR codes are another level.
More data AND error correction.
More data AND error correction.
It's crazy how they never patented it
From the wiki:
Denso Wave owns a number of patents on QR code technology, but has chosen to exercise them in a limited fashion. In order to promote widespread usage of the technology Denso Wave chose to waive its rights to a key patent in its possession for standardized codes only. In the US, the granted QR code patent is US 5726435, and in Japan JP 2938338, both of which have expired. The European Patent Office granted patent EP 0672994 to Denso Wave, which was then validated into French, UK, and German patents, all of which expired in March 2015.
Denso Wave owns a number of patents on QR code technology, but has chosen to exercise them in a limited fashion. In order to promote widespread usage of the technology Denso Wave chose to waive its rights to a key patent in its possession for standardized codes only. In the US, the granted QR code patent is US 5726435, and in Japan JP 2938338, both of which have expired. The European Patent Office granted patent EP 0672994 to Denso Wave, which was then validated into French, UK, and German patents, all of which expired in March 2015.
This is also greatly covered in the second edition of Charles Petzold's Code.
Somebody please update the wikipedia article about this!
Fasincating.
The images on this site are pretty useless on mobile: you can't zoom on the site nor the modal that appears on click.
[deleted]
The whole "ever wondered/no me neither" / "I know these sound super fucking boring" attitude is extremely off-putting to me. Yes I've wondered! I wonder about a lot of things! It doesn't sound boring at all! It reads like badly written kids' science books which start with the presupposition that "you think science is boring and I have to convince you otherwise" instead of just ... not doing that.
"Please don't pick the most provocative thing in an article or post to complain about in the thread. Find something interesting to respond to instead."
"Please don't fulminate."
https://news.ycombinator.com/newsguidelines.html
One reason we have those guidelines is that comments like this tend to get upvoted to the top of threads, where they sit gathering mass, letting off fumes, and choking out more interesting discussion. That's where this one was when I saw it a moment ago. Unfortunately, it takes manual intervention to do anything about, which is scarce and intermittent at best.
"Please don't fulminate."
https://news.ycombinator.com/newsguidelines.html
One reason we have those guidelines is that comments like this tend to get upvoted to the top of threads, where they sit gathering mass, letting off fumes, and choking out more interesting discussion. That's where this one was when I saw it a moment ago. Unfortunately, it takes manual intervention to do anything about, which is scarce and intermittent at best.
I like to think of this as the YouTube-ification of blogs.
You won't believe how genius QR codes try not to laugh at this one weird trick you'll HATE! :-o
Alternatively, I appreciate the author injecting a bit of personality into an otherwise "boring" topic.
Writing with personality is great, but if the very first sentence of a work is essentially there to downplay the very topic it talks about, then how does that help the content whatsoever?
It kind of reminds me of people showing you art they've made, or a meal they've cooked, who feel the need to start off by saying "I know it's super bad / don't expect much / I really messed up".
– If the thing is indeed bad, then the comment won't save it. Furthermore, I might question why you're showing this thing to me in the first place if you don't believe in it yourself?
– If the thing is actually good, then I get the impression you're just self-deprecating for no reason… Possibly looking for attention? It could also make me look for flaws where I otherwise wouldn't, just for the sake of it, because you have now convinced me — at least subconsciously — that your creation sucks.
Bottom line being: Let the content speak for itself, and leave it up to the audience to decide whether something is interesting or not.
It kind of reminds me of people showing you art they've made, or a meal they've cooked, who feel the need to start off by saying "I know it's super bad / don't expect much / I really messed up".
– If the thing is indeed bad, then the comment won't save it. Furthermore, I might question why you're showing this thing to me in the first place if you don't believe in it yourself?
– If the thing is actually good, then I get the impression you're just self-deprecating for no reason… Possibly looking for attention? It could also make me look for flaws where I otherwise wouldn't, just for the sake of it, because you have now convinced me — at least subconsciously — that your creation sucks.
Bottom line being: Let the content speak for itself, and leave it up to the audience to decide whether something is interesting or not.
> if the very first sentence of a work is essentially there to downplay the very topic it talks about, then how does that help the content whatsoever?
It signifies 'you may not think you are going to find this interesting, you may not be very technical - but trust me, I'm like you and you will find it interesting - and this article will be written in plain, colloquial english which you are likely to understand with a bit of humour'.
It may not work for you, but it provides reassurance for other readers, such as - me.
It signifies 'you may not think you are going to find this interesting, you may not be very technical - but trust me, I'm like you and you will find it interesting - and this article will be written in plain, colloquial english which you are likely to understand with a bit of humour'.
It may not work for you, but it provides reassurance for other readers, such as - me.
I found them super funny! Bazinga! xD /s
On a more serious note, I know someone who does this kind of talk in real life, 24/7. He's insufferable.
On a more serious note, I know someone who does this kind of talk in real life, 24/7. He's insufferable.
QR code works similarly to barcodes at the super-market. Every QR code consists black squares and dots and they represent different pieces of information. When scanned, unique pattern on the barcode translates into human-readable data. This transaction happens in seconds.
Creative stuff, built on a robust standard.
https://twitter.com/zackfreedman/status/1517555638456389632?...