Algorithmus zur Ähnlichkeitssuche

[mit]

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).



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.



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

Viele Grüße

[numerix]

Ich verstehe das Problem nicht:

Du kennst die Koordinaten der Punkte aus Bild 1?
Aber nicht die Koordinaten der Punkte aus Bild 2?
Wenn doch, dann brauchst du ja nur nach den Koordinaten zu suchen.
Wenn nicht, dann ist die Frage, was du über die Punkte aus Bild 2 weißt: Kennst du nur die Abstände aller paarweise verbindbaren Punkte?

Deine Hinweise auf die Abstände verstehe ich an sich nicht.

[BlackJack]

Ich nehme mal an gegeben sind die Abstände aus 1 und die Koordinaten der Punkte aus 2 und gefragt ist die Menge der Punkte die möglichst genau im Abstandsverhältnis aus 1 stehen. Wobei das nicht wirklich eindeutig ist, weil die Abstandsbeziehungen ja durchaus auf mehrere Punktmengen zutreffen können. Triviales Beispiel: Abstand zwischen zwei Punkten ist 1 und die zu untersuchende Punktmenge sind n*2 gleichmässig auf einem Kreis mit Durchmesser 1 verteilte Punkte.

Das würde jedenfalls als (nichttriviale) Frage Sinn machen. Klingt ein wenig nach einem Rätsel oder einer Hausaufgabe. So á la: Wir haben einen Fahrtenschreiber mit zurückgelegten Strecken und eine Karte von Land X. Welche Städte hat der LKW-Fahrer wohl angesteuert?

[Rebecca]

Den Abstand zweier Punkte x, y ist die Laenge des Vektors x - y.
Die Laenge eines Vektors x ist sqrt((x|x)), oder ausgeschrieben sqrt (x_1**2 + x_2 **2 + x_3 **2).

Jetzt kannst du ueber die Punkte der zweite Vektorenmenge laufen und jeweils die Abstaende zu den Punkten aus der ersten Menge ausrechnen. Diejenigen Punkte aus der zweiten Menge, bei denen besageter abstand "sehr klein wird", sind dann die gesuchten.

Zumindest nach meiner Interpretation des Posts (Die Abstaende der Punkte der ersten Menge zueinander braucht man da nicht.)

[HWK]

Wenn es sich um sehr viele Punkte handelt, scheint das ein komplexes Problem zu sein. Hier geht es ja wohl um etwas Ähnliches. Du kannst Dich ja einmal mit der dort angegebenen umfangreichen Literatur beschäftigen.
MfG
HWK

[BlackJack]

@Rebecca: Ob man die Abstände in der ersten Menge braucht, hängt ganz von der Aufgabenstellung ab. Ich vermute ja wie gesagt, dass das die einzigen Daten sind, die über Menge 1 gegeben sind. Denn Deine Fragestellung/Lösung ist ja nun wirklich trivial und das der Aufgabensteller, ob das nun der OP ist oder jemand anders, wird sich beim einzeichnen der Kanten wohl etwas gedacht haben.

Aber da muss mit wohl nochmal eine Klarstellung liefern.

[mit]

@ numerix:
Ich kenne die Koordinaten der Punkte aus Bild 1 und Bild 2. Die suche nach den selben Koordinaten führt leider nicht immer zum Ziel, da es möglich sein kann, dass das Bild 1 im Bild 2 in einer anderen Orientierung liegt, also gedreht ist.

Die Abstände sollen dazu dienen das wirklich das Muster aus Bild 1 in Bild 2 gefunden wird.

@ BlackJack:
Ja ich kenne die Abstände aus Bild 1 und alle Koordinaten im Bild 1 und 2. Vielleicht hilft ja wenn man die Punkte zusätzlich makiert. 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.

@ Rebecca:
Das mit Vetktoren hört sich gut an. Aber ab den zweiten Punkt müsst man noch die Richtung betrachten können, da das Muster aus Bild 1 im Bild 2 in einer anderen orientierung vorliegen müsste.

@ HWK:
Danke für den Link es hört sich wirklich nach meinem Problem an. Denn ich suche ein Muster aus Bild 1 in Bild 2. Wobei das Muster aus Bild 1 in Bild2 in einer anderen Orientierung vorliegen kann. Jetz muss ich nur an die Literatur ran kommen. Ist dir vielleicht schon ein Algorithmus bekannt, weil die Literatur aus 1997 ist.

Hat jemand eine Idee ob schon etwas fertiges gibt?

[HWK]

Hier scheint es ziemlich viel Informationen zu geben.
MfG
HWK

[mit]

Danke für den Link. Ich glaube ich benötige "Branch and Bound"-Algorithmus hast du vielleicht eine Implementierung irgendwo schon gesehen?

[HWK]

Hier gibt es wohl einiges. Diese Seite ist zwar in Tschechisch, mit dem Python-Code kannst Du aber vielleicht trotzdem etwas anfangen.
MfG
HWK

[mit]

Danke für die Links.

[Konrad Wenzel]

- alle Links habe ich nicht gelesen, würde aber mal folgenden Ansatz verfolgen und eine Lösung in PYTHON ins Forum posten, falls es ein paar Wochen Zeit hat:

Die unteren vier Punkte der Menge 1 liegen nicht immer, wie es hier aussieht, in einer Ebene,
es sind aber immer 5 oder mehr Punkte M

3 Punkte der Menge 1 legen jeweils mit 3 Punkten der Menge 2 eine eindeutige Abbildung
fest (Tensoren) --> Abbildungsformel = AF
Dann bleiben M-3 Punkte der Menge 1, die per AF in Menge 2 in [einem gewählten Unschärfewürfell(x,y,z)+-d] aufgefunden werden - ein Treffer; oder eben nicht.

Die Anzahl der AF ist zwar endlich, aber bei größeren Punktmengen könnte es dauern, bis der Algorithmus endet

Zunächst werde ich eine 5 - 5 Menge benutzen und vielleicht ist dabei abzusehen, wie der Aufwand zu verkleinern ist.