webarkit / webarkit/jsfeatNext

Add FREAK binary descriptor module

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

Nobody has claimed this yet.

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

Description

Summary

Add src/freak/freak.ts — the FREAK descriptor (Alahi et al., CVPR 2012),
ported from OpenCV's xfeatures2d, alongside the existing orb binary
descriptor.

Scope narrowed from the original wording: this issue is FREAK and only FREAK.
TEBLID and GMS now have issues of their own.

Motivation

jsfeatNext ships one binary descriptor (orb, ORB/rBRIEF-style). FREAK uses a
retinal sampling pattern with pairwise intensity comparisons and occupies a
niche none of the alternatives cover:

It estimates orientation internally, from 45 long-distance sampling pairs
(NB_ORIENPAIRS), instead of relying on an angle supplied by the detector. That
matters concretely: detectors that produce no orientation (StarDetector/CenSurE
being the obvious candidate for PureCV) work with FREAK out of the box, whereas
pairing them with TEBLID would require a separate orientation estimator such as
the intensity centroid ORB uses.

It also supports cascade matching — the first 16 bytes reject most candidates
before the remaining 48 are compared — which sits naturally on top of a
Hamming brute-force matcher.

Scope

  • Retinal sampling pattern, pairwise intensity comparisons → binary descriptor.
  • Internal orientation estimation from the 45 long-distance pairs.
  • API shaped like orb.describe(...) for consistency.
  • Attached as jsfeatNext.freak.

The design decision this issue must make explicitly

Pattern generation is not a porting detail. OpenCV's buildPattern()
allocates NB_SCALES × NB_ORIENTATION × NB_POINTS = 64 × 256 × 43 = 704,512
PatternPoint structures of 12 bytes each — roughly 8.5 MB on the heap at
construction. That is heavy for WASM and simply impossible for no_std on
constrained targets, which is what the PureCV port faces downstream.

This is not intrinsic to the algorithm, only to OpenCV's implementation, which
trades memory for computation. Three options:

  1. Compute on demand. Pattern points are
    (x·cosθ − y·sinθ, x·sinθ + y·cosθ) scaled; recomputing them per keypoint
    costs a few dozen float operations against 8.5 MB saved. Preferred.
  2. Reduce NB_ORIENTATION from 256 to 32 or 64 → a ~1–2 MB table, with
    negligible loss of angular precision (256 steps is 1.4°, well beyond the real
    accuracy of any orientation estimator).
  3. Lazy per-scale population of only the scale indices the frame's keypoints
    actually use.

Suggested resolution: (1) as the default, (2) available as an option. Whichever
is chosen must be stated in the PR description, because PureCV inherits it — and
if the decision stays implicit, the OpenCV implementation gets ported literally
and the memory profile comes with it.

Acceptance criteria

  • Descriptors bit-exact against OpenCV fixtures, computed from the committed
    keypoint set.
  • The pattern-generation strategy is chosen deliberately and documented in
    the PR, with its memory cost stated.
  • Orientation estimated internally; a rotated-input property test shows
    descriptor stability without any detector-supplied angle.
  • Keypoints near the image borders handled explicitly, not silently
    contaminated (cf. #110).
  • Shared-pool buffers balanced; no new any (#85).
  • Attached to the namespace and covered by the API-shape test.

Non-goals

  • BRISK, AKAZE, and a full features2d-equivalent suite.
  • TEBLID — separate issue.
  • Match filtering — see #134.
  • Not blocked on haar/bbf (#43/#44).

Dependencies

  • #131 (FREAK computes box means over an integral
    image).
  • #132.
  • #130 (OpenCV-derived code).
  • #128, for the descriptor-kind selection this module is exposed through.

Related

  • Sibling descriptor: #135
  • Descriptor selection contract: #128
  • 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/freak/freak.ts and the existing orb.describe(...) implementation, then review docs/features2d-expansion-plan.md and dependencies #131, #132, #130, and #128. Compare against OpenCV fixtures and the rotated-input property/API-shape tests; done means FREAK is attached to jsfeatNext.freak, handles borders and shared-pool buffers, and documents the chosen pattern strategy and memory cost.

Written by the indexing model from the issue text.

Assessment

Tech stack
opencv, typescript
Domain
computer-vision
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.