PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiple Extended Target Tracking with Labelled Random Finite Sets

Michael Beard, Stephan Reuter, Karl Granström, Ba-Tuong Vo, Ba-Ngu Vo, Alexander Scheel

arXiv:1507.07392v1stat.CO

TL;DR

Extended targets generate multiple measurements, challenging point-target tracking models. The paper develops GGIW-based GLMB and cheaper LMB filters for labelled multi-target tracking, and reports improved estimation and tracking performance over GGIW-(C)PHD filters, including real-world pedestrian tracking.

  • Problem

    Standard point-target measurement models assume at most one measurement per target, whereas extended targets can generate multiple measurements at one time.

  • Method

    The paper models multiple extended targets as a GLMB random finite set with GGIW distributions and proposes a cheaper LMB variant.

  • Results

    The proposed algorithms outperform GGIW-(C)PHD filters, with GLMB more accurate and both methods performing well in a real-world pedestrian-tracking application.

  • Takeaways & Limitations

    Target labels enable continuous tracks while the filters estimate target number, kinematics, extents, and measurement rates.

Abstract

from arXiv · show

Targets that generate multiple measurements at a given instant in time are commonly known as extended targets. These present a challenge for many tracking algorithms, as they violate one of the key assumptions of the standard measurement model. In this paper, a new algorithm is proposed for tracking multiple extended targets in clutter, that is capable of estimating the number of targets, as well the trajectories of their states, comprising the kinematics, measurement rates and extents. The proposed technique is based on modelling the multi-target state as a generalised labelled multi-Bernoulli (GLMB) random finite set (RFS), within which the extended targets are modelled using gamma Gaussian inverse Wishart (GGIW) distributions. A cheaper variant of the algorithm is also proposed, based on the labelled multi-Bernoulli (LMB) filter. The proposed GLMB/LMB-based algorithms are compared with an extended target version of the cardinalised probability hypothesis density (CPHD) filter, and simulation results show that the (G)LMB has improved estimation and tracking performance.

I. INTRODUCTION

Extended-target tracking requires measurement models that allow multiple detections per target, unlike the standard point-target model. The paper develops GLMB- and LMB-based approaches using GGIW distributions to estimate labelled extended-target tracks and compares them with CPHD methods.

  • Motivation: The standard measurement model assumes each target produces at most one measurement, which is often unrealistic in practice.
  • Motivation: Higher-resolution sensors can produce multiple measurements per target, requiring an extended-target measurement model.
  • Extended-target modelling: Extended-target models represent both the number of measurements generated and their spatial distribution, which depend on sensor and target characteristics.
  • Extended-target modelling: GIW models estimate elliptical target extents online by combining Gaussian measurements with an inverse-Wishart covariance model.
  • Related filters: GGIW-CPHD extends the GIW approach by modelling each target’s Poisson measurement rate with a gamma distribution.
  • Related filters: (C)PHD filters reduce computational cost through approximations but do not directly produce target tracks and may suffer cardinality uncertainty or the spooky effect.
  • Paper contribution: The paper develops GGIW-GLMB and cheaper GGIW-LMB filters, adding adaptive birth modelling and evaluation on simulations and real lidar data.
  • Labelled RFS motivation: Labelled RFSs assign distinct labels to targets, allowing trajectories to be identified without post-processing, while standard GLMB does not accommodate extended-target likelihoods.

III. LABELLED RFS-BASED EXTENDED TARGET TRACKING

The paper proposes two labelled-RFS algorithms for tracking multiple extended targets: a GLMB filter and a cheaper LMB approximation.

  • III. LABELLED RFS-BASED EXTENDED TARGET TRACKING: The proposed filters track multiple extended targets in clutter using labelled random finite sets.
  • III. LABELLED RFS-BASED EXTENDED TARGET TRACKING: The GLMB formulation is paired with a cheaper LMB approximation for extended multi-target tracking.

A. Observation Model for Multiple Extended Targets

The observation model combines detection and misdetection, target-generated measurement sets, Poisson clutter, and associations between targets and measurement partitions. Exact likelihood evaluation can become computationally intractable, so infeasible partitions and insignificant mappings are reduced.

  • Measurement assumptions: The model allows each extended target either to be detected with probability pD(ξ,l) or misdetected with probability qD(ξ,l)=1−pD(ξ,l).
  • Measurement assumptions: When detected, each target generates a measurement set W through likelihood ˜g(W|ξ,l), independently of other targets.
  • Measurement assumptions: False observations form an independent Poisson RFS K with intensity κ(·), and the total measurement set is Z=Y∪K.
  • Likelihood construction: The likelihood organizes measurements into partitions and maps target labels to partition groups, with each positive association assigned to one label.
  • Computational tractability: Exact likelihood computation is generally intractable because measurement partitions and group-to-target mappings grow extremely large.
  • Computational tractability: The implementation reduces computation by removing infeasible partitions and using ranked assignment to eliminate insignificant mapping terms.

B. Extended Target State-space Model

The extended-target state combines measurement rate, kinematic state, and spatial extent, represented jointly by a gamma Gaussian inverse Wishart distribution.

  • The model defines positive reals, real vectors, and positive-definite or positive-semidefinite matrices as the relevant state spaces.
  • Each target state contains its average measurement rate, centroid kinematics, and extent covariance.
  • The rate, kinematics, and extent are modeled respectively by Gamma, Gaussian, and inverse-Wishart distributions.
  • The GGIW density is the product of these three component distributions, parameterized by ζ = (α, β, m, P, v, V).

1) Prediction :

Prediction propagates the GGIW target state through dynamic models, using closed-form kinematic propagation and approximations for measurement rate and extent.

  • Prediction: The predicted target density is obtained through the Chapman–Kolmogorov integral and approximated by another GGIW density.
  • Prediction: Under a linear Gaussian dynamic model, the kinematic component remains Gaussian with m = (F ⊗ I_d)m′ and P = FP′F^T + Q.
  • Prediction: The measurement-rate prediction uses a Gamma approximation that retains its expected value while increasing variance through an exponential forgetting factor.
  • Prediction: The forgetting factor is µ = 1/(1−1/w), with window length w > 1, and controls the rate-density variance adjustment.
  • Prediction: The extent prediction approximates the inverse-Wishart component by retaining its expected value while reducing density precision through its degrees of freedom.

2) Update:

The update incorporates a target-generated measurement subset into the predicted GGIW state and computes both posterior parameters and Bayes evidence.

  • Update: Each extended target is updated using different subsets of the measurements received on a scan.
  • Update: The update first computes the measurement-set mean and scale matrix, innovation terms, innovation matrix, and gain vector.
  • Update: The resulting posterior remains GGIW, with updated parameters ζ_W = (α_W, β_W, m_W, P_W, v_W, V_W).
  • Update: Bayes evidence for each single-target update is calculated from a product of two terms and contributes to posterior GLMB component weights.
  • Update: The rate component corresponds to a negative-binomial density, while the kinematics–extension component is proportional to a matrix-variate generalized beta type II density.

C. GLMB Filter for Extended Targets

The extended-target GLMB filter performs prediction and measurement update using GGIW target models, while the LMB variant reduces complexity by compressing the representation after updates.

  • GLMB Filter: The extended-target GLMB filter has prediction and update steps, with prediction following the standard birth/death GLMB model.
  • GLMB Filter: Its single-target transition kernel is the GGIW transition defined for the extended-target state model.
  • GLMB Filter: The extended-target update differs from the standard GLMB update because the extended-target measurement likelihood has a different form.
  • GLMB Filter: If the prior is GLMB, the extended multi-target likelihood produces a posterior that is also GLMB over the expanded label space L+ = L ∪ B.
  • GLMB Filter: The GLMB is therefore conjugate with respect to the extended multi-target measurement likelihood.
  • LMB Variant: The LMB filter reduces computation by replacing the full GLMB representation with an LMB representation after each measurement update.

1) LMB Prediction:

The LMB prediction propagates each target’s GGIW state and survival probability, then combines surviving targets with spontaneous births. This avoids the subset summation and component generation required by GLMB prediction.

  • Each target’s GGIW density is predicted forward, while its existence probability is multiplied by the survival probability.
  • The predicted LMB is formed by taking the union of predicted surviving tracks and birth tracks.
  • LMB prediction is cheaper than GLMB prediction because it avoids summing over subsets of the label set.
  • The LMB update converts the predicted LMB representation into a GLMB representation before posterior processing.
  • After updating, the posterior GLMB is approximated by an LMB with matching probability hypothesis density.
  • Each LMB track can become a mixture of GGIW densities representing different measurement-association histories, requiring pruning and merging to control growth.

IV. IMPLEMENTATION

The implementation uses pseudo-code functions and cost-based procedures for GLMB prediction and update. Computational tractability is achieved by pruning infeasible measurement partitions and retaining highly weighted assignments.

  • Implementation utilities: Implementation utilities include Poisson evaluation, randomized allocation, weight normalization, GGIW prediction, and GGIW update.
  • Representations: GLMB data structures store single-target densities, labels, component weights, and cardinality distributions, whereas LMB structures store densities, labels, and existence probabilities.
  • GLMB prediction: GLMB prediction constructs surviving-target components using a cost matrix, directed graph, and k-shortest paths, then multiplies them by the spontaneous-birth GLMB.
  • GLMB update: The GLMB update is difficult because its posterior sums over measurement partitions, whose number grows combinatorially with measurement-set size.
  • GLMB update: Distance-based clustering and expectation-maximization generate feasible measurement partitions, reducing the partition set before GGIW updates.
  • GLMB update: A cost matrix assigns measurement groups or misdetections to targets, and Murty’s algorithm retains n-best assignments as posterior GLMB components.

3) Track Extraction and Pruning:

Track estimates are extracted from the posterior GLMB using a MAP cardinality and highest-weight component, while adaptive births and clustered LMB updates reduce computational cost.

  • Track Extraction and Pruning: Track extraction first selects the maximum-a-posteriori cardinality, then chooses the highest-weight GLMB component with that cardinality.
  • Track Extraction and Pruning: Existing labels extend reported tracks with current estimates, while unseen labels initiate new reported tracks.
  • Adaptive Birth: The adaptive birth model allows new targets to appear anywhere in the state space instead of only near predetermined locations.
  • Adaptive Birth: Measurement clusters far from existing tracks are treated as likely new births, whereas nearby clusters are likely associated with existing tracks.
  • Prediction: LMB prediction propagates each target’s GGIW and survival probability, then unions surviving and birth densities.
  • Update: LMB updates cluster well-separated targets, convert each group to GLMB, update it, approximate it back to LMB, and merge the group posteriors.
  • Track Extraction and Pruning: The LMB computational saving depends on groups containing relatively few targets and therefore relatively few GLMB components.

V. SIMULATION RESULTS

Simulations compare GGIW-GLMB, GGIW-LMB, adaptive-birth LMB, and CPHD filters across target-tracking scenarios using cardinality error and modified OSPA metrics. GLMB and LMB generally achieve similar performance, while adaptive birth improves recovery after track loss and LMB is substantially cheaper computationally.

  • Evaluation setup: The evaluation compares GGIW-GLMB, GGIW-LMB, adaptive-birth GGIW-LMB, and GGIW-CPHD using cardinality error and modified OSPA distance.The modified OSPA metric incorporates measurement rates and target extent in addition to cardinality and state errors.
  • Scenario 1: Scenario 1 uses four targets over 200 time steps, detection probability pD = 0.8, and Poisson clutter with mean 30 measurements per time step.The scenario includes target appearances and disappearances and was evaluated over 1000 Monte Carlo runs.
  • Scenario 1: In scenario 1, GLMB and LMB have approximately equal performance, while CPHD matches their cardinality error but has larger mean OSPA.Adaptive-birth LMB converges more slowly because its birth density is initially unknown, eventually reaching the error of GLMB and static-birth LMB.
  • Computational cost: 3.95 ± 3.41s for GLMB, 0.19 ± 0.29s for LMB, and 2.20 ± 0.47s for CPHD are the mean execution times in scenario 1.Adaptive-birth LMB is even faster because it uses only clusters with more than four measurements as birth candidates.
  • Scenario 2: In scenario 2, GLMB slightly outperforms LMB and CPHD, while adaptive-birth LMB achieves lower OSPA distance and cardinality error than LMB after time 78.Adaptive birth can initiate a new track at the current location of a target previously lost when measurement clusters were close.
  • Scenario 3: In the spooky-effect scenario, CPHD increases the detected target’s weight when the other target is misdetected, whereas LMB leaves its existence probability unaffected.LMB also decreases existence probability more conservatively after missed detections than PHD and CPHD decrease their weights.

VI. EXPERIMENTAL RESULTS

The GGIW-LMB filter tracks pedestrians continuously, including when they approach closely, while estimating trajectories and time-varying extents from laser measurements. The broader proposed GGIW-(G)LMB approach supports labelled extended-target tracking and estimates target number, kinematics, extents, and measurement rates.

  • Pedestrian tracking: Figure 9 compares manually labelled ground-truth trajectories with estimated trajectories, two-sigma extent ellipses, and selected laser measurements.Dashed lines denote ground truth, solid lines estimates, and ellipses represent estimated target extents.
  • Pedestrian tracking: The GGIW-LMB filter tracks both pedestrians continuously, even when they are very close.The (G)LMB representation facilitates consistent association hypotheses and track maintenance over time.
  • Pedestrian tracking: Fluctuating measurements from legs, arms, and torso make precise centroid estimation difficult for both manual labelling and the tracker.These fluctuations explain most deviations between labelled ground truth and estimated trajectories.
  • Pedestrian tracking: Estimated pedestrian extents vary over time, with detailed scans revealing periodic adaptation linked to leg motion during strides.The changing ellipses reflect this time-varying extent behaviour.
  • Proposed methods: The proposed GGIW-GLMB and GGIW-LMB filters estimate target number, kinematics, extents, and measurement rates using labelled random finite sets and GGIW mixtures.Target labels enable continuous tracks, which GGIW-(C)PHD filters do not directly support.
  • Proposed methods: GGIW-GLMB is more accurate but more computationally demanding than GGIW-LMB, and the proposed algorithms outperform GGIW-(C)PHD filters in simulations.The performance advantage is especially evident when CPHD performance is degraded by the spooky effect.
Loading 1507.07392v1…