Android GPS Coordinates Scattered

Question

I have the following code below which seems to be working fine:

    // GPS Reader
    // Criteria
    Criteria criteria = new Criteria();
    //criteria.setAccuracy(Criteria.ACCURACY_COARSE); // Used when we can't get a GPS Fix
    criteria.setAccuracy(Criteria.ACCURACY_FINE); // Used when we can get a GPS Fix

    criteria.setAltitudeRequired(false);
    criteria.setBearingRequired(false);
    criteria.setCostAllowed(true);
    criteria.setPowerRequirement(Criteria.POWER_LOW);

    LocationListener locationListener = new MyLocationListener();
    LocationManager lm = (LocationManager) getSystemService(Context.LOCATION_SERVICE);
    lm.requestLocationUpdates(lm.getBestProvider(criteria, true), 0, 0,
            locationListener);

However, when I graph the data I have collected on Google maps, the GPS coordinates are very scattered in some instances, or it will be going along a path I am walking just find and then all of the sudden jump to a point a mile away and then back. Is there any way to fix this? Some sort of accuracy check I guess?

Update:

Basically my problem looks like this as an example - GPS Jitter

Update 2:

I considered not making this a bounty but I figured I might as well get a complete understanding of what is going on here, and see if maybe my approach is over kill. I still have the same problem that my coordinates have jitter in them despite the fact that I have accuracies of 3m, etc. Now this could be to available satellites, etc. I don't know, but basically I'm trying to understand how are all these other applications, especially the exercise apps, able to get such smooth readings under the same circumstances.

I was on Quora and was able to find this Does any running app have a feature of filtering GPS data to get more accurate tracking? Unfortunately it didn't give much insight into my problem, except you can use a Kalman filter if you want, but surely there has to be less complex means, since I doubt most apps out there are implementing this.

Anyways if a fellow developer would like to share what they are doing with some pseudocode that would be greatly appreciated. I mean if I'm stuck with Kalman I am, but I am sure there have to be easier to implement algorithms, and would hope to learn those and how to implement them, that are decent fits.

Context: This is a mobile pedestrian application.

Relevant SO Questions I have tried to glean information from Create a smooth curve from a series of GPS coordinates Smooth gps data : This was a good start, though I am not sure what pseudocode I would need to implement to properly get the Least Squares Fit to work appropriately so that I will have a splines GPS data which I can then view on something like google maps to confirm I did it correctly. I think the issue is if this was general X and Y data I was dealing with, and not GEO coordinates, I could write something up in matlab test it, and go on.

Update 3

An image of the messed up GPS data I am recieving https://www.dropbox.com/s/ilsf8snao2no65e/gpsdata2.png

Code https://gist.github.com/4505688

Answer 1

The GPS data itself is prone to errors. Even if you have all the LocationManager set correctly (and it looks like you do) you will be seeing occasional jitter in the locations.

Accuracy

One thing to note is that the GPS accuracy only gives you an estimate to how good the calculation was given the GPS signals received. Systematic errors can give you a good accuracy number (<10m) but still represent a large position error. This is why you will see the jitter even if your accuracy is very good. Accuracy measures are good to remove very large errors (>100m) but on a lower level it just gives you an indication that the calculations converged.

Filtering

Filtering, like many things, is best if you do as little as possible. An accuracy filter should be able to remove large errors and if you end up with a good threshold you might be able to get smooth data.

You might also get some benefit if you put a threshold on position changes for running apps. For instance a runner can only cover a certain distance over time and by setting an upper threshold (Usain Bolt Cutoff) you should be able to remove bad points. The problem with that is that if your first point is the error you end up removing all the other points.

Kalman Filter

The Kalman Filter is a great solution and I have implemented it on navigation app that I am working on. The results are very reasonable and it even allows for limited dead-reckoning in the cases where GPS is bad or unavailable. Unfortunately I can't share the source code but I can give you a little guidance if you decide to go that way. The best results have come from a 6 DoF filter where you calculate acceleration and velocity and use that to estimate positions. It isn't the simplest solution but we have seen good results from it.

Least-Squares

The Kalman Filter is great since it can be used in realtime to filter the positions. It keeps track of its own state and you don't need to store old locations. But on the other hand if you want to post-process your route, least-squares fit is an optimal way to go. (Kalman is derived from the LSQ formulas). I don't do a lot of post-processing but I suspect I can dig up some old textbooks on it. The theory should be the same however.

Most GPS devices are pretty good and from all the testing I have seen I don't often see the jitter you are seeing in your example. However, one big advantage and the reason why I implemented the Kalman Filter is that your distance traveled and velocity calculations are much more accurate