Ähnlichkeit zwischen Linienzug

Question

Ich habe eine Reihe von Spuren, die von einem GPS aufgezeichnet, die formal als eine Anzahl von Linienzügen beschrieben werden kann.

Jetzt könnten einige der aufgezeichneten Spuren Aufnahmen von der gleichen Strecke, aber wegen inaccurasies in dem GPS-System, die Tatsache, dass die Aufnahmen bei verschiedenen Gelegenheiten gemacht wurden und dass sie aufgezeichnet wurden, können bei verschiedenen Geschwindigkeiten, sie passen nicht perfekt, aber immer noch nah genug aussehen, wenn auf einer Karte von einem Menschen betrachtet, um festzustellen, dass es tatsächlich die gleiche Route, die aufgezeichnet wurde.

Ich möchte einen Algorithmus finden, der die Ähnlichkeit zwischen zwei Linienzüge berechnet. Ich habe mit einigen home grown Methoden kommen, dies zu tun, aber ich würde gerne wissen, ob dies ein Problem ist, das ich bereits haben gute Algorithmen, es zu lösen.

Wie würden Sie berechnen die Ähnlichkeit, da ähnliche Mittel den gleichen Weg auf einer Karte darstellen?

Bearbeiten: Für diejenigen, unsicher, was ich spreche, schauen Sie bitte auf diesen Link für eine Definition dessen, was eine Linie String lautet: http://msdn.microsoft.com/en-us/library/bb895372.aspx - ich bin nicht fragt nach Zeichenkette.

Answer 1

Berechnen Sie die Fréchet Abstand auf wobei jedes Paar von Spuren. Der Abstand verwendet werden kann, die Ähnlichkeit der Tracks zu messen.

Math Alarm: Fréchet war ein Pionier auf dem Gebiet des metrischen Raumes , die für Ihr Problem relevant ist.

Answer 2

Ich möchte einen Puffer um die erste Zeile hinzufügen auf dem geschätzten wahrscheinlichen Fehler basiert, und dann bestimmen, ob die zweite Zeile vollständig im Puffer passt.

Answer 3

Um „gleichen Weg“, bestimmt die minimale Menge von normalisierten Pfadvektoren erstellen, berechnet die Gesamtleistungsdifferenzen und die Gesamtzahl auf einen Qualitätsmaß vergleichen.

1. Normalisieren der GPS-Wegpunkte auf Gesamtpfadlänge,
2. gehen die Vektoren der Pfade zusammen, für jeden Weg einen neuen Satz von Pfadvektoren zu schaffen an jedem Wegpunkt auf dem kürzesten Vektor basiert,
3. berechnen die Gesamtleistungsunterschiede zwischen den Endpunkten jedes Vektors in der normierten Pfade für Vektorlänge Wichten und
4. vergleichen gegen einen Qualitätsmaß.

Stimmen Sie die Leistung der Differenzen (beginnen mit, sagen wir, quadriert Unterschiede) und das Qualitätsmaß (zB als Prozentsatz der Gesamtleistungsdifferenzen) visuell. Dieser Algorithmus eine kontinuierliche Qualitätsmessung des Wegs Spiels erzeugt sowie ein binäres Ergebnis (Sind die Wege gleich?)

  

Paul Tomblin sagte: Ich würde einen Puffer hinzufügen   um die erste Linie auf der Basis   wahrscheinliche Fehler geschätzt wird, und dann   festzustellen, ob die zweite Leitung paßt   vollständig innerhalb des Puffers.

Sie können den Algorithmus als die normierten Vektor-Endpunkte ändern verglichen werden. Sie könnten bestimmen, ob ein Endpunkt Differenz oberhalb einer bestimmten Größe war (Paul-Puffer Idee Umsetzung) oder vielleicht, wenn die Endpunkte außerhalb des „Puffer“, waren diese Tatsache nutzt, dass der Endpunkt Unterschied zu ignorieren, so dass ein Vergleich ignorieren Abstechern .

Answer 4

Sie könnten entlang jeder Punkt zu Fuß (Pa) der Linestring A und messen die Entfernung von Pa bis zum nächsten Liniensegment B Linestring, wobei jeder dieser Abstände mittelt.

Dies ist keine schnelle oder perfekte Methode, soll aber Gebrauch eine nützliche Zahl geben kann und ziemlich schnell zu implementieren ist.

Sie die Linienzüge beginnen und enden an ähnlichen Punkten, oder sind sie von sehr unterschiedlichen Ausmaßen?

Answer 5

Wenn Sie eine einzelne Zeile Zeichenfolge betrachten eine Folge von sein [x, y] Punkte (oder [x, y, z] Punkte), dann könnte man die Ähnlichkeit berechnen zwischen jedem Paar von Linienzügen mit der Needleman-Wunsch-Algorithmus . Wie in dem zitierten Artikel beschrieben Wikipedias erfordert der Needleman-Wunsch-Algorithmus eine „Ähnlichkeitsmatrix“, die zwischen einem Paar von Punkten, die Entfernung definiert. Allerdings wäre es einfach, eine Funktion anstelle einer Matrix zu verwenden. In Ihrem Fall könnten Sie einfach die euklidische Distanz Funktion (oder eine Funktion 3D-euklidischen, wenn Ihr Punkte Elevation) den Abstand zwischen jedem Paar von Punkten zu liefern.

Answer 6

ich die Seite tatsächlich mit der Person (Aaron F), der sagte, dass Sie in dem Levenshtein-Distanz Problem interessiert sein könnten (und zitierte diese ). Seine Antwort scheint mir das bisher beste zu sein.

Insbesondere Levenshtein-Distanz (auch Edit-Distanz), misst nicht streng an die Zeichen-für-Zeichen-Abstand, sondern auch ermöglicht es Ihnen, Einfügungen und Löschungen durchzuführen. Der beste Algorithmus für diese Abstandsmessung kann in quadratischer Zeit berechnet werden (ziemlich langsam, wenn die Saiten sind lang), aber die Bioinformatiker haben ziemlich gute Heuristik für diese, die auf ihren eigenen für Sie von Interesse sein könnten. Schauen Sie sich BLAST und FASTA .

Ihr Problem, so scheint es, dass Sie mit den Unterschieden zwischen den Zahlenketten zu tun haben, und Sie kümmern sich um die Zahlen. Wenn Sie weitere Informationen geben, könnte ich in der Lage sein, Sie an die richtige Variante von BLAST / FASTA zu lenken / etc für Ihre Zwecke. In jedem Fall sollten Sie überlegen, BLAST und FASTA für Ihre Bedürfnisse anzupassen. Sie sind ganz einfach.

1 : http://en.wikipedia.org/wiki/Levenshtein_distance , http://www.nist.gov/dads/HTML/Levenshtein.html