Finds a sheet of paper in a photo, straightens it, and turns the pen lines on it into lines and arcs at a stated scale.
How the precision is kept
The arithmetic is 64-bit, but the result is set by the picture: paper corners are found on a copy reduced to at most 400 pixels, the sheet is resampled to 1800 pixels on its long side, and lines are traced to a tolerance of 1.6 pixels by default. The drawing scale comes from the paper's long side in millimeters divided by its length in pixels.
Open item. When no paper is named, use the long side of the standard paper whose ratio was matched instead of always 297 mm.
Calculations under this policy
6 calculations in 1 source file. The code is read from the released app when this page loads. It is the calculation people run, not a copy kept for this page.
The four corners of the sheet of paper in the photo.
corner = (pixel + 0.5) × k on a copy reduced by the whole factor k; fill = bright pixels inside ÷ outline area
Corners are whole pixels of a grey copy reduced to at most 400 pixels on its long side, moved to the pixel center and multiplied by the reduction factor k, so a corner is known to the nearest k photo pixels. The outline area is the shoelace sum of the four corners.
photosketch.js
lines 45 to 83
CadCraft 0.8.2
/** The largest bright patch that fills most of its four-cornered outline: the paper. Photo pixels, TL TR BR BL (y down). */
export function findSheet(img, { minArea = 0.15, minFill = 0.82 } = {}) {
const g = toGrey(img), s = downsample(g, 400), n = s.w * s.h;
if (s.w < 8 || s.h < 8) return null;
const lvl = otsuLevel(s.data);
const seen = new Uint8Array(n), stack = new Int32Array(n);
let best = null;
for (let i0 = 0; i0 < n; i0++) {
if (seen[i0] || s.data[i0] <= lvl) continue;
let sp = 0, cnt = 0; stack[sp++] = i0; seen[i0] = 1;
let tl = null, br = null, tr = null, bl = null, tlv = Infinity, brv = -Infinity, trv = -Infinity, blv = Infinity;
while (sp) {
const i = stack[--sp], x = i % s.w, y = (i - x) / s.w; cnt++;
const a = x + y, b = x - y;
if (a < tlv) { tlv = a; tl = [x, y]; } if (a > brv) { brv = a; br = [x, y]; } if (b > trv) { trv = b; tr = [x, y]; } if (b < blv) { blv = b; bl = [x, y]; }
if (x > 0 && !seen[i - 1] && s.data[i - 1] > lvl) { seen[i - 1] = 1; stack[sp++] = i - 1; }
if (x < s.w - 1 && !seen[i + 1] && s.data[i + 1] > lvl) { seen[i + 1] = 1; stack[sp++] = i + 1; }
if (y > 0 && !seen[i - s.w] && s.data[i - s.w] > lvl) { seen[i - s.w] = 1; stack[sp++] = i - s.w; }
if (y < s.h - 1 && !seen[i + s.w] && s.data[i + s.w] > lvl) { seen[i + s.w] = 1; stack[sp++] = i + s.w; }
}
if (!best || cnt > best.cnt) best = { cnt, tl, tr, br, bl };
}
if (!best || best.cnt < minArea * n) return null;
const q = [best.tl, best.tr, best.br, best.bl];
let a = 0; for (let i = 0; i < 4; i++) { const p = q[i], r = q[(i + 1) % 4]; a += p[0] * r[1] - r[0] * p[1]; }
const quad = Math.abs(a) / 2, sign = a >= 0 ? 1 : -1;
// ink that closes a figure cuts the paper in pieces: count every bright pixel inside the outline, not only the biggest piece
let inside = 0;
const x0 = Math.min(...q.map((p) => p[0])), x1 = Math.max(...q.map((p) => p[0])), y0 = Math.min(...q.map((p) => p[1])), y1 = Math.max(...q.map((p) => p[1]));
for (let y = y0; y <= y1; y++) for (let x = x0; x <= x1; x++) {
if (s.data[y * s.w + x] <= lvl) continue;
let in4 = true;
for (let i = 0; i < 4 && in4; i++) { const p = q[i], r = q[(i + 1) % 4]; if (sign * ((r[0] - p[0]) * (y - p[1]) - (r[1] - p[1]) * (x - p[0])) < 0) in4 = false; }
if (in4) inside++;
}
const fill = quad > 0 ? inside / quad : 0;
if (fill < minFill || fill > 1.15) return null;
return { corners: q.map(([x, y]) => ({ x: (x + 0.5) * s.k, y: (y + 0.5) * s.k })), fill: Math.min(1, fill), area: inside / n };
}
Perspective matrix from four corners
64-bit
The 3 × 3 matrix that takes the straight sheet's corners to the corners found in the photo.
8 equations in h₁ … h₈ with h₉ = 1, solved by Gauss–Jordan elimination
Elimination with partial pivoting in 64-bit; a pivot below 1e-12, an absolute value, returns no matrix. The system is not scaled first: its entries run from 1 to products of two pixel coordinates.
photosketch.js
lines 87 to 101
CadCraft 0.8.2
/** 3×3 matrix (row-major, h33 = 1) with H·src[i] = dst[i] for four point pairs. */
export function solveHomography(src, dst) {
const A = [];
for (let i = 0; i < 4; i++) {
const { x, y } = src[i], { x: u, y: v } = dst[i];
A.push([x, y, 1, 0, 0, 0, -u * x, -u * y, u], [0, 0, 0, x, y, 1, -v * x, -v * y, v]);
}
for (let c = 0; c < 8; c++) { // Gauss–Jordan with partial pivoting
let p = c; for (let r = c + 1; r < 8; r++) if (Math.abs(A[r][c]) > Math.abs(A[p][c])) p = r;
if (Math.abs(A[p][c]) < 1e-12) return null;
[A[c], A[p]] = [A[p], A[c]];
for (let r = 0; r < 8; r++) if (r !== c) { const f = A[r][c] / A[c][c]; for (let k = c; k < 9; k++) A[r][k] -= f * A[c][k]; }
}
return [...Array.from({ length: 8 }, (_, i) => A[i][8] / A[i][i]), 1];
}
Applying the perspective matrix
64-bit
Where a point of the straight sheet lies in the photo.
Two divisions by w, which is not checked for zero.
photosketch.js
line 102
CadCraft 0.8.2
export const applyH = (H, x, y) => { const w = H[6] * x + H[7] * y + H[8]; return { x: (H[0] * x + H[1] * y + H[2]) / w, y: (H[3] * x + H[4] * y + H[5]) / w }; };
Sheet proportions
64-bit
The long-to-short side ratio of the straightened sheet.
w = mean of top and bottom; h = mean of left and right; ratio = max ÷ min
Side lengths by hypot. A named paper sets the ratio outright; otherwise the measured ratio is replaced by the nearest standard paper ratio when it is within 8 % of it.
photosketch.js
lines 105 to 116
CadCraft 0.8.2
/** The straight sheet's long/short ratio: the named paper's, else the nearest standard one within 8 %, else as measured. */
function sheetRatio(corners, paper) {
const d = (a, b) => Math.hypot(a.x - b.x, a.y - b.y);
const [tl, tr, br, bl] = corners;
const w = (d(tl, tr) + d(bl, br)) / 2, h = (d(tl, bl) + d(tr, br)) / 2;
const landscape = w >= h;
let r = Math.max(w, h) / Math.min(w, h);
const p = paper && paper !== 'auto' ? PAPERS.find((x) => x.key === paper) : null;
if (p) r = p.w / p.h;
else { const near = RATIOS.reduce((a, b) => (Math.abs(b - r) < Math.abs(a - r) ? b : a)); if (Math.abs(near - r) / near <= 0.08) r = near; }
return { ratio: r, landscape };
}
Drawing units per pixel
64-bit
The size of one pixel of the straightened sheet in drawing units.
units per px = long side (mm) ÷ long side (px) × scale ÷ mm per unit
With a named paper the long side is its size in millimeters. With paper 'auto' it is 297 mm whatever sheet was photographed, so sizes are right only for A4 unless the paper is named. A unit name not in the table counts as 1 mm per unit.
Turns each traced arc into a circle or an arc object in drawing units.
r = r(px) × units per px; arc through start, middle and end
A sweep within 1e-6 rad of a full turn becomes a circle. Other arcs are rebuilt from three points (start, the point at the middle angle, end) by arcThrough of scan.js, after the y axis is flipped. The trace is run with a tolerance of 1.6 pixels by default.
photosketch.js
lines 204 to 209
CadCraft 0.8.2
for (const a of res.arcs) {
const c = toDraw(a.cx, a.cy), r = a.r * unitsPerPx;
if (a.a1 - a.a0 >= Math.PI * 2 - 1e-6) { made.push({ type: 'circle', layer: L.name, color: null, cx: c.x, cy: c.y, r }); continue; }
const m = (a.a0 + a.a1) / 2, s = toDraw(a.sx, a.sy), e = toDraw(a.ex, a.ey), md = toDraw(a.cx + a.r * Math.cos(m), a.cy + a.r * Math.sin(m));
const arc = arcThrough(s, md, e);
if (arc) made.push({ type: 'arc', layer: L.name, color: null, cx: arc.cx, cy: arc.cy, r: arc.r, a0: arc.a0, a1: arc.a1 });
In detail
Method
Otsu threshold and flood fill for the paper; four-point homography by Gauss–Jordan elimination with partial pivoting; bilinear resampling to 8-bit; tracing by the shared raster library.
Number types
64-bit numbers for geometry; images are 8-bit arrays.
Tolerances
Homography pivot below 1e-12 (absolute) is refused. Paper ratio snaps to a standard ratio within 8 %. Paper must fill 0.82 to 1.15 of its four-cornered outline and at least 15 % of the photo. A traced arc within 1e-6 rad of a full turn becomes a circle.
Limits
With no paper named, the long side is taken as 297 mm whatever the sheet is. Corner positions are known to one pixel of the reduced copy.
Approach: 64-bit, stated limit
The arithmetic is 64-bit, but the method or the data sets the accuracy: a solver tolerance, a mesh, a step size, a datum shift, a table. The limit is stated where the result is shown.