Efficient Evaluation of Target Tracking Using Entropic Optimal Transport

Abstract

Multiple target tracking deals with the task of estimating targets which appear, disappear, and move within a scene, given data from noisy measurements. To solve this task, a wide range of algorithms can be employed. In order to assess the performance of such algorithms, the so-called GOSPA metric for trajectories can be applied. This metric is formulated as an optimization problem, which has proven computationally demanding for large problem instances. In this thesis, we reformulate this metric in two different ways to obtain optimization problems with optimal transport structure. Following a recent breakthrough in computational optimal transport, we introduce entropic regularization into these formulations. For the regularized problems, we derive and present two numerical algorithms for finding approximate solutions. We test the performance of each algorithm on simulated data with regards to accuracy and computational efficiency. The numerical results suggest that the regularization can be made small enough to allow for an adequate approximation of the GOSPA metric for trajectories while simultaneously allowing a satisfactory convergence rate. Lastly, we compare the running time of our most efficient algorithm with that of a conventional linear programming solver. If a small approximation error is allowed, we find that our algorithm scales better both when the number of trajectories in the data increases, and when the number of considered time steps in the data increases.