Computational complexity analysis for Multiple Hypothesis Tracking

This paper presents a detailed analysis of computational complexity of Mult iple Hypothesis Tracking (MHT). The result proves that the computational co mplexity of MHT is dominated by the number of hypotheses. Effects of track merging and pruning are analyzed also. Certain common design parameters of MHT, such as thresholds, are also discussed in detail. The results of this paper provide a guidance for selecting parameters in an MHT tracker and pre dicting its performance. Among the design parameters discussed in this pape r, track merging appears to be the most important way for controlling the c omputational complexity of MI-IT. Thresholds for track deletion are also cr itical. If not all measurements are allowed to initiate new tracks, the num ber of new tracks can also be used for tuning the computation requirement o f MHT, but it is not as significant as thresholds. (C) 1999 Elsevier Scienc e Ltd. All rights reserved.