9 ms·
How a QR code works
- amenghra 4y agoCheck out PagedOut! issue #2, page 19 (https://pagedout.institute/download/PagedOut_002_beta2.pdf https://pagedout.institute/download/PagedOut_002_beta2.pdf)
- rhn_mk1 4y agoWhat 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.
- ajhurliman 4y agoConvert 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).
- lifthrasiir 4y agoIn 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).
- ajhurliman 4y agoYou 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.
- lifthrasiir 4y ago> 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.
- lordnacho 4y agoI 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}
- lifthrasiir 4y agoAs 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?
- theideaofcoffee 4y agoI 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.
- Kaibeezy 4y agoThird. I’m not even tech side and this stopped short just when it was getting interesting. The global cumulative IQ is melting :(
- entangledqubit 4y agoA 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.
- sa1 4y agoThis explainer goes into the math: https://atcm.mathandtech.org/EP2021/invited/21891.pdf https://atcm.mathandtech.org/EP2021/invited/21891.pdf Or an explainer for Reed-Solomon codes: https://sidewords.files.wordpress.com/2007/12/thesis.pdf https://sidewords.files.wordpress.com/2007/12/thesis.pdf
- emilecantin 4y agoI'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.
- jrm4 4y agoNot 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.
- ajhurliman 4y agoIf 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.
- UpstandingUser 4y ago> they eventually just gave me a beer and put a tally mark on a notepad oof
- systemvoltage 4y ago
- deleted 4y ago[deleted]
- tirusaquce 4y agoPeople have been claiming society is degenerating for as long as there's been society. It may not be proceeding in a direction you like, but that doesn't mean it's degenerating.
- collyw 4y agoSociety objectively degenerated since the start of the covid scam. To pretend otherwise in being willfully blind to the changes we saw. Unchecked authoritarianism in democratic countries. House arrest of healthy people. Telling people that they do not have the right to run a legal business. Heavy censorship and lack of debate. Treating others as vectors of disease instead of fellow humans is not in any way positive for society. Coercion of a rushed, not fully tested "vaccine" onto a general public, the vast majority of whom did not need it. We have demonized having a common cold, while at the same time normalized young people having heart attacks and stokes. Since the vaccine rollout excess deaths are not notably down, so it's very debatable that they have "saved lives". https://www.euromomo.eu/graphs-and-maps#excess-mortality https://www.euromomo.eu/graphs-and-maps#excess-mortality All for what objectively amounts to a bad flu - age adjusted 2020 showed the same number of deaths as 2008 in the UK. 2003 in terms of non adjusted numbers.
- theophrastus 4y agoLately 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%20code https://www.google.com/search?tbm=isch&q=circular%20qr%20cod...
- doodlesdev 4y agoI 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-codes-to-create-circles-are-corners-necessary https://stackoverflow.com/questions/66837985/damaging-qr-cod...
- yboris 4y agoI 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://videohubapp.com/ & https://github.com/whyboris/Video-Hub-App https://github.com/whyboris/Video-Hub-App & https://github.com/whyboris/Video-Hub-App-remote https://github.com/whyboris/Video-Hub-App-remote
- bo1024 4y agoNice. 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/ https://pypi.org/project/qrcode/
- yboris 4y agoFor JS I used the npm package an-qrcode https://www.npmjs.com/package/an-qrcode https://www.npmjs.com/package/an-qrcode :)
- hbn 4y agoThat'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
- countmora 4y agoThis is also greatly covered in the second edition of Charles Petzold's Code.
- Darkphibre 4y agoThis animated QR code has every frame scannable. It seems to be selecting different correction levels and bitmasks to aid in randomizing the noise. Also note that the timing blocks are relatively huge... so I suspect they are relying on 'pixel' modules being averaged and then thresholded (and when that doesn't work, they'll just allow some modules to be corrupted and rely on the error correction to read other pixels. Creative stuff, built on a robust standard. https://twitter.com/zackfreedman/status/1517555638456389632?s=20&t=nx1ZXYk11DS48C8QLCuYJw https://twitter.com/zackfreedman/status/1517555638456389632?...
- kingforaday 4y agoWell played.
- nayuki 4y ago"Creating a QR Code step by step" https://www.nayuki.io/page/creating-a-qr-code-step-by-step https://www.nayuki.io/page/creating-a-qr-code-step-by-step
- kstenerud 4y agoThe 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/ https://www.technicalsourcery.net/posts/qr-superpowers/
- arcastroe 4y agoHow does this compare against simply encoding the binary data in base64?
- pkulak 4y ago30% more efficient, I'd guess.
- matheusmoreira 4y agoQR 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 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?
- tiagod 4y agobase45 is preferred (it was used for the EU COVID certificates) as the binary mode isn't reliable.
- matheusmoreira 4y agoIt 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_points 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/ 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.
- boringg 4y agoFasincating.
- dmd 4y agoThe 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.
- addisonl 4y agoAlternatively, I appreciate the author injecting a bit of personality into an otherwise "boring" topic.
- isametry 4y agoWriting 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.
- Angostura 4y ago> 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.
- k__ 4y agoHad to build a barcode scanner for smartphone cameras, and I can tell you, QR codes are another level. More data AND error correction.
- dt3ft 4y agoI 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/ https://pdf2qrcode.com/
- treve 4y agoQR 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.
- iyedgivehead 4y agoIt's crazy how they never patented it
- chunkyguy 4y agoFrom 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.
- dublin 4y agoFWIW, 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!)
- lifthrasiir 4y ago> [...] 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.
- crispyambulance 4y agoYeah 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?
- WelcomeShorty 4y agoVery 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.
- aaaaaaaaaaab 4y agoI knew they would skimp on explaining the Reed-Solomon code... :^)
- nayuki 4y agoThis is what explanations look like: https://www.nayuki.io/page/reed-solomon-error-correcting-code-decoder https://www.nayuki.io/page/reed-solomon-error-correcting-cod... , https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders#Finite_field_arithmetic https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_f... , https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders#Reed%E2%80%93Solomon_codes https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_f...
- steve_john 4y agoQR 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.
- marcodiego 4y agoSomebody please update the wikipedia article about this!
- axiolite 4y ago> 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 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/IntelligentMailBarcode_LandingPage.png 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.
- hyperhopper 4y agoThe images on this site are pretty useless on mobile: you can't zoom on the site nor the modal that appears on click.
- deleted 4y ago[deleted]
- hyperhopper 4y ago> 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.
- nayuki 4y agoIn 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.
- designerdada 4y ago