webarkit / webarkit/jsfeatNext
Add FREAK binary descriptor module
Nobody has claimed this yet.
- 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:
- 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. - Reduce
NB_ORIENTATIONfrom 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). - 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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