Goal

Detect oriented keypoints from a greyscale image at multiple scales and compute a 256-bit binary descriptor per keypoint suitable for Hamming-distance matching. Input: a greyscale image $I$. Output: a list of keypoints $(x, y, \theta, \ell)$ — pixel location, orientation angle, and pyramid level — each paired with a 256-bit binary descriptor $\mathbf{d} \in \{0,1\}^{256}$. The defining property is a rotation-invariant binary descriptor pipeline (oFAST + rBRIEF) that operates at video rate on a single CPU core without GPU or SIMD acceleration.

Algorithm

Let $I: \Omega \to \mathbb{R}$ denote the greyscale input image. Let $I_\ell$ denote the image at pyramid level $\ell$, with $I_0 = I$. Let $s = \sqrt{2}$ denote the scale factor between successive pyramid levels. Let $L = 5$ denote the total number of pyramid levels. Let $N$ denote the target total keypoint count. Let $r = 15$ denote the half-width of the 31-pixel orientation patch (so the patch covers $[-r, r]$ in both dimensions). Let $R_H$ denote the Harris cornerness response used to rank FAST candidates. Let $p$ denote the integral-image-smoothed patch on a $31 \times 31$ window centred at a keypoint. Let $w_p = 31$ denote the patch side length. Let $w_t = 5$ denote the sub-window side length used in each binary test. Let $n = 256$ denote the descriptor bit length. Let $S$ denote the $2 \times n$ matrix of test-pair offsets. Let $R_\theta$ denote the $2 \times 2$ rotation matrix for angle $\theta$. Let $S_\theta = R_\theta S$ denote the steered offset matrix. Let $\tau$ denote a single pixel-pair test. Let $f_n$ denote the packed binary descriptor. Let $g_n$ denote the steered descriptor operator.

oFAST: oriented FAST

rBRIEF: rotated BRIEF

The candidate test pool is drawn from the $(w_p - w_t)^2 = 676$ possible non-overlapping $5 \times 5$ sub-window positions inside the $31 \times 31$ patch. Pairing two sub-windows and discarding pairs whose support overlaps yields $M = 205{,}590$ usable test pairs.

Greedy uncorrelated-test selection

This one-time offline step produces the steered table $\mathcal{T}$. It is run once on the PASCAL 2006 training set and the resulting table is compiled into the algorithm.

Implementation

The runtime descriptor packing in Rust, given a precomputed steered offset table indexed by angle bin:

const N: usize = 256;
const WORDS: usize = N / 64;
const BINS: usize = 30;

type Descriptor = [u64; WORDS];

struct SteerTable {
    offsets: [[(i32, i32); 2]; N],
}

fn box_sum(ii: &[u32], stride: usize, h: usize, cx: i32, cy: i32, r: i32) -> u32 {
    let x0 = (cx - r).max(0) as usize;
    let y0 = (cy - r).max(0) as usize;
    let x1 = (cx + r).min(stride as i32 - 1) as usize;
    let y1 = (cy + r).min(h as i32 - 1) as usize;
    ii[y1 * stride + x1]
        .wrapping_sub(ii[y0 * stride + x1])
        .wrapping_sub(ii[y1 * stride + x0])
        .wrapping_add(ii[y0 * stride + x0])
}

fn rbrief(
    ii: &[u32], stride: usize, h: usize,
    kx: i32, ky: i32, theta: f32,
    table: &[SteerTable; BINS],
) -> Descriptor {
    let step = 2.0 * std::f32::consts::PI / BINS as f32;
    let bin = ((theta / step).round() as isize).rem_euclid(BINS as isize) as usize;
    let st = &table[bin];
    let half_wt: i32 = 2;
    let mut d: Descriptor = [0u64; WORDS];
    for (i, pair) in st.offsets.iter().enumerate() {
        let s1 = box_sum(ii, stride, h, kx + pair[0].0, ky + pair[0].1, half_wt);
        let s2 = box_sum(ii, stride, h, kx + pair[1].0, ky + pair[1].1, half_wt);
        if s1 < s2 {
            d[i / 64] |= 1u64 << (i % 64);
        }
    }
    d
}

fn hamming(a: &Descriptor, b: &Descriptor) -> u32 {
    a.iter().zip(b.iter()).map(|(x, y)| (x ^ y).count_ones()).sum()
}

Remarks

• Per-keypoint description costs $O(n)$ integer comparisons — one integral-image box-sum pair per test — plus $\lceil n / 64 \rceil$ word-level XOR + popcount for matching. Pyramid construction, FAST, and the Harris ranking dominate frame time over the descriptor packing itself.
• Scale is handled by a discrete 5-level $\sqrt{2}$ pyramid; a keypoint's scale is the pyramid level at which it survived non-maximum suppression, not a continuous sub-level interpolation. Rotation is handled by the intensity-centroid orientation, which is reliable only when $|C|$ is bounded away from zero.
• Naively rotating the BRIEF test set collapses descriptor variance: the eigenvalue spectrum after PCA on steered-but-unlearned BRIEF is far sharper than for unsteered BRIEF. The greedy decorrelated selection is what restores the variance — without the learned offset table, steering hurts more than it helps.
• ORB is in-plane rotation invariant only. The intensity-centroid orientation is a single scalar and cannot encode 3-D tilt independently; out-of-plane rotation degrades matching, and the binary descriptor provides no recovery mechanism.
• Common extensions include per-keypoint scale interpolation across pyramid levels, GPU and SIMD popcount acceleration, and learned descriptor stacks that replace the entire oFAST + rBRIEF pipeline with a jointly trained network.

References

1. E. Rublee, V. Rabaud, K. Konolige, G. Bradski. ORB: An efficient alternative to SIFT or SURF. ICCV, 2011. doi.org
2. M. Calonder, V. Lepetit, C. Strecha, P. Fua. BRIEF: Binary Robust Independent Elementary Features. Lecture Notes in Computer Science, 2010. link.springer.com
3. E. Rosten, T. Drummond. Machine Learning for High-Speed Corner Detection. European Conference on Computer Vision, 2006.
4. C. Harris, M. Stephens. A Combined Corner and Edge Detector. Alvey Vision Conference, 1988.
5. D. G. Lowe. Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision, 2004.