HMC Bee Lab: When Ants Bump Into Each Other: A Motion-Based Multiple Object Tracking Problem

In our lab, we are interested in analyzing the movement of ants in an artificial environment. Because of this, we can generate many hours of videos of ants crossing bridges or exploring the environment we have designed for them. A software pipeline built with Python and MATLAB’s Motion-Based Multiple Object Tracking Software helps analyze these videos. My role in the Bee Lab has been to test and evaluate our Ant Tracking pipeline and suggest ways for improving it.

Recently, manual verification of the pipeline’s results has revealed a concerning tendency for our software to lose track of ants when they move towards each other from opposite directions, bump, and then move back the way they came. In a situation like this, the algorithm is prone to switch IDs, so that each ant is identified as the other. Why does this happen? I decided to take a look at the implementation of MATLAB’s Tracking Model to try to understand.

An illustration of two ants bumping into each other. Notice how their IDs switch when they turn around.

The primary problem in object tracking is finding the new location of an object, say an ant, that appeared in a previous frame. The problem is made easier by use of a mathematical model for how we expect the object to move. For example, the motion of a ball across a surface might be approximated by the equation

$p = p_0 + v_0 t$

(and in fact, this constant velocity model is also used to track ants). At each point in time, the software must decide how to match every ant in the prior frame with an ant in the current frame such that it minimizes the total distance cost. For now, it will be convenient to think of this cost as the distance between the expected location of an ant (calculated using the mathematical model) and the observed location. In reality, it’s a little more complicated, but I’ll explain this in greater detail later.

To solve this matching problem, MATLAB uses the Hungarian algorithm, an assignment algorithm designed exactly for this type of problem. First, it represents all distance costs in a cost matrix where the rows of the matrix represent the location of previously detected ants and the columns represent those of ants in the current frame. Then, a number of operations are performed on the matrix to transform it. The resulting matrix will have a 0 in each row and column and nowhere else. The location of these 0’s indicates that the ant in this row should be assigned to the ant in this column.

I told you that distance cost was the distance between the expected location of an ant (obtained by plugging the location of the ant in the prior frame into the constant velocity model) and the observed location (in the current frame). But in truth the expected location isn’t exactly what we use. Usually, an algorithm called the Kalman filter is used to incorporate knowledge about both the expected location and the observed location (that the software retrieves from the video) to calculate a corrected location, which is the value that we actually use to calculate the distance cost. But how exactly is this corrected location calculated and why is it used instead?

The Kalman filter is typically used to reduce noise in observed measurements using information about an object’s expected state from a mathematical model. For example, say that we are at time t+1 in the tracking of an ant, and we want to know where the ant is. Our software observes the ant to be located at position x, but we expect this measurement to be slightly off from the actual location due to some noise. Usually, this is drawn as a probability density distribution with a peak at the observed location, so that we may represent the uncertainty in our estimate of the location.

We can also obtain an expected location for the object using a mathematical model based on the prior state (i.e. position and velocity) of the ant. This prediction also comes with some uncertainty.

The Kalman filter uses these two distributions to calculate a new distribution more reflective of the true position than the past two.

But how is this new curve calculated? Well, since these are probability density distributions, we can multiply the equations of the red and blue curves to obtain that of the green curve, a joint probability distribution. Since all of these curves follow a normal distribution, we can then use a little bit of math to derive the following: if μ₀ and σ₀ represent the mean and standard deviation of the observed location and μ₁ and σ₁represent those of the expected location, we can obtain the value

$k = \frac{\sigma_0 ^ 2}{\sigma_0 ^ 2 + \sigma_1 ^ 2}$

which can be used to find the mean

$\mu' = \mu_0 + k(\mu_1 - \mu_0)$

and variance

$\sigma^{\prime2}=\sigma_0^2-k\sigma_0^2$

of the green curve. Of course, the example above works only when we are predicting the new location of something on a single dimensional axis. In reality, our Kalman filter is working with matrices to perform these calculations in many dimensions, since the ant can move vertically and horizontally and can have different velocities in each of these dimensions, but the main idea is the same. Using the Kalman filter, we can appropriately weight our observed locations by our expected locations at each point in the video in order to reduce noise in the observed locations.

The Kalman filter is applied between every pair of ants between the prior frame and the current frame. It compares the corrected location of each ant in the current frame to the observed location in the current frame to calculate a distance cost. The Hungarian algorithm uses the distance costs for each possible pairing of ants to choose the optimal assignment of ants between frames. Thus, the optimal assignment of ants will also minimize the corrections performed by the Kalman filter. Perfect!

So why does the algorithm switch the ID’s of ants that bump into each other? My hypothesis is that the Kalman filter is assigning too much weight to the expected location of each ant. It is being a little overzealous in its noise correction. There exists a way to tell MATLAB to lighten up in this regard: we can increase the MotionNoise parameter to the Kalman filter to tell it that it’s actually ok if our observed measurements deviate from the constant velocity model, as real ants actually do. Perhaps this will finally solve our simple but oh-so vexing problem!

HMC Bee Lab

Pages

Thursday, January 3, 2019

When Ants Bump Into Each Other: A Motion-Based Multiple Object Tracking Problem

No comments:

Post a Comment