► A control systems problem to point an antenna towards an object of interest.

► The prediction of the future state of a dynamical system based on measurements and models.

► The act of connecting a vehicle’s consecutive positions over time.

► A problem that was solved by Rudolph E. Kálmán in 1960.

► An aid to reduce the workload of radar operators.

► A process of finding objects of interest where humans couldn’t discern them.

► An optional part of a radar/sonar system.

► An indispensable part of a radar system.

► A critical part of a missile control system or of a counter-missile system.

► A trivial connecting of the dots.

► Something that people can do better than the computer.

► Something that the computed can do better than people.

► An aid to reduce the workload of radar operators.

► A process of finding objects of interest where humans couldn’t discern them.

► An optional part of a radar/sonar system.

► An indispensable part of a radar system.

► A critical part of a missile control system or of a counter-missile system.

► A trivial connecting of the dots.

► Something that people can do better than the computer.

► Something that the computed can do better than people.

► Getting started can be difficult.

► No comprehensive textbooks on tracking exist.

► Some useful books:

► The International Conference on Information Fusion by the International Society of Information Fusion (ISIF) is the most relevant to target tracking, especially networked/multistatic tracking.

► The Tracker Component Library (TCL) offers over 1,000 free, commented Matlab routines related to Tracking, Coordinate Systems, Mathematics, Statistics, Combinatorics, Astronomy, etc.

1. Mathematical Preliminaries

2. Coordinate Systems (in the unabridged slides)

3. Measurements and Noise

4. Measurement Conversion (in the unabridged slides)

5. Bayes’ Theorem and the Linear Kalman Filter Update

6. Stochastic Calculus and Linear Dynamic Models (in the unabridged slides)

7. The Linear Kalman Filter Prediction

8. Linear Initial State Estimation and the Information Filter

9. Nonlinear Measurement Updates

10. Square Root Filters (in the unabridged slides)

11. Direct Filtering Versus Measurement Conversion

12. Data Association

13. Integrated and Cascaded Logic Trackers

14. Dealing with Beams (in the unabridged slides)

15. Summary

1. Univariate and Multivariate Taylor Series Expansions

2. Useful Probability Distributions.

3. Cubature Integration.

4. The Cramér-Rao Lower Bound.

► The four most prevalent probability distributions in target tracking tend to be:

► In the TCL, functions relating to these and many other distributions are given in “Mathematical Functions/Statistics/Distributions.”

► For the above distributions, see GaussianD, ChiSquareD, BinomialD, and PoissonD in the TCL.

► The central chi-squared distribution with k degrees of freedom is

where Γ is the gamma function.

► Plotted is χ²(x, 3).

► Confidence regions of a desired % are easily determined using Gaussian approximations, Mahalanobis distances, and chi-squared statistics.

► Given a Gaussian PDF estimate of a target, a point x, is within the first pth-percentile if

where γ_p depends on p and on d_x, the dimensionality of x.

Values of γp for p and dx.

► Use ChiSquareD.invCDF in the TCL to determine γ_p.

► The chi-squared distribution plays a role in assessing covariance consistency.

► The covariance is consistent if it realistically models the error.

► The Normalized Estimation Error Squared (NEES) is the simplest of multiple methods for assessing consistency.

► If estimator is unbiased, covariance is always correct and errors truly Gaussian, then the NEES is time a central chi-squared random variable with Nd_x degrees of freedom.

► The function calcNEES in the TCL can be useful.

► Consider constant false alarm rate (CFAR) detector with a given P_FA per cell, such as the ones given by the CACFAR or OSCFAR functions in the TCL.

► Grid of N cells (e.g. in range and range-rate).

► Probability of n false alarms is binomially distributed.

► The binomial distribution is almost never used in trackers.

► It is approximated by a Poisson distribution with the same .

► Both plots, for both distributions.

► At N = 1000, the binomial and Poisson plots look the same.

► Many integrals cannot be solved analytically with a finite number of terms.

► Try to evaluate a Fresnel integral:

► Quadrature integration is a technique for efficient numerical evaluation of univariate integrals.

► Cubature integration is multivariate quadrature integration.

► The TCL has many functions related to cubature integration in “Mathematical Functions/Numerical Integration” and “Mathematical Functions/Numerical Integration/Cubature Points.”

► Evaluate

► Basic calculus solution: A Riemann sum:

► Riemann sums converge very slowly.

► The idea in quadrature/cubature is the relation

► Efficient: For a fifth-order integral with a multivariate Gaussian weighting function, one can choose points such that N = 12.

► Many parts of target tracking involve solving difficult multivariate integrals.

► Many algorithms fall into one of two categories:

► This comes up again and again.

► The Cramér-Rao Lower Bound (CRLB) is a lower bound on the variance (or covariance matrix) of an unbiased estimator.

► The CRLB and a posterior CRLB (PCRLB) are widely used to asses tracker performance.

► Under certain conditions, the CRLB states

► The Fisher information matrix has two equivalent formulations:

► Are these points false alarms or a possible track over time?

► Are they accurate measurements that are far apart?

► Are false alarms very unlikely or highly likely?

► Are these points false alarms or a possible track over time?

► These are the same points as before at a different scale.

► Measurements are inherently noisy.

► Knowledge of measurement noise level determines scale.

► The blue line is “connect-the-dots.” The orange line just adds interpolation.

► The blue/orange lines are only good if the points are very accurate.

► The green line is much more reasonable if the points are inaccurate.

► The noise level determines the best fit.

► Given a PDF p(x) representing the target state estimate at a particular time.

► Given a measurement z and a conditional PDF of the measurement p(z|x).

► Bayes’ theorem states that

► The value p(z) is essentially a normalizing constant.

where S is whatever space x is in (For discrete variables, the integral becomes a sum).

► Bayes’ theorem underlies all rigorous measurement update algorithms in tracking.

► The Kalman filter measurement update is just Bayes’ theorem applied to a linear/Gaussian measurement model assuming a Gaussian prior.

► Notation change for standard tracking:

► The discrete measurement update step of the Kalman filter

with common notation/terminology.

► The updated covariance estimate has been reformulated in Joseph’s form for numerical stability.

► See KalmanUpdate in “Dynamic Estimation/Measurement Update” in the TCL.

► The Kalman filter update is optimal for measurements that are linear combinations of the target state.

► However, why not just apply Bayes’ theorem more precisely?

► Bayes’ theorem is again:

► Bayes’ theorem is trivial. Why not always do it optimally?

► Bayes’ theorem is just normalized multiplication. Why not just discretize space and do everything almost optimally on a grid?

► Simplest “optimal” Bayesian filter:

► It is simple.

► With parallelization over GPUs, couldn’t it be done quickly?

► Why the brute-force grid approach is seldom done:

► A smarter approach would be to use some type of adaptive grid or set of points.

► The Kalman filter is much faster than the most efficient particle filter.

► The stochastic dynamic models describe prediction when the initial state x is deterministic.

► The prediction step of the standard Kalman filter is derived in the unabridged slides and handles random x.

► See the discKalPred function in the TCL.

1. One-point initiation.

2. Using an information filter.

► One-point initiation is the simplest approach:

► Known position, other components “uninformative”.

► Updates and predictions can then be done using the standard Kalman filter.

► A rule of thumb for σ_i is to use the maximum value of the value of the moment divided by 2 or 3.

► Measurement updates are possible without Cartesian conversion.

► Major nonlinear filtering algorithms shown.

► We focus on the Extended Kalman Filter and variants of the cubature Kalman filter (which include the “unscented” KF).

► See EKFUpdate and cubKalUpdate in the TCL.

► The Kalman filter arose from a Bayesian update given that a linear measurement and the state are jointly Gaussian.

► Approximating a nonlinear measurement

where w is Gaussian, as jointly Gaussian with the state, one still has the same basic update equations as the Kalman filter

► The simplest solution to the nonlinear integrals is to use cubature integration, shown above.

► The square root is a lower-triangular Cholesky decomposition.

► The vector formulation above requires all cubature weights be positive, but allows for Joseph’s form to be used.

► A Joseph’s formulation supporting negative cubature weights is probably impossible.

► An alternative approach is to use a Taylor series expansion of the nonlinear function.

► The result is the extended Kalman filter (EKF), shown above.

► Two common approaches for basic tracking exist:

► These shall be compared in a simple example.

► A flat Earth.

► All ships on the surface traveling −10m/s in the negative z direction.

► The target initially at an altitude of 7 km going 100m/s.

► Radars on ships pointed 15° up from the horizontal.

► q͂ = 0.4802m²/s³

► Measurements every T = 0.5 s.

► Tracks initialized via an information filter with 2 converted measurements.

► .

► The positional RMSE error of three different tracking algorithms. The CKF used 5th order points.

► The CKF has the best RMSE performance.

► The NEES of three different tracking algorithms.

► The EKF is bad; the CKF is the best over time; converted measurements are initially the best.

► Common algorithms for assigning measurements to targets shown.

► We focus on non random finite set (RFS)-based single scan approaches.

1. The Likelihood Function.

2. Naïve Nearest Neighbor, the Score Function, and Global Nearest Neighbor (GNN)

3. Probabilistic Data Association (PDA) and Joint Probabilistic Data Association (JPDA) variants

► Consider one known target with a Gaussian prediction x̂_k|k−1, P_k|k−1 with a 100% detection probability and with N_M measurements present.

► Which measurement should be assigned to the target?

► Single-scan data association algorithms make this decision based only on the current state prediction x̂_k|k−1, P_k|k−1.

► Multiple scan data association look at multiple sets of measurements.

► Let H^p be a matrix so H^px extracts the position components of a Cartesian state.

► Given Cartesian-converted measurements one might assign the ith one such that

► This is usually bad:

► One cannot convert the state to the measurement coordinate system and use a similar l₂ norm.

► Valid distance measures can be derived from likelihood functions and likelihood ratios.

► Let Z^k−1 be the set of all measurements up to discrete time k − 1 and Θ^k−1 be the information of which measurements are assigned to the track up to time k − 1.

► A valid cost function is the likelihood p(z|Z^k−1, Θ^k−1).

► Written out, the likelihood of the ith measurement:

► depends on the covariance matrix R_i of the ith measurement.

► Taking the negative logarithm of the likelihood and dropping the normalizing constant terms and 1/2 scale factor one has a Mahalanobis distance:

► From the mathematics section, we know that Mahalanobis distances can be used for chi-squared testing to determine whether measurements can even be considered valid.

► For multiple targets, one is tempted to assign the highest likelihood measurement to each target.

► In the above scenario, both targets would be assigned to measurement m₁.

► Naïve nearest neighbor leads to track coalescence and ultimately, needless track loss.

► A practical algorithm must assign measurements jointly across targets, accounting for missed detections.

► Naïve nearest neighbor is one of the options in singleScanUpdate in the TCL.

► We want to derive a cost function (a score function) that can be used for multiple target assignment.

► The exponential of the score function derived in the unabridged slides here is computed in makeStandardLRMatHyps and makeStandardCartOnlyLRMatHyps in the TCL.

► Under many standard assumptions, the marginal change in the log-likelihood for assigning a measurement is

► The term ΔΛ_t,i is the marginal score function for single-frame assignment.

► Summing the marginals for a full target-measurement assignment, one forms the full score function Λ(θ) for a scan.

► When using a converted measurement filter, the units of are in Cartesian coordinates, but the units of λ are usually in the radar’s local coordinates.

► The proper conversion of λ to Cartesian coordinates yields a different λ at every point.

► The Cartesian version of λ given λ in the measurement coordinate system is

► In the TCL, necessary Jacobians are in “Coordinate Systems/Jacobians/Converted Jacobians” and include calcRuvConvJacob and calcPolarConvJacob, among others.

► One could assign measurements to targets and false alarms by choosing the assignment θ that maximizes the score function.

► How many valid assignments are there for m measurement and N_T targets?

► Suppose there are 3000 measurements and targets, and no false alarms or missed detections.

► There are 3000! ≈ 4.14 × 10⁹¹³⁰ hypotheses, but only 3000² = 9 × 10⁶ marginal hypotheses (values of ΔΛ_t,i).

► The efficient solution is formulated as a GNN assignment (2D assignment) problem:

► N_R = N_T and N_C = N_T + m, number of measurements plus missed detection hypotheses.

► Each target gets its own missed detection hypotheses; costs for other targets’ hypotheses are −∞.

► To use the algorithm note that the cost matrix takes the form

► 2D assignment is a binary integer programming problem.

► A polynomial time solution is implemented as assign2D and kBest2DAssign in the TCL

► The GNN algorithm is a maximum-likelihood approach.

► An alternative is to use the expected value over all possible target-measurement assignments.

► For a single target, the expected value and the covariance of the estimate are called probabilistic data association (PDA).

► For multiple targets, it is called Joint Probabilistic Data Association (JPDA).

► Variants of the PDA and JPDA are implemented in singleScanUpdate in the TCL.

► For the tth target, the JPDA update is

► The literature often uses a simpler expression for that is not quadratic in form and subject to finite precision errors.

► Assumptions going into the PDA/JPDA are that the prior distributions on all targets are Gaussian.

► The covariance cross terms between targets are not zero, but are omitted.

► The hardest part of the PDA/JPDA is the computation of the β values.

► Gating and clustering are important parts of a large-scale JPDA implementation.

► In the above figure, measurements are said to gate with a target if in the ellipse overlaps them.

► There are three clusters of targets and measurements.

► Brute-force gating and likelihood evaluation is implemented in the TCL via the makeStandardLRMatHyps and makeStandardCartOnlyLRMatHyps functions.

► Clustering can be computationally efficiently performed using disjoint sets, an obscure Computer Science data structure.

► Disjoint sets for clustering are implemented in the DisjointSetM and DisjointSet classes in the TCL; DisjointSet keeps track of only targets in clusters; DisjointSetM keeps track of targets and measurements in clusters.

► An illustration go how separate clusters can be processed independently.

► G_g is the set of targets and measurements in the gth cluster.

► When the β terms must be computed exactly, two approaches shall be considered:

► The matrix permanent approach is faster, but brute force is necessary to derive some JPDAF variants.

► Consider a matrix of likelihoods with non-normalized assignment probabilities:

► The normalized expression for the β terms can be rewritten directly in terms of likelihoods using elements of C:

► The expression simplifies to

where C̄_j,k is the matrix C after removing row j and column k.

► The matrix permanent cannot be evaluated in polynomial time unless P=NP.

► Efficient exponential complexity algorithms exist. In the TCL, the function perm implements an efficient algorithm.

► Functions to explicitly compute the β values are implemented in the calc2DAssignmentProbs function in the TCL.

► Many techniques to approximate β values exist and are implemented in calc2DAssignmentProbsApprox in the TCL.

► Methods to do the complete PDA and JPDA update are given in singleScanUpdate in the TCL.

► However, one usually uses a variant of the JPDA algorithm rather than the JPDA algorithm itself.

► Consider two targets whose states consist only of scalar position and have been stacked.

► Suppose that the joint PDF for the two targets is

► One target is located at +1 and one target is located at −1, but we do not know which.

► E{x} = 0, where no target is located.

► Coalescence is not a “bias”.

► Coalescence is the result of using the expected value given uncertain identity.

► The Set JPDAF, the GNN-JPDA and the JPDA* can reduce coalescence.

► The GNN-JPDA is simple:

► The hard assignment avoids coalescence.

► Computing P_k|k as a MSE matrix improves covariance consistency/reduces track loss.

► Available as an option in singleScanUpdate in the TCL with exact and approximate βs.

► The brute-force computation of the βs had loops:

► The JPDA* is the same as the JPDA except in the innermost loop, only the maximum likelihood permutation is used.

► Use calcStarBetasBF for the βs in the TCL. Available as an option in singleScanUpdate in the TCL.

► A 2D example of the JPDA* including gating and clustering is given in demo2DDataAssociation in “Sample Code/Basic Tracking Example” in the TCL.

► A sample run is shown above. Tracks were started from two cued measurements.

► Estimated tracks: Red. True track: Dashed black. Detections: Blue. Very resistant to false alarms.

► The GNN and JPDA algorithms only update established tracks.

► Most practical systems require the ability to start and terminate tracks.

► Two main categories of algorithms exist for single-scan data association approaches:

► Multiple Types of cascaded logic trackers exist.

► There are confirmed tracks and candidate tracks.

► Scores usually updated via GNN assignments.

► Measurements not in GNN assignments go on to the next stage.

► Creation, promotion and deletion of tracks in purple-outlined boxes.

► Integrated trackers maintain a probability of target existence with each possible target.

► Usually, a track is not considered firm until its existence probability exceeds a threshold.

► A track is not terminated until its existence probability goes below a lower threshold.

► Measurement update implemented in the singleScanUpdateWithExistence function in the TCL.

► A rigorous derivation of the JIPDA class of filters is usually done using finite set statistics.

► A proper coverage of finite set statistics is beyond the scope of this presentation.

► An example of a minimal end-to-end GNN-JIPDAF in 2D is given in demo2DIntegratedDataAssociation in “Sample Code/Basic Tracking Examples” in the TCL.

► A plot of a run of the sample code with the detections and found tracks (green) and true tracks (red) is shown above for the simple two-target scenario.

► Gaussian approximations and Poisson clutter are widely used.

► Tracking algorithms need consistent measurement covariance matrices. Cross terms between range and range rate can matter.

► The Kalman filter comes from a Bayesian update of a linear dynamic model and a linear measurement.

► The EKF and CKF use Taylor series and cubature approximations to solve difficult integrals in an approximate nonlinear Kalman filter.

► Approaches to measurement conversion with consistent covariances include using Taylor series and cubature approximations to solve difficult integrals.

► The GNN filter is a maximum likelihood filter for data association.

► The JPDA is an MMSE (expected value) filter for data association.

► One typically uses a variant of the JPDA, because the expected value is undesirable given target identity uncertainty.

► Cascaded logic and integrated additions to GNN and JPDA filter variants allow for track initiation and termination.

► Lots of free, commented Matlab code for tracking can be found at https://github.com/USNavalResearchLaboratory/TrackerComponentLibrary which is also http://www.trackercomponentlibrary.com