Drehmatrix herausfinden

[DocEW]

Hallo,

irgendwie raff ich's gerade nicht:

Ich habe ein paar Punkte und ein paar dazu korrespondierende Punkte im R³. Diese sind durch eine Rotation und eine Translation aus den ursprünglichen Punkten hervorgegangen. Wie bekomme ich jetzt die Rotationsmatrix und den Translationsvektor heraus?

Ich kann natürlich für jede Punktepaarung eine Gleichung aufstellen:

x' = A*x + t

allerdings sieht die Rotationsmatrix ja so (http://de.wikipedia.org/wiki/Rotationsmatrix#Drehmatrizen_des_Raumes_R.C2.B3) aus, d.h. ich muß irgendwie nach alpha und t lösen..?

Argh! Bitte um Tipps... :-/

DocEW

[Gast]

Wenn du A hast und du weißt, dass es eine Drehmatrix ist, kannst du dir ja einfach einen Punkt und sein Bild nehmen und den Winkel berechnen

[Gast]

bzw. 2 Punkte im R^3

[Gast]

Allgemein?
-t
*A^(-1)
In Komponenten auflösen und Gleichungssystem lösen.
Glücklich sein ;D

[DocEW]

Also A hab ich ja nicht. A hängt ja gerade vom Winkel ab.

Ich kann auch nicht einfach den Winkel zwischen Punkt und Bild messen (vom Ursprung aus). Vielleicht nochmal zur Verdeutlichung: Die Abbildung (Rotation+Translation) muß für alle Punktepaare gelten. Man kann sich alternativ vorstellen, daß man zwei Positionen irgendeines Gegenstandes im R³ hat und wissen will, wie man von der einen zur anderen kommt.

Oder hab ich dich nur nicht richtig verstanden? =)

[Gast]

oder: Tr(A) = 3 cos alpha + ||v||(1 - cos alpha) = 1 + 2 cos alpha

[Gast]

Also A hab ich ja nicht. Ach so. Dann setzt du einfach ein LGS an

[DocEW]

Ach so. Dann setzt du einfach ein LGS an
Ist aber nicht linear, wenn

A=[ cos(alpha)+v1^2*(1-cos(alpha)), v1*v2*(1-cos(alpha))-v3*sin(alpha), v1*v3*(1-cos(alpha))+v2*sin(alpha)]
[ v1*v2*(1-cos(alpha))+v3*sin(alpha), cos(alpha)+v2^2*(1-cos(alpha)), v2*v3*(1-cos(alpha))-v1*sin(alpha)]
[ v1*v3*(1-cos(alpha))-v2*sin(alpha), v2*v3*(1-cos(alpha))+v1*sin(alpha), cos(alpha)+v3^2*(1-cos(alpha))]

[DocEW]

oder: Tr(A) = 3 cos alpha + ||v||(1 - cos alpha) = 1 + 2 cos alpha
Das raffe ich leider nicht - ich habe A nicht, ich habe alpha nicht... was kann ich mit der Gleichung berechnen?

[Gast]

Ist aber nicht linear, wenn

A=[ cos(alpha)+v1^2*(1-cos(alpha)), v1*v2*(1-cos(alpha))-v3*sin(alpha), v1*v3*(1-cos(alpha))+v2*sin(alpha)]
[ v1*v2*(1-cos(alpha))+v3*sin(alpha), cos(alpha)+v2^2*(1-cos(alpha)), v2*v3*(1-cos(alpha))-v1*sin(alpha)]
[ v1*v3*(1-cos(alpha))-v2*sin(alpha), v2*v3*(1-cos(alpha))+v1*sin(alpha), cos(alpha)+v3^2*(1-cos(alpha))]für A. Dann berechnest du mit der Formel alpha

[ScottManDeath]

Singular Value Decomposition (SVD) bringt Dir einen optimalen Fit der die Punkte von A nach B transformiert. D.h. zuerst löst Du das (möglicherweise überbestimmte) LGS mit SVD und bekommst eine Matrix. Danach kannst Du diese mit einer weiteren SVD in eine Rotation und Skalierung zerlegen. Für die Translation sollte die Differenz der Durchschnitte der Punktegruppen ausreichend sein. Diesen Vektor ziehst Du dann von Deinen Zielpunkten ab, so dass die Matrix die Du suchst nur 3x3 ist.

Wenn Du dann noch Achse + Winkel suchst, kannst Du Dir aus der 3x3 Matrix ein Quaternion basteln ;)

[DocEW]

Erstmal vielen Dank für eure Mühe.
Tut mir ja echt leid, wenn ich mich blöd anstelle...aber auch nach ein bißchen googeln und durchschauen einiger Sachen raff ich's net.

Aaaalso:

Erstmal: Welches lineare GS soll ich lösen? Die Variablen in der Rotationsmatrix sind also drei Winkel oder alternativ ein Winkel und ein Vektor, um den gedreht wird (geht auch als Parametrisierung, oder..?). Die Matrix ist also recht gut bestückt mit nichtlinearen cosinus und sinus-Zeugs.

SVD. Ok, damit bekomme ich eine Matrix M in die Form R1*D*R2. Wie zerlege ich damit etwas in Translation und Rotation?

Was ist die "Differenz der Durchschnitte der Punktegruppen"? Die Punktegruppen sind die Ursprungspunkte und die Bilder nehme ich an? Dann gibt es keinen Schnitt. Oder meinst du sowas wie einen Centroid? Ist das nicht zu grob, davon einfach die Entfernung zu nehmen? Durch eine Rotation verschiebt sich doch so ein "Schwerpunkt".

*seufz*
Wenn es irgendwie einfacher (für euch) ist, könnt ihr mir auch gerne einfach vorführen, was an diesem Beispiel hier zu tun ist:

P = { (1, 1, 1), (2, 2, 1), (4, 1, 1) } ursprüngliche Punkte
P' = { (2, 1, 2), (3, 0, 2), (2, -2, 2) } Bilder der Punkte

Das sollte recht fein aufgehen, habe ich mir gerade ausgedacht. ;)
Was ist also dort die Rotationsmatrix und was ist der Translationsvektor?

Danke nochmals für die Hilfe,

DocEW

[Xmas]

Im R2 würdest du folgendes tun:
Du nimmst zwei Punkte p und q sowie ihre Bilder p' und q'. Damit berechnest du den Winkel zwischen den Vektoren (p-q) und (p'-q'). Dieser Winkel ist der Rotationswinkel. Dann rotierst du p um diesen Winkel und berechnest die Differenz des resultierenden Punktes zu p'. Die Differenz ist der Translationsvektor.

Im R3 funktioniert ähnliches, nur nimmst du diesmal drei Punkte welche eine Ebene definieren und bestimmst damit Normalen:
n = (p - q) x (p - r)
n' = (p' - q') x (p' - r')

n x n' ist die Rotationsachse, acos(|n| · |n'|) der Rotationswinkel (wobei man da noch je nach Orientierung das Vorzeichen ändern muss). Dann rotierst du wieder p und ermittelst aus der Differenz des resultierenden Punktes zu p' den Translationsvektor.

[DocEW]

Ah, super, danke! Eine Frage noch: Bei acos(|n| · |n'|) ist ja das |n| · |n'| nicht unbedingt kleiner 1... wie interpretiere ich das dann? Kommt ja was komplexes raus. Nehme ich nur den Realteil?

Achja, und bei n x n' muß man den Fall abfangen, daß n=n' ist, oder?

[Xmas]

Sorry, aber das was ich oben geschrieben habe ist Stuss. Im R3 ist es ja so dass es eine ganze Ebene von Rotationsachsen gibt, um einen Punkt a auf einen Punkt b zu rotieren. Da Translation nichts an der Orientierung der Punkte zueinander ändert, sollte man die Rotation mit der Orientierung der Punkte zueinander berechnen können.

Nehmen wir drei Punkte p, q, r und ihre Bilder p', q', r'. Dazu dann die Richtungsvektoren
a = p - q, a' = p' - q'
b = p - r, b' = p' - r'

Nun brauchen wir die Rotation die sowohl a in a' als auch b in b' abbildet. Um a in a' abzubilden gibt es eine Ebene an möglichen Rotationsachsen mit dem Normalenvektor (a - a'). Analog für b und b'. Da es ja nur eine Rotation ist, muss die Rotationsachse in beiden Ebenen liegen, also der Schnittgerade der beiden Ebenen entsprechen. Folglich also ist (a - a') x (b - b') die Rotationsachse c (wenn hier der Nullvektor herauskommt müssen andere Punkte gewählt werden).
Um den Rotationswinkel zu bestimmen, projizieren wir a und a' auf die Ursprungsebene mit Normale c und bestimmen den von den projizierten Vektoren aufgespannten Winkel.

Mit Rotationswinkel und Rotationsachse ist es dann einfach, p zu rotieren und aus der Differenz des Ergebnisses zu p' den Translationsvektor zu bestimmen.

[DocEW]

Cool, hat funktioniert, vielen vielen Dank dafür!
Jetzt muß ich mal schauen, ob das Verfahren auch halbwegs robust ist (d.h. Fehlerquadrate minimiert o.ä.), oder ob ich doch noch ein Optimierungsproblem lösen muß. ;)
In meinem Mini-Beispiel oben war übrigens ein Fehler, hab ich korrigiert.