Mendeteksi dan memperbaiki outlier dalam lintasan GPS

9

Saya perlu menemukan algoritma atau metode yang dapat mendeteksi latitude longitude titik outlier dalam lintasan selama post-processing , yang kemudian dapat diperbaiki (dibawa kembali ke lintasan lintasan berdasarkan tetangganya).

Sebagai contoh dari jenis outlier yang ingin saya deteksi dan perbaiki, saya telah melampirkan gambar yang menunjukkan:

Data mentah berwarna biru.

Saya telah mencoba menggunakan filter Kalman tanpa wewangian untuk memuluskan data sebaik mungkin, tetapi ini tampaknya tidak bekerja cukup efektif untuk outlier yang lebih ekstrem (data mentah berwarna biru, data halus dalam warna merah):

Data mentah berwarna biru, UKF merapikan data dalam warna merah.

UKF saya mungkin tidak dikalibrasi dengan benar (tapi saya cukup yakin itu).

Lintasan adalah orang-orang pejalan kaki, pelari, pengendara sepeda - gerakan bertenaga manusia yang dapat memulai dan berhenti, tetapi tidak secara drastis mengubah kecepatan atau posisi yang cepat atau tiba-tiba.

Solusi yang tidak bergantung pada data waktu (dan hanya pada data posisi) akan sangat berguna (karena data yang sedang diproses mungkin tidak selalu berisi data waktu). Namun, saya sadar betapa tidak mungkin solusi semacam ini ada, jadi saya sama senangnya memiliki solusi apa pun!

Idealnya, solusi akan mendeteksi pencilan sehingga dapat diperbaiki, menghasilkan lintasan yang diperbaiki:

Data mentah terkoreksi dalam warna hijau.


Sumber yang telah saya pilah:

JP
sumber

Jawaban:

1

Sebagai bagian dari alat untuk memproses jaringan sungai saya membuat alat kontrol kualitas untuk mencari "paku" di jaringan. Sementara saya tidak menyarankan Anda menggunakan alat saya (karena untuk memproses jaringan sungai) saya mengarahkan Anda ke file Bantuan yang menunjukkan gambar dari apa yang telah saya lakukan.

Saya telah mengembangkan kode sekitar menggunakan hukum cosinus untuk mengidentifikasi sudut berturut-turut antara setiap segmen garis polyline. Anda dapat mengembangkan kode Anda sendiri di sekitar ide ini untuk melangkah sepanjang polyline dan mengidentifikasi sudut ekstrem.

Hornbydd
sumber
Saya telah menggunakan metode seperti yang Anda gambarkan (menggunakan hukum cosinus) dan termasuk jarak antar titik untuk menentukan outlier yang lebih baik, dan tampaknya bekerja dengan sangat baik. Terima kasih!
JP
8

Algoritma yang saya gunakan.

  1. Hitung pohon spanning minimum Euclidean poin:

masukkan deskripsi gambar di sini

  1. Temukan 2 poin paling jauh satu sama lain di jaringan ini

masukkan deskripsi gambar di sini

  1. Temukan rute terpendek di antara mereka:

masukkan deskripsi gambar di sini

Seperti yang dapat dilihat, itu mungkin memotong sudut pada tikungan tajam.

Saya memiliki implementasi python ArcGIS dari algoritma di atas, ia menggunakan modul networkx. Beri tahu saya jika ini menarik dan saya akan memperbarui jawaban saya dengan skrip

MEMPERBARUI:

# 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
sumber
Pendekatan yang menarik hmmm .. terima kasih sudah berbagi ini! contoh kerja akan dihargai saya yakin!
Nickes
1
Beberapa jenis perbandingan sedikit demi sedikit antara hasil pendekatan ini dan apa yang akan Anda dapatkan dengan hanya mengikuti data input mungkin memungkinkan Anda untuk menetapkan ambang batas yang akan menghilangkan "paku" tetapi masih mempertahankan sudut. Ini bisa sangat berguna jika Anda juga memiliki informasi waktu yang terkait dengan setiap titik, yang secara alami muncul dari beberapa log.
Doug McClean
1
Cukup adil. Sangat mudah untuk memodifikasi skrip dengan tidak membuat tautan antar node yang berjarak n interval waktu satu sama lain. Saya menggunakan skrip untuk hal-hal lain, bukan jalur GPS. Ada cara-cara lain untuk perbaikan juga, misalnya triangulasi, yang secara besar-besaran akan mengurangi jumlah tautan dalam grafik
FelixIP
2
Metode ini berfungsi dalam beberapa kasus, namun bentuk beberapa lintasan berarti bahwa menggunakan metode ini tidak layak dalam kasus penggunaan saya. (Masalah terjadi ketika, misalnya, lintasan menggandakan kembali pada dirinya sendiri, karena banyak node diabaikan dan zig-zags. Demikian pula, seluruh bagian lintasan dapat diabaikan jika pintu masuk / keluar bagian itu cukup dekat bersama-sama).
JP
1
@ JP untuk jalur yang mundur mungkin membantu untuk memadatkan garis mentah 1st
FelixIP
4

Satu ide adalah membuat skrip yang mencantumkan sudut (dan mungkin juga panjangnya) dari setiap segmen jalur Anda. Sekarang Anda dapat membandingkan nilai setiap segmen dengan tetangga langsungnya (dan mungkin tetangga kedua juga untuk meningkatkan akurasi) dan memilih semua titik di mana nilainya melebihi nilai threashold yang diberikan. Akhirnya cukup hapus poin dari jalur Anda.

HimBromBeere
sumber
Saya telah menggunakan metode serupa yang dijelaskan oleh @Hornbydd yang mencapai ini menggunakan hukum cosinus untuk menentukan sudut, dan juga menggabungkan jarak antar titik. Terima kasih atas sarannya.
JP
2

Juga patut dilihat adalah metode Median-5.

Setiap koordinat x (atau y) diatur ke median dari nilai 5 x (atau y) di sekitarnya secara berurutan (yaitu sendiri, dua nilai sebelumnya dan dua nilai berikutnya).

misal x3 = median (x1, x2, x3, x4, x5) y3 = median (y1, y2, y3, y4, y5) dll.

Metode cepat dan juga mudah digunakan pada streaming data.

Thrud
sumber
0

Anda dapat mengimpor data Anda ke excel atau menggunakan panda dan bendera dan atau menghapus semua jarak dari titik sebelumnya yang melebihi beberapa ambang batas jarak yang tidak realistis.

risail
sumber