Détection et correction des valeurs aberrantes dans une trajectoire GPS

9

J'ai besoin de trouver un algorithme ou une méthode qui puisse détecter des latitude longitude points aberrants dans une trajectoire pendant le post-traitement , qui peut ensuite être corrigé (ramené dans le chemin de la trajectoire en fonction de ses voisins).

À titre d'exemple du type de points aberrants que je voudrais détecter et corriger, j'ai joint une image démontrant:

Données brutes en bleu.

J'ai essayé d'utiliser un filtre de Kalman non parfumé pour lisser le mieux possible les données, mais cela ne semble pas fonctionner suffisamment efficacement pour les valeurs extrêmes plus extrêmes (données brutes en bleu, données lissées en rouge):

Données brutes en bleu, données lissées UKF en rouge.

Mon UKF n'est peut-être pas calibré correctement (mais je suis assez certain qu'il l'est).

Les trajectoires sont celles des marcheurs, des coureurs, des cyclistes - des mouvements à propulsion humaine qui peuvent démarrer et s'arrêter, mais pas changer radicalement de vitesse ou de position aussi rapidement ou soudainement.

Une solution qui ne repose pas sur des données de synchronisation (et uniquement sur des données de position) serait extrêmement utile (car les données en cours de traitement ne contiennent pas toujours des données de synchronisation). Cependant, je suis conscient de l'improbabilité de ce type de solution, donc je suis tout aussi heureux d'avoir une solution!

Idéalement, la solution détecterait la valeur aberrante afin qu'elle puisse être corrigée, résultant en une trajectoire corrigée:

Données brutes corrigées en vert.


Ressources que j'ai passées en revue:

JP
la source

Réponses:

1

Dans le cadre d'un outil de traitement des réseaux fluviaux, j'ai créé un outil de contrôle qualité pour rechercher des "pointes" dans le réseau. Bien que je ne vous suggère pas d'utiliser mon outil (comme c'est le cas pour le traitement des réseaux fluviaux), je vous montre le fichier d'aide qui montre une image de ce que j'ai fait.

J'avais développé un code autour de l'utilisation de la loi des cosinus pour identifier les angles successifs entre chaque segment de ligne d'une polyligne. Vous pouvez développer votre propre code autour de cette idée pour avancer le long d'une polyligne et identifier les angles extrêmes.

Hornbydd
la source
J'ai utilisé une méthode comme vous l'avez décrite (en utilisant la loi des cosinus) et en incluant les distances entre les points pour mieux déterminer les valeurs aberrantes, et cela semble très bien fonctionner. Je vous remercie!
JP
8

Algorithme que j'utilise.

  1. Calculer l’arbre de points minimal euclidien:

entrez la description de l'image ici

  1. Trouvez les 2 points les plus éloignés les uns des autres sur ce réseau

entrez la description de l'image ici

  1. Trouvez l'itinéraire le plus court entre eux:

entrez la description de l'image ici

Comme on peut le voir, cela pourrait prendre un virage serré.

J'ai une implémentation ArcGIS python de l'algorithme ci-dessus, il utilise le module networkx. Faites-moi savoir si cela vous intéresse et je mettrai à jour ma réponse avec le script

MISE À JOUR:

# 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
la source
Hmmm approche intéressante .. merci de partager cela! un exemple de travail serait apprécié, j'en suis sûr!
nickves
1
Une sorte de comparaison par morceaux entre le résultat de cette approche et ce que vous obtiendriez en suivant simplement les données d'entrée pourrait vous permettre de définir un seuil qui éliminerait les «pics» tout en conservant les coins. Cela pourrait être particulièrement utile si vous avez également des informations de temps associées à chaque point, qui découlent naturellement de certains journaux.
Doug McClean
1
C'est suffisant. Il est facile de modifier le script en ne créant pas de liens entre les nœuds distants de n intervalles de temps. J'utilise le script pour d'autres choses, pas pour les trajets GPS. Il existe également d'autres moyens d'amélioration, par exemple la triangulation, qui réduira considérablement le nombre de liens dans le graphique
FelixIP
2
Cette méthode fonctionne dans certains cas, mais la forme de certaines trajectoires signifie que l'utilisation de cette méthode n'est pas possible dans mon cas d'utilisation. (Des problèmes se produisent lorsque, par exemple, une trajectoire se replie sur elle-même, car de nombreux nœuds sont ignorés et zigzaguent. De même, des sections entières d'une trajectoire peuvent être ignorées si l'entrée / la sortie de cette section est suffisamment rapprochée).
JP
1
@JP pour les chemins en arrière, cela pourrait aider à densifier la ligne brute 1er
FelixIP
4

Une idée est de créer un script qui répertorie les angles (et peut-être aussi la longueur) de chaque segment de votre chemin. Vous pouvez maintenant comparer les valeurs de chaque segment avec ses voisins directs (et éventuellement les seconds voisins également pour augmenter la précision) et sélectionner tous les points où les valeurs dépassent une valeur de seuil donnée. Enfin, supprimez simplement les points de votre chemin.

HimBromBeere
la source
J'ai utilisé une méthode similaire décrite par @Hornbydd qui accomplit cela en utilisant la loi des cosinus pour déterminer les angles, en incorporant également la distance entre les points. Merci pour la suggestion.
JP
2

La méthode Median-5 mérite également d'être étudiée.

Chaque coordonnée x (ou y) est définie sur la médiane des 5 valeurs x (ou y) qui l'entourent en séquence (c'est-à-dire elle-même, les deux valeurs précédentes et les deux valeurs suivantes).

par exemple x3 = médiane (x1, x2, x3, x4, x5) y3 = médiane (y1, y2, y3, y4, y5) etc.

La méthode est rapide et est également facile à utiliser sur les données en streaming.

Thrud
la source
0

Vous pouvez importer vos données dans Excel ou utiliser des pandas et des drapeaux et / ou supprimer toutes les distances du point précédent qui dépassent un certain seuil de distance irréaliste.

risail
la source