Data association problems posed as multidimensional assignment problems: problem formulation

A. B. Poore; N. Rijavec; M. Liggins; V. C. Vannicola

doi:10.1117/12.157786

22 October 1993 Data association problems posed as multidimensional assignment problems: problem formulation

A. B. Poore, N. Rijavec, M. Liggins, V. C. Vannicola

Proceedings Volume 1954, Signal and Data Processing of Small Targets 1993; (1993) https://doi.org/10.1117/12.157786
Event: Optical Engineering and Photonics in Aerospace Sensing, 1993, Orlando, FL, United States

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.

Citation Download Citation

A. B. Poore, N. Rijavec, M. Liggins, and V. C. Vannicola "Data association problems posed as multidimensional assignment problems: problem formulation", Proc. SPIE 1954, Signal and Data Processing of Small Targets 1993, (22 October 1993); https://doi.org/10.1117/12.157786

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available