PaperlayerView exact revision on arXiv

Source-linked AI summary

An Efficient Implementation of the Generalized Labeled Multi-Bernoulli Filter

Ba Ngu Vo, Ba Tuong Vo, Hung Gia Hoang

arXiv:1606.08350v2stat.COstat.AP

TL;DR

GLMB filtering becomes inefficient when separate prediction and update truncations propagate many components that later receive negligible weights. The paper combines both operations and uses Gibbs sampling for truncation. The resulting tracker has linear complexity in measurements and quadratic complexity in hypothesized tracks.

  • Problem

    Separate prediction and update truncations waste computation on predicted components whose updated components have negligible weights.

  • Method

    The paper combines GLMB prediction and update into one step and truncates the filtering density using Gibbs sampling.

  • Results

    The resulting implementation has linear complexity in the number of measurements and quadratic complexity in the number of hypothesized tracks.

  • Takeaways & Limitations

    The implementation provides an online GLMB tracker that can accommodate nonlinear dynamics and measurements, non-uniform survival probabilities, sensor field of view, and clutter intensity.

Abstract

from arXiv · show

This paper proposes an efficient implementation of the generalized labeled multi-Bernoulli (GLMB) filter by combining the prediction and update into a single step. In contrast to an earlier implementation that involves separate truncations in the prediction and update steps, the proposed implementation requires only one truncation procedure for each iteration. Furthermore, we propose an efficient algorithm for truncating the GLMB filtering density based on Gibbs sampling. The resulting implementation has a linear complexity in the number of measurements and quadratic in the number of hypothesized objects.

I. INTRODUCTION

Multi-object tracking estimates object counts and trajectories from sensor data, while GLMB provides a tractable labeled-RFS framework. The paper targets inefficiency from separate prediction and update truncations by jointly performing both and using Gibbs sampling.

  • Multi-object tracking jointly estimates the number of objects and their trajectories from sensor data.
  • GLMB introduced a tractable and mathematically principled RFS-based multi-object tracker.Its labeled representation supports propagation of the multi-object filtering density.
  • The original implementation separately truncates prediction and update sums using K-shortest path and ranked assignment algorithms.
  • Separate truncations waste computation because many predicted components produce updated components with negligible weights.The ranked assignment problems have at best cubic complexity in the number of measurements.
  • The proposed implementation jointly performs prediction and update and truncates the GLMB density with Gibbs sampling.It has linear complexity in measurements and is at least two orders of magnitude less than the original implementation.

B. Multi-object system model

The model represents objects and trajectories with labeled finite sets, then propagates surviving or newly born objects and associates detections through positive 1-1 maps. The GLMB recursion generates exponentially many components, motivating weight-based truncation.

  • Multi-object system model: Objects receive labels encoding birth time and a unique index, while labels persist across time to identify trajectories.
  • Multi-object system model: Objects independently survive and evolve, die, or appear as new births under the multi-object transition model.
  • Multi-object system model: Measurements arise from independent object detections or Poisson clutter, with missed detections assigned explicitly.
  • Multi-object system model: A positive 1-1 association map assigns measurements to labels while preventing any measurement from being assigned to multiple objects.
  • GLMB filter: Each GLMB component generates prediction and association children, causing the filtering density to grow exponentially with time.The original implementation truncates predicted and updated densities separately using K-shortest path and ranked assignment problems.

III. EFFICIENT IMPLEMENTATION OF THE GLMB FILTER

The efficient implementation directly recurses from one GLMB filtering density to the next by combining prediction and update. It retains significant children through one truncation procedure per iteration.

  • Joint prediction and update avoids propagating prediction components that would produce weak updated components.
  • Proposition 1 establishes a direct recursion between GLMB filtering-density components at consecutive times.
  • The joint recursion enumerates births, deaths, survivals, and measurement associations as combinations of component children.
  • At the next iteration, only components with their associated weights are propagated forward.
  • One truncation selects significant children of each component, reducing the inefficiency of separate prediction and update truncations.

B. GLMB truncation formulation

The truncation problem is reformulated as finding high-weight positive 1-1 vectors that encode object survival, birth, death, missed detection, and measurement association choices.

  • For a fixed component and measurement set, truncation seeks significant pairs of next labels and association maps.
  • Each vector entry records the measurement assigned to a label, with 0 denoting misdetection and −1 denoting nonexistence.
  • Positive 1-1 vectors prevent distinct labels from sharing the same positive measurement index.
  • The vector representation recovers both the next label set and its association map.
  • Finding significant GLMB children is equivalent to finding positive 1-1 vectors with significant weights.

C. Ranked Assignment

The paper formulates joint GLMB prediction and update truncation as a ranked assignment problem, then replaces costly ordered enumeration with Gibbs sampling of high-weight positive 1-1 vectors.

  • Ranked assignment: Ranked assignment algorithms generate the T highest-weight positive 1-1 vectors without exhaustive enumeration, but existing methods have high computational cost.Murty’s algorithm and more efficient ranked-assignment algorithms are identified as alternatives, while the paper targets a cheaper generation method.
  • Assignment formulation: Each positive 1-1 vector represents an assignment of hypothesized objects to measurements, misdetection, or nonexistence.The corresponding assignment matrix has one 1 per row and at most one 1 per column, with three partitions for detection, misdetection, and death or nonbirth.
  • Assignment formulation: The assignment cost matrix incorporates measurement generation, misdetection, and nonexistence through costs based on −ln ηi(j), −ln ηi(0), and −ln ηi(−1).Entries outside the permitted assignments have infinite cost, and assignment cost is related to the vector weight through an exponential transformation.
  • Gibbs sampling: Gibbs sampling generates unordered significant positive 1-1 vectors by decomposing the high-dimensional distribution into low-dimensional conditional sampling problems.The target distribution assigns probabilities proportional to vector weights, ensuring that higher-weight vectors are more likely to be sampled.
  • Gibbs sampling: The Gibbs conditionals are inexpensive to sample because they exclude assignments violating the positive 1-1 property, yielding O(PM) conditional sampling complexity and O(TP^2M) overall Gibbs complexity.The sampler always accepts proposed conditional updates and converges exponentially to the target distribution from any initial state in Γ.
  • Gibbs sampling: Distinct Gibbs samples can all contribute to δ-GLMB truncation because higher-weight sampled vectors reduce the L1 approximation error more.Unlike conventional MCMC inference, the procedure does not require discarding burn-in samples for stationary-distribution estimation.

E. Joint Prediction and Update Implementation

The implementation jointly performs prediction and update, then truncates the resulting GLMB density using Gibbs sampling. This reduces complexity to quadratic in hypothesized labels and linear in measurements.

  • Algorithm structure: At time k + 1, the algorithm processes three main tasks for generating and consolidating GLMB components.The procedure is summarized in Algorithm 2 and propagates the parameter set without storing ξ(h).
  • Gibbs-sampling truncation: Gibbs sampling generates candidate components by sampling parent parameters according to their weights and then sampling conditional child parameters.The implementation uses positive 1-1 vectors to represent the relevant associations.
  • Gibbs-sampling truncation: Annealing or tempering can seek more diverse samples, including components involving births, deaths, or other multi-object model events.Tempering changes the stationary distribution used by the sampler, while actual component weights are computed with the correct model parameters.
  • Limitations: If significant components exceed Hmax, filtering performance degrades in subsequent iterations.Small birth weights can also cause birth-containing components to be discarded when the available Hmax is insufficient, harming track initiation.
  • Complexity: O(P^2M) is the Gibbs-sampling complexity, quadratic in hypothesized labels P and linear in measurements M.Ranked assignment alternatives have complexities O((2P + M)^4) and O((2P + M)^3), cubic in both labels and measurements at best.

IV. NUMERICAL STUDIES

The numerical studies evaluate the proposed GLMB implementation in two scenarios. They assess computational efficiency in a linear Gaussian setting and versatility in a challenging nonlinear setting with non-uniform detection and dense clutter.

  • Numerical studies: Two numerical experiments evaluate the proposed GLMB filter implementation without considering parallelization.The first uses a linear Gaussian scenario, while the second uses a challenging nonlinear scenario with non-uniform detection and dense clutter.

A. Linear Gaussian

The linear Gaussian experiment compares CPU-time speedups against the original implementation in a multi-object tracking scenario with births, deaths, and crossings.

  • Scenario: The scenario contains an unknown, time-varying number of objects, with up to 10 objects, including births, deaths, and crossings.Individual object kinematics are described by a 4D state vector.
  • Scenario: The experiment uses survival probability PS = 0.99 and an LMB birth model with three birth labels, each having birth weight 0.04.The birth labels are ℓi = (k, i).
  • Scenario: Observations are 2D position vectors over a 2,000 m × 2,000 m region with 10 m noise standard deviation and detection probability PD = 0.88.Clutter follows a uniform Poisson RFS intensity of 1.65 × 10^-5 m^-2, averaging 66 false alarms per scan.
  • Implementation comparison: The proposed Gibbs implementation tempers the birth, survival, and detection parameters to increase component diversity.Birth weights are increased tenfold, while survival and detection probabilities are reduced by 5%; the Murty implementation uses the same tempered parameters.
  • Evaluation measures: Figures 2 and 3 compare the implementations using OSPA error and CPU-time speedup factors relative to the original implementation.Figure 2 reports OSPA errors, while Figure 3 reports speedup ranges across cases.

1) Case 1:

In Case 1, the joint prediction-update implementations achieve similar tracking accuracy with substantially lower computational cost than the original implementation.

  • Accuracy and truncation: Hmax = 10^4 for the original implementation and Hmax = 10^3 for both joint prediction-update implementations at comparable average OSPA error.The original implementation also exhibits pronounced OSPA peaks between k = 55 and k = 75.
  • Computational efficiency: About two orders of magnitude and one order of magnitude are the speedups for the Gibbs-based and Murty-based implementations, respectively.The comparison is against the original implementation.
  • Equal-budget comparison: With all implementations assigned Hmax = 10^4, Gibbs sampling still provides over one order of magnitude speedup while Murty yields a small improvement.Both joint implementations show slightly better average OSPA error than the original, supporting Hmax = 10^3 as a computational-performance trade-off.

3) Case 3:

In a challenging nonlinear, high-clutter scenario, the proposed implementation successfully tracks all objects, while joint prediction and update substantially outperform the original implementation in speed and OSPA behavior.

  • 3) Case 3:: Roughly three and two orders of magnitude of speedup are obtained by the Gibbs-based and Murty-based joint implementations, respectively.These speedups are reported for the extreme case with Hmax = 10^5 for the original implementation.
  • 3) Case 3:: The original implementation’s OSPA peaks reduce only slightly after increasing Hmax to 10^5 and remain worse than both joint implementations.In this extreme case, the original implementation takes too long for larger Hmax values to be useful.
  • 3) Case 3:: Reported speedups depend strongly on the scenario and testing platform and should be interpreted as broad indications of the expected range.The paper refers readers to separate real-data comparisons for actual speed and accuracy against recent algorithms.
  • 3) Case 3:: The scenario contains up to 10 objects with births, deaths, crossings, nonlinear kinematics, reduced detection, and increased clutter.Objects use a 5D state including planar position, velocity, and turn rate; observations are noisy 2D bearings and ranges with an average of 100 false alarms per scan.
  • 3) Case 3:: The proposed implementation successfully tracks all objects, as illustrated by the track estimates and confirmed by the OSPA curve.The cited sample run corresponds to Fig. 4 for tracks, measurements, and ground truths, and Fig. 5 for OSPA error.

VI. APPENDIX: MATHEMATICAL PROOFS

The appendix proves key properties of the Gibbs sampler’s finite-state Markov chain, including irreducibility, regularity, and convergence to the target distribution.

  • VI. APPENDIX: MATHEMATICAL PROOFS: The proofs characterize positive 1-1 association vectors by showing that repeated positive measurement assignments are excluded.The indicator identities establish when a vector and its reduced form satisfy the positive 1-1 property.
  • VI. APPENDIX: MATHEMATICAL PROOFS: A two-step transition argument shows that the Markov chain can move between any states and that a finite power of its transition matrix has positive entries.This establishes irreducibility and regularity for the finite-state chain.
  • VI. APPENDIX: MATHEMATICAL PROOFS: For the finite-state Gibbs sampler, irreducibility is sufficient for convergence to the target distribution, while regularity yields uniqueness of the stationary distribution and a convergence rate.The proof notes that the square of the transition matrix has all positive elements.
Loading 1606.08350v2…