Efficient Implementations of Extended Object PMBM Filters with Blocked Gibbs Sampling

Technical Summary: Efficient Implementations of Extended Object PMBM Filters with Blocked Gibbs Sampling

1. Problem Statement

Modern high-resolution sensors (e.g., Lidar, automotive radar) often violate the "point object" assumption by generating multiple measurements per object in a single scan. This necessitates Extended Object Tracking (EOT), where the object state includes both kinematics and an extent description (shape/size).

The primary challenge in multiple EOT is data association: determining which measurements belong to which objects and which are clutter. Traditional methods like Clustering-and-Assignment (C&A) struggle when objects are closely spaced, while existing sampling-based or belief propagation (BP) methods often face high computational costs or performance degradation due to premature hypothesis merging. The paper seeks to implement the Poisson Multi-Bernoulli Mixture (PMBM) filter—which provides a closed-form Bayesian solution for EOT—in a way that is both computationally efficient and robust to data association ambiguity.

2. Methodology

The authors propose a sampling-based approach to approximate the PMBM posterior by targeting the joint posterior of potential objects, previous global hypotheses, and current measurement associations.

• Augmented State Space: To make the PMBM density tractable for sampling, the authors formulate it on an augmented space using auxiliary "track index" variables. This allows the density to be decomposed into a Poisson component (for undetected objects) and a Multi-Bernoulli Mixture (MBM) component (for detected objects).
• Blocked Gibbs Sampling: Instead of sampling all variables simultaneously, the authors derive a factorized joint posterior that allows for blocked Gibbs sampling. The variables are sampled in three sequential blocks:
  1. Previous Global Hypotheses: Sampling the history of associations.
  2. Measurement Associations: Sampling which measurement belongs to which Bernoulli component (enabling parallel sampling).
  3. Detected Objects: Sampling the actual states of the objects.
• Collapsed Gibbs Sampling: To improve efficiency, the authors introduce a "collapsed" variant where the Bernoulli existence variables are marginalized out. While this introduces a variational approximation, it significantly improves the mixing of the Markov chain, particularly for the initiation of new tracks.
• Mathematical Model: The implementation utilizes the Gamma Gaussian Inverse-Wishart (GGIW) model, which provides a conjugate prior for the Poisson measurement rate, kinematic state, and object extent.
• Track-Oriented Implementation: To avoid redundant computations, the authors use a tree-structured local hypothesis representation and hash tables to ensure each updated local hypothesis is computed only once per iteration.

3. Key Contributions

• Factorized Joint Posterior: Derivation of a representation that explicitly captures data association uncertainty while remaining computationally scalable.
• Two Sampling Variants: Development of both Blocked Gibbs (for exactness) and Collapsed Gibbs (for efficiency and robustness to initialization).
• Improved Initialization: A clustering-based initialization strategy (using DBSCAN) that helps the sampler converge faster by providing high-quality starting points.
• Weight-Based Approximation: Unlike previous methods that rely on frequency-based approximations (which require discarding "burn-in" samples), this method uses a weight-based approach, allowing for more efficient use of all generated samples.

4. Results

The proposed methods were compared against a Particle Belief Propagation (Particle BP) implementation of the PMB filter using the GOSPA metric (which accounts for state error, missed detections, and false detections).

• Performance vs. Runtime: The PMBM-based Gibbs samplers achieved comparable or superior estimation performance to Particle BP while requiring substantially less runtime. For example, PMBM-C-Gibbs2 with only 20 iterations outperformed Particle BP with 5,000 particles while being roughly an order of magnitude faster.
• Error Decomposition: The PMBM filters generally produced fewer false detections than the Particle BP method. While Particle BP was slightly better at reducing missed detections (due to its specific birth model), the PMBM approach offered a more stable trade-off.
• Robustness: The collapsed Gibbs sampler showed high robustness to initialization, performing well even when starting from simple, non-optimized states.

5. Significance

This work provides a highly efficient framework for real-time multi-object extended object tracking. By leveraging the mathematical elegance of the PMBM filter and the flexibility of Gibbs sampling, the authors bridge the gap between theoretically optimal Bayesian filtering and the practical requirements of high-speed, high-resolution sensor processing in fields like autonomous driving and defense. The ability to handle closely-spaced objects without the heavy computational burden of traditional particle filters makes this a significant advancement in the field of Random Finite Set (RFS) based tracking.