Partial branch and bound algorithm for improved data association in multiframe processing

Aubrey B. Poore; Xin Yan

doi:10.1117/12.357166

27 July 1999 Partial branch and bound algorithm for improved data association in multiframe processing

Aubrey B. Poore, Xin Yan

Proceedings Volume 3720, Signal Processing, Sensor Fusion, and Target Recognition VIII; (1999) https://doi.org/10.1117/12.357166
Event: AeroSense '99, 1999, Orlando, FL, United States

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.

Citation Download Citation

Aubrey B. Poore and Xin Yan "Partial branch and bound algorithm for improved data association in multiframe processing", Proc. SPIE 3720, Signal Processing, Sensor Fusion, and Target Recognition VIII, (27 July 1999); https://doi.org/10.1117/12.357166

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