The Complexity of Object Association in Multiple Object Tracking

Authors

  • Robert Ganian TU Wien
  • Thekla Hamm TU Wien
  • Sebastian Ordyniak University of Leeds

Keywords:

Motion & Tracking

Abstract

Object association, i.e., the identification of which observations correspond to the same object, is a central task for the area of multiple object tracking. Two prominent models capturing this task have been introduced in the literature: the Lifted Multicut model and the more recent Lifted Paths model. Here, we carry out a detailed complexity-theoretic study of the problems arising from these two models that is aimed at complementing previous empirical work on object association. We obtain a comprehensive complexity map for both models that takes into account natural restrictions to instances such as possible bounds on the number of frames, number of tracked objects and branching degree, as well as less explicit structural restrictions such as having bounded treewidth. Our results include new fixed-parameter and XP algorithms for the problems as well as hardness proofs which altogether indicate that the Lifted Paths problem exhibits a more favorable complexity behavior than Lifted Multicut.

Downloads

Published

2021-05-18

How to Cite

Ganian, R., Hamm, T., & Ordyniak, S. (2021). The Complexity of Object Association in Multiple Object Tracking. Proceedings of the AAAI Conference on Artificial Intelligence, 35(2), 1388-1396. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16228

Issue

Section

AAAI Technical Track on Computer Vision I