Smooth gps data

Question

Hi,

I'm working with gps data, getting values every second and displaying current position on a map. The problem is that sometimes (specially when accuracy is low) the values vary a lot, making the current position to "jump" between distant points in the map

I was wondering about some easy enough method to avoid this. As a first idea, I thought about discarding values with accuracy beyond certain threshold, but I guess there are some other better ways to do. What's the usual way programs perform this?

Thanks!

Answer 1

What you are looking for is called a Kalman Filter. It's frequently used to smooth navigational data. It is not necessarily trivial, and there is a lot of tuning you can do, but it is a very standard approach and works well.

My next fallback would be least squares fit. A Kalman filter will smooth the data taking velocities into account, whereas a least squares fit approach will just use positional information. Still, it is definitely simpler to implement and understand. It looks like the GNU Scientific Library may have an implementation of this.

Answer 2

One method that uses less math/theory is to sample 2, 5, 7, or 10 data points at a time and determine those which are outliers. A less accurate measure of an outlier than a Kalman Filter is to to use the following algorithm to take all pair wise distances between points and throw out the one that is furthest from the the others. Typically those values are replaced with the value closest to the outlying value you are replacing

For example

Smoothing at five sample points A, B, C, D, E

ATOTAL = SUM of distances AB AC AD AE

BTOTAL = SUM of distances AB BC BD BE

CTOTAL = SUM of distances AC BC CD CE

DTOTAL = SUM of distances DA DB DC DE

ETOTAL = SUM of distances EA EB EC DE

If BTOTAL is largest you would replace point B with D if BD = min { AB, BC, BD, BE }

This smoothing determines outliers and can be augmented by using the midpoint of BD instead of point D to smooth the positional line. Your mileage may vary and more mathematically rigorous solutions exist.

Answer 3

As for least squares fit, here are a couple other things to experiment with:

1. Just because it's least squares fit doesn't mean that it has to be linear. You can least-squares-fit a quadratic curve to the data, then this would fit a scenario in which the user is accelerating. (Note that by least squares fit I mean using the coordinates as the dependent variable and time as the independent variable.)

2. You could also try weighting the data points based on reported accuracy. When the accuracy is low weight those data points lower.

3. Another thing you might want to try is rather than display a single point, if the accuracy is low display a circle or something indicating the range in which the user could be based on the reported accuracy. (This is what the iPhone's built-in Google Maps application does.)

Answer 4

You can also use a spline. Feed in the values you have and interpolate points between your known points. Linking this with a least-squares fit, moving average or kalman filter (as mentioned in other answers) gives you the ability to calculate the points inbetween your "known" points.

Being able to interpolate the values between your knowns gives you a nice smooth transition and a /reasonable/ approximation of what data would be present if you had a higher-fidelity. http://en.wikipedia.org/wiki/Spline_interpolation

Different splines have different characteristics. The one's I've seen most commonly used are Akima and Cubic splines.

Another algorithm to consider is the Ramer-Douglas-Peucker line simplification algorithm, it is quite commonly used in the simplification of GPS data. (http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm)

Answer 5

Going back to the Kalman Filters ... I found a C implementation for a Kalman filter for GPS data here: http://github.com/lacker/ikalman I haven't tried it out yet, but it seems promising.