I have run into a problem in my project that can be generalized to a more abstract problem, and wanted to know if there is a specific machine learning algorithm developed for solving it.

Let's say I have a image consisting of a white background and identical circles. All of the circles have the same radius and color, but different positions. This image captures those positions at a particular moment in time. I have a feature extractor that looks at the image and generates a list of points corresponding to the positions of each of the circles.

I have a second image showing those same circles at the next moment in time. I run the feature extractor and get a list of their new positions.

So I have two lists - a list of positions at time $t$, and a second list of positions at time $t + 1$. I want to now pair each item in the first list with an item in the second list, indicating that these two lists describe the positions of the same set of circles. With this I can track the movement of each circle over time. The two lists are randomly sorted, so the position of the same circle in the lists can arbitrarily move from, say, index 0 in the first list to 5 in the second list without reason.

I could achieve this with some sort of heuristic, but the circles' behavior is very complex. I would rather provide a set of labeled examples and have a machine learning algorithm figure out the probabilistic tendency in the data.

Can this be reduced to an already existing algorithm or tool?

  • $\begingroup$ Are you familiar with (hidden) Markov models? $\endgroup$ – galoosh33 Apr 6 '17 at 21:07
  • $\begingroup$ @galoosh33 I just stumbled upon them but I'm having difficulty seeing what the inputs and outputs would be. $\endgroup$ – NmdMystery Apr 6 '17 at 21:10
  • $\begingroup$ Essentially it's a family of models designed to learn probabilities of state transitions (e.g: if today rained, what is the probability tomorrow will be sunny). Simple models assume the states are observed, and hidden models assume the states are not directly observed, but the output, dependent on the state, is observed. In your case, the states could be the set of potential centroids (this will require descretizing your domain), and you learn the probabilities of a circle "moving" to every other location. This should allow you to map your list at time $t$ to the list at time $t+1$. $\endgroup$ – galoosh33 Apr 6 '17 at 21:21

https://en.wikipedia.org/wiki/Hungarian_algorithm, which has optimizations for the special case of Euclidean plane (e.g., A Survey on Algorithms for Euclidean Matching).

An unrelated suggestion: if the circles correspond to physical objects (they have inertia), then it may improve tracking if you consider more than two snapshots of the coordinates (or alternatively, keep inferred velocities along coordinates).


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.