Multi-object tracking with representations of the symmetric group.
Risi Kondor, Andrew Howard, Tony Jebara · 2007
Abstract We present an efficient algorithm for approx-imately maintaining and updating a distribution over permutations matching tracks toreal world objects. The algorithm hinges on two insights from the theory of harmonicanalysis on noncommutative groups. The first is that most of the information in thedistribution over permutations is captured by certain "low frequency " Fourier components.The second is that Bayesian updates of these components can be efficiently realized by ex-tensions of Clausen's FFT for the symmetric group. 1 Introduction Multi-object trackers associate tracks r1, r2,..., rnwith real world objects o1, o2,..., on called targets.When the targets are well separated and good quality observations are available, following which trackcorresponds to which target is relatively easy. However, when two objects come very close, are occluded,or observations are not available, the association between tracks and objects becomes uncertain. This iswhat is referred to as the data association problem in multi-object tracking. Most tracking systems in practical use today are prob-abilistic, in the sense that at time