6 ms·

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 4y ago
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).
- lifthrasiir 4y ago
  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).
  - ajhurliman 4y ago
    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 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 ago
    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 4y ago
      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 4y ago
  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;".
  - guhidalg 4y ago
    It really is draw the rest of the owl, here's a good place to start https://en.wikipedia.org/wiki/Feature_(computer_vision)#Detection 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.
    - sophacles 4y ago
      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?
      - trevorhlynn 4y ago
        This paper (https://link.springer.com/chapter/10.1007/978-3-030-57058-3_34 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 https://github.com/nimiq/qr-scanner).
      - guhidalg 4y ago
        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:services/shape_detection/ https://source.chromium.org/chromium/chromium/src/+/main:ser...
  - 4y ago
- dublin 4y ago
  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.
theideaofcoffee 4y ago
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 4y ago
  Third. I’m not even tech side and this stopped short just when it was getting interesting. The global cumulative IQ is melting :(
entangledqubit 4y ago
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.
sa1 4y ago
This 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 ago
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.
jrm4 4y ago
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.

ajhurliman 4y ago

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).

lifthrasiir 4y ago
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).
- ajhurliman 4y ago
  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 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 ago
  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 4y ago
    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 4y ago
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;".
- guhidalg 4y ago
  It really is draw the rest of the owl, here's a good place to start https://en.wikipedia.org/wiki/Feature_(computer_vision)#Detection 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.
  - sophacles 4y ago
    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?
    - trevorhlynn 4y ago
      This paper (https://link.springer.com/chapter/10.1007/978-3-030-57058-3_34 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 https://github.com/nimiq/qr-scanner).
    - guhidalg 4y ago
      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:services/shape_detection/ https://source.chromium.org/chromium/chromium/src/+/main:ser...
- 4y ago
dublin 4y ago
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.

theideaofcoffee 4y ago

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 4y ago
Third. I’m not even tech side and this stopped short just when it was getting interesting. The global cumulative IQ is melting :(

entangledqubit 4y ago

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.

sa1 4y ago

This 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 ago

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.

jrm4 4y ago

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.