webarkit / webarkit/jsfeatNext

feat(gms): grid-based motion statistics match filter

Open
#134 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement tests Typescript
Dominant language
TypeScript
Stars
12
Forks
4
Avg merge
16h 24m
Merged PRs (30d)
34

Description

Summary

Add src/gms/gms.tsGrid-based Motion Statistics (Bian et al., CVPR 2017),
a post-matching filter that separates correct from incorrect matches before
RANSAC.

Port of cv::xfeatures2d::matchGMS. No trained data, no external dependency.

Why

GMS is neither a detector nor a descriptor: it is a statistical filter that runs
between matching and find_homography. The observation it exploits is that a
correct match has neighbours whose own correspondences land near its
correspondence — surfaces are locally coherent, so motion is locally coherent.
An incorrect match is a random event and its neighbours scatter.

For planar WebAR tracking the payoff is downstream of the filter. RANSAC's
iteration count for a given confidence goes as log(1 - p) / log(1 - r^4),
where r is the inlier fraction. Moving from ~25% to ~60% inliers — a typical
reported gain for GMS over ORB matches — cuts the required iterations by an
order of magnitude. In practice: faster and more stable homography estimation,
with fewer frames where the solution degenerates and the anchored content jumps.

GMS's assumption — locally uniform motion — holds poorly for strong parallax and
deformable scenes, and holds very well for the planar rigid targets WebARKit
tracks. This is the best case for the algorithm.

It is also descriptor-independent: identical behaviour with ORB, TEBLID or
FREAK, and no trained tables. It can therefore be implemented and measured in
isolation, before any decision about which descriptor to add next.

Scope

  • 20×20 grid over both images; per cell-pair match counts.
  • 9-cell neighbourhood scoring (getNB9 upstream).
  • Threshold alpha * sqrt(mean points per cell), alpha = 6 by default; cells
    above threshold have all their matches marked inlier, the rest are discarded
    wholesale.
  • Four half-cell grid offsets (x, y, and both), so a match straddling a cell
    border is not penalised.
  • withRotation — 8 permutation patterns of the 9-cell neighbourhood.
  • withScale — 5 grid size ratios on the train side.
  • Keep the configuration producing the most inliers.
  • Signature mirroring matchGMS(size1, size2, keypoints1, keypoints2, matches1to2, withRotation, withScale, thresholdFactor).
Both invariance flags default to false

As in OpenCV. The full search costs 8 × 5 configurations × 4 offsets = 160 grid
passes against 4 — still linear in the number of matches and cheap in absolute
terms, but no longer negligible, and the caller should pay only for what they
use.

The full paths are nevertheless implemented, not skipped: #96 makes
jsfeatNext the numeric oracle for the PureCV port, and a partial implementation
yields a partial oracle. If the rotation path does not exist here, it has to be
debugged directly in Rust + WASM when PureCV adds it. It is also genuinely
needed: initial detection against a stored pattern_t has arbitrary in-plane
rotation, unlike frame-to-frame tracking.

Acceptance criteria

  • Bit-exact against OpenCV fixtures on all three paths — default,
    withRotation, withScale — not only the default. The "keep the best
    configuration" loop and the permutation table are where the bugs hide.
  • An OpenCV-independent property test: on cornerScene under an exact
    translation (dx, dy), the post-filter inlier ratio is >= the pre-filter
    ratio, and every discarded match is genuinely inconsistent with the known
    translation.
  • Degenerate inputs handled: zero matches, one match, all matches in one
    cell, images smaller than the grid.
  • Shared-pool buffers balanced (get_buffer / put_buffer).
  • Attached as jsfeatNext.gms and covered by the API-shape test.
  • No new any (#85).

Out of scope

  • LOGOS or any other geometric verification method.
  • Changing find_homography or motion_estimator.
  • Wiring GMS into the CvBackend adapter — that is the filterMatches seam of
    #129, delivered by #136.

Dependencies

  • #133 — bfmatcher: match_t must exist before there is anything to filter.
  • #132 — OpenCV ground-truth fixtures.
  • #130 — licence-header variant, since this is OpenCV-derived code.

Related

  • Contract seam: #129
  • Consumer: #97 (planar tracker inlier ratio)
  • Plan: docs/features2d-expansion-plan.md

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with src/gms/gms.ts and the upstream getNB9 behavior, then inspect the OpenCV ground-truth fixtures and the cornerScene property-test requirements. Verify default, rotation, and scale paths, degenerate inputs, shared-pool balancing, the jsfeatNext.gms export, and the API-shape test; done means all listed acceptance checks pass without new any types.

Written by the indexing model from the issue text.

Assessment

Tech stack
typescript
Domain
computer-vision, testing
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.