A Graph Transduction Game for Multi-target Tracking

Tewodros Mulugeta Dagnew, Dalia Coppi, Marcello Pelillo, Rita CucchiaraarXiv 2018 · arXiv

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.

Feature extraction process leading to the covariance matrix representation.

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.
Overview of the tracking pipeline, from input frames to the Graph Transduction Game results.

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

Abstract

Semi-supervised learning is a popular class of techniques to learn from labeled and unlabeled data. The paper proposes an application of a recently proposed approach of graph transduction that exploits game theoretic notions to the problem of multiple people tracking. Within the proposed framework, targets are considered as players of a multi-player non-cooperative game. The equilibria of the game is considered as a consistent labeling solution and thus an estimation of the target association in the sequence of frames. Patches of persons are extracted from the video frames using a HOG based detector and their similarity is modeled using distances among their covariance matrices. The solution we propose achieves satisfactory results on video surveillance datasets. The experiments show the robustness of the method even with a heavy unbalance between the number of labeled and unlabeled input patches.
BibTeX
@misc{dagnew2018graph,
  author = {Tewodros Mulugeta Dagnew and Dalia Coppi and Marcello Pelillo and Rita Cucchiara},
  title = {{A Graph Transduction Game for Multi-target Tracking}},
  year = {2018},
  eprint = {1806.07227},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.07227},
}
Figure