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

TLDR

Multi‑target tracking is usually addressed with dynamic‑programming track‑before‑detect, but the joint maximization over a high‑dimensional multi‑target state is computationally intractable and requires a pre‑determined state dimension, which is problematic when the number of targets is unknown. This study introduces two contributions: an efficient DP‑TBD algorithm and a detection procedure that removes the need to pre‑determine the multi‑target state dimension. By factorizing the joint posterior density according to MTT structure, the authors derive a fast DP‑TBD algorithm and add a novel detection step that eliminates the requirement for a fixed state dimension before the DP search. The algorithm attains near‑linear complexity in the number of frames, independent of target count, and simulations show accurate target enumeration and reliable tracking even when targets are in close proximity.

Abstract

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.