QR error correction helps and hinders scanning

Error correction sounds good. It means fewer errors, right? When it comes to QR codes, that’ll mean easier scanning for people, surely? It seems like that’s not the whole story.

I wondered about this, and couldn’t find an answer, so I did some exploration, and found there’s two factors in tension: the error correction on one hand, and the resulting data density on the other:

1. For fixed data, like a particular URL, it’s easier to read a QR code with lower error correction, but only when there’s minimal damage to the code (like reflections and dirt).
2. Error correction works as advertised when there’s damage: higher error correction means more codes can be read.

The rest of this article explores what this means.

Quick intro to quick response

QR (quick response) codes are now extremely widespread in Australia, because they’re used for COVID contact tracing check-ins and placed in every shop window, but they’re somewhat magic. Before diving into the details, Wikipedia says a whole lot about QR codes; the summary is: a QR code is a pattern of black and white squares that encodes some data (often a URL), that cameras can read.

The article even has diagrams. Here’s one with a whole lot of detail, highlighting a bunch of key concepts going into a QR code, however there’s two that are most important when considering how easy it is to scan a QR code: version and error correction.

What are these two factors?

• error correction (EC): a measure of redundancy in the QR code, translating into how much “damage” it can tolerate and still be readable. This is how images and logos can be directly embedded into QR codes, without any special consideration. This is chosen when creating the QR code. The number of modules that can be damaged for each level is:

  EC	max damage
  L (low)	7%
  M (medium)	15%
  Q (quartile)	25%
  H (high)	30%

• version: the number of little squares (modules) along each side of the big square. This is normally computed automatically when creating the QR code (from the data and error correction).

  version	modules
  1	21
  2	25
  …	…
  n	4n + 17
  …	…
  39	173
  40	177

Together, the version and error correction dictate how much data a given QR code can store⁰:

(The plots in this article are interactive: hover/tap for more info, tap or double tap the legend to toggle series’ visibility, tap-and-drag to zoom, and hit the ‘home’ icon to reset.)

That plot indicates a QR code using EC level H can store less than half the data of one using level L: the closest they get is at version 3 (53 vs. 24 bytes). The other levels have less overhead, but it’s still a cost that’s paid:

That’s some hefty overhead: presumably it is useful for something… I did some experiments.

Experiments

I set up a little Rust program that ran ZBar against an exhaustive set of different QR configurations: all 40 versions and all 4 EC levels. For each of these 160 configurations:

1. scale the QR code to given size
2. place it into a background image, to simulate “real world” conditions
3. pass the resulting image into ZBar and check if it scans successfully
4. repeat at different sizes to find the smallest size at which the QR code scans successfully, or determine that it couldn’t be scanned at any size

Error correction makes scanning more reliable

Error correction sounds useful for scanning: if the QR code is further away or smaller, then there’s more likely to be blurriness or other “damage”, and so higher error-correction will make it easier to read… right?

A camera generally doesn’t care about the actual distance, as it just “thinks” in the pixels it sees. Thus, it’s the size of the QR code within the overall image that matters. I call this the field of view. Example, for the full sized version of Figure 4:

Under the reasonable assumption that the camera is close to rectilinear, this gives a measure of how close the user has to be that scales smoothly with the physical size of the QR code: if the device can read a 10cm QR code from 1m away, it’ll be able to read a 1m code from 10m. Similarly, fields of view can be used to predict distance: given two codes, where the first needs 4% field of view and the second only needs 1%, the second can likely be scanned from about twice as far¹.

Error correction definitely allows scanning a given QR code from further away. At version 40, a level H QR code only requires 1.7% field of view, while a level L one requires 2.4%.

This seems to all come back to the size of the individual modules (the small squares that make up the overall QR code):

The lines of best fit look pretty flat, and quantitative measures like the parameter confidence intervals agree (except for level L, the 95% confidence intervals on the slope coefficient include 0). In other words: a QR code is scannable if its modules are sufficiently large, and that size threshold doesn’t change much as the version changes.

On the other hand, the size threshold does change with EC level: level L modules need to be 25-35% larger than level H ones, matching the intuition about the benefits of higher error correction.

Cool, hypothesis confirmed: error correction makes scanning more reliable…

Error correction makes scanning less reliable

Not so fast! When creating a QR code, versions and module sizes usually don’t matter, it’s the data that matters: one will usually choose the data and error correction, and then have the version computed automatically, as the smallest that works.

The overhead of higher error correction matters a lot.

If we change from looking at the version to the actual data stored, the ordering reverses, and EC level L works best!

If one is trying to “send” 1000 bytes via QR code, using level H requires a field of view of 1.4%, while level L only needs half that (approximately), at 0.8%. This means a device can be further away and still read the L code successfully.

This doesn’t seem to match the results in Figures 5 and 6. What’s going on? The level L code uses version 22 with 105² ≈ 11k modules, while level H requires version 36 with 161² ≈ 26k modules. This ratio (2.35) is much larger than the ratio between the module sizes (~1.3), so, sure, level H allows the individual modules to be smaller, but it requires using so many more that the overall QR code is larger than the level L ones².

This seems to apply consistently across versions, as might be expected from Figure 3: a QR code at level L can store twice as much data as one at level H, for the same version. The data storage overhead of error correction doesn’t seem be worth the apparently dubious benefits.

Nice. This hypothesis—error correction makes scanning less reliable—is correct, right?

Error correction really does make scanning more reliable

There is more to the story. Those measures had no noise introduced to the QR codes. They’re the easy cases. What happens if we turn up the noise?

I generated 10 different noise patterns, and thresholded them at 8 different levels, and overlaid this noise across each of the QR codes, for a total of 160 × 80 = 12800 configurations. This is meant to simulate reflections and dirt that could make it harder for a device to read the code.

Across all of these experiments, 60% more EC level H QR codes could be scanned successfully than level L ones:

This is driven by resilience to damage: the QR code at level H is more likely to be able to be read when there’s significant damage. The following plot has a point for each successful scan, against the percentage of pixels damaged.

Under these experimental conditions, level L codes become much less readable above ~6% damage, level M above ~12%, level Q above ~18% and level H above ~20%. This correlates with the resilience I quoted in the table above.

Conclusion

I’ve learnt that the four different QR error correction levels influence both data volume and ability to scan. For a given QR version, increasing error correction allows storing less data, but makes scanning easier and more reliable. However, for storing a fixed amount of data, like a particular URL, the version is computed automatically, and the easier scanning can trade off against the data volume. This ties back to the size of the individual modules (little squares): there is a minimum certain size before a code is scannable, and so a denser code needs to be larger.

Experimental caveats

The results I’ve talked about here are all empirical, and there’s a bunch of reasons that they’re not perfect:

1. I tested only one method of reading QR codes, ZBar, although some quick experiments with my iPhone seem to correlate with the results here.
2. I also tested only one background image, so the behaviour may differ greatly with QR codes contained in different surrounds.
3. The QR codes are generated to be perfectly rectangular and aligned to the image pixel grid, which is unlikely to happen in the real world.
4. The noise generated is random Perlin noise, which isn’t likely to be what occurs in the real world.
5. The overlaying of the noise carefully skips damaging the position patterns (the big squares in three corners), because the performance is catastrophically worse if they can be damaged too.