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.
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.
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).
a) There's enough of a QR there
b) The orientation is {coords}
c) The contents are {contents}
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?
Either way, incredible design, it's mind-blowing to learn more about the elegance and level of sophistication.
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.
* 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;".
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...
In computer vision there is no magic bullet, you will have to sink deep into the details.
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?
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.
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.
Or an explainer for Reed-Solomon codes: https://sidewords.files.wordpress.com/2007/12/thesis.pdf