Kalman Filter for Image Object Tracking

Hi,

I am currently doing a object tracking project in computer vision. My
project involves tracking snooker balls on a snooker table. The balls
are tracked frame by frame but the resulting tracking information is
noisy and does not follow the smooth linear motion of the balls on the
table. To smooth the resulting information i am trying to use the
kalman filter as i assumed this was what it was created for.

The issue i am having is that i am not a very mathematical person but i
am willing to learn. The kalman filter looks very challenging and i
dont know how to go about smoothing the tracking data so that i get a
smooth, noise-less motion.

Can someone try and explain the steps in laymans terms to help someone
who isnt so mathematically minded. I have read various online tutorials
and the kalman introduction paper and they try and explain it simply
but i am still finding it hard to work out what the inputs and outputs
are into the filter, what needs to be set up before running the filter
and the matrix the filter uses and what each matrix represents.

I know i am asking a lot but it would be helping me greatly. Also if
you think that there is a better solution to my problem that is easier
to implement then feel free to let me know.

Thanks and kind regards

    Paul
-=---------=-

ProdigalSon wrote:
> Hi,
>
> I am currently doing a object tracking project in computer vision. My
> project involves tracking snooker balls on a snooker table. The balls
> are tracked frame by frame but the resulting tracking information is
> noisy and does not follow the smooth linear motion of the balls on the
> table. To smooth the resulting information i am trying to use the
> kalman filter as i assumed this was what it was created for.
>
> The issue i am having is that i am not a very mathematical person but i
> am willing to learn. The kalman filter looks very challenging and i
> dont know how to go about smoothing the tracking data so that i get a
> smooth, noise-less motion.
>
> Can someone try and explain the steps in laymans terms to help someone
> who isnt so mathematically minded. I have read various online tutorials
> and the kalman introduction paper and they try and explain it simply
> but i am still finding it hard to work out what the inputs and outputs
> are into the filter, what needs to be set up before running the filter
> and the matrix the filter uses and what each matrix represents.
>
> I know i am asking a lot but it would be helping me greatly. Also if
> you think that there is a better solution to my problem that is easier
> to implement then feel free to let me know.

You might want to ask this particular question on sci.image.processing.

Rune

ProdigalSon wrote:
> Hi,
> 
> I am currently doing a object tracking project in computer vision. My
> project involves tracking snooker balls on a snooker table. The balls
> are tracked frame by frame but the resulting tracking information is
> noisy and does not follow the smooth linear motion of the balls on the
> table. To smooth the resulting information i am trying to use the
> kalman filter as i assumed this was what it was created for.
> 
> The issue i am having is that i am not a very mathematical person but i
> am willing to learn. The kalman filter looks very challenging and i
> dont know how to go about smoothing the tracking data so that i get a
> smooth, noise-less motion.
> 
> Can someone try and explain the steps in laymans terms to help someone
> who isnt so mathematically minded. I have read various online tutorials
> and the kalman introduction paper and they try and explain it simply
> but i am still finding it hard to work out what the inputs and outputs
> are into the filter, what needs to be set up before running the filter
> and the matrix the filter uses and what each matrix represents.
> 
> I know i am asking a lot but it would be helping me greatly. Also if
> you think that there is a better solution to my problem that is easier
> to implement then feel free to let me know.
> 
> Thanks and kind regards
> 
>     Paul
> -=---------=-
> 
First, a Kalman filter on the tracker data will only do you good to the 
extent that the tracker is doing it's job -- for tracker questions 
you'll need to use that image processing newsgroup that Rune suggested.

Second, a Kalman filter is a mathematical construct that gives you the 
Very Best Filter that you can possibly have, given some assumptions 
about the nature of the system you're trying to observe and the nature 
of the noise with which your data is corrupted.  The big pile-o-math 
that you encounter is there (a) to translate your assumptions into a 
filter, and (b) to prove that the filter is, indeed, optimal.

Unfortunately, if your assumptions aren't valid then the Kalman filter 
won't be the Very Best Filter.  It will, at best, be a Pretty Good 
Filter, but it may be a Very Bad Filter.  Furthermore, if you don't make 
the right assumptions then the math will go from something that is 
conceptually difficult but easy once you grasp it to something that is 
difficult, if not impossible, to solve.

The input(s) into a Kalman filter are everything you know about the 
problem at hand.  In your case I assume that it is just the tracker's x 
and y outputs, but if you had any prior knowledge about the ball motion, 
or about the tilt of the table, you'd want to find a way to include 
that, too.

The output(s) from a Kalman filter are everything you want to know about 
the problem at hand.  In your case I assume that this will be a four 
element vector, with x and y velocity and position.

In your case, the outputs from the Kalman filter are also the states of 
the filter -- velocity and position are all you need to make good 
estimates of velocity and position.

If you make your inputs into a vector and call it 'u', and call your 
outputs 'y', then the core operation in a discrete-time Kalman filter 
can be expressed as:

y_k = A_k y_{k-1} + B_k u_k.

Note the subscripting -- not only do you get a new input each time, but 
your gains change.

In the above equation the A matrix is called the "state transition 
matrix", and the B matrix is called the "input matrix".  These matrices 
change with time; what they encode is the very best that you know about 
how the estimates should change with every bit of new information. 
These matrices are found by answering the question "if I take the prior 
state of the system and it's current input, what are the very best 
values of A and B to get the very best estimate of it's current state?"

Much of the complexity of Kalman filter design goes into answering the 
above question, but remember that at it's heart the Kalman filter is 
just a simple linear* system, albeit time varying.

For your system, if you can safely assume that the snooker table surface 
is frictionless and if you have no prior knowledge of the ball's 
position and velocity then your Kalman filter will devolve into a 
computationally efficient way to do a least-squares curve fit to the x 
and y data, to find the 'a' and 'b' in x = a*t + b (t being your time 
variable).  Keep this in mind -- the Kalman filter problem is stated in 
a manner that for the assumptions I've given above there can be no other 
answer.  So should you construct a Kalman filter with those assumptions 
and get a different answer then you've made an error.

If you _can_ assume a frictionless surface (which you can only do if the 
ball is traveling fairly fast) then you don't have to construct a 'real' 
Kalman filter -- you can just go to your nearest statistics book and 
pull out the single-variable least-squares fit for a line and use that 
equation on both the x position and y.

If you _can't_ assume a frictionless surface (i.e. the ball will slow 
down significantly over the length of time that you're tracking it, 
perhaps even stop) then you will have to use something fancier.  You'll 
either have to assume that the ball is being given some unknown 
acceleration, or you'll have to use an extended Kalman filter (friction 
is a nonlinear phenomenon).

I hope this helps -- I have a feeling it's too long, too short, not 
clear enough and not detailed enough.

* A Kalman filter is only optimal for a certain set of cost criteria, 
system behavior, and noise distributions.  An "Extended Kalman Filter" 
is used when you can't assume that costs, behavior and noise fit into 
these sets.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Posting from Google?  See http://cfaj.freeshell.org/google/

ProdigalSon wrote:
> 
> Hi,
> 
> I am currently doing a object tracking project in computer vision. My
> project involves tracking snooker balls on a snooker table. The balls
> are tracked frame by frame but the resulting tracking information is
> noisy and does not follow the smooth linear motion of the balls on the
> table. To smooth the resulting information i am trying to use the
> kalman filter as i assumed this was what it was created for.
> 

It doesn't seem that you have really defined your problem/solution very
well. I would say you could state your problem like this: You need to
know where the balls are at regular instants of time and you need to
figure out where the balls go between those instants. I can see how
various things can lead to adding error (or noise) to the estimation of
where the balls are at each frame instant, but smoothing isn't going to
be always the right solution to that problem. If a ball changes course
between frames (due to collision) you don't want a smoothed
representation of that in your model. So you need to be selective about
what you smooth. 
	So it seems you need to model the motion as generally well behaved
smooth motion in between collision nodes. So the task would seem to be
to identify the collision nodes and to smooth the paths between nodes.
That seems easy to say but since the 2 depend on each other it probably
alot more difficult to do. The nodes need to be defined in 2d, but the
motion between nodes should be able to be dealt with as two 1d problems. 
	So the smoothing the samples between nodes could be done independently
in X and Y. That is the input to your smoothing filter in the x
direction would be distance traveled in x between each frame (with no
collisions). That is to say, the change in x from one frame to the next
should not be erratic but should graph as a smooth curve (and usually
descending).
	I wouldn't think you need anything like an adaptive filter to
accomplish this. At least it would seem that starting with something
simple like low pass filter would tell you if you need something more
complicated.

-jim   


> The issue i am having is that i am not a very mathematical person but i
> am willing to learn. The kalman filter looks very challenging and i
> dont know how to go about smoothing the tracking data so that i get a
> smooth, noise-less motion.
> 
> Can someone try and explain the steps in laymans terms to help someone
> who isnt so mathematically minded. I have read various online tutorials
> and the kalman introduction paper and they try and explain it simply
> but i am still finding it hard to work out what the inputs and outputs
> are into the filter, what needs to be set up before running the filter
> and the matrix the filter uses and what each matrix represents.
> 
> I know i am asking a lot but it would be helping me greatly. Also if
> you think that there is a better solution to my problem that is easier
> to implement then feel free to let me know.
> 
> Thanks and kind regards
> 
>     Paul
> -=---------=-

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----