Kabsch Algorithmus

Hallo,

ich implementiere gerade den Kabsch.

https://en.wikipedia.org/wiki/Kabsch_algorithm

Leider habe ich das Problem dass wenn die Punkte (3d) in meiner Eingangsmatrix in einer anderen Reihenfolge vorliegen, als die in der Ausgangsmatrix der Algorithmus scheitert.

Kurzum, die Trafo-Matrix ist dann kompletter Nonsens.

Weiß jemand eine idee, wie ich das problem lösen könnte?

Gregor

Nach dem, wie ich den Wikipedia-Eintrag interpretiere, geht der Algorithmus davon aus, dass man die paarweisen Zugehörigkeiten der Punkte zu einander im Vorfeld klärt:

The algorithm starts with two sets of paired points, P and Q.

Der Iterative Closest Point Algorithmus macht das nicht, sollte aber das gleiche Ziel haben (und ist vielleicht wesentlich allgemeiner als Du es brauchst):

https://en.wikipedia.org/wiki/Iterative_closest_point

Leider scheint auf Wikipedia keine detaillierte Beschreibung des Algorithmus vorhanden zu sein. Dazu sollte es aber trotzdem jede Menge Material zu finden geben.

Im Wesentlichen wird der Unterschied sein, dass mehrere Tranformationen nach einander durchgeführt werden und nach jeder Transformation die Zugehörigkeiten zwischen den Punkten neu festgelegt werden. ...mit dem jeweils am nächsten liegenden Punkt aus der anderen Punktmenge.

Gregor schrieb:

Nach dem, wie ich den Wikipedia-Eintrag interpretiere, geht der Algorithmus davon aus, dass man die paarweisen Zugehörigkeiten der Punkte zu einander im Vorfeld klärt:

The algorithm starts with two sets of paired points, P and Q.

Richtig. Deshalb scheitert auch meine Implementierung bei nicht korrespondierenden Punkten.

Eine Möglichkeit wäre wohl die Punkte vorab nach ihrer Distanz zu sortieren.

Ich kenne ja die Distanz der Punkte in der Eingangsmatrix. Also sortiere ich die Ausgangsmatrix auch so.

Natürlich bedeutet das Rechenaufwand, weil ich die Distanz von jedem Punkt zu jedem anderen ausrechnen muss.

Gregor schrieb:

Der Iterative Closest Point Algorithmus macht das nicht, sollte aber das gleiche Ziel haben (und ist vielleicht wesentlich allgemeiner als Du es brauchst):

https://en.wikipedia.org/wiki/Iterative_closest_point

Leider scheint auf Wikipedia keine detaillierte Beschreibung des Algorithmus vorhanden zu sein. Dazu sollte es aber trotzdem jede Menge Material zu finden geben.

Im Wesentlichen wird der Unterschied sein, dass mehrere Tranformationen nach einander durchgeführt werden und nach jeder Transformation die Zugehörigkeiten zwischen den Punkten neu festgelegt werden. ...mit dem jeweils am nächsten liegenden Punkt aus der anderen Punktmenge.

Ja, der ICP ist allgemeiner. Gibt auch genug Implementierungen bzw. fette Bibliotheken mit Hilfe von K-D-Bäumen etc.

Aber das ist mir zuviel des Guten. Ich wollte etwas eigenes. Klar, möglichst kompakt.

Laufzeitverhalten ist nicht so entscheidend, weil ich nicht allzu viele Punkte habe.

Gregor

Stevo465 schrieb:

Ja, der ICP ist allgemeiner. Gibt auch genug Implementierungen bzw. fette Bibliotheken mit Hilfe von K-D-Bäumen etc.

k-d Bäume sind doch nur Beiwerk für Leute, die es besonders gut machen möchten. Im Wesentlichen kannst Du Deinen Kabsch Algorithmus als Kern eines ICP Algorithmus verwenden. In etwa so:

Bis Abbruchkriterium erfüllt wiederhole:

   1. Assoziiere jeden Punkt aus Menge A mit dem jeweils nächsten Punkt aus Menge B und ordne die Punkte entsprechend an.

   2. Führe Kabsch aus und rotiere die Punkte danach entsprechend.

Gregor schrieb:

Im Wesentlichen kannst Du Deinen Kabsch Algorithmus als Kern eines ICP Algorithmus verwenden. In etwa so:
Bis Abbruchkriterium erfüllt wiederhole:

   1. Assoziiere jeden Punkt aus Menge A mit dem jeweils nächsten Punkt aus Menge B und ordne die Punkte entsprechend an.

   2. Führe Kabsch aus und rotiere die Punkte danach entsprechend.

Ja, läuft im Prinzip aufselbe raus.

Gut. Habe jetzt ein Bild vor Augen. Danke für deine Antworten!

Habe jetzt den ICP mit einem KD-Tree implementiert.

Dummerweise konvergiert der Algo nicht immer. Zum Beispiel verändere ich einfach nur mal die Reihenfolge der Ausgangspunkte und schon landet mein Algo in einem lokalen Minimum und nicht im globalen.

Zur Optimierung könnte ich jetzt noch die Abweichung T=R*M+2 berechnen und schauen ob es matched. Wenn nicht, permutiere ich die Ausgangspunkte und lasse den Algo erneut laufen.

Was gibt es da noch für Möglichkeiten?

So.

Ausgangspunkte um 1 verschieben, bis ich unter eine minimale Distanz/Fehler bin, funktioniert.

Im schlechtesten Fall habe ich natürlich dann n-1 Aufrufe.

Sorry, habe Scheiße erzählt.

Die Konvergenz ist nicht abhängig von der Reihenfolge der Punkte, sondern ganz massiv von der initialen Transformationsmatrix.

A = R * B + t

R und t entscheiden ganz massiv darüber, ob ich am Ende über meinen ICP korrekte Daten bekomme.

Ziemlich unbefriedigend...

Habe es jetzt dadurch gelöst, dass ich um X,Y,Z um 1 Grad rotiere.

Alle meine Beispiel-Punktwolken konvergieren dann irgendwann.

Kritisch beim ICP scheint tatsächlich die Rotationsmatrix zu sein. Wenn die nicht zum Problem passt, konvergiert (global) das Ding einfach nicht.