You are here

Minimum Cost Multi-Way Data Association for Optimizing Multitarget Tracking of Interacting Objects

TitleMinimum Cost Multi-Way Data Association for Optimizing Multitarget Tracking of Interacting Objects
Publication TypeJournal Article
Year of Publication2015
AuthorsPark, C, Woehl, TJ, Evans, JW, Browning, ND
JournalIeee Transactions on Pattern Analysis and Machine Intelligence
Volume37
Pagination611-624
Date Published03
Type of ArticleArticle
ISBN Number0162-8828
Accession NumberWOS:000349626200010
Keywordsbinary integer programming, Data association, decomposition, detection responses, dual relaxation, growth, lagrange, multiple targets, probabilistic data association, splitting targets, visual tracking
Abstract

This paper presents a general formulation for a minimum cost data association problem which associates data features via one-to-one, m-to-one and one-to-n links with minimum total cost of the links. A motivating example is a problem of tracking multiple interacting nanoparticles imaged on video frames, where particles can aggregate into one particle or a particle can be split into multiple particles. Many existing multitarget tracking methods are capable of tracking non-interacting targets or tracking interacting targets of restricted degrees of interactions. The proposed formulation solves a multitarget tracking problem for general degrees of inter-object interactions. The formulation is in the form of a binary integer programming problem. We propose a polynomial time solution approach that can obtain a good relaxation solution of the binary integer programming, so the approach can be applied for multitarget tracking problems of a moderate size (for hundreds of targets over tens of time frames). The resulting solution is always integral and obtains a better duality gap than the simple linear relaxation solution of the corresponding problem. The proposed method was validated through applications to simulated multitarget tracking problems and a real multitarget tracking problem.

DOI10.1109/tpami.2014.2346202
Custom 1

Not AL