Reduce GPS data error on Android with Kalman filter and accelerometer(blog.maddevs.io)
blog.maddevs.io
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
30 comments
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.
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.
* 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.
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 :)
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 :)
For 1., on android you can have third party location providers I believe, and then any app could use it.
Yes, but you need to specify coefficients somehow for that and add calibration step.
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!
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!
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.
This is great! How would accelerometer + algorithm power usage compare to GPS?
Is there any reason this isn't already used?
Is there any reason this isn't already used?
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.
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.
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.
The same thing has been taught for hundreds of years in that realm. Her you take it 3D.
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.
I thought that ios and android did this already for a long time.
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!
Good job fixing that externally!
"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"
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"
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.
They give good accelerometer readings. Also they give good GPS readings. All we need to do - "fuse" this.
Android has had a "fused location provider" which does this for a long time...
That's true, but we have drivers with phones without google play services. Strange thing, but it's true :) Also sometimes we need to use phone without internet access .
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.
'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.
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.
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.
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.
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.
Kalman filters do exactly that. Add in accelereometer and you have a basic INS.
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?
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)?
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)?
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.
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.
I work in marine robotics and am interested in experimenting with it to see how it could improve our current nav solution.
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)
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