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 | 15x 15x 15x 5x 124996x 5x 5x 1280x 5x 5x 5x 5x 5x 1108x 1108x 930x 930x 925x 925x 925x 925x 925x 8x 8x 5x 4x 4x 123300x 4x 194x 194x 194x 194x 194x 7627x 7627x 7627x 390723x 390723x 390723x 390723x 390723x 3103410x 3103410x 24652936x 24652936x 24652936x 390723x 390723x 141713x 141713x 127193x 127193x 127193x 127193x 127193x 390723x 194x 194x 7627x 7627x 7627x 7627x 7627x 390723x 390723x 390723x 390723x 390723x 390723x 390723x 1907637x 9316359x 9316359x 390723x 390723x 3103410x 3103410x 24652936x 24652936x 194x 198x 195x 193x 198x | import type { Binarizer, GrayImage } from "../types";
import { BitMatrix } from "./bitmatrix";
/**
* Turning a luminance plane into black-and-white modules — the step that
* decides whether a photograph is readable at all.
*
* A single global threshold fails the common case: a phone held over a page
* casts a shadow across half the symbol, and any one cutoff makes the shadowed
* half solid black. The default here is therefore a **local** threshold, with
* a global Otsu pass for images too small for the block grid to mean anything.
*/
/** Side of the square blocks the local threshold is computed over. */
const BLOCK_SIZE = 8;
/** Radius, in blocks, of the neighbourhood each block's threshold averages. */
const BLOCK_RADIUS = 2;
/**
* A block whose pixels are all within this range is treated as uniform — it is
* either all paper or all ink, and its own min/max says nothing useful.
*/
const MIN_DYNAMIC_RANGE = 24;
/**
* Otsu's method: the threshold that minimises intra-class variance.
*
* Exported because it is genuinely useful on its own for clean, evenly-lit
* images (rendered codes, screenshots), where it is both faster and slightly
* more accurate than the local method.
*/
export function otsuThreshold(gray: GrayImage): number {
const histogram = new Uint32Array(256);
for (let i = 0; i < gray.data.length; i++) histogram[gray.data[i]!]!++;
const total = gray.data.length;
let sum = 0;
for (let level = 0; level < 256; level++) sum += level * histogram[level]!;
let backgroundSum = 0;
let backgroundCount = 0;
let best = 0;
let bestVariance = -1;
for (let level = 0; level < 256; level++) {
backgroundCount += histogram[level]!;
if (backgroundCount === 0) continue;
const foregroundCount = total - backgroundCount;
if (foregroundCount === 0) break;
backgroundSum += level * histogram[level]!;
const backgroundMean = backgroundSum / backgroundCount;
const foregroundMean = (sum - backgroundSum) / foregroundCount;
const variance =
backgroundCount * foregroundCount * (backgroundMean - foregroundMean) ** 2;
if (variance > bestVariance) {
bestVariance = variance;
best = level;
}
}
return best;
}
/** Threshold the whole image at one cutoff. Dark pixels (≤ threshold) become 1. */
export function globalBinarize(gray: GrayImage, threshold = otsuThreshold(gray)): BitMatrix {
const matrix = new BitMatrix(gray.width, gray.height);
for (let i = 0; i < gray.data.length; i++) {
matrix.data[i] = gray.data[i]! <= threshold ? 1 : 0;
}
return matrix;
}
/**
* Local (adaptive) thresholding over an 8×8 block grid.
*
* Each block gets the midpoint of its own min and max, then every block's
* threshold is replaced by the average over a 5×5 neighbourhood of blocks, so
* the cutoff varies smoothly across an unevenly lit photo instead of jumping
* at block boundaries.
*
* Uniform blocks — a run of pure paper, or the inside of a large dark area —
* have no meaningful midpoint of their own, so they inherit a value derived
* from the blocks above and to the left, which are the ones already known to
* contain an edge.
*/
export function hybridBinarize(gray: GrayImage): BitMatrix {
const { width, height, data } = gray;
const blocksX = Math.max(1, Math.ceil(width / BLOCK_SIZE));
const blocksY = Math.max(1, Math.ceil(height / BLOCK_SIZE));
const thresholds = new Int32Array(blocksX * blocksY);
for (let by = 0; by < blocksY; by++) {
const yStart = by * BLOCK_SIZE;
const yEnd = Math.min(yStart + BLOCK_SIZE, height);
for (let bx = 0; bx < blocksX; bx++) {
const xStart = bx * BLOCK_SIZE;
const xEnd = Math.min(xStart + BLOCK_SIZE, width);
let min = 255;
let max = 0;
for (let y = yStart; y < yEnd; y++) {
let index = y * width + xStart;
for (let x = xStart; x < xEnd; x++) {
const value = data[index++]!;
if (value < min) min = value;
if (value > max) max = value;
}
}
let threshold = (min + max) >> 1;
if (max - min <= MIN_DYNAMIC_RANGE) {
// A uniform block is all paper or all ink, and its own midpoint says
// nothing. Half its darkest pixel is the estimate — *not* "just below
// its own level".
//
// That difference is not cosmetic. `min - 1` puts a uniform block's
// threshold right at its own brightness, and the 5 × 5 smoothing then
// drags the thresholds of neighbouring blocks that *do* contain modules
// up towards it, until a dim light module reads as ink. Measured on a
// symbol under a 90 % illumination ramp: with `min - 1` the detector
// found zero finder patterns; with `min / 2`, all three. Block size and
// the dynamic-range cutoff made no difference either way.
threshold = min / 2;
if (by > 0 && bx > 0) {
// Where neighbours exist, a smoothed estimate from them is better
// than a guess from a featureless block. This is what keeps a large
// dark logo or quiet zone from being sliced apart.
const above = thresholds[(by - 1) * blocksX + bx]!;
const left = thresholds[by * blocksX + bx - 1]!;
const aboveLeft = thresholds[(by - 1) * blocksX + bx - 1]!;
const estimate = (above + 2 * left + aboveLeft) >> 2;
if (min < estimate) threshold = estimate;
}
}
thresholds[by * blocksX + bx] = threshold;
}
}
const matrix = new BitMatrix(width, height);
for (let by = 0; by < blocksY; by++) {
const yStart = by * BLOCK_SIZE;
const yEnd = Math.min(yStart + BLOCK_SIZE, height);
const top = Math.max(0, by - BLOCK_RADIUS);
const bottom = Math.min(blocksY - 1, by + BLOCK_RADIUS);
for (let bx = 0; bx < blocksX; bx++) {
const xStart = bx * BLOCK_SIZE;
const xEnd = Math.min(xStart + BLOCK_SIZE, width);
const left = Math.max(0, bx - BLOCK_RADIUS);
const right = Math.min(blocksX - 1, bx + BLOCK_RADIUS);
let sum = 0;
let count = 0;
for (let ny = top; ny <= bottom; ny++) {
for (let nx = left; nx <= right; nx++) {
sum += thresholds[ny * blocksX + nx]!;
count++;
}
}
const threshold = sum / count;
for (let y = yStart; y < yEnd; y++) {
let index = y * width + xStart;
for (let x = xStart; x < xEnd; x++) {
matrix.data[index] = data[index]! <= threshold ? 1 : 0;
index++;
}
}
}
}
return matrix;
}
/**
* Apply the requested binarizer.
*
* Images smaller than a few blocks per side fall back to Otsu regardless of
* the setting: with two or three blocks across, "local" is just a noisier
* global threshold.
*/
export function binarize(gray: GrayImage, binarizer: Binarizer = "hybrid"): BitMatrix {
if (typeof binarizer === "function") return binarizer(gray);
if (binarizer === "otsu") return globalBinarize(gray);
const tooSmall = gray.width < BLOCK_SIZE * 5 || gray.height < BLOCK_SIZE * 5;
return tooSmall ? globalBinarize(gray) : hybridBinarize(gray);
}
|