Share Email Print

Proceedings Paper

Partial branch and bound algorithm for improved data association in multiframe processing
Author(s): Aubrey B. Poore; Xin Yan
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

A central problem in multitarget, multisensor, and multiplatform tracking remains that of data association. Lagrangian relaxation methods have shown themselves to yield near optimal answers in real-time. The necessary improvement in the quality of these solutions warrants a continuing interest in these methods. These problems are NP-hard; the only known methods for solving them optimally are enumerative in nature with branch-and-bound being most efficient. Thus, the development of methods less than a full branch-and-bound are needed for improving the quality. Such methods as K-best, local search, and randomized search have been proposed to improve the quality of the relaxation solution. Here, a partial branch-and-bound technique along with adequate branching and ordering rules are developed. Lagrangian relaxation is used as a branching method and as a method to calculate the lower bound for subproblems. The result shows that the branch-and-bound framework greatly improves the resolution quality of the Lagrangian relaxation algorithm and yields better multiple solutions in less time than relaxation alone.

Paper Details

Date Published: 27 July 1999
PDF: 13 pages
Proc. SPIE 3720, Signal Processing, Sensor Fusion, and Target Recognition VIII, (27 July 1999); doi: 10.1117/12.357166
Show Author Affiliations
Aubrey B. Poore, Colorado State Univ. (United States)
Xin Yan, Colorado State Univ. (United States)

Published in SPIE Proceedings Vol. 3720:
Signal Processing, Sensor Fusion, and Target Recognition VIII
Ivan Kadar, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?