Algorithmus zur Ähnlichkeitssuche

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Algorithmus zur Ähnlichkeitssuche

    Hallo,
    Ich habe Punkte im Raum die durch die Koordinaten x,y,z dargestellt werden und der Abstand zwischen den Punkten ist bekannt (siehe Bild 1).

    [Blockierte Grafik: http://mitlox.republika.pl/similarsearch/similar-search1.png]

    Im Bild 2 habe ich jede Menge Punkte (x,y,z) die im Raum liegen und jetzt möchte ich die Punkte aus Bild 1 im Bild 2 finden.
    Der Abstand darf einwenig abweichen.

    [Blockierte Grafik: http://mitlox.republika.pl/similarsearch/similar-search2.png]

    Gibt es bereits ein Algorithmus mit dem die Punkte aus Bild 1 in Bild 2 finden kann?

    Viele Grüße

  • Hallo,

    meines erachtens ist das nicht mathematisch lösbar, du musst das geometrisch lösen, sprich eine Abtastung schreiben. Damit wirst du vermutlich am schnellsten sein. Weil die anzahl der Testmöglichkeiten wären mathematisch 11! = 39 916 800 möglichkeiten. Von daher, kannst du es meiner Meinung nach nur durch eine Abtastung raus finden. Wenn du aber noch sagen kannst, was alles genau gegeben ist, gibt es eventuell noch eine andere Lösung, aber derzeit nicht.

    so long
    jd
    Erst wenn der letzte FTP Server kostenpflichtig, der letzte GNU-Sourcecode verkauft, der letzte Algorithmus patentiert, der letzte Netzknoten kommerzialisiert, die letzte Newsgroup moderiert wird, werdet Ihr merken, dass man mit Geld allein nicht programmieren kann.

  • ich denke auch, das es mathematisch keinesfalls lösbar ist...

    aber durch probieren krigst du das relativ schnell raus...

    ich hatte dazu gerade so eine idee...

    du machst das via vectoren...
    du nimmst einen vector, und schaust erstmal bei allen punkten, ob der vector nun genau auf einen anderen punkt zeigt...
    so, den rest der punkte verwerfen wir (also bleiben erstmal immer 2 paare an punkten, und davon wahrscheinlich ein paar...)
    das selbe machst du nun nochmal, abe rmit einem anderen vector... usw
    irgentwann (wenn du alle vectoren fertig hast), bleibt die lösungsmenge übrig.

    so würde ich das denke ich lösen...

  • ich würde stinknormales Backtracking einsetzten:

    Ums anschaulicher zu machen nenne ich die Punkte in Bild1 mal A1, A2, ..., A5 und die in Bild 2 B1, B2, ...., B11.

    Anfangen würde ich dann so:
    Ich versuche A1 zu besetzen indem ich zufällig einen Punkt aus B auswähle, beispielweise B1. Da es noch keinen Widerspruch gibt (woher auch) gehe ich weiter und Versuche A2 zu besetzen. Ich wähle wieder zufällig aus den übrigen Bs einen aus und überprüfe jetzt ob der Abstand zu B1 passt (also ob er dem von A1 zu A2 entspricht). Passt er, gehe ich weiter und versuche A3 zu besetzten, passt er nicht versuche ich ein anderes B für A2. Finde ich an einer Stelle keinen Punkt aus B mehr der passt, gehe ich einen Schritt zurück und versuche es mit dem nächsten.

    Hm, ich glaub die Erklärung ist jetzt nicht sooo verständlich, aber vieleicht wird ja doch ersichtlich worauf ich hinauswill. Allgemein zum Backtracking hilft vieleicht auch noch http://de.wikipedia.org/wiki/Backtracking.

    Zum Aufwand: Im absoluten Worst-Case, der quasi nur auftritt, wenn ich die Aufgabenstellung extra fies gestalte, braucht der Algorithmus in diesem Fall 11! / 6! = 55440 Schritte. Im normalfall sollte er weit darunter liegen (wobei selbst die 55000 vom Rechenaufwand her

  • @ JFoX:
    Wie würde eine Abtastung funktionieren. Ich kenne die Koordinaten der Punkte aus Bild 1 und Bild 2. Die Abstände sollen dazu dienen das wirklich das Muster aus Bild 1 in Bild 2 gefunden wird. Vielleicht hilft ja wenn man die Punkte zusätzlich makiert werden. Dann würde man zuerst Punkt A aus Bild 1 in Bild 2 suchen und anschließen Punkt B aus Bild 1 in Bild 2 suchen. Aber ab den dritten Punkt C müsste man zusätlich noch die Winkel vergleichen damit man das Muster aus Bild 1 im Bild 2 findet.


    @ pocky:
    Hört sich gut an mit Vektoren. Du meinst in Bild 1 bestimme ich alle Vetktoren zwischen den Punkten. Dann suche ich mir im Bild 2 ein Punkt aus und benutze die Länge des Vektors aus Bild 1 und drehe in alle Richtungen um den zweiten Punkt zu finden. Aber um den dritten Punkt bestimmen zu können muss ich zusätlich noch Winkel betrachten, weil das Muster aus Bild 1 in Bild 2 in einer anderen Orientiertung vorliegen könnte.

    Leider verstehe ich nicht ganz welche Punkte du verwerfen möchtest (aus Bild 1 oder 2)?

    @ Rondrer:
    Ja das würde funktionieren, aber leider kann es sein, dass das Muster aus Bild 1 in Bild 2 in einer anderen Orientierung liegt. Wahrscheinlich müßte man noch die Winkel ab den zweiten gefunden Punkt vergleichen.

  • du suchst dir einen punkt, welchen du mit (0|0|0) bezeichnest, und von diesem aus, holst du dir den vector zu allen anderen punkten (von Bild 1)
    dann nimmst du jeden einzelnen Punkt von Bild 2, und schaust, ob ein vector von dem punkt aus auf nem anderen punkt liegt...
    wenn nein, verwirfst du einfach den punkt, und machsr den nächsten...
    alle übriggebliebenen testest du nach den nächsten vector