PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiple target tracking based on sets of trajectories

Ángel F. García-Fernández, Lennart Svensson, Mark R. Morelande

arXiv:1605.08163v6cs.CVcs.SYeess.SY

TL;DR

Current multitarget filtering densities may not retain the associations needed to answer trajectory questions, while a full Bayesian MTT solution requires the trajectory distribution given measurements. The paper models sets of trajectories with multitrajectory densities and derives a conjugate family; it concludes that this framework supports trajectory questions and related MTT tasks.

  • Problem

    Multitarget filtering densities do not always retain the associations needed for trajectory-related questions, while a full Bayesian MTT solution requires the trajectory distribution given measurements.

    Source: §I · p. 1, B. Motivation for sets of trajectories · p. 4

  • Method

    The paper applies the random finite set framework to sets of trajectories and derives a conjugate multitrajectory density for filtering.

    Source: §VI · pp. 14–15

  • Results

    The authors conclude that multitrajectory densities contain the information needed to answer trajectory-related questions and that the derived conjugate density gives rise to the trajectory MBM01 filter.

    Source: §VI · p. 15

  • Takeaways & Limitations

    Sets of trajectories with the random finite set framework support trajectory-related questions, physically interpretable metrics, estimator design, and algorithm evaluation.

    Source: §VI · p. 15

Abstract

from arXiv · show

We propose a solution of the multiple target tracking (MTT) problem based on sets of trajectories and the random finite set framework. A full Bayesian approach to MTT should characterise the distribution of the trajectories given the measurements, as it contains all information about the trajectories. We attain this by considering multi-object density functions in which objects are trajectories. For the standard tracking models, we also describe a conjugate family of multitrajectory density functions.

I. INTRODUCTION

The paper makes sets of trajectories the state variable for MTT, aiming to retain the full posterior information needed for trajectory questions without arbitrary labels. It defines trajectories by their start time, length, and consecutive target states, then represents a system as a set of them.

I. INTRODUCTION

  • The paper focuses on targets without a unique identification, where no single target movement or measurement effect identifies the target.This is described as the common case in radar applications.Source: §I · p. 1
  • Target-set filtering densities support current-time target questions but cannot answer trajectory questions or soundly establish trajectories.The paper therefore develops theoretical foundations for full Bayesian MTT, rather than efficient practical algorithms.Source: §I · pp. 1–2
  • A multitrajectory density retains all trajectory information given measurements, while using significantly fewer terms than the joint density over sequences of labelled sets.The paper also presents filtering equations and a conjugate family for computing this density.Source: §I · p. 2

A. State variables and notation

  • A trajectory is specified by its start time, length, and sequence of target states at consecutive time steps.A set of trajectories represents the tracking system across time.Source: A. State variables and notation · pp. 2–3
  • Unlike a sequence of labelled target sets, a set of trajectories represents the same physical tracks uniquely, without arbitrary labels.Labels assigned to target states can be permuted while representing the same physical reality.Source: A. State variables and notation · p. 3

B. Motivation for sets of trajectories

Sequences of labelled multitarget filtering densities can lose the associations needed to recover trajectories, especially when labels and targets are ambiguously associated. Joint densities preserve that information but are cumbersome and retain arbitrary labels; sets of trajectories offer a compact alternative.

B. Motivation for sets of trajectories

  • Labelled multitarget filtering or smoothing densities can lose the associations needed to link target states, particularly for IID-cluster births or targets that approach and separate.The Poisson RFS is identified as a commonly used birth model within the IID-cluster family.Source: B. Motivation for sets of trajectories · p. 4
  • A joint density over labelled sets preserves trajectory information, but arbitrary labels prevent physically meaningful metrics and make its explicit expressions cumbersome.Different labelings can describe identical trajectories while yielding nonzero distance under metrics on labelled-set sequences.Source: B. Motivation for sets of trajectories · pp. 4–5
  • Sets of trajectories avoid arbitrary labels, support trajectory-related questions, and allow metrics with physical interpretation.Such metrics can evaluate algorithms whose estimates are represented as unlabelled trajectories.Source: B. Motivation for sets of trajectories · p. 5
  • For the five-step example, the multitrajectory density preserves full trajectory information in 2 terms, versus 64 for the joint density over labelled sets.The labelled-set expression grows exponentially with sequence length in the example.Source: B. Motivation for sets of trajectories · p. 5

C. Probability and integration

The paper adapts finite-set statistics to sets of trajectories by treating trajectories as the single objects. Its integrals provide probabilities for trajectory-set events, including cardinality and region-based questions.

C. Probability and integration

  • Finite-set statistics can be applied to trajectory sets by replacing target objects and single-target integrals with trajectories and single-trajectory integrals.The paper gives the corresponding single-trajectory and set integrals.Source: C. Probability and integration · p. 5
  • The set integral of a multitrajectory density is one, and its cardinality distribution gives the probability of the number of trajectories that have existed.Source: C. Probability and integration · pp. 5–6
  • Set integrals calculate the probability that a random set of trajectories belongs to a specified region.The construction maps sequences of trajectories to sets of trajectories.Source: C. Probability and integration · pp. 5–6
  • In the example density, the probability of one trajectory is 0.9 and the probability of two trajectories is 0.1.Integrating over a region can also give the probability of a trajectory starting in one region and moving to another.Source: C. Probability and integration · p. 6

III. FILTERING RECURSION FOR RFSS OF TRAJECTORIES

The recursion treats the evolving set of trajectories as the state, with births, survival, motion, and death determining its dynamics. Prediction and measurement updates then yield the multitrajectory filtering density from prior trajectory densities and current measurements.

A. Dynamic model

  • Each target survives and moves or dies, while independently generated births join the next-time-step set; the resulting trajectory set includes all trajectories ever present.The model leaves the number of trajectories and new births unknown.Source: A. Dynamic model · p. 6

B. Filtering with a general measurement model

  • Prediction propagates the previous filtering density through the trajectory transition, and the measurement update combines the predicted density with the likelihood to obtain the current filtering density.The predicted density represents trajectories through time k given measurements only through k−1; trajectories cannot extend beyond k in either density.Source: B. Filtering with a general… · pp. 6–7
  • The prediction accounts for surviving, dying, and newly born trajectories by combining prior trajectory density, motion and survival terms, death probabilities, and the birth density.Figure 4 illustrates 20 possible time-6 sets given the time-5 set, with no births and survival probability one.Source: A. Dynamic model · p. 6, B. Filtering with a general… · p. 7, Figure 4 · p. 7

C. Filtering with the standard measurement model

For the standard point-target measurement and specified birth models, the multitrajectory filtering density belongs to a conjugate MBM01 family. The paper gives recursive prediction and update steps and discusses their implementation and extensions.

C. Filtering with the standard measurement model

  • Under the standard point-target measurement and specified birth models, predicted and filtering densities are MBM01 densities, making MBM01 conjugate for the standard likelihood.MBM01 is a multi-Bernoulli mixture whose existence probabilities are either 0 or 1.Source: C. Filtering with the standard… · pp. 7–8
  • Trajectory hypotheses encode birth component, start time, duration, and data associations, with labels corresponding to birth component and start time omitted from the trajectory state.The association vector records clutter or a measurement assignment at each corresponding time step.Source: C. Filtering with the standard… · p. 8
  • The predicted density has the same form as the filtering density, with each trajectory’s data-association vector one entry shorter because the current scan is not yet processed.The recursion initializes with an empty hypothesis of weight one and alternates prediction and update.Source: C. Filtering with the standard… · p. 8
  • Prediction weights combine the parent hypothesis weight with birth, survival, and death probabilities, while trajectories that ended earlier retain their densities.Newborn trajectories are drawn from the birth model; its component weights specify the probabilities of different birth-component subsets.Source: C. Filtering with the standard… · pp. 8–9
  • The update weights each present-trajectory hypothesis by its data-association probabilities, while trajectories no longer present keep their densities unchanged.The standard measurement model includes target detections or misses and Poisson clutter.Source: C. Filtering with the standard… · pp. 7, 9
  • For linear-Gaussian models with constant detection and survival probabilities and Gaussian birth densities, the recursion has closed-form implementations; nonlinear or non-Gaussian models require single-trajectory density approximations.Both cases still require practical management of the growing number of hypotheses and trajectory dimensions.Source: C. Filtering with the standard… · p. 9
  • Conjugacy also holds for trajectory PMBMs and MBMs; the PMBM Poisson component represents non-detected trajectories efficiently.Source: C. Filtering with the standard… · p. 9

D. Practical considerations

The paper establishes foundations for trajectory-set tracking rather than efficient practical algorithms, and notes that recursive implementations need approximations or other hypothesis-management strategies as their state grows.

D. Practical considerations

  • The trajectory MBM01 recursion cannot run indefinitely without approximation because state dimension grows linearly and the number of hypotheses grows super-exponentially.Source: D. Practical considerations · p. 9
  • Gating or pruning hypotheses can manage their growth; pruning approximates selected MBM01 weights as zero and renormalizes the remaining weights.The paper also mentions joint multi-scan data-association pruning.Source: D. Practical considerations · pp. 9–10
  • Sliding time windows can limit the trajectory history updated or retained, based on the stated practical assumption that current measurements significantly affect only recent trajectory states.Source: D. Practical considerations · p. 10
  • Sequential track builders do not use all available information and may produce unreasonable trajectories; sequential and non-sequential estimation are both possible formulations.Source: D. Practical considerations · p. 10

IV. RELATION WITH OTHER MTT MODELS

The paper relates trajectory-based filtering to labelled trajectory models, MHT, and conventional target-set filtering. Marginalising trajectory densities recovers the standard target-set filtering result and links the labelled trajectory MBM01 filter to δ-GLMB.

A. Relation with sets of labelled trajectories

  • The labelled-trajectory representation maps to labelled target sets at each time, and formula (23) provides a closed-form single-trajectory-density expression for linear/Gaussian systems.The authors state that such a formula had not been proposed for sequences of labelled sets.Source: A. Relation with sets of labelled… · p. 10

B. Relation with MHT algorithms

  • For the standard measurement model, trajectory MBM01 computes multiple association hypotheses with densities over trajectories, making it an MHT-type algorithm derived using sets of trajectories and FISST.The approach represents quantities of interest as a random set of trajectories, supporting Bayesian trajectory posteriors and metric-based estimation errors.Source: B. Relation with MHT algorithms · p. 11

C. Relation with sets of targets

  • Theorem 11 obtains the target-set filtering density at a particular time by marginalising the multitrajectory density.The paper states that applying this marginalisation after prediction and update yields the same target-set filtering density as the usual RFS framework.Source: C. Relation with sets of targets · p. 11
  • Marginalising trajectory densities recovers the standard RFS target-set filtering density, and the labelled trajectory MBM01 filter extends δ-GLMB to labelled trajectories.The equivalence holds for the stated standard dynamic and measurement models and birth model (25).Source: C. Relation with sets of targets · p. 11, Figure 5 · p. 11

V. ILLUSTRATIVE EXAMPLES

The simulations illustrate trajectory-density inference and the trajectory MBM01 filter in one- and two-dimensional scenarios. In two dimensions, the trajectory filter outperforms the δ-GLMB filter on GOSPA and OSPA, while increasing the smoothing window improves localization and past-state knowledge.

A. One dimensional scenario

  • The most likely global hypothesis has three trajectories and accurately represents the trajectories from which measurements were generated; five lower-ranked hypotheses differ in trajectory births, measurement associations, or splitting.Source: A. One dimensional scenario · p. 12
  • The δ-GLMB estimate switches tracks for targets born at the same time, whereas the highest-weight trajectory hypothesis does not.The paper attributes the δ-GLMB switching to the IID cluster birth process and says it can be avoided using the joint density over labelled-set sequences or a set of trajectories as state variable.Source: A. One dimensional scenario · p. 12
  • With higher clutter and measurement noise, none of the three most likely hypotheses contains both trajectories born at time 2, and the third includes a switch.One trajectory was not detected at time 2.Source: A. One dimensional scenario · p. 13

B. Two dimensional scenario

  • The trajectory conjugate prior estimates the ten true trajectories without false trajectories, although some trajectories are detected after a delay.Increasing L improves knowledge of past states; L = 1 performs no trajectory smoothing and requires more storage than δ-GLMB to retain past states for all trajectory hypotheses, including dead ones.Source: B. Two dimensional scenario · pp. 13–14
  • 143.2 s (1-scan/δ-GLMB filter), 144.4 s (2-scan), 145.7 s (5-scan), and 159.7 s (10-scan) were the running times for 150 steps.The paper reports similar computational burden for L between 1 and 5, with a small additional cost for improving knowledge of past trajectory states.Source: B. Two dimensional scenario · p. 14
  • For every L, the trajectory MBM01 filter has lower GOSPA and OSPA errors than the δ-GLMB filter, and increasing L lowers both errors.Increasing L lowers localization error for properly detected targets but does not change missed- or false-target costs; missed-target and localization costs are the main GOSPA sources.Source: B. Two dimensional scenario · p. 14
  • The trajectory MBM01 filter has lower track-switch error than the δ-GLMB filter under the trajectory metric.That metric penalizes localization errors, missed and false targets, and track switches.Source: B. Two dimensional scenario · p. 14

VI. CONCLUSIONS

The conclusions present sets of trajectories under Mahler’s RFS framework as a way to characterize MTT without a priori target identification. The paper also derives a trajectory MBM01 filter, relates the approach to other models, and identifies directions for future work.

VI. CONCLUSIONS

  • The set-of-trajectories RFS approach characterizes MTT without a priori target identification and supports trajectory questions, physically interpretable metrics, estimator design, and algorithm evaluation.The conclusions state that these tools enable the tasks of MTT.Source: §VI · pp. 14–15
  • The derived conjugate multitrajectory density gives rise to the trajectory MBM01 filter, with relations described to labelled and unlabelled RFS models and MHT.The paper illustrates the approach through simulations.Source: §VI · p. 15
  • Future work includes specifying measure-theoretic aspects, developing computationally efficient algorithms, and including target spawning.Source: §VI · p. 15

APPENDIX A

The appendix establishes the trajectory space properties and integral conventions used for applying FISST, then relates multiobject densities to Janossy densities and develops trajectory transition-density calculations.

APPENDIX A

  • FISST applies to sets of trajectories because their space up to time k′ is locally compact, Hausdorff, and second-countable.The appendix also describes single-trajectory and set integrals for this space.Source: Appendix A · p. 15

A. The space T(k′) is LCHS

  • The trajectory space T(k′) is locally compact and Hausdorff because it is a finite disjoint union of spaces {t} × D_i with those properties.Source: A. The space T(k′) is LCHS · p. 15
  • A countable base for T(k′) establishes that the trajectory space is second-countable.The construction uses countable bases for the Euclidean subspaces and the disjoint-union topology.Source: A. The space T(k′) is LCHS · p. 15

B. Integrals

  • The single-trajectory integral over the disjoint-union space is the sum of integrals over its subspaces, and the corresponding set integral follows the FISST convention.The text notes that measure-theoretic integrals for functions on LCHS sets are beyond the paper’s scope.Source: B. Integrals · p. 15

APPENDIX B; A. Target case

  • A multiobject density packages its family of Janossy densities, and the nth Janossy density gives the probability density for exactly n points in distinct infinitesimal regions.Source: A. Target case · p. 15

B. Trajectory case

  • For trajectories, the corresponding Janossy probability concerns exactly n distinct trajectories with specified start times and lengths in infinitesimal regions.Source: B. Trajectory case · p. 16

APPENDIX C

  • Without births, trajectories that died before the previous step remain unchanged, while surviving trajectories either die or extend through the single-target transition model.The appendix partitions trajectories into dead and alive sets when calculating the transition-density integral.Source: Appendix C · p. 16

APPENDIX D

Appendix D proves that the birth model and the predicted and filtering multitrajectory densities have MBM01 form. Its prediction proof organizes trajectory hypotheses by survival, death, and birth status.

APPENDIX D

  • Appendix D proves that the birth model is MBM01 and establishes Lemmas 9 and 10.Source: Appendix D · p. 17

A. Birth model

  • The birth model is a mixture of multi-Bernoulli densities whose component existence probabilities are 0 or 1, with mixture weights wB(L).The appendix also establishes that the multitrajectory filtering and predicted densities are MBM01.Source: A. Birth model · p. 17

B. Prediction

  • The prediction proof partitions trajectories into surviving, dying, dead, and newborn groups to identify the predicted global-hypothesis weights and single-trajectory densities.Terms inconsistent with those trajectory categories are zero.Source: B. Prediction · p. 17

C. Update

The update proof derives the updated density and its weights for alive and dead trajectory hypotheses. Appendix E gives single-trajectory density computation details for the linear/Gaussian model with constant survival and detection probabilities.

C. Update

  • The update derivation substitutes the preceding equation and equation (10) into equation (9) to obtain the updated density and weights.The updated densities correspond to alive and dead trajectory hypotheses.Source: C. Update · p. 18

APPENDIX E

  • Appendix E details single-trajectory density computations for the trajectory MBM01 filter under a linear/Gaussian model with constant pS and pD.The labelled trajectory MBM01 recursion is analogous.Source: Appendix E · p. 18

A. Prediction

The prediction and update derivations compute quantities from earlier trajectory densities and restrict the measurement-update function to hypotheses containing trajectories that exist through the current time step. The appendices relate trajectory transitions to target transitions and focus on the prediction relation.

A. Prediction

  • The prediction derivation computes quantities in Lemma 9 from the previous single-trajectory densities for a hypothesis.The passage also states that γS(h) = pS and that wB(·) is given in the problem formulation.Source: A. Prediction · p. 18

B. Update

  • The update derivation computes quantities in Lemma 10 and uses ψzk(·) only for hypotheses with trajectories existing up to time step k.Source: B. Update · p. 18

APPENDIX F

  • Theorem 11 treats a transitioned set of trajectories through a multitrajectory density; the corresponding target RFS is a trajectory RFS with length-one trajectories and discarded start-time information.For the theorem's transition y = τk(X), the passage identifies the transition kernel as a multitarget Dirac delta.Source: Appendix F · p. 19

APPENDIX G

  • Appendix G states that the update relation is trivial and focuses on showing the prediction relation in Figure 5.Source: Appendix G · p. 19

Prediction without births (targets):

The derivation relates prediction densities for trajectory sets without births to densities after the transition to time k. It also describes prediction with births using convolution for targets and Theorem 11 for trajectories.

Prediction without births (trajectories):

Related papers

Loading 1605.08163v6…