An Optimal Transport Approach to Multiple Target Tracking via Entropic Regularization

Sammanfattning

Multiple target tracking (MTT) describes the problem of estimating tracks oftargets by using finitely many observations identified from a sensor. This thesisexplores the feasibility of designing an algorithm or an algorithmic pipeline to finda suboptimal but accurate solution in a reasonable time. It is not obvious that thisis possible, since finding an exact solution to the multimarginal matching problem,which is the mathematical description of MTT, is NP-hard. We show that thisis in fact possible by describing such a process. This process finds a solutionto the entropic regularized problem by using the Sinkhorn algorithm and doesthis efficiently by leveraging gating. From the relaxed solutions generated by theSinkhorn algorithm, an integer solution, that is, a solution to the multimarginalmatching problem, is recovered by solving a set of bimarginal assignment problems.These bimarginal matching problems can all be solved in polynomial time,connecting these into a complete integer solution. It turns out that this is notonly a process that generates a feasible solution to the matching problem in areasonable time, but the solution obtained outperforms solutions found by somealready existing tracking algorithms.