Erkennen und Beheben von Ausreißern in einer GPS-Flugbahn

9

Ich muss einen Algorithmus oder eine Methode finden, die Ausreißerpunkte latitude longitude in einer Trajektorie während der Nachbearbeitung erkennen kann , die dann behoben werden können (basierend auf ihren Nachbarn wieder in den Pfad der Trajektorie gebracht).

Als Beispiel für die Art von Ausreißerpunkten, die ich erkennen und beheben möchte, habe ich ein Bild angehängt, das Folgendes demonstriert:

Rohdaten in blau.

Ich habe versucht, einen nicht parfümierten Kalman-Filter zu verwenden, um die Daten so gut wie möglich zu glätten, aber dies scheint für extremere Ausreißer nicht effektiv genug zu funktionieren (Rohdaten in Blau, geglättete Daten in Rot):

Rohdaten in blau, UKF geglättete Daten in rot.

Mein UKF ist möglicherweise nicht richtig kalibriert (aber ich bin mir ziemlich sicher, dass dies der Fall ist).

Die Flugbahnen sind die von Wanderern, Läufern und Radfahrern - von Menschen angetriebene Bewegungen, die starten und stoppen können, aber ihre Geschwindigkeit oder Position nicht so schnell oder plötzlich drastisch ändern.

Eine Lösung, die nicht auf Zeitdaten (und nur auf Positionsdaten) beruht, wäre äußerst nützlich (da die verarbeiteten Daten möglicherweise nicht immer Zeitdaten enthalten). Ich bin mir jedoch bewusst, wie unwahrscheinlich es ist, dass es eine solche Lösung gibt, und bin daher genauso froh, eine Lösung zu haben!

Im Idealfall erkennt die Lösung den Ausreißer, sodass er behoben werden kann, was zu einer korrigierten Flugbahn führt:

Rohdaten in grün korrigiert.


Ressourcen, die ich durchgesehen habe:

JP
quelle

Antworten:

1

Als Teil eines Tools zur Verarbeitung von Flussnetzen habe ich ein Qualitätskontrollwerkzeug erstellt, um nach "Spikes" im Netzwerk zu suchen. Obwohl ich nicht vorschlage, dass Sie mein Tool verwenden (wie es für die Verarbeitung von Flussnetzen dient), verweise ich Sie auf die Hilfedatei, die ein Bild von dem zeigt, was ich getan habe.

Ich hatte Code entwickelt, der das Kosinusgesetz verwendet , um aufeinanderfolgende Winkel zwischen jedem Liniensegment einer Polylinie zu identifizieren. Sie können Ihren eigenen Code um diese Idee herum entwickeln, um entlang einer Polylinie zu gehen und extreme Winkel zu identifizieren .

Hornbydd
quelle
Ich habe eine Methode verwendet, wie Sie sie beschrieben haben (unter Verwendung des Kosinusgesetzes) und die Abstände zwischen Punkten einbezogen, um Ausreißer besser zu bestimmen, und sie scheint sehr gut zu funktionieren. Vielen Dank!
JP
8

Algorithmus, den ich benutze.

  1. Berechnen Sie den euklidischen minimalen Spannbaum von Punkten:

Geben Sie hier die Bildbeschreibung ein

  1. Finden Sie in diesem Netzwerk 2 Punkte, die am weitesten voneinander entfernt sind

Geben Sie hier die Bildbeschreibung ein

  1. Finden Sie den kürzesten Weg zwischen ihnen:

Geben Sie hier die Bildbeschreibung ein

Wie man sehen kann, könnte es in einer scharfen Kurve eine Ecke schneiden.

Ich habe ArcGIS Python Implementierung des obigen Algorithmus, es verwendet Networkx-Modul. Lassen Sie mich wissen, ob dies von Interesse ist, und ich werde meine Antwort mit dem Skript aktualisieren

AKTUALISIEREN:

# 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()            
FelixIP
quelle
Hmmm interessanter Ansatz .. danke für das Teilen! Ein funktionierendes Beispiel wäre sicher, da bin ich mir sicher!
Nickves
1
Eine Art stückweiser Vergleich zwischen dem Ergebnis dieses Ansatzes und dem, was Sie erhalten würden, wenn Sie nur den Eingabedaten folgen, könnte es Ihnen ermöglichen, einen Schwellenwert festzulegen, der die "Spitzen" beseitigt, aber dennoch Ecken beibehält. Dies kann besonders nützlich sein, wenn Sie mit jedem Punkt auch Zeitinformationen verknüpft haben, die sich natürlich aus einigen Protokollen ergeben.
Doug McClean
1
Fair genug. Es ist einfach, Skripte zu ändern, indem keine Verknüpfungen zwischen Knoten erstellt werden, die n Zeitintervalle voneinander entfernt sind. Ich benutze Skript für andere Dinge, nicht GPS-Pfade. Es gibt auch andere Möglichkeiten zur Verbesserung, z. B. Triangulation, die die Anzahl der Links in der Grafik massiv reduziert
FelixIP
2
Diese Methode funktioniert in einigen Fällen, jedoch bedeutet die Form einiger Trajektorien, dass die Verwendung dieser Methode in meinem Anwendungsfall nicht möglich ist. (Probleme treten beispielsweise auf, wenn sich eine Trajektorie auf sich selbst verdoppelt, da viele Knoten ignoriert werden und sie im Zick-Zack verläuft. Ebenso können ganze Abschnitte einer Trajektorie ignoriert werden, wenn der Ein- / Ausgang dieses Abschnitts nahe genug beieinander liegt.)
JP
1
@ JP für Pfade, die rückwärts gehen, könnte es helfen, rohe Linie 1.
FelixIP
4

Eine Idee ist, ein Skript zu erstellen, das die Winkel (und möglicherweise auch die Länge) jedes Abschnitts Ihres Pfades auflistet. Jetzt können Sie die Werte jedes Segments mit seinen direkten Nachbarn vergleichen (und möglicherweise auch mit den zweiten Nachbarn, um die Genauigkeit zu erhöhen) und alle Punkte auswählen, an denen die Werte einen bestimmten Wert überschreiten. Zum Schluss löschen Sie einfach die Punkte aus Ihrem Pfad.

HimBromBeere
quelle
Ich habe eine ähnliche von @Hornbydd beschriebene Methode verwendet, die dies unter Verwendung des Kosinusgesetzes zur Bestimmung von Winkeln erreicht und auch den Abstand zwischen Punkten berücksichtigt. Vielen Dank für den Vorschlag.
JP
2

Sehenswert ist auch die Median-5-Methode.

Jede x- (oder y-) Koordinate wird nacheinander auf den Median der 5 x- (oder y-) Werte um sie herum gesetzt (dh selbst, die beiden vorherigen Werte und die beiden nachfolgenden Werte).

zB x3 = Median (x1, x2, x3, x4, x5) y3 = Median (y1, y2, y3, y4, y5) usw.

Die Methode ist schnell und auch beim Streaming von Daten einfach anzuwenden.

Thrud
quelle
0

Sie können Ihre Daten in Excel importieren oder Pandas und Flag verwenden und / oder alle Entfernungen vom vorherigen Punkt löschen, die einen unrealistischen Entfernungsschwellenwert überschreiten.

risail
quelle