9

I need to find an algorithm or method that can detect outlier latitude longitude points in a trajectory during post-processing, which can then be fixed (brought back into the trajectory's path based on its neighbours).

As an example of the kind of outlier points I would like to detect and fix, I've attached an image demonstrating:

Raw data in blue.

I have tried using an unscented Kalman filter to smooth out the data as best as possible, but this does not seem to work effectively enough for more extreme outliers (raw data in blue, smoothed data in red):

Raw data in blue, UKF smoothed data in red.

My UKF may not be calibrated properly (but I'm fairly certain that it is).

The trajectories are those of walkers, runners, cyclists - human-powered movement that can start and stop, but not drastically change in speed or position that quickly or suddenly.

A solution that does not rely on timing data (and only on position data) would be extremely useful (as the data being processed may not always contain timing data). However, I'm aware of how unlikely this kind of solution is to exist, so I'm equally as happy to have any solution!

Ideally, the solution would detect the outlier so that it could be fixed, resulting in a corrected trajectory:

Corrected raw data in green.


Resources I've sifted through:

1

As part of a tool for processing river networks I created a quality control tool to search for "spikes" in the network. Whilst I'm not suggesting you use my tool (as it is for processing river networks) I point you to the Help file which shows an image of what I had done.

I had developed code around using the law of cosines to identify successive angles between each line segment of a polyline. You could develop your own code around this idea to step along a polyline and identify extreme angles.

  • I've used a method like you described (using the law of cosines) and including the distances between points to better determine outliers, and it seems to work very well. Thank you! – J.P. Dec 19 '15 at 10:39
8

Algorithm I use.

  1. Calculate Euclidean minimum spanning tree of points:

enter image description here

  1. Find 2 points most far apart from each other on this network

enter image description here

  1. Find shortest route between them:

enter image description here

As one can see it might cut corner on a sharp turn.

I have ArcGIS python implementation of above algorithm, it uses networkx module. Let me know if this is of interest and I'll update my answer with the script

UPDATE:

# Connects points to make polyline. Makes 1 line at a time
# Tool assumes that 1st layer in Table of Conternt is TARGET polyline feature class,
# second layer in TOC is SOURCE point fc.
# If no selection found in SOURCE layer, works on entire dataset

import arcpy, traceback, os, sys
import itertools as itt
from math import sqrt
sys.path.append(r'C:\Users\felix_pertziger\AppData\Roaming\Python\Python27\site-packages')
import networkx as nx
from networkx import dijkstra_path_length

try:
    def showPyMessage():
        arcpy.AddMessage(str(time.ctime()) + " - " + message)
    def CheckLayerLine(infc):
        d=arcpy.Describe(infc)
        theType=d.shapeType
        if theType!="Polyline":
            arcpy.AddWarning("\nTool designed to work with polylines as TARGET!")
            raise NameError, "Wrong input\n"
        return d
    def CheckLayerPoint(infc):
        d=arcpy.Describe(infc)
        theType=d.shapeType
        if theType!="Point":
            arcpy.AddWarning("\nTool designed to work with points as SOURCE!")
            raise NameError, "Wrong input\n"
        return d
    mxd = arcpy.mapping.MapDocument("CURRENT")
    layers = arcpy.mapping.ListLayers(mxd)
    if len(layers)<=1:
        arcpy.AddWarning("\nNot enough layers in the view!")
        raise NameError, "Wrong input\n"
    destLR, sourceLR=layers[0],layers[1]
    a = CheckLayerPoint(sourceLR);d = CheckLayerLine(destLR)

#  copy all points to manageable list
    g=arcpy.Geometry()
    geometryList=arcpy.CopyFeatures_management(sourceLR,g)
    nPoints=len(geometryList)
    arcpy.AddMessage('Computing minimum spanning tree')
    list2connect=[p.firstPoint for p in geometryList]
#  create network    
    p=list(itt.combinations(range(nPoints), 2))
    arcpy.SetProgressor("step", "", 0, len(p),1)
    G=nx.Graph()
    for f,t in p:
        p1=list2connect[f]
        p2=list2connect[t]
        dX=p2.X-p1.X;dY=p2.Y-p1.Y
        lenV=sqrt(dX*dX+dY*dY)
        G.add_edge(f,t,weight=lenV)
        arcpy.SetProgressorPosition()
    arcpy.AddMessage(len(G.edges()))
    mst=nx.minimum_spanning_tree(G)
    del G

#  find remotest pair
    arcpy.AddMessage(len(mst.edges()))
    length0=nx.all_pairs_dijkstra_path_length(mst)
    lMax=0
    for f,t in p:
        lCur=length0[f][t]
        if lCur>lMax:
            lMax=lCur
            best=(f,t)
    gL=nx.dijkstra_path(mst,best[0],best[1])
    del mst
    nPoints=len(gL)
    ordArray=arcpy.Array()
    for i in gL: ordArray.add(list2connect[i])

#  append line to TARGET
    curT = arcpy.da.InsertCursor(destLR,"SHAPE@")
    curT.insertRow((arcpy.Polyline(ordArray),))
    arcpy.RefreshActiveView()
    del curT

except:
    message = "\n*** PYTHON ERRORS *** "; showPyMessage()
    message = "Python Traceback Info: " + traceback.format_tb(sys.exc_info()[2])[0]; showPyMessage()
    message = "Python Error Info: " +  str(sys.exc_type)+ ": " + str(sys.exc_value) + "\n"; showPyMessage()            
  • Hmmm interesting approach.. thanks for sharing this! a working example would be valued I'm sure! – nickves Dec 16 '15 at 20:25
  • 1
    Some kind of piecewise comparison between the result of this approach and what you would get by just following the input data might allow you to set a threshold that would get rid of the "spikes" but still retain corners. This could be especially useful if you also have time information associated with each point, which naturally arises from some logs. – Doug McClean Dec 16 '15 at 22:05
  • 1
    Fair enough. It's easy to modify script by not creating links between nodes that are n time intervals away from each other. I am using script for other things, not GPS paths. There are other ways for improvement as well, e.g. triangulation, which will massively reduce number of links in the graph – FelixIP Dec 16 '15 at 22:14
  • 2
    This method works in some cases, however the shapes of some trajectories means that using this method is not feasible in my use-case. (Problems occur when, for example, a trajectory doubles back on itself, as many nodes are ignored and it zig-zags. Similarly, entire sections of a trajectory can be ignored if the entrance/exit of that section is close enough together). – J.P. Dec 17 '15 at 16:50
  • 1
    @J.P. for paths going backwards it might help to densify raw line 1st – FelixIP Dec 17 '15 at 18:01
4

One idea is to create a script that lists the angles (and maybe the length also) of every segment of your path. Now you can compare the values of every segment with its direct neighbours (and possibly the second neighbours also to increase accuracy) and select all those points where the values exceed a given threashold-value. Finally simply delete the points from your path.

  • I have used a similar method described by @Hornbydd that accomplishes this using the law of cosines to determine angles, an also incorporating the distance between points. Thank you for the suggestion. – J.P. Dec 19 '15 at 10:43
2

Also worth looking at is the Median-5 method.

Each x (or y) coordinate is set to the median of the 5 x (or y) values around it in sequence (i.e. itself, the two previous values and the two subsequent values).

e.g. x3 = median(x1,x2,x3,x4,x5) y3 = median(y1,y2,y3,y4,y5) etc.

Method is quick and is also easy to use on streaming data.

1

There is some good data in this question/answers.

Though it all depends on how your points are clustered on what will/will not work. You will need to be careful on points that are spread out but not outliers.

0

You could import your data into excel or use pandas and flag and or delete all distances from the previous point that exceed some unrealistic distance threshold.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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