A fast and gridless ORKA algorithm for tracking moving and deforming objects

Florian Boßmann, Siwei Ma, Wen-Ze WuarXiv 2024 · DOI · arXiv

Tracking objects that move and change shape across multiple measurements—like a person running through a video or a seismic wave traveling through the Earth—is a computationally expensive challenge. In a new paper, researchers Florian Bossmann, Jianwei Ma, and Wenze Wu introduce fg-ORKA (fast and gridless Object Reconstruction using K-approximation), an iterative algorithm that smashes the "exponential wall" of previous methods while achieving sub-pixel accuracy.

TL;DR

The authors present an iterative multiresolution version of the ORKA algorithm that tracks deforming objects across measurements. By processing data from low to high resolution, the new method reduces computational complexity from exponential to linear relative to search range and enables "gridless" tracking that goes beyond the original data resolution.

What Problem Does This Paper Address?

The original ORKA algorithm was designed to find objects in "multiple measurement" problems. Imagine a stack of images where an object moves slightly in each frame. ORKA models this using a shift operator and a sparsity-promoting framework.

However, the original ORKA had two major "deal-breakers":

  1. The Exponential Wall: Its complexity scales exponentially with the search range ($C$). If an object moves fast (requiring a large $C$), the algorithm becomes unusable.
  2. Grid-Lock: It can only track movements in integer steps. If an object moves 0.5 pixels per frame, the algorithm struggles because it is bound to the discrete grid of the data.

Methods

The core innovation is an iterative multiresolution strategy. Instead of solving the whole problem at high resolution, fg-ORKA follows these steps:

  1. Downsampling: It creates a "pyramid" of data at different resolutions using a resampling pair ($R_\downarrow, R_\uparrow$).
  2. Coarse-to-Fine Tracking: It starts at the lowest resolution where the search range is tiny (and thus very fast). It finds a rough path for the object.
  3. Iterative Refinement: It moves to the next higher resolution, using the previous path as a starting point and only calculating a small "update" or correction.
  4. Artificial Upsampling: To become "gridless," the algorithm can artificially upsample the data beyond its original resolution, allowing it to estimate sub-pixel movements.

The authors explore three resampling strategies: Wavelet-based, Fourier-based, and a novel Optimal Resampling method that minimizes the approximation error of the orthogonal projection for a specific dataset.

Datasets

The algorithm was evaluated on three types of data:

  • Synthetic Random Data: Used for rigorous runtime and error analysis, specifically testing non-integer shifts and high-frequency noise.
  • Real Seismic Data: Post-stack geophysical data used to track subsurface wavefronts.
  • UCF Sports Action Data Set: Specifically, a soccer video used to test the algorithm's ability to track players, referees, and advertisement boards in a complex, moving-camera environment.

Key Insights and Ideas

  • Complexity Decoupling: By using a small, constant resampling factor (like $r=2$ or $r=3$), the complexity of each iteration becomes independent of the total movement speed. The algorithm scales linearly with the number of iterations rather than exponentially with the search range.
  • The "Balanced Ternary" Advantage: The authors found that a resampling rate of $r=3$ is mathematically the most efficient, but $r=2$ is more "stable" because it allows the algorithm to correct errors made in earlier, lower-resolution iterations.
  • Optimal vs. Low-Pass: While "Optimal Resampling" is best for high-frequency data (where details matter most), simple Fourier or Wavelet (low-pass) resampling is often superior for noisy data because it naturally filters out high-frequency interference during the coarse tracking phase.

Key Results

  • Massive Speedup: In benchmarks with a search range of $C=5$, fg-ORKA was orders of magnitude faster than the original ORKA. As $C$ increases, the original ORKA quickly becomes impossible to run, while fg-ORKA remains efficient.
  • Sub-Grid Accuracy: The upsampling strategy ($J$ iterations) successfully reduced tracking errors for non-integer shifts. Errors dropped significantly within the first 4–5 upsampling steps, approaching theoretical limits.
  • Seismic Superiority: On real geophysical data, fg-ORKA provided a much tighter fit to the seismic structure compared to the original version, which produced "blocky" results due to its grid dependency.

Limitations and Future Work

Despite the improvements, the authors note several areas for growth:

  • Object Size Variance: The algorithm struggles when a scene contains both very large objects (background) and very small objects (a soccer ball) simultaneously.
  • Overlapping Objects: The current model assumes objects are sparse and don't "stack" their intensities; in reality, objects in video often occlude one another.
  • Periodic Shifts: The current math assumes periodic boundaries (objects exiting left reappear on the right), which isn't true for standard video.
  • Future Directions: The authors suggest enforcing more restrictions on the object matrix $U$, such as requiring it to have a "compact or connected support," to improve reconstruction quality in noisy environments.

Summary updated

Abstract

Identifying objects in given data is a task frequently encountered in many applications. Finding vehicles or persons in video data, tracking seismic waves in geophysical exploration data, or predicting a storm front movement from meteorological measurements are only some of the possible applications. In many cases, the object of interest changes its form or position from one measurement to another. For example, vehicles in a video may change its position or angle to the camera in each frame. Seismic waves can change its arrival time, frequency, or intensity depending on the sensor position. Storm fronts can change its form and position over time. This complicates the identification and tracking as the algorithm needs to deal with the changing object over the given measurements. In a previous work, the authors presented a new algorithm to solve this problem - Object reconstruction using K-approximation (ORKA). The algorithm can solve the problem at hand but suffers from two disadvantages. On the one hand, the reconstructed object movement is bound to a grid that depends on the data resolution. On the other hand, the complexity of the algorithm increases exponentially with the resolution. We overcome both disadvantages by introducing an iterative strategy that uses a resampling method to create multiple resolutions of the data. In each iteration the resolution is increased to reconstruct more details of the object of interest. This way, we can even go beyond the original resolution by artificially upsampling the data. We give error bounds and a complexity analysis of the new method. Furthermore, we analyze its performance in several numerical experiments as well as on real data. We also give a brief introduction on the original ORKA algorithm. Knowledge of the previous work is thus not required.
BibTeX
@misc{bomann2024fast,
  author = {Florian Boßmann and Siwei Ma and Wen-Ze Wu},
  title = {{A fast and gridless ORKA algorithm for tracking moving and deforming objects}},
  year = {2024},
  eprint = {2402.02395},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.02395},
}
Figure