Adaptive Aggregation of Arbitrary Online Trackers with a Regret Bound

Heon Song, Daiki Suehiro, Seiichi UchidaWACV 2020

TL;DR

This paper introduces a novel online visual object tracking method that adaptively aggregates multiple existing trackers using a delayed-Hedge algorithm. This approach guarantees robust performance even in adversarial environments by theoretically bounding the "regret" (the performance difference from the best tracker), making it a strong contender for real-world applications.

What Problem Does This Paper Address?

Visual object tracking is crucial for many applications, but achieving robust and accurate tracking in real-time remains a significant challenge. Existing online trackers often struggle with unpredictable changes in target appearance, illumination, and occlusions, especially in adversarial scenarios where performance can degrade severely. While using multiple trackers and aggregating their predictions is a promising direction, simply averaging or switching between them doesn't guarantee optimal performance. The core problem is how to effectively combine diverse trackers to achieve performance close to the best possible tracker, even when the environment is unpredictable and the "best" tracker might change dynamically.

Methods

The proposed method, "delayed-Hedge online tracking," leverages the theoretical framework of adaptive expert aggregation (AEA). It treats each individual online tracker as an "expert." The key innovation is the use of a delayed-Hedge algorithm for dynamically weighting these experts.

Here's how it works:

  • Expert Aggregation: At each frame, the method combines the predictions of N arbitrary online trackers (experts) using a weighted sum.
  • Delayed Feedback: Unlike standard AEA, this method uses "delayed feedback." This means the true target location (or a very accurate estimate) is only provided at specific "anchor frames." This feedback is crucial for evaluating expert performance.
  • Anchor Frame Determination: Anchor frames are identified online by detecting when a target object is recognized with high confidence, often using a combination of expert predictions and feature matching.
  • Weight Updates: Expert weights are updated only at anchor frames. The update rule is based on the performance (loss) of each expert in the interval between the current and the previous anchor frame. This "delayed" update is the core of the algorithm's theoretical guarantee.
  • Regret Bound: The theoretical foundation of the delayed-Hedge algorithm guarantees a bounded "regret." This means the performance of the aggregated tracker will not be significantly worse than the best individual tracker over the entire sequence, even in adversarial conditions.

Datasets

The paper evaluates its method on several standard benchmark datasets for visual object tracking:

  • OTB2013
  • OTB2015
  • VOT2018
  • TColor128

The authors note that they used default parameters for all methods and experts, aiming to demonstrate performance "in the wild" rather than optimizing for specific datasets.

Key Insights and Ideas

  • Theoretical Guarantees for Practical Problems: The paper successfully bridges the gap between theoretical machine learning (AEA) and a practical computer vision problem (object tracking). The "regret bound" provides a strong theoretical assurance of performance, which is rare in real-world tracking.
  • No "Almighty" Tracker: The initial analysis (Figure 1) clearly shows that no single tracker performs best across all scenarios, motivating the need for adaptive aggregation.
  • Delayed Feedback is Sufficient: The delayed nature of feedback doesn't hinder performance; in fact, it's a key to the algorithm's robustness and ability to handle unpredictable environments.
  • Arbitrary Trackers are Welcome: The method is designed to work with any set of online trackers, meaning it can easily incorporate new, state-of-the-art trackers as they emerge, continuously improving its performance.
  • Robustness in Adversarial Scenarios: The experimental results demonstrate that the proposed method consistently performs well, even when the "best" expert changes frequently, highlighting its adaptability.

Key Results

  • State-of-the-Art Performance: The proposed method achieves competitive, often state-of-the-art, performance across multiple benchmark datasets (Table 1, Figure 3).
  • Near-Best Performance: The method consistently achieves performance close to the best performing expert, as predicted by its theoretical regret bound.
  • Robustness: The performance histogram (Figure 5) shows that the proposed method achieves high ranks more consistently than other methods, indicating robustness across different sequences.
  • Real-time Capability: With a set of real-time experts, the proposed method can operate in near real-time (around 12 FPS in experiments, depending on the slowest expert). The overhead for anchor frame detection and feedback calculation is minimal.
  • Anchor Frame Ratio: Figure 4 shows that the method effectively utilizes anchor frames, with a high ratio (often > 0.8) across sequences, indicating reliable target detection when needed.

Limitations and Future Work

  • Dependence on Anchor Frame Quality: The performance of the delayed-feedback mechanism relies on the ability to accurately detect anchor frames. If anchor frames are not reliably identified, the feedback quality suffers, potentially impacting performance.
  • Offline Tracker for Feedback: The method uses an offline tracker to generate accurate feedback between anchor frames. While this is computationally efficient for short intervals, its reliance on an external tracker could be a limitation.
  • Future Work: The authors suggest extending the framework to multiple-object tracking scenarios, which would be a natural progression given the aggregation approach. They also implicitly suggest that using faster real-time experts would further improve the overall speed.

Summary updated

BibTeX
@inproceedings{song2020adaptive,
  author = {Heon Song and Daiki Suehiro and Seiichi Uchida},
  title = {{Adaptive Aggregation of Arbitrary Online Trackers with a Regret Bound}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2020},
}
Figure