A QR code is mostly not read. The scanner finds the three heavy corners, squares the picture up, and then samples one point at the centre of each module — so at three pixels per module, eight pixels in nine are never looked at by anything. Andrew Taylor’s dithered QR codes put a photograph in that space, and his explanation of how is the clearest writing on the subject I have found.
What follows is his technique, rebuilt, plus the one question his page raises and does not answer: how far you can actually go. Type a URL, drop a picture in.
Drop a picture here. Nothing is uploaded — it is read, dithered and drawn in the page.
—
- correction
- —
- worst block
- —
- local error
- —
Everything runs here. The encoder, the dithering and the correction accounting are all in the page; no image is uploaded and nothing is fetched.
The part nobody reads
Two kinds of module. The function patterns — three finders, the timing lines, the alignment squares — are how a scanner locates the code and works out where the grid is, before it has read a single bit. Their shape matters at full resolution, so they are the one part a picture may never touch. Everything else is data, and data is sampled at a point.
That is the whole opening. Divide each module into a 3×3 grid, keep the centre pixel for the code, and hand the other eight to the photograph.
Solid black is structure, and no image may touch it. Every tinted tile carries one bit; the tint steps with each codeword, so a run of one tint is eight modules that stand or fall together. Point at any tile.
Turn on sampled points: those dots are the only pixels a scanner reads. Everything the dots are not is yours.
Two passes
Reducing a photograph to one bit is a solved problem with a well-known answer. Threshold each pixel and you get a silhouette; the tones are gone. Floyd–Steinberg keeps them: quantise a pixel, then push the error you just made into the neighbours you have not reached yet, so a region that was 40% grey comes out with 40% of its dots set even though no individual dot is grey.
Andrew’s contribution is to run that twice, and the second pass is the ordinary one. The first pass deals with the pixels the code has already decided. A module’s centre is not the dithering algorithm’s to choose — it is whatever the codeword says — so if the photograph wanted a bright pixel there and the code insists on a dark one, that is an error the diffusion never gets to distribute. It just sits there. Thousands of them sit there, one per module, on a regular grid, which is the worst possible arrangement for something you are trying not to notice.
So: before dithering, walk the forced pixels, compute the error each one is about to commit, and diffuse that into the free pixels around it. The neighbourhood is pre-compensated for a mistake that has not happened yet.
18.44% to 5.06% to 3.74%. The first step is dithering doing what dithering does. The second is the pre-pass, and a quarter off the remainder for one extra walk over the image is a good trade.
One detail that is mine rather than his: both passes renormalise their weights over the neighbours that are actually free. Floyd–Steinberg’s 7/3/5/1 assumes four available neighbours, and every time the sweep passes a finder pattern some of that error is pushed into a pixel that will be overwritten — which is to say, deleted. Dividing by the weight that is really there keeps it in the picture.
What a flipped module actually costs
Now the part everyone gets wrong, including me until I had the map to look at.
QR codes carry Reed–Solomon correction, and every generator in this space offers a slider that says something like proportion of pixels to change: let the picture win on the modules it disagrees with most, and let the correction clean up after you. It works, up to a point. Andrew is straight about the risk — his help text reads “this can easily render the code unscannable but might help in some cases”, his defaults are the cautious ones, level H at size 6, and the tool warns you again next to the download link. What nobody says, because nobody has the number, is where the point is.
Here is where. Reed–Solomon does not correct pixels. It corrects codewords — eight-bit symbols — and it can restore ⌊ecc/2⌋ of them per block, because locating an error costs as much as fixing it. A codeword occupies eight modules. So one wrong module and eight wrong modules in the same codeword cost the decoder exactly the same thing: one symbol.
That has an immediate consequence. Ranking modules by how badly the photograph wants them scatters your flips across the code, and a scattered flip pays full price every time. Ranking codewords — take all eight modules or none — buys up to eight modules for the price of one.
On a version-6 code at level M, ranking by codeword gives 5.4 modules per symbol spent; ranking by module gives 4.5. It is not the eight-for-one the arithmetic promises, and the reason is worth knowing: within any codeword the picture only disagrees with about half the modules, so half of what you buy was already yours. Switch the allocator in the tool above and watch the module count move while the symbols spent stays put.
The percentage slider is the wrong instrument
The bigger problem is not efficiency, it is that a percentage does not know what it is spending.
I built a harness: encode, dither, render to a bitmap with a quiet zone, and hand it to a decoder that has never heard of any of this. Then sweep. On a version-6 code carrying https://arsyad.cc/dithered-qr-codes/, taking the top slice of data modules by disagreement, this is the last setting that still decodes:
| level | budget | blind slider survives to | modules it wins | by codeword, at full budget |
|---|---|---|---|---|
| L | 2 blocks × 9 symbols | 3.50% of data modules | 52 | 101 |
| M | 4 blocks × 8 symbols | 4.75% | 69 | 172 |
| Q | 4 blocks × 12 symbols | 9.25% | 131 | 238 |
| H | 4 blocks × 14 symbols | 11.75% | 166 | 264 |
Level L is finished before four percent, in a harness with no blur, no angle and no bad light. And the figure moves around: it is not four percent of anything, it is wherever this particular picture happens to collide with this particular code, and swapping the photograph moves every row. One percent at level L is eighteen modules, and those eighteen consume five of the eighteen symbols that exist — more than a quarter of the whole account, on a control that reads 1% and offers no other number.
The right-hand column is the same code, the same picture, the same correction level, allocated by codeword under a per-block cap. Between 1.6× and 2.5× more photograph, and it decodes — and, more to the point, it decodes knowably, which the left-hand column never does at any setting.
Then the part I did not expect to be so clean. Over 492 runs across every level, every allocator and forty budget settings, the code decodes exactly when no block exceeds its own capacity — 492 out of 492, with no case of the decoder returning a wrong payload instead of failing. That is the whole scanability question reduced to one integer per block, computable before anything is rendered, and it is the number the tool prints as worst block. Push it past 100% and the readout turns and tells you the code is dead.
Which sounds like the answer to Andrew’s caveat about the stranger’s potato phone: the budget is knowable, so spend half and keep half for the crease in the flyer, the angle, the dim room. It is half the answer. A perfect reader is not a phone, and “no block over capacity” is a statement about codewords, not about photographs. So I built the other harness.
What it costs to be looked at
Render the code, then do to it what a camera in a hurry does. Tilt the plane and reproject it. Blur it. Light it unevenly across the frame, lift the black and drop the white the way glare and tired ink do, add sensor noise, and hand the decoder fewer pixels per module because the reader is standing further back. One dial drives all of it: 0 is a flat scan, 1 is a bad photograph of a creased flyer. Sixty decodes at every point.
- no picture
- nothing spent
- 25% spent
- 50% spent
- 75% spent
- 100% spent
Three findings, in the order they changed my mind.
The reserve is real, and it is monotone. Level M, halving at severity 0.84, 0.82, 0.77, 0.67, 0.54 as the budget goes from untouched to spent. Leaving correction unspent is not a superstition; it buys a measurable amount of world.
It is convex, and that is the useful part. The first quarter of the budget costs 0.02 of severity. The last quarter costs 0.13 — more than the first three quarters put together. So the rule is not “spend half”: it is that the first half is nearly free and the second half is the one you are actually trading. The tool opens at 50% for that reason.
And the picture costs before you have spent anything at all. A plain code, same version, same payload, never falls through half in this harness — still reading 75% of the time at the far end. The same code with the photograph in its free pixels and not one symbol spent halves at 0.84. That gap is the cost of asking a binariser to find module centres in a field of dither, and the per-block accounting cannot see it, because nothing is wrong with any codeword. It is the part of the answer the number in the readout does not contain, and I would not have believed how large it was without measuring it.
Then the comparison that settles the argument of the previous section. The blind percentage, wound up to the very last setting that still decodes on a clean bitmap, takes 69 modules and halves at 0.62. Allocating by codeword at half the budget takes 92 modules and halves at 0.77. More picture and more robustness, from the same code, at the same correction level — the percentage slider is not merely wasteful, it is dominated.
And one more, which fell out of switching the chart to H. Every curve moves right when you buy more correction — 0.90, 0.88, 0.85, 0.81 against M’s 0.84, 0.82, 0.77, 0.67 — except the last one. Spend the whole budget and level H halves at 0.57 where level M halves at 0.54: the same place, from four times the correction. Which is obvious once stated, and I did not see it coming. At 100% spent every block sits exactly on its correction limit whatever the limit was, so the first thing the world does to the code kills it. Buying a bigger account and then emptying it leaves you exactly where you started. The level is not what makes a code robust; the unspent part of it is.
What this still is not: one picture, one payload, one decoder, no printer, and no actual phone in an actual car park. Severity is a composite I invented, so the curves are ordinal, not calibrated. A reader who wants the absolute numbers should go and photograph one.
Props
DitheredQR
- textstringhttps://arsyad.cc
What the code encodes on load.
- idstring'dithered-qr'
Element id.
Anatomy and Diffusion each take a text and an id. All three encode in the browser, so the figures and the tool cannot disagree about what a QR code is — there is one encoder.
Notes
The encoder is mine, and that was the point. Every QR library hands back a finished matrix and throws the bookkeeping away, and the bookkeeping is the entire article: which codeword each module carries a bit of, which Reed–Solomon block that codeword belongs to. So qr.ts keeps the map. To be sure it is a QR encoder and not a plausible imitation of one, I compared it module for module against an independent implementation across all 40 versions, 4 correction levels, 8 masks and inputs covering numeric, alphanumeric, byte and UTF-8 modes: 9824 matrices, bit-identical. The first run was not — version 8 at level H came back wrong at every mask, and the cause was one digit in the block-count table, a 5 where a 6 belongs. A test that checks the output of the thing you just typed against the thing you typed it from cannot find that.
Choose the mask by the photograph, not by the spec. A QR code is XORed with one of eight patterns before it ships, and the standard picks the one that scores best on a readability heuristic. All eight are legal and all eight carry the same payload, so the heuristic is a tie-break — and there is a better one available here. Encode all eight, measure each against the picture, keep the one that already agrees with it. Free fit, no correction spent. It is on by default; turn it off and watch the module count drop.
Odd numbers of pixels per module, always. At three pixels a module the code owns the one in the middle. At five it owns one in twenty-five. At four it owns four — an even module has no centre pixel, so the sample has to be a 2×2 block straddling where the centre would be, and you have paid four times the price for the same information. The tool offers 4 so you can see it happen.
Structure to the separators, not the finders. The white ring around each finder pattern is not a function pattern in the strict sense and the generator I started from leaves it to the picture. But detection works by scanning for a 1:1:3:1
run of light and dark, and a dithered pixel touching the outside of a finder is exactly what breaks that run. It costs 45 modules across three corners to lock it, out of 1400. I locked it.The physics is right and I did not use it. Brightness comes from Rec. 709 rather than the green channel alone — a small correction on a photograph, a large one on anything saturated. Then a gamma step, and I had it at 2.2, linearising before the dither, for a reason I still believe: two dots and a gap average optically, in linear light, not in the encoded space the file was stored in. Every photograph came out as a dark mush. Linearising takes a mid-grey to 22%, and it is only the correct thing to do if the dots fuse — true in print, true at poster distance, false for a code on a screen at three pixels a module, where what you see is the dots. It is set to 1 now, for the way these actually get looked at, and the argument for 2.2 is still there waiting for the first one I have printed at A2.
Stretch the tones, or uploads are hopeless. One bit has no headroom to waste on a picture that only uses the middle of its own range. A flat, dim photograph — which most photographs are — dithers to grey mush, and the fix is not the contrast slider, it is finding where the picture’s own black and white already sit and mapping those to the ends. The clip is by percentile, 2% off each end, so one blown highlight cannot set the ceiling for everything else, and it declines to stretch anything whose range is under 0.05 because dividing by that turns sensor noise into the subject. It is the single change that made dropping an arbitrary file in worth doing.
A bug worth a patch, upstream. In fudge.ts the lock test is called as isLocked(l, y, x) while the image is indexed [y][x]. isData happens to be symmetric so it does not care, but isLocked stops being symmetric the moment rotation or mirroring is on — both of which that generator offers. Used together, the slider picks its modules from a transposed mask. It is two characters.
Two harnesses, and the second one is the one that argues. The clean-bitmap sweep establishes the ceiling: past ⌊ecc/2⌋ symbols in any one block the code is gone for everybody, and below it the code is intact for a perfect reader. That is a fact about codewords, and it is the whole of what the per-block number knows. The degradation sweep is what turns it into advice, and it is also what caught the per-block number being incomplete — the picture costs robustness before it costs a single symbol, which is a cost the accounting is structurally unable to notice. If I had shipped only the first harness I would have shipped a readout that was correct and a conclusion that was not.
The tilt is a real reprojection, not a shear. A homography fitted to four corners of a plane rotated about a random in-plane axis, with the source sampled two-by-two per output pixel. That last part is not fussiness: a tilted plane minifies its far edge, and point-sampling a minified edge produces aliasing that a decoder reads as damage. Measure that and you have measured your own resampler.
Blind’s real defeat is not the module count. Held to the last setting that decodes on a clean bitmap, the percentage slider takes 69 modules and halves at severity 0.62; allocating by codeword at half the budget takes 92 and halves at 0.77. Dominated on both axes at once — which is a stronger claim than the clean-bitmap section could make, and it only exists because the second harness does.
One file, no DOM, no dependencies. The encoder is separate because the dithering never needs to know how a QR code is built, only what the map says. This is everything else:
/**
* Error diffusion into the parts of a QR code nobody reads, plus an allocator
* that decides which parts nobody reads *hard enough*.
*
* The two-pass diffusion is Andrew Taylor's. The allocator is not: it uses the
* codeword map from qr.ts to spend Reed–Solomon correction by the symbol rather
* than by the pixel, which is the unit the correction is actually denominated
* in. See `allocate`.
*/
import type { QrCode } from './qr'
import { encodeQr, type EncodeOptions } from './qr'
export const ROLE_FREE = 0
export const ROLE_SAMPLE = 1
export const ROLE_LOCKED = 2
/**
* How to decide which modules the picture is allowed to take.
*
* `blind` is the generator this started from: rank every data module by how
* much the picture disagrees with it and take the top slice, with no reference
* to what the code can actually absorb. `pixel` is that same ranking held to
* the budget. `codeword` ranks whole codewords instead, because the budget is
* denominated in codewords.
*/
export type Allocator = 'none' | 'blind' | 'pixel' | 'codeword'
export interface Tuning {
/** Pixels per module. 3 gives each module one data pixel and eight free ones. */
scale: number
gamma: number
contrast: number
brightness: number
minInk: number
maxInk: number
/** Stretch the picture's own tonal range to fill the one bit available. */
levels: boolean
/** Pass one: pre-diffuse the modules the code has already decided. */
prePass: boolean
/** Pass two: Floyd–Steinberg over what is left. */
mainPass: boolean
allocator: Allocator
/** Fraction of each block's correction budget to spend on the picture. */
spend: number
}
export const DEFAULT_TUNING: Tuning = {
scale: 3,
gamma: 1,
contrast: 1,
brightness: 0,
minInk: 0,
maxInk: 1,
levels: true,
prePass: true,
mainPass: true,
allocator: 'codeword',
spend: 0.5
}
export interface DitherStats {
/** Modules taken from the code and given to the picture. */
modulesTaken: number
/** …of which cost nothing, being remainder bits no decoder reads. */
freeModules: number
/** Symbol errors introduced, summed over blocks. */
symbolsSpent: number
/** Symbol errors available at this version and level, summed over blocks. */
symbolsAvailable: number
/** The most-damaged block, as a fraction of its own capacity. */
worstBlock: number
correctable: number
blockCount: number
/** Mean local-brightness error against the photograph, over free pixels. */
localError: number
}
export interface DitherResult {
qr: QrCode
scale: number
/** Side length in pixels: qr.size × scale. */
size: number
/** 0 or 1 per pixel, 1 is dark. */
pixels: Uint8Array
role: Uint8Array
stats: DitherStats
}
/* --------------------------------------------------------------- the image */
/**
* sRGB to ink: 0 is paper, 1 is a full dot. Luminance is Rec.709 rather than
* the green channel alone.
*
* `gamma` is 1, which is to say the dithering happens in the encoded space
* rather than in linear light — and that is the opposite of what the physics
* says. Two dots and a gap do average in linear light, so a generator that
* linearises first is right about print and about anything seen from far
* enough away that the dots fuse. A QR code on a screen is not that: at three
* pixels a module and any size worth scanning, you see the dots, not their
* average, and linearising takes a mid-grey to 22% and every photograph with
* it. This one is set for the way these actually get looked at.
*
* Then the tones are stretched to fill the range. One bit has no headroom to
* spend on a photograph that only uses the middle of its own: a dim landscape
* dithers to a grey mush, and the fix is not more contrast, it is knowing where
* the picture's own black and white already are. The clip is by percentile so a
* single blown highlight cannot set the ceiling for everything else.
*/
export function inkFrom(image: ImageData, tuning: Tuning) {
const { gamma, contrast, brightness, minInk, maxInk, levels } = tuning
const count = image.width * image.height
const out = new Float32Array(count)
for (let i = 0; i < count; i++) {
const r = image.data[i * 4]! / 255
const g = image.data[i * 4 + 1]! / 255
const b = image.data[i * 4 + 2]! / 255
out[i] = (0.2126 * r + 0.7152 * g + 0.0722 * b) ** gamma
}
let low = 0
let high = 1
if (levels) {
const bins = 256
const histogram = new Int32Array(bins)
for (let i = 0; i < count; i++) histogram[Math.min(bins - 1, Math.max(0, Math.round(out[i]! * (bins - 1))))]!++
const cut = Math.max(1, Math.round(count * 0.02))
let seen = 0
for (let b = 0; b < bins; b++) {
seen += histogram[b]!
if (seen > cut) {
low = b / (bins - 1)
break
}
}
seen = 0
for (let b = bins - 1; b >= 0; b--) {
seen += histogram[b]!
if (seen > cut) {
high = b / (bins - 1)
break
}
}
// A flat image has nothing to stretch, and dividing by its range would turn
// sensor noise into the whole picture.
if (high - low < 0.05) {
low = 0
high = 1
}
}
const span = high - low
for (let i = 0; i < count; i++) {
let value = (out[i]! - low) / span
value = (value - 0.5) * contrast + 0.5 + brightness
let ink = 1 - value
if (ink < minInk) ink = minInk
if (ink > maxInk) ink = maxInk
out[i] = ink
}
return out
}
/** Offsets within a module that a scanner samples. */
export function centreOffsets(scale: number) {
return scale % 2 === 1 ? [(scale - 1) / 2] : [scale / 2 - 1, scale / 2]
}
function buildRoles(qr: QrCode, scale: number) {
const size = qr.size * scale
const role = new Uint8Array(size * size)
const centres = new Set(centreOffsets(scale))
for (let y = 0; y < size; y++) {
const my = Math.floor(y / scale)
const insideY = centres.has(y % scale)
for (let x = 0; x < size; x++) {
const mx = Math.floor(x / scale)
if (qr.locked[my * qr.size + mx]) role[y * size + x] = ROLE_LOCKED
else if (insideY && centres.has(x % scale)) role[y * size + x] = ROLE_SAMPLE
}
}
return role
}
/* ----------------------------------------------------------- the allocator */
/**
* Reed–Solomon corrects whole codewords. One wrong bit in a codeword and eight
* wrong bits in the same codeword cost the decoder exactly the same thing: one
* symbol. A codeword occupies eight modules, so the greedy-by-pixel approach
* pays full price for every module it takes, while taking all eight modules of
* a codeword together costs one symbol for the lot.
*
* That is the whole idea. `pixel` is the per-module greedy given the same
* budget so the comparison is about allocation and nothing else; `codeword`
* ranks whole codewords by what the picture gains from all eight.
*/
function allocate(qr: QrCode, ink: Float32Array, scale: number, tuning: Tuning) {
const modules = Uint8Array.from(qr.modules)
const used = new Int32Array(qr.blockCount)
const centre = centreOffsets(scale)[0]!
const pixels = qr.size * scale
// Ink at the module's sampled centre, and what flipping the module would buy:
// the error before minus the error after, which is positive exactly when the
// picture disagrees with the code.
const benefit = new Float32Array(qr.size * qr.size)
for (let my = 0; my < qr.size; my++)
for (let mx = 0; mx < qr.size; mx++) {
const m = my * qr.size + mx
if (qr.locked[m]) continue
const value = ink[(my * scale + centre) * pixels + mx * scale + centre]!
benefit[m] = Math.max(0, 2 * Math.abs(value - modules[m]!) - 1)
}
let modulesTaken = 0
let freeModules = 0
// Remainder bits: past the last codeword, read by nothing, free to take.
for (let m = 0; m < modules.length; m++) {
if (qr.fixed[m] || qr.codeword[m]! >= 0) continue
if (benefit[m]! > 0) {
modules[m]! ^= 1
modulesTaken++
freeModules++
}
}
const spend = Math.min(Math.max(tuning.spend, 0), 1)
const budget = Math.floor(qr.correctable * spend)
if (tuning.allocator === 'blind') {
// No budget at all: a share of the data modules, taken because the picture
// wanted them. Whether the code survives is not consulted.
const order = Array.from({ length: modules.length }, (_, i) => i).filter((i) => qr.codeword[i]! >= 0)
order.sort((a, b) => benefit[b]! - benefit[a]!)
const take = Math.round(order.length * spend)
const broken = new Set<number>()
for (let i = 0; i < take; i++) {
const m = order[i]!
if (benefit[m]! <= 0) break
const c = qr.codeword[m]!
if (!broken.has(c)) {
broken.add(c)
used[qr.blockOf[c]!]!++
}
modules[m]! ^= 1
modulesTaken++
}
} else if (tuning.allocator !== 'none' && budget > 0) {
if (tuning.allocator === 'codeword') {
const gain = new Float64Array(qr.totalCodewords)
for (let m = 0; m < modules.length; m++) {
const c = qr.codeword[m]!
if (c >= 0) gain[c]! += benefit[m]!
}
const order = Array.from({ length: qr.totalCodewords }, (_, i) => i)
.filter((i) => gain[i]! > 0)
.sort((a, b) => gain[b]! - gain[a]!)
for (const c of order) {
const block = qr.blockOf[c]!
if (used[block]! >= budget) continue
used[block]!++
for (let m = 0; m < modules.length; m++) {
if (qr.codeword[m] !== c || benefit[m]! <= 0) continue
modules[m]! ^= 1
modulesTaken++
}
}
} else {
const order = Array.from({ length: modules.length }, (_, i) => i)
.filter((i) => qr.codeword[i]! >= 0 && benefit[i]! > 0)
.sort((a, b) => benefit[b]! - benefit[a]!)
const broken = new Set<number>()
for (const m of order) {
const c = qr.codeword[m]!
const block = qr.blockOf[c]!
if (!broken.has(c)) {
if (used[block]! >= budget) continue
used[block]!++
broken.add(c)
}
modules[m]! ^= 1
modulesTaken++
}
}
}
let symbolsSpent = 0
let worst = 0
for (const value of used) {
symbolsSpent += value
worst = Math.max(worst, value)
}
return {
modules,
modulesTaken,
freeModules,
symbolsSpent,
symbolsAvailable: qr.correctable * qr.blockCount,
worstBlock: qr.correctable === 0 ? 0 : worst / qr.correctable
}
}
/* ------------------------------------------------------------- diffusion */
/** Orthogonal 3, diagonal 1, normalised over whichever neighbours are free. */
function preDiffuse(
ink: Float32Array,
role: Uint8Array,
size: number,
modules: Uint8Array,
qrSize: number,
scale: number
) {
const neighbours: Array<[number, number, number]> = [
[-1, 0, 3],
[1, 0, 3],
[0, -1, 3],
[0, 1, 3],
[-1, -1, 1],
[1, -1, 1],
[-1, 1, 1],
[1, 1, 1]
]
for (let y = 0; y < size; y++)
for (let x = 0; x < size; x++) {
const at = y * size + x
if (role[at] !== ROLE_SAMPLE) continue
const module = modules[Math.floor(y / scale) * qrSize + Math.floor(x / scale)]!
const error = ink[at]! - module
let total = 0
for (const [dx, dy, weight] of neighbours) {
const nx = x + dx
const ny = y + dy
if (nx < 0 || ny < 0 || nx >= size || ny >= size) continue
if (role[ny * size + nx] !== ROLE_FREE) continue
total += weight
}
if (total === 0) continue
for (const [dx, dy, weight] of neighbours) {
const nx = x + dx
const ny = y + dy
if (nx < 0 || ny < 0 || nx >= size || ny >= size) continue
const to = ny * size + nx
if (role[to] !== ROLE_FREE) continue
ink[to]! += (error * weight) / total
}
}
}
/** Floyd–Steinberg, with the weights renormalised over the free neighbours so
* no error leaks into a module the picture does not own. */
function floydSteinberg(ink: Float32Array, role: Uint8Array, size: number) {
const spread: Array<[number, number, number]> = [
[1, 0, 7],
[-1, 1, 3],
[0, 1, 5],
[1, 1, 1]
]
for (let y = 0; y < size; y++)
for (let x = 0; x < size; x++) {
const at = y * size + x
if (role[at] !== ROLE_FREE) continue
const value = ink[at]! >= 0.5 ? 1 : 0
const error = ink[at]! - value
ink[at] = value
let total = 0
for (const [dx, dy, weight] of spread) {
const nx = x + dx
const ny = y + dy
if (nx < 0 || ny < 0 || nx >= size || ny >= size) continue
if (role[ny * size + nx] !== ROLE_FREE) continue
total += weight
}
if (total === 0) continue
for (const [dx, dy, weight] of spread) {
const nx = x + dx
const ny = y + dy
if (nx < 0 || ny < 0 || nx >= size || ny >= size) continue
const to = ny * size + nx
if (role[to] !== ROLE_FREE) continue
ink[to]! += (error * weight) / total
}
}
}
/**
* Salt and pepper is a local statement, not a per-pixel one: the eye reads a
* neighbourhood's mean. Blur both the target and the result by one module and
* compare the means — that is the number the pre-pass is supposed to move.
*/
function localError(target: Float32Array, pixels: Uint8Array, role: Uint8Array, size: number, radius: number) {
const blur = (read: (i: number) => number) => {
const out = new Float32Array(size * size)
for (let y = 0; y < size; y++)
for (let x = 0; x < size; x++) {
let sum = 0
let count = 0
for (let dy = -radius; dy <= radius; dy++)
for (let dx = -radius; dx <= radius; dx++) {
const nx = x + dx
const ny = y + dy
if (nx < 0 || ny < 0 || nx >= size || ny >= size) continue
sum += read(ny * size + nx)
count++
}
out[y * size + x] = sum / count
}
return out
}
const a = blur((i) => target[i]!)
const b = blur((i) => pixels[i]!)
let sum = 0
let count = 0
for (let i = 0; i < a.length; i++) {
if (role[i] !== ROLE_FREE) continue
sum += Math.abs(a[i]! - b[i]!)
count++
}
return count === 0 ? 0 : sum / count
}
/* ------------------------------------------------------------------ render */
export function dither(qr: QrCode, image: ImageData, tuning: Tuning): DitherResult {
const scale = tuning.scale
const size = qr.size * scale
const ink = inkFrom(image, tuning)
const target = Float32Array.from(ink)
const role = buildRoles(qr, scale)
const allocation = allocate(qr, ink, scale, tuning)
const modules = allocation.modules
if (tuning.prePass) preDiffuse(ink, role, size, modules, qr.size, scale)
if (tuning.mainPass) floydSteinberg(ink, role, size)
const pixels = new Uint8Array(size * size)
for (let y = 0; y < size; y++)
for (let x = 0; x < size; x++) {
const at = y * size + x
pixels[at] =
role[at] === ROLE_FREE
? ink[at]! >= 0.5
? 1
: 0
: modules[Math.floor(y / scale) * qr.size + Math.floor(x / scale)]!
}
return {
qr: { ...qr, modules },
scale,
size,
pixels,
role,
stats: {
modulesTaken: allocation.modulesTaken,
freeModules: allocation.freeModules,
symbolsSpent: allocation.symbolsSpent,
symbolsAvailable: allocation.symbolsAvailable,
worstBlock: allocation.worstBlock,
correctable: qr.correctable,
blockCount: qr.blockCount,
localError: localError(target, pixels, role, size, Math.max(1, Math.floor(scale / 2) + 1))
}
}
}
/**
* Every mask is legal, and they differ only in which modules the code insists
* on. So do not pick the one the spec's readability heuristic likes — pick the
* one that already agrees with the photograph, and get the fit for free.
*/
export function encodeForImage(
text: string,
options: EncodeOptions,
sample: (qr: QrCode) => Float32Array,
scale: number
) {
const first = encodeQr(text, { ...options, mask: 0 })
const ink = sample(first)
const centre = centreOffsets(scale)[0]!
const pixels = first.size * scale
let best = first
let bestCost = Infinity
for (let mask = 0; mask < 8; mask++) {
const candidate = mask === 0 ? first : encodeQr(text, { ...options, mask })
let cost = 0
for (let my = 0; my < candidate.size; my++)
for (let mx = 0; mx < candidate.size; mx++) {
const m = my * candidate.size + mx
if (candidate.locked[m] || candidate.codeword[m]! < 0) continue
cost += Math.abs(ink[(my * scale + centre) * pixels + mx * scale + centre]! - candidate.modules[m]!)
}
if (cost < bestCost) {
bestCost = cost
best = candidate
}
}
return best
}And the camera. The degradation model is in the repository too, and it is also dependency-free — it takes a rendered bitmap and returns a worse one, and knows nothing about QR codes. The runner that drives it and counts decodes is not here: it needs a decoder, and a decoder is a dependency this site has no other use for. The measured output it produced is checked in beside the chart, so the numbers in the section above and the numbers under the curves cannot drift apart.
/**
* Put a rendered code through the things a camera does to it, and ask a
* decoder that has never heard of any of this whether it still reads.
*
* Severity 0 is a flat scan; severity 1 is a creased flyer photographed at an
* angle in a dim room by a cheap phone. Every component scales with it.
*/
export interface Grey {
width: number
height: number
data: Float32Array // 0..255
}
export function paint(pixels: Uint8Array, size: number, modulePx: number, quietModules: number): Grey {
const quiet = Math.round(quietModules * modulePx)
const side = Math.round(size * modulePx) + quiet * 2
const data = new Float32Array(side * side).fill(255)
for (let y = 0; y < side; y++)
for (let x = 0; x < side; x++) {
const sx = Math.floor((x - quiet) / modulePx)
const sy = Math.floor((y - quiet) / modulePx)
if (sx < 0 || sy < 0 || sx >= size || sy >= size) continue
if (pixels[sy * size + sx]) data[y * side + x] = 0
}
return { width: side, height: side, data }
}
/* ------------------------------------------------------------- homography */
function solve(matrix: number[][], rhs: number[]) {
const n = rhs.length
for (let col = 0; col < n; col++) {
let pivot = col
for (let row = col + 1; row < n; row++)
if (Math.abs(matrix[row]![col]!) > Math.abs(matrix[pivot]![col]!)) pivot = row
;[matrix[col], matrix[pivot]] = [matrix[pivot]!, matrix[col]!]
;[rhs[col], rhs[pivot]] = [rhs[pivot]!, rhs[col]!]
const lead = matrix[col]![col]!
for (let row = 0; row < n; row++) {
if (row === col) continue
const factor = matrix[row]![col]! / lead
for (let k = col; k < n; k++) matrix[row]![k]! -= factor * matrix[col]![k]!
rhs[row]! -= factor * rhs[col]!
}
}
return rhs.map((value, i) => value / matrix[i]![i]!)
}
/** Homography taking the four `from` points to the four `to` points. */
function homography(from: number[][], to: number[][]) {
const rows: number[][] = []
const rhs: number[] = []
for (let i = 0; i < 4; i++) {
const [x, y] = from[i]!
const [u, v] = to[i]!
rows.push([x!, y!, 1, 0, 0, 0, -u! * x!, -u! * y!])
rhs.push(u!)
rows.push([0, 0, 0, x!, y!, 1, -v! * x!, -v! * y!])
rhs.push(v!)
}
const h = solve(rows, rhs)
return [h[0]!, h[1]!, h[2]!, h[3]!, h[4]!, h[5]!, h[6]!, h[7]!, 1]
}
/**
* Tilt the plane away from the camera and reproject. The decoder is expected to
* undo this — that is what the finder patterns are for — so what this really
* tests is whether it can still find them, and how much resolution the far edge
* has lost by the time it does.
*/
export function warp(image: Grey, tiltDeg: number, rollDeg: number, rng: () => number): Grey {
const w = image.width
const h = image.height
const tilt = (tiltDeg * Math.PI) / 180
const roll = (rollDeg * Math.PI) / 180
const axis = rng() * Math.PI * 2
// Corners of the code in plane coordinates, rotated in-plane then tilted.
const corners = [
[-0.5, -0.5],
[0.5, -0.5],
[0.5, 0.5],
[-0.5, 0.5]
]
const projected = corners.map(([x, y]) => {
const rx = x! * Math.cos(roll) - y! * Math.sin(roll)
const ry = x! * Math.sin(roll) + y! * Math.cos(roll)
// Rotate about an axis in the plane, at `axis` degrees round.
const along = rx * Math.cos(axis) + ry * Math.sin(axis)
const across = -rx * Math.sin(axis) + ry * Math.cos(axis)
const depth = along * Math.sin(tilt)
const flat = along * Math.cos(tilt)
const f = 3.2
const scale = f / (f + depth)
const px = (flat * Math.cos(axis) - across * Math.sin(axis)) * scale
const py = (flat * Math.sin(axis) + across * Math.cos(axis)) * scale
return [px, py]
})
// Fit the projection back into the frame with room to spare.
const xs = projected.map((p) => p[0]!)
const ys = projected.map((p) => p[1]!)
const span = Math.max(Math.max(...xs) - Math.min(...xs), Math.max(...ys) - Math.min(...ys))
const cx = (Math.max(...xs) + Math.min(...xs)) / 2
const cy = (Math.max(...ys) + Math.min(...ys)) / 2
const fit = (w * 0.94) / span
const dst = projected.map(([x, y]) => [(x! - cx) * fit + w / 2, (y! - cy) * fit + h / 2])
const src = [
[0, 0],
[w, 0],
[w, h],
[0, h]
]
const inverse = homography(dst, src)
const out = new Float32Array(w * h).fill(255)
for (let y = 0; y < h; y++)
for (let x = 0; x < w; x++) {
let sum = 0
// Two by two, because a tilted plane minifies one edge and point
// sampling a minified edge is aliasing, not distance.
for (const [ox, oy] of [
[0.25, 0.25],
[0.75, 0.25],
[0.25, 0.75],
[0.75, 0.75]
]) {
const px = x + ox!
const py = y + oy!
const denominator = inverse[6]! * px + inverse[7]! * py + inverse[8]!
const sx = (inverse[0]! * px + inverse[1]! * py + inverse[2]!) / denominator
const sy = (inverse[3]! * px + inverse[4]! * py + inverse[5]!) / denominator
sum += sample(image, sx, sy)
}
out[y * w + x] = sum / 4
}
return { width: w, height: h, data: out }
}
function sample(image: Grey, x: number, y: number) {
if (x < 0 || y < 0 || x >= image.width - 1 || y >= image.height - 1) return 255
const x0 = Math.floor(x)
const y0 = Math.floor(y)
const fx = x - x0
const fy = y - y0
const at = (px: number, py: number) => image.data[py * image.width + px]!
return (
at(x0, y0) * (1 - fx) * (1 - fy) +
at(x0 + 1, y0) * fx * (1 - fy) +
at(x0, y0 + 1) * (1 - fx) * fy +
at(x0 + 1, y0 + 1) * fx * fy
)
}
/** Separable Gaussian: the lens, and the hand that did not hold still. */
export function blur(image: Grey, sigma: number): Grey {
if (sigma <= 0.01) return image
const radius = Math.max(1, Math.ceil(sigma * 3))
const kernel = new Float32Array(radius * 2 + 1)
let total = 0
for (let i = -radius; i <= radius; i++) {
const value = Math.exp(-(i * i) / (2 * sigma * sigma))
kernel[i + radius] = value
total += value
}
for (let i = 0; i < kernel.length; i++) kernel[i]! /= total
const { width: w, height: h } = image
const pass = new Float32Array(w * h)
const out = new Float32Array(w * h)
for (let y = 0; y < h; y++)
for (let x = 0; x < w; x++) {
let sum = 0
for (let i = -radius; i <= radius; i++)
sum += kernel[i + radius]! * image.data[y * w + Math.min(w - 1, Math.max(0, x + i))]!
pass[y * w + x] = sum
}
for (let y = 0; y < h; y++)
for (let x = 0; x < w; x++) {
let sum = 0
for (let i = -radius; i <= radius; i++)
sum += kernel[i + radius]! * pass[Math.min(h - 1, Math.max(0, y + i)) * w + x]!
out[y * w + x] = sum
}
return { width: w, height: h, data: out }
}
/**
* Glare and faded ink, plus an uneven light across the frame — the thing that
* actually defeats a global threshold, and the reason decoders binarise in
* tiles rather than all at once.
*/
export function tone(image: Grey, black: number, white: number, unevenness: number, rng: () => number): Grey {
const { width: w, height: h } = image
const out = new Float32Array(w * h)
const angle = rng() * Math.PI * 2
const dx = Math.cos(angle)
const dy = Math.sin(angle)
for (let y = 0; y < h; y++)
for (let x = 0; x < w; x++) {
const t = ((x / w - 0.5) * dx + (y / h - 0.5) * dy + 0.5) * unevenness - unevenness / 2
const value = image.data[y * w + x]! / 255
out[y * w + x] = Math.min(255, Math.max(0, (black + value * (white - black)) * (1 + t)))
}
return { width: w, height: h, data: out }
}
export function noise(image: Grey, sigma: number, rng: () => number): Grey {
if (sigma <= 0) return image
const out = new Float32Array(image.data.length)
for (let i = 0; i < out.length; i++) {
const u = Math.max(1e-9, rng())
const gauss = Math.sqrt(-2 * Math.log(u)) * Math.cos(2 * Math.PI * rng())
out[i] = Math.min(255, Math.max(0, image.data[i]! + gauss * sigma))
}
return { width: image.width, height: image.height, data: out }
}
export function toRgb(image: Grey) {
const data = new Array(image.width * image.height * 3)
for (let i = 0; i < image.width * image.height; i++) {
const value = Math.round(image.data[i]!)
data[i * 3] = data[i * 3 + 1] = data[i * 3 + 2] = value
}
return { width: image.width, height: image.height, data }
}
/** Deterministic, so a run can be repeated exactly. */
export function makeRng(seed: number) {
let state = seed >>> 0
return () => {
state ^= state << 13
state >>>= 0
state ^= state >>> 17
state ^= state << 5
state >>>= 0
return state / 4294967296
}
}
export interface Severity {
modulePx: number
tilt: number
roll: number
blurSigma: number
black: number
white: number
unevenness: number
noiseSigma: number
}
/** One draw from the conditions at a given severity, with jitter. */
export function conditions(severity: number, rng: () => number): Severity {
const jitter = (spread: number) => 1 + (rng() * 2 - 1) * spread
const s = Math.min(1, Math.max(0, severity))
return {
modulePx: Math.max(1.6, (6 - 3.6 * s) * jitter(0.12)),
tilt: 48 * s * rng(),
roll: (rng() * 2 - 1) * 20 * s,
blurSigma: 1.5 * s * jitter(0.3) * rng(),
black: 70 * s * rng(),
white: 255 - 60 * s * rng(),
unevenness: 0.45 * s * rng(),
noiseSigma: 16 * s * rng()
}
}
export function apply(base: Grey, c: Severity, rng: () => number) {
let image = base
if (c.tilt > 0.5 || Math.abs(c.roll) > 0.5) image = warp(image, c.tilt, c.roll, rng)
image = blur(image, c.blurSigma)
image = tone(image, c.black, c.white, c.unevenness, rng)
image = noise(image, c.noiseSigma, rng)
return image
}