Dynamically adaptable m-best 2-D assignment algorithm andmultilevel parallelization

In recent years, there has been considerable interest within the tracking community in an approach to data association based on the m-best two-dimensional (2D) assignment algorithm. Much of the interest has been spurred by its ability to provide various efficient data association solutions, including joint probabilistic data association (JPDA) and multiple hypothesis tracking (MHT). The focus of this work is to describe several recent improvements to the m-best 2D assignment algorithm. One improvement is to utilize a nonintrusive 2D assignment algorithm switching mechanism, based on a problem sparsity threshold. Dynamic switching between two different 2D assignment algorithms, highly suited for sparse and dense problems, respectively, enables more efficient solutions to the numerous 2D assignment problems generated in the m-best 2D assignment framework. Another improvement is to utilize a multilevel parallelization enabling many independent and highly parallelizable tasks to be executed concurrently, including 1) solving the multiple 2D assignment problems via a parallelization of the m-best partitioning task, and 2) calculating the numerous gating tests, state estimates, covariance calculations, and likelihood function evaluations (used as cost coefficients in the 2D assignment problem) via a parallelization of the data association interface task. Using both simulated data and an air traffic surveillance (ATS) problem based on data from two Federal Aviation Administration (FAA) air traffic control radars, we demonstrate that efficient solutions to the data association problem are obtainable using our improvements in the m-best 2D assignment algorithm     

IMM estimator versus optimal estimator for hybrid systems

The special feature of the interacting multiple model (TMM) estimator that distinguishes it from other suboptimal multiple model (MM) estimators is the "mixing/interaction" between its "mode-matched" base state filtering modules at the beginning of each cycle. This note shows that the same feature is exactly what it has in common with the optimal estimator for hybrid (MM) systems and this can be seen as the main reason for its success.     

Track labeling and PHD filter for multitarget tracking

Multiple target tracking requires data association that operates in conjunction with filtering. When multiple targets are closely spaced, the conventional approaches (as, e.g., MHT/assignment) may not give satisfactory results. This is mainly because of the difficulty in deciding what the number of targets is. Recently, the probability hypothesis density (PHD) filter has been proposed and particle filtering techniques have been developed to implement the PHD filter. In the particle PHD filter, the track labeling problem is not considered, i.e., the PHD is obtained only for a frame at a time, and it is very difficult to perform the multipeak extraction, particularly in high clutter environments. A track labeling method combined with the PHD approach, as well as considering the finite resolution, is proposed here for multitarget tracking, i.e., we keep a separate tracker for each target, use the PHD in the resolution cell to get the estimated number and locations of the targets at each time step, and then perform the track labeling ("peak-to-track" association), whose results can provide information for PHD peak extraction at the next time step. Besides, by keeping a separate tracker for each target, our approach provides more information than the standard particle PHD filter. For example, in group target tracking, if we are interested in the motion of a specific target, we can track this target, which is not possible for the standard particle PHD filter, since the standard particle PHD filter does not keep track labels. Using our approach, multitarget tracking can be performed with automatic track initiation, maintenance, spawning, merging, and termination     

Precision large scale air traffic surveillance using IMM/assignmentestimators

We present the development and implementation of a multisensor-multitarget tracking algorithm for large scale air traffic surveillance based on interacting multiple model (IMM) state estimation combined with a 2-dimensional assignment for data association. The algorithm can be used to track a large number of targets from measurements obtained with a large number of radars. The use of the algorithm is illustrated on measurements obtained from 5 FAA radars, which are asynchronous, heterogeneous, and geographically distributed over a large area. Both secondary radar data (beacon returns from cooperative targets) as well as primary radar data (skin returns from noncooperative targets) are used. The target IDs from the beacon returns are not used in the data association. The surveillance region includes about 800 targets that exhibit different types of motion. The performance of an IMM estimator with linear motion models is compared with that of the Kalman filter (KF). A number of performance measures that can be used on real data without knowledge of the ground truth are presented for this purpose. It is shown that the IMM estimator performs better than the KF. The advantage of fusing multisensor data is quantified. It is also shown that the computational requirements in the multisensor case are lower than in single sensor case, Finally, an IMM estimator with a nonlinear motion model (coordinated turn) is shown to further improve the performance during the maneuvering periods over the IMM with linear models     

Tracking considerations in selection of radar waveform for rangeand range-rate measurements

The conventional approach for tracking system design is to treat the detection and tracking subsystems as completely independent units. However, the two subsystems can be designed jointly to improve system (tracking) performance. It is known that different radar signal waveforms result in very different resolution cell shapes (for example, a rectangle versus an eccentric parallelogram) in the range/range-rate space, and that there are corresponding differences in overall tracking performance. We develop a framework for the analysis of this performance. An imperfect detection process, false alarms, target dynamics, and the matched filter sampling grid are all accounted for, using the Markov chain approach of Li and Bar-Shalom. The role of the grid is stressed, and it is seen that the measurement-extraction process from contiguous radar "hits" is very important. A number of conclusions are given, perhaps the most interesting of which is the corroboration in the new measurement space of Fitzgerald's result for delay-only (i.e., range) measurements, that a linear FM upsweep offers very good tracking performance     

On joint track initiation and parameter estimation under measurement origin uncertainty

The problem of joint detection and estimation for track initiation under measurement origin uncertainty is studied. The two well-known approaches, namely the maximum likelihood estimator with probabilistic data association (ML-PDA) and the multiple hypotheses tracking (MHT) via multiframe assignment, are characterized as special cases of the generalized likelihood ratio test (GLRT) and their performance limits indicated. A new detection scheme based on the optimal gating is proposed and the associated parameter estimation scheme modified within the ML-PDA framework. A simplified example shows the effectiveness of the new algorithm in detection performance under heavy clutter. Extension of the results to state estimation with measurement origin uncertainty is also discussed with emphasis on joint detection and recursive state estimation.     

Explicit Expressions for the Bias and Variance of the ML Estimated Gumbel Distribution Parameters

Explicit expressions are derived for the bias and the variance of the maximum likelihood (ML) estimator of the Gumbel distribution.     

Estimation near "Zero Information" points: angle-of-arrival near the endfire

We examine large-sample properties of the maximum- likelihood estimator (MLE) in the vicinity of points where the Fisher information measure (FIM) equals zero. Under mild regularity conditions the MLE is asymptotically efficient and therefore lower bounded by the Cramer-Rao lower bound (CRLB) [5], which diverges for such points. When a linear sensor array is used for angle-of-arrival (AOA) estimation, the CRLB diverges as the AOA approaches pi/2. We provide new results characterizing the MLE performance in the AOA problem.     

Multiassignment for tracking a large number of overlapping objects[and application to fibroblast cells]

In this paper we present a new technique for data association using multiassignment for tracking a large number of closely spaced (and overlapping) objects. The algorithm is illustrated on a biomedical problem, namely the tracking of a group of fibroblast (tissue) cells from an image sequence, which motivated this work. Because of their proximity to one another and due to the difficulties in segmenting the images accurately from a poor-quality image sequence, the cells are effectively closely spaced objects (CSOs). The algorithm presents a novel dichotomous, iterated approach to multiassignment using successive one-to-one assignments of decreasing size with modified costs. The cost functions, which are adjusted depending on the “depth” of the current assignment level and on the tracking results, are derived. The resulting assignments are used to form, maintain and terminate tracks with a modified version of the probabilistic data association (PDA) filter, which can handle the contention for a single measurement among multiple tracks in addition to the association of multiple measurements to a single track. Estimation results are given and compared with those of the standard 2D one-to-one assignment algorithm. It is shown that iterated multiassignment results in superior measurement-to-track association. The algorithms presented can be used for other general tracking problems, including dense air traffic surveillance and control     

New assignment-based data association for tracking move-stop-move targets

We present a new assignment-based algorithm for data association in tracking ground targets employing evasive move-stop-move maneuvers using ground moving target indicator (GMTI) reports obtained from an airborne sensor. To avoid detection by the GMTI sensor, the targets deliberately stop for some time before moving again. The sensor does not detect a target when the latter's radial velocity (along the line-of-sight from the sensor) falls below a certain minimum detectable velocity (MDV). Even in the absence of move-stop-move maneuvers, the detection has a less-than-unity probability (P/sub D/<1) due to obscuration and thresholding. Then, it is of interest, when a target is not detected, to develop a systematic technique that can distinguish between lack of detection due to P/sub D/<1 and lack of detection due to a stop (or a near stop). Previously, this problem was solved using a variable structure interacting multiple model (VS-IMM) estimator with a stopped target model (VS-IMM-ST) without explicitly addressing data association. We develop a novel "two-dummy" assignment approach for move-stop-move targets that considers both the problem of data association as well as filtering. Typically, in assignment-based data association a "dummy" measurement is used to denote the nondetection event. The use of the standard single-dummy assignment, which does not handle move-stop-move motion explicitly, can result in broken tracks. The new algorithm proposed here handles the evasive move-stop-move motion by introducing a second dummy measurement to represent nondetection due to the MDV. We also present a likelihood-ratio-based track deletion scheme for move-stop-move targets. Using this two-dummy data association algorithm, the track corresponding to a move-stop-move target is kept "alive' during missed detections both due to MDV and due to P/sub D/<1. In addition, one can obtain reductions in both rms estimation errors as well as the total number of track breakages.