How to filter wrong GPS points?

Question

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]

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 07 '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 07 '12 at 12:51
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 07 '12 at 13:09
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 http://stats.stackexchange.com/questions/213/. — whuber, Aug 07 '12 at 15:16

score 3 · Answer 1 · answered Aug 07 '12 at 13:23

3

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 ....
);

answered Aug 07 '12 at 13:23

Micha

15,555
23
29

1
The points are not sorted. 2. What if error will be lower than 10000 meters? For example 150 meters?

smirnoffs

Aug 07 '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 08 '12 at 05:24

blord-castillo · Accepted Answer · 2012-08-07T15:54:36.693

3

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.

edited Aug 07 '12 at 15:54

answered Aug 07 '12 at 13:26

blord-castillo

6,447
22
42

(-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 07 '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 07 '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 07 '12 at 15:25
+1 for the thoughtful edits. (One might be better off using a non-ArcGIS platform altogether, though, such as R, which has many, many clustering packages that should do a similar job.) – whuber Aug 07 '12 at 15:59
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 07 '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 07 '12 at 16:12

score 1 · Answer 3 · answered Aug 08 '12 at 12:14

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

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 09 '12 at 06:48

How to filter wrong GPS points?

3 Answers3

Linked