Introduction
Classical tracking algorithms, such as Kalman Filters or Unscented Particle Filters (UPF), typically rely on rigid, pre-defined motion models (e.g., constant velocity or constant acceleration). While effective in controlled environments, these models often fail when target dynamics change abruptly or during severe occlusions. When the internal model of a tracker diverges from the actual physical movement of the target, the system loses its "lock," a problem exacerbated by cluttered backgrounds.
This paper introduces a robust framework that treats target dynamics not as a fixed equation, but as an unknown mathematical operator. By leveraging interpolation theory and convex optimization, the proposed method can learn motion patterns on the fly and provide guaranteed error bounds.
Methodology: From State Estimation to System Identification
The core innovation of this approach is shifting the tracking problem from state estimation to real-time system identification.
1. Operator Modeling
The target's dynamics are modeled as an operator $F$ that maps a sequence of past positions to the current position. This operator is decomposed into two distinct components:
- Parametric Part: A combination of known motion "modes" (potentially learned from prior training data).
- Non-parametric Part: A residual component that accounts for unmodeled dynamics, bounded by a "worst-case" gain ($K$).
2. Optimization via Linear Matrix Inequalities (LMIs)
Tracking is reframed as finding an operator that satisfies observed data points—essentially an interpolation problem. Using the Caratheodory–Fejer Lemma, the authors demonstrate that such an operator exists if and only if a specific set of Linear Matrix Inequalities (LMIs) is feasible. This allows the use of efficient convex optimization solvers to determine the target's path.
3. Model Validation and Error Bounds
Unlike probabilistic methods that provide a "most likely" position, this framework offers a "sanity check." If the LMI solver finds the problem infeasible, it serves as a mathematical signal that the target has changed behavior or that noise levels have exceeded the model's assumptions. Furthermore, the method calculates a "diameter of information," providing a guaranteed spatial region where the target must reside given the noise bounds.
Experimental Results
The approach was evaluated on challenging video sequences involving complex motion and total occlusion.
Occlusion Survival
A primary test involved tracking a person walking behind a tree. In this scenario, standard Kalman and UPF trackers typically lose the target by frame 95 as their internal models fail to account for the hidden movement. By identifying the specific dynamics of the individual before the occlusion, the Caratheodory–Fejer approach accurately propagates the position through the period of invisibility.
Comparative Performance
In head-to-head comparisons with the Mean Shift tracker, the identification-based (Id-based) method showed significantly lower error rates. For instance, in a child centroid sequence, the Mean Shift error reached ~64.8 pixels, while the proposed method maintained an error of ~26.0 pixels—well within the target's physical width. Notably, this performance was achieved with lower computational complexity than Unscented Particle Filters.
Conclusion and Future Work
The Caratheodory–Fejer approach provides a mathematically rigorous alternative to stochastic tracking. By treating motion as a system to be identified, it achieves superior robustness during occlusions and provides built-in model validation.
However, the authors note that if both the dynamics and the driving forces (inputs) are unknown, the problem becomes non-convex and NP-hard. Future research directions include exploring mixed $H_2/H_\infty$ filters to better balance average-case performance with worst-case robustness requirements.
Summary updated