Detección y fijación de valores atípicos en una trayectoria GPS

Question

Necesito encontrar un algoritmo o método que pueda detectar los valores atípicos latitude longitude puntos de una trayectoria durante el posprocesamiento que puede ser fijada (devuelta a la trayectoria en función de sus vecinos).

Como ejemplo del tipo de puntos atípicos que me gustaría detectar y corregir, adjunto una imagen demostrativa:

He intentado utilizar un filtro de Kalman no perfeccionado para suavizar los datos lo mejor posible, pero esto no parece funcionar con suficiente eficacia para los valores atípicos más extremos (datos brutos en azul, datos suavizados en rojo):

Puede que mi UKF no esté bien calibrada (pero estoy bastante seguro de que lo está).

Las trayectorias son las de los caminantes, los corredores y los ciclistas, es decir, movimientos de tracción humana que pueden arrancar y detenerse, pero que no cambian drásticamente de velocidad o posición de forma tan rápida o repentina.

Una solución que no dependa de los datos de sincronización (y sólo de los datos de posición) sería extremadamente útil (ya que los datos que se procesan pueden no contener siempre datos de sincronización). Sin embargo, soy consciente de lo improbable que es la existencia de este tipo de solución, ¡así que estoy igualmente contento de tener cualquier solución!

Lo ideal sería que la solución detectara el valor atípico para poder fijarlo, lo que daría lugar a una trayectoria corregida:

---

Recursos que he buscado:

• Smooth GPS data - https://stackoverflow.com/questions/1134579/smooth-gps-data

• Common GPS and Geospatial Tracking Challenges and Solutions - http://www.toptal.com/gis/adventures-in-gps-track-analytics-a-geospatial-primer (la solución parece perder la precisión de los datos)

• ¿Qué algoritmo debo utilizar para eliminar los valores atípicos en los datos de rastreo?

Answer 1

Algoritmo que utilizo.

1. Calcule el árbol de expansión mínimo euclidiano de los puntos:

2. Encuentra los 2 puntos más alejados entre sí en esta red

3. Encuentra la ruta más corta entre ellos:

Como se puede ver, podría cortar la esquina en una curva cerrada.

Tengo una implementación en ArcGIS python del algoritmo anterior, que utiliza el módulo networkx. Hágame saber si esto es de interés y voy a actualizar mi respuesta con la secuencia de comandos

ACTUALIZACIÓN:

# 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()

Answer 2

Una idea es crear un script que enumere los ángulos (y quizá también la longitud) de cada segmento de su trayectoria. Ahora puede comparar los valores de cada segmento con sus vecinos directos (y posiblemente también con los segundos vecinos para aumentar la precisión) y seleccionar todos aquellos puntos en los que los valores superen un determinado valor de tres veces. Por último, simplemente elimine los puntos de su trayectoria.

Answer 3

Hay algunos buenos datos en esta pregunta/respuesta.

Aunque todo depende de cómo estén agrupados tus puntos en lo que funcionará/no funcionará. Tendrás que tener cuidado con los puntos que están dispersos pero no son valores atípicos.

Answer 4

Como parte de una herramienta para procesar redes fluviales, he creado una herramienta de control de calidad para buscar "picos" en la red. Aunque no le sugiero que utilice mi herramienta (ya que es para el procesamiento de redes fluviales), le remito a la página Archivo de ayuda que muestra una imagen de lo que había hecho.

Había desarrollado un código en torno al uso del ley de los cosenos para identificar los ángulos sucesivos entre cada segmento de línea de una polilínea. Podrías desarrollar tu propio código en torno a esta idea para recorrer una polilínea y identificar ángulos extremos.

Answer 5

Podrías importar tus datos a excel o usar pandas y marcar y o borrar todas las distancias desde el punto anterior que superen algún umbral de distancia poco realista.