PaperlayerView exact revision on arXiv

Source-linked AI summary

Marginal multi-Bernoulli filters: RFS derivation of MHT, JIPDA and association-based MeMBer

Jason L. Williams

arXiv:1203.2995v6eess.SYcs.CV

TL;DR

Existing tractable RFS trackers avoid explicit data association, but the paper shows that association is implicit in the full Bayes RFS posterior. It derives association approximations yielding TOMB/P and MOMB/P, which show promising or improved performance in challenging tracking environments.

  • Problem

    RFS tracking methods avoid explicit data association for tractability, motivating the question of how association is represented in the full Bayes filter and approximated without losing useful tracking performance.

  • Method

    The paper derives a conjugate full Bayes RFS filter with MHT-like association structure, then approximates marginal association distributions to obtain TOMB/P and MOMB/P.

  • Results

    The proposed methods show promising performance in challenging scenarios; MOMB/P is reported as robust to coalescence and improves upon CPHD and CB-MeMBer, especially at lower detection probabilities.

  • Takeaways & Limitations

    The RFS framework can recover association-based structures and connect tractable approximations to methods related to JIPDA and MeMBer.

Abstract

from arXiv · show

Recent developments in random finite sets (RFSs) have yielded a variety of tracking methods that avoid data association. This paper derives a form of the full Bayes RFS filter and observes that data association is implicitly present, in a data structure similar to MHT. Subsequently, algorithms are obtained by approximating the distribution of associations. Two algorithms result: one nearly identical to JIPDA, and another related to the MeMBer filter. Both improve performance in challenging environments.

I. INTRODUCTION

RFS tracking methods gain tractability by approximating distributions to avoid explicit data association, while this paper shows that association nevertheless emerges in the full Bayes filter and supports related MHT, JIPDA, and MeMBer formulations.

  • RFS tracking context: RFS methods such as PHD, CPHD, and MeMBer use approximations that avoid explicitly reasoning over measurement-to-target correspondence.PHD uses a PPP posterior, while CPHD also calculates cardinality and MeMBer approximates association under assumptions about false alarms.
  • Association-based methods: JPDA and MHT explicitly formulate association hypotheses, with JPDA marginalising association variables and MHT selecting the most likely association hypothesis.JIPDA and JITS additionally estimate target existence.
  • Paper contributions: The paper derives a full Bayes RFS filter whose posterior structure resembles TOMHT and contains a summation over MHT-like association hypotheses.The derivation establishes a conjugate prior form preserved by prediction and update.
  • Paper contributions: Approximating the association distribution produces TOMB/P, which is very similar to JITS and JIPDA, including a Bayesian model of target birth.The RFS derivation differs through its treatment of target birth, with only minor changes needed to recover related JITS/JIPDA algorithms.
  • Paper contributions: MOMB/P groups hypotheses associated with each measurement into one Bernoulli component while weighting them with marginal association probabilities, following the philosophy of MeMBer.Both proposed filters can use a tractable approximation of marginal measurement-to-track association probabilities.
  • Evaluation: Experiments in challenging scenarios report improved performance over CPHD and CB-MeMBer, particularly at lower detection probabilities, for a similar computational load.The paper addresses finite-set tracking with unknown target number and unordered measurements whose correspondence is unknown.

A. Dynamics model and prediction step

The model combines PPP births and false alarms with independent Markovian target survival, motion, and point-measurement processes; prediction and update are derived using p.g.fl operations.

  • Dynamics assumptions: Targets arrive through a nonhomogeneous PPP, depart through iid Markovian survival processes, and move according to iid Markovian transition densities.Births are independent of existing targets, with birth intensity λb(x), survival probability Ps(x), and transition PDF ft|t−1(x|x′).
  • Dynamics assumptions: The multiple-target dynamics are represented as the union of a birth PPP and independent Bernoulli processes describing each existing target.The Bernoulli process includes survival and single-target motion through the transition p.g.fl.
  • Prediction derivation: The prediction p.g.fl. combines the birth intensity with the transformed prior distribution using a PPP exponential factor.The displayed prediction form is exp{⟨λb, h−1⟩} multiplied by the prior p.g.fl. evaluated at 1−Ps+Psph.
  • Measurement assumptions: Each target produces at most one measurement, each measurement comes from at most one target, and false alarms form an independent PPP.Target-derived measurements are conditionally independent with single-target likelihood f(z|x).
  • Update derivation: The Bayes update is derived directly in p.g.fl. form using the measurement likelihood and a product rule for functional derivatives.Disjoint-set decompositions support differentiation of products of component p.g.fl.s.

III. RANDOM SET FILTER DERIVATION

The full RFS posterior is represented by unknown targets in a PPP and detected-track hypotheses in an MBM, with data association emerging implicitly through measurement decompositions.

  • Association hypotheses: Association arises implicitly from summing over disjoint decompositions of the measurement set assigned to prior tracks.The decomposition appears through the product rule used in the p.g.fl. update.
  • Association hypotheses: A global association history hypothesis partitions all measurements into subsets assigned to particular potential targets.Each subset contains at most one measurement from each time under the measurement assumptions.
  • Track representation: A single-target hypothesis is a subset of measurements associated with one potential target and includes its measurement history, weight, and hypothesis-conditioned Bernoulli distribution.Tracks group hypotheses sharing the same hypothesised first-detection measurement.
  • Track representation: The RFS representation is more compact than conventional MHT because Bernoulli hypotheses encode existence uncertainty rather than a unique target cardinality.A global hypothesis specifies a distribution over target cardinality, and tracks include a non-existence hypothesis.
  • Track representation: A track is a collection of single-target hypotheses representing alternative measurement sequences for the target first detected in a particular measurement.The structure resembles TOMHT and creates a new track for each received measurement, while sharing hypotheses across global hypotheses.
  • Posterior structure: The posterior distribution consists of two independent components: a PPP for unknown targets and an MBM for detected-target tracks.The derivation assumes a distributional form maintained through prediction and update.

A. Prediction step

Prediction preserves the PPP–multi-Bernoulli structure, while measurement update branches existing tracks over missed detections and new measurements and creates new tracks for each measurement.

  • Prediction step: The predicted PPP follows the standard PHD prediction, while existing multi-Bernoulli tracks are predicted independently in a MeMBer-equivalent manner.The distinction is that new-target births are represented by a PPP rather than a multi-Bernoulli birth model.
  • Measurement update: The updated distribution retains the same structural form, with the PPP intensity update matching a PHD update with no measurements.The multi-Bernoulli update is represented through track and hypothesis expansions.
  • Filter structure: The resulting branching structure is similar to TOMHT, with non-existence hypotheses continued without branching.Gating, clustering, and mixture reduction can reduce the computational burden in practical implementations.
  • Measurement update: Each continuing track receives hypotheses for missed detection and for updating every prior hypothesis with each new measurement.Before practical pruning, the hypothesis count becomes hi_t|t−1(1+mt) for a continuing track.
  • New tracks: A new track is created for every measurement and contains hypotheses for association with an existing track or for a false alarm or first detection.The latter hypothesis uses existence probability to represent the relative likelihood of a false alarm versus a newly detected target.

C. Initialisation

The Poisson component supplies prior information about undetected targets, while marginal association approximations produce tractable multi-Bernoulli tracking updates. These updates retain target existence, track continuity, and relationships to JITS/JIPDA while introducing practical approximations for association and hypothesis management.

  • Initialisation: The Poisson prior represents the expected number and spatial distribution of targets before measurements are available.It is initialized with expected target count λu_0 and prior state density f_0(x).
  • Initialisation: 55%?
  • Marginal association approximation: TOMB/P yields a multi-Bernoulli distribution and preserves the first moment of the approximated distribution.
  • Marginal association approximation: TOMB/P approximates the global association-history distribution by independent per-track marginal association distributions.This is the same approximation used in JPDA, expressed within the RFS framework.
  • Marginal association approximation: The resulting Bernoulli track state uses an existence probability and a weighted mixture of hypothesis-conditioned position distributions.
  • Relation to JITS/JIPDA: Within the RFS framework, TOMB/P is equivalent to a variant of JITS/JIPDA with a parametric clutter model and Bayesian target-birth modelling.The derivation includes unknown-target effects in association probabilities and connects track initiation to a stationary unknown-target intensity.
  • Practical approximations: Practical implementations additionally prune low-existence tracks, reduce mixture components, and approximate marginal association distributions.

B. Measurement oriented marginal MeMBer-Poisson filter

MOMB/P reparameterizes association hypotheses by measurement rather than track, producing a MeMBer-like approximation that groups hypotheses sharing each measurement. Compared with TOMB/P, this measurement-oriented structure can better represent the joint posterior when targets are close.

  • Measurement-oriented association: MOMB/P indexes global association hypotheses by the track associated with each measurement, rather than by the measurement associated with each track.This alternative parameterization is equivalent under the stated assumptions, but supports independence across measurement-association variables.
  • Two-target example: In the two-target example, the exact posterior is formed by symmetrising products of the alternative measurement-conditioned updates, accounting for switched target identities.The approximation shown for MOMB/P is described as closer to the true distribution than the TOMB/P approximation.
  • Marginalisation: MOMB/P uses marginal association probabilities for measurement-to-track events, while the corresponding TOMB/P marginals are track-to-measurement probabilities.Both marginalisations approximate the association distribution by enforcing independence, but on different variables.
  • Model extensions: The derivation extends measurement-oriented hypotheses to new targets, false alarms, missed detections, and non-existence through alternative association encodings.The mapping β assigns hypotheses according to whether a measurement updates an existing track, creates a new target, or represents a missed detection.
  • MeMBer relation: The MOMB/P approximation collects all single-target hypotheses updated with a given measurement into one posterior Bernoulli component.Its weights arise by interpreting terms in the association sum as a distribution over association events, unlike the p.g.fl.-based MeMBer approximation.
  • Track construction: TOMB/P forms posterior tracks around prior tracks and new measurements, whereas MOMB/P forms one track per measurement and separate missed-detection tracks for prior targets.The MOMB/P Bernoulli components collect hypotheses from all prior tracks that use a given measurement.

C. Approximating marginal association distributions

The proposed filters require marginal association probabilities whose exact computation is closely related to a #P-complete matrix permanent. The paper motivates loopy belief propagation as an accurate, tractable approximation and evaluates the methods in difficult close-proximity tracking scenarios.

  • Computational challenge: Computing the marginal association probabilities needed by TOMB and MOMB is closely related to the #P-complete calculation of a matrix permanent.This computational barrier is identified as the greatest obstacle to practical application of the algorithms.
  • Practical limitations: Practical implementations still require pruning unlikely tracks, reducing mixture components, and approximating the marginal association distributions.These additional approximations are separate from the core derivation's association-distribution approximation.
  • Approximation methods: Loopy belief propagation is proposed as an accurate and tractable approximation for calculating marginal association probabilities.The derivation itself is not tied to LBP; exact EHM and MCMCDA are also identified as possible alternatives.
  • Relationship to MHT: The full Bayes RFS derivation does not justify replacing the sum over global association hypotheses with maximisation, as in MHT.The derivation retains a total-probability expansion over unobserved association hypotheses rather than selecting only the most likely one.
  • Experimental setting: The experiments use challenging scenarios with 6, 10, or 20 closely proximate targets, including cases with targets indistinguishable at the simulation midpoint.Detection probabilities range from 0.3 to 0.98, and expected false alarms range from 10 to 80 per scan.

A. Tracking performance

The experiments evaluate tracking accuracy and computation under close-target, low-detection, cluttered, and cardinality-changing conditions. MOMB/P is robust to coalescence and generally outperforms CPHD and CB-MeMBer, while complexity depends on scenario structure.

  • Evaluation setup: Mean OSPA is evaluated over 200 Monte Carlo trials with p = 1 and c = 20, combining position and velocity errors over time.The scenarios involve n ∈{6, 10, 20} targets, including close-proximity cases.
  • Coalescence: Coalescence produces alias peaks in track marginals, causing multiple estimates to be placed on the same target.The effect is visible for JITS, TOMB/P, and LMITS when targets become closely spaced.
  • Coalescence: MOMB/P, CPHD, and CB-MeMBer are robust to coalescence because measurement-oriented updates spatially concentrate Bernoulli components and suppress alias peaks.MOMB/P’s association approximation yields a multi-Bernoulli density closer to the full RFS density in these cases.
  • Cardinality changes: MOMB/P, CPHD, and CB-MeMBer respond faster to cardinality changes, but MOMB/P outperforms the latter two, especially at lower P_d.CPHD and CB-MeMBer suffer from inaccurate local cardinality despite accurate global cardinality, whereas TOMB/P and MOMB/P do not show the same difficulty.
  • Track management: At P_d = 0.3, TOMB/P, MOMB/P, and CB-MeMBer maintain around 200 tracks on average, while JITS and LMITS maintain 20–30.The smaller JITS problem explains its apparent lower complexity and lower performance in this setting.

APPENDIX A PROOF OF PREDICTION STEP

The appendix proves that the prediction and update operations preserve the proposed RFS distributional structure. Its key algebraic step exposes a sum over global association hypotheses.

  • Prediction structure: The prediction proof substitutes the p.g.fl into the Bayes RFS prediction formula and separates the result into PPP and multi-Bernoulli components.The PPP intensity follows a standard PHD prediction, while each track hypothesis is predicted separately.
  • Prediction structure: The predicted PPP component retains its form, with intensity calculated through the PHD prediction step.The proof explicitly identifies the first component as a PPP.
  • Prediction structure: The remaining component is a mixture of multi-Bernoulli distributions, whose prediction uses the MeMBer prediction equation.Target birth is represented separately in the Poisson component under the stated survival/death setting.
  • Update structure: The Bayes update likewise factors into a PPP component and an updated remaining component assembled from Bernoulli updates.The proof treats missed detections, existing-track detections, new tracks without measurements, and updates of new tracks separately.
  • Association hypotheses: Linearity of differentiation lets the update be computed separately for each prior association hypothesis before recombining the resulting terms.The resulting weights decompose according to the association structure.
  • Association hypotheses: Lemma 5 rewrites the product rule as a sum whose terms correspond to global association hypotheses.Measurements assigned to false alarms or unknown targets are separated from measurements assigned to pre-existing tracks.

APPENDIX C IMPLEMENTATION PSEUDO-CODE

The implementation uses Gaussian representations for unknown-target intensity and Bernoulli tracks, with prediction, update, LBP association, and either TOMB/P or MOMB/P track formation.

  • State representation: The simplified implementation approximates each track with a Gaussian and the unknown-target PPP intensity with a Gaussian mixture.The experimental implementation used a Gaussian mixture version involving hypothesis management.
  • Model assumptions: The model assumes uniform detection and survival probabilities, linear-Gaussian measurements and dynamics, and Gaussian-mixture target birth intensity.These assumptions define the implementation model.
  • Processing pipeline: The algorithm executes prediction, update, LBP marginal-association calculation, and either TOMB/P or MOMB/P track formation.Low-existence tracks and low-weight PPP components are eliminated, although those steps are omitted from the pseudocode presentation.
  • Estimate extraction: TOMB/P outputs means of tracks above an existence threshold, whereas MOMB/P estimates cardinality and outputs means from the highest-weight components.The two procedures therefore use different estimate-extraction rules.
  • Hypothesis management: After updating and reforming tracks, each pre-existing track has m_t + 1 hypotheses, while new tracks retain one explicitly stored hypothesis.Hypothesis-conditioned existence probabilities are maintained for pre-existing tracks.

1 Predict existing tracks

The prediction procedure begins by setting the number of predicted existing tracks from the previous track count.

  • Initialization: The pseudocode initializes n_t|t−1 to n_t−1|t−1 before iterating over the existing tracks.This establishes the predicted track set for the subsequent prediction operations.

8 Predict existing PPP intensity

The prediction/update pipeline processes existing tracks, missed detections, and measurements, while creating new tracks from measurements through PPP updates.

  • The prediction algorithm is followed by component updates for existing tracks and PPP updates using measurements.
  • Missed detection hypotheses are explicitly created for existing tracks.
  • The pipeline creates a new track for each measurement by updating the PPP with that measurement.
  • LBP produces approximate marginal association probabilities for subsequent track formation.

3 Run LBP iteration

The LBP iteration approximates marginal association probabilities, which are then used to reform updated hypotheses into single-hypothesis tracks with existence probabilities.

  • LBP iteratively updates messages between tracks and measurements to approximate marginal association probabilities.
  • The track-reformation procedures take component-updated tracks and marginal probability estimates as input.
  • Each re-formed track comprises an existence probability.
  • TOMB/P: TOMB/P forms re-formed single-hypothesis tracks from the updated components.
  • MOMB/P: MOMB/P forms re-formed single-hypothesis tracks from the updated components.
Loading 1203.2995v6…