Search

Two algorithms for tracking in clutter, based on the Viterbi algorithm are presented: single-target Viterbi data association (ST-VDA) and multihypothesis VDA (MH-VDA). MH-VDA is designed specifically for multiple-target tracking (MTT), although ST-VDA still achieves good performance on MTT problems. The basic philosophy of both methods is to set up an optimisation problem for the sequence of measurement-to-target associations rather than directly seeking the target state estimates. The joint optimisation problem for the data association sequence is decomposed into a sequence of scalar optimisation problems by means of an approximate forward dynamic programming recursion to which the Viterbi algorithm is applicable. Once the data association problem is solved, the target state estimates can be retrieved by backtracking. The operation of the algorithms is easily visualised as a search on a trellis for the optimal path. For ST-VDA, nodes in the trellis correspond to measurements. For MH-VDA, nodes correspond to multitarget data association hypotheses. Conventional measurement gating is extended to work within this context. Results from simulations that compare the performance of ST-VDA and MH-VDA with four, standard, zero-scan-back tracking approaches are given. The performance assessment includes metrics for track loss and track swaps in a multiple crossing target context. The Viterbi data association (VDA) algorithms are shown to outperform the alternative algorithms. In particular the ST-VDA is found to have the best track swap performance, while MH-VDA has the lowest track loss figure. Average state estimation errors for both VDA algorithms are only about 10% larger than a Kalman filter with known data associations. While both variants of VDA are essentially batch processing approaches, the simulation results indicate that the algorithms can be implemented with a fixed processing lag of only a few scans without significant loss in performance.

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 fully automatic tracking algorithm must be able to deal with an unknown number of targets, unknown target initiation and termination times, false measurements and possibly time-varying target trajectory behaviour. An efficient algorithm for tracking in this environment is presented here. This approach makes use of estimates of the probability of target existence, which is an integral part of the algorithm. This allows for the efficient generation and management of possible target hypotheses, yielding an algorithm with performance that matches what can be obtained by multiple hypothesis tracking-based approaches, but at a significantly lower computational cost. This paper considers only the single target case for clarity. The extension to multiple targets is easily incorporated into this framework. Simulation studies are given that show the effectiveness of this approach in the presence of heavy and nonuniform clutter when tracking a target in an environment of low probability of detection and in an environment where the target performs violent manoeuvres.

Two algorithms are derived for the problem of tracking a manoeuvring target based on a sequence of noisy measurements of the state. Manoeuvres are modeled as unknown input (acceleration) terms entering linearly into the state equation and chosen from a discrete set. The expectation maximization (EM) algorithm is first applied, resulting in a multi-pass estimator of the MAP sequence of inputs. The expectation step for each pass involves computation of state estimates in a bank of Kalman smoothers tuned to the possible manoeuvre sequences. The maximization computation is efficiently implemented using the Viterbi algorithm. A second, recursive estimator is then derived using a modified EM-type cost function. To obtain a dynamic programming recursion, the target state is assumed to satisfy a Markov property with respect to the manoeuvre sequence. This results in a recursive but suboptimal estimator implementable on a Viterbi trellis. The transition costs of the latter algorithm, which depend on filtered estimates of the state, are compared with the costs arising in a Viterbi-based manoeuvre estimator due to Averbuch, et al. (1991). It is shown that the two criteria differ only in the weighting matrix of the quadratic part of the cost function. Simulations are provided to demonstrate the performance of both the batch and recursive estimators compared with Averbuch's method and the interacting multiple model filter.

The problem of constructing a frequency tracker for weak, narrowband signals with slowly varying frequency is considered. An extended Kalman filter is proposed that uses prior knowledge of the nature of the signal to overcome the difficulties presented by the inherent nonlinearity of the problem and the very low signal-to-noise ratios.