Hypothesised filter for independent stochastic populations

Jérémie Houssineau, Daniel E. ClarkarXiv 2014 · arXiv

Abstract: A new filter for independent stochastic populations is studied and detailed, based on recent works introducing the concept of distinguishability in point processes. This filter propagates a set of hypotheses corresponding to individuals in a population, using a version of Bayes' theorem for multi-object systems. Due to the inherent complexity of the general multi-object data association problem, approximations are required to make the filter tractable. These approximations are justified and detailed along with explanations for the modelling choices. The efficiency of this new approach is then demonstrated through a comparison against one of the most popular multi-object filters.

Introduction

Multi-target tracking (MTT) involves estimating the number and states of multiple objects from noisy, incomplete sensor data. The primary challenge in MTT is data association: correctly linking observations to specific targets amidst missed detections and clutter. Traditional methods like Multiple Hypothesis Tracking (MHT) maintain distinct track identities but suffer from exponential computational complexity. Conversely, point-process methods like the Probability Hypothesis Density (PHD) filter are computationally efficient but treat targets as an indistinguishable set, making track maintenance difficult. The Hypothesised filter for Independent Stochastic Populations (HISP) bridges this gap, providing track-level detail with linear computational complexity.

The HISP Framework

The HISP filter is built on the foundation of partially-distinguishable multi-target systems. It distinguishes between targets that have never been detected (treated as an indistinguishable group) and those that have been previously detected (treated as distinct individuals). This hybrid approach optimizes computational resources by focusing on known tracks while maintaining a unified Bayesian framework for target appearance and disappearance.

State transitions in the partially-distinguishable framework.

The model utilizes an extended state space that includes "empty" states to represent targets that may exist but are not currently tracked. This allows the filter to compute an a posteriori probability of detection failure, enabling it to "remember" targets through several missed detections more effectively than standard point-process methods.

Computational Efficiency and Algorithm 1

To avoid the combinatorial explosion typical of data association, HISP employs sparsity approximations. It assumes that in sparse scenarios, the likelihood of multiple targets competing for the same observation—or one target being linked to multiple observations—is negligible. This allows the multi-target marginal likelihood to be factorized, enabling efficient updates.

Algorithm 1 for efficient computation of association weights.

As shown in Algorithm 1, the update step can be computed in $O(N \times M)$ time, where $N$ is the number of tracks and $M$ is the number of observations. This linear scaling makes HISP significantly more practical for real-time applications with many targets compared to traditional MHT or non-approximated distinguishable filters.

Evaluation and Results

The filter was evaluated using simulated 2-D scenarios with five targets and varying Signal-to-Noise Ratios. Performance was measured using the Optimal Sub-Pattern Assignment (OSPA) metric against industry standards: the PHD, Cardinalised PHD (CPHD), and Labelled Multi-Bernoulli (LMB) filters.

Key findings include:

  • Superior Accuracy: HISP consistently outperformed benchmarks, particularly in low-detection environments ($P_d = 0.5$).
  • Robust Track Maintenance: The filter effectively maintained tracks through target crossings and high clutter (false alarms).
  • Scalability: The paper confirms that the HISP filter maintains its theoretical linear complexity, offering a "best of both worlds" solution for large-scale tracking problems.

Conclusion and Future Work

The HISP filter offers a robust solution for multi-target tracking by combining the mathematical rigor of point processes with the track-oriented nature of classical methods. While the filter is sensitive to parameters like survival probability ($p_\pi$), its ability to handle data association efficiently marks a significant advancement. Future research may explore extending the HISP framework to non-linear target dynamics through Sequential Monte Carlo (particle filter) methods.

Summary updated

Abstract

A new filter for independent stochastic populations is studied and detailed, based on recent works introducing the concept of distinguishability in point processes. This filter propagates a set of hypotheses corresponding to individuals in a population, using a version of Bayes' theorem for multi-object systems. Due to the inherent complexity of the general multi-object data association problem, approximations are required to make the filter tractable. These approximations are justified and detailed along with explanations for the modelling choices. The efficiency of this new approach is then demonstrated through a comparison against one of the most popular multi-object filters.
BibTeX
@misc{houssineau2014hypothesised,
  author = {Jérémie Houssineau and Daniel E. Clark},
  title = {{Hypothesised filter for independent stochastic populations}},
  year = {2014},
  eprint = {1404.7408},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1404.7408},
}
Figure