Efficient approximations in multi-target tracking

Posted on April 11, 2020

Background

The core challenge in multi-target tracking is data association: The tracking method must account for the different possibilities for how the given measurements may be due to different targets or false alarms (clutter). Optimal solutions to this problem need to consider an exponential number of combinations, which clearly is not practically feasible for anything more complex than toy problems. Different solution strategies can be pursued depending on the computational resources available.

A popular compromise is found in the Joint Probabilistic Data Association (JPDA) method, which keeps a single Gaussian distribution for each target, and marginalizes over all association hypotheses during each estimation cycle to maintain this representation. For a single-target tracking problem, this reduces to one association hypothesis for each measurement, plus one hypotheses for the misdetection case. The single-target version of the JPDA is known as the Probabilistic Data Association Filter (PDAF). The JPDA/PDAF can easily be generalized to also calculate probabilities of target existence, known as the (Joint) Integrated Data Association, or (J)IPDA.

A more dramatic simplification is achieved by the Probability Hypothesis Density (PHD) filter. In this approach, the posterior distribution of the set of targets is approximated as a Poisson process. This approximation makes it possible to circumvent the enumeration of association hypotheses entirely. The computational complexity is then equal to the product of number of terms in the representation of the prior Poisson process, with the number of measurements. For the tracking of a single target with high detection probability, which is the most common tracking problem one encounters, the PHD filter has troublesome misdetection problems. However, for problems such as tracking a group of targets moving together, or tracking targets with very low existence probabilities, it exhibits more sensible behaviour.

An approach that aims to combine the best of the JIPDA and the PHD filter is the Linear Multi-target IPDA (LMIPDA). The key idea of the LMIPDA is to update each track independently by treating the measurements from other targets as clutter. This also gives a linear complexity in the number of measurements. The LMIPDA has never received the same attention as the PHD filter, possibly because the theory of random finite sets came to dominate the field of multi-target tracking in the last decade. The PHD filter was the original random finite set filter, while the LMIPDA was not derived from random finite set foundations.

It is possible to express the optimal solution to multi-target tracking under standard assumptions on a structured form known as the Poisson Multi-Bernoulli Mixture (PMBM) filter. The PMBM filter consists of two components: Its Poisson-component is similar to a PHD filter, while its MBM component can be approximated by a JIPDA. This raises the question of whether the MBM component also could be approximated by an LMIPDA.

Scope

In this project you will investigate the potential of LMIPDA as a lightweight alternative to JIPDA. The aim is both to understand the relationship between LMIPDA and the methods mentioned above, and to quantify the gains and losses that one could expect by replacing a PHD filter or a JIPDA with an LMIPDA. The work is intended to mainly rely on simulations, but real data can also be used.

Proposed Tasks for the 5th year project

  1. Make yourself familiar with the standard model of multi-target tracking and popular methods such as JIPDA, PHD filter, CPHD filter and PMBM filter.
  2. Study the PMBM-based derivation of the JIPDA, and do the required derivations to replace the JIPDA with LMIPDA.
  3. Design simulation scenarios and benchmark measures to compare tracking methods.
  4. Compare basic LMIPDA, PMBM-based LMIPDA, PHD filter, basic JIPDA, PMBM-based JIPDA and CPHD filter.
  5. Write report.

Proposed Tasks for the master thesis

The project work aims to be extended into a master thesis for the spring of 2021. Several directions are possible depending on the interest of the student.

  • Development of an LMIPDA method tailored to be used in a drone-based tracking system.
  • Can strategies such as those used in an LMIPDA also be used in a more complex JIPDA or PMBM filter? One project that possibly could be addressed in this manner is clustering and cluster-splitting of nearby tracks.
  • Integration of multiple models using the IMM framework.
  • Integration of wake models.
  • Integration of visibility probabilities.
  • Benchmarking on several real world data sets.

Contact

For more information, contact supervisors Edmund F. Brekke or Lars-Christian Tokle

References