webarkit / webarkit/jsfeatNext

feat(bfmatcher): brute-force Hamming matcher and match_t

Open
#133 0 comments 0 reactions 1 assignee View on GitHub

@kalwalt is already working on this.

Since Aug 25, 2026.

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

Description

Summary

Add src/bfmatcher/bfmatcher.ts — a brute-force Hamming matcher for binary
descriptors — plus the match_t correspondence type.

This is the first half of #83, extracted so it can land independently.
#83 narrows to pose_estimator.

Why

jsfeatNext can detect keypoints and compute ORB descriptors, but it cannot match
them. The only matcher in the repository is match_pattern(), written inline in
examples/sample_orb_pinball.html. A consumer of the published package
therefore cannot run the natural-feature pipeline end to end without
reimplementing matching themselves.

Two further things depend on this:

  • GMS (separate issue) is a post-matching filter. Without a matcher and a
    match_t type it has nothing to operate on.
  • TEBLID (separate issue) produces 64-byte descriptors at p512. The matcher
    must therefore handle arbitrary descriptor widths from the start, not the
    32 bytes the sample hardcodes.

Extracting this from #83 keeps pose_estimator — the larger, more speculative
half — off the critical path.

Scope

#83 already carries a full prototype in its body; this issue is its
implementation, with one correction (generalised width).

  • match_t { queryIdx, trainIdx, distance }, the equivalent of cv::DMatch.
  • match(query, train, maxDistance) — nearest neighbour, with optional
    crossCheck.
  • knnMatch(query, train, k) — k nearest neighbours per query descriptor.
  • ratio_test(knn, ratio) — Lowe's ratio test helper.
  • Hamming distance via SWAR popcount over the Int32Array view, bit-identical
    to the sample's popcnt32.
  • Generalised descriptor width (columns a multiple of 4), not hardcoded to
    32 bytes.
  • Attached to the namespace as jsfeatNext.bfmatcher (singleton, per the
    post-0.9.0 convention) and jsfeatNext.match_t (constructor).
  • NORM_HAMMING mirrors OpenCV's constant value.

Acceptance criteria

  • match, knnMatch, ratio_test and crossCheck implemented, with the
    OpenCV-shaped API of the #83 prototype.
  • Numeric parity with the inline match_pattern() of
    sample_orb_pinball.html: same input descriptors produce the same
    correspondences and the same distances.
  • Works at 32 and 64 bytes per descriptor, so TEBLID p512 is supported
    the day it lands.
  • Buffers borrowed from the shared pool are balanced (get_buffer /
    put_buffer), covered by the pool-balance test helper.
  • No new any (see #85).
  • Attached to the namespace and covered by the API-shape test.

Out of scope

  • pose_estimator and homography-to-pose decomposition — stays in #83.
  • FLANN or any approximate nearest-neighbour index.
  • Match filtering / geometric verification — see #134.
  • Float descriptors and L2 distance: NORM_HAMMING is the only norm here.

Related

  • Split from: #83 (which narrows to pose_estimator)
  • Consumers: #134 (GMS), and #135 (TEBLID) for end-to-end matching tests
  • Contract: #128 (Match type and match kind guard), #129 (filterMatches)
  • 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.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.