Tracker: typed pyramidal Lucas–Kanade

Tracker follows a caller-supplied set of points from a previous Gray image to a current Gray image. It does not detect features, assign identities, compact lost points, or retain frames. Compose detection and tracking in the application. Use FAST+BRIEF when detection must also produce descriptors; that fused operation does not accept arbitrary Tracker output points. Describing tracked points requires a separate application-supplied stage. Tracker is EV74-only; selecting A65 must return unsupported rather than silently running a different algorithm.

Contract

All tensors are contiguous. Images have rank 3–6 and trailing [H,W,1] with UInt8 pixels. Let O denote the unchanged leading outer axes and K capacity. For an unbatched image [H,W,1], points are [K,2], not [1,K,2].

Port	Shape	Dtype	Meaning
Input 0	O + [H,W,1]	UInt8	Previous image
Input 1	O + [H,W,1]	UInt8	Current image, same geometry
Input 2	O + [K,2]	Int32 or Float32	Previous XY point coordinates
Input 3	O + [1]	Int32	Number of occupied prefix slots per image
Optional input 4	O + [K]	Int32	Prior status: zero skips, nonzero tracks
Output 0	O + [K,2]	Float32	Current XY point coordinates
Output 1	O + [K]	Int32	1 tracked; 0 lost, skipped or unused

Counts stay device-resident, permitting FAST → Tracker without reading counts on A65. check_inference() validates metadata, not tensor contents. The native entry validates every count against [0,K] before launching kernels or writing outputs. Invalid counts return an invocation error without partial outputs. Valid but untrackable points are per-point results, not invocation errors. Tails [count,K) are zero-filled in both outputs on every invocation.

An active point that cannot be solved retains its input coordinate and status zero. Finite output outside the image has status zero; its computed coordinate is retained. Nonfinite Float32 input points are returned unchanged with status zero and never converted to integer indices. Int32 extreme values are rejected as points before coordinate subtraction; their output representation is the normal Float32 conversion. Prior-status suppression also preserves coordinates.

Limits: each image axis is 1–4096; at most 64 flattened outer images; capacity 1–65536. These are explicit admission limits, not silent clamps. There is no strided/image-format conversion and no MLA tiled layout for this operation.

Parameters

Parameter	Default	Range	Meaning
window_half	7	1–15	Window width and height are 2*window_half+1
max_iterations	20	1–100	Maximum LK updates at each level
pyramid_levels	0	0–4	Downsampled levels above full resolution

The fixed determinant threshold is 1e-6; squared update convergence threshold is 0.0009 (0.03 pixels). Reaching the iteration cap is not itself failure. Status is not a confidence score, minimum-eigenvalue test, forward/backward consistency test or guarantee that a physical feature was found.

C++ call

Use ops::tracker::check_inference() to obtain an immutable owned plan from explicit input/output specifications. ev74::tracker encodes a versioned little-endian native descriptor without allocating buffers or submitting work.

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

Runtime maps buffers, binds addresses and owns coherency and dependency ordering. It must retain inputs, outputs and any workspace until confirmed device completion. A synchronous call waits for the submitted job; see the call lifecycle.

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

namespace k = simaai::kernels;
const std::array inputs{
    k::TensorSpec{{480, 640, 1}, k::DType::UInt8}, // previous image
    k::TensorSpec{{480, 640, 1}, k::DType::UInt8}, // current image
    k::TensorSpec{{256, 2}, k::DType::Float32},    // fractional XY seeds
    k::TensorSpec{{1}, k::DType::Int32},    // active prefix count, on device
    k::TensorSpec{{256}, k::DType::Int32}}; // optional previous status
const std::array outputs{k::TensorSpec{{256, 2}, k::DType::Float32},
                         k::TensorSpec{{256}, k::DType::Int32}};
const k::ops::tracker::Params params{
    .window_half = 7, .max_iterations = 20, .pyramid_levels = 2};
auto checked = k::ops::tracker::check_inference(
    {inputs, outputs, params});
if (auto *e = std::get_if<k::Error>(&checked)) return *e;
const auto &plan = std::get<k::ops::tracker::Plan>(checked);
auto invocation = k::ev74::tracker::encode_relocatable(plan);
if (auto *e = std::get_if<k::Error>(&invocation)) return *e;
// Encoding leaves device addresses unbound; no device work has run.
return {};

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

Memory and lifecycle

The plan exposes all input/output requirements and workspace_requirements(). For zero pyramid levels, bind an empty scratch region with both address and capacity zero; an unused nonempty region is rejected. Otherwise, scratch holds both image pyramids for one outer image, reused serially across the batch:

scratch_bytes = 2 * sum(align_up(width[level],16) * height[level])
width[level]  = ceil(width[level-1]/2)
height[level] = ceil(height[level-1]/2), level=1..pyramid_levels

Scratch alignment is 16 bytes; points/count/status require 4-byte alignment; images require byte alignment. Inputs may overlap other read-only inputs. Outputs and nonempty scratch must not overlap any other binding. A separate scratch allocation is required for each simultaneously in-flight invocation. Nothing in the kernel caches frames or pointers between invocations. Sharing a plan is safe; reusing mutable buffers before completion is not.

For frame-to-frame feedback, supply Float32 output points as the next call's Float32 seeds and output status as optional prior status. Keep or forward the occupied prefix count, and rotate image/buffer owners through Runtime completion dependencies. Use distinct output buffers: in-place updates are rejected. This preserves subpixel points and holes without A65 rounding or compaction. Replenishing holes is a separate application policy.

Numerical behavior

Pyramid construction

Each downsampled pixel samples a clamped 3×3 neighborhood centered at (2x,2y). The horizontal and vertical weights are [1,2,1]. Accumulate the exact integer weighted sum, add 8, shift right 4, and store UInt8. Odd dimensions round upward. This is the implemented filter; it is not OpenCV's different pyramid filter. Pyramid rows have 16-byte physical pitch alignment, avoiding two workers writing one DMA output granule. The padding bytes are not logical pixels or sampled.

Coordinates, tiles and borders

Let h=window_half, so the tracking window has side 2*h+1. At level L, the previous center s=(sx,sy) is (x >> L,y >> L) for Int32 seeds and (x/2^L,y/2^L) for Float32 seeds. Define q=floor(s) and template fraction t=s-q componentwise. Int32 seeds therefore have t=(0,0) at every level; Float32 seeds retain their subpixel location.

Propagated flow v=(vx,vy) starts at zero at the coarsest level. With g=floor(v), load these square tiles at each level. Reject nonfinite flow or either component with magnitude greater than 16384 before converting g to integer coordinates:

Tile	Top-left coordinate	Side in pixels
Previous template and gradient halo	q - (h+1,h+1)	2*h+3 for Int32; 2*h+4 for Float32
Current search tile	q + g - (h+4,h+4)	2*h+10

Both tiles must fit completely inside that image level. A failed fit loses the point; no image-border extension is used here. Float32 templates reserve the extra right column and bottom row even when a fractional component is zero. This is separate from the clamped borders used to build the pyramid.

Tiles are shown at one level, not to scale. The current tile moves by the integer flow g; iterations refine a residual inside that fixed tile. An admitted image shape does not guarantee that a particular point's tiles fit.

Ordered FP32 sampling and updates

For fractional offsets (fx,fy) and neighboring values I00 at (u,v), I10 at (u+1,v), I01 at (u,v+1), and I11 at (u+1,v+1), bilinear sampling is:

w00 = (1.0f-fx)*(1.0f-fy); w01 = fx*(1.0f-fy)
w10 = (1.0f-fx)*fy;        w11 = fx*fy
sample = ((I00*w00 + I10*w01) + I01*w10) + I11*w11

Previous samples use fraction t. When both components of t are zero, read the previous pixels directly instead. Form the template P and central differences Ix=(right-left)*0.5f, Iy=(down-up)*0.5f; for a fractional template, each neighbor is itself sampled with the same t. Values and gradients are FP32.

For Gxx=sum(Ix*Ix), Gxy=sum(Ix*Iy) and Gyy=sum(Iy*Iy), zero 16 FP32 accumulators per sum. Visit rows from top to bottom and columns left to right; window column c contributes to lane c % 16, restarting the column index on each row. Padded lanes contribute zero. Reduce the lanes by adding pairs at offsets 8, then 4, then 2, then 1, retaining the lower half at each step. The residual-gradient sums below use this same accumulation and reduction order.

Let det=Gxx*Gyy-Gxy*Gxy. A nonfinite determinant or det<1e-6 loses the point; otherwise compute inv=1.0f/det. Initialize the tile-local residual to r=v-g+t, preserving this expression order. At each iteration:

1. Reject a nonfinite residual or either component with magnitude greater than 16384 before integer conversion.

2. Set bx0=clamp(4+floor(rx),0,8) and by0=clamp(4+floor(ry),0,8). Keep fx=rx-floor(rx) and fy=ry-floor(ry) unchanged. Sample the current tile at each window offset plus (bx0,by0) using the weights above.

3. Form It=P-sampled_current, then bx=sum(It*Ix) and by=sum(It*Iy).

4. Update the residual in this order:

   drx = (Gyy*bx - Gxy*by) * inv
   dry = (Gxx*by - Gxy*bx) * inv
   rx += drx; ry += dry
   stop if drx*drx + dry*dry < 0.0009f

Products and additions are separate FP32 operations; native OpenCL is compiled with FP contraction disabled. At the iteration limit, a finite residual is accepted even without convergence; a nonfinite final residual loses the point. Recover flow as v=(g+r)-t; the Int32 single-level path directly uses r, since g=t=0.

Coarse-to-fine flow and final status

Before the next finer level, the Int32 compatibility route applies: vx=2.0f*vx-((x>>(L-1))&1) and likewise for Y. The Float32 route instead doubles the flow without this parity adjustment. Float32 seeds may therefore differ from Int32 seeds with numerically equal coordinates when pyramids introduce fractional centers. This is an explicit extension, not a cast or a claim of bitwise compatibility.

If every level succeeds, the output is the original point plus the final flow. Status is one only when both output coordinates lie in the inclusive ranges [0,W-1] and [0,H-1]; an out-of-image computed coordinate is retained with status zero. A failed level preserves the original input coordinate instead.

The four-pixel per-level search margin is finite: clamping the integer residual while preserving its fraction does not provide an unbounded motion search. Pyramids increase motion reach, not tracking quality guarantees. Border, finite value and status checks protect indexing; they are not a confidence metric.

Implementation notes

The wrapper builds previous/current pyramids, then invokes the point kernel for each outer image. Dispatch uses at most four available workers. Point work is capped by output capacity, not active count: inactive slots still need their required coordinate/status initialization. If the coarsest image cannot contain the search patch, pyramid construction is skipped; the ordinary point entry still publishes original active coordinates, lost status and initialized tails.

Workers own disjoint point ranges and pyramid rows. Pyramid downsampling uses five input-row slots: three hold the current stencil and two prefetch the next rows. Adjacent stencils reuse their shared row, including replicated borders. Packed integer SIMD handles the regular interior; exact border/tail handling preserves the integer 3×3 weighting and (sum + 8) >> 4 rounding. Two output slots overlap writes with subsequent computation. Every event retires before slot reuse or return; no cross-worker reduction is needed.

UInt8 point patches move to VCCM with 2D DMA. Current patches convert to FP32 once per point/level; gradients and iterations then read local memory. Both Int32 and Float32 single-level routes overlap the next point's DMA with current-point computation, preserving the fractional route's original FP32 expression order. Local padded lanes are initialized once when a worker slot first becomes live; every dynamic image byte is overwritten before use. No tensor content or padding state is cached across jobs, and the final pending event is always drained.

Pyramidal tracking retains the coarse-to-fine per-level schedule. A worker may reuse its most recent admitted seed's result when the coordinate bits match exactly and prior-status admission succeeds. Images, pyramids and parameters are immutable within that invocation; the cache does not cross jobs. This does not introduce a CPU seed conversion or relax coordinate/status checks.

Tests and qualification

EV74/tracker/tests/correctness.cpp runs independent scalar mathematical references against the actual OpenCL source in a host vector/deferred-DMA model. It covers Int32/Float32, feedback, prior status, rank/batch/worker variants, pyramid levels, window limits, odd tails, invalid counts and binding errors. The model checks software ordering; it does not simulate EV ISA, cache behavior, DMA bus details or target latency. ASan/UBSan host results and a private MetaWare build are separate from device correctness.

runtime_e2e.cpp executes public Runtime submission and checks independent results and buffer guards before measurement. It also submits two consecutive invalid later-batch counts and requires retired errors with every output and workspace byte unchanged. Subsequent dependent Float32 feedback jobs consume device-produced points/status directly, use separate per-in-flight scratch and verify surviving fractional coordinates without a host seed conversion or copy. The platform error-reply path must leave the service available for these jobs. Device comparison uses exact statuses and an absolute 0.002-pixel FP32 coordinate bound; host-model comparisons use a tighter 0.00003-pixel bound. Both compare every slot, not only successful tracks. The default fixture measures submit-to-completion latency and process CPU time with 5 warmups and 100 samples; non-median statistics are diagnostic. No reviewed native Tracker latency baseline is established by compilation or host tests. Firmware composition and real-device qualification remain explicit.