Kalman Filter - R.E.Kalman 1960

sources :
1- http://www.innovatia.com/software/papers/kalman.htm

2- http:// www.cs.unc.edu/~welch/kalman

3- http://www.cs.unc.edu/~welch/media/pdf/kalman_intro.pdf

4- http://http//en.wikipedia.org/wiki/Kalman_filter

A good filtering algorithm can remove the noise while still retaining the useful information.A Kalman Filter produces values that tend to be closer to the true values of some observed value set using measured values that are observed over time containing noise/random variations and other inaccuracies.
[? somewhat similar to the ID3 algorithm]
The Kalman Filter produces estimates of the true values of measurements and their associated calculated values by predicting a value, estimating the uncertainty of the predicted value, and computing a weighted average of the predicted value and the measured value.
The estimates produced by the method tend to be closer to the true values than the original measurements because the weighted average has a better estimated uncertainty than either of the values that went into the weighted average.



Filtering:

An example is filtering out noise from our surroundings. If we paid attention to all the little noises around us we would go crazy. We learn to ignore superfluous sounds (traffic, appliances, etc.) and focus on important sounds, like the voice of the person we're speaking with.


Mathematics:

The question which is addressed by the Kalman filter is : Given our knowledge of the behavior of the system, and given our measurements, what is the best estimate of position and velocity?

Consider the problem of estimating the variables of some system. In dynamic systems (that is, systems which vary with time) the variables are denoted as state variables. Let vector X represent the system variables. Assume that the system variables, represented by the vector x, are governed by the equation below.

xk+1 = Axk + wk

wk is random process noise
subscripts on the vectors represent the time step

Suppose that X represents the time step of a spacecraft which is accelerating. X consists of position - p & velocity - v .





ak is the random time-varying acceleration, and T is the time between step k and step k+1.

Now suppose we can measure the position p. Then our measurement at time k can be denoted

z_k = p_k + v_k

where v_k is random measurement noise.

How can we determine the best estimate of the system variables? We can do better than just take each measurement at its face value, especially if we suspect that we have a lot of measurement noise. Suppose we assume that the process noise w_k is white with a covariance matrix Q. Further assume that the measurement noise v_k is white with a covariance matrix R, and that it is not correlated with the process noise.

The Kalman filter is formulated as follows, on average :

1. estimate of the state will equal the true state.
2. our algorithm gives the smallest possible estimation error.

Kalman filter is the estimation algorithm which satisfies these criteria.One of the formulations is :
(In the equations, the superscript –1 indicates matrix inversion and the superscript T indicates matrix transposition. S is called the covariance of the innovation, K is called the gain matrix, and P is called the covariance of the prediction error. )

Sk = Pk + R





--5

The first term used to derive the state estimate at time k+1 is just A times the state estimate at time k. This would be the state estimate if we didn't have a measurement.The second term in Equation 5 is called the correction term, representing how much to correct the propagated estimated due to our measurement. If the measurement noise is much greater than the process noise, K will be small (that is, we won't give much credence to the measurement), & vice versa

Example of a simulated system generated using MATLAB shows how well the Kalman Filter was able to estimate the position.
















Applications :

This is a simple implementation of a KF I happend to come across, that tracks the movement of a soccer player.

KF can be thought of as operating in two distinct phases: predict and update. In the prediction phase, the player's old position will be modified according to the physical laws of motion (the dynamic or "state transition" model) plus any changes produced. Not only will a new position estimate be calculated, but a new covariance will be calculated as well. Perhaps the covariance is proportional to the speed of the player because we are more uncertain about the accuracy of the dead reckoning estimate at high speeds but very certain about the position when moving slowly. Next, in the update phase, a measurement of the player's position is taken. Along with this measurement comes some amount of uncertainty, and its covariance relative to that of the prediction from the previous phase determines how much the new measurement will affect the updated prediction. Ideally, if the dead reckoning estimates tend to drift away from the real position, the measurement should pull the position estimate back towards the real position but not disturb it to the point of becoming rapidly changing and noisy.

Dead reckoning- The player's position can be estimated by integrating the velocity and direction over time, determined by keeping track of the amount the acceleration is put in and how much the body's turned. provide a very smooth estimate of the position, but it will drift over time as small errors accumulate.