I'm afraid the title is terrible, but I don't know how to summarize this problem in a few words.

Using an instrument, we are monitoring the trajectory of several objects during a period of time. We take a lot of measurements of the position of the objects in the field of view of the instrument, so we have a list of triplets composed of (time, X, Y). Usually there are several objects in view, so we have several positions for the same time.

We already have an algorithm that can reconstruct the trajectory of a single object if you give its measurements, however, this algorithm won't work if several objects are provided at the same time. So we are looking for an algorithm to first classify the different observations in different objects.

Here is an example of an easy problem, plotted in 2D, containing two objects. It seem they cross paths but actually they approach at different times so it should be possible to classify them without confusion. Sometimes the objects will really cross paths at the same time (get really close). In that case, it is better just to discard the points near the encounter than get some points wrong.

two objects

Some other scenarios are much more complicated, but it would be OK to discard points from different trajectories that are very close in position and in time. Trajectories can be curved lines, and in fact, almost always they are smoothly curved lines:

multiple objects

Any hint on how should I approach this problem?

  • $\begingroup$ What are those gaps? Is it one object moving especially quickly in those? Or is it not observed? Is the number of objects fixed? $\endgroup$
    – Kirill
    Aug 1 '15 at 1:11
  • $\begingroup$ The gaps are from the observation, due to the download time from the camera or sensor movement, but the actual object speed is very stable, it may vary but very slowly. The number of objects is unknown a priori, it may be from one to about 50, but usually is below 10. $\endgroup$
    – siritinga
    Aug 1 '15 at 9:21

The gist of this answer is that this problem fits into a general framework that is part of machine learning.

I think this can be done using the standard machinery of clustering / filtering problems in statistics, which are pretty standard. There's a lot of literature on this, so I'm going to present just the basic outline of how this can be done: it's easy to write down a basic model and then improve on it.

Let the set of observations be $O=\{o_n\}_n$, with each observation $o = (t, x)$ consisting of time and location. Let $\Lambda$ be the set of all objects' labels (fixed for now). We can write down the likelihood function for all the observations given a specific assignment of labels, and then try to find the assignment of object labels that maximizes log-likelihood.

This translates to finding that assignment of labels to observations that is the most likely under some statistical model of objects' behaviour.

The likelihood function is, given an assignment of labels $\{\lambda_n\}_n$, the p.d.f. of those observations given this assignment: $$ L(\{\lambda_n\}) = \mathbb{P}(o_1,\ldots,o_n\mid \{\lambda_n\}). $$ We can try to factor this likelihood function as $$ L(\{\lambda_n\}) = \prod_\lambda \mathbb{P}(o^\lambda_1) \mathbb{P}(o^\lambda_2\mid o^\lambda_1)\cdots\mathbb{P}(o^\lambda_k \mid o^\lambda_{k-1},o^\lambda_{k-2},\ldots,o^\lambda_1), $$ where the product goes over all assigned object labels $\lambda$, and each term is the likelihood of observing the same object $\lambda$ at different observations $o^\lambda_1,\ldots,o^\lambda_k$.

To write down the probabilities we can try to model their motion as constant-velocity motion, so that $$ \mathbb{P}(o^\lambda_j \mid o^\lambda_{j-1},o^\lambda_{j-2},\ldots) $$ can be written in terms of $(t_j,x_j), (t_{j-1},x_{j-1}), (t_{j-2},x_{j-2})$ using (say) the normal distribution $$ N\left(x_j \mid x_{j-1} + (t_j - t_{j-1})\frac{x_{j-1}-x_{j-2}}{t_{j-1}-t_{j-2}}, \xi \right). $$ This says that after observing object $\lambda$ at $o^\lambda_{j-2}$, then $o^\lambda_{j-1}$ the expected next location is at $x_{j-1}+\delta t\cdot v$, with some variance $\xi$. For the initial observations one might write down $$ \mathbb{P}(o^\lambda_1) = \mathrm{const}, \qquad \mathbb{P}(o^\lambda_2|o^\lambda_1) = N(x_2 \mid x_1, (t_2-t_1)\eta), $$ where $\mathrm{const}$ is a p.d.f. (up to a multiplicative constant that will drop out later) that is like a penalty for introducing a new object label, and where $\eta$ represents uncertainty in how much an object might move in one time step.

Once this is all done, $-\log L$ becomes a sum of squared errors (although a bit laborious to write out in full) in the observations given an assignment of labels. This sum of squared errors (negative log-likelihood) can be minimized by a simple iterative process: walk through observations in chronological order, and for each next observation pick a label (existing or new) that results in the smallest sum of squared errors over observations so far.

This might already be good enough. If not, you might consider equipping each observation with a hidden state, such as $(t, x, v, a)$ where only $t$ and $x$ are directly observed, and each object also has velocity $v$ and acceleration $a$ that need to be inferred. You might also have to consider more carefully what the optimal assignment of labels is (the above strategy is a greedy assignment; a common method is the EM algorithm), and how to best determine the total number of objects (e.g., introduce a penalty into $-\log L$ for the total number of objects).

What I described here is a kind of Bayesian filtering approach (this is too long already). But this is a pretty standard problem: you have a hidden state (assignment of labels, velocities, etc.), and a statistical model of how that hidden state produces the observations that you have (the likelihood function), and you are trying to infer the hidden state from the observations (by maximization of log-likelihood). Textbooks that discuss machine learning, Bayesian inference, graphical models would be helpful here.

  • $\begingroup$ Wow, thank you very much for this lengthy and detailed explanation. Your approach certainly looks very promising but I'm afraid I don't have the expertise to follow and implement it. However, I will make the effort, and I think that a similar approach can be applied to some other (similar) problems we have to solve. I have implemented a deterministic approach of predicting the position in the future depending on past classifications (starting with a greedy position algo) and taking the closest candidate, it works moderately well except in cluttered sections. $\endgroup$
    – siritinga
    Aug 4 '15 at 9:34
  • $\begingroup$ @siritinga I hope I didn't make it sound too complicated. There's a bit of jargon, due to this coming from a different field than pure numerical analysis, but it's really not bad. Cluttering is the sort of situation where you need to backtrack a little to properly minimize the sum of squared errors and where a greedy method wouldn't work so well. $\endgroup$
    – Kirill
    Aug 4 '15 at 17:29

If I understand correctly, the form of your problem seems similar to the one faced by a radar or sonar system. In that case, the sensor periodically outputs a number of "hits" or detections, each consisting of a time and a location in space.

Machine learning brings powerful general methods to bear on problems of this form (as observed in the answer by Kirill) but in addition there is a substantial literature tailored to this specific problem.

The task in tracking is to decide which hits are associated with a single object. E.g., when many aircraft are up, then deciding which of a radar sweep's detections are associated with the previous sweep's detections is not so obvious.

Tracking algorithms typically work by having a model that predicts roughly where a next detection is expected, given previous detections, and using this prediction as a guide to associating a new detection with previous ones.

Wikipedia of course is often good for a quick survey of a technique to see if it is worth exploring more. In this case there are several similarly-named articles of very different content. I suggest that Tracking system is quite off the mark and Track algorithm is broad but thin; Radar tracker on the other hand has a solid list of well-known algorithms, starting from the simplest (alpha-beta) through the Kalman filter and its variants, to the particle filter.


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.