Scalable Detection and Tracking of Geometric Extended Objects

A. State of the Art

• Random-matrix EOT models represent elliptical objects; the original model ties kinematic driving-noise variance to extent and keeps orientation constant.Refinements and particle-based alternatives address these limitations –.Source: A. State of the Art · p. 1
• Multiple-measurement JPDA methods, scale combinatorially and rely on gating; clustering-based EOT methods can lose performance when objects are close, –.The cited JPDA methods suit scenarios with few measurements and no more than four objects in close proximity.Source: A. State of the Art · p. 2
• Existing scalable SPA approaches can struggle to determine first-detection existence,, while alternatives assume known object counts or prior birth locations,.These assumptions make the alternatives unsuitable for spontaneous object births.Source: A. State of the Art · p. 2

B. Contributions and Notations

• The proposed Bayesian particle-based SPA uses measurement-oriented association variables and a Poisson birth process to track an unknown number of extended objects.Its factor graph supports scalable message passing and object-existence inference; the paper also reports performance advantages in simulation and with real autonomous-vehicle lidar measurements.Source: B. Contributions and Notations · p. 2

II. SYSTEM MODEL

• A positive-semidefinite extent state represents object geometry, allowing the particle-based method to model shapes beyond ellipses.The state can represent an ellipsoid or cube, with its eigenvalues and eigenvectors specifying shape dimensions and orientation.Source: B. Contributions and Notations · p. 2, §II · p. 3, Figure 1 · p. 4

B. Contributions and Notations

• The paper extends its conference account with a detailed factor-graph derivation, a particle implementation, scaling analysis, and synthetic and real comparisons with the PMBM filter.The probabilistic model is closely related to the PMBM model, while this work focuses on an SPA-friendly factor graph and particle-based accuracy and flexibility.Source: B. Contributions and Notations · pp. 2–3

II. SYSTEM MODEL

• Potential objects represent the unknown object count: each has a binary existence variable and an augmented state containing kinematics, extent, and existence.The number of potential objects is the maximum number of actual objects that have produced a measurement so far.Source: §II · p. 3

A. State-Transition Model

• Legacy-object transitions include survival with probability p_s and a kinematic state transition; the extent prediction uses a Wishart distribution.The degrees of freedom q_k,n govern extent-prediction uncertainty: smaller q_k,n means greater uncertainty.Source: A. State-Transition Model · p. 3

B. Measurement Model

• Three extent models describe measurements using a Gaussian covariance, a uniform elliptical support, or a uniform cubical support.The selected shape model determines the conditional measurement density.Source: B. Measurement Model · p. 4
• Each existing object generates a Poisson-distributed number of measurements, while false alarms follow a Poisson point process.The expected object-generated count may depend on extent and sensor resolution.Source: B. Measurement Model · p. 4

C. New POs

• Newly detected objects are modeled by a Poisson point process and represented by states linked to measurements, with a mapping for objects generating multiple measurements.The mapping assigns existence to the new-object state indexed by the smallest associated measurement index.Source: C. New POs · p. 4

D. Data Association Uncertainty

• Measurement-oriented association variables identify each return’s originating object or false-alarm status and support scalable sum-product algorithms.The mapping for new objects ensures each association event has a unique configuration of new-object existence variables and association values.Source: D. Data Association Uncertainty · p. 5

III. PROBLEM FORMULATION AND FACTOR GRAPH

• The section formulates object detection and estimation through a joint posterior density and its associated factor graph.The formulation is the basis for the proposed extended-object tracking method.Source: §III · p. 5

A. Object Detection and State Estimation

• Object detection thresholds posterior existence probability, while detected-object kinematic and extent states are estimated using MMSE estimators.The Bayesian approach computes existence probabilities and state posteriors from the observed measurement history.Source: A. Object Detection and State Estimation · p. 5

IV. THE PROPOSED SUM-PRODUCT ALGORITHM

• Sum-product message passing on the factor graph provides efficient approximate beliefs for marginal posterior densities of legacy and newly introduced objects.The target is a recursive calculation of the marginal posteriors.Source: A. Object Detection and State Estimation · p. 6

B. The Factor Graph

• The factor graph for the model has cycles, and message computations are ordered without sending messages backward in time, with parallel processing at each time step.Its structure is the same as a conventional multi-scan tracking problem when each measurement is treated as a scan.Source: §IV · p. 6, B. The Factor Graph · p. 6

A. Prediction Step

• The algorithm begins by predicting the states of all legacy objects from their previous beliefs.The following iterative message-passing operations are performed for legacy and new objects.Source: A. Prediction Step · p. 6

B. Iterative Message Passing

• The iterative message-passing stage performs its specified operations for all legacy and new objects at each iteration.The iteration index ranges from 1 to P.Source: B. Iterative Message Passing · p. 7

1) Measurement Evaluation:

• Measurement-evaluation messages are calculated between factor and variable nodes for legacy and new objects.The evaluation stage introduces normalized messages used in subsequent data association and measurement updates.Source: 1) Measurement Evaluation · p. 7

2) Data Association:

• Data-association messages pass from measurement-oriented variable nodes to factor nodes.The messages are computed using the sum-product algorithm rule.Source: 2) Data Association · p. 7

3) Measurement Update:

• Measurement-update messages are sent to object-state variables for legacy and newly introduced objects.The update operations include messages from factors associated with legacy and new objects.Source: 3) Measurement Update · pp. 7–8

4) Extrinsic Information:

• Updated messages provide extrinsic information for the next message-passing iteration.For non-existent objects, the messages incorporate the predicted density for the extent state.Source: 4) Extrinsic Information · p. 8

C. Belief Calculation

• Legacy and new-object beliefs are calculated from incoming messages as normalized products, with normalization constants ensuring valid probability distributions.Source: C. Belief Calculation · p. 8
• Parallel message passing has been reported to improve performance over sequential processing.Source: C. Belief Calculation · p. 8

D. Computational Complexity and Scalability

• For fixed P, overall complexity is O(KM+M^2), equivalently O(KM), and increasing iterations beyond P = 3 does not significantly improve typical EOT performance.Preclustering and censoring can further reduce complexity.Source: D. Computational Complexity and… · pp. 8–9

V. PARTICLE-BASED IMPLEMENTATION

• The particle-based implementation approximates operations that generally lack closed-form solutions, representing beliefs with weighted particles whose weight sum approximates object-existence probability.Source: §V · p. 9

A. Prediction

• Prediction represents the legacy-object prediction message α with weighted particles drawn using a proposal based on the preceding particle representation.Source: A. Prediction · p. 9

B. Measurement Evaluation

• Measurement evaluation approximates transformed measurements as Gaussian, using linearization or the unscented transformation to enable closed-form likelihood expressions.A proposal distribution for new-object messages can be calculated from each measurement and its uncertainty.Source: B. Measurement Evaluation · p. 9

• The approximate measurement-evaluation messages feed the subsequent approximation of ξ.Source: C. Measurement Update, Belief… · p. 10
• Importance sampling implements the measurement update and belief calculation, using α(x_k,e_k,1) as the proposal density for the legacy-object belief.Source: C. Measurement Update, Belief… · p. 10
• The belief calculation reuses particles, while particle representations for new-object beliefs and extrinsic-information messages can be obtained by similar steps.Source: C. Measurement Update, Belief… · p. 10

D. Detection, Estimation, Pruning, and Resampling

• For each legacy or new object, the method estimates existence probability and declares it detected when that probability exceeds a threshold; it then estimates kinematic state and extent.Objects with existence probabilities below a pruning threshold are removed from the state space, and resampling may be used to avoid particle degeneracy.Source: D. Detection, Estimation, Pruning, and… · p. 10

VI. NUMERICAL RESULTS

• The numerical evaluation compares the proposed method with the PMBM filter implementation in using simulation results.The simulations use OSPA and GOSPA metrics; the PMBM implementation uses measurement gating and clustering.Source: §VI · p. 10, A. Simulation Scenario · p. 11, B. Performance Comparison with the… · p. 11

A. Simulation Scenario

• Objects were simulated on intersecting tracks: ten started around a circle, began existing in pairs, and converged near the region’s center.Their extents were held constant over time, with a mean of eight measurements per object and ten false alarms on average.Source: A. Simulation Scenario · pp. 10–11

B. Performance Comparison with the PMBM Filter

• When objects were close, the proposed SPA methods outperformed PMBM on mean OSPA; PMBM’s increased cardinality error arose when clusters from multiple objects were assigned to one object.The resulting missed detections reduced other objects’ existence probabilities; despite avoiding gating, clustering, and association-event pruning, SPA runtime was comparable to PMBM in the 10-object simulation.Source: B. Performance Comparison with the… · p. 12, Figure 4 · p. 12

C. Size, Orientation, and Scalability

• The proposed particle-based SPA estimated object size and orientation more reliably than PMBM when objects were close together.Errors were computed using optimum assignments from OSPA across 120 simulation runs.Source: C. Size, Orientation, and Scalability · p. 12, Figure 5 · p. 13
• For 20 closely spaced objects, SPA’s OSPA performance advantage over PMBM was comparable to that in the 10-object scenario.This was an extreme case in which all 20 objects came into close proximity; per-time-step runtimes were 48.1 s for SPA-2-10000, 76.0 s for SPA-3-10000, 6.7 s for PMBM-CR, and 171.4 s for PMBM-FR.Source: C. Size, Orientation, and Scalability · pp. 12–13

VII. REAL-DATA PROCESSING

• Evaluation used four nuScenes scenes not used for training, with vehicle-related lidar measurements extracted by a supervised method trained on 700 scenes and filtered at confidence above 0.25.The dataset contains 850 scenes, each about 20 seconds long with approximately 400 lidar point clouds.Source: §VII · p. 13
• Vehicles are modeled with 2-D cubical extents and kinematic states that include position, velocity, turn rate, and mean measurement count.The mean measurement count is part of the random state because it depends strongly on distance from the lidar sensor.Source: §VII · p. 13
• At time step 105 of scene S4, all five actual vehicles are detected and tracked reliably.The figure presents lidar observations, ground truth, and estimated positions, extents, and tracks.Source: §VII · p. 14, Figure 7 · p. 14
• The proposed SPA outperforms PMBM in mean GOSPA and individual error contributions across four scenes and all time steps.All PMBM variants perform similarly; Table II also reports runtimes per time step.Source: Table II · p. 14, §VII · p. 14

VIII. CONCLUSION

• The factor-graph SPA models association uncertainty with measurement-oriented variables and births with a Poisson process, while particle inference supports different shapes and quadratic scaling in objects and measurements.It dynamically introduces newly detected object states and allows multiple measurements per object.Source: §VIII · p. 14
• In intersecting-track simulations, the method outperforms PMBM despite reduced computational complexity, and real urban lidar results also show performance advantages over PMBM.Vehicle-related lidar measurements were extracted using supervised learning with a deep neural network.Source: §VIII · p. 14
• The authors identify neural-network integration with iterative message passing and GPU-oriented parallelization as future research directions.The proposed parallel variants could exploit particle flow for real-time implementations.Source: §VIII · p. 14

Supplementary Material

• The listed authors are Florian Meyer and Jason L. Williams.Source: Supplementary Material · p. 17
• The manuscript provides derivations and pseudocode for “Scalable Extended Object Tracking.”It is described as a supplement to the publication by the same authors.Source: Supplementary Material · p. 17
• The manuscript is arXiv:2103.11279v4, dated 9 Dec 2021.Source: Supplementary Material · p. 17

1.1 The Conditional Prior PDF p

• The conditional prior maps newly detected objects into a fixed set of new potential-object states and models object births and false-alarm counts with Poisson distributions.The number of newly detected objects remains random even though the number of new potential-object states is fixed by the measurements.Source: §1.1 · pp. 17–20

1.2 The Joint Prior PDF f

• The joint prior combines per-object state transitions with assumptions of independent object evolution and temporal conditional independence.The derivation assumes new states, associations, and measurement counts at time n are conditionally independent of earlier states and associations given the preceding states.Source: §1.2 · pp. 23–24

1.3 The Joint Likelihood Function f(z1:n|y1:n, b1:n, M1:n)

• The joint likelihood factors across measurements under the assumption that measurements are conditionally independent given the object states, associations, and measurement count.Source: §1.3 · p. 24
• Assuming measurement noise and false-alarm measurements are independent across time, the joint likelihood is expressed using that assumption.The passage introduces the likelihood expression after stating the independence assumption.Source: §1.3 · p. 24

1.4 Final Expression for the Joint Posterior PDF f

• With measurements observed and fixed, Bayes’ rule and the implication from z_n to M_n support deriving the joint posterior, reported in [1, Eq. (11)].Substituting the joint prior and likelihood expressions and rearranging yields combined factors h_k and the final posterior expression.Source: §1.4 · p. 25

2 Evaluation of the Likelihood Function

• The approximation reduces the likelihood calculation to one-dimensional integrations with closed-form expressions obtainable using the Q-function.The resulting closed form is intended to enable efficient particle-based methods for extended-object tracking.Source: §2 · pp. 25–26
• The proposed likelihood approximation treats the object extent as an infinite plane or volume when it is much larger than the measurement-noise standard deviation.It uses the closest point on the extent boundary and projects the measurement noise onto the direction toward the measurement.Source: §2 · p. 26
• For a cube with uniform support and iid Gaussian measurement noise, the exact likelihood is the product of three directional contributions, normalized by the cube’s volume.Each contribution corresponds to one eigenvalue and its associated eigenvector; along the first direction, the expression distinguishes measurements between the two edges from those beyond either edge.Source: §2 · pp. 26–27

3 Implementation of the Proposed EOT Method

• Algorithm 1 presents the proposed particle-based extended-object tracking method as pseudocode for one time step.The pseudocode follows the particle-based implementation discussed in [1, Section V].Source: §3 · pp. 27–28
• The time-step procedure predicts legacy objects and initializes new objects before evaluating measurements for legacy objects.The pseudocode then combines measurement-evaluation information for legacy and new objects.Source: §3 · p. 28
• The procedure calculates extrinsic information messages and beliefs for legacy and new objects.Its update loops include measurement-oriented calculations over measurements and object particles.Source: §3 · p. 28