Detectar y corregir valores atípicos en una trayectoria GPS

9

Necesito encontrar un algoritmo o método que pueda detectar latitude longitude puntos atípicos en una trayectoria durante el procesamiento posterior , que luego se puede arreglar (volver a la trayectoria de 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 que demuestra:

Datos sin procesar en azul.

Intenté usar un filtro Kalman sin perfume para suavizar los datos lo mejor posible, pero esto no parece funcionar de manera suficientemente efectiva para valores atípicos más extremos (datos sin procesar en azul, datos suavizados en rojo):

Datos sin procesar en azul, datos suavizados UKF en rojo.

Es posible que mi UKF no esté calibrado correctamente (pero estoy bastante seguro de que sí).

Las trayectorias son las de caminantes, corredores, ciclistas: movimiento impulsado por humanos que puede comenzar y detenerse, pero que no cambia drásticamente la velocidad o la posición tan rápido o repentino.

Una solución que no se base en datos de tiempo (y solo en datos de posición) sería extremadamente útil (ya que los datos que se procesan no siempre contienen datos de tiempo). Sin embargo, soy consciente de cuán improbable es que exista este tipo de solución, ¡así que estoy igualmente feliz de tener alguna solución!

Idealmente, la solución detectaría el valor atípico para poder solucionarlo, lo que da como resultado una trayectoria corregida:

Datos brutos corregidos en verde.


Recursos que he examinado:

JP
fuente

Respuestas:

1

Como parte de una herramienta para procesar redes fluviales, creé una herramienta de control de calidad para buscar "picos" en la red. Si bien no estoy sugiriendo que use mi herramienta (ya que es para procesar redes fluviales), le indico el archivo de Ayuda que muestra una imagen de lo que había hecho.

Había desarrollado código en torno al uso de la ley de cosenos para identificar ángulos sucesivos entre cada segmento de línea de una polilínea. Podría desarrollar su propio código en torno a esta idea para avanzar por una polilínea e identificar ángulos extremos.

Hornbydd
fuente
He usado un método como el que usted describió (usando la ley de cosenos) e incluyendo las distancias entre puntos para determinar mejor los valores atípicos, y parece funcionar muy bien. ¡Gracias!
JP
8

Algoritmo que uso.

  1. Calcule el árbol de puntos de expansión mínima euclidiana:

ingrese la descripción de la imagen aquí

  1. Encuentre 2 puntos más alejados entre sí en esta red

ingrese la descripción de la imagen aquí

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

ingrese la descripción de la imagen aquí

Como se puede ver, podría cortar la esquina en un giro brusco.

Tengo la implementación de ArcGIS python del algoritmo anterior, utiliza el módulo networkx. Avíseme si esto le interesa y actualizaré mi respuesta con el script

ACTUALIZAR:

# 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
fuente
Hmmm enfoque interesante ... gracias por compartir esto! ¡un ejemplo de trabajo sería valorado, estoy seguro!
nickves
1
Algún tipo de comparación por partes entre el resultado de este enfoque y lo que obtendría simplemente siguiendo los datos de entrada podría permitirle establecer un umbral que eliminaría los "picos" pero aún conservaría las esquinas. Esto podría ser especialmente útil si también tiene información de tiempo asociada con cada punto, que surge naturalmente de algunos registros.
Doug McClean
1
Lo suficientemente justo. Es fácil modificar la secuencia de comandos al no crear enlaces entre nodos que están a n intervalos de tiempo entre sí. Estoy usando script para otras cosas, no rutas de GPS. También hay otras formas de mejora, por ejemplo, triangulación, que reducirá enormemente el número de enlaces en el gráfico
FelixIP
2
Este método funciona en algunos casos, sin embargo, las formas de algunas trayectorias significan que usar este método no es factible en mi caso de uso. (Los problemas ocurren cuando, por ejemplo, una trayectoria se duplica sobre sí misma, ya que se ignoran muchos nodos y zigzaguea. De manera similar, se pueden ignorar secciones enteras de una trayectoria si la entrada / salida de esa sección está lo suficientemente cerca).
JP
1
@JP para caminos que van hacia atrás, podría ayudar a densificar la línea sin procesar 1 °
FelixIP
4

Una idea es crear un script que enumere los ángulos (y tal vez la longitud también) de cada segmento de su ruta. Ahora puede comparar los valores de cada segmento con sus vecinos directos (y posiblemente los segundos vecinos también para aumentar la precisión) y seleccionar todos aquellos puntos donde los valores exceden un valor de umbral dado. Finalmente, simplemente elimine los puntos de su ruta.

HimBromBeere
fuente
He utilizado un método similar descrito por @Hornbydd que logra esto usando la ley de cosenos para determinar ángulos, y también incorporando la distancia entre puntos. Gracias por la sugerencia.
JP
2

También vale la pena mirar es el método Median-5.

Cada coordenada x (o y) se establece en la mediana de los 5 valores x (o y) a su alrededor en secuencia (es decir, los dos valores anteriores y los dos valores posteriores).

Por ejemplo, x3 = mediana (x1, x2, x3, x4, x5) y3 = mediana (y1, y2, y3, y4, y5) etc.

El método es rápido y también es fácil de usar en la transmisión de datos.

Thrud
fuente
0

Puede importar sus datos a Excel o usar pandas y banderas y eliminar todas las distancias desde el punto anterior que excedan un umbral de distancia poco realista.

risail
fuente