Strengthen tests beyond parity: property/invariant tests, edge cases, third-party ground truth

[kalwalt]

Summary

The test suite is currently parity-only: all 60 cases compare jsfeatNext against the vendored original-jsfeat oracle on (mostly) a single fixed input each. That's an excellent refactor safety net but not sufficient correctness testing for a 1.0 library. Complement it with oracle-independent property tests, edge/boundary cases, and a few third-party ground-truth values.

Motivation — the three ceilings of parity-only testing

1. Parity can never catch a bug present in both libraries. The oracle is original jsfeat, so these tests prove "identical behavior to jsfeat," not "correct." They inherit jsfeat's bugs by construction. (We saw both sides: the jsfeatNext-only affine2d bug Bug: ransac/lmeds with affine2d kernel throws TypeError (missing motion_model.check_subset) #51 was caught by parity; jsfeat's own broken hough_transform never could be.) For 1.0, "bug-for-bug identical" ≠ "correct."
2. Almost everything runs on one fixed input. imgproc tests a single 64×48 synthetic pattern, one input per function — no boundary conditions (1×1, empty/uniform images, min/max intensities, odd-vs-even dims, tiny kernels, singular/degenerate matrices), which is exactly where CV code breaks.
3. No oracle-independent checks. No property/invariant tests — the kind true regardless of jsfeat, and the only kind that will work where no oracle exists (future haar/bbf, Port haar module (Haar cascade object/face detection) #43/Port bbf module (BBF face detection) #44) or where we intentionally diverge (e.g. the transform matrix_t signature).

Proposed additions (keep the parity suite; layer on top)

A. Property / invariant tests (oracle-independent correctness)

• matmath/transform: invert(invert(M)) ≈ M; M · invert(M) ≈ I; warp-then-unwarp round-trips to ~identity
• linalg: SVD reconstruction U · diag(W) · Vᵀ ≈ A; lu_solve/cholesky_solve residual ‖A·x − b‖ ≈ 0; eigenVV eigen-equation A·v ≈ λ·v
• imgproc: output-range guarantees (grayscale/blur ∈ [0,255]); box_blur/gaussian_blur of a uniform image returns the same uniform value; integral-image corner sums equal brute-force region sums
• detectors: idempotence/structural invariants (e.g. detected corner counts monotic in threshold)

B. Edge / boundary inputs (add as extra cases to existing module tests)

• 1×1 and Nx1/1xN images; empty and uniform images; extreme intensities (all 0, all 255); odd-vs-even dimensions; minimum kernel sizes; singular / ill-conditioned matrices for the solvers.

C. A few third-party ground-truth values

• Hand-computed or OpenCV-sourced expected outputs for a handful of core functions (grayscale luma, a 3×3 SVD, a known homography), so we are not 100% circular with jsfeat.

D. Coverage gaps

• data_type has no dedicated test (only module lacking one). Confirm yape (the non-yape06 detector) has real coverage, not just an import.

Scope / phasing

Additive and incremental — one module (or one category) per PR, existing parity suite staying green. Suggest starting with the linalg invariants (highest bug-catching value, purely mathematical) as the exemplar.

Impact

Low/Medium — test-only, no runtime/API change. High value: real correctness signal + safety for the modules where jsfeat can't be an oracle. Pre-1.0 quality gate (relates to #85, #86).

Non-goals

• Not removing or replacing the parity suite — it stays as the refactor safety net.
• Not a coverage-percentage target for its own sake.

[kalwalt]

Concrete plan

Agreed strategy, after the #102 discussion. The parity suite stays as the refactor safety net — everything here is additive.

Guiding principle

Different test kinds catch different bug classes:

Kind	Catches	Cost
Parity (have it)	regressions vs. previous behaviour	—
Property/invariant	bugs shared with jsfeat (#102), and anything where no oracle exists (haar/bbf #43/#44, the new modules in #83)	free — no dependency
Golden fixtures	convention/detail mismatches ("is our Gaussian kernel OpenCV's?")	one-off generation
Live reference lib	continuous cross-check	dependency + maintenance

Decision on external libraries

No live reference dependency, for now. Where independent ground truth is needed, generate it offline and commit fixtures.

The decisive reason: fixtures free us from the JS ecosystem. The gold standards for this maths are numpy/scipy and OpenCV — neither is a sane runtime dependency for a browser CV library, but both are trivial as an offline generator. We get better ground truth than any JS library, with no CI fragility and no version drift, plus a committed script documenting exactly how every number was produced.

Evaluated and rejected for now: mathjs (~9.4 MB unpacked — far too heavy). ml-matrix (~1.1 MB) is the only live candidate worth reconsidering later, and only for linear algebra.

Fixture convention: tests/fixtures/<module>.<case>.json plus tools/gen-fixtures/<module>.py (or .js), with a header comment stating the source, version and command used.

---

Phase 1 — Property/invariant tests (no dependencies)

These are the highest value per unit of effort, and are what would have caught #102.

linalg

• lu_solve / cholesky_solve: residual ‖A·x − b‖ ≈ 0
• svd_decompose: reconstruction U·diag(W)·Vᵀ ≈ A; W non-negative and descending; U, V orthonormal (Uᵀ·U ≈ I)
• svd_solve: residual ‖A·x − b‖ ≈ 0
• eigenVV: A·v ≈ λ·v for every eigenpair; eigenvectors orthonormal for symmetric A
• svd_invert: see the linalg.svd_invert returns a wrong pseudo-inverse for non-square matrices (bug shared with jsfeat) #102 section below — this test encodes the decision

matmath

• M · M⁻¹ ≈ I, and invert(invert(M)) ≈ M
• multiply_3x3 associativity (A·B)·C ≈ A·(B·C); M · I ≈ M
• identity_3x3(M, v): diagonal = v, off-diagonal = 0
• transpose(transpose(M)) = M; det(A·B) ≈ det(A)·det(B)

transform

• perspective_4point_transform: applying the resulting H to the four source points must land on the four destination points (strong and direct)
• invert_perspective_transform / invert_affine_transform: H · H⁻¹ ≈ I

imgproc

• output range: grayscale, blurs, equalize_histogram all stay within [0, 255]
• uniform-image invariants (cheap and surprisingly effective): blurring a constant image returns the same constant; resample/pyrdown of a constant image stays constant; sobel/scharr derivatives of a constant image are all zero; canny on a constant image finds no edges
• compute_integral_image: the four-corner sum formula equals a brute-force sum over random rectangles
• equalize_histogram is monotonic: a ≤ b ⇒ out(a) ≤ out(b)
• canny output is strictly binary (0 or 255)
• warp_perspective / warp_affine with the identity transform returns the input unchanged
• pyrdown output dimensions are (w>>1, h>>1)

math

• qsort: result is sorted and is a permutation of the input (same multiset — catches element loss)
• median: equals the middle element of the sorted copy (odd n)
• get_gaussian_kernel: symmetric, non-negative, sums to 1.0 (float) or 256 (U8)

detectors — fast_corners, yape, yape06

• every detected corner lies inside the image bounds (respecting border)
• a uniform image yields zero corners
• threshold monotonicity: raising the threshold never increases the corner count
• translation equivariance: shifting the image shifts the detected corners by the same offset

orb

• determinism: describing the same patch twice gives an identical descriptor (Hamming distance 0)
• brightness invariance: +30 grey levels ⇒ small Hamming distance, while a different point is ~128 (already demonstrated in examples/orb_test.html — promote it to a test)

optical_flow_lk

• zero motion: tracking between an image and itself leaves points where they are
• known translation: shifting the image by (dx, dy) moves tracked points by ≈ (dx, dy) (very strong)

motion_estimator

• clean correspondences generated from a known homography ⇒ recovered model ≈ ground truth, all points marked inliers
• with injected outliers ⇒ those points get mask 0

data structures

• matrix_t.resize preserves type/channel; data.length ≥ cols*rows*channel (note: the buffer is padded to a multiple of 8 bytes — see examples/matrix_t_example.html)
• pyramid_t: level i has dimensions (w>>i, h>>i)
• cache: get_buffer(n) returns a node with size ≥ n; a balanced get/put sequence returns the pool to its original size (guards the shared-pool contract from API/behavioral parity: static-vs-instance, double namespace, per-instance cache (Axis 2) #41)

Phase 2 — Edge & boundary cases

Add as extra cases to the tests above, not as a separate suite:

• 1×1, N×1, 1×N images
• uniform images at the extremes (all 0, all 255)
• odd vs even dimensions (off-by-one in the >>1 paths)
• minimum kernel sizes
• singular / ill-conditioned matrices: lu_solve must return 0 rather than produce garbage

Phase 3 — Golden fixtures (offline ground truth)

Only where an invariant cannot express correctness — i.e. convention questions:

• get_gaussian_kernel vs OpenCV's getGaussianKernel for the same size/sigma
• svd_decompose singular values vs numpy.linalg.svd (sign/ordering conventions documented)
• a small canny / sobel reference image vs OpenCV
• a known homography from perspective_4point_transform vs cv2.getPerspectiveTransform

---

The svd_invert question (#102) — what the test looks like under each option

This is the part that should make the decision concrete. The test encodes the choice, so the choice has to come first.

Option (a) — document as square-only

// square: full inverse property
expect(A.multiply(Ainv)).toBeCloseToIdentity();
// non-square: NOT tested — documented as unsupported in the TSDoc

Consequence: the Moore-Penrose invariant can only ever be asserted for square input. A public method still silently returns wrong numbers for valid-looking non-square input. Cheapest; preserves parity exactly.

Option (b) — fix it to a true pseudo-inverse

// holds for square AND non-square — the defining Moore-Penrose property
expect(A.multiply(Aplus).multiply(A)).toBeCloseTo(A);

Consequence: the strongest, most honest test, and the only option where one invariant covers all shapes. But it is a deliberate parity break: tests/parity/linalg.test.ts would need the non-square case re-baselined away from the jsfeat oracle, and that deviation must be documented (this would be the first intentional numeric divergence from jsfeat).

Option (c) — reject non-square input

expect(() => linalg.svd_invert(nonSquareDst, nonSquareSrc)).toThrow();
// or: expect(linalg.svd_invert(...)).toBe(0)  // failure code

Consequence: users get a loud failure instead of a wrong answer — a strictly safer default than (a) at nearly the same cost. Still a behaviour change vs jsfeat, but an unambiguous one (error vs. silent garbage), which is much easier to justify than a numeric divergence.

My read: if the goal is "never hand a user wrong numbers", (c) is the best cost/benefit right now and can be shipped immediately; (b) is the right long-term answer and fits naturally into this issue's correctness work. (a) is the weakest — documentation alone doesn't stop the wrong value being returned.

---

Suggested sequencing

1. linalg + matmath invariants — highest bug-catching density, pure maths, no fixtures needed. Start here; it is also where linalg.svd_invert returns a wrong pseudo-inverse for non-square matrices (bug shared with jsfeat) #102 lives.
2. imgproc uniform-image and integral-image invariants — cheap, and cover a lot of surface.
3. detectors + optical_flow_lk (the translation invariant is very strong).
4. Edge cases folded into the above.
5. Golden fixtures last, only for the convention questions listed in phase 3.

Non-goals

• Replacing the parity suite (it stays — it is the refactor safety net).
• A coverage-percentage target.
• Adding a live external dependency (revisit ml-matrix only if fixtures prove insufficient).