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     

基于高斯混合概率假设密度滤波的扫描型光学传感器像平面多目标跟踪算法

高斯混合概率假设密度(GM-PHD)滤波是一种基于随机有限集理论的次优贝叶斯多目标跟踪方法,本文研究了该算法在扫描型光学传感器像平面的多目标跟踪问题.针对典型的锥扫模式和推扫模式,根据其扫描特性建立目标的运动模型和测量模型.介绍高斯混合概率假设密度滤波的基本原理.针对原算法在强杂波环境中的低效率问题,借鉴传统多目标跟踪...     

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     

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

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

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.     

一种基于模糊遗传算法的多传感器多目标跟踪数据关联算法

基于模糊遗传算法发展了一种新的数据关联算法。数据关联的静态部分靠一个模糊遗传算法来得出量测组合序列和S-D分配的m个最优解。在数据关联的动态部分，将得到的S-D分配的m个最优解在一个基于多种群模糊遗传算法的动态2D分配算法中依靠一个卡尔曼滤波估计器估计出移动目标各个时刻的状态。这一基于分配的数据关联算法的仿真试验内容为被动式传感器的航迹形成和维持的问题。仿真试验的结果表明该算法在多传感器多目标跟踪中应用的可行性。另外，对算法发展和实时性问题进行了简单讨论。     

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.     

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     

Evaluating a multiple-hypothesis multitarget tracking algorithm

The performance evaluation of multiple-hypothesis, multitarget tracking algorithm is presented. We are primarily interested in target-detection/track-initiation capabilities as measures of performance. Through Monte Carlo simulations, a multiple-hypothesis tracking algorithm was evaluated in terms of 1) probability of establishing a track from target returns and 2) false track density. A radar was chosen as the sensor, and a general multiple-hypothesis, multitarget tracking algorithm was used in the Monte Carlo simulations. The simulation results predict the probability of establishing a track from returns of a target as well as the false track density per scan volume per unit time. The effects of the target radar cross section and the radar power, measured through the mean signal-to-noise ratio (SNR) were studied, as were the effects of detection threshold and track quality threshold. Computational requirements were also investigated     

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.     

Tracking multitarget in cluttered environment

A method for multitarget tracking and initiating tracking in a cluttered environment is proposed. The algorithm uses a sliding window of length uT (T is the sampling time) to keep the measurement sequence at time k. Instead of solving a large problem, the entire set of targets and measurements is divided into several clusters so that a number of smaller problems are solved independently. When a set of measurements is received, a new set of data-association hypotheses is formed for all the measurements lying in the validation gates within each cluster from time K-u+1 to K. The probability of each track history is computed, and, choosing the largest of these histories, the target measurement is updated with an adaptive state estimator. A covariance-matching technique is used to improve the accuracy of the adaptive state estimator. In several examples, the algorithm successfully tracks targets over a wide range of conditions     

基于改进多元优化算法的动态路径规划

为满足动态路径规划实时性强和动态跟踪精度高的需求,提出一种基于能够同时发现并追踪多条最优以及次优路径的改进多元优化算法(IMOA)的求解方法。首先,通过利用贝赛尔曲线描述路径的方法把动态路径规划问题转化为动态优化问题;然后,把相似性检测操作引入到多元优化算法(MOA)中,增加算法同时跟踪多个不同最优以及次优解的概率;最后,用IMOA对贝赛尔曲线的控制点进行寻优。实验结果表明:当最优路径由于环境变化而变为非优或者不可行时,利用IMOA对多个最优以及次优解动态跟踪的特点,能够快速调整寻优策略对其他次优路径进行寻优以期望再次找到最优路径;其综合离线性能较其他方法也有一定的提高。因此,IMOA满足动态路径规划的实际需求,适用于解决动态环境中的路径规划问题。     

On mapping a tracking algorithm onto parallel processors

The problem of mapping the tasks of a multitarget tracking algorithm onto parallel computing architectures to maximize speedup is considered. An asymptotically optimal mapping algorithm is developed and applied to study the effects of task granularity and processor architectures on the speedup. From the simulation results, it is concluded that task granularity and the parallelization of clustering and global hypotheses formation stages of the tracking algorithm are major determinants of speedup     

Explicit formulas for two state Kalman, H/sub 2/ and H/sub /spl infin// target tracking filters

The continuous time, two state, target tracking problem is considered from the Kalman, H/sub 2/, and H/sub /spl infin// filter viewpoint. While previous treatments were numerical in nature, analytic transient responses and infinite horizon solutions with analytic performance expressions are presented here. Tracking indices, involving the maneuver and measurement uncertainties, are shown to have a role for both the steady state and transient responses. In addition, the H/sub /spl infin// tracker has a sensor index involving the performance bound and measurement uncertainty, which, along with the tracking index, plays a significant role in the H/sub /spl infin// tracker expressions. Analytical expressions for the probability of target escape, the probability that the target position will be outside the radar beamwidth (BW), are developed not only to compare the performance of various trackers, but also as a design tool to meet tracking specifications. Examples illustrate the performance of the target trackers as a function of the error gain upper bound.     

Multitarget Bayes filtering via first-order multitarget moments

The theoretically optimal approach to multisensor-multitarget detection, tracking, and identification is a suitable generalization of the recursive Bayes nonlinear filter. Even in single-target problems, this optimal filter is so computationally challenging that it must usually be approximated. Consequently, multitarget Bayes filtering will never be of practical interest without the development of drastic but principled approximation strategies. In single-target problems, the computationally fastest approximate filtering approach is the constant-gain Kalman filter. This filter propagates a first-order statistical moment - the posterior expectation - in the place of the posterior distribution. The purpose of this paper is to propose an analogous strategy for multitarget systems: propagation of a first-order statistical moment of the multitarget posterior. This moment, the probability hypothesis density (PHD), is the function whose integral in any region of state space is the expected number of targets in that region. We derive recursive Bayes filter equations for the PHD that account for multiple sensors, nonconstant probability of detection, Poisson false alarms, and appearance, spawning, and disappearance of targets. We also show that the PHD is a best-fit approximation of the multitarget posterior in an information-theoretic sense.     

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     

Discrete-time min-max tracking

The problem of optimal state estimation of linear discrete-time systems with measured outputs that are corrupted by additive white noise is addressed. Such estimation is often encountered in problems of target tracking where the target dynamics is driven by finite energy signals, whereas the measurement noise is approximated by white noise. The relevant cost function for such tracking problems is the expected value of the standard H/sub /spl infin// performance index, with respect to the measurement noise statistics. The estimator, serving as a tracking filter, tries to minimize the mean-square estimation error, and the exogenous disturbance, which may represent the target maneuvers, tries to maximize this error while being penalized for its energy. The solution, which is obtained by completing the cost function to squares, is shown to satisfy also the matrix version of the maximum principle. The solution is derived in terms of two coupled Riccati difference equations from which the filter gains are derived. In the case where an infinite penalty is imposed on the energy of the exogenous disturbance, the celebrated discrete-time Kalman filter is recovered. A local iterations scheme which is based on linear matrix inequalities is proposed to solve these equations. An illustrative example is given where the velocity of a maneuvering target has to be estimated utilizing noisy measurements of the target position.     

Interacting multiple model fixed-lag smoothing algorithm forMarkovian switching systems

We investigate a suboptimal approach to the fixed-lag smoothing problem for Markovian switching systems. A fixed-lag smoothing algorithm is developed by applying the basic Interacting Multiple Model (IMM) approach to a state-augmented system. The computational load is roughly d (the fixed lag) times beyond that of filtering for the original system. In addition, an algorithm that approximates the “fixed-lag” mode probabilities given measurements up to current time is proposed. The algorithm is illustrated via a target tracking simulation example where a significant improvement over the filtering algorithm is achieved at the cost of a time delay (i.e., data up to time k are used to produce the smoothed state estimate at time k-d where the fixed large d>0). the IMM fixed-lag smoothing performance for the given example is comparable to that of an existing IMM fixed-interval smoother. Compared with fixed-interval smoothers, the fixed-lag smoothers can be implemented in real-time with a small delay     

Sequential Monte Carlo methods for multitarget filtering with random finite sets

Random finite sets (RFSs) are natural representations of multitarget states and observations that allow multisensor multitarget filtering to fit in the unifying random set framework for data fusion. Although the foundation has been established in the form of finite set statistics (FISST), its relationship to conventional probability is not clear. Furthermore, optimal Bayesian multitarget filtering is not yet practical due to the inherent computational hurdle. Even the probability hypothesis density (PHD) filter, which propagates only the first moment (or PHD) instead of the full multitarget posterior, still involves multiple integrals with no closed forms in general. This article establishes the relationship between FISST and conventional probability that leads to the development of a sequential Monte Carlo (SMC) multitarget filter. In addition, an SMC implementation of the PHD filter is proposed and demonstrated on a number of simulated scenarios. Both of the proposed filters are suitable for problems involving nonlinear nonGaussian dynamics. Convergence results for these filters are also established.