`motion_estimator.ransac`: doc comment promises a refit over all inliers; jsfeatNext has no layer that performs one

[kalwalt]

Summary

ransac()'s doc comment claims:

"...keeps the hypothesis with the most inliers (adapting the iteration count from the observed inlier ratio), and finally refits the model on all inliers of the best hypothesis."

The code never does this. After the loop it returns the winning minimal-sample model (4 points for homography, 3 for affine) — the only two kernel.run() calls are the count === model_points exact-fit special case and the in-loop minimal-sample fit.

Correction to the original framing of this issue: OpenCV does not refit inside RANSAC either. cv::RANSACPointSetRegistrator::run (modules/calib3d/src/ptsetreg.cpp) is structurally identical to ours — same count == modelPoints special case, same goodCount > MAX(maxGoodCount, modelPoints-1) test, same RANSACUpdateNumIters, and ends with bestModel.copyTo(_model); result = true;. No refit. jsfeat ported that class faithfully and jsfeatNext inherited the fidelity.

So ransac() is not wrong relative to its OpenCV counterpart. What jsfeatNext is missing is the caller-level layer that OpenCV has and jsfeat never ported: cv::findHomography / cv::estimateAffine2D. That is where the refit lives.

This reframes the issue from "fix a bug in ransac()" to "decide where the missing layer goes, then make the doc comment true".

What OpenCV actually does (4.x)

Three steps after RANSAC returns, in findHomography (only when npoints > 4, method != RHO):

compressElems( src.ptr<Point2f>(), tempMask.ptr<uchar>(), 1, npoints );
npoints = compressElems( dst.ptr<Point2f>(), tempMask.ptr<uchar>(), 1, npoints );
if( npoints > 0 ) {
    src = src.rowRange(0, npoints);  dst = dst.rowRange(0, npoints);
    if( method == RANSAC || method == LMEDS )
        cb->runKernel( src, dst, H );                                            // (a) linear DLT refit
    Mat H8(9, 1, CV_64F, H.ptr<double>());
    LMSolver::create(makePtr<HomographyRefineCallback>(src, dst), 10)->run(H8);  // (b) Levenberg-Marquardt
    H.convertTo(H, H.type(), scaleFor(H.at<double>(2,2)));
    cb->computeError(src_input, dst_input, H, errors);                           // (c) recompute inlier mask
    for (int i = 0; i < npoints_input; i++)
        maskptr[i] = static_cast<uchar>(errors_ptr[i] <= thr_sqr);
}

estimateAffine2D runs only step (b) (refineIters, default 10) — for a linear model LM from the RANSAC seed converges to the LS solution anyway.

Conceptual point worth recording: step (a) alone does not buy geometric accuracy. A DLT refit over all inliers still minimises the algebraic residual (‖Lh‖ subject to ‖h‖=1), not reprojection error. OpenCV's sub-pixel behaviour comes from step (b). A test asserting sub-pixel precision is really asserting LM.

Evidence (unchanged, re-attributed)

Building webarkit/webarkit's cv-backend-jsfeatnext adapter, a sub-pixel assertion on a clean, noise-free 12-point correspondence set was flaky ~1 run in 45.

• numInliers was 12/12 across 2000 repeated calls — inlier classification is solid.
• The returned homography's coefficients varied run to run: reprojection error up to ~0.36px across 3000 calls on data that is mathematically exact.
  The original issue attributed this entirely to which minimal sample RANSAC drew. That is one of three contributing causes:

1. Minimal-sample variance — different 4-point subsets condition the DLT differently. Addressed by the refit.
2. Single-precision DLT — homography2d.mLtL and Evec are F32_t, as are T0/T1. Normal equations square the condition number and every LtL[j] += ... rounds to f32 on each accumulation. OpenCV uses double LtL[9][9] / double V[9][9] throughout. See #TODO-A.
3. Unseeded RNG — get_subset uses Math.random(); OpenCV uses RNG rng((uint64)-1), a fixed seed, so findHomography is deterministic run to run. See #TODO-B.
   A refit will substantially reduce the spread (12 points condition far better than 4, and average the noise) but will not eliminate it while the accumulators stay f32. Any acceptance criterion here needs a measured tolerance, not a qualitative "converges to the same model".

The decision this issue actually needs

tests/parity/motion_estimator.test.ts seeds Math.random with the same mulberry32 for jsfeatNext and for the vendored jsfeat oracle, then asserts expect(model.data[i]).toBeCloseTo(modelO.data[i], 5). Adding a refit inside ransac() does not merely shift that number — it compares a 4-point model against a ~34-point model. The parity test stops being a parity test.

Option A — refit inside ransac(). ~20 lines, immediately fixes the adapter. Cost: motion_estimator.ransac deliberately diverges from jsfeat.motion_estimator.ransac and from cv::RANSACPointSetRegistrator. The parity test has to be downgraded to a "we intentionally differ" test, and we lose the oracle for this function permanently.

Option B — keep ransac() at parity, add the missing layer. Introduce find_homography(from, to, count, method, thresh, model, mask, max_iters) (and later estimate_affine2d) that composes ransac/lmeds + inlier compaction + refit + mask recompute, mirroring OpenCV's layering. ransac() stays byte-comparable to jsfeat, the parity test survives untouched, and the adapter calls the new entry point. Cost: a new public API surface to name, document and version before 1.0.0.

Recommendation: B. It matches OpenCV's actual architecture rather than a mental model of it, keeps the only oracle we have for ransac(), and the adapter gets a better-named call site than ransac() anyway.

Whichever is chosen, the doc comment gets fixed: under A it becomes true, under B the false clause is deleted from ransac() and the promise moves to find_homography's docs.

Implementation notes (apply to either option)

curr_mask is stale at loop exit. It holds the mask of the last evaluated hypothesis, not the best one — the best mask survives only if the caller passed mask. A dedicated best_mask buffer is required. OpenCV does exactly this: it allocates bestMask itself when _mask isn't needed and uses std::swap(mask, bestMask).

const bs_buff = this.cache.get_buffer(count);
const best_mask = new matrix_t(count, 1, JSFEAT_CONSTANTS.U8C1_t, bs_buff.data);
 
// in the loop, replace `if (mask) curr_mask.copy_to(mask);` with:
curr_mask.copy_to(best_mask);
 
// after the loop:
if (result) {
    const in0: point_t[] = [], in1: point_t[] = [];
    for (let i = 0; i < count; ++i) {
        if (best_mask.data[i]) { in0.push(from[i]); in1.push(to[i]); }
    }
    if (in0.length > model_points && kernel.run(in0, in1, M, in0.length) > 0) {
        M.copy_to(model);
        this.find_inliers(kernel, model, from, to, count, params.thresh, err, best_mask.data);
    }
    if (mask) best_mask.copy_to(mask);
}
this.cache.put_buffer(bs_buff);

Edge cases:

• If kernel.run on the inlier set returns <= 0 (degenerate — e.g. all inliers collinear), keep the minimal-sample model. The sketch above does this by construction.
• OpenCV does not check that the post-refit inlier count is still >= model_points. Worth being more defensive than OpenCV and reverting to the pre-refit model if the count collapses — pathological but silent otherwise.
• The count === model_points early return stays as is: an exact fit has nothing to refine.
• homography2d.run allocates nothing per-count (mLtL is a fixed 9×9), so the refit is free. affine2d.run takes 2*count*6 from the cache — negligible. One extra kernel.run() per call.

Acceptance criteria

• Decision recorded (A or B) with @ThorstenBux, and the public API named if B
• After RANSAC converges, the returned model is refit over all inlying correspondences via kernel.run()
• The inlier mask is recomputed against the refit model over the full original point set, so mask and model describe the same transform (OpenCV step (c) — missing from the original criteria)
• A dedicated best_mask buffer, so the refit uses the best hypothesis's inliers and not the last one's
• Degenerate refit (kernel.run() <= 0) falls back to the minimal-sample model rather than returning garbage
• Under A: tests/parity/motion_estimator.test.ts reclassified from parity to intentional-divergence, with the reason documented in the test. Under B: parity test untouched and passing
• A property test on a noise-free correspondence set showing repeated calls now agree to a measured tolerance (re-run the 3000-call experiment with the patch and pin the observed number), not a qualitative claim
• ransac()'s doc comment and the code agree

Out of scope

• Levenberg-Marquardt refinement — see #TODO-C Add non-linear refinement (Levenberg–Marquardt) for homography and affine, as OpenCV does after RANSAC #187. It is what actually delivers OpenCV's sub-pixel accuracy, but it needs a solver jsfeatNext does not have yet.
• mLtL/Evec precision — see #TODO-A homography2d: DLT normal equations accumulated in Float32, capping achievable precision #186 .
• Seeded RNG — see #TODO-B motion_estimator.get_subset uses the global Math.random; make the RNG injectable #189.
• lmeds() — see #TODO-D motion_estimator.lmeds needs the same post-convergence refit as ransac — OpenCV refines both through one branch #188 . OpenCV refines it through the same branch (method == RANSAC || method == LMEDS); fixing only ransac() creates an asymmetry.
• get_subset / find_inliers sampling and classification logic — unchanged, and fine.

Related

Surfaced while building webarkit/webarkit's cv-backend-jsfeatnext adapter (follow-on work from #96). The workaround there is webarkit/webarkit#8 (test tolerance loosened from sub-pixel to 1px, with measured numbers documented) — a pragmatic fix for the symptom; this issue plus #TODO-A and #TODO-C are the root causes.

[kalwalt]

Decision recorded: Option B — keep ransac()/lmeds() at jsfeat/OpenCV parity (no refit inside either), and introduce a composed find_homography() (and later estimate_affine2d()) entry point that layers inlier compaction + refit + mask recompute on top, mirroring OpenCV's actual architecture (cv::findHomography vs cv::RANSACPointSetRegistrator::run).

Rationale: preserves the only oracle we have for ransac()/lmeds() in tests/parity/motion_estimator.test.ts, matches OpenCV's real layering rather than a mental model of it, and gives the adapter a better-named call site than ransac() directly.

Consolidated attack order across #185/#186/#187/#188/#189:

1. motion_estimator.ransac: doc comment promises a refit over all inliers; jsfeatNext has no layer that performs one #185 — implement find_homography() per Option B (this issue)
2. motion_estimator.lmeds needs the same post-convergence refit as ransac — OpenCV refines both through one branch #188 — apply the identical refit+mask-recompute pattern to lmeds() (cheap once motion_estimator.ransac: doc comment promises a refit over all inliers; jsfeatNext has no layer that performs one #185's shape exists; lmeds already holds the right inlier mask)
3. motion_estimator.get_subset uses the global Math.random; make the RNG injectable #189 — injectable RNG (independent of the above, can land anytime)
4. homography2d: DLT normal equations accumulated in Float32, capping achievable precision #186 — F64 DLT accumulators (needed before LM has a clean seed to converge from)
5. Add non-linear refinement (Levenberg–Marquardt) for homography and affine, as OpenCV does after RANSAC #187 — Levenberg-Marquardt refinement (depends on motion_estimator.ransac: doc comment promises a refit over all inliers; jsfeatNext has no layer that performs one #185's entry point existing and homography2d: DLT normal equations accumulated in Float32, capping achievable precision #186's precision floor being fixed first)

ransac()'s and lmeds()'s doc comments get the false refit claim removed under this option; the promise moves to find_homography()'s own docs once it exists.

[kalwalt]

Fixed via jsfeatNext#190 (merged into dev at 5a9e774): added find_homography() implementing Option B, plus the lmeds threshold fix and mask-leak fix found during review.