absolute-orientation-problem mit SVD (Arun)

24/04/2008 - 12:38 von Tobias Foehst | Report spam
Hallo

Ich schreibe gerade meine Diplomarbeit und habe ein ziemliches
Verstaendnisproblem mit einem Verfahren, das ich einsetze, um
Punktwolken registrieren. Also ich suche die Transformation, die
zwei identische Punktwolken aufeinander abbilden wuerde und bei
fehlerhaften Daten wenigstens eine Annaeherung liefert.
Das ist jetzt nicht so neu und ich habe auch mehrere Verfahren, die
funktionieren, aber bei einem fehlt mir jegliche Idee, wo die
einzelnen ueberhaupt herkommen.

Kurz: Es geht um das Least-Squares-Verfahren von Arun (1987), in dem
eine Singulaerwertzerlegung verwendet wird.

Fuer alle das nicht kennen:

Soweit ist mir alles klar:
Die beiden Punktwolken m und d sind gleich gross und so sortiert,
dass Punkte mit dem gleichen Index letzlich aufeinander abgebildet
werden (korrespondieren).
Wenn man die richtige Rotation gefunden hat und die Wolken
uebereinander schiebt, sind die Schwerpunkte identisch. Darum
berechnet man die Schwerpunkte und zieht sie von den Punktkoordinaten
ab. Das kommt einer Verschiebung der Schwerpunkte in den Ursprung
gleich.

Jetzt will man 1/n $\sum_{i=1}^n \| d_i - Rm_i \|^2, also die
mittlere quadratische Abweichung minimieren, multiplizert das aus und
kommt darauf, dass man \sum_{i=0}^n d'_i R m_i maximieren muss.


Jetzt geht das Problem los:
Ich habe gelesen, um das zu erreichen muss man eine Kovarianzmatrix
berechnen. Die Formel dafuer ist als Summe ueber die ausseren Produkte
korrespondierender Punkte angegeben: H = 1/n \sum_{i=0}^n d_i m_i'

Wie kann das eine Kovarianzmatrix sein? Die ist doch nie im Leben
symmetrisch. Meine Punkte sind 2D und ich bekomme auch brav fuer
jeden Summanden eine 2x2-Matrix raus. Nur halt nicht symmetrisch.

Jetzt geht es weiter: Man soll die Spur von RH maximieren. Warum das?
Welchen Sinn haette das und stimmt das ueberhaupt? Meine
Implementation funktioniert eigentlich, aber die Spur von RH ist
kleiner als die von H.

Um die optimale Rotationsmatrix R zu erhalten, soll man eine SVD
machen: H = USV', wobei S eine Diagonalmatrix mit den Singulaerwerten
auf der Hauptdiagonalen ist. R erhaelt man danach mit R = UV', wenn
alles gut ging. Wenn man Pecht hat, ist R jetzt eine Reflexionsmatrix,
aber das kann man ja anhand der Determinante erkennen und beheben.
Und auch hier stellt sich mir die Frage: Warum das? Wie haengt das
zusammen? Aber das kann ich dann vielleicht selbst beantworten, wenn
ich weiss, was das mit der Matrix H soll. Die ist mir suspekt.

Das Verfahren funktioniert so super. Ich habe nur keine Idee, wie ich
das herleiten soll.

Tobias
 

Lesen sie die antworten

#1 Tobias Foehst
24/04/2008 - 12:41 | Warnen spam
Ach ja: ich habe das auch schon in einem Matheforum gefragt. Da mit
einem kleinen Beispiel, falls das hilft:

http://matheplanet.com/matheplanet/....php?topic1239

Tobias

Ähnliche fragen