Inaccurate/bad/jumping GPS

[dratasich]

I have very inaccurate results of the distance and overall route of a workout (at least here in Vienna ;).

I started to add the Kalman filter from Oleg Katkov who wrote a very nice documentation of his implementation (MIT license).

After a 2-3 attempts with an added KF, it gives me already better results (especially regarding the total distance). Yes, the red track still looks bad :( but on the long run (blue track) its much better (it even matches the street for the first time :) ...

(track length: "yellow" RunnerUp 530m, true 280m; "red" RunnerUp+KF 320m, true 300m, walking with the phone swinging in the hand; "blue" RunnerUp+KF 1.3km, true 1.2km, walking with the phone in the backpack)

I think it can get even better (parameters not yet changed/optimized). I can do a lot more smoothing.

However, before I do a pull request I want to tweak the filter parameters. So this is more or less a notification, that somebody/me works on an KF for RunnerUp ;).

My current status is in my develop branch. Probably related issues #257, #632, #659 and PRs #660.

Best, Denise

[gerhardol]

I looked in to filtering some time ago but did not find a good filter. As the filter is also using the speed and accuracy information from the GPS, it could improve the filtering. The distance (and especially speed) will improve, but I cannot see that hitting the streets will. Looking forward to this!

If this filter is updated, I suggest you isolate the changes.See elevation adjustment, but this should probably be in both latest and froyo.

https://github.com/dratasich/runnerup/tree/develop/app/latest/java/org/matthiaszimmermann/location/egm96

[dratasich]

I expect that the jumping comes from GPS reflections / the "high" buildings. GPS is ok in the countryside.

I tried various settings and improvements of the existing implementation by Katkov (still the results do not look like the one he posted). The linear acceleration which I had to derive from raw acc values in API8 could be the reason (it drifts, has an offset and makes things worse in suburban area / countryside).

What would be your target API for the filtering? Will it stay at 8 and 15? Up to now, I tried the KF, moving average for froyo only. But I'm open to try android.hardware.sensors (rotation, linear acceleration) of later APIs (I guess and hope that Android provides some pre-filtering of acceleration and rotation). Still I could provide a small KF or moving average for froyo if it shows better results on your phones.

[gerhardol]

The plan was to drop Froyo build completely and raise min SDK for "latest" to Lollipop. However, @12people has refreshed the user interface and wanted to keep Froyo some more. Froyo must be dropped to update Play services eventually though.

MinSDK for latest can be raised if that helps(question is if those previously on latest should get the refreshed Froyo build or stay on old-latest). That makes development more difficult though, wrappers can be used to some extent. Not sure if that is possible here. Maps, graphs, elevation adjustment is done with wrappers, to some extent support libs too.

TYPE_ROTATION_VECTOR (fused sensors) was added in API 20 (KitKat), so Marshmallow may be a target.

[gerhardol]

Any progress?

[dratasich]

Sry, I didn't have time last week. The result of the KF is not satisfactory yet to be merged (I suspect a bug in my code or timing issues).

[gerhardol]

Any progress?

[dratasich]

My phone's GPS seems to be quite bad compared to others (distance of a run is +0.5km off on a 4.5km track due to noise). I've played around with various configurations (on offline data).

• I got the best results when I used a KF only with GPS position (without accelerometer) and additionally reducing the number of points -- this helped a lot (this would also significantly decrease the size of the GPX files, e.g., 300kb to 11kb for about 2km).

I didn't dare to make these changes in the RunnerUp code yet, because it would affect the whole pipeline (track to save). When I have time (unfortunately not before May), I think I would try to simplify the tracks (using existing implementations, e.g., simplify-java) before saving the points. But I didn't have a look into this part of RunnerUp yet.

[dratasich]

Status update: I've added simplification of the path/track at the end of an activity, branch simplify_track. I didn't create a pull request yet.

Basically, the algorithm removes points. Think of a straight line where every 1s a point is logged - the algorithm removes intermediate points, i.e., keeps only the end points of the line; given an allowed error (tested with 3m).

• Reduction of location points
  • Smooths path/track
  • Smooths graphs (disable "smooth pace graph" for testing)
  • Significantly reduces the size of exported activities (test with gpx: 45min biking, 1s GPS poll, reduces from 900kB to 55kB -- of course this depends on the track)

What needs to be tested:

• Check HR graph. Because other measurements (e.g., HR) are part of a location entry in the database, also these are reduced.
• Check if pace graph is correctly calculated when time intervals between points are different (no periodic location points any more!). Disable "smooth pace graph" for testing.
• Check simplification when a specific resolution is kept (quantity vs. quality).

My branch simplify_track uses simplification as follows, for testing: on save activity, the current activity is copied and simplified -> two activities with original path and simplified path.

What do you think? Shall we add an option for simplification?

[gerhardol]

Great! Will review. Please open a pr, easier that way. But options (in Recording) to enable the functionality and for edit activity should be added, (maybe to export without modifying the original too).

[dratasich]

PR: #836

[darkdragon-001]

@gerhardol Any news?

I will add some thoughts:

@dratasich: I expect that the jumping comes from GPS reflections / the "high" buildings. GPS is ok in the countryside.

Uber Engineering posted a very interesting blog post about their approach of fixing urban environments with high buildings by taking signal strength (SNR) into account to guess reflections.

@dratasich: I got the best results when I used a KF only with GPS position (without accelerometer) and additionally reducing the number of points -- this helped a lot (this would also significantly decrease the size of the GPX files, e.g., 300kb to 11kb for about 2km).

If I understand the Ramer–Douglas–Peucker algorithm correctly, it removes points which only have a small distance from the straight line connecting its neighbors. While this is good for compression, I don't think it is suitable to improve GPS accuracy since the outliers (points with big distance from the straight line) are mostly responsible for the inaccuracy in distance. I think the KF looked quite promising. While an offset can easily be removed, drifts are more difficult. More advanced techniques like loop closure (for round trips) could help here.

How can I record test data (all GPS, accelerometer, HR data) to test these algorithms offline?

Did anyone try out the FusedLocationProviderClient in the latest Google Location Services API from Google Play services? Would be interesting to compare the Google algorithms with self-baked ones!

[darkdragon-001]

Approach 1: Moving average Data points should be low-pass filtered with a symmetrical exponential moving average (e.g. weights 1 2 5 2 1). If stronger smoothing is desired, a normal moving average (equal weights) should be tested. It requires a constant sampling rate.

Optimization: When the calculations of all smoothened data points are performed on the original data without propagation, which is what I suggest, the data set can be split arbitrarily and thus parallelized easily. This does not work in place though an requires double the storage of the track, which should still not be a problem.

Approach 2: Outlier correction This algorithm is basically the opposite of Doublas-Peucker algorithm: Removing/weakening the points which are far away from the line connecting the neighbors (outliers/jumps). Of course the parameters must be optimized for the activity: The amount of weakening (w₁, w₂) should depend on the maximum distance one can overcome between two data ponts (maximum speed of activity, timely distance between data points). Again, this approach requires equidistant data points. Although I am wondering if this is mathematically equivalent to the symmetrical moving average for constants factors w :thinking: Further, outliers far away have data points with small angles between the neighboring lines, so they should have less confidence. So setting w based on this angle could yield some additional improvements. On the other hand, for equidistant data points the angle directly depends on the distance from the line, so might not contribute additional information here :thinking:

Any thoughts and comments are welcome!

[gerhardol]

@gerhardol Any news?

The PR is still in review, some comments.

Did anyone try out the FusedLocationProviderClient

The open source aTrainingTracker app uses Fused location. I see very small differences there. Note that signal strength is not available in the GPS API (just accuracy). The phone GPS firmware is tuned to give the best current position. A sports clock is tuned to give the best relative position, using the history. Especially Garmin has quite poor GPS but reports the distance quite well.

A stronger filter (likely Kalman) can remove outliers and fused location could improve, but will likely not improve a lot. The information on the driver level is more detailed than in the GPS API.

I am not working actively on this now. All information in GPS API can be saved to .gpx logs, so anyone can use the logs to test better solutions, also without updating the app.

L5/E5 (GPS dual band/mode) is a better longterm option. Just in a few flagship phones so far, not enough satellites too.

[darkdragon-001]

Note that signal strength is not available in the GPS API (just accuracy).

You can get the carrier to noise density (signal-to-noise ratio for satellite communications) of every satellite in the Android SDK.

I am not working actively on this now. All information in GPS API can be saved to .gpx logs, so anyone can use the logs to test better solutions, also without updating the app.

This is only GPS information, right? Accellerometer and heart rate need to be recorded manually?

L5/E5 (GPS dual band/mode) is a better longterm option. Just in a few flagship phones so far, not enough satellites too.

Do you mean using GPS and Galileo simultaneously? My cheap and old Xiaomi Mi A1 already supports GPS, GLONASS, GALILEO, BEIDOU and shows all those satellites simultaneously.

[gerhardol]

https://medium.com/@sjbarbeau/dual-frequency-gnss-on-android-devices-152b8826e1c

S/n is in quite new api and not correlated to each position reported. But it could be saved too.

[darkdragon-001]

https://medium.com/@sjbarbeau/dual-frequency-gnss-on-android-devices-152b8826e1c

Thanks for pointing me to this article. These improvements allow to cancel out the atmospherical perturbations like weather. Curious to test when I get a new device!

S/n is in quite new api and not correlated to each position reported. But it could be saved too.

In earlier API versions, there was [getSnr()](https://developer.android.com/reference/android/location/GpsSatellite.html#getSnr()).

[dratasich]

How can I record test data (all GPS, accelerometer, HR data) to test these algorithms offline?

All information in GPS API can be saved to .gpx logs, so anyone can use the logs to test better solutions, also without updating the app.

I tried some algorithms offline, here: https://github.com/dratasich/gpx-pipeline/blob/master/plot.py For anyone interested to further improve the path/position estimation...