Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 | 15x 15x 15x 15x 8x 8x 8x 8x 8x 8x 8x 1632x 1632x 1632x 1632x 1632x 1632x 1632x 1632x 7928x 7928x 7928x 7928x 7928x 1632x 7928x 1632x 8x 4x 4x 4x 4x 3464x 3464x 3464x 2421024x 2421024x 2421024x 2421024x 2421024x 2421024x 12084096x 12084096x 2421024x 4x 716x 716x 716x 716x 716x 485256x 485256x 2421024x 485256x 211x 5x 5x 5x 5x 5x 211x 211x 211x 211x 211x 211x 211x 211x 211x 211x 211x 211x 207x 62158x 62158x 62158x 25531636x 25531636x 4x 211x 2x | import type { GrayImage, Rect } from "../types";
/**
* RGBA pixels → a luminance plane, with optional cropping and downscaling.
*
* This is the first thing every frame goes through, so it is written to
* allocate once and reuse: at 12 frames a second a fresh 640 KB buffer per
* frame is half a megabyte of garbage every 80 ms, which shows up as GC
* stutter in exactly the moment the user is holding a phone steady.
*/
/** ITU-R BT.601 luma coefficients, in 16.16 fixed point. */
const R_WEIGHT = 19595; // 0.299
const G_WEIGHT = 38470; // 0.587
const B_WEIGHT = 7471; // 0.114
/**
* How much smaller the working image must be before shrinking is worth doing.
*
* Downscaling reads every source pixel, so it costs roughly what one pass of
* detection over the same pixels costs — and it only saves work on the *smaller*
* image that follows. A modest reduction therefore loses outright: you pay for
* the whole frame and get a slightly cheaper analysis back.
*
* Measured on this machine (median of 20, after warm-up), capping to 800 px:
*
* | Frame | reduction | capped | uncapped |
* |-------------|-----------|----------|----------|
* | 1280 × 720 | 1.6× | 9.6 ms | **7.1 ms** |
* | 1920 × 1080 | 2.4× | 20.6 ms | **19.8 ms** |
* | 4000 × 3000 | 5.0× | **61.2 ms** | 71.2 ms |
*
* So the cap now applies only past this ratio. Below it the frame is analysed
* at full resolution, which is both faster and strictly more accurate; above
* it, shrinking pays for itself and also bounds memory — a 12 megapixel photo
* would otherwise need 24 MB of intermediate buffers.
*/
const MIN_WORTHWHILE_REDUCTION = 2.5;
export interface GrayOptions {
/** Cap on the longest side, in pixels. `0` (or omitted) means no cap. */
maxDimension?: number;
/** Crop rectangle in source pixels, applied before the downscale. */
region?: Rect;
/**
* A buffer to write into. Reused across frames when it is large enough;
* a new one is allocated (and returned in the result) when it is not.
*/
buffer?: Uint8ClampedArray;
}
/**
* The source range and weights each destination pixel draws from, along one
* axis.
*
* Precomputing these is what makes area-weighted downscaling affordable. The
* obvious implementation recomputes a fractional overlap inside the innermost
* loop — two `min`s, two `max`s and a multiply for every source pixel — and
* measurably costs *more* than the work it was meant to save: with per-pixel
* weights, capping a 1920 × 1080 frame to 800 px took 33 ms against 19 ms for
* not capping at all. Weights depend only on the axis, so they are computed
* once per axis instead of once per pixel.
*/
interface AxisWeights {
/** First source index contributing to each destination index. */
readonly starts: Int32Array;
/** Number of source indices contributing to each destination index. */
readonly counts: Int32Array;
/** Flattened weights, `counts[i]` of them starting at `offsets[i]`. */
readonly weights: Float32Array;
readonly offsets: Int32Array;
}
function axisWeights(sourceLength: number, targetLength: number): AxisWeights {
const ratio = sourceLength / targetLength;
const starts = new Int32Array(targetLength);
const counts = new Int32Array(targetLength);
const offsets = new Int32Array(targetLength);
// Each destination cell spans at most `ceil(ratio) + 1` source cells.
const weights = new Float32Array(targetLength * (Math.ceil(ratio) + 1));
let cursor = 0;
for (let i = 0; i < targetLength; i++) {
const from = i * ratio;
const to = Math.min(sourceLength, (i + 1) * ratio);
const first = Math.floor(from);
const last = Math.min(sourceLength - 1, Math.ceil(to) - 1);
starts[i] = first;
offsets[i] = cursor;
let total = 0;
for (let s = first; s <= last; s++) {
const weight = Math.min(s + 1, to) - Math.max(s, from);
Iif (weight <= 0) continue;
weights[cursor + (counts[i]! ?? 0)] = weight;
counts[i]!++;
total += weight;
}
// Normalize here so the hot loop is a plain multiply-accumulate.
Eif (total > 0) {
for (let k = 0; k < counts[i]!; k++) weights[cursor + k]! /= total;
}
cursor += counts[i]!;
}
return { starts, counts, weights, offsets };
}
/**
* Separable area-weighted downscale: horizontal first, then vertical.
*
* Separating the passes turns an O(sx · sy) inner loop per destination pixel
* into two O(1)-per-source-pixel sweeps, and the colour conversion happens
* exactly once per source pixel rather than once per contribution.
*
* Area weighting rather than whole-pixel averaging: at a non-integer ratio,
* counting whole pixels gives some destination cells two source rows and their
* neighbours one, which beats a periodic ripple into a uniform image and drifts
* module edges. `luminance.test.ts` measures that directly.
*/
function resample(
source: Uint8ClampedArray,
sourceWidth: number,
region: Rect,
target: Uint8ClampedArray,
width: number,
height: number,
): void {
const horizontal = axisWeights(region.width, width);
const vertical = axisWeights(region.height, height);
// One horizontal-only row per source row, reused across the vertical pass.
const rows = new Float32Array(region.height * width);
for (let sy = 0; sy < region.height; sy++) {
const rowBase = sy * width;
const pixelBase = ((sy + region.y) * sourceWidth + region.x) * 4;
for (let x = 0; x < width; x++) {
const start = horizontal.starts[x]!;
const count = horizontal.counts[x]!;
const offset = horizontal.offsets[x]!;
let value = 0;
let index = pixelBase + start * 4;
for (let k = 0; k < count; k++) {
value +=
horizontal.weights[offset + k]! *
((source[index]! * R_WEIGHT +
source[index + 1]! * G_WEIGHT +
source[index + 2]! * B_WEIGHT) >>
16);
index += 4;
}
rows[rowBase + x] = value;
}
}
for (let y = 0; y < height; y++) {
const start = vertical.starts[y]!;
const count = vertical.counts[y]!;
const offset = vertical.offsets[y]!;
const targetBase = y * width;
for (let x = 0; x < width; x++) {
let value = 0;
for (let k = 0; k < count; k++) {
value += vertical.weights[offset + k]! * rows[(start + k) * width + x]!;
}
target[targetBase + x] = value;
}
}
}
/** Clamp a crop to the image, rounding outward so no requested pixel is lost. */
function clampRegion(region: Rect | undefined, width: number, height: number): Rect {
if (!region) return { x: 0, y: 0, width, height };
const x = Math.max(0, Math.min(width - 1, Math.floor(region.x)));
const y = Math.max(0, Math.min(height - 1, Math.floor(region.y)));
const right = Math.max(x + 1, Math.min(width, Math.ceil(region.x + region.width)));
const bottom = Math.max(y + 1, Math.min(height, Math.ceil(region.y + region.height)));
return { x, y, width: right - x, height: bottom - y };
}
/**
* Convert (and optionally crop and shrink) an `ImageData` into a `GrayImage`.
*
* Downscaling uses a box filter — averaging every source pixel that falls in a
* destination cell — rather than nearest-neighbour sampling. Point sampling a
* QR code is how thin modules disappear entirely: at 3 px per module, dropping
* two rows out of three can erase a whole timing pattern.
*/
export function toGray(image: ImageData, options: GrayOptions = {}): GrayImage {
const region = clampRegion(options.region, image.width, image.height);
const cap = options.maxDimension ?? 0;
const longest = Math.max(region.width, region.height);
const shrinkBy = cap > 0 ? longest / cap : 1;
const scale = shrinkBy >= MIN_WORTHWHILE_REDUCTION ? cap / longest : 1;
const width = Math.max(1, Math.round(region.width * scale));
const height = Math.max(1, Math.round(region.height * scale));
const size = width * height;
const data =
options.buffer && options.buffer.length >= size
? options.buffer.subarray(0, size)
: new Uint8ClampedArray(size);
const source = image.data;
const sourceWidth = image.width;
if (width === region.width && height === region.height) {
// Fast path: no resampling, just the colour conversion.
for (let y = 0; y < height; y++) {
let target = y * width;
let index = ((y + region.y) * sourceWidth + region.x) * 4;
for (let x = 0; x < width; x++) {
data[target++] =
(source[index]! * R_WEIGHT + source[index + 1]! * G_WEIGHT + source[index + 2]! * B_WEIGHT) >>
16;
index += 4;
}
}
} else {
resample(source, sourceWidth, region, data, width, height);
}
return {
data,
width,
height,
scale,
offsetX: region.x,
offsetY: region.y,
};
}
/**
* Map a point from the working luminance plane back to source-image pixels.
*
* Every coordinate this package reports goes through here, which is why the
* scale and the crop origin travel with the image rather than being remembered
* by the caller.
*/
export function toSourcePoint(gray: GrayImage, x: number, y: number): { x: number; y: number } {
return {
x: gray.offsetX + x / gray.scale,
y: gray.offsetY + y / gray.scale,
};
}
|