[HN Gopher] How a QR code works
___________________________________________________________________
How a QR code works
Author : todsacerdoti
Score : 188 points
Date : 2022-09-14 14:17 UTC (8 hours ago)
(HTM) web link (typefully.com)
(TXT) w3m dump (typefully.com)
| dt3ft wrote:
| 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/
| dmd wrote:
| 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.
| MisterSandman wrote:
| I like to think of this as the YouTube-ification of blogs.
| aaaaaaaaaaab wrote:
| 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.
| dang wrote:
| " _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.
| addisonl wrote:
| Alternatively, I appreciate the author injecting a bit of
| personality into an otherwise "boring" topic.
| isametry wrote:
| 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.
| aaaaaaaaaaab wrote:
| I knew they would skimp on explaining the Reed-Solomon code...
| :^)
| rhn_mk1 wrote:
| 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.
| ajhurliman wrote:
| 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).
| sophacles wrote:
| 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;".
| ajhurliman wrote:
| 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...
| guhidalg wrote:
| It really is draw the rest of the owl, here's a good place
| to start https://en.wikipedia.org/wiki/Feature_(computer_vi
| sion)#Dete...
|
| In computer vision there is no magic bullet, you will have
| to sink deep into the details.
| sophacles wrote:
| 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?
| guhidalg wrote:
| It's not a small problem, I'm just warning you. Check the
| chromium source for their shape detection API: https://so
| urce.chromium.org/chromium/chromium/src/+/main:ser...
| trevorhlynn wrote:
| 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).
| lifthrasiir wrote:
| 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).
| lordnacho wrote:
| 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}
| lifthrasiir wrote:
| 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?
| sophacles wrote:
| 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?
| lifthrasiir wrote:
| 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
| sophacles wrote:
| I see, fair enough. I've used your library in the past,
| so thanks for that, and also thanks for the insight that
| writing my own toy qr generator might help me understand
| the reading process. :)
| ajhurliman wrote:
| 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.
| lifthrasiir wrote:
| > 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.
| dublin wrote:
| 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.
| emilecantin wrote:
| 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 moire 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.
| entangledqubit wrote:
| 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.
| jrm4 wrote:
| 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.
| sa1 wrote:
| 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
| theideaofcoffee wrote:
| 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.
| Kaibeezy wrote:
| Third. I'm not even tech side and this stopped short just
| when it was getting interesting. The global cumulative IQ is
| melting :(
| kstenerud wrote:
| 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/
| matheusmoreira wrote:
| 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?
| arcastroe wrote:
| How does this compare against simply encoding the binary data
| in base64?
| pkulak wrote:
| 30% more efficient, I'd guess.
| lifthrasiir wrote:
| 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
| ajhurliman wrote:
| 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.
| hbn wrote:
| 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)
| mbesto wrote:
| Adoption != technical capability.
|
| The OP is talking about adoption.
| hbn wrote:
| Apple wouldn't implement the capability if they didn't
| think it had the adoption
| mbesto wrote:
| Just like when they automatically added the U2 album to
| everyones phone? Apple isn't immune.
| moduspol wrote:
| 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.
| systemvoltage wrote:
| [deleted]
| tirusaquce wrote:
| People 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.
| LtWorf wrote:
| 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.
| furyofantares wrote:
| 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.
| latchkey wrote:
| > 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...
| djbeadle wrote:
| 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...
| latchkey wrote:
| Yes, that's where I heard about this problem. Sketchy
| indeed.
| bobbylarrybobby wrote:
| 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.
| CamelCaseName wrote:
| 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!)
| s1mon wrote:
| 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.
| UpstandingUser wrote:
| > they eventually just gave me a beer and put a tally mark on a
| notepad
|
| oof
| k__ wrote:
| Had to build a barcode scanner for smartphone cameras, and I can
| tell you, QR codes are another level.
|
| More data AND error correction.
| dublin wrote:
| 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!)
| lifthrasiir wrote:
| > [...] 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.
| nayuki wrote:
| "Creating a QR Code step by step"
| https://www.nayuki.io/page/creating-a-qr-code-step-by-step
| iyedgivehead wrote:
| It's crazy how they never patented it
| theophrastus wrote:
| 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...
| doodlesdev wrote:
| 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...
| countmora wrote:
| This is also greatly covered in the second edition of Charles
| Petzold's Code.
| amenghra wrote:
| Check out PagedOut! issue #2, page 19
| (https://pagedout.institute/download/PagedOut_002_beta2.pdf)
| dfc wrote:
| The QR code is on page 20;)
|
| I have never heard of Paged Out. It looks neat. I hope they are
| still putting out issues.
| boringg wrote:
| Fasincating.
| Darkphibre wrote:
| This 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?...
| yboris wrote:
| 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
| bo1024 wrote:
| 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/
| yboris wrote:
| For JS I used the npm package _an-qrcode_
| https://www.npmjs.com/package/an-qrcode :)
| hbn wrote:
| 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
___________________________________________________________________
(page generated 2022-09-14 23:00 UTC)