Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I have a database of GPS points. There aren't any tracks, only points. I need to calculate some value for every 100 meters, but sometimes GPS gave a wrong coordinates that lies far from real GPS points, and instead of calculating values for a small square, I have to calculate it for a really big rectangular area.

What is the best algorithm to filter wrong GPS points?

I made a screenshot to help understand:

![http://content.screencast.com/users/smirnoffs/folders/Jing/media/94624331-db6a-4171-bed9-e2183f953a1d/gps_error.png]

share|improve this question
1  
I'd use a small multiple of the moving frame (say 10 last points) average distance between points as the criterion to detect such outliers. –  lynxlynxlynx Aug 7 '12 at 12:02
    
Can you describe your method more detailed? I have a database of points, they are not sorted in any kind. So the distance could be 2 meters or 500 meters. But some of points are very far. I made a screenshot to help you understand –  smirnoffs Aug 7 '12 at 12:51
2  
I see. In this case my approach is not so good. I would instead calculate the nearest neighbouring point for each point and then shave off the outliers there. –  lynxlynxlynx Aug 7 '12 at 13:09
2  
The second approach suggested by @lynx would work well with the sample data, especially when the outlier detection method is a good one. See questions about outliers on our stats site for options. For instance, many creative (and valid) approaches are suggested at stats.stackexchange.com/questions/213. –  whuber Aug 7 '12 at 15:16

4 Answers 4

up vote 3 down vote accepted

Run Anselin Local Moran's I against the points and throw out anything with a z-score below -1.96. That's a statistical method for locating spatial outliers. You must ensure that all points have a value related to their spatial position to do that.

But in checking on the tools in 10.1 after whuber's comment, I realize that if you use ArcGIS 10.1, the grouping analysis tool is available, which is really what you want to do.

I -think- you would want to do a grouping analysis with a Delaunay Triangulation spatial constraint. The roadblock here is that you need to have a number of partitioning groups equal to or greater than the number of disconnected groups (if any of the outliers are natural neighbors to each other). Otherwise, outliers with no natural neighbors will come up with no group from the grouping analysis.

Based on that, I think Delauney triangulation might be the source of a filter algorithm, but I am not sure yet.

Another update: After digging into Partition.py, the script that runs the grouping analysis tool, I think it is possible to use the algorithm in there for disconnected groups combined with the NoNeighbors portion, though I am having trouble digging out that part of the script.

share|improve this answer
    
(-1) This is guaranteed to throw away about 1 in 40 points no matter what. It is not advisable to use any such test for outlier detection. –  whuber Aug 7 '12 at 15:11
1  
That is not true when testing for pure spatial outliers -if- spatial outliers exist. If spatial outliers do not exist, then you will have that issue, but if they do exist then only those outliers should fall into such a low z-score. It all depends on the spatial distribution of the points. –  blord-castillo Aug 7 '12 at 15:20
1  
Almost: if the outliers themselves form a cluster, you might fail to detect them altogether. (Consider a situation where null or obviously bad coordinates are mapped to (0,0) automatically.) Your comment shows that finding outliers can be tricky and depends on the nature of the outliers: whether there can be one or many; how far off they can be; whether they can cluster; etc. As a general principle, statistics that make distributional assumptions (like this use of Local Moran's I) do not work as well as the robust, non-parametric statistics. –  whuber Aug 7 '12 at 15:25
2  
I was considering a specific theoretical problem, where you have the "good" GPS points and you have an equal number of "bad" GPS points stacked on top of each other at a far corner of the bounding box. Without knowledge of the area of interest for the "good" points, I don't think you can statistically separate out which set is "good" and which set is "bad". This might be a problem that requires manual designation of areas of interest. –  blord-castillo Aug 7 '12 at 16:09
2  
That is correct: you have described a bimodal multivariate distribution. What is usually done in such cases is either estimation of a mixture model or application of a cluster algorithm. The result is to separate out the mixture/cluster components but without designating any of them as "outliers:" that duty must fall to the user. –  whuber Aug 7 '12 at 16:12

THis might help to get a list of the outliers:

SELECT p1.point_id 
FROM p1 AS points, p2 AS points
WHERE p1.point_id <> p2.point_id AND
ST_Distance(p1.geom, p2.geom) > 10000

Here, point_id would be the primary key in your points table. The distance function will find points where the nearest is greater than 10000 meters. (You can, of course, put any value appropriate)

If the above works, then change to a DELETE statment, something like:

DELETE FROM points WHERE point_id IN (
-- SELECT as above
SELECT ....
);
share|improve this answer
1  
1. The points are not sorted. 2. What if error will be lower than 10000 meters? For example 150 meters? –  smirnoffs Aug 7 '12 at 13:55
1  
Maybe I did not understand. From your image, I see that almost all points are clustered in one area, and a very small number are very far away. Is that not the problem? If a point is only 150 meters away from another, how do you know it's an outlier? –  Micha Aug 8 '12 at 5:24

I'll try to provide a more practical answer to help you get the job done. (apologies if you are looking for a discussion on algorithms )

Scenario 1: You mention 'GPS points', so if you have access to original GPS waypoints, the job becomes much easier. You can throw out points with high HDOP/VDOP or number of satellits in view - which would have caused the error originally. A free tool like gpsbabel has such filters built-in. http://www.gpsbabel.org/htmldoc-development/Data_Filters.html

Scenario 2: You simply have a set of points. The problem then becomes detecting spatial outliers. There is a lot of research in this area and I see many papers on this subject from a web search. If you are looking to clean up your data, you can use GRASS's v.outlier algorithm which should work in your case based on the screenshot you shared. http://grass.osgeo.org/gdp/html_grass63/v.outlier.html

share|improve this answer
    
Thanks for comment. Unfortunately I have only coordinates. GPS was just a source of coordinates and I haven't access to original GPS tracks. –  smirnoffs Aug 9 '12 at 6:48

I think you've got junk data. Realistically, if you care about the fact that some of the data is wrong, and you can't reliably identify every wrong point using some other factor, then you're going to have some bad data in your analysis.

If that matters, then you should probably consider tossing everything, figuring out the root cause (e.g. the bad GPS points are from multipath), addressing that root cause (e.g. adding a choke antenna, or better type of GPS, or whatever the best fix is), and then redoing the data collection.

If the bad data doesn't matter, then just use it and ignore the errors.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.