1
$\begingroup$

time series data I have a time series data. Where for every time step I have a varying number of object coordinates. I want to track these over time. There might also be some missing coordinates for a few frames. Ideally, given the time series input and I am looking to find out a list of tracks and their respective start and end time.

What kind of algorithms am I supposed to use? Are there any implementations available.

$\endgroup$
2
$\begingroup$

Your problem falls into the category of problems known as $Multitarget\; Tracking$. Are there algorithms?, you Betcha there are algorithms. This is an active area of research. IEEE Explore returns 1,620 hits for (multitarget tracking)

The optimal algorithm is known as Reid's Multi Hypothesis Tracker (MHT), which unfortunately requires the exhaustive enumeration of an exponentially growing set of hypothesis. There are various heuristics to keep thing manageable.

Another contender is Bar Shalom's Joint Probability Data Association Filter (JPDA) which isn't optimal, but is more manageable.

There are numerous other algorithms as well. Fundamentally, the general problem is NP hard.

The essential problem is that if each measurement was labeled from each source, the data could directly update something like a Kalman Filter for each object. Unfortunately, data is not labeled, and there are also false and missed measurements. Most approaches attempt the data association anyway.

Most implementations are closely held, As far as Matlab code goes, you can try.

https://www.mathworks.com/matlabcentral/fileexchange/43526-multiple-target-tracking-with-multiple-observations

Most free code that I've seen only do data association over a single measurement epoch, not over multiple epochs.

If you want to look at books,

Multiple-target Tracking with Radar Applications Book by Samuel S. Blackman

Multitarget-Multisensor Tracking Book by Yaakov Bar-Shalom

If you don't want to turn this problem into a lifelong obsession, (too late for me) , I would suggest doing a k-means for a reasonable number of k's, at each time instance. formulate a heuristic of what looks best, and then update a set of something like a set of Kalman Filters. This will work until you have crossing targets, and then you have to come up with another heuristic.

$\endgroup$
0
$\begingroup$

Normally a filter can be deduced from the Bayes equation, which deals with random variables. Ronald Mahler has generalized the Bayes equation to deal with random finite sets (RFS), where each element, if any, might be a tracking vector. With this RFS algebra, hi has proposed a filter (PHD-Filter) which handles all current tracks and all available measurements at once, with no need of heuristics and data association steps. Bar Shalom himself has published comments on it, and several authors have contributed with even more robust filters. Some results are available at youtube, like this or this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.