Algorithmus zur Quantifizierung der Differenz der Liniensegment-Paths

Question

sagen, ich habe zwei Liniensegment Pfade, wie beispielsweise eine Teilmenge der folgenden Beispiele. Wie kann ich den Unterschied zwischen ihnen quantifizieren?

1. | __
2. \ _
3. _ _
4. / \
5. \ /
6. |
7. _

Die beiden Wege kann eine unterschiedliche Anzahl von Segmenten aufweisen, und die Länge jedes Segments und der Winkel zwischen ihnen ist veränderlich.

Ich dachte, es wäre gut, ein Koordinatensystem zu etablieren und die Segmente als Knoten und Kanten zu definieren. Der Unterschied könnte vielleicht durch die Operationen quantifiziert werden benötigt einen in die andere zu verwandeln, ähnlich wie die Levenshtein Abstand Algorithmus. Leider ist der Arbeitsraum sehr groß. Irgendwelche Ideen? Dank!

Answer 1

Ich werde ein bisschen weiter gehen als das, was @awoodland darauf hingewiesen:., Wie Sie quantifizieren es hängt ganz auf, warum Sie den Unterschied quantifizieren wollen

Möchten Sie mit einer einzigartigen kommen (zumindest dürfte weltweit einmalig sein) Nummer wie ein Hash-Code für ein Liniensegment Weg? Oder versuchen Sie Liniensegment Wege zu quantifizieren zu sagen: „Dieser Weg ist komplexer (oder länger, oder haben spitzen Winkel) als dieser Weg“?

Wenn Sie einen Hash-Code erstellen möchten, würde ich vorschlagen, zwei 32-Bit-CRCs zu schaffen (oder so ähnlich): eine für die Segmentlängen und eine für die Winkel. Sobald Sie diese CRCs berechnet haben, setzen sie zusammen in einem 64-Bit-Wert mit den Winkeln in den hohen 32 Bits und die Längen in den niedrigen 32 Bit. Je nach Anzahl der Segmente, vielleicht ein einzelner CRC-Wert tun würde:. Für jedes Segment, fügen Sie die Länge und dann den Winkel zwischen ihm und dem nächsten Segment

Beachten Sie, dass die oben wahrscheinlich, dass Ihnen eine eindeutige Nummer für jeden Weg zu geben, aber nicht garantiert.

Wenn Sie die Komplexität des Liniensegments Weg quantifizieren wollen ... Ich weiß nicht viele Ideen haben.

Answer 2

Sie könnten sie in fester Größe Bilder zeichnen und dann euklidischen Abstand verwenden, um die Bilder zu vergleichen.

Oder Sie könnten die Gesamtlänge und die Summe der Absolutwert der Winkel (sowie die unterschriebenen Winkel vielleicht) als Maß messen. Etwas auf dieser Grundlage würde die schöne Eigenschaft, invariant zu der Ausrichtung der Form hat (wenn man das will!).

Wie Sie quantifizieren es hängt etwas von Warum Sie wollen den Unterschied zwischen ihnen zu quantifizieren.

Answer 3

Sie können an diesem Papier aussehen:

http://www.vision.ee.ethz.ch /~calvin/Publications/ferrari07pami.pdf

In diesem Papier verwenden wir KAS (eine Verallgemeinerung von Segmenten Paare: Sie mehrere Segmente jeweils anderen verbunden haben kann) für die Objekterkennung. Wir stellen einen Beschreiber für diese Gruppen von Segmenten, dass Sie Ihre Paare zu beschreiben, verwenden können.

Unser Descriptor ist nicht drehungsinvarianten, damit es nicht zu Ihnen passen könnte.

Answer 4

Wenn Sie Operationen verwenden:

• In Ecke und Segment
• Entfernen Ecke und Segment
• Stretch-Segment (mit dem Gewicht der Differenz)
• Bend-Ecke (mit dem Gewicht der Differenz)

Sie würden noch in der Lage sein Levenshtein Abstand zu verwenden, während noch in n ^ 2 Zeit.

Encode die Segmente wie folgt [Segment Ecke] *. Es wäre also:

[length, rotation] [length, rotation]...

Wo Drehung auf das Segment Zeigerichtung jeweils ist.

Die Berechnung Strecken und Beugen ist ganz offensichtlich. Value[i-1, j-1] + stretch + bend.

Die Berechnung Hinzufügen / Entfernen. In Value[i,j-1] + Cost of adding, entfernen Value[i-1, j] + cost of removal.