An Introduction to Tracking

Introduction to Tracking
A Super Simple Tracking Example for Fun and Profit

Work Independent Other Education Transcript Skills Resume

Introduction

Here is an extremely simple introduction to tracking presented by Dr. Clayton Kerce at the Georgia Institute of Technology. Things will be explained with ideas and pictures as much as possible.

Imagine a target, maybe a truck moving along a road with position p and constant velocity v. The road is straight so the truck may only move forwards and backwards at a given speed.

We wish to find the truck's position and velocity. However, we can only observe the position at a given moment in time. Worse, the position we observe is corrupted by white noise u~U[-1,1].

The dynamics of our system are therefore defined as:

This just says that

The trucks new position is the position plus the velocity
The velocity doesn't change
We can only measure the trucks position that has been corrupted with noise (and not the velocity at all, at least directly)
The noise is somewhere between -1 and 1

Without the noise, we would instantly know the position, and we could calculate the velocity by simply differencing the first two position measurements:

With the noise, however, this equation for velocity will give poor results. The velocity will be poor because the measurement, Y_n, is noisy.

This example will show graphically how to visualize and solve this problem. It will be fun.

Setting up the Problem

Let's say that the truck is located at the origin and traveling at a constant five meters per second. If we plot this point, with position on the horizontal axis and velocity in the vertical axis we get the following simple plot:

After one second passes, the truck will have traveled five meters and will now have a position of five. The velocity will not change. The x in the first plot will advance to the right.

Lets pretend that we don't know these numbers, just like we wouldn't know them in the real world if we were just watching a truck drive by. The only way to discover these true values is to take measurements (remember we can only measure the position) and try and discern both position and velocity despite the noise. In this example we will take a measurement once every second (1Hz). Remember that between each measurement the truck is moving, so we we have to take into account these changes (or "dynamics") as we try and estimate the state.

We summarize as follows:

P₀ = 0m
V₀ = 5m/s
Sample Rate = f = 1Hz

First Measurement

When we make our first measurement of the position, it looks like this:

So far, we have no information about velocity whatsoever. We do get a first guess at the position.

Our guess isn't a single number. Instead it's a range of possible values that the position and velocity could be.

Say our first measurement at time zero is y[0] = 0.2m. Because we know that our noise cannot be greater than one or less than minus one, we know that the true value of the position is between -0.8m and 1.2m. Recall that the true value of position is the starting position of 0m.

One measurement gives us absolutely no information about velocity (rate of change) so we can only say that velocity is bounded by the region [-Infinity, Infinity]. This doesn't help as much, but it's a start.

We will draw the plot again, but this time we color in the region where we think the true state might be based on our first measurement.

With only one measurement we have a pretty poor grasp of what the true value of X actually is. Next, we'll see how an additional measurement will help us.

Second Measurement

The second measurement will give us information about velocity and it will help us better understand the true position.

Before we take our measurement at time = 1 sec let's talk about what happens to our old estimate. We know for sure the truck was between p=-0.8m and p=1.2m. If the truck isn't moving, then we expect to measure it near the origin again on our next reading. However, if it is moving very fast then we expect to find it far away from where we last measured it.

It we move every point in the set of possibilities forward (or backward) by its corresponding velocity (the y-axis) then the result is our best guess of where we expect to find the truck on our second measurement given what we learned in the first measurement. It looks like this:

Now that we know our best guess for where the truck should be, why don't we take another measurement and see how it compares?

Once again, the new measurement will be the true position plus some noise. We will define another blue region that shows what our best guess might be at t=1s only given the second measurement:

Now we have two regions to consider: the gray and the new blue.

The gray region is where the state should be if our first measurement was trustworthy.
The new blue region is where the state should be if the second measurement is trustworthy.
Both measurements are trustworthy. Therefore, we consider the two set's intersection as our new best guess for where x lives.

Let's color this new best guess / intersection red:

Third Measurement

We will now just repeat what we did in the second measurement.

The red region is now our best guess, so we simply

Advance this new set of possibilities forward in time.
Take a third measurement and define set of possible positions based on this measurement alone.
Use the intersection of these two new sets to form our next best guess for where x resides.

The result will look like this:

Notice how the red set, our "best guess", is getting small with every new measurement. This makes sense.

We could keep taking measurements forever and get a better and better estimate for the true value of X.

Evaluating Performance

We will use the centroid of our new shape to evaluate the performance of our algorithm by comparing it to the true state.

The centroid is the center of our set of possible positions and velocities, and so we will make a note of how this error grows or shrinks over time.

To get a good feel of how the system will perform, we should take an average of many different runs so we can see how things evolve with many combinations of different random numbers in the measurements.

Here are results using an average of 120 runs:

Notice that this is done on a log-log axis. The error shrinking very quickly. After only a handful of measurements we can give a very accurate estimate for the value of both the position AND the velocity.

MATLAB Code

Download Here

I coded this example in MATLAB and have released it here for your review. You can set various options at the top of the file.

References

Acknowledgments

This example is an adaptation of a constant velocity tracker that was made as extremely simple as possible--namely, by removing all of the probability theory--by Dr. James Clayton Kerce and presented in his MA8813 class, Statistical Inversion Problems, at the Georgia Institute of Technology in Spring 2008.