Ich habe zwei Sequenzen der Länge n und m. Jede ist eine Folge von Punkten der Form (x, y) und repräsentiert Kurven in einem Bild. Ich muss herausfinden, wie verschieden (oder ähnlich) diese Sequenzen gegeben sind, dass
Diese Sequenzen könnten in entgegengesetzten Richtungen liegen (d. h. Sequenz 1 geht von links nach rechts, während Sequenz 2 von rechts nach links geht)
Ich habe einige Differenzenschätzungen wie Levenshtein sowie Editierabstände in der Strukturähnlichkeit, die für die Proteinfaltung passen, untersucht, aber keiner von ihnen scheint den Trick zu machen. Ich könnte meine eigene Brute-Force-Methode schreiben, aber ich möchte wissen, ob es einen besseren Weg gibt.
Danke.
Eine Methode in dieser Richtung könnte funktionieren:
Für beide Sequenzen:
Passen Sie eine Kurve durch die Sequenz. Stellen Sie sicher, dass Sie eine kontinuierliche Eins-zu-eins-Funktion von [0,1] bis zu Punkten auf dieser Kurve haben. Das heißt, für jede (reale) Zahl zwischen 0 und 1 gibt diese Funktion einen Punkt auf der zugehörigen Kurve zurück. Wenn Sie die Funktion für alle Zahlen von 0 bis 1 verfolgen, erhalten Sie die gesamte Kurve.
Eine Möglichkeit, eine Kurve anzupassen, wäre, eine gerade Linie zwischen jedem Paar aufeinander folgender Punkte zu ziehen (es ist keine schöne Kurve, weil es scharfe Kurven hat, aber für Ihren Zweck könnte es gut sein). In diesem Fall kann die Funktion durch Berechnen der Gesamtlänge aller Liniensegmente (Pythagoras) erhalten werden. Der Punkt auf der Kurve, der einer Zahl Y (zwischen 0 und 1) entspricht, entspricht dem Punkt auf der Kurve, der einen Abstand Y * (Gesamtlänge aller Liniensegmente) von dem ersten Punkt der Sequenz aufweist, gemessen durch Fahren über die Liniensegmente (!!).
Nun, nachdem wir eine solche Funktion F (double) für die erste Sequenz und G (double) für die zweite Sequenz erhalten haben, können wir die Ähnlichkeit wie folgt berechnen:
%Vor%Mögliche Verbesserungen:
- Finden Sie eine verbesserte Methode, um die Kurven anzupassen. Beachten Sie, dass Sie immer noch die Funktion benötigen, die die Kurve für die oben beschriebene Methode zeichnet.
- Bei der Berechnung der Entfernung sollte die Funktion G so neu parametrisiert werden, dass der Abstand minimiert wird. (Das heißt, Sie haben eine zunehmende Funktion R, so dass R (0) = 0 und R (1) = 1, aber das ist sonst allgemein. Bei der Berechnung der Entfernung verwenden Sie
%Vor%Anschließend versuchen Sie, R so zu wählen, dass die Entfernung minimiert wird. (Um zu sehen, was passiert, beachte, dass G (R (d)) auch die Kurve verfolgt)).
Meinst du, du versuchst Kurven zu vergleichen, die in x, y Koordinaten übersetzt wurden? Eine Technik der Bildverarbeitung ist die Verwendung von Kettencodes [ Ich suche nach einer anständigen Referenz, aber alles, was ich im Moment finden kann, ist dies ], um jede Sequenz zu codieren und dann diese Kettencodes zu vergleichen. Sie könnten die Summe der Differenzen nehmen (Modulo 8) und wenn das Ergebnis 0 ist, sind die Kurven identisch. Da die Sequenzen unterschiedliche Längen haben und nicht notwendigerweise an der gleichen relativen Position beginnen, müssten Sie eine Sequenz verschieben und dies immer wieder tun, aber Sie müssen die Kettencodes nur einmal erstellen. Der einzige Weg, um festzustellen, ob eine der Sequenzen umgekehrt ist, besteht darin, sowohl die Vorwärts- als auch die Rückwärtsrichtung einer der Sequenzen zu versuchen. Wenn die Kurven nicht genau gleich sind, wird die Summe größer als Null sein, aber es ist nicht einfach zu sagen, wie unterschiedlich die Kurven einfach von der Summe sind.
Diese Methode ist nicht rotationsinvariant. Wenn Sie eine rotationsinvariante Methode benötigen, sollten Sie sich die Boundary-Centered Polar Encoding-Funktion ansehen. Ich kann keine kostenlose Referenz dafür finden, aber wenn Sie mich brauchen, um es zu beschreiben, lassen Sie es mich wissen.
Warum nicht eine Art von Kurvenanpassungsprozedur (kleinste Quadrate, ob normal oder nichtlinear) durchführen und sehen, ob die Koeffizienten der Formparameter gleich sind. Wenn Sie es als ein Panel-Data-Modell ausführen, gibt es explizite statistische Tests, ob sich Parametergruppen signifikant voneinander unterscheiden. Das würde das Problem der gleichen Kurve lösen, aber bei unterschiedlichen Auflösungen abgetastet werden.
Schritt 1: Canonicalize die Ausrichtung. Nehmen wir beispielsweise an, dass alle Kurven am Endpunkt mit der niedrigsten lexikographischen Ordnung beginnen.
%Vor%Schritt 2: Sie können entweder grob oder sehr genau sein. Wenn Sie sehr genau sein wollen, berechnen Sie einen Spline oder passen Sie beide Kurven an ein Polynom mit geeignetem Grad an und vergleichen Sie die Koeffizienten. Wenn Sie nur eine grobe Schätzung möchten, gehen Sie wie folgt vor:
%Vor%Dies kann von einem linearen Resampling zu etwas Besserem geändert werden.
%Vor%Wo Z ungefähr so ist wie der "Durchmesser" Ihres Pfades, vielleicht der maximale euklidische Abstand zwischen zwei beliebigen Punkten in einem Pfad.
Ich würde eine Kurvenanpassungsprozedur verwenden, aber auch einen konstanten Term einwerfen, dh 0 = B0 + B1 * X + B2 * Y + B3 * X * Y + B4 * X ^ 2 usw. Dies würde die Translationsvarianz erfassen und dann können Sie einen statistischen Vergleich der geschätzten Koeffizienten der Kurven, die durch die zwei Punktsätze gebildet werden, als eine Möglichkeit zum Klassifizieren derselben durchführen. Ich gehe davon aus, dass Sie eine bivariate Interpolation durchführen müssen, wenn die Daten willkürliche Kurven in der x-y-Ebene bilden.
Tags und Links math edit-distance numerical-methods