Tracking of Spawning Targets with Multiple Finite Resolution Sensors

In this paper the problem of tracking multiple spawning targets with multiple finite-resolution sensors is considered and a new algorithm for measurement-to-track association with possibly unresolved measurements is presented. The goal is to initialize new tracks of spawned targets before they are resolved from the mother platform so that one has the ability to carry out early discrimination when they become resolved. The multiple scan data association problem is first formulated as a multidimensional assignment problem with explicit new constraints for the unresolved measurements. Then the top M hypotheses tracking (TMHT) is presented where the state estimates and their covariances are modified based on the M best hypotheses through the assignment solutions. A modification to the assignment problem is developed that leads to a linear programming (LP) where the optimal solution can be a noninteger in [0,1]. The fractional optimal solution is interpreted as (pseudo) probabilities over the N - 1 frame sliding window. The best hard (binary) decision assignment solution and the M best via TMHT are compared with the soft decision solution for 2-D tracking scenarios with various sensor configurations. Based on the simulation results, the soft assignment approach has better track maintenance capability than the single best hard assignment and a performance nearly as good as the TMHT. Its computational load is slightly higher than the single best hard assignment but much lighter than TMHT.     

Efficient multisensor fusion using multidimensional dataassociation

We present the development of a multisensor fusion algorithm using multidimensional data association for multitarget tracking. The work is motivated by a large scale surveillance problem, where observations from multiple asynchronous sensors with time-varying sampling intervals (electronically scanned array (ESA) radars) are used for centralized fusion. The combination of multisensor fusion with multidimensional assignment is done so as to maximize the “time-depth” in addition to “sensor-width” for the number S of lists handled by the assignment algorithm. The standard procedure, which associates measurements from the most recently arrived S-1 frames to established tracks, can have, in the case of S sensors, a time-depth of zero. A new technique, which guarantees maximum effectiveness for an S-dimensional data association (S⩾3), i.e., maximum time-depth (S-1) for each sensor without sacrificing the fusion across sensors, is presented. Using a sliding window technique (of length S), the estimates are updated after each frame of measurements. The algorithm provides a systematic approach to automatic track formation, maintenance, and termination for multitarget tracking using multisensor fusion with multidimensional assignment for data association. Estimation results are presented for simulated data for a large scale air-to-ground target tracking problem     

Evaluation of multiple radar target trackers in stressfulenvironments

This paper evaluates the performance of multiple target tracking (MTT) algorithms in real-life stressful radar tracking environments. Real closely spaced maneuver radar data, generated by six F-18 fighters and other targets, were collected jointly by the defence departments of Canada and United States to support this practical MTT algorithm evaluation study. A set of performance metrics was defined here to compare the suboptimal nearest neighbor (SNN), global nearest neighbor (GNN), and various variants of the joint probabilistic data association (JPDA) MTT trackers. Results reveal an interesting result that all these MTT algorithms exhibited very close performance. In addition, the weighted sum approach of the PDA/JPDA trackers which are theoretically effective were observed to perform poorly in tracking closely spaced targets. Overall speaking, the GNN filter based on the Munkres algorithm had the best performance in terms of both tracking performance and robustness     

Multi-Target Tracking in Clutter without Measurement Assignment

When tracking targets using radars and sonars, the number of targets and the origin of data is uncertain. Data may be false measurements or clutter, or they may be detections from an unknown number of targets whose possible trajectories and detection processes can only be described in a statistical manner. Optimal all-neighbor multi-target tracking (MTT) in clutter enumerates all possible joint measurement-to-track assignments and calculates the a posteriori probabilities of each of these joint assignments. The numerical complexity of this process is combinatorial in the number of tracks and the number of measurements. One of the key differences between most MTT algorithms is the manner in which they reduce the computational complexity of the joint measurement-to-track assignment process. We propose an alternative approach, using a form of soft assignment, that enables us to bypass this step entirely. Specifically, our approach treats possible detections of targets followed by other tracks as additional clutter measurements. It starts by approximating the a~priori probabilities of measurement origin. These probabilities are then used to modify the clutter spatial density at the location of the measurements. A suitable single target tracking (STT) filter then uses the modified clutter intensity for updating the track state. In effect, the STT filter is transformed into an MTT filter with a numerical complexity that is linear in the number of tracks and the number of measurements. Simulations show the effectiveness of this approach in a number of different multi-target scenarios.     

A sequential detection approach to target tracking

Sequential hypothesis testing is investigated for multiframe detection and tracking of low-observable maneuvering point-source targets in a digital image sequence. The proposed multiple multistage hypothesis test tracking (MMHTT) algorithm extends tracks formed from sequentially detected target trajectory segments using a multiple hypothesis tracking strategy. The MMHTT algorithm does not require a probabilistic larger maneuver model. Computational efficiency is achieved by using a truncated sequential probability ratio test (SPRT) to prune a dense tree of candidate target trajectories and score the detected trajectory segments. An analytical performance evaluation is presented and confirmed by experimental results from an optical satellite tracking application     

A formulation of multitarget tracking as an incomplete data problem

Traditional multihypothesis tracking methods rely upon an enumeration of all the assignments of measurements to tracks. Pruning and gating are used to retain only the most likely hypotheses in order to drastically limit the set of feasible associations. The main risk is to eliminate correct measurement sequences. The probabilistic multiple hypothesis tracking (PMHT) method has been developed by Streit and Luginbuhl in order to reduce the drawbacks of "strong" assignments. The PMHT method is presented in a general mixture densities perspective. The Expectation-Maximization (EM) algorithm is the basic ingredient for estimating mixture parameters. This approach is then extended and applied to multitarget tracking for nonlinear measurement models in the passive sonar perspective.     

Track segment association, fine-step IMM and initialization with Doppler for improved track performance

In this work we present a new track segment association technique to improve track continuity in large-scale target tracking problems where track breakages are common. A representative airborne early warning (AEW) system scenario, which is a challenging environment due to highly maneuvering targets, close target formations, large measurement errors, long sampling intervals, and low detection probabilities, provides the motivation for the new technique. Previously, a tracker using the interacting multiple model (IMM) estimator combined with an assignment algorithm was shown to be more reliable than a conventional Kalman filter based approach in tracking similar targets but it still yielded track breakages due to the difficult environment. In order to combine the broken track segments and improve track continuity, a new track segment association algorithm using a discrete optimization approach is presented. Simulation results show that track segment association yields significant improvements in mean track life as well as in position, speed, and course rms errors. Also presented is a modified one-point initialization technique with range rate measurements, which are typically ignored by other initialization techniques, and a fine-step IMM estimator, which improves performance in the presence of long revisit intervals. Another aspect that is investigated is the benefit of "deep" (multiframe or N-dimensional, with N > 2) association, which is shown to yield significant benefit in reducing the number of false tracks.     

Tracker and signal processing for the benchmark problem with unresolved targets

Radar signal processing is particularly important in tracking closely spaced targets and targets in the presence of sea-surface-induced multipath. Closely spaced targets can produce unresolved measurements when they occupy the same range cell of the radar. These issues are the salient features of the benchmark problem for tracking unresolved targets combined with radar management, for which this paper presents the only complete solution to date. In this paper a modified version of a recently developed maximum likelihood (ML) angle estimator, which can produce two measurements from a single (unresolved) detection, is presented. A modified generalized likelihood ratio test (GLRT) is also described to detect the presence of two unresolved targets. Sea-surface-induced multipath can produce a severe bias in the elevation angle measurement when the conventional monopulse ratio angle extractor method is used. A modified version of a recently developed ML angle extractor, which produces nearly unbiased elevation angle measurements and significantly improves the track accuracy, is presented. Efficient radar resource allocation algorithms for two closely spaced targets and targets flying close to the sea surface are also presented. Finally, the IMMPDAF (interacting multiple model estimator with probabilistic data association filter modules) is used to track these targets. It is found that a two-model IMMPDAF performs better than the three-model version used in the previous benchmark. Also, the IMMPDAF with a coordinated turn model works better than the one using a Wiener process acceleration model. The signal processing and tracking algorithms presented here, operating in a feedback manner, form a comprehensive solution to the most realistic tracking and radar management problem to date.     

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     

Multiple hypothesis track maintenance with possibly unresolved measurements

In surveillance problems dense clutter/dense target situations call for refined data association and tracking techniques. In addition, closely spaced targets may exist which are not resolved. This phenomenon has to be considered explicitly in the tracking algorithm. We concentrate on two targets which temporarily move in close formation and derive a generalization of MHT methods on the basis of a simple resolution model.     

一种红外多传感器对中段弹道空间邻近目标的联合超分辨弹道估计方法

 分析红外焦平面(IR FRA)对中段弹道空间邻近目标(CSO)的成像特点,指出星载红外传感器为实现对空间邻近目标的跟踪必须对其进行超分辨。提出了一种中段弹道空间邻近目标联合超分辨与弹道估计新方法。该方法结合红外焦平面成像模型和中段弹道动力学模型,使得能够同时利用红外多传感器的多帧信息,基于最小二乘准则建立联合超分辨弹道估计目标函数,并分析选择各目标的起始状态参数作为模型参数。针对目标函数的高维非线性特点,推导最小化意义下等价的降维目标函数,采用量子粒子群优化算法最优化该降维目标函数直接求解模型参数,进而计算出各目标的弹道和辐射强度,实现中段弹道空间邻近目标的联合超分辨与弹道估计。仿真结果验证了该方法的有效性,且相比于传统的先单传感器单帧超分辨、然后多传感器多帧测角数据关联与滤波方法,新方法在避免数据关联复杂问题的同时,其弹道估计精度更高、分辨能力更强。     

Tracking multiple objects with particle filtering

We address the problem of multitarget tracking (MTT) encountered in many situations in signal or image processing. We consider stochastic dynamic systems detected by observation processes. The difficulty lies in the fact that the estimation of the states requires the assignment of the observations to the multiple targets. We propose an extension of the classical particle filter where the stochastic vector of assignment is estimated by a Gibbs sampler. This algorithm is used to estimate the trajectories of multiple targets from their noisy bearings, thus showing its ability to solve the data association problem. Moreover this algorithm is easily extended to multireceiver observations where the receivers can produce measurements of various nature with different frequencies.     

Multi-Target/Multi-Sensor Tracking using Only Range and Doppler Measurements

A new approach is described for combining range and Doppler data from multiple radar platforms to perform multi-target detection and tracking. In particular, azimuthal measurements are assumed to be either coarse or unavailable, so that multiple sensors are required to triangulate target tracks using range and Doppler measurements only. Increasing the number of sensors can cause data association by conventional means to become impractical due to combinatorial complexity, i.e., an exponential increase in the number of mappings between signatures and target models. When the azimuthal resolution is coarse, this problem will be exacerbated by the resulting overlap between signatures from multiple targets and clutter. In the new approach, the data association is performed probabilistically, using a variation of expectation-maximization (EM). Combinatorial complexity is avoided by performing an efficient optimization in the space of all target tracks and mappings between tracks and data. The full, multi-sensor, version of the algorithm is tested on simulated data. The results demonstrate that accurate tracks can be estimated by exploiting spatial diversity in the sensor locations. Also, as a proof-of-concept, a simplified, single-sensor range-only version of the algorithm is tested on experimental radar data acquired with a stretch radar receiver. These results are promising, and demonstrate robustness in the presence of nonhomogeneous clutter.     

Tracking with classification-aided multiframe data association

In most conventional tracking systems, only the target kinematic information from, for example, a radar or sonar or an electro-optical sensor, is used in measurement-to-track association. Target class information, which is typically used in postprocessing, can also be used to improve data association to give better tracking accuracy. The use of target class information in data association can improve discrimination by yielding purer tracks and preserving their continuity. In this paper, we present the simultaneous use of target classification information and target kinematic information for target tracking. The approach presented integrates target class information into the data association process using the 2-D (one track list and one measurement list) as well as multiframe (one track list and multiple measurement lists) assignments. The multiframe association likelihood is developed to include the classification results based on the "confusion matrix" that specifies the accuracy of the target classifier. The objective is to improve association results using class information when the kinematic likelihoods are similar for different targets, i.e., there is ambiguity in using kinematic information alone. Performance comparisons with and without the use of class information in data association are presented on a ground target tracking problem. Simulation results quantify the benefits of classification-aided data association for improved target tracking, especially in the presence of association uncertainty in the kinematic measurements. Also, the benefit of 5-D (or multiframe) association versus 2-D association is investigated for different quality classifiers. The main contribution of this paper is the development of the methodology to incorporate exactly the classification information into multidimensional (multiframe) association.     

Track monitoring when tracking with multiple 2D passive sensors

A fast method of track monitoring is presented which determines what tracks are good and what tracks have had data association problems and should be eliminated. The philosophy of tracking in a dense target environment with limited central processing unit (CPU) time is to acquire the targets, track them with as simple a filter as will meet requirements, and monitor the tracks to determine if they are still tracking a target or are tracking incorrect returns and should be terminated. After termination the true targets are reacquired. However, it is difficult to determine from simple track monitoring the correct interpretation of a poor track. Poor tracks can be a result of a sensor failure, target maneuver, or incorrect data association. The author describes track monitoring and provides a solution to this dilemma when tracking with multiple two-dimensional passive sensors. The method is much faster than other monitoring methods.<>     

Loopy belief propagation based data association for extended target tracking

The data association problem of multiple extended target tracking is very challenging because each target may generate multiple measurements. Recently, the belief propagation based multiple target tracking algorithms with high efficiency have been a research focus. Different from the belief propagation based Extended Target tracking based on Belief Propagation (ET-BP) algorithm proposed in our previous work, a new graphical model formulation of data association for multiple extended target tracking is proposed in this paper. The proposed formulation can be solved by the Loopy Belief Propagation (LBP) algorithm. Furthermore, the simplified measurement set in the ET-BP algorithm is modified to improve tracking accuracy. Finally, experiment results show that the proposed algorithm has better performance than the ET-BP and joint probabilistic data association based on the simplified measurement set algorithms in terms of accuracy and efficiency. Additionally, the convergence of the proposed algorithm is verified in the simulations.     

Tracking in Clutter using IMM-IPDA?Based Algorithms

We describe three single-scan probabilistic data association (PDA) based algorithms for tracking manoeuvering targets in clutter. These algorithms are derived by integrating the interacting multiple model (IMM) estimation algorithm with the PDA approximation. Each IMM model a posteriori state estimate probability density function (pdf) is approximated by a single Gaussian pdf. Each algorithm recursively updates the probability of target existence, in the manner of integrated PDA (IPDA). The probability of target existence is a track quality measure, which can be used for false track discrimination. The first algorithm presented, IMM-IPDA, is a single target tracking algorithm. Two multitarget tracking algorithms are also presented. The IMM-JIPDA algorithm calculates a posteriori probabilities of all measurement to track allocations, in the manner of the joint IPDA (JIPDA). The number of measurement to track allocations grows exponentially with the number of shared measurements and the number of tracks which share the measurements. Therefore, IMM-JIPDA can only be used in situations with a small number of crossing targets and low clutter measurement density. The linear multitarget IMM-IPDA (IMM-LMIPDA) is also a multitarget tracking algorithm, which achieves the multitarget capabilities by integrating linear multitarget (LM) method with IMM-IPDA. When updating one track using the LM method, the other tracks modulate the clutter measurement density and are subsequently ignored. In this fashion, LM achieves multitarget capabilities using the number of operations which are linear in the: number of measurements and the number of tracks, and can be used in complex scenarios, with dense clutter and a large number of targets.     

Joint integrated probabilistic data association: JIPDA

A new recursive filter for multi-target tracking in clutter is presented. Multiple tracks may share the same measurement(s). Joint events are formed by creating all possible combinations of track-measurement assignments and the probabilities for these joint events are calculated. The expressions for the joint event probabilities incorporate the probabilities of target existence of individual tracks, an efficient approximation for the cluster volume and a priori probability of the number of clutter measurements in each cluster. From these probabilities the data association and target existence probabilities of individual tracks are obtained, which allows track state update and false track discrimination. A simulation study is presented to show the effectiveness of this approach.     

Data association for deghosting in Y-shaped passive linear array sonars

This paper deals with data association using three sets of passive linear array sonars (PLAS) geometrically positioned in a Y-shaped configuration, fixed in an underwater environment. The data association problem is directly transformed into a 3D assignment, which is known to be NP hard. For generic passive sensors, it can be solved using conventional algorithms, while in PLAS, it becomes a formidable task due to the presence of bearing ambiguity. Thus, the central issue of the problem in PLAS is how to eliminate the bearing ambiguity without increasing tracking error. To solve this problem, the 3D assignment algorithm used the likelihood value of only those observed bearing measurements is modified by incorporating frequency information in consecutive time-aligned scans. The region of possible ghost targets is first established by the geometrical relation of PLAS with respect to target. The ghost targets are then confirmed and eliminated by generating multiple observations in consecutive scans. Representative simulations demonstrate the effectiveness of the proposed approach.     

An interior point linear programming approach to two-scan dataassociation

We present an efficient two-scan data association method (TSDA) based on an interior point linear programming (LP) approach. In this approach, the TSDA problem is first formulated as a 3-dimensional assignment problem, and then relaxed to a linear program; the latter is subsequently solved by the highly efficient homogeneous, self-dual interior point LP algorithm. When the LP algorithm generates a fractional optimal solution, we use a technique similar to the joint probabilistic data association method (JPDA) to compute a weighted average of the resulting fractional assignments, and use it to update the states of the existing tracks generated by Kalman filters. Unlike the traditional single scan JPDA method, our TSDA method provides an explicit mechanism for track initiation. Extensive computer simulations have demonstrated that the new TSDA method is not only far more efficient in terms of low computational complexity, but also considerably more accurate than the existing single-scan JPDA method