PaperlayerView exact revision on arXiv

Source-linked AI summary

A Scalable Algorithm for Tracking an Unknown Number of Targets Using Multiple Sensors

Florian Meyer, Paolo Braca, Peter Willett, Franz Hlawatsch

arXiv:1607.07647v1cs.DS

TL;DR

Multisensor multitarget tracking must handle unknown target counts and data association while avoiding the exponential complexity of optimum methods. The paper uses belief propagation on a detailed factor graph with augmented target states and redundant association variables. Its complexity is quadratic in targets and linear in sensors and measurements, while simulations show performance comparable to or better than several existing filters.

  • Problem

    Multisensor tracking must address unknown target counts and data association, while optimum methods scale exponentially with key system parameters.

  • Method

    The method performs belief propagation on a detailed factor graph using augmented target states with binary indicators and redundant association variables.

  • Results

    The method scales quadratically in targets and linearly in sensors and measurements per sensor, with performance comparable to or better than previously proposed filters.

  • Takeaways & Limitations

    The approach supports multisensor tracking with an unknown, time-varying number of targets and provides approximate marginal posteriors for individual target states.

Abstract

from arXiv · show

We propose a method for tracking an unknown number of targets based on measurements provided by multiple sensors. Our method achieves low computational complexity and excellent scalability by running belief propagation on a suitably devised factor graph. A redundant formulation of data association uncertainty and the use of "augmented target states" including binary target indicators make it possible to exploit statistical independencies for a drastic reduction of complexity. An increase in the number of targets, sensors, or measurements leads to additional variable nodes in the factor graph but not to higher dimensions of the messages. As a consequence, the complexity of our method scales only quadratically in the number of targets, linearly in the number of sensors, and linearly in the number of measurements per sensors. The performance of the method compares well with that of previously proposed methods, including methods with a less favorable scaling behavior. In particular, our method can outperform multisensor versions of the probability hypothesis density (PHD) filter, the cardinalized PHD filter, and the multi-Bernoulli filter.

I. INTRODUCTION

Multitarget tracking must handle unknown target counts and measurement-to-target associations, while multisensor methods face difficult scalability and performance trade-offs. The paper proposes a belief-propagation method using augmented states and redundant association variables to address these challenges.

  • Multitarget tracking estimates moving-target states from measurements, often requiring multiple sensors for satisfactory reliability and accuracy.
  • Unknown target counts and measurement-to-target associations create central challenges for practical multitarget tracking.
  • Traditional methods commonly assume a fixed, known target count and therefore generally do not perform track management.
  • FISST-based methods avoid explicit data association and implicitly perform track management, but most existing methods are restricted to a single sensor.
  • Optimum multisensor-multitarget tracking has exponential complexity in sensors, targets, and measurements per sensor, whereas feasible methods use approximations or retain poor scaling.
  • The proposed method uses BP on a factor graph with augmented target states and redundant target- and measurement-oriented association variables.
  • Simulations with intersecting targets show performance comparable to prior methods and possible outperformance of several multisensor PHD, CPHD, and multi-Bernoulli filters.

B. Target Detection and State Estimation

The paper formulates target detection and state estimation as Bayesian inference over existence indicators and target states. It models potential-target dynamics with birth, survival, and state-transition distributions, while using augmented-state representations for BP computation.

  • The task is to calculate marginal posterior existence probabilities and conditional state pdfs from all past and present sensor measurements.
  • Targets are detected by thresholding posterior existence probabilities, after which their states are estimated with an MMSE estimator.
  • The main computational goal is a feasible recursive calculation of these posterior existence probabilities and state pdfs.
  • Augmented-state pdfs and BP messages represent both continuous target states and binary existence variables.
  • The model assumes target augmented states evolve independently according to Markovian dynamic models and are initially independent across targets.
  • Potential-target dynamics use birth probabilities and birth pdfs for previously nonexistent targets, and survival probabilities with transition pdfs for existing targets.
  • The known-target formulation from earlier work is recovered by setting survival probabilities to 1 and birth probabilities to 0.

B. Sensor Measurements

The sensor model describes thresholded measurements generated by existing targets or false alarms. Conditional independence assumptions factorize the multisensor likelihood into simpler components.

  • An existing target may be detected by a sensor when it generates a corresponding measurement.
  • False-alarm counts at each sensor follow a Poisson pmf with mean µ(s), and false-alarm measurements follow a sensor-specific pdf.
  • The likelihood formulation accounts for measurements that originate from targets, false alarms, or missed detections.
  • Given the relevant target states, association variables, and measurement counts, measurements are assumed conditionally independent across time and sensors.
  • Measurements at a sensor are additionally assumed conditionally independent given the target states, associations, and number of measurements.

C. Joint Prior Distribution of Association Variables and Numbers of Measurements

The joint prior over association variables and measurement counts is factorized using conditional-independence assumptions and a redundant association representation. This factorization supports the proposed BP method.

  • The prior over association vectors and measurement counts factorizes across time and sensors under conditional-independence assumptions.
  • A random-permutation assumption treats all measurement orderings at a sensor as equally likely.
  • The exclusion factor enforces that each existing target generates at most one measurement and each measurement is assigned to at most one target.
  • Target-oriented and measurement-oriented association vectors provide redundant representations of the association uncertainty.
  • The resulting factorization is identified as an important basis for the proposed BP method.

IV. REVIEW OF BP MESSAGE PASSING

Factor graphs represent a factorized joint posterior, enabling belief propagation to compute marginal posterior densities through local message passing. BP is exact on trees and approximate on loopy graphs.

  • Direct marginalization of the joint posterior is usually infeasible, whereas factorization enables efficient marginalization.
  • A factor graph represents variables as variable nodes and factors as factor nodes, connecting variables to the factors in which they appear.
  • BP computes marginal posterior pdfs by passing variable-dependent messages between adjacent variable and factor nodes.
  • Variable-to-factor messages multiply incoming messages from neighboring factors, while factor-to-variable messages integrate over the other variables.
  • On tree-structured factor graphs, beliefs equal exact marginal posteriors; on loopy graphs, iterative BP produces approximate beliefs whose values can depend on message order.

V. THE PROPOSED BP-BASED MULTISENSOR-

The proposed method represents multisensor multitarget detection and estimation with augmented target states and redundant association variables, then applies loopy BP to the resulting factor graph.

  • Target existence probabilities and conditional target-state posteriors are obtained from the marginal posterior pdf of each augmented target state.
  • The joint posterior includes augmented states, target-oriented and measurement-oriented association variables, and all sensor measurements through the current time.
  • Bayes’ rule and the implication that target-oriented associations determine measurement-oriented associations yield the final posterior factorization.
  • The factorization is represented by a factor graph that provides the starting point for the proposed BP method.
  • Loopy BP approximates each augmented-state marginal, using message-order rules that prohibit backward-in-time messages.
  • Prediction is performed for all potential targets, followed by parallel per-target and per-sensor processing.

1) Measurement evaluation:

After prediction, the method performs iterative data association and then forms normalized beliefs that approximate augmented-target marginals for detection and state estimation.

  • 1) Measurement evaluation: The data-association loop is initialized before successive message updates and uses an efficient implementation described in prior work.
  • 1) Measurement evaluation: Final beliefs are formed as products of messages and normalized to approximate the marginal posterior of each augmented target state.
  • 1) Measurement evaluation: The resulting beliefs support Bayesian target detection and state estimation and provide input for the next time step.
  • 1) Measurement evaluation: The data-association loop uses loopy BP, so it is not exact, but its high accuracy has been demonstrated numerically and its convergence proven.

C. Scalability

The method’s detailed factorization keeps message dimensions low as system size grows, yielding favorable complexity scaling while supporting particle-based implementation for nonlinear and non-Gaussian models.

  • C. Scalability: With a fixed number of iterations, total complexity is linear in sensors and quadratic in potential targets.
  • C. Scalability: Per-sensor operations scale linearly with the number of potential targets and false alarms.
  • C. Scalability: Favorable scaling follows from the detailed factorization enabled by redundant target-oriented and measurement-oriented association variables.
  • C. Scalability: Adding targets, sensors, or measurements adds variable nodes without increasing message dimensions.
  • C. Scalability: For general nonlinear and non-Gaussian models, a particle implementation avoids explicit evaluation of otherwise infeasible integrals and message products.
  • C. Scalability: Particle beliefs represent target existence through weight sums rather than normalized particle weights, and processing is parallel across potential targets.

B. Measurement Evaluation

The method implements belief propagation and subsequent measurement and belief updates with particle-based approximations. Importance sampling supplies weighted particles for association messages, normalization constants, and target-state beliefs.

  • The calculated weights yield a Monte Carlo approximation of the posterior quantities used by the data-association loop.Predicted existence and nonexistence probabilities are interpreted from the corresponding weighted-particle quantities.
  • After data-association convergence, approximate η messages are available for every potential target and sensor.These messages are then used in the measurement update and belief calculation steps.
  • Importance sampling rewrites the target-state belief so nonnormalized particle weights approximate the required belief quantities.The proposal density is α(xn,k, 1), represented by weighted particles.
  • Particle weights provide approximations of normalization constants and implicitly represent αn,k after normalization.The resulting particle-based approximation is used for the normalization constant Cn,k.

D. Target Detection, State Estimation, Resampling 

The method detects potential targets from estimated existence probabilities, computes MMSE states for detected targets, and resamples particles for the next time step. Birth and survival parameters are assigned using reliability-based track categories and measurement-driven birth proposals.

  • Target Detection and State Estimation: Each potential target is detected when its estimated existence probability exceeds the threshold Pth, after which its MMSE state estimate is calculated.The detection rule uses the particle-weight approximation of existence probability.
  • Resampling: Resampling reduces each potential target’s particle count to J and produces equally weighted particles for the next time step.The step is intended to reduce particle degeneracy effects.
  • Birth and Survival Parameters: Birth particles are generated by propagating particles from a previous birth density using particle-based prediction and prior knowledge.The construction uses measurements from an arbitrary sensor to form the birth density.
  • Birth and Survival Parameters: The birth scheme is heuristic but scales with the number of sensors while retaining good detection and tracking performance in the reported evaluation.It assumes Poisson-distributed newly born targets with mean µb and a fixed survival probability ps.
  • Birth and Survival Parameters: Reliable potential targets retain survival probability and receive no birth probability, whereas unreliable targets are assigned zero survival probability and measurement-based birth probabilities.Reliable and unreliable tracks are separated using the reliability threshold Rth.

VIII. RELATION TO EXISTING METHODS

The proposed method combines elements related to earlier belief-propagation, Bernoulli, JPDA, and track-initialization methods while extending the setting to multisensor multitarget tracking. Simulations evaluate the method against five previously proposed multisensor-multitarget trackers in a challenging intersecting-trajectory scenario.

  • Relation to Existing Methods: The hybrid target-oriented and measurement-oriented association model and belief propagation have precedents, but earlier uses addressed optical flow or data association without multitarget tracking.
  • Relation to Existing Methods: The target-existence model resembles search-initialize-track filtering, while the proposed method differs through belief propagation, multisensor operation, hybrid association, and track initialization.
  • Relation to Existing Methods: With one target and one sensor, the proposed method reduces to a particle-based Bernoulli filter implementation.
  • Relation to Existing Methods: Compared with TOMB/P, the proposed method is not restricted to one sensor or linear-Gaussian models, and it uses a fixed number of potential targets.TOMB/P allows the number of tracks to vary over time.
  • Simulation Setting: The simulation evaluates multisensor-multitarget tracking with up to five targets whose trajectories intersect at the region-of-interest center.Targets use a constant-velocity model, while sensors provide range and bearing measurements.
  • Simulation Setting: The implementation uses K = 8 potential targets, J = 3000 particles, I = 3000 birth particles, P = 20 BP iterations, and 150 time steps.The detection threshold is Pth = 0.5 and the reliability threshold is Rth = 10^-3.

B. Performance Comparison

Across challenging multisensor tracking scenarios, the proposed BP method outperforms the compared filters while maintaining favorable runtime scaling. Its complexity is linear in sensors and measurements, roughly quadratic in targets, and remains below 0.4 s per time step for 20 targets under the reported setting.

  • Accuracy: The proposed method outperforms the IC-PHD, IC-CPHD, IC-MB, MS-PHD, and MS-CPHD filters in the reported simulations.The comparison includes particle implementations of the IC filters and partition-based multisensor PHD variants.
  • Accuracy: Around intersecting target trajectories, particle-based PHD variants show higher MOSPA error because their clustering step becomes unreliable for nearby targets.The effect is reported around time n = 100, when trajectories intersect in the ROI center.
  • Accuracy: The MS-PHD and MS-CPHD errors increase for S larger than 5 because their maximum subset and partition counts are too small.Increasing those limits would lead to excessive simulation times.
  • Scalability: The proposed method’s runtime scales linearly with S and the mean number of measurements per sensor, while scaling roughly quadratically with the number of actual targets.With either the number of actual targets or PTs held fixed, the corresponding scaling becomes linear.
Loading 1607.07647v1…