gridfinder - npm Package Compare versions

Comparing version 1.48.0 to 1.49.0

lib/detectGrid.js

 import {findGrid1d} from "./findGrid.js";
+import {averageInliers, nth, numericAsc, numericDesc, percentile} from "./util.js";
 
 function* probes(limit) {
 	let step = Math.sqrt(limit) + 1 |0;
-	let half = limit / 2 |0;
 
@@ -12,46 +12,47 @@ for (let i = step; i < limit; i += step) {
 
-function extractLine(img, primaryLimt, secondaryLimit, offset) {
-	let pixels = img.data;
+export const EDGE_RANGE = 8;
 
-	const localtreshold = 8;
+export function scorePoint(img, x, y, offset) {
+	let p = img.data;
 
+	let from = x - EDGE_RANGE;
+	let to = x + EDGE_RANGE;
+
+	let off = offset(x, y) * 4;
+	let sum = p[off] + p[off+1] + p[off+2] + p[off+3];
+
+	let lavg = sum;
+	for (let i = from; i < x; i++) {
+		let off = offset(i, y) * 4;
+		lavg += p[off] + p[off+1] + p[off+2] + p[off+3];
+	}
+	lavg /= EDGE_RANGE;
+
+	let ravg = sum;
+	for (let i = x + 1; i <= to; i++) {
+		let off = offset(i, y) * 4;
+		ravg += p[off] + p[off+1] + p[off+2] + p[off+3];
+	}
+	ravg /= EDGE_RANGE;
+
+	if ((sum < lavg) != (sum < ravg)) {
+		return 0;
+	}
+
+	let ldiff = Math.abs(sum - lavg);
+	let rdiff = Math.abs(sum - ravg);
+	return Math.min(ldiff, rdiff);
+}
+
+function scoreLine(img, primaryLimt, secondaryLimit, offset) {
 	let line = Array(primaryLimt).fill(0);
 	let samples = [];
-	for (let x = localtreshold; x < primaryLimt - localtreshold; x++) {
+	for (let x = EDGE_RANGE; x < primaryLimt - EDGE_RANGE; x++) {
 		samples.length = 0;
 
-		// Edge detection range.
-		let from = x - localtreshold;
-		let to = x + localtreshold;
-
 		for (let y of probes(secondaryLimit)) {
-			let off = offset(x, y) * 4;
-			let sum = pixels[off] + pixels[off+1] + pixels[off+2] + pixels[off+3];
-
-			let lavg = sum;
-			for (let i = from; i < x; i++) {
-				let off = offset(i, y) * 4;
-				lavg += pixels[off] + pixels[off+1] + pixels[off+2] + pixels[off+3];
-			}
-			lavg /= localtreshold;
-
-			let ravg = sum;
-			for (let i = x + 1; i <= to; i++) {
-				let off = offset(i, y) * 4;
-				ravg += pixels[off] + pixels[off+1] + pixels[off+2] + pixels[off+3];
-			}
-			ravg /= localtreshold;
-
-			if ((sum < lavg) != (sum < ravg)) {
-				samples.push(0);
-			} else {
-				let ldiff = Math.abs(sum - lavg);
-				let rdiff = Math.abs(sum - ravg);
-				samples.push(Math.min(ldiff, rdiff));
-			}
+			samples.push(scorePoint(img, x, y, offset));
 		}
 
-		samples.sort((a, b) => a - b);
-		let middle = samples.slice(samples.length * 0.25 | 0, samples.length * 0.75 | 0)
-		line[x] = middle.reduce((a,b)=>a+b)/middle.length;
+		line[x] = averageInliers(samples, 0.5, 0.6);
 	}
@@ -62,24 +63,63 @@
 
+export function scoreCols(img) {
+	return scoreLine(img, img.width, img.height, (x, y) => x + y*img.width);
+}
+
+export function scoreRows(img) {
+	return scoreLine(img, img.height, img.width, (y, x) => x + y*img.width);
+}
+
+export const TOP_LINES = 16;
+
 function detectGrid1d(line) {
-	let sorted = [...line];
-	sorted.sort((a, b) => a - b);
+	let sorted = line.map((value, point) => ({value, point}));
+	sorted.sort((b, a) => a.value - b.value);
 
-	let point_count = Math.log(sorted.length) |0;
-	let threshold = sorted[sorted.length - point_count];
+	let limit = Math.min(TOP_LINES, sorted.length);
 
-	let points = [];
-	for (let y = 0; y < line.length; y++) {
-		if (line[y] >= threshold) {
-			points.push(y);
+	let best = 0;
+	let bestsize = Infinity;
+	let bestpoint;
+	let bestoff;
+
+	for (let ai = 0; ai < limit-1; ai++) {
+		let a = sorted[ai];
+		for (let bi = ai+1; bi < limit; bi++) {
+			let b = sorted[bi];
+
+			let size = Math.abs(a.point - b.point);
+			if (size < 8) continue;
+			let off = a.point % size;
+
+			let avg = 0;
+			for (let p = off; p < line.length; p += size) {
+				avg += Math.sqrt(line[p]);
+			}
+			avg /= (line.length - off) / size + 1;
+			avg /= Math.sqrt(size); // Prefer smaller grids.
+
+			if (avg <= best) continue;
+
+			best = avg;
+			bestsize = size;
+			bestpoint = a.point;
+			bestoff = off;
 		}
 	}
 
-	return findGrid1d(points);
+	if (bestoff*2 > bestsize) {
+		bestoff -= bestsize;
+	}
+
+	return {
+		cellSize: bestsize,
+		offset: bestoff,
+	};
 }
 
 export default function detectGrid(img) {
-	let cols = extractLine(img, img.width, img.height, (x, y) => x + y*img.width);
+	let cols = scoreCols(img);
 	let xdim = detectGrid1d(cols);
 
-	let rows = extractLine(img, img.height, img.width, (y, x) => x + y*img.width);
+	let rows = scoreRows(img);
 	let ydim = detectGrid1d(rows);
@@ -86,0 +126,0 @@

lib/detectGrid.test.js

@@ -11,14 +11,14 @@ import * as gridfinder from "./lib.js";
 		},
-		// "crossroad-keep.jpg": {
-		// 	width: 22.25,
+		"crossroad-keep.jpg": {
+			width: 11, // 22.25,
+			height: 10, // Wrong, non-integer.
+			offTolerance: 10, // Wrong.
+		},
+		// "grass.jpg": {
+		// 	width: 12.5,
 		// },
-		"grass.jpg": {
-			width: 12.5,
-			height: 8.5, // Wrong.
-			offY: -3, // Wrong.
-		},
 		"irish-pub.jpg": {
 			width: 70,
-			height: 1315, // Wrong, detects roof tiles.
-			offY: -575, // Wrong.
+			height: 11, // Wrong
+			offY: -3, // Wrong.
 		},
@@ -30,7 +30,8 @@ "mythictable-tutorial.jpg": {
 			width: 35,
-			height: 35/2, // Wrong
-			tolerance: 0.1,
+			height: 20, // Wrong
+			offY: -5,
 		},
 		"floating-islands.jpg": {
-			width: 17,
+			width: 17.06,
+			offTolerance: 5, // Wrong, but we don't do non-integer grids yet.
 		},
@@ -37,0 +38,0 @@ // "spaceship-main-blur.jpg": {

lib/ui.js

 import Point from "./Point.js";
+import * as debugDetectGrid from "./debugDetectGrid.js"
 import {findGrid, detectGrid} from "./lib.js";
@@ -10,3 +11,3 @@
 let canvas = document.getElementById("canvas");
-let ctx = canvas.getContext('2d');
+let ctx = canvas.getContext("2d");
 
@@ -129,2 +130,16 @@ export function click(e) {
 
+function detect() {
+	let debug = new URLSearchParams(location.search).get("debug");
+
+	ctx.drawImage(img, 0, 0);
+
+	if (debug) {
+		debugDetectGrid[debug](canvas);
+	} else {
+		let data = ctx.getImageData(0, 0, canvas.width, canvas.height);
+		let r = detectGrid(data);
+		drawGrid(r);
+	}
+}
+
 let img = document.getElementById("bg");
@@ -139,6 +154,3 @@ function onLoad() {
 	try {
-		ctx.drawImage(img, 0, 0);
-		let data = ctx.getImageData(0, 0, canvas.width, canvas.height);
-		let r = detectGrid(data);
-		drawGrid(r);
+		detect();
 	} catch (e) {
@@ -145,0 +157,0 @@ if (!(e instanceof DOMException)) throw e;

package.json

 {
   "name": "gridfinder",
-  "version": "1.48.0",
+  "version": "1.49.0",
   "license": "Apache 2.0",
@@ -5,0 +5,0 @@ "homepage": "https://gridfinder.kevincox.ca",

No alert changes

Improved metrics

Total package byte prevSize

8683702

increased by0.06%

Number of package files

43

increased by4.88%

Lines of code

1211

increased by19.66%

No dependency changes