An efficient multiple hypothesis tracker using max product belief propagation

The multiple hypothesis tracker (MHT) is a popular algorithm for solving multi-target tracking (MTT) problem in cluttered environment. It is known as a maximum a posterior (MAP) estimator which enumerates all possible global hypotheses and dedicates to find the most likely solution based on the received reports. However, its practical application is often limited by the complexity of data association step. This paper describes an efficient MHT data association algorithm which based on the 'track-oriented' MHT framework. The proposed approach translates the data association problem to the maximum weight independent set problem (MWISP) and introduces a graph representation to describe the track hypotheses and the compatibility restrictions between them. In this way, the MAP assignment in tracking application can be solved by applying max-product belief propagation (MPBP) inference algorithm to the corresponding graph. Empirical results demonstrate that the MPBP-MHT algorithm outperforms other algorithms in tracking performance even in challenging closely-spaced MTT case.