Multiscan Multitarget Tracking Based on a Hybrid Message-Passing Method

The multiple hypothesis tracking (MHT) algorithm is widely applied in various multi-target tracking (MTT) scenarios due to its high association accuracy. The global hypothesis generation (GHG) poses a core and challenging problem within MHT. In this paper, we treat the GHG from the message passing perspective and propose a hybrid message passing (HMP) method. Firstly, the GHG problem is mapped onto the Markov random field (MRF), thereby transforming the problem into solving the maximum a posteriori (MAP) estimation on the MRF. Secondly, the HMP method is introduced within the MRF, especially containing loops. This method utilizes the max-product belief propagation for rapid pre-selection, obtaining preliminary results. Subsequently, to improve the accuracy of the GHG problem, further refinement is performed on these preliminary results. Based on whether these preliminary results satisfy the independent set condition (ISC), we employ different refinement strategies. For preliminary results that do not meet the ISC, they are fed into the junction tree algorithm for refinement. Furthermore, the remaining preliminary results are integrated to obtain the refined result. Finally, we analyze its computational complexity. Through simulations with existing message-passing-based MHT algorithms, we demonstrate the superiority of the HMP method. The proposed HMP method in this paper achieves a compromise between accuracy and computational efficiency when addressing MRFs containing loops.