Suboptimal joint probabilistic data association

A significant problem in multiple target tracking is the hit-to-track data association. A hit is a received signal from a target or background clutter which provides positional information. If an incorrect hit is associated with a track, that track could diverge and terminate. Prior methods for this data association problem include various optimal and suboptimal two-dimensional assignment algorithms which make hit-to-track associations. Another method is to assign a weight for the reasonable hits and use a weighted centroid of those hits to update the track. The method of weighting the hits is known as joint probabilistic data association (JPDA). The authors review the JPDA approach and a simple ad hoc approximation and then introduce a new suboptimal JPDA algorithm. Examples which compare an optimal two-dimensional assignment algorithm with the ad hoc and the new suboptimal JPDA formulation are given     

Multisensor covariance control strategies for reducing bias effects in interacting target scenarios

Algorithms are presented for managing sensor information to reduce the effects of bias when tracking interacting targets. When targets are close enough together that their measurement validation gates overlap, the measurement from one target can be confused with another. Data association algorithms such as the joint probabilistic data association (JPDA) algorithm can effectively continue to track targets under these conditions, but the target estimates may become biased. A modification of the covariance control approach for sensor management can reduce this effect. Sensors are chosen based on their ability to reduce the extent of measurement gate overlap as judged by a set of heuristic parameters derived in this work. Monte Carlo simulation results show that these are effective methods of reducing target estimate bias in the JPDA algorithm when targets are close together. An analysis of the computational demands of these algorithms shows that while they are computationally demanding, they are not prohibitively so.     

密集杂波环境下的数据关联快速算法

基于联合概率数据互联（JPDA）的思想,提出了一种新的数据关联快速算法（Fast Al-gorithm for Data Association,简称FAFDA算法）.该方法不需象在最优JPDA算法中那样生成所有可能的联合互联假设,因而具有计算量小,易于工程实现的特点。仿真结果表明,与最优JPDA算法相比,FAFDA算法的跟踪性能令人满意,并且在密集杂波环境下可实时、有效地跟踪100批次以上的目标。     

Neural solution to the multitarget tracking data associationproblem

The problem of tracking multiple targets in the presence of clutter is addressed. The joint probabilistic data association (JPDA) algorithm has been previously reported to be suitable for this problem in that it makes few assumptions and can handle many targets as long as the clutter density is not very high. However, the complexity of this algorithm increases rapidly with the number of targets and returns. An approximation of the JPDA that uses an analog computational network to solve the data association problem is suggested. The problem is viewed as that of optimizing a suitably chosen energy function. Simple neural-network structures for the approximate minimization of such functions have been proposed by other researchers. The analog network used offers a significant degree of parallelism and thus can compute the association probabilities more rapidly. Computer simulations indicate the ability of the algorithm to track many targets simultaneously in the presence of moderately dense clutter     

Tracking of multiple maneuvering targets using multiscan JPDA and IMM filtering

The paper considers the problem of tracking multiple maneuvering targets in the presence of clutter using switching multiple target motion models. A novel suboptimal filtering algorithm is developed by applying the basic interacting multiple model (IMM) approach and the joint probabilistic data association (JPDA) technique. Unlike the standard single-scan JPDA approach, the authors exploit a multiscan joint probabilistic data association (mscan-JPDA) approach to solve the data association problem. The algorithm is illustrated via a simulation example involving tracking of four maneuvering targets and a multiscan data window of length two     

Multiple scan joint probabilistic data association

This paper presents a multiple scan or n-scan-back joint probabilistic data association (JPDA) algorithm which addresses the problem of measurement-to-track data association in a multiple target and clutter environment. The standard single scan JPDA algorithm updates a track with weighted sum of the measurements which could have reasonably originated from the target in track. The only information the standard JPDA algorithm uses is the measurements on the present scan and the state vectors and covariance matrices of the present targets. The n-scan-back algorithm presented here uses multiple scans of measurements along with the present target information to produce better weights for data association. The standard JPDA algorithm can utilize a formidable amount of processing power and the n-scan-back version only worsens the problem. Therefore, along with the algorithm presentation, implementations which make this algorithm practical are discussed and referenced. An example is also shown for a few n-scan-back window lengths     

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     

修正的概率数据互联算法

阐明了概率数据互联(PDA)算法能很好地解决密集环境下的目标跟踪问题,在该算法基础上,人们又提出了联合概率数据互联(JPDA)算法和一些基于 PDA 的修正算法。在概率数据互联算法中,有一个很重要的参数就是杂波数密度(或波门内虚假量测期望数)。然而在许多实际情况中,这个参数是很难获取的。针对这一问题,文中提出了一种修正的概率数据互联算法,该算法通过实时地调整这一参数来获得对目标较为准确的估计结果。最后,给出了算法的仿真分析。     

STOCHASTIC NEURAL NETWORK AND ITS APPLICATION TO MULTI－MANEUVERING TARGET TRACKING

ＳＴＯＣＨＡＳＴＩＣＮＥＵＲＡＬＮＥＴＷＯＲＫＡＮＤＩＴＳＡＰＰＬＩＣＡＴＩＯＮＴＯＭＵＬＴＩ－ＭＡＮＥＵＶＥＲＩＮＧＴＡＲＧＥＴＴＲＡＣＫＩＮＧＪｉｎｇＺｈｏｎｇｌｉａｎｇ；ＤａｉＧｕａｎｚｈｏｎｇ；ＴｏｎｇＭｉｎｇａｎ；ＺｈｏｕＨｏｎｇｒｅｎ（Ｄ...     

Multiple model PMHT and its application to the benchmark radar tracking problem

The probabilistic multiple hypothesis tracker (PMHT) uses the expectation-maximization (EM) algorithm to solve the measurement-origin uncertainty problem. Here, we explore some of its variants for maneuvering targets and in particular discuss the multiple model PMHT. We apply this PMHT to the six "typical" tracking scenarios given in the second benchmark problem from W. D. Blair and G. A. Watson (1998). The manner in which the PMHT is used to track the targets and to manage radar allocation is discussed, and the results compared with those of the interacting multiple model probabilistic data association filter (IMM/PDAF) and IMM/MHT (multiple hypothesis tracker). The PMHT works well: its performance lies between those of the IMM/PDAF and IMM/MHT both in terms of tracking performance and computational load.     

面向目标的概率多假设跟踪算法

 概率多假设跟踪(PMHT)算法由于其计算量与目标和量测的个数成线性关系而成为一种重要的数据关联方法,但该算法采用的是一种面向量测的参数模型,容易受到杂波的干扰。针对这个问题,提出一种面向目标的PMHT（TO/PMHT）算法,将量测与目标的距离作为权重,使计算出的后验关联概率能够真实地反映量测和目标的关联可能性。通过多种典型环境的仿真计算表明：TO/PMHT算法和面向量测的PMHT算法相比,跟踪性能有了明显的提高;与多假设跟踪(MHT)算法相比,在保持跟踪性能的同时,极大地提高了计算效率。     

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     

空间多分辨率模糊目标跟踪

提出了一种新的模糊目标跟踪算法--CPDA算法。这个算法在空间多分辨率框架下应用概率数据互联算法,在粗分辨率上实现模糊目标跟踪。在不同虚警密度的模糊目标环境下,利用仿真实验分析了CPDA算法的跟踪性能,同时将其与单分辨率上的联合概率数据互联方法进行了性能比较。仿真结果表明,CPDA算法的跟踪性能在达到与单分辨率上JPDA算法同样性能的条件下,能够以较小的计算量跟踪模糊目标。     

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.     

多目标跟踪的概率假设密度粒子滤波

在多目标跟踪中,当目标数很大时,目标状态的联合分布的计算量会非常大。如果目标独立运动,可用各目标分别滤波来代替,但这要求考虑数据互联问题。文章介绍一种可以解决计算量问题的方法,只需计算联合分布的一阶矩——概率假设密度(PHD),PHD在任意区域S上的积分是S内目标数的期望值。因未记录目标身份,避免了数据互联问题。仿真中,传感器为被动雷达,目标观测值为距离、角度及速度时,对上述的PHD滤波进行了粒子实现,并对观测值是否相关的不同情况进行比较。PHD粒子滤波应用在非线性模型的多目标跟踪,实验结果表明,滤波可以稳健跟踪目标数为变数的情况,得到了接近真实情况的结果。     

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     

基于数据关联的故障快速检测

 多数情况下,快速实时地进行故障检测是很重要的。将故障看做是通过多传感器观测的动态模型,进行多传感器多模型概率数据关联,以各个模型的关联结果和设定的阈值为依据,可以有效地实现故障检测。联合概率数据关联（JPDA）算法是解决多传感器多目标跟踪的一个有效方法,文中通过分析概率数据关联算法,对联合概率数据关联算法进行了改进：（1）通过正确地选择阈值,移除小概率事件,进而建立一个近似的确认矩阵;（2）根据被跟踪目标故障跟踪门的相交情况,将跟踪空间进行数学划分,形成若干相互独立的区域;（3）对同一区域内公共有效量测的概率密度值进行衰减,计算出关联概率。仿真对比表明,本文的改进算法能显著减少计算时间,有效提高故障检测的快速性和实时性。     

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     

Joint probabilistic data association for autonomous navigation

A new autonomous navigation scheme based on the joint probabilistic data association (JPDA) approach that processes landmark detections in the field of view (FOV) of an on-board sensor is developed. These detections-some true, some false-are associated to a set of stored landmarks and used to update the state of the vehicle. The results obtained from Monte Carlo simulations prove the ability of this navigation filter to perform in very high false alarm environments. In the different environmental conditions tested in the simulations, the performance of the JPDA navigation filter (JPDANF) is very close to that of the filter based on perfect data association. The very efficient cluster decomposition algorithm presented for the purpose of the navigation problem can also be used in many multitarget tracking applications