PaperlayerView exact revision on arXiv

Source-linked AI summary

Extended Object Tracking: Introduction, Overview and Applications

Karl Granstrom, Marcus Baum, Stephan Reuter

arXiv:1604.00970v3cs.CVeess.SPeess.SY

TL;DR

Extended object tracking must represent object extent while handling difficult distance evaluation and combinatorial data association. The article surveys modelling and multi-object tracking approaches, highlighting tractable approximations and unresolved challenges in arbitrary-shape estimation.

  • Problem

    Extended-object estimates include extent information, making distance to ground truth nontrivial, while multi-object updates require intractable measurement partitions and associations.

  • Method

    The article surveys extended-object models and tracking methods, including random-matrix extensions, PHD, CPHD, GLMB, LMB, PMBM, and distance-partitioning approaches.

  • Results

    Distance Partitioning reduced more than 10^10 possible partitions to 5 in one 17-measurement example without sacrificing reported performance in simulations and experiments.

  • Takeaways & Limitations

    Extended-object tracking remains an active area because arbitrary-shape estimation is challenging and performance bounds are needed to relate shape complexity, measurements, and estimation error.

  • Takeaways & Limitations

    Current evaluation measures can behave counterintuitively, including identical IoU errors for differently sized non-overlapping translational errors and RMSE inconsistencies for equivalent shapes.

Abstract

from arXiv · show

This article provides an elaborate overview of current research in extended object tracking. We provide a clear definition of the extended object tracking problem and discuss its delimitation to other types of object tracking. Next, different aspects of extended object modelling are extensively discussed. Subsequently, we give a tutorial introduction to two basic and well used extended object tracking approaches - the random matrix approach and the Kalman filter-based approach for star-convex shapes. The next part treats the tracking of multiple extended objects and elaborates how the large number of feasible association hypotheses can be tackled using both Random Finite Set (RFS) and Non-RFS multi-object trackers. The article concludes with a summary of current applications, where four example applications involving camera, X-band radar, light detection and ranging (lidar), red-green-blue-depth (RGB-D) sensors are highlighted.

I. INTRODUCTION

Extended object tracking addresses objects that generate multiple spatially distributed measurements, requiring recursive estimation of both object shape and kinematic parameters. This article introduces the problem, reviews modelling and tracking methods, discusses multi-object association, and surveys applications and research developments.

  • Traditional multiple target tracking assumes independently evolving point-like objects that generate at most one measurement per time step.
  • Advances in sensor resolution increasingly produce scenarios where objects occupy several sensor cells, invalidating the traditional small-object assumptions.
  • Extended object tracking recursively estimates an object’s unknown, potentially time-varying shape together with its kinematic parameters from multiple noisy measurements.
  • Unlike contour tracking, extended object tracking uses sparse Cartesian point measurements rather than contours extracted from complete RGB images.
  • Shape estimation generally requires accumulating and fusing measurements across several time steps while accounting for unknown motion and sensor noise.
  • For multiple extended objects without measurement-to-object associations, data association requires measurement partitions and assignments, creating a huge hypothesis space.
  • The article surveys extended-object definitions, shape and measurement models, single- and multiple-object methods, applications, and future trends, building on substantial progress since early work.

B. Object state

An extended-object state combines position, motion, and extent parameters, while measurement models describe noisy detections conditioned on that state. The required state and measurement assumptions depend on the object, sensor, and motion being represented.

  • The object state typically combines position, kinematic variables, and extent parameters describing shape, size, and orientation.
  • For a car tracked with horizontally mounted 2D LIDAR, the state includes 2D position, velocity, heading, turning angle, length, and width.
  • This car model assumes a rectangular shape whose orientation is aligned with the car’s heading.
  • State design depends strongly on the object type, sensor data, and motion to be described; cars may use 2D position, whereas airborne objects may require 3D position.
  • The number and spatial arrangement of detections vary with sensor-to-target geometry and object orientation, while sensor noise affects the measurements.
  • Extended-object measurement modelling uses a conditional likelihood that captures both the number of detections and their spatial distribution around the target state.

1) Set of points on a rigid body:

Set-of-Points-on-a-Rigid-Body models represent an extended object through a fixed number of reflection points, each capable of producing at most one measurement. They require explicit association between reflection points and detections, whereas spatial models avoid that association by modelling detections directly around the target.

  • Set of points on a rigid body: SPRB models represent an extended object using reflection points located on a rigid body shape.Automotive-radar examples model eight points on a car, including corners and wheel-houses.
  • Set of points on a rigid body: Each reflection point is detected independently with a state-dependent detection probability, and the measurement process forms a multi-Bernoulli RFS.Each point contributes a Bernoulli measurement process, while the complete object is represented by a multi-Bernoulli random finite set.
  • Set of points on a rigid body: SPRB likelihoods require data association between the object’s reflection points and target detections.Association becomes challenging when the number and locations of reflection points are uncertain; auction, Murty, PDA, and related methods can address it.
  • Spatial model: Spatial models instead describe a varying number of detections distributed around the target, using either Poisson or binomial detection-count assumptions.The PPP model uses a state-dependent Poisson rate and avoids explicit association; the alternative spatial model uses a binomial count with parameters L and pD.
  • Spatial model: Spatial measurement models can combine an object-shape source distribution with a sensor-noise model, such as uniform sources on visible car sides and Gaussian noise for 2D LIDAR.For rectangular cars, measurements may be modelled along one or two visible sides.
  • Spatial model: The PPP model is mathematically convenient and has been applied to structured measurements, but tracking results are sensitive to the state-dependent Poisson rate γ(x).A gamma-augmented state distribution can estimate an individual Poisson rate for each extended object.

3) Physics based modelling:

Physics-based modelling derives extended-object measurement models from sensor properties, while shape modelling ranges from no extent representation to arbitrary shapes. The suitable complexity and spatial distribution depend on the sensor, object, motion, available measurements, and tracking purpose.

  • Physics based modelling: Physics-based approaches derive SPRB models for automotive radar and can model both detection counts and measurement likelihoods from sensor properties.For high-resolution radar, measurements may depend on their locations in the range-Doppler image.
  • Shape modelling: Shape modelling has three levels: no shape model, a basic geometric shape, or an arbitrary shape representation.These levels correspond respectively to estimating kinematics only, using shapes such as ellipses or rectangles, and representing more general extents.
  • Shape modelling: More complex shapes require more and less noisy measurements to obtain a reasonable shape estimate.The appropriate choice also depends on sensor type, object class, motion, computational resources, and the intended tracking output.
  • Shape modelling: For 2D-LIDAR bicycle tracking, modelling a stick-shaped extent with uniform sources and Gaussian noise improved estimation performance and captured rotations.The simple stick was chosen as a measurement-likelihood model rather than as a literal visual representation of the bicyclist.
  • Measurement spatial distribution: Boundary measurements form noisy points on curves or surfaces, whereas volumetric measurements form clusters inside the object extent.Automotive LIDAR commonly produces boundary measurements, while some marine-radar detections can be interpreted as measurements from inside a two-dimensional shape.
  • Dynamic modelling: Extended-object tracking dynamics include kinematic evolution, extent changes such as rotation, and changes in measurement count over time.Probabilistic prediction uses a transition density together with the Chapman-Kolmogorov equation, and standard CV, CA, and CT motion models can describe kinematics.

III. TRACKING A SINGLE EXTENDED OBJECT

The section introduces random matrix modelling for single extended objects, including Gaussian and noise-adapted measurement models. It also reviews approximate updates and their reported performance trade-offs.

  • A. Random Matrix Approach: Random matrix models represent an object with a kinematic state vector and a symmetric positive-definite extent matrix, approximating its shape by an ellipse.The kinematic vector captures position and motion properties, while the extent matrix is d × d for 2D or 3D tracking.
  • 1) Original measurement model:: The original model assumes conditionally Gaussian measurements with measurement noise negligible relative to the object extent.Its conjugate Gaussian and inverse Wishart structure supports the original state distribution and linear measurement update.
  • 2) Improved noise modelling:: The factorised state model permits more general kinematic vectors, including nonlinear dynamics such as heading and turn-rate, but assumes independence between kinematics and extent.The measurement update provides practical interdependence, while the assumption cannot be fully theoretically justified.
  • 2) Improved noise modelling:: The noisy factorised model outperforms the original model when measurement noise is non-negligible, while variational updates reduce error at higher computational cost.The variational update is reported to converge on average in 5 iterations, with 20 iterations used in the simulation study; log-linearisation nearly matches it at lower cost.

3) Non-linear measurements:

Real-world radar measurements are often nonlinear and have range-dependent noise, requiring coordinate conversion or nonlinear update approximations. The reviewed approaches adapt the covariance and reuse existing update schemes.

  • 3) Non-linear measurements:: Radar commonly measures range and azimuth rather than Cartesian position, making the measurement model nonlinear.Polar noise also makes the Cartesian noise covariance depend on the reflection point.
  • 3) Non-linear measurements:: One approach converts polar measurements to Cartesian coordinates and models the noise covariance as a function of the reflection point.The resulting noise spread is larger farther from the sensor, and the convolution lacks an analytical solution.
  • 3) Non-linear measurements:: Approximating the noise covariance enables the linearised, Cholesky-based, or variational updates developed for other measurement models.Other work handles nonlinear range and azimuth using linearisation and variational Bayes, while radar Doppler rate can also be integrated into the model.

4) Dynamic modelling:

Random matrix dynamic models predict kinematics and extent through transition densities, heuristics, or approximations. More general state-dependent transformations improve modelling of turning targets, especially when motion prediction matters.

  • 4) Dynamic modelling:: The original model uses linear Gaussian kinematic transitions and Wishart extent transitions, with process noise controlled by the parameter n_k.Smaller n_k corresponds to higher extent process noise, while heuristic prediction keeps expected extent constant and increases its variance.
  • 4) Dynamic modelling:: Heuristic extent prediction is sufficient for sufficiently slow manoeuvres but neglects extent rotation and other dependencies on kinematics.The model assumes kinematics are independent of extent, which helps retain the desired functional form.
  • 4) Dynamic modelling:: Generalised transition densities use transformations dependent on the kinematic state, allowing rotation to be coupled to turn-rate and estimated online.For nonlinear motion models, the predicted density is approximated as factorised Gaussian inverse Wishart by minimising Kullback-Leibler divergence.
  • 4) Dynamic modelling:: For constant-turn targets with unknown turn-rate, the state-dependent prediction gives the lowest filtering and prediction errors among the compared predictions.When the true turn-rate is known, the predictions in Tables X and XI perform similarly.
  • 4) Dynamic modelling:: Accurate motion modelling becomes crucial when multiple nearby objects make prediction important despite many measurements per object.With many measurements and well-separated objects, the measurement update can dominate and compensate for dynamic modelling errors.

5) Further extensions of the random matrix model:

The random matrix framework has been extended to multiple-object tracking, mapping, non-ellipsoidal shapes, and improved performance evaluation. These extensions broaden applicability while addressing shape and dependence limitations.

  • 5) Further extensions of the random matrix model:: Random matrix models have been incorporated into PMHT and RFS-type filters for tracking multiple extended objects in clutter.Related extensions include JPDA-type algorithms, spawning and merging, multiple object types, and multisensor updates.
  • 5) Further extensions of the random matrix model:: The random matrix model has also been applied to mapping with batch measurement updates that process all data at once rather than sequentially.This extends the framework beyond conventional single-object filtering applications.
  • 5) Further extensions of the random matrix model:: Irregular extents can be approximated by combining multiple elliptically shaped subobjects, although basic subobject models assume independence.Making subobject kinematic vectors dependent can significantly improve estimation performance.
  • 5) Further extensions of the random matrix model:: Gaussian Wasserstein distance is identified as the best performance measure for estimates from random matrix predictions and updates.A posterior Cramér-Rao lower bound is also available for the prediction and update proposed in.

B. Star-Convex Shape Approaches

Star-convex approaches represent general shapes with parametric contours, Gaussian joint-state uncertainty, and nonlinear Kalman-filter updates. They avoid the elliptic restriction of random matrix models but require more complex formulas.

  • Star-convex approaches use a parametric contour representation, Gaussian uncertainty for joint kinematic and shape parameters, and nonlinear Kalman filters for measurement updates.
  • Unlike random matrix models, these approaches represent general star-convex shapes without using multiple subobjects.
  • The nonlinear measurement model maps state and noise to measurements while assuming Gaussian prior-state and measurement-noise densities.
  • Because the measurement noise is non-additive, the likelihood generally lacks a closed-form solution, preventing direct application of likelihood-based nonlinear estimators.
  • Nonlinear Kalman filters approximate posterior mean and covariance by extending Kalman formulas, but the approximation can be rough under high measurement nonlinearity.

2) Random Hypersurface Model for Star-Convex Shapes:

The random hypersurface model parameterizes star-convex contours through a radius function and embeds them in a nonlinear measurement equation. Fourier and Gaussian-process representations provide alternative shape models, while partial likelihood improves association in high noise.

  • The random hypersurface model maps shape parameters and an angle through a radius function to contour points relative to the object center.
  • Fourier coefficients with small indices capture coarse shape features, whereas larger indices represent finer contour details.
  • The overall state combines shape parameters, object location, and kinematic parameters in a joint representation.
  • The polar measurement equation uses multiplicative scaling noise and angle as latent variables, reducing filled-shape estimation to curve fitting.
  • Partial likelihood outperforms greedy association in many cases, including high-noise scenarios, without additional complexity for star-convex shapes.
  • Gaussian-process models replace Fourier expansions and are recursively approximated with a finite set of function values or basis points for tracking.

4) Further developments, extensions and variations:

Further developments extend random hypersurface and multiplicative-error models to elliptic, symmetric, and arbitrary connected shapes. Extended-object filters address clutter, missed detections, and association, with performance–computation trade-offs.

  • Random hypersurface models can represent circular and elliptic shapes using implicit functions instead of parametric forms.
  • Extensions incorporate symmetry information and combine boundary scaling with level sets to model arbitrary connected shapes.
  • Clutter detections can improve shape estimation when modelled as negative information, and extended-object tracking can support camera calibration.
  • The Multiplicative Error Model uses scaling factors for both dimensions to better match uniform spatial distributions for simple shapes such as circles and ellipses.
  • Direct Kalman updates for the elliptic model can be unsatisfactory because of strong nonlinearities, motivating measurement augmentation with squared measurements.
  • Multiple-target tracking must handle unknown object counts, missed measurements, variable detection counts, clutter, and unknown measurement origins.

A. Review – RFS filters

RFS filters model object and measurement sets jointly to address multiple-object tracking under uncertain counts, detections, clutter, and associations. PHD, CPHD, multi-Bernoulli, GLMB, and PMBM approaches trade representational detail, trajectory handling, accuracy, and computational cost.

  • RFS tracking models both the set of objects and the set of measurements as random finite sets.
  • Full multi-object Bayes filtering is computationally demanding because of data association, motivating tractable approximations such as PHD and CPHD filters.
  • PHD filters estimate the first-order moment under a Poisson cardinality assumption, whose high cardinality variance appears especially with missed measurements.
  • PHD and CPHD filters use multi-modal intensities for objects, but nearby objects can produce unresolved modes corresponding to multiple objects.
  • Basic PHD and CPHD forms do not formally estimate trajectories, although trajectories can be recovered through post-processing with labelling schemes.
  • GLMB filters use labels to obtain trajectories and represent association histories as mixture components, while LMB approximates this mixture with a single labeled multi-Bernoulli density.
  • The PMBM prior separates detected from undetected objects, representing them with a multi-Bernoulli mixture and a Poisson point process, respectively.
  • GGIW-CPHD outperforms GGIW-PHD especially at low detection probability or high clutter density, but its computational cost is higher.

2) CB-MeMBer filters:

Extended-object multi-target tracking must manage partitions of measurements and assignments of partition cells to object sources, creating severe combinatorial complexity. The literature addresses this through approximate filters, clustering, gating, and alternative tracker formulations.

  • Complexity analysis: Extended-object data association splits into partitioning measurements into cells and associating cells with object or clutter sources.Each cell contains measurements from one extended object or clutter, and every partition requires considering possible source assignments.
  • Complexity analysis: Bayes-optimal updates require all partitions and cell associations, but both become intractable except with very few measurements and objects.The number of partitions grows rapidly with the Bell numbers, while cell-association possibilities also become infeasible as cells and objects increase.
  • Complexity reduction: Gating removes measurement-to-object associations whose measurements differ too much from predicted measurements, reducing the association search space.For extended targets, gates must account for the target’s spatial extent.
  • Complexity reduction: For 17 measurements, Distance Partitioning reduces more than 10^10 possible partitions to 5 candidate partitions without sacrificing reported performance.The method uses spatial proximity and multiple thresholds; prior object-count information can help when nearby objects cannot be separated by distance alone.
  • Tracker approaches: Extended-object filters and trackers approximate association complexity using methods including PHD and CPHD filters, clustering, MHT, PMHT, and Markov chain Monte Carlo filtering.The Gaussian Mixture Markov Chain Monte Carlo filter is reported as less sensitive to clutter but considerably more computationally costly than the linear ET-GM-PHD filter.

V. METRICS AND PERFORMANCE EVALUATION

Extended-object tracking requires metrics that compare both kinematics and shape, but common measures can behave unintuitively or lack generality. The paper reviews these issues alongside applications demonstrating evaluation across sensors, shapes, and crowded scenes.

  • Metrics and performance evaluation: Extended-object performance evaluation is difficult because tracker outputs include extent information, making estimate-to-ground-truth distance nontrivial.RMSE is not always straightforward for extended objects because different parameterizations can represent the same Cartesian shape.
  • Metrics and performance evaluation: RMSE can assign different errors to equivalent rectangular shapes when width and length are switched in the state representation.This violates the intuition that identical shapes in Cartesian surveillance space should have identical shape-comparison errors.
  • Metrics and performance evaluation: IoU divides the intersection area by the union area, but it is always zero for non-overlapping shapes regardless of translational separation.For non-axis-aligned rectangles and other shapes, IoU computation can also be cumbersome.
  • Metrics and performance evaluation: No general single performance criterion has yet been specified for non-elliptic extended-object shapes.For multiple extended objects, OSPA and G-OSPA are directly applicable once a single-object metric has been chosen.
  • Applications: The reviewed applications span camera, X-band radar, LIDAR, and RGB-D sensors, including pedestrian groups, marine vessels, autonomous-vehicle cars, and complex-shaped objects.The examples cover group tracking, differing shape complexity, and crowded scenarios with occlusions.
  • Applications: In camera-based pedestrian-group tracking, estimated ellipses approximate groups well, while Poisson rates tend to underestimate group size because occluded individuals are missed.The Poisson rate is more accurate when interpreted as a lower bound for the number of persons in the group.

B. Tracking marine vessels using X-band radar

Marine X-band radar provides high-resolution vessel measurements that support extended-object tracking and size estimation, while noise modelling materially affects the estimated vessel extent.

  • Marine vessel tracking: Marine X-band radar supports tracking vessels in busy harbours, where estimating vessel size can also enable classification using size priors.The sensor’s field of view and harbour-tracking context are illustrated in Figure 13.
  • Marine vessel tracking: CFAR preprocessing produces polar detections, which are converted to Cartesian coordinates before applying a random matrix model with elliptical vessel shapes.The ellipse assumption is an approximation because boats and ships are typically not elliptically shaped.
  • Marine vessel tracking: Correctly modelling measurement noise prevents the vessel size from being overestimated, especially in the cross-range dimension.Figure 14 contrasts estimates obtained with correctly modelled and unmodelled noise.
  • Marine vessel tracking: Using multiple radar sensors can further improve tracking results.
Loading 1604.00970v3…