Detectando e corrigindo discrepantes em uma trajetória GPS

9

Preciso encontrar um algoritmo ou método que possa detectar latitude longitude pontos extremos em uma trajetória durante o pós-processamento , que poderá ser corrigido (trazido de volta ao caminho da trajetória com base em seus vizinhos).

Como exemplo do tipo de pontos extremos que gostaria de detectar e corrigir, anexei uma imagem demonstrando:

Dados brutos em azul.

Tentei usar um filtro Kalman sem cheiro para suavizar os dados da melhor maneira possível, mas isso parece não funcionar de maneira eficaz o suficiente para valores extremos mais extremos (dados brutos em azul, dados suavizados em vermelho):

Dados brutos em azul, UKF suavizou os dados em vermelho.

Meu UKF pode não estar calibrado corretamente (mas tenho certeza de que está).

As trajetórias são as de caminhantes, corredores, ciclistas - movimentos movidos a humanos que podem começar e parar, mas não mudam drasticamente a velocidade ou a posição de maneira rápida ou repentina.

Uma solução que não depende de dados de temporização (e apenas de dados de posição) seria extremamente útil (pois os dados que estão sendo processados ​​nem sempre podem conter dados de temporização). No entanto, estou ciente de quão improvável é esse tipo de solução, então estou igualmente feliz por ter qualquer solução!

Idealmente, a solução detectaria o outlier para que pudesse ser corrigido, resultando em uma trajetória corrigida:

Dados brutos corrigidos em verde.


Recursos que eu examinei:

JP
fonte

Respostas:

1

Como parte de uma ferramenta para o processamento de redes fluviais, criei uma ferramenta de controle de qualidade para procurar "picos" na rede. Enquanto não estou sugerindo que você use minha ferramenta (como é para processar redes fluviais), aponto para o arquivo de Ajuda, que mostra uma imagem do que eu havia feito.

Eu desenvolvi código usando a lei dos cossenos para identificar ângulos sucessivos entre cada segmento de linha de uma polilinha. Você pode desenvolver seu próprio código em torno dessa ideia para percorrer uma polilinha e identificar ângulos extremos.

Hornbydd
fonte
Eu usei um método como você descreveu (usando a lei dos cossenos) e incluindo as distâncias entre os pontos para determinar melhor os valores extremos, e parece funcionar muito bem. Obrigado!
JP
8

Algoritmo que eu uso.

  1. Calcular a árvore de extensão mínima euclidiana de pontos:

insira a descrição da imagem aqui

  1. Encontre 2 pontos mais distantes um do outro nesta rede

insira a descrição da imagem aqui

  1. Encontre o caminho mais curto entre eles:

insira a descrição da imagem aqui

Como se pode ver, isso pode fazer uma curva acentuada.

Eu tenho implementação python ArcGIS do algoritmo acima, ele usa o módulo networkx. Informe-me se isso for interessante e atualizarei minha resposta com o script

ATUALIZAR:

# 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
fonte
Hmmm abordagem interessante .. obrigado por compartilhar isso! um exemplo de trabalho seria valorizado, tenho certeza!
nickves
11
Algum tipo de comparação por partes entre o resultado dessa abordagem e o que você obteria apenas seguindo os dados de entrada pode permitir que você defina um limite que elimine os "picos", mas ainda mantenha cantos. Isso pode ser especialmente útil se você também tiver informações de tempo associadas a cada ponto, que naturalmente surgem de alguns logs.
Doug McClean
11
Justo. É fácil modificar o script, não criando links entre nós que estão n intervalos de tempo um do outro. Estou usando scripts para outras coisas, não para caminhos de GPS. Existem outras maneiras de melhorar também, por exemplo, a triangulação, que reduzirá enormemente o número de links no gráfico
FelixIP
2
Esse método funciona em alguns casos, no entanto, as formas de algumas trajetórias significam que o uso desse método não é viável no meu caso de uso. (Problemas ocorrem quando, por exemplo, uma trajetória se dobra novamente, pois muitos nós são ignorados e zig-zags. Da mesma forma, seções inteiras de uma trajetória podem ser ignoradas se a entrada / saída dessa seção estiver próxima o suficiente).
JP
11
@JP para caminhos que retrocedem pode ajudar a densificar a linha bruta primeiro #
FelixIP
4

Uma idéia é criar um script que lista os ângulos (e talvez o comprimento também) de cada segmento do seu caminho. Agora você pode comparar os valores de cada segmento com seus vizinhos diretos (e possivelmente os segundos vizinhos também para aumentar a precisão) e selecionar todos os pontos em que os valores excedem um determinado valor threashold. Finalmente, basta excluir os pontos do seu caminho.

HimBromBeere
fonte
Eu usei um método semelhante descrito por @Hornbydd que realiza isso usando a lei dos cossenos para determinar ângulos, e também incorporando a distância entre os pontos. Obrigado pela sugestão.
JP
2

Também vale a pena observar o método Median-5.

Cada coordenada x (ou y) é definida como a mediana dos valores de 5 x (ou y) ao seu redor em sequência (isto é, ela própria, os dois valores anteriores e os dois valores subsequentes).

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

O método é rápido e também é fácil de usar no streaming de dados.

Thrud
fonte
0

Você pode importar seus dados para o Excel ou usar pandas e sinalizadores e / ou excluir todas as distâncias do ponto anterior que excedam algum limite de distância irrealista.

risail
fonte