6 ms·

How Kalman Filters Work

377 points by slackpad 10y ago

tnecniv 10y ago
Nice writeup. I use these filters quite often (especially the particle filter). Very powerful tools.
- personjerry 10y ago
  In what context do you use them?
  - yarou 10y ago
    They're used quite extensively in GPS/positioning.
  - makmanalp 10y ago
    Basically situations where you have a few data sources for the same thing, all with their own margins of error, update rate, etc. And you want to combine them to get one better data point. Eg in robotics, you can put together GPS, vision (e.g. from visual markers or perceived movement) and wheel encoder (how many times did the wheel spin, where do I think I am based on that) data to get one much more accurate location point.
  - tnecniv 10y ago
    Robotics in different contexts. I've used two different styles of Kalman filter for cleaning up data from computer vision based pose/velocity estimation. I also used a particle filter as a way of tracking humans in thermal images from a camera on a UAV.
  - dharma1 10y ago
    https://www.youtube.com/watch?v=xMf-XW8vv0k https://www.youtube.com/watch?v=xMf-XW8vv0k
aethertap 10y ago
I spent quite a bit of time working through the Kalman filter content in Sebastian Thrun's book "Probabilistic Robotics"[1] a while back. I ended up making some notes [2] of the process that might be of interest to others if you're trying to get a grasp of everything that's going on with that process. One other person on the Internet that I know of thought they were useful, so I'll post the link here. This was part of a project I was working on to build a K-8 robotics curriculum (no, not teaching the kids Kalman filters, but I wanted to know how it all worked before starting to make a curriculum). The book is really good if you're wanting to make robots that can navigate uncertain environments. Edit: I wish I'd had access to this article when I was going through that process. This is really well done. 1. http://amzn.com/0262201623 http://amzn.com/0262201623 2. https://github.com/aethertap/probabilistic-robotics https://github.com/aethertap/probabilistic-robotics
- radioactivity 10y ago
  There is also a class at Stanford that builds up all the theory of the Kalman filter, starting with elementary probability [1]. The slides are all posted, and while they wouldn't be great to learn the material from, they're an excellent reference (and go into more depth on multivariate Gaussians and estimation theory than Probabilistic Robotics). 1. http://engr207b.stanford.edu/ http://engr207b.stanford.edu/
- WaxProlix 10y ago
  Weird that Sebastian Thrun would come up again - he's on the front page stepping down as Udacity CEO right now [1], too, and I'd never heard of the guy before. 1 https://news.ycombinator.com/item?id=11562468 https://news.ycombinator.com/item?id=11562468
  - emcq 10y ago
    That's because he has had tremendous impacts on computer science and robotics for many years now as a pioneering professor at CMU and Stanford. He was a leading force in the DARPA grand challenge which showcased self driving car technologies long before it was cool. He led the self driving car project at Google-X, developed street view, and cofounded Udacity. It's not weird; the guy is brilliant and has had many large impacts to the community as a whole.
andhess 10y ago
Awesome to see some Kalman filters! Takes me back to my undergrad :-)
aswanson 10y ago
Best breakdown from a conceptual as well as mathematically precise description I have ever read.
kxyvr 10y ago
The best presentation that I've ever seen on what a Kalman filter really is comes from a SIAM Review article, "A Fresh Look at the Kalman Filter" by Jeffrey Humpherys, Preston Redd, and Jeremy West http://epubs.siam.org/doi/abs/10.1137/100799666 http://epubs.siam.org/doi/abs/10.1137/100799666 It sets up the discrete-time linear system and then uses a minimization principle to show what's going on. I can highly recommend it especially for people coming to Kalman filters from a math or optimization background.
- chombier 10y ago
  Yes! If you put the process covariance aside, then Kalman filtering really just is a linear least squares problem solved incrementally, using Woodbury formula to solve the normal equations efficiently.
  - CraigJPerry 10y ago
    Now I know how my wife feels when she asks what I'm up to...
platz 10y ago
I find it odd that nowhere in the 3-part series is discussed the relationship between kalman filters and hidden markov models.
- karussell 10y ago
  Thanks! I've not yet dived deep into kalman filters but only done hhm a bit and therefore hoped to get exactly this relationship uncovered. Can you summarize or link to this relationship :) ?
  - thisisdave 10y ago
    In both models, there's an unobserved state that changes over time according to relatively simple rules, and you get indirect information about that state every so often. In Kalman filters, you assume the unobserved state is Gaussian-ish and it moves continuously according to linear-ish dynamics (depending on which flavor of Kalman filter is being used). In HMMs, you assume the hidden state is one of a few classes, and the movement among these states uses a discrete Markov chain. In my experience, the algorithms are often pretty different for these two cases, but the underlying idea is very similar.
kshitijl 10y ago
For people familiar with Gaussian Processes, it may help to think of Kalman filters as a special case of GPs where you can construct the inverse of the covariance matrix directly, and this inverse has a tridiagonal structure. Thus, a really efficient Bayesian regression algorithm.
- deleted 10y ago
  [deleted]
rboyd 10y ago
I'd like to add Roger Labbe's free book "Kalman and Bayesian Filters in Python" to the mix. Along with Thrun (which he cited to point me at), this is the resource that finally drove it home for me. https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt... For people wondering about application, one of the popular recent uses is for sensor fusion in virtual reality.
- laen 10y ago
  More on application: Historically, KFs are used extensively for sensor fusion in the aviation industry. Aircraft (and missiles) use internal gyroscopes(INUs) for navigation in association with GPS. The INUs are prone to drifting and corrected with Kalman Filter estimated real time drift errors. These error rates are computed while GPS information is available and continue to be corrected in the case of GPS loss.
fuzzythinker 10y ago
Another nice explanation, a bit more visual. http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/ http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures...
danpalmer 10y ago
What's even more interesting is that there is some experimental evidence to suggest that the human brain uses Kalman filters for certain things. I think this was one of the papers about it: http://papers.nips.cc/paper/3665-a-neural-implementation-of-the-kalman-filter.pdf http://papers.nips.cc/paper/3665-a-neural-implementation-of-...
rsp1984 10y ago
What many don't know about Kalman Filters (and took me a while to realize as well) is that it's just recursive least squares. It is just formulated a bit differently such that incremental update complexity depends of the dimensionality of the observation, not the dimensionality of the estimated state. Depending on the dimensions this can be a lot more efficient.
univalent 10y ago
Adaptive Filter Theory by Simon Haykin is the single best engineering book I used. http://www.amazon.com/Adaptive-Filter-Theory-Simon-Haykin/dp/013267145X http://www.amazon.com/Adaptive-Filter-Theory-Simon-Haykin/dp... Covers Kalman filters in great detail. Did anyone else us it?

377 points by slackpad 10y ago

tnecniv 10y ago

Nice writeup. I use these filters quite often (especially the particle filter). Very powerful tools.

personjerry 10y ago
In what context do you use them?
- yarou 10y ago
  They're used quite extensively in GPS/positioning.
- makmanalp 10y ago
  Basically situations where you have a few data sources for the same thing, all with their own margins of error, update rate, etc. And you want to combine them to get one better data point. Eg in robotics, you can put together GPS, vision (e.g. from visual markers or perceived movement) and wheel encoder (how many times did the wheel spin, where do I think I am based on that) data to get one much more accurate location point.
- tnecniv 10y ago
  Robotics in different contexts. I've used two different styles of Kalman filter for cleaning up data from computer vision based pose/velocity estimation. I also used a particle filter as a way of tracking humans in thermal images from a camera on a UAV.
- dharma1 10y ago
  https://www.youtube.com/watch?v=xMf-XW8vv0k https://www.youtube.com/watch?v=xMf-XW8vv0k

aethertap 10y ago

I spent quite a bit of time working through the Kalman filter content in Sebastian Thrun's book "Probabilistic Robotics"[1] a while back. I ended up making some notes [2] of the process that might be of interest to others if you're trying to get a grasp of everything that's going on with that process. One other person on the Internet that I know of thought they were useful, so I'll post the link here. This was part of a project I was working on to build a K-8 robotics curriculum (no, not teaching the kids Kalman filters, but I wanted to know how it all worked before starting to make a curriculum). The book is really good if you're wanting to make robots that can navigate uncertain environments. Edit: I wish I'd had access to this article when I was going through that process. This is really well done. 1. http://amzn.com/0262201623 http://amzn.com/0262201623 2. https://github.com/aethertap/probabilistic-robotics https://github.com/aethertap/probabilistic-robotics

radioactivity 10y ago
There is also a class at Stanford that builds up all the theory of the Kalman filter, starting with elementary probability [1]. The slides are all posted, and while they wouldn't be great to learn the material from, they're an excellent reference (and go into more depth on multivariate Gaussians and estimation theory than Probabilistic Robotics). 1. http://engr207b.stanford.edu/ http://engr207b.stanford.edu/
WaxProlix 10y ago
Weird that Sebastian Thrun would come up again - he's on the front page stepping down as Udacity CEO right now [1], too, and I'd never heard of the guy before. 1 https://news.ycombinator.com/item?id=11562468 https://news.ycombinator.com/item?id=11562468
- emcq 10y ago
  That's because he has had tremendous impacts on computer science and robotics for many years now as a pioneering professor at CMU and Stanford. He was a leading force in the DARPA grand challenge which showcased self driving car technologies long before it was cool. He led the self driving car project at Google-X, developed street view, and cofounded Udacity. It's not weird; the guy is brilliant and has had many large impacts to the community as a whole.

andhess 10y ago

Awesome to see some Kalman filters! Takes me back to my undergrad :-)

aswanson 10y ago

Best breakdown from a conceptual as well as mathematically precise description I have ever read.

kxyvr 10y ago

The best presentation that I've ever seen on what a Kalman filter really is comes from a SIAM Review article, "A Fresh Look at the Kalman Filter" by Jeffrey Humpherys, Preston Redd, and Jeremy West http://epubs.siam.org/doi/abs/10.1137/100799666 http://epubs.siam.org/doi/abs/10.1137/100799666 It sets up the discrete-time linear system and then uses a minimization principle to show what's going on. I can highly recommend it especially for people coming to Kalman filters from a math or optimization background.

chombier 10y ago
Yes! If you put the process covariance aside, then Kalman filtering really just is a linear least squares problem solved incrementally, using Woodbury formula to solve the normal equations efficiently.
- CraigJPerry 10y ago
  Now I know how my wife feels when she asks what I'm up to...

platz 10y ago

I find it odd that nowhere in the 3-part series is discussed the relationship between kalman filters and hidden markov models.

karussell 10y ago
Thanks! I've not yet dived deep into kalman filters but only done hhm a bit and therefore hoped to get exactly this relationship uncovered. Can you summarize or link to this relationship :) ?
- thisisdave 10y ago
  In both models, there's an unobserved state that changes over time according to relatively simple rules, and you get indirect information about that state every so often. In Kalman filters, you assume the unobserved state is Gaussian-ish and it moves continuously according to linear-ish dynamics (depending on which flavor of Kalman filter is being used). In HMMs, you assume the hidden state is one of a few classes, and the movement among these states uses a discrete Markov chain. In my experience, the algorithms are often pretty different for these two cases, but the underlying idea is very similar.

kshitijl 10y ago

For people familiar with Gaussian Processes, it may help to think of Kalman filters as a special case of GPs where you can construct the inverse of the covariance matrix directly, and this inverse has a tridiagonal structure. Thus, a really efficient Bayesian regression algorithm.

deleted 10y ago
[deleted]

rboyd 10y ago

I'd like to add Roger Labbe's free book "Kalman and Bayesian Filters in Python" to the mix. Along with Thrun (which he cited to point me at), this is the resource that finally drove it home for me. https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt... For people wondering about application, one of the popular recent uses is for sensor fusion in virtual reality.

laen 10y ago
More on application: Historically, KFs are used extensively for sensor fusion in the aviation industry. Aircraft (and missiles) use internal gyroscopes(INUs) for navigation in association with GPS. The INUs are prone to drifting and corrected with Kalman Filter estimated real time drift errors. These error rates are computed while GPS information is available and continue to be corrected in the case of GPS loss.

fuzzythinker 10y ago

Another nice explanation, a bit more visual. http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/ http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures...

danpalmer 10y ago

What's even more interesting is that there is some experimental evidence to suggest that the human brain uses Kalman filters for certain things. I think this was one of the papers about it: http://papers.nips.cc/paper/3665-a-neural-implementation-of-the-kalman-filter.pdf http://papers.nips.cc/paper/3665-a-neural-implementation-of-...

rsp1984 10y ago

What many don't know about Kalman Filters (and took me a while to realize as well) is that it's just recursive least squares. It is just formulated a bit differently such that incremental update complexity depends of the dimensionality of the observation, not the dimensionality of the estimated state. Depending on the dimensions this can be a lot more efficient.

univalent 10y ago

Adaptive Filter Theory by Simon Haykin is the single best engineering book I used. http://www.amazon.com/Adaptive-Filter-Theory-Simon-Haykin/dp/013267145X http://www.amazon.com/Adaptive-Filter-Theory-Simon-Haykin/dp... Covers Kalman filters in great detail. Did anyone else us it?