Share Email Print

Proceedings Paper

Data association problems posed as multidimensional assignment problems: problem formulation
Author(s): A. B. Poore; N. Rijavec; M. Liggins; V. C. Vannicola
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

The ever-increasing demand in surveillance is to produce highly accurate target and track identification and estimation in real-time, even for dense target scenarios and in regions of high track contention. The use of multiple sensor, through more varied information, has the potential to greatly enhance target identification and state estimation. For multitarget tracking, the processing of multiple scans all at once yields high track identification. However, to achieve this accurate state estimation and track identification, one must solve an NP-hard data association problem of partitioning observations into tracks and false alarms in real-time. The primary objective in this work is to formulate a general class of these data association problems as a multidimensional assignment problem to which new, fast, near-optimal, Lagrangian relaxation based algorithms are applicable. The dimension of the formulated assignment problem corresponds to the number of data sets, and the constraints define a feasible partition of the data sets. The linear objective function is developed from Bayesian estimation and is the negative log likelihood function, so that the optimal solution yields the maximum likelihood estimate. After formulating this general class of problems, the equivalence between solving data association problems by these multidimensional assignment problems and by the currently most popular method of multiple hypothesis tracking is established. Track initiation and track maintenance using an N-scan sliding window are then used as illustrations.

Paper Details

Date Published: 22 October 1993
PDF: 12 pages
Proc. SPIE 1954, Signal and Data Processing of Small Targets 1993, (22 October 1993); doi: 10.1117/12.157786
Show Author Affiliations
A. B. Poore, Colorado State Univ. (United States)
N. Rijavec, Colorado State Univ. (United States)
M. Liggins, Rome Labs. (United States)
V. C. Vannicola, Rome Labs. (United States)

Published in SPIE Proceedings Vol. 1954:
Signal and Data Processing of Small Targets 1993
Oliver E. Drummond, Editor(s)

© SPIE. Terms of Use
Back to Top