Share Email Print

Proceedings Paper

Performance comparison of 2D assignment algorithms for assigning truth objects to measured tracks
Author(s): Mark Levedahl
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

The processing time requirements of several algorithms for solving the 2-d (also called single frame) linear assignment problem are compared, along with their accuracy given either random or biased measurement errors. The specific problem considered is that of assigning measurements to truth objects using costs that are the chi-squared distances between them. Performance comparisons are provided for the algorithms implemented both in a compiled language C or FORTRAN) as well as the interpretive MatLab language. Accuracy considerations show optimal assignment algorithm is preferred if biased measurement errors are present. The Jonker-Volgenant-Castanon (JVC) algorithm is the preferred approach considering both average and maximum solution time. The Auction algorithm finds favor due to being both efficient as well as easy to understand, but is never faster and often much slower than the JVC algorithm. Both algorithms are dramatically faster than the Munkres algorithm. The greedy nearest neighbor algorithm is an ad hoc solution to provide a sub-optimal but unique solution more cheaply than the optimal assignment algorithms. However, the JVC algorithm is as fast as the greedy for simple problems, marginally slower at hard problems, and is vastly more accurate in the presence of measurement biases.

Paper Details

Date Published: 13 July 2000
PDF: 10 pages
Proc. SPIE 4048, Signal and Data Processing of Small Targets 2000, (13 July 2000); doi: 10.1117/12.392018
Show Author Affiliations
Mark Levedahl, Raytheon Co. (United States)

Published in SPIE Proceedings Vol. 4048:
Signal and Data Processing of Small Targets 2000
Oliver E. Drummond, 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?