Anpassen eines Satzes von Punkten an einen anderen durch eine starre Bewegung

8

Ich bin mir nicht sicher, wie ich dieses Problem klar erklären soll. Bitte nehmen Sie Kontakt mit mir auf. Ich habe eine Basis von 3 orthonormalen Einheitsvektoren und eine Position, eine Standard-4x4-Transformationsmatrix in der Computergrafik.

Außerdem habe ich mehrere Punkte (Offsets) in diesem Raum, die ich in den Weltraum verwandle. Die Punkte werden dann leicht gestört, und jetzt möchte ich die neue Basis finden, die der Darstellung der gestörten Punkte am nächsten kommt.

Es ist nicht genau so, als würde man Hauptkomponenten finden, weil ich möchte, dass die ursprünglichen Offsets berücksichtigt werden. Wenn das Sinn macht. Wie Federn von jedem neuen Punkt zu ihren jeweiligen Startpositionen. Ich denke, die Antwort liegt in der Lösung eines Problems der kleinsten Quadrate, aber ich habe es mir angesehen und jetzt tut mir der Kopf weh.

Kann es mir jemand einfach erklären. Ich würde eine geschlossene Lösung bevorzugen, aber eine iterative wäre auch in Ordnung. Vielen Dank

DaleyPaley
quelle
Weitere Details zu Ihrem Problem müssen angegeben werden. Anscheinend haben Sie eine starre Transfomation ("3 orthonormale Einheitsvektoren und eine Position"), die aus einer orthogonalen Transformation und einer Translation besteht. Wahrscheinlich fragen Sie, wie Sie die orthogonale Transformation ändern können, wobei der Translationsteil fest bleibt, damit die neu gestörten Punkte am besten angenähert werden (indem Sie die angepasste starre Transformation auf die ursprünglichen Punkte anwenden). Schreiben Sie Details auf: Benennen Sie die Transformationen, die Übersetzung, die Punkte. Geben Sie vor allem an, welches Kriterium (kleinste Quadrate?) Die beste Anpassung bestimmt.
Hardmath
Ja, tut mir leid, ich bin mir nicht sicher, welche Terminologie und wie ich sie am besten beschreiben kann. Eigentlich möchte ich auch die Position ändern. Orthogonale Basis + Position ist eine affine Transformation, oder? Ich habe also eine affine Transformation, A, die eine kleine Anzahl von Punkten transformiert, und ich möchte A finden, damit die Transformation den Punkten so gut wie möglich folgt, nachdem sie gestört wurden. Ich hoffe das ist klarer.
DaleyPaley
1
Dies ist ein "klassisches" Problem mit einem "klassischen" Namen, das orthogonale Procrustes-Problem , meine Lieblingsanwendung von SVD (Singular Value Decomposition).
Hardmath
1
Ja, gib mir ein bisschen Zeit, darüber nachzudenken, es schön aufzuschreiben.
Hardmath
1
Ich weiß, dass dies ungefähr 2 Jahre zu spät ist, aber ich habe einen Code auf Github, der die SVD verwendet, um diese Art von Problem zu lösen. Vielleicht hilft es Ihnen? Hier ist der Link
Entwickler Paul

Antworten:

14

Inge Söderkvist (2009) hat eine schöne Zusammenfassung der Lösung des Problems der starren Körperbewegung durch Singular Value Decomposition (SVD).

{x1,,xn}{y1,,yn}Rdxi

i=1n||Rxi+dyi||2

xi,yiR3×3det(R)=1

Der erste Schritt besteht darin, die jeweiligen Mittelwerte von den Punkten , was den Effekt hat, dass die unbekannte Übersetzung (vorerst) "eliminiert" wird . Das heißt, das Problem wird:x¯,y¯xi,yid

minRSO(3)||RAB||F

Dabei ist und . Hier bezeichnet die spezielle orthogonale Gruppe von Rotationsmatrizen in 3D, aus der wir auswählen dürfen , und die Matrixnorm bezeichnet hier die Frobenius-Norm , dh die Quadratwurzel der Summe der Quadrate von Matrixeinträgen (wie ein Euklidischer Norm, aber auf Matrixeinträgen).A=[x1x¯,,xnx¯]B=[y1y¯,,yny¯]SO(3)RF

Jetzt sind beide Matrizen. Die obige Minimierung ist ein orthogonales Procrustes-Problem, das nur Rotationsmatrizen zulässt. Die Lösung ergibt sich aus der Singularwertzerlegung der "Kovarianz" -Matrix :A,B3×nRC=BAT

C=USVT

Dabei sind orthogonale Matrizen und die diagonale Matrix der Singularwerte . Numerische lineare Algebra-Pakete wie Matlab und Octave berechnen die SVD für Sie.U,VS=diag(σ1,σ2,σ3)σ1σ2σ30

Sobald wir die SVD haben, definieren Sie wobei das Vorzeichen im mittleren Faktor so gewählt wird, dass . Normalerweise hat eine reale Anwendung , und daher wäre das gewählte Vorzeichen positiv. Wenn nicht, bedeutet dies, dass die beste orthogonale (abstandserhaltende) Anpassung an die neuen Punkte eine Reflexion beinhaltet, und es wird vorgeschlagen, die Daten auf Fehler zu überprüfen.R=Udiag(1,1,±1)VTdet(R)=1det(UVT)=1

Schließlich definieren wir die Übersetzung . Erledigt!d=y¯Rx¯

Die Variante der orthogonalen Procrustes-Probleme, bei denen nur Rotationen zulässig sind, ist auch Gegenstand eines anderen Wikipedia-Artikels zum Kabsch-Algorithmus . Die Notation in den Wikipedia-Artikeln unterscheidet sich von unserer durch die Multiplikation mit rechts und nicht (wie hier) links.R

Hardmath
quelle
1
Fantastisch! Vielen Dank, dass Sie sich die Zeit genommen haben, das aufzuschreiben. Sehr nützlich in der Tat.
DaleyPaley
Gibt es eine Standardmethode zur Lösung der "gewichteten" Version dieses Problems, bei der die Geräusche an den verschiedenen Punkten unterschiedliche Abweichungen aufweisen?
Nibot
@nibot: Schauen Sie sich die Dissertation von T. Vikland (2006) an , in der einige Expositionen und veröffentlichte Artikel zum Problem der gewichteten orthogonalen Procrustes (WOPP) vorgestellt werden: "Die Lösung eines WOPP kann nicht so einfach berechnet werden wie für ein OPP kann ein WOPP mehrere lokale Minima haben. "
Hardmath
Es gibt eine weitere ähnliche und nützliche Beschreibung des SVD-Ansatzes von der ETHZ: igl.ethz.ch/projects/ARAP/svd_rot.pdf
Linuxios