WorksPhysics and Astronomy
A Fast and Memory-Efficient Algorithm for Searching Faint Moving Objects using Synthetic Tracking
Abstract
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.
Introduction
Track-before-detect (TBD) is an important paradigm for detecting faint targets with unknown or poorly constrained trajectories [1, 2]. Detection difficulty increases substantially for rapidly moving sources, a scenario exemplified by small near-Earth objects (NEOs). These bodies are extremely faint at large geocentric distances but move rapidly once they approach Earth, at which point they may become marginally detectable. Discovering and monitoring small NEOs is a fundamental requirement for planetary-defense surveys for its large population [3]. Even a 30 m-diameter NEO can produce catastrophic damage upon impacting a densely populated region. We usually use long exposure to image faint targets to gain signal-to-noise ratio (S/N), however, motion-induced trailing loss arises when a moving target is imaged as an extended streak rather than a compact point-spread-function (PSF) spot [4]. Short-exposure imaging mitigates trailing loss; however, individual short-exposure frames do not contain sufficient signal energy to detect faint moving sources. Multiple short-exposure frames must therefore be co-added to boost the S/N. Based on these considerations, synthetic tracking has been developed to survey small NEOs [4, 5, 6]. Instead of acquiring a single long-exposure image, the technique operates on a 3-D image datacube composed of many short-exposure snapshots. In synthetic tracking, the integration of these short-exposure images numerically simulates on-sky tracking of a moving source by spatially shifting each frame according to a candidate target motion vector before the summation. Since the true target velocity is unknown, a grid of plausible velocities must be exhaustively searched. This brute-force search dominates the overall computational cost.
Although sub-pixel frame shifts can be implemented via interpolation, standard synthetic tracking pipelines only align the frames to integer-pixel precision, allowing a maximum tracking error of pixel [5]. For a datacube containing frames of dimension , surveys are typically configured such that targets move no more than one PSF width, or approximately one pixel, between consecutive exposures [6]. Therefore, we usually consider the range of motion is within the range of 1 pixel per frame when integrating the frames. Velocity grids are therefore commonly sampled over the range . Neglecting directional degrees of freedom, the total computational cost scales as with the number of velocities , with and being velocity components along and , yielding an overall complexity of . For megapixel-scale frames with frames, the total workload reaches the teraFLOP regime, necessitating massively parallel hardware. This computational bottleneck has motivated existing operational implementations, such as the JPL robotic telescope pipeline, to rely on GPU acceleration [6].
The fast discrete X-ray transform (FaXT) adapts a 2-D fast Radon transform algorithm built upon dynamic programming and divide-and-conquer principles [7] into a 3-D formulation, accelerating synthetic tracking by casting frame integration as a computed-tomography-style X-ray transform [8]. The computation of synthetic tracking has been significantly reduced to , times faster than the brute force approach. The primary practical limitation of FaXT is its substantial memory requirement of .
We propose a novel frame integration strategy that matches the computational speed of dynamic programming-based methods while limiting memory consumption to comparable to the memory footprint of the raw input datacube, in sharp contrast to required by the FaXT algorithm. Our method makes an approximation in the computation of the integer shifts of frames for aligning them to simulate a tracking rate and then integrates the frames by adding consecutive frame pairs, which allows us to explicitly store the required intermediate frames for signal integration.
Method
We name the proposed algorithm Fast Synthetic Tracking (FST), which will be presented in this section.
Conventional Implementation
The brute force formulation of synthetic tracking can be summarized in the pseudocode below. We sample velocities and on a grid spanning approximately pixel/frame. It is convenient to consider a grid with spacing being so that the tracking rate error is pixel/frame (maximum tracking error to be less than 0.5 pixel) and with candidate velocities taking discrete values . To simplify the discussion, let . Without loss of generality, let us consider the case where the candidate velocities are all positive. The cases with different signs can be done similarly by considering the frame shifts with the desired direction. Let denote the pixel coordinate in a frame, represent the intensity of frame , and be the integrated intensity with a linear tracking rate of respectively. We have the following pseudo-code (Python-like) for synthetic tracking integration as
detected_signals = []
for $v_x$ in $[0,1,\ldots,N_f-1]/N_f$:
for $v_y$ in $[0,1,\ldots,N_f-1]/N_f$:
$I_{\mathrm{ST}}(x,y,v_x,v_y)=0$
for in :
signals_detected = convolve > detection_threshold
detected_signals.append(signals_detected)
Here denotes a spatial filter kernel used to improve the detection S/N. A matched filter, constructed from the instrument PSF, is generally optimal for optical imaging data [5]. The brute force implementation yields a computational complexity of . For typical parameters and , the workload falls within the teraFLOP range, requiring GPU hardware or large CPU clusters.
Fast Synthetic Tracking
Operational synthetic-tracking pipelines currently depend on GPU acceleration to manage computational cost [6]. Our FST algorithm introduces a controlled approximation to drastically reduce computation while maintaining a memory footprint of memory of , matching the size of the input datacube.
The core mathematical approximation is to approximate the round function in and , for computing the integer shifts, as a sum of round of addends. To illustrate this, we use binary representations for
to have
where we have defined
Using the binary representations for ,
with , being bits, we compute
Similarly for direction, defining , we have
with presenting bits for in binary. The integration of frames or summing over the frame index can be viewed as summing over its bits , in its binary representation. With the round function approximation, the sum over ’s can be carried out independently because frame shifts are decoupled between the bits ’s.
Summing over bits ’s can be conveniently viewed as first summing over consecutive paired frames (lowest bit) and then summing over the consecutive resulting frames (the second lowest bits) and so on. This recursive formulation for frame integration is illustrated in Figure 1 and mathematically described below.

Figure 1. A schematic chart illustrating how the frames are integrated by pairing consecutive frames and the layout of memory usage to store the intermediate data frames.
Define the initial 3-D datacube
where the frame index has been explicitly expressed in terms of bits ’s. The standard synthetic-tracking summation
is rewritten using our bitwise decomposition and rounding approximation:
We perform recursion by summing sequentially over each binary bit. After summing over , we obtain
where we have introduced
with the base-level shift .
The general recursive update rule for stage m reads:
where
The recursion terminates at yielding the final integrated image .
At recursion level m, there are, there are totally intermediate arrays in view of the all the possible values of bits .
As sketched in Figure 1, the peak memory consumption scales as the total number of frames giving the amount of .
Because the computation of only needs and only depends on the th highest bits of velocity vector , we therefore can arrange the computation with nested loops over the velocity vector bits. Starting from the highest bit and compute at the outer loops whenever possible to minimize the number of computations. Therefore, can be computed at m-level of the loops. The pseudocode for the full recursive algorithm is:
for in :
for in :
for :
for :
for :
for :
Note that each loop involving velocity vector along two dimensions, therefore, at level- the computation amount has a factor from the nested loops, and we need to add frame-pairs (different 's), therefore summing the arithmetic workload, the total computational complexity is
The integrated frame can be passed into a detection threshold checking logic to create a list of detected signals.
So far, we have assumed the velocity range is up to 1 pixel/frame. In case the range is larger with , velocity components ranges being up to pixel/frame and pixel/frame, the total computation load is then , where we have used , . Compared with the brute force load of , the speed up is a factor of , which is significant for .
Results
In this subsection, we present results from applying FST to both simulation data and observational data from the Zwicky Transient Facility (ZTF).
Simulation Tests
We present single-thread CPU execution times of FST measured on an Apple Macbook Pro M3 Max processor for varying spatial dimensions and number of frames.
| CPU Time (sec) | |||
| 620 | 1000 | 1000 | 64 |
| 1230 | 1000 | 2000 | 64 |
| 1231 | 2000 | 1000 | 64 |
| 2448 | 2000 | 2000 | 64 |
Table 1. Single-thread CPU runtime for synthetic-tracking integration of 64 frames on an Apple M3-Max processor
Measured runtime scales linearly with and , consistent with our complexity analysis. The execution time also scales quadratically with number of frames as plotted in Figure 2. Note that the quoted timings here cover the full two-dimensional velocity search space (positive and negative velocity components); processing only the positive-velocity quadrant would reduce runtime by approximately a factor of four as considered in the estimation presented in § 2.2.

Figure 2. CPU time measured on Apple Max-M3 processor for using FST to integrate different number of frames of size (1K1K).
FST approximates the round of a sum as the sum of round values. This approximation introduces extra errors from the additional round errors, whose number is with random values within range [-0.5, 0.5]. This is the price paid to use FST compared with the brute force approach discussed in § 2.1.
We numerically evaluated the tracking errors for integrating different number of frames up to 1024. The true velocities are simulated with a quantum of to cover range of [0,1]. The maximum tracking errors is plotted against number of frames integrated shown in the left plot in Figure 3. It has an upper bound about . An upper bound of was reported by reference [7] where the definition of tracking error has a minor difference due to our distinct geometric formulation. A detailed explanation is provided in the Appendix.

Figure 3. Tracking errors of FST from simulation as function of number of frames: left plot displays maximum tracking error and right plot displays the mean of tracking error RMS (root-mean-squares) for different velocities.
The right plot in Figure 3 displays the mean and maximum of RMS (root-mean-squares) of the tracking error over the integrated frames. This quantifies how much larger the effective PSF is due to the tracking errors. As expected, it increases with the number of frames logarithmically. We also show in the Appendix the behavior of mean RMS is . The price paid for speeding up the computation to integrate 1000 frames is less than 0.7 pixel. Unless the PSF is smaller than 1 pixel, this extra error is in general small.
Because of the extra spread of the integrated signal from these tracking errors, the detection S/N is slightly lower than from the synthetic tracking with only the integer pixel shift error (+/-0.5 pixel). The tracking error would degrade the detection S/N relative the conventional implementation which only has tracking error up to pixel. With the quantification of the tracking error RMS, we can estimate the effective PSF after using FST. We did a simulation for different sizes of PSFs assuming a Gaussian shape. We then estimate the optimal kernel to be used to perform matched filter detection. The SNR degradation due FST relative to conventional implementation is displayed in Figure 4 as function of the size of PSF, which is measured in unites of Gaussian .

Figure 4. Degradation of signal-to-noise ratio (SNR) as function of PSF size.
Figure 5 displays examples of the integrated signal from integrating 128 frames for simulated six objects with different motion rates and PSF sizes.

Figure 5. Example PSFs after FST and conventional synthetic tracking of six objects used in simulation.
Application to Zwicky Transit Facility Datasets
As an application to detecting asteroids, we applied FST to integrate a deep drilling dataset from the Zwicky Transient Facility (ZTF) as demonstrated by reference [9]. Figure 6 displays what we discovered from integrating a datacube, taken on 2018 July 12, for which we integrated 128 frames over the central pixel area. The rates of motion suggest that these objects are likely main belt asteroids except for the first one, which is probably a Trojan asteroid going with the Jupiter. The number of detections is roughly 8 over about 0.3 Sqdeg. For ZTF’s large FOV of ~ 47 Sqdeg, we expect to detect about 1 thousand objects, which is consistent with the statistics reported by reference [9].

Figure 6. Example detections from integration 128 frames of a ZTF dataset over the center 2000x2000 pixels. The rates suggest that they are main-belt asteroids except for the first one, which is likely to be a Trojan asteroid moving with the Jupyter’s orbit.
Conclusions and Discussions
We have introduced the Fast Synthetic Tracking (FST) algorithm for detecting faint moving astronomical targets from multi-frame image datacubes. Our implementation achieves the computational speed-up of dynamic-programming-based FaXT yet limits memory consumption to , comparable to the raw input data volume, whereas FaXT requires memory. This algorithm enables synthetic-tracking processing on consumer-grade workstations and laptops, removing the historical requirement for dedicated GPU servers or large CPU clusters. It therefore lowers the deployment barrier for NEO search pipelines supporting planetary-defense efforts. FST only introduces a small amount of tracking errors (less than 0.7 pixel RMS for integrating 1000 frames), growing logarithmically with number of frames.
Beyond asteroid surveys, the algorithm can be adapted to one-dimensional streak-detection tasks, where it again offers substantial memory savings relative to conventional fast Radon-transform methods [7, 10]. Straightforward extensions also permit processing of four-dimensional datacubes. We anticipate that this low-memory fast formulation will facilitate broader adoption of synthetic-tracking techniques across additional application domains.
The code that we implemented the FST together with a test routine is available at https://github.com/ajzhai/fast-synthetic-tracking.
Acknowledgements
The authors would like to acknowledge the usage of observations obtained with the Samuel Oschin 48-inch Telescope at the Palomar Observatory as of the Zwicky Transient Facility project. ZTF is supported by the National Science Foundation under Grant No. AST-1440341 and a collaboration including Caltech, IPAC, the Weizmann Institute for Science, the Oskar Klein Center at Stockholm University, the University of Maryland, the University of Washington, Deutsches Elektronen Synchrotron and Humboldt University, Los Alamos National Laboratories, the TANGO Consortium of Taiwan, the University of Wisconsin at Milwaukee, and Lawrence Berkeley National Laboratories. Operations are conducted by COO, IPAC, and UW.
Appendix
Here we explain the upper bound of the behavior of maximum tracking error .
Let . FST tracking error can be computed as
If we want to maximize the round error of , the bit pattern of cannot be uniformly 1 or 0 because the round error would be 0. The maximum round error can be achieved when or . But the total error is no more than . Assuming a periodic pattern, we found that having a bit pattern of 0, 1, 0, 1, 0, would maximize the total errors. We can compute the round errors to be 1/2 -1/8 -1/32 + 1/2 -1/8/(1-1/4) =1/3. In the meantime, we have bits, so we alternatively taking the same sign of round errors, we also alternatively having bits to be 1’s for , so that each 1 would match a round error of 1/3, thus ½ bits to be 1’s alternatively with each 1 gives 1/3 error, thus the asymptotic behavior of 1/6 .
We now look at the average RMS. It is convenient to consider shifted bits:
so that these bits fluctuate around 0 with values of ±1/2. The tracking error can be expressed as
Because the errors from rounding numbers in general are unbiased, so the second term, which is the sum of these errors tend to be small. Now we show it is in range of [-0.5, 0.5]. First rearranging the terms gives
For the second term, shifting index and switching the order of sum, we have
where we can bound the negative part in the parenthesis by -2 when all the bits are one by summing the geometric series and the positive part in the parenthesis by 2, thus the total value can only be within .
Expanding the square and using , , we compute the RMS of tracking error as
Because , the overall shift of ½ cancels between the two terms and we get
and
Using and expanding the square, we calculate the first term as
We evaluate the second term by noting that
and using to get
Therefore,
the RMS of tracking error .
References
- [1]Reed, I. S., Gagliardi, R. M., & Stotts, L. B. 1988, ITAES, 24, 327
- [2]Davey, S. J., Rutten, M. G., & Cheung, B. 2007, EURASIP J. Adv. Signal Process, 2008, 1
- [3]NASA Planetary Defense Strategy & Action Plan Working Group 2023, Nasa Planetary Defense Strategy and Action Plan. https://go.nasa.gov/3U02mmt.
- [4]Shao, M., Nemati, B., Zhai, C., et al. 2014, ApJ, 782, 1
- [5]Zhai, C., Shao, M., Nemati, B., et al. 2014, ApJ, 792, 60
- [6]Zhai, C., Shao, M., Saini N., et al. 2024, PASP, 136:034401 (21pp), https://doi.org/10.1088/1538-3873/ad23fc
- [7]Brady, M. L. 1998, SISC, 27, 107
- [8]Nguyen, T., Woods, D. F., Ruprecht, J., & Birge, J. (2024), The Astronomical Journal, 167, 113, doi: 10.3847/1538-3881/ad20e0.DOI
- [9]C. Zhai, Q. Ye, M. Shao, et al (2020), Synthetic Tracking Using ZTF Deep Drilling Data Sets, Publications of the Astronomical Society of the Pacific, 132, 1012.DOI
- [10]Bellm, E. C., Kulkarni, S. R., Graham, M. J., et al, The Zwicky Transient Facility: System Overview, Performance, and First Results, PASP, 131:018002, 2019.