Visual Tracking via Dynamic Graph Learning

Chenglong Li, Liang Lin, Wangmeng Zuo, Jin Tang, Ming-Hsuan YangIEEE TPAMI 2019 · DOI · OpenReview

TL;DR

This paper introduces a novel visual tracking method that represents the target object as a dynamic graph of image patches. By jointly learning the graph structure, edge weights (appearance compatibility), and node weights (foreground likelihood), the method effectively suppresses background clutter and improves tracking robustness. This dynamic graph representation is then integrated into a structured SVM for accurate object localization.

What Problem Does This Paper Address?

Visual tracking, the task of following an object across video frames, is notoriously challenging due to factors like background clutter, occlusion, and illumination changes. Many existing "tracking-by-detection" methods rely on classifiers that can be easily corrupted by background information, leading to "model drift" where the tracker loses the target. While some methods attempt to mitigate this by assigning weights to image patches, they often use static graph structures or rely on low-level features that are not robust to noise and clutter. This paper aims to address the problem of robustly representing the target object in the presence of significant background clutter by learning a dynamic, appearance-aware graph representation.

Methods

The core of this work is a dynamic graph learning approach for object representation. Here's a breakdown:

  • Patch-based Graph Representation: The target object's bounding box is divided into non-overlapping image patches. These patches serve as nodes in a graph.
  • Node and Edge Weights:
    • Node weights indicate the likelihood of a patch belonging to the foreground (target object).
  • Edge weights capture the appearance compatibility between neighboring patches.
  • Joint Optimization: Crucially, the paper proposes to jointly learn the graph structure, edge weights, and node weights. This is achieved by formulating an optimization problem that considers:
  • Sparse representation (SR) of patches (using $l_1$-norm) to capture higher-order relationships and improve discriminative power.
  • Low-rank representation (LRR) (implicitly through the graph structure) to capture global data structure and robustness to noise.
  • Graph Laplacian term to encourage spatial smoothness and relationships between patches.
  • Smoothness and fitting constraints for node weights to ensure consistency with initial estimates and suppress outliers.
  • Alternating Direction Method of Multipliers (ADMM): An efficient ADMM algorithm is developed to solve the complex optimization problem, breaking it down into smaller, manageable subproblems that can be solved efficiently.
  • Structured SVM for Tracking: The learned patch weights are then used to construct a robust feature representation for the target object. This representation is fed into a structured Support Vector Machine (SVM), similar to the Struck tracker, to predict the object's location in each frame.

Datasets

The proposed method was evaluated on several standard benchmark datasets:

  • OTB100: A widely used dataset for evaluating visual tracking algorithms, containing 100 challenging image sequences.
  • Temple Color Dataset: Another dataset for evaluating tracking performance.
  • NUS-PRO Dataset: A dataset with 365 challenging image sequences, annotated with occlusion levels.
  • VOT2014 Challenge Dataset: Used for evaluating robustness, particularly in scenarios with deformations and noisy bounding boxes.

Key Insights and Ideas

  • Dynamic Graph Learning is Key: The most significant insight is that learning the graph structure and weights dynamically for each frame, rather than using a fixed structure, is crucial for adapting to changing object appearance and background conditions.
  • Joint Optimization for Robustness: By jointly optimizing graph structure, node weights, and edge weights, the method can effectively suppress background clutter and learn a more accurate representation of the target object. This is a departure from methods that optimize these components separately.
  • Patch Weights as a Clutter Suppressor: The learned patch weights are shown to be highly effective in down-weighting background patches, leading to improved tracking accuracy, especially in cluttered scenes.
  • ADMM for Efficient Optimization: The development of an efficient ADMM algorithm is critical for making the complex graph learning process computationally feasible for real-time tracking.

Key Results

The proposed Weighted Patch-based Graph (WPG) tracker demonstrated strong performance across multiple benchmarks:

  • OTB100: WPG outperformed several state-of-the-art trackers, achieving 9.1% higher precision than SOWP and 5.5% higher success rate than MUSTer. It showed particular strength in handling illumination variation, background clutter, deformation, and partial occlusion.
  • Temple Color Dataset: WPG achieved competitive results, outperforming several trackers like DGT, Staple, and SRDCF.
  • NUS-PRO Dataset: The tracker performed favorably against 20 conventional trackers, showing robustness across various attributes like background clutter, deformation, and partial occlusion.
  • VOT2014 Challenge Dataset: WPG achieved the best robustness (ROB) scores, indicating its ability to handle tracking failures and noisy initializations better than other methods.
  • Efficiency: The algorithm could track at approximately 5 frames per second, with optimization converging within 50 iterations.

Limitations and Future Work

  • Feature Limitations: The authors acknowledge that the performance on sequences with low illumination (DL) and fast background changes (FBC) could be improved by integrating more features beyond color and gradient histograms.
  • Scale Handling: While the method shows improvements in scale variation, it is noted that the SOWP method's weight computation scheme is limited in handling scale variations. The proposed WPG method also has limitations in this regard, which could be further improved.
  • Future Work: The authors suggest several promising directions:
  • Learning dynamic spatio-temporal graphs to capture more complex relationships.
  • Developing more robust motion or search models to address fast object or background motions.
  • Exploring hierarchical appearance models to replace hand-crafted features.

Summary updated

Abstract

Existing visual tracking methods usually localize a target object with a bounding box, in which the performance of the foreground object trackers or detectors is often affected by the inclusion of background clutter. To handle this problem, we learn a patch-based graph representation for visual tracking. The tracked object is modeled by with a graph by taking a set of non-overlapping image patches as nodes, in which the weight of each node indicates how likely it belongs to the foreground and edges are weighted for indicating the appearance compatibility of two neighboring nodes. This graph is dynamically learned and applied in object tracking and model updating. During the tracking process, the proposed algorithm performs three main steps in each frame. First, the graph is initialized by assigning binary weights of some image patches to indicate the object and background patches according to the predicted bounding box. Second, the graph is optimized to refine the patch weights by using a novel alternating direction method of multipliers. Third, the object feature representation is updated by imposing the weights of patches on the extracted image features. The object location is predicted by maximizing the classification score in the structured support vector machine. Extensive experiments show that the proposed tracking algorithm performs well against the state-of-the-art methods on large-scale benchmark datasets.
BibTeX
@article{li2019visual,
  author = {Chenglong Li and Liang Lin and Wangmeng Zuo and Jin Tang and Ming-Hsuan Yang},
  title = {{Visual Tracking via Dynamic Graph Learning}},
  journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  year = {2019},
  doi = {10.1109/tpami.2018.2864965},
}
Figure