Native FAST corner detection

Contract

ops::fast::check_inference() admits one packed, contiguous UInt8 image tensor of rank 3–6 with trailing H,W,1. Leading axes describe independent images and are preserved on all outputs. Height and width are 7–4096.

With the default OutputEncoding::Separate, outputs are explicit, contiguous tensors in this order:

Role	Shape	Scalar
Points	[outer..., K, 2]	INT32, (x,y)
Scores	[outer..., K]	INT32
Count	[outer..., 1]	INT32

K is taken from the output shape and must be 1–65536. Output shapes must agree; there is no hidden allocation or dynamically resized tensor. OutputEncoding::Packed instead requires one contiguous INT32 tensor shaped [outer...,1+3*K]: [count,x0,y0,score0,x1,y1,score1,...]. The compact stage writes that representation directly on EV; Runtime does not repack features on the CPU. Only the count and valid records are written. All physical spans must fit EV74's 32-bit address capacity. Empty images, pitched layouts and non-grayscale channels are rejected.

Parameters

Params::threshold is an integer in [0,255], default 30. The FAST variant and nonmaximum suppression are fixed. Params::output_encoding defaults to OutputEncoding::Separate; set it to OutputEncoding::Packed when consuming count-prefixed feature lists. The cold named request uses output_encoding = "separate" or "packed".

Params::grid is optional. Its absence preserves raster-first selection. GridSelection{columns, rows, minimum_distance} instead selects strong corners by spatial cell before optional minimum-distance suppression:

Field	Range	Default when grid is present
columns	1..W	1
rows	1..H	1
minimum_distance	0..65535 pixels	0

The cold named fields are grid_columns, grid_rows and minimum_distance. Supplying any of them enables grid selection; unspecified fields use the defaults above. Supplying none leaves it disabled. An explicit GridSelection{} is score-ranked selection in one cell, not raster-first selection.

Numerical behavior

FAST-9 examines a radius-three ring of 16 samples. A corner needs a circular arc of nine samples strictly above center + threshold or strictly below center - threshold. Its score is the largest minimum contrast over all nine-sample arcs in either direction. The score is not decremented by one. For ring samples R[0..15] and center intensity C, all differences are signed integers:

S = max over start=0..15, polarity in {-1,+1}
      min over j=0..8 (polarity * (R[(start+j) % 16] - C))
score = S if S > threshold, otherwise 0

The upper panel gives the exact FAST sample positions: ring indices run clockwise from (0,-3), with X rightward and Y downward. Plain FAST needs only the radius-three ring. The lower panel's 15-pixel exclusion applies only to FAST+BRIEF, which also needs a complete 31×31 descriptor patch. Both operations apply NMS before their configured selection. The panels are schematic, not to scale.

A positive score survives 3×3 nonmaximum suppression when no eight-connected neighbor has a larger score. Equal-score neighbors survive. Border scores outside the valid radius-three centers are zero. Valid centers include x=3 and y=3, through W-4 and H-4.

Without a grid, features are emitted in increasing (y,x) order, retaining the first K; this default is not score-ranked top-K. All coordinates and scores are exact integers; there is no floating-point tolerance. Only count and records [0,count) are written. Unused point and score bytes are preserved and must not be consumed.

Grid selection and spacing

Grid selection examines all legal post-NMS corners before capacity truncation. The grid covers the full image, including its feature-ineligible borders. For Gx = columns, Gy = rows, define the row-major cell index and quota:

cx = floor(x * Gx / W)
cy = floor(y * Gy / H)
c  = cy * Gx + cx
M  = Gx * Gy
q(c) = floor(K / M) + (c < K % M ? 1 : 0)

Cell X boundaries are ceil(cx*W/Gx) and ceil((cx+1)*W/Gx); Y boundaries use the corresponding formula. These half-open rectangles assign every pixel once even when image dimensions do not divide the grid dimensions.

Within each cell, retain at most q(c) corners in descending score order, with ties resolved by increasing y, then x. Combine cell winners in that same global order. Empty or sparse cells do not lend unused quota to other cells. When K < M, only the first K row-major cells have quota one; all other cells have quota zero. Choose an appropriate grid for the requested output capacity.

If minimum_distance > 1, visit this ordered frontier and accept a corner only if every previously accepted corner satisfies:

(x - previous_x)^2 + (y - previous_y)^2 >= minimum_distance^2

Distance equality is accepted. Suppression crosses cell boundaries and uses overflow-safe integer arithmetic. No discarded or suppressed corner is refilled: spacing can reduce the count below the cell quotas. Distances zero and one do not suppress distinct integer-coordinate corners. The final output order remains score descending, then raster ties. These rules are deterministic across worker counts and are shared by FAST+BRIEF.

FAST scores -> unchanged 3x3 NMS -> per-cell strongest quotas
                                      |
                                      v
                             global score/raster order
                                      |
                                      v
                        greedy cross-cell spacing -> outputs

C++ call

The call below uses installed public headers to construct explicit input/output specifications, check the request and encode a relocatable descriptor. It does not submit device work.

Place the includes and namespace aliases at file scope; the remaining statements belong in a simaai::kernels::Status-returning caller function.

Runtime's EV74 executor accepts the typed request, maps buffers, binds addresses and submits input/output views plus an explicit workspace view asynchronously. Runtime must retain all bound storage until confirmed device completion. Wait for that completion before accessing results or reusing storage.

#include <array>
#include <simaai/kernels/ev74/fast.h>

namespace k = simaai::kernels;
namespace op = k::ops::fast;
namespace ev = k::ev74::fast;
const std::array inputs{k::TensorSpec{{2, 480, 640, 1}, k::DType::UInt8}};
const std::array outputs{k::TensorSpec{{2, 1024, 2}, k::DType::Int32},
                         k::TensorSpec{{2, 1024}, k::DType::Int32},
                         k::TensorSpec{{2, 1}, k::DType::Int32}};
op::Params params{};
params.threshold = 30;
params.grid = k::GridSelection{8, 6, 16}; // Omit for default raster-first selection.
auto admitted = op::check_inference({inputs, outputs, params});
if (auto *error = std::get_if<k::Error>(&admitted)) return *error;
const auto &plan = std::get<op::Plan>(admitted);
auto encoded = ev::encode_relocatable(plan);
if (auto *error = std::get_if<k::Error>(&encoded)) return *error;
// Encoding leaves device addresses unbound; no device work has run.
return {};

See the host contract tests (EV74/fast/tests/correctness.cpp) and device fixture (EV74/fast/tests/runtime_e2e.cpp) for binding and execution coverage.

Memory and lifecycle

The immutable plan owns its specs and reports every input/output requirement. workspace_requirements() reserves batch * 4 * (1 + 3*K) * sizeof(INT32) bytes for up to four workers. This is the default raster-first workspace. Grid selection instead requires the following per-image storage, multiplied by batch:

d = minimum_distance
bin_bytes = d > 1 ? ceil(W/d) * ceil(H/d) * 4 : 0
map_bytes = round_up_to_4(max(W*H, bin_bytes))
grid_workspace_bytes = map_bytes + 12*K + (d > 1 ? 4*K : 0)

The byte score map is reused for spatial-bin heads after candidate extraction; the K coordinate/score records and optional links remain private scratch. Grid work uses bounded local row buffers and 256-bin score histograms, not a capacity-sized local heap. Caller allocation must use the plan's reported requirement, not the default formula. Allocate separate workspace for concurrent submissions. Workspace and writable outputs must not overlap any other binding. Input byte alignment is one; points, scores, count and workspace require four-byte alignment.

Native entry simaai_kernels_ev74_fast_v3 validates its 256-byte, version-three wire descriptor before dispatch. Relocation slots are input at byte 16, points/scores/count at 24/32/40, and workspace at 56. Wire data is little-endian; C++ plan objects are not wire descriptors. Runtime owns allocation, mapping, coherence, asynchronous transport and retirement. Firmware must explicitly register and capability-verify the entry.

Implementation notes

The default detector/compact leaves remain separate from grid processing; an ordinary call does not add per-pixel selection branches or score-map passes. The detector retains seven image rows and three score rows in VCCM, streams image rows with DMA and tests 16-column blocks with vector operations. Workers partition the flattened batch of legal center rows, using up to four useful workers. Each interval stages its frame-local NMS halo; halos never cross image boundaries. Unsigned-byte compass tests and a circular bit mask reject non-corners before scoring. Vector NMS and positive-row flags skip empty scans, while bounded scalar tails preserve the same border and tie rules. Compaction follows band order. Retaining at most K records per band is sufficient to preserve the global first K for every active worker count. Workers buffer 64 feature records locally and flush complete or partial blocks with DMA. Compaction reads these blocks, separates points and scores locally, and writes only the retained output prefixes. Initial row loads are batched; after scoring, the next row enters the dead ring slot while NMS consumes score rows. Every pending transfer completes before its storage is reused. A second dispatch writes the separate outputs. Serialized native calls reuse the two dispatcher handles; argument storage stays live through blocking enqueue. No numerical graph adapter or ConfigManager is involved. The larger BRIEF row ring is intentionally a separate fused operation.

Workspace bands and output prefixes can end inside a 16-byte DMA granule. Transfers therefore use only aligned complete granules; exact volatile byte stores handle each head and tail. Pending record writes retire before count publication, and no DMA touches another band's count or an output suffix.

The grid route streams all score/NMS rows into a byte map instead of stopping after the first K corners. A 256-bin histogram identifies each cell's exact score cutoff; raster tie selection enforces its quota. Counting/scatter produces the globally ordered bounded frontier. Histogram, pruning and scatter process bulk score-row spans through DMA into bounded VCCM storage; exact scalar edge accesses handle narrow or unaligned spans. Pruned spans use exact-edge DMA writes, retired before the local row is reused; neighboring cells remain untouched. A spatial-bin index performs exact greedy spacing without a quadratic scan of all previously accepted points. Internal bin divisions use max(minimum_distance, 1) even if guarded arithmetic is evaluated eagerly; the original parameter still controls spacing eligibility and its strict squared-distance comparison. There is no host readback, CPU sorting or per-cell host submission. Every DMA event retires before scratch reuse. Full-image selection necessarily does more work than an early-terminating raster-first call; code structure alone does not establish its latency or throughput.

Tests and qualification

EV74/fast/tests/correctness.cpp checks admission, byte capacities, wire rejection, mock dispatch and guards. With Clang, expressions.cpp executes the actual OpenCL source against an independent scalar oracle, including 1–4 workers, deferred DMA, ranks through six, border/tail cases, threshold extremes and truncation. Grid fixtures add literal strongest-late-corner, cross-cell ties/spacing, distance equality, uneven boundaries, sparse quotas, capacity-below-cell count, maximum distance, and independent scratch-size checks. They reuse dirty map storage across all worker/completion configurations and both output encodings. This is host-model evidence, not EV74 execution.

EV74/fast/tests/e2e/ builds a standalone Runtime/device fixture from installed packages. Its default invocation performs correctness and latency; --list-cases prints the catalogue. Exact outputs are checked outside timing. Reused buffers are dirtied and feature counts change between calls. Measurements report per-call completion latency in microseconds, warmups, raw samples and workload metadata. A private compiler build or measurement without a matched native baseline is not device correctness or performance qualification. The device catalogue includes grid correctness and VGA/HD grid latency cases; those new semantics have no pre-grid firmware reference and must not be reported as baseline-qualified gains.

Wire compatibility

This operation uses descriptor ABI 3, with output count at byte 12 and grid_columns, grid_rows, minimum_distance at bytes 136, 140 and 144. Zero columns/rows/distance mean the default mode; positive columns and rows enable grid selection. Remaining reserved words start at byte 148 and must be zero. Both output modes require matching host codecs and firmware. The versioned capability probe rejects older firmware before dispatch; rebuild the composed firmware and consuming packages together. Output encoding does not change detection, selection, scores or descriptor mathematics.