Abstract
Multi-target tracking (MTT) is reformulated as a non-cooperative game played on a graph. By treating individual person detections as players competing to adopt consistent identity strategies, this approach leverages game-theoretic Nash equilibria to solve the data association problem. The method demonstrates high performance with minimal labeled data, effectively propagating identities through unlabeled video frames.
Introduction
Multi-target tracking (MTT) involves correctly linking person detections across multiple video frames into continuous trajectories. This data association task is often complicated by occlusions, lighting variations, and the high cost of manual labeling. This paper addresses these challenges by framing tracking as a Semi-Supervised Learning (SSL) problem, where labels from a few initial frames are propagated through the rest of the sequence.
Methodology
The proposed framework utilizes a Graph Transduction Game (GTG) for tracking.
Feature Extraction and Representation
Detections are initially obtained using a HOG detector. To ensure robustness against small shifts and lighting changes, each detection patch is represented by a covariance matrix of features, including position, HSV color values, and image gradients.
The Graph Transduction Game
The tracking problem is mapped onto a graph $G=(V, E)$, where each node represents a detection patch. Edges denote similarity between patches, calculated via a specialized Riemannian distance metric for covariance matrices.
In this game-theoretic setting:
- Players: Each unlabeled detection node.
- Strategies: Potential target IDs (e.g., Person 1, Person 2).
- Payoffs: Players receive higher payoffs for choosing labels consistent with their neighbors.
The system employs imitation dynamics from evolutionary game theory to evolve labels until a Nash equilibrium is reached—a state of global consistency where no player can improve their payoff by unilaterally changing their identity label.
Experimental Results
The GTG approach was evaluated on the THIS, CAVIAR, and 3DPes datasets. It achieved high F-measures: 0.99 on THIS, 0.96 on CAVIAR, and 0.92 on 3DPes. The method proves highly efficient, with performance saturating at high levels of precision and recall with as few as five labeled frames. It consistently outperforms state-of-the-art transductive methods like TLT, particularly in precision.
Conclusion
By recasting multi-target tracking as a game-theoretic equilibrium problem, this method achieves robust data association with minimal supervision. Future work will focus on adapting the framework for online, real-time tracking and handling dynamic target counts.
Summary updated