Multi-object tracking with representations of the symmetric group

Risi Kondor, Andrew G. Howard, Tony JebaraAISTATS 2007 · OpenReview

Abstract

We present an efficient algorithm for approximately maintaining and updating a distribution over permutations matching tracks to real world objects. The algorithm hinges on two insights from the theory of harmonic analysis on noncommutative groups. The first is that most of the information in the distribution over permutations is captured by certain “low frequency” Fourier components. The second is that Bayesian updates of these components can be efficiently realized by extensions of Clausen’s FFT for the symmetric group.

Introduction

In multi-object tracking, the "data association" problem is the central challenge: determining which physical object corresponds to which track. While simple when objects are isolated, the problem becomes computationally explosive when objects cross paths or become occluded. For $n$ objects, there are $n!$ possible assignments. For $n=15$, this exceeds 1.3 trillion, making it impossible to store or update the full distribution in real-time. Existing solutions often resort to brittle single-best-guess estimates or particle filters that struggle in high-dimensional spaces. This paper proposes a principled approach to maintain a "blurry" but accurate probability distribution over all $n!$ assignments by leveraging harmonic analysis.

Methodology

The core innovation lies in treating the probability distribution over permutations as a function on the symmetric group ($S_n$).

Fourier Analysis on $S_n$

Just as a complex signal can be decomposed into sine waves, a distribution over permutations can be represented by Fourier components (irreducible representations). By "band-limiting" the distribution—keeping only the first few low-frequency components—the authors compress the $n!$ space into a manageable subspace. This is analogous to JPEG compression for permutations, discarding high-frequency details that are non-essential for tracking.

Efficient Computation

To maintain efficiency, the authors adapt Clausen’s Fast Fourier Transform (FFT) for the symmetric group. This allows for Bayesian updates and noise modeling (diffusion) directly in the Fourier domain. The "swapping" of identities over time is modeled as a diffusion process on a Cayley graph, which simplifies to efficient multiplication in the Fourier domain.

The Bratteli diagram for the symmetric group, illustrating the hierarchical relationship between irreducible representations.

The algorithm utilizes the Bratteli diagram (Figure 1), a structure showing how group representations relate to one another, to pass information efficiently between different levels of the tracking hierarchy.

Experimental Setup

The algorithm was evaluated using real-world radar data of aircraft near JFK International Airport. The dataset includes challenging scenarios such as aircraft crossing paths over the Hudson River or simultaneous approaches to parallel runways. Tests were conducted for $n = 6, 10, \text{ and } 15$ aircraft, with artificial uncertainty introduced via simulated identity swaps to test filter robustness.

Results

The spectral method demonstrates significant scalability and accuracy. It handles up to $n=15$ objects in real-time (~59ms per update) and remains viable for up to $n=30$.

Tracking error rates as a function of the number of Fourier components used, demonstrating improved accuracy with higher-order representations.

On the JFK dataset, the spectral method outperformed the state-of-the-art information-form filter. For $n=10$, the spectral method achieved an error rate of 0.215, compared to 0.2885 for the baseline. As shown in Figure 2, performance consistently improves as more Fourier components (irreducibles) are included, confirming that higher-order representations capture valuable information.

Discussion and Future Work

While effective for "vague" or uncertain distributions, the method faces challenges with "highly peaked" distributions (high certainty), where Fourier-based "ringing" artifacts can occur. Additionally, the current framework assumes a fixed number of objects. Future work will focus on extending the model to handle dynamic scenes where objects enter and leave the environment.

Summary updated

Abstract

We present an efficient algorithm for approximately maintaining and updating a distribution over permutations matching tracks to real world objects. The algorithm hinges on two insights from the theory of harmonic analysis on noncommutative groups. The first is that most of the information in the distribution over permutations is captured by certain “low frequency” Fourier components. The second is that Bayesian updates of these components can be efficiently realized by extensions of Clausen’s FFT for the symmetric group.
BibTeX
@inproceedings{kondor2007multi,
  author = {Risi Kondor and Andrew G. Howard and Tony Jebara},
  title = {{Multi-object tracking with representations of the symmetric group}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2007},
  url = {https://openreview.net/forum?id=IV2paTb526},
}
Figure