The book shows that the analytic combinatorics (AC) method encodes the combinatorial problems of multiple object tracking―without information loss―into the derivatives of a generating function (GF). The book lays out an easy-to-follow path from theory to practice and includes salient AC application examples. Since GFs are not widely utilized amongst the tracking community, the book takes the reader from the basics of the subject to applications of theory starting from the simplest problem of single object tracking, and advancing chapter by chapter to more challenging multi-object tracking problems. Many established tracking filters (e.g., Bayes-Markov, PDA, JPDA, IPDA, JIPDA, CPHD, PHD, multi-Bernoulli, MBM, LMBM, and MHT) are derived in this manner with simplicity, economy, and considerable clarity. The AC method gives significant and fresh insights into the modeling assumptions of these filters and, thereby, also shows the potential utility of various approximation methods that are well established techniques in applied mathematics and physics, but are new to tracking. These unexplored possibilities are reviewed in the final chapter of the book.
Author(s): Roy Streit, Robert Blair Angle, Murat Efe
Publisher: Springer
Year: 2020
Language: English
Pages: 221
City: Cham
Preface
Contents
Acronyms
1 Introduction to Analytic Combinatorics and Tracking
1.1 Introduction
1.2 The Benefits of Analytic Combinatorics to Tracking
1.3 Sensor and Object Models in Tracking
1.4 Likelihood Functions and Assignments
1.5 A First Look at Generating Functions for Tracking Problems
1.5.1 Statement A—Object Existence and Detection
1.5.2 Statement B—Gridded Measurements
1.5.3 Statement C—Gridded Object State and the Genesis of Tracking
1.6 Generating Functions for Bayes Theorem
1.6.1 GF of the Bayes Posterior Distribution
1.6.2 Bayes Inference in Statement A
1.6.3 Bayes Inference in Statement B
1.6.4 Bayes Inference in Statement C
1.7 Other Models of Object Existence and Detection
1.7.1 Multiple Object Existence Models
1.7.2 Random Number of Object Existence Models
1.7.3 False Alarms
1.8 Organization of the Book
References
2 Tracking One Object
2.1 Introduction
2.2 AC and Bayes Theorem
2.3 Setting the Stage
2.4 Bayes-Markov Single-Object Filter
2.4.1 BM: Assumptions
2.4.2 BM: Generating Functional
2.4.3 BM: Exact Bayesian Posterior Distribution
2.5 Tracking in Clutter—The PDA Filter
2.5.1 PDA: Assumptions
2.5.2 PDA: Generating Functional
2.5.3 PDA: Exact Bayesian Posterior Distribution
2.5.4 PDA: Closing the Bayesian Recursion
2.5.5 PDA: Gating—Conditioning on Subsets of Measurements
2.6 Object Existence—The IPDA Filter
2.6.1 IPDA: Assumptions
2.6.2 IPDA: Generating Functional
2.6.3 IPDA: Exact Bayesian Posterior Distribution
2.6.4 IPDA: Closing the Bayesian Recursion
2.7 Linear-Gaussian Filters
2.7.1 The Classical Kalman Filter
2.7.2 Linear-Gaussian PDA: Without Gating
2.7.3 Linear-Gaussian PDA: With Gating
2.8 Numerical Example: IPDA
References
3 Tracking a Specified Number of Objects
3.1 Introduction
3.2 Joint Probabilistic Data Association (JPDA) Filter
3.2.1 Multivariate Generating Functional
3.2.2 Exact Bayes Posterior Probability Distribution via AC
3.2.3 Measurement Assignments and Cross-Derivative Terms
3.2.4 Closing the Bayesian Recursion
3.2.5 Number of Assignments
3.2.6 Measurement Gating
3.3 Joint Integrated Probabilistic Data Association (JIPDA) Filter
3.3.1 Integrated State Space
3.3.2 Generating Functional
3.3.3 Exact Bayes Posterior Probability Distribution via AC
3.3.4 Closing the Bayesian Recursion
3.4 Resolution/Merged Measurement Problem—JPDA/Res Filter
3.5 Numerical Examples: Tracking with Unresolved Objects
3.5.1 JPDA/Res Filter with Weak and Strong Crossing Tracks
3.5.2 JPDA/Res with Parallel Object Tracks
3.5.3 Discussion of Results
References
4 Tracking a Variable Number of Objects
4.1 Introduction
4.2 Superposition of Multiple Object States
4.2.1 General Considerations
4.2.2 Superposition with Non-identical Object Models
4.3 JPDAS: Superposition with Identical Object Models
4.3.1 Information Loss Due to Superposition
4.3.2 Generating Functional of the Bayes Posterior
4.3.3 Probability Distribution
4.3.4 Intensity Function and Closing the Bayesian Recursion
4.3.5 Intensity Function and the Complex Step Method
4.4 CPHD: Superposition with an Unknown Number of Objects
4.4.1 Markov Chain for Number of Objects
4.4.2 Probabilistic Mixture GFL
4.4.3 Bayes Posterior GFL
4.4.4 Posterior GF of Object Count
4.4.5 Exact Bayes Conditional Probability
4.4.6 Intensity Function
4.4.7 Closing the Bayesian Recursion
4.5 State-Dependent Models for Object Birth, Death, and Spawning
4.5.1 New Object Birth Process
4.5.2 Darwinian Object Survival Process
4.5.3 Object Spawning (Branching)
4.6 PHD: A Poisson Intensity Filter
4.7 Numerical Examples
4.7.1 JPDAS Filter
4.7.2 PHD Filter
4.7.3 Discussion of Results
References
5 Multi-Bernoulli Mixture and Multiple Hypothesis Tracking Filters
5.1 Introduction
5.2 Multi-Bernoulli (MB) Filter
5.2.1 Prior and Predicted Processes: JIPDA with Superposition
5.2.2 GF of Predicted Number of Objects
5.2.3 Predicted Multiobject PDF
5.2.4 Predicted Multiobject Intensity Function
5.2.5 GFL of the MB Filter
5.2.6 GFL of the MB Posterior Process
5.2.7 Exact MB Posterior Process Is an MBM
5.2.8 Interpretation of the Posterior Mixture
5.2.9 Posterior Probability Distribution
5.2.10 Intensity Function of the Posterior Process
5.2.11 GF of the Number of Existing Objects—MB Filter
5.2.12 Closing the Multi-Bernoulli Bayesian Recursion
5.3 Multi-Bernoulli Mixture (MBM) Filter
5.3.1 GFL of the MBM Process at Scan k-1
5.3.2 GFL of the MBM Predicted Process at Scan k
5.3.3 GF of the Predicted Aggregate Number of Objects in the MBM
5.3.4 Probability Distribution of Predicted MBM Multiobject State
5.3.5 GFL of the Joint MBM Process
5.3.6 GFL of the MBM Bayes Posterior Process
5.3.7 MHT-Style Hypotheses
5.3.8 GF of Aggregate Object Number—MBM Filter
5.3.9 Intensity of the MBM Posterior
5.3.10 Closing the Bayesian Recursion for MBM Filters
5.4 Labeled MBM Filter
5.4.1 Labels in Analytic Combinatorics
5.4.2 GFL of the LMBM Filter
5.4.3 Track-Oriented LMBM and Closing the Bayesian Recursion
5.5 Multiple Hypothesis Tracking (MHT) Filter
5.6 Conjugate Families
5.7 Numerical Example: JIPDAS Filter
References
6 Wither Now and Why
6.1 To Count or Not to Count, that Is the Question
6.2 Low Hanging Fruit
6.3 Techniques for High Computational Complexity Problems
6.4 Higher Level Fusion and Combinatorial Optimization
References
Appendix Generating Functions for Random Variables
A.1 Introduction
A.2 Definitions and Basic Properties for One Variable
A.3 Bivariate Generating Functions
A.4 Multivariate Generating Functions
A.5 Generating Functions for Random Histograms
Appendix Generating Functionals for Finite Point Processes
B.1 Introduction
B.2 Cluster Point Processes
B.3 Generating Functionals (GFLs) for Finite Point Processes
B.4 Derivatives of GFLs
B.5 Secular Functions
B.6 Intensity Function and Other Summary Statistics
B.7 Bivariate Finite Point Processes
B.8 Bayesian Posterior Finite Point Processes
B.9 Marginalizing a Bivariate Point Process
B.10 Superposition of Bivariate Finite Processes
B.11 Sequential Bayesian Estimation—Palm Processes
B.12 Pair Correlation Functions
Appendix Mathematical Methods
C.1 Complex Variables
C.1.1 One Variable
C.1.2 Several Variables
C.2 Dirac Deltas and Trains of Dirac Deltas
C.3 Calculus of Variations
C.4 Mixed and Cross-Derivatives
C.5 Machine Precision Derivative of Analytic Functions
C.6 Automatic Differentiation (AD)
Appendix Glossary
Index
