Different Impressions Obtained from the Literature: ► 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.
Target Tracking Is: ► 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.
Target Tracking Is: ► 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.
The difficulty and utility of target tracking methods depend on the application. ► 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
Useful Mathematical Tools 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:
1. The Multivariate Gaussian Distribution.
2. The Central Chi-Square Distribution. 3. The Binomial Distribution. 4. The Poisson Distribution.
► 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 χ2(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 dx, the dimensionality of x.
| Confidence Region p |
---|
dx | 0.9 | 0.99 | 0.999 | 0.9999 | 0.99999 |
---|
1 | 2.7055 | 6.6349 | 10.8276 | 15.1367 | 19.5114 | 2 | 4.6052 | 9.2103 | 13.8155 | 18.4207 | 23.0259 | 3 | 6.2514 | 11.3449 | 16.2662 | 21.1075 | 25.9017 | 6 | 10.6446 | 16.8119 | 22.4577 | 27.8563 | 33.1071 | 9 | 14.6837 | 21.6660 | 27.8772 | 33.7199 | 39.3407 |
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 Ndx degrees of freedom. ► The function calcNEES in the TCL can be useful.
► Consider constant false alarm rate (CFAR) detector with a given PFA 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.
with mean
► The binomial distribution is almost never used in trackers. ► It is approximated by a Poisson distribution with the same .
Example: ► 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.”
Numerically integrate the function from 0 to 2. Numerically integrate the function from 0 to 2. ► Riemann sums converge very slowly. ► The idea in quadrature/cubature is the relation
is exact for a particular weighting function w for all polynomials f up to a certain order and approximate for other functions f.
► S is a region, such as ℝn or the surface of a hypersphere. ► Unlike a Riemann sum, N is finite. ► Cubature weights ωi and points xi depend on w and the order.
► 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
► A matrix inequality refers to sorted eigenvalues. ► x is the quantity being estimated. ► T(z) is the best unbiased estimator. ► J is the Fisher information matrix. ► The expectation is taken over the conditional PDF p(z|x) if x is deterministic.
► 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 “prior” subscript will be replaced by “k|k − 1” to indicate that one has an estimate of a current (step k) state given prior (step k − 1) information. ► The “posterior” subscript will be replaced by “k|k” to indicate that one has an estimate of a current state given current information.
► 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:
1. Discretize the entire estimation space 2. Evaluate probabilities on a discrete grid for given distributions 3. Multiply matrices of probabilities to get posterior; normalize
► It is simple. ► With parallelization over GPUs, couldn’t it be done quickly?
► Why the brute-force grid approach is seldom done:
► One target 3D position and velocity in 50 km cube all directions about sensor, speed in any direction to Mach 4 (1372, m/s), discretized to 5m and 1m/s. ► Grid for single probability density function (PDF) is more than 2 × 1022 in size (we need two). ► As floating doubles, one grid requires more than 82 zettabytes of RAM (1 ZB=1 trillion GB). ► 64GB RAM stick ≈ $255 so cost ≈ $330 trillion ($660 trillion for two grids, US GDP ≈ $53 trillion). ► Computing power to multiply two grids in 1 ms is ≈ 20 exaflops. ► Most powerful supercomputer (Tianhe-2, China) 33.85 petaflops. We need 612 of them.
► 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.
Two common approaches to starting the filter are ► 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
but the quantities are now integrals.
► 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.
► 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.4802m2/s3 ► Measurements every T = 0.5 s. ► Tracks initialized via an information filter with 2 converted measurements. ► .
Topics considered are: 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, Pk|k−1 with a 100% detection probability and with NM 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, Pk|k−1. ► Multiple scan data association look at multiple sets of measurements.
► One cannot convert the state to the measurement coordinate system and use a similar l2 norm.
► Valid distance measures can be derived from likelihood functions and likelihood ratios.
► Let Zk−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|Zk−1, Θk−1).
► Written out, the likelihood of the ith measurement:
► depends on the covariance matrix Ri 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 m1. ► 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
► is the predicted measurement from the tth target, ► is the innovation covariance the for ith measurement and tth target.
► 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 NT targets?
► Suppose there are 3000 measurements and targets, and no false alarms or missed detections.
► There are 3000! ≈ 4.14 × 109130 hypotheses, but only 30002 = 9 × 106 marginal hypotheses (values of ΔΛt,i). ► The efficient solution is formulated as a GNN assignment (2D assignment) problem:
► NR = NT and NC = NT + 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
► βi,t is the probability of assigning measurement i to target t (0 is a missed detection). ► Superscripts of i and t indicate measurement and target hypotheses. ► Ip is information on the (assumed Gaussian) prior estimates.
► 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.
1. Target t1 is in a cluster with m4. 2. Targets t2 and t3 (linked by m2) cluster with m1, m2, and m3. 3. Target t4 is in a cluster with m6.
► 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.
► 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.
► 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:
1. Determine the measurement to use with a GNN filter, giving x̂x|x. 2. Compute Pk|k as in the JPDA, using the GNN estimate as the mean x̂k|k.
► The hard assignment avoids coalescence. ► Computing Pk|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:
1. Choose how many targets are observed. 2. Choose which targets are observed. 3. Choose which measurements originated from targets. 4. Permute all associations of observed targets to target-originated measurements.
► 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
|