A Caratheodory-Fejer Approach to Robust Multiframe Tracking

Octavia I. Camps, Hwasup Lim, Cecilia Mazzaro, Mario Sznaier

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.

The proposed tracker identifies the target's dynamics to maintain a precise trajectory even through complex motion paths.

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.

Comparison of tracking performance across frames 150 to 85, demonstrating the system's ability to maintain tracking through occlusions that cause standard filters to fail.

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

Abstract

A requirement common to most dynamic vision applications is the ability to track objects in a sequence of frames. This problem has been extensively studied in the past few years, leading to several techniques, such as unscented particle filter based trackers, that exploit a combination of the (assumed) target dynamics, empirically learned noise distributions and past position observations. While successful in many scenarios, these trackers remain fragile to occlusion and model uncertainty in the target dynamics. As we show in this paper, these difficulties can be addressed by modeling the dynamics of the target as an unknown operator that satisfies certain interpolation conditions. Results from interpolation theory can then be used to find this operator by solving a convex optimization problem. As illustrated with several examples, combining this operator with Kalman and UPF techniques leads to both robustness improvement and computational complexity reduction.
BibTeX
@inproceedings{camps2003caratheodory,
  author = {Octavia I. Camps and Hwasup Lim and Cecilia Mazzaro and Mario Sznaier},
  title = {{A Caratheodory-Fejer Approach to Robust Multiframe Tracking}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2003},
  doi = {10.1109/iccv.2003.1238465},
}
Figure