PaperlayerView exact revision on arXiv

Source-linked AI summary

A Solution for Large-scale Multi-object Tracking

Michael Beard, Ba Tuong Vo, Ba-Ngu Vo

arXiv:1804.06622v1stat.CO

TL;DR

Large-scale multi-object tracking must handle unknown, time-varying object populations amid clutter, misdetections, and association uncertainty. The paper develops a scalable GLMB tracker based on density decomposition and parallel processing, and demonstrates tracking with more than one million simultaneous objects while evaluating performance with OSPA(2).

  • Problem

    Large-scale tracking is computationally difficult because object and measurement combinations grow rapidly, creating a need for methods that can process very large populations.

  • Method

    The tracker decomposes GLMB densities into approximately independent sub-problems, exploits parallel computation, and uses OSPA(2) for scalable track-set evaluation.

  • Results

    More than one million objects appear simultaneously in the simulated scenario, while OSPA(2) error stabilises to approximately 0.2 metres per object per unit time outside birth periods.

  • Takeaways & Limitations

    The implementation estimates trajectories for millions of objects per frame by decomposing large tracking problems into smaller independent sub-problems.

Abstract

from arXiv · show

A large-scale multi-object tracker based on the generalised labeled multi-Bernoulli (GLMB) filter is proposed. The algorithm is capable of tracking a very large, unknown and time-varying number of objects simultaneously, in the presence of a high number of false alarms, as well as misdetections and measurement origin uncertainty due to closely spaced objects. The algorithm is demonstrated on a simulated large-scale tracking scenario, where the peak number objects appearing simultaneously exceeds one million. To evaluate the performance of the proposed tracker, we also introduce a new method of applying the optimal sub-pattern assignment (OSPA) metric, and an efficient strategy for its evaluation in large-scale scenarios.

I. INTRODUCTION

Large-scale multi-object tracking is computationally difficult because object counts vary, measurements contain clutter and missed detections, and associations are uncertain. The paper proposes a GLMB-based tracker that decomposes computation while introducing OSPA(2) for scalable trajectory evaluation.

  • Multi-object tracking is NP-hard because object counts vary and measurements involve clutter, misdetections, and association uncertainty.
  • Large-scale tracking is challenging because the number of event combinations grows explosively with objects and measurements.
  • The proposed filter targets tracking on the order of a million objects and measurements per frame using off-the-shelf computing equipment.
  • The tracker adaptively approximates each GLMB filtering density as a product of tractable, approximately independent GLMB densities.
  • Parallel computation exploits GLMB conjugacy to identify significant combinations efficiently under limited processing and memory resources.
  • OSPA(2) adapts OSPA to compare track sets while accounting for trajectory-related properties and remaining computable for scenarios involving millions of tracks.

III. SCALABLE GLMB FILTERING: THEORETICAL FOUNDATIONS

Existing GLMB implementations become infeasible at large object counts because measurement updates process many posterior hypotheses. The theoretical foundation therefore decomposes the label space into smaller sub-problems and approximates the resulting density by independent factors.

  • The original GLMB implementation has a measurement-update bottleneck because it ranks posterior components for every predicted-density component using Murty’s algorithm.
  • Cubic complexity in the numbers of targets and measurements makes the original implementation computationally infeasible for large N and M.
  • Gibbs sampling lowers per-component computational cost, but quadratic complexity in the number of objects remains infeasible for large simultaneous tracking problems.
  • The proposed decomposition partitions the label space so each sub-problem has an upper-bounded number of objects.
  • For a fixed label-space partition, the GLMB density can be decomposed optimally into a product of smaller GLMB densities by using marginal densities.

B. Marginalising GLMB Densities

The marginalisation construction produces a GLMB density for each group in a label-space partition. This supplies the group-wise factors needed for the product approximation.

  • For a two-group label-space partition, the marginalised GLMB density for the first group is given by the stated marginalisation equations.
  • For a general partition, the marginalised density corresponding to each group is constructed using the same argument.

IV. SCALABLE GLMB FILTERING: IMPLEMENTATION

The scalable GLMB filter decomposes a large tracking problem into smaller groups whose posterior densities can be processed in parallel. The decomposition exploits approximate statistical independence arising when tracks are well separated in measurement space, but may fail when independent subsets do not exist.

  • The implementation decomposes one large tracking problem into many smaller sub-problems requiring fewer computational resources.
  • The partition limits group size to control each group’s memory use and GLMB update time under available computing and real-time constraints.
  • The ideal decomposition balances approximation error against group-size constraints by approximating the full GLMB with a product of marginal GLMB densities.
  • Labels are partitioned so objects in different groups are approximately statistically independent, avoiding direct optimisation over the intractable space of partitions.
  • Measurement-space bounding-region overlap identifies potential measurement sharing, while spatial searching reduces partition-construction complexity to O(N log N).
  • In the worst case, independent label subsets may not exist, preventing the proposed decomposition from effectively reducing computational complexity.
  • Each update factorises prior terms, reconstructs marginal priors for new groups, and computes their posterior GLMB densities in parallel using Gibbs sampling.

V. PERFORMANCE EVALUATION

The paper extends OSPA-based evaluation from point states to tracking performance while establishing the notation for time, object states, tracks, and metric properties. This provides the foundation for evaluating estimated and true sets of tracks.

  • Traditional OSPA measures distance between estimated and true multitarget states at each instant but does not fully account for errors between sets of tracks.
  • OSPA(2) applies OSPA to tracking evaluation by using an OSPA-based distance as its base distance.
  • The framework defines T as the finite set of scenario time indices and X as the single-object state space, with F(X) containing finite subsets of X.
  • A track is a function from time indices in T to state vectors in X, and its domain contains the times at which the object exists.
  • The base distance relies on a metric satisfying non-negativity, identity, symmetry, and the triangle inequality.

1) Base Distance Between Tracks :

The base distance between tracks averages OSPA distances between their state sets over the union of their active time domains. It is bounded by the cutoff and is proven to be a metric under stated conditions.

  • The track distance averages OSPA distances between the state sets generated by two tracks over all times in their combined domains.
  • At times when a track is absent, its state set is empty; when present, the state set is a singleton containing its state.
  • The order parameter p becomes redundant in the resulting singleton-or-empty-set base-distance expression.
  • The base distance is a metric when the underlying finite-set distance is a metric and singleton-to-empty-set distance equals the cutoff c.
  • Because the base distance is bounded by c, distances between tracks saturate at the cutoff value.
  • For tracks with identical domains, the base distance can be interpreted as mean square error and generalises it to differing lengths or domains.

2) OSPA(2) for Tracks:

OSPA(2) measures dissimilarity between finite sets of tracks by applying optimal assignment to a track-distance cost matrix. Its efficient evaluation exploits cutoff saturation, while sliding windows expose performance over selected time scales.

  • OSPA(2) is the OSPA distance between sets of tracks using the time-averaged track distance as its base distance.
  • The metric is interpreted as time-averaged per-track error, with cutoff c and order parameter p controlling the distance.
  • Evaluation forms an m × n cost matrix, solves a two-dimensional optimal assignment, and applies the resulting minimum cost to the OSPA(2) distance.
  • A dense implementation is infeasible for millions of objects because storing the cost matrix consumes excessive memory and solving the assignment is computationally impractical.
  • Because most track-pair distances saturate at c, exploiting cutoff saturation can substantially reduce evaluation complexity for large-scale problems.
  • Sliding windows retain tracks whose domains overlap the selected time indices, allowing performance trends to be examined across different time scales.
  • When the window contains one time step, OSPA(2) becomes identical to traditional OSPA; window choice therefore changes the interpretation of the result.

B. Numerical Results

The GLMB implementation is evaluated in a simulated 1000-step scenario exceeding one million simultaneous objects, using cardinality, OSPA(2), and density summaries. It tracks at large scale, with delayed initiation during births and stable error between birth periods.

  • Scenario: 1,082,974 objects peak simultaneously at time 400 in the simulated large-scale tracking scenario.The scenario spans 1000 time steps in a 16 km × 9 km surveillance region.
  • Computational performance: The implementation processes the highest-cardinality frame in approximately 5 minutes on 64 physical cores with 256 GB of memory.The algorithm was coded in C++ and parallelized with OpenMP.
  • OSPA(2) evaluation: The average time to evaluate each point on the OSPA(2) curve is approximately 1 minute.The reported evaluation uses the large-scale scenario's OSPA(2) performance curve.
  • Tracking performance: The estimated cardinality lags behind the true cardinality while new targets are born because measurement-driven birth considers many potential tracks.Track initiation is delayed to obtain more data and avoid excessive false tracks.
  • Tracking performance: OSPA(2) error increases during target births, then stabilizes at approximately 0.2 metres per object per unit time.The OSPA(2) calculation uses cutoff c = 2, order p = 1, and a 50-step sliding window.
  • Density summaries: Figures 3 and 4 compare true and estimated target densities at times 50, 200, 400, 600, 800, and 1000.The density summaries replace individual trajectories, which are impractical to display at this scale.

APPENDIX

The appendix proves that the proposed track-set distance satisfies the metric properties, including identity, symmetry, and the triangle inequality. The triangle inequality is established by induction over time and algebraic bounds on the component distances.

  • Metric properties: The proposed distance is nonnegative because its summation terms and track-set cardinalities are nonnegative.This establishes metric property P1.
  • Metric properties: The distance equals zero exactly when the two track sets are identical, establishing metric property P2.The proof applies the single-time metric property across all relevant time instants.
  • Metric properties: Symmetry follows because the underlying single-time distance is symmetric and the union of time domains is commutative.This establishes metric property P3.
  • Triangle inequality: The triangle inequality is proved by induction over successive time instants, using the single-time triangle inequality and bounds on p, q, and r.The proof treats empty and non-empty track-domain cases and verifies the resulting algebraic expressions are nonnegative.
  • Proof notation: The appendix defines P, Q, R, and T as cardinality combinations of shared and unmatched track-time domains for the triangle-inequality proof.These quantities organize the algebraic bounds used in the induction.
Loading 1804.06622v1…