An Efficient Multi-Frame Track-Before-Detect Algorithm for Multi-Target Tracking

This paper considers the multi-target tracking (MTT) problem through the use of dynamic programming based track-before-detect (DP-TBD) methods. The usual solution of this problem is to adopt a multi-target state, which is the concatenation of individual target states, then search the estimate in the expanded multi-target state space. However, this solution involves a high-dimensional joint maximization which is computationally intractable for most realistic problems. Additionally, the dimension of the multi-target state has to be determined before implementing the DP search. This is problematic when the number of targets is unknown. We make two contributions towards addressing these problems. Firstly, by factorizing the joint posterior density using the structure of MTT, an efficient DP-TBD algorithm is developed to approximately solve the joint maximization in a fast but accurate manner. Secondly, we propose a novel detection procedure such that the dimension of the multi-target state no longer needs be to pre-determined before the DP search. Our analysis indicates that the proposed algorithm could achieve a computational complexity which is almost linear to the number of processed frames and independent of the number of targets. Simulation results show that this algorithm can accurately estimate the number of targets and reliably track multiple targets even when targets are in proximity.