13 July 2000 Performance comparison of 2D assignment algorithms for assigning truth objects to measured tracks
Author Affiliations +
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.
© (2000) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Mark Levedahl, Mark Levedahl, } "Performance comparison of 2D assignment algorithms for assigning truth objects to measured tracks", Proc. SPIE 4048, Signal and Data Processing of Small Targets 2000, (13 July 2000); doi: 10.1117/12.392018; https://doi.org/10.1117/12.392018


A General, Iterative Method Of Image Recovery
Proceedings of SPIE (October 12 1987)
Sparse dual frames in compressed sensing
Proceedings of SPIE (September 27 2011)
Domain decomposition, boundary integrals, and wavelets
Proceedings of SPIE (August 31 1995)

Back to Top