A Fast and Memory-Efficient Algorithm for Searching Faint Moving Objects using Synthetic Tracking

Detecting unknown faint moving objects using optical imaging is challenging. Long exposure times are infeasible for such targets, as the resulting image streaking causes a loss of signal-to-noise ratio due to energy dispersal across multiple pixels. To address this, synthetic tracking, a track-before-detect method, replaces long exposures with many short exposures, integrating them in post-processing to recover the moving signal. Enabled by modern CMOS detectors with fast readout and low read noise, this technique synthesizes telescope tracking by searching over a grid of velocities. However, the conventional brute-force implementation imposes a significant computational burden: integrating N_f frames of size (N_x,N_y) requires O(N_x N_y N_f^3) operations. This cost becomes prohibitive for megapixel-scale frames with N_f~100. Although dynamic programming can reduce the computational complexity by a factor of N_f, it requires a prohibitive memory of O(N_x N_y N_f^2), unsuitable for large-format detectors. This article presents a novel algorithm to achieve the computational efficiency of dynamic programming while maintaining a memory footprint of just O(N_x N_y N_f) by slightly approximating the computation of frame shifts for alignment. By expressing the shift as a sum of terms proportional to the digits frame index in binary and rounding up each of these terms, frames can be integrated efficiently by hierarchically adding intermediate sums that are shared across different velocities with the same higher bits in binary. The approximation only introduces a small tracking error that increases logarithmically with the number of frames. This advancement enables synthetic tracking to be executed with high energy efficiency, making it practical for deployment on standard workstations rather than requiring high-performance computing infrastructure such as GPU servers or CPU clusters.