Trajectory PHD and CPHD Filters Garcia-Fernandez, Angel F.; Svensson, Lennart
IEEE transactions on signal processing,
11/2019, Volume:
67, Issue:
22
Journal Article
Peer reviewed
Open access
This paper presents the probability hypothesis density filter (PHD) and the cardinality PHD (CPHD) filter for sets of trajectories, which are referred to as the trajectory PHD (TPHD) and trajectory ...CPHD (TCPHD) filters. Contrary to the PHD/CPHD filters, the TPHD/TCPHD filters are able to produce trajectory estimates from first principles. The TPHD filter is derived by recursively obtaining the best Poisson multitrajectory density approximation to the posterior density over the alive trajectories by minimising the Kullback-Leibler divergence. The TCPHD is derived in the same way but propagating an independent identically distributed (IID) cluster multitrajectory density approximation. We also propose the Gaussian mixture implementations of the TPHD and TCPHD recursions, the Gaussian mixture TPHD (GMTPHD) and the Gaussian mixture TCPHD (GMTCPHD), and the L-scan computationally efficient implementations, which only update the density of the trajectory states of the last L time steps.
In this article, we propose a metric on the space of finite sets of trajectories for assessing multi-target tracking algorithms in a mathematically sound way. The main use of the metric is to compare ...estimates of trajectories from different algorithms with the ground truth of trajectories. The proposed metric includes intuitive costs associated to localization error for properly detected targets, missed and false targets and track switches at each time step. The metric computation is based on solving a multi-dimensional assignment problem. We also propose a lower bound for the metric, which is also a metric for sets of trajectories and is computable in polynomial time using linear programming. We also extend the proposed metrics on sets of trajectories to random finite sets of trajectories.
Temporal Parallelization of Bayesian Smoothers Sarkka, Simo; Garcia-Fernandez, Angel F.
IEEE transactions on automatic control,
2021-Jan., 2021-1-00, 20210101, Volume:
66, Issue:
1
Journal Article
Peer reviewed
Open access
This article presents algorithms for temporal parallelization of Bayesian smoothers. We define the elements and the operators to pose these problems as the solutions to all-prefix-sums operations for ...which efficient parallel scan-algorithms are available. We present the temporal parallelization of the general Bayesian filtering and smoothing equations, and specialize them to linear/Gaussian models. The advantage of the proposed algorithms is that they reduce the linear complexity of standard smoothing algorithms with respect to time to logarithmic.
Trajectory Poisson multi-Bernoulli filters Garcia-Fernandez, Angel F.; Svensson, Lennart; Williams, Jason L. ...
IEEE transactions on signal processing,
01/2020, Volume:
68
Journal Article
Peer reviewed
Open access
This paper presents two trajectory Poisson multi-Bernoulli (TPMB) filters for multi-target tracking: one to estimate the set of alive trajectories at each time step and another to estimate the set of ...all trajectories, which includes alive and dead trajectories, at each time step. The filters are based on propagating a Poisson multi-Bernoulli (PMB) density on the corresponding set of trajectories through the filtering recursion. After the update step, the posterior is a PMB mixture (PMBM) so, in order to obtain a PMB density, a Kullback-Leibler divergence minimisation on an augmented space is performed. The developed filters are computationally lighter alternatives to the trajectory PMBM filters, which provide the closed-form recursion for sets of trajectories with Poisson birth model, and are shown to outperform previous multi-target tracking algorithms.
This article proposes a general formulation for temporal parallelization of dynamic programming for optimal control problems. We derive the elements and associative operators to be able to use ...parallel scans to solve these problems with logarithmic time complexity rather than linear time complexity. We apply this methodology to problems with finite state and control spaces, linear quadratic tracking control problems, and to a class of nonlinear control problems. The computational benefits of the parallel methods are demonstrated via numerical simulations run on a graphics processing unit.
This paper proposes a Poisson multi-Bernoulli mixture (PMBM) filter on the space of sets of tree trajectories for multiple target tracking with spawning targets. A tree trajectory contains all ...trajectory information of a target and its descendants, which appear due to the spawning process. Each tree contains a set of branches, where each branch has trajectory information of a target or one of the descendants and its genealogy. For the standard dynamic and measurement models with multi-Bernoulli spawning, the posterior is a PMBM density, with each Bernoulli having information on a potential tree trajectory. To enable a computationally efficient implementation, we derive an approximate PMBM filter in which each Bernoulli tree trajectory has multi-Bernoulli branches, obtained by minimising the Kullback-Leibler divergence. The resulting filter improves tracking performance of state-of-the-art algorithms in a simulated scenario.
Belief propagation (BP) is a useful probabilistic inference algorithm for efficiently computing approximate marginal probability densities of random variables. However, in its standard form, BP is ...only applicable to the vector-type random variables with a fixed and known number of vector elements, while certain applications rely on random finite sets (RFSs) with an unknown number of vector elements. In this paper, we develop BP rules for factor graphs defined on sequences of RFSs where each RFS has an unknown number of elements, with the intention of deriving novel inference methods for RFSs. Furthermore, we show that vector-type BP is a special case of set-type BP, where each RFS follows the Bernoulli process. To demonstrate the validity of developed set-type BP, we apply it to the Poisson multi-Bernoulli (PMB) filter for simultaneous localization and mapping (SLAM), which naturally leads to a set-type BP PMB-SLAM method, which is analogous to a vector type SLAM method, subject to minor modifications.
This paper presents the posterior linearization belief propagation (PLBP) algorithm for cooperative localization in wireless sensor networks with nonlinear measurements. PLBP performs two steps ...iteratively: linearization and belief propagation. At the linearization step, the nonlinear functions are linearized using statistical linear regression with respect to the current beliefs. This SLR is performed in practice by using sigma-points drawn from the beliefs. In the second step, belief propagation is run on the linearized model. We show by numerical simulations how PLBP can outperform other algorithms in the literature.
This article proposes a Gaussian filtering method to approximate the single-target updates and normalizing constants for multitarget tracking with nonlinear, non-Gaussian measurements, and a ...state-dependent probability of detection. The Gaussian approximation is based on the posterior linearization technique, which seeks the optimal affine approximation of the nonlinearities in a mean square error sense. The normalizing constant is approximated using sigma-points based on the posterior. The proposed approach is implemented in a Poisson multi-Bernoulli mixture filter and compared against standard methods to approximate single-target posteriors and normalizing constants in two range-bearings tracking scenarios.
This paper presents a multitarget tracking particle filter for general track-before-detect measurement models. The particle filter is presented in the random-finite-set framework and uses a labeled ...multi-Bernoulli approximation. I also present a label-switching improvement algorithm based on Markov-chain Monte Carlo methods that is expected to increase filter performance if targets are in close proximity for a sufficiently long time. The particle filter is tested in two challenging numerical examples.