Reduce GPS data error on Android with Kalman filter and accelerometer

https://blog.maddevs.io/reduce-gps-data-error-on-android-with-kalman-filter-and-accelerometer-43594faed19c

by Gen1us2k • 8 years ago

118 30 8 years ago

blog.maddevs.io

jakecopp• 8 years ago

This is great! How would accelerometer + algorithm power usage compare to GPS?

Is there any reason this isn't already used?

fisian• 8 years ago

This principle is already sometimes used for determining the position of UAVs (e.g. Quadcopters). So absolute position is provided by GPS and short term movements can be calculated from accelerometers and other sensors.

Of course sensor data can only provide a relative position. After longer intervals of solely relying on the relative sensor-based position small errors can accumulate which makes "synchronization" with GPS necessary to retain accuracy.

dustinmr• 8 years ago

It’s fun to think about how related that is to maritime navigation and in particular Dead Reckoning.

The same thing has been taught for hundreds of years in that realm. Her you take it 3D.

random4369• 8 years ago

The power consumption of computing the kalman filter is negligible compared to the power consumption of the gps module.

I thought that ios and android did this already for a long time.

molszanski2• 8 years ago

I was 100% sure that both iOS and Android give you that by default unless you opt out and request raw GPS data.

Good job fixing that externally!

TickleSteve• 8 years ago

"raw" data from the GPS chipset has already been through a Kalman filter... its how they form a 'fix' based on constant measurement inaccuracies.

Of course the difference here is that the extra accelerometer data is involved. It's been a few years since I last worked on GPS chipsets, but I would be surprised if they didn't now incorporate one for this exact reason.

edit: They do: https://www.broadcom.com/products/wireless/gnss-gps-socs/bcm...

"Broadcom's second-generation sensor integration technology, adding accelerometer, gyroscope, magnetometer and altimeter outputs to the positioning engine"

molszanski2• 8 years ago

I get your point. I just assumed that in a world of billions of various hardware solutions, OS level sane software defaults would be reasonable to expect. Even if GPS sensors would not provide that kind of filtering. And since OS generally has a very good access to all the sensors... you get the rest.

antirez• 8 years ago

I wonder if filtering just based on the GPS previous positions (thus averaging different errors to kinda cancel them) works almost equally well in this case, since cars tend to move in a quite smooth way.

ballooney• 8 years ago

'almost' equally well is a bit qualitative; one of the main advantages of a kalman filter is that it's predictive and so doesn't suffer from the lag that a simple low-pass filter has. But as you say, a car is not a missile so the degree to which the performance of a LPF is worse than a KF may not be significant.

michaelt• 8 years ago

In the case of sat nav software, the software is at its most important when users aren't moving in a smooth way.

Sure, 99.9% of gps measurements on a sat nav are users going in a straight line - but it's when navigating complex junctions with many turns, traffic circles etc that users most need the sat nav's guidance.

toxik• 8 years ago

Kalman filters do exactly that. Add in accelereometer and you have a basic INS.

zb• 8 years ago

Calculating a position (and time) from the GPS data is basically a case of throwing it in a matrix and calculating the fix with the least squared error, and many receivers do just just. However, many (most?) actually use a Kalman filter, which takes into account the estimated error from the previous fix (and calculates a new estimated error to be taken into account for the next fix). So what you're suggesting is already done inside the receiver.

This is also the ideal place to add in additional data such as from an accelerometer. If you only have the calculated position (and speeds, which are useful for figuring out how far you're actually likely to have moved since the last fix) but not the error estimates to work on then you've thrown away much of the useful data.

IshKebab• 8 years ago

Converting coordinates to string-based hashes is quite weird. Why not just find which grid square they are in and used the flat index of it?

tuukkah• 8 years ago

Hmm, you don't have to convert the geohash to a (base-32) string - int64 may be just as fine.

Perhaps they can take advantage of the better locality of Z index compared to flat index, and/or they want to store higher precision and do lookups with varying precisions (grid sizes)?

Gen1us2k7• 8 years ago

We use geohash because it's really fast and we can control precision. We don't need to store any information about grid and we don't need to convert coordinates to spherical view.

randomerr• 8 years ago

I would love to plug a cheap accelerometer an get these efficiencies. But it leaves me some questions:

* Will these techniques work on a stock Android device for stock programs (ie Google Maps)?

* Will the different (extra?) calculations cause my processor's calculation to go up, killing battery life? I didn't see any testing on this and your statements seemed questionable - "Herewith, the algorithm should not consume whole battery within 3 minutes as well as all available RAM."

Doesn't Android already have similar filters? I would assume they do since they've been in the business for a while.

This looks like great theoretical ideas. I hope you can use it to get a job at Google or turn it into a marketable product.

Gen1us2k7• 8 years ago

1. It won't be working on stock devices, unfortenately. It's library to integrate to your android application

2. Extra calculations don't consume as much battery as GPS and with this technique we use GPS less often. In other hand we use accelerometer and magnetometer. I tested this by eye :) and didn't find big difference between GPS only solution and presented solution. But as written in article - it doesn't accumulate coordinates.

3. Android already has similar filters. They use Kalman filter and many interesting things. See here : https://android.googlesource.com/platform/frameworks/native/... and other files. They did really huge work here :)

londons_explore2• 8 years ago

For 1., on android you can have third party location providers I believe, and then any app could use it.

opencl• 8 years ago

This is a pretty old/widely used technique. Here's a paper about it from 1999, implementing on a DOS PC.

http://www8.cs.umu.se/research/ifor/dl/LOCALIZATION-NAVIGATI...

The really interesting stuff more recently is using RTK software to get accuracy on the order of 10s of cm with cheap GPS receivers.

https://wiki.openstreetmap.org/wiki/RTKLIB

TeMPOraL• 8 years ago

RTK stands for Real Time Kinematics, for those who (like me) wondered.

Gen1us2k7• 8 years ago

Yes, that's is. This is not unique solution. We collected all information in one article and described what we did.

emj• 8 years ago

With some hackery you can get an RTKLIB compatible GPS for as low as $30, but one should expect to pay no less than $200-$400 for a ready made solution with an useable antenna. Costs go up fast from there.

mparr4• 8 years ago

Has anyone worked with the Madgwick filter (mentioned in the post)? Any high level takeaways to share?

I work in marine robotics and am interested in experimenting with it to see how it could improve our current nav solution.

wintermutesGhst• 8 years ago

Neat article covering a lot of topics, but I'm fairly surprised by these results.

At one point I was looking at building a navigation module for a car using a similar setup to smooth noise, but after some searching I found a paper which showed essentially no benefit from the accelerometer/gyro. The 'drift' on the accelerometer meant it could only filter very fast changes, which the Kalman filter on the GPS board already handled quite well.

I should dig out my little MTK3339 and try to replicate!

Gen1us2k7• 8 years ago

Yes, accelerometer's "drift" became a world of pain for me, but android developers did great work for that and all we need to do is to add calibration step to application and use their "linear acceleration" sensor.

petermcneeley• 8 years ago

I wonder if terrain roughness features could be used collectively to form extremely accurate positioning for vehicles. Collect data on bumps, slopes, curves, orientation and then use this data to predict most probable current location based on accelerometer data. This would be accurate in cases where "Dead reckoning" is inaccurate and vis versa. (related concept https://en.wikipedia.org/wiki/TERCOM)

Reduce GPS data error on Android with Kalman filter and accelerometer

Related Stories