Hypercell ein ] Hypercell aus ] Zeige Navigation ] Verstecke Navigation ]
c++.net  
   

Die mobilen Seiten von c++.net:
https://m.c-plusplus.net

  
C++ Forum :: Mathematik und Physik ::  Kabsch Algorithmus     Zeige alle Beiträge auf einer Seite Auf Beitrag antworten
Autor Nachricht
Stevo465
Unregistrierter




Beitrag Stevo465 Unregistrierter 17:11:50 03.01.2017   Titel:   Kabsch Algorithmus            Zitieren

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
Moderator

Benutzerprofil
Anmeldungsdatum: 16.01.2002
Beiträge: 8670
Beitrag Gregor Moderator 17:27:34 03.01.2017   Titel:              Zitieren

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:
Zitat:

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.

_________________
"Die Mathematiker sind eine Art Franzosen: Redet man zu ihnen, so übersetzen sie es in ihre Sprache, und dann ist es alsobald ganz etwas anderes." - Johann Wolfgang von Goethe


Zuletzt bearbeitet von Gregor am 17:31:15 03.01.2017, insgesamt 2-mal bearbeitet
Stevo465
Unregistrierter




Beitrag Stevo465 Unregistrierter 17:41:47 03.01.2017   Titel:              Zitieren

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:
Zitat:

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
Moderator

Benutzerprofil
Anmeldungsdatum: 16.01.2002
Beiträge: 8670
Beitrag Gregor Moderator 17:51:47 03.01.2017   Titel:              Zitieren

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:

Code:
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.

_________________
"Die Mathematiker sind eine Art Franzosen: Redet man zu ihnen, so übersetzen sie es in ihre Sprache, und dann ist es alsobald ganz etwas anderes." - Johann Wolfgang von Goethe
Stevo465
Unregistrierter




Beitrag Stevo465 Unregistrierter 18:00:01 03.01.2017   Titel:              Zitieren

Gregor schrieb:
Im Wesentlichen kannst Du Deinen Kabsch Algorithmus als Kern eines ICP Algorithmus verwenden. In etwa so:

Code:
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!
Stevo465
Unregistrierter




Beitrag Stevo465 Unregistrierter 17:09:27 10.01.2017   Titel:              Zitieren

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?
Stevo465
Unregistrierter




Beitrag Stevo465 Unregistrierter 18:13:38 10.01.2017   Titel:              Zitieren

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.
Stevo465
Unregistrierter




Beitrag Stevo465 Unregistrierter 19:57:51 11.01.2017   Titel:              Zitieren

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... :(
Stevo465
Unregistrierter




Beitrag Stevo465 Unregistrierter 23:11:07 11.01.2017   Titel:              Zitieren

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.
C++ Forum :: Mathematik und Physik ::  Kabsch Algorithmus   Auf Beitrag antworten

Zeige alle Beiträge auf einer Seite




Nächstes Thema anzeigen
Vorheriges Thema anzeigen
Sie können Beiträge in dieses Forum schreiben.
Sie können auf Beiträge in diesem Forum antworten.
Sie können Ihre Beiträge in diesem Forum nicht bearbeiten.
Sie können Ihre Beiträge in diesem Forum nicht löschen.
Sie können an Umfragen in diesem Forum nicht mitmachen.

Powered by phpBB © 2001, 2002 phpBB Group :: FI Theme

c++.net ist Teilnehmer des Partnerprogramms von Amazon Europe S.à.r.l. und Partner des Werbeprogramms, das zur Bereitstellung eines Mediums für Websites konzipiert wurde, mittels dessen durch die Platzierung von Werbeanzeigen und Links zu amazon.de Werbekostenerstattung verdient werden kann.

Die Vervielfältigung der auf den Seiten www.c-plusplus.de, www.c-plusplus.info und www.c-plusplus.net enthaltenen Informationen ohne eine schriftliche Genehmigung des Seitenbetreibers ist untersagt (vgl. §4 Urheberrechtsgesetz). Die Nutzung und Änderung der vorgestellten Strukturen und Verfahren in privaten und kommerziellen Softwareanwendungen ist ausdrücklich erlaubt, soweit keine Rechte Dritter verletzt werden. Der Seitenbetreiber übernimmt keine Gewähr für die Funktion einzelner Beiträge oder Programmfragmente, insbesondere übernimmt er keine Haftung für eventuelle aus dem Gebrauch entstehenden Folgeschäden.