The Kalman Filter is a math transformation to guess at unknown stuff based on known stuff. It’s been used in mission critical applications such the Apollo lunar landing, and other safety critical systems like collision avoidance, and pedestrian detection.
In the examples below, it’s used in a computer program designed to locate, in real time, objects (i.e. a bicycle) using a fusion of input from Laser and Radar. It’s a two step process, it first predicts information based on it’s current belief, then it updates it’s belief with new information.
The filter expects noise from sensors, noise in the environment, and general uncertainty. For example, the tires may slip, sensor may have an error, etc.
Ok the fun part! :) A thought experiment for an intuition behind a 1 dimensional Kalman filter is this:
Picture a person walking in a straight line. They walk forward for 3 seconds. At each second, they take 1 step. If you were to guess where they would be if they walked for 1 more second, you would likely say “Forward, 1 step”.
This is actually quite interesting. The direction, continuing to go forward, is fairly obvious, if you draw a line through the first 3 steps and continue drawing you will arrive dead ahead. ie x x x -> x. The ‘1 more step” is not. Why not 2 steps? or 3? or 10?
We are guessing at the velocity of the person walking, based on our prior belief of the person’s position. We are inferring an hidden variable (velocity) from the visible variable (position).
Since we know the person moved 3 steps in 3 seconds we guess in the future they will continue to move 1 step per second. That’s the core idea.
Now we can extend that idea into the standard Kalman filter with more dimensions and an uncertainty component represented by Gaussian distributions. For further detail see this excellent technical explanation.
Extended Kalman filter
The Kalman filter can’t handle curves as input. The Extended filter introduces a workaround that transforms the curve to a line before it hits the Kalman filter. This is needed for Radar. We use a Jacobian Matrix to transform the curve into an straight line approximation. Code example.
Unscented Kalman filter
Instead of using one point (Jacobian) to transform the curve into a line, they use a bunch of points (ie 15). These “Sigma” points lead to a high resolution belief and generally better results. Now the actual work of generating/predicting/updating/ etc. these Sigma points is fairly involved, and that’s what this project is focused on → Code example
The running joke is that the Unscented Kalman filter is called “Unscented” because the team that invented it felt the Extended filter’s performance was “stinky” and prove a point they called the better performing one “Unscented”!
Here is the real reason, as explained by the inventor Jeffrey Uhlmann:
One evening everyone else in the lab was at the Royal Opera House, and as I was working I noticed someone’s deodorant on a desk. The word “unscented” caught my eye as the perfect technical term. At first people in the lab thought it was absurd — which is okay because absurdity is my guiding principle — and that it wouldn’t catch on. My claim was that people simply accept technical terms as technical terms: for example, does anyone think about why a tree is called a tree?
Within a few months we had a speaker visit from another university who talked about his work with the “unscented filter.” Clearly he had never thought about the origin of the term.
Quote source: http://ethw.org/First-Hand:The_Unscented_Transform Thanks to Vivek Yadav for catching a mistake in an earlier draft of this.
Thanks for reading! :)
The projects, and the example, have come from being a student in the Udacity Self-Driving Car Nano degree program.