Projekt: Estimation from Uncertain Data in Geometric Algebra
Forscher: Gebken C. , Perwass C. , Sommer G.
Im Mittelpunkt dieses Projektes steht das Schätzen von geometrischen Entitäten und geometrischen Operatoren aus Beobachtungsdaten die mit (Meß-) Unsicherheiten behaftet sind. Geschätzt werden die das Element definierenden Parameter, weshalb auch von Parameterschätzung gesprochen wird. Die zugrunde liegenden Daten sind fast immer 2D- oder 3D-Punkte, dessen Unsicherheiten über Kovarianzmatrizen repräsentiert werden. Deren Bestimmung leitet sich meist aus der Kenntnis des datenerzeugenden Meßprozesses her. Für eine hohe Präzision wird die Anzahl der Beobachtungen üblicherweise so gewählt, daß das Schätzproblem überbestimmt ist, die Datenmenge also die Menge der zu bestimmenden Parameter weit übersteigt. Letztere müssen mit der Gesamtheit der Beobachtungen möglichst gut in Übereinstimmung gebracht werden. Hierfür wird die Methode der Ausgleichsrechnung angewandt, die bei dem Bestimmen der Parameter die Konfidenzen (reziproke Unsicherheiten) berücksichtigt, um 'gute' Daten stärker zu gewichteten als unsichere. Beobachtungen und Parameter hängen über ein Modell zusammen, das den zugrunde liegenden physikalischen Meßprozess wiederspiegelt. Dessen mathematische Formalisierung wird genutzt, um die jeweiligen Abweichungen zwischen Datum und Schätzung, also der Parametermenge, zu berechnen. In der Ausgleichsrechnung wird die Summe der Quadrate der gewichteten Abweichungen - in Abhängigkeit von den Parametern - minimiert.
Geometrische Algebra
Geometrische Algebra ist eine geometrische Interpretation der Clifford Algebra und bietet einen mächtigen Zugang zu geometrische Berechnungen. Im Projekt wird die 32-dimensionale Algebra des 5-dimensionalen konformen Raumes verwendet. Punkte des Euklidischen 3D-Raumes müssen in den konformen Raum eingebettet werden. Die Elemente der Algebra können als Vektoren aus R^32 angesehen bzw. repräsentiert werden - insbesondere bei numerischen Berechnungen ? jedoch darf die individuell unterschiedliche Bedeutung der Vektoreinträge nicht außer Acht gelassen werden. Typische in Frage kommende Elemente sind Entitäten wie Punkte, Kugeln, Kreise, Linien und Ebenen. Operatoren wie für Spiegelungen, Inversionen, Translationen oder Drehungen werden durch die Entitäten selbst repräsentiert und resultieren aus deren Anwendung auf andere Entitäten über das geometrische Produkt, der Algebra-Multiplikation. Eine Anwendung einer Kugel auf eine Linie erfolgt beispielsweise durch Bildung des Spinorproduktes ? dabei wird die Kugel S von links und rechts an die Linie L ranmultipliziert ? und resultiert in einer Inversion der Linie an der Kugel (dies entspricht der Inversion aller die Linie bildenden Punkte und ergibt die Entität Kreis K = S*L*S).
Die betrachteten Elemente der Algebra definieren sich über Produktnullräume; Ist etwa das Produkt von Punkt und Linie Null (bzgl. bestimmter Stellen im Ergebnisvektor), dann liegt der Punkt auf der Linie und die Linie ist definiert durch alle so mit ihr inzidierenden Punkte.
Besonderer Bedeutung kommt der Bilinearität des geometrischen Produkts als Abbildung R^32 x R^32 nach R^32 zu. Es bedeutet, daß das Produkt linear in beiden Operanden ist und folglich jeder Eintrag des Ergebnisvektors als quadratische Form geschrieben werden kann. Die geometrische Produktoperation ist damit durch ein 32-Tupel von 32x32 Matrizen vollständig charakterisiert. Solche 32x32x32 Matrizen sollen hier (3-wertige) Tensoren genannt werden. Wichtig ist, daß komplexe Algebraausdrücke mit mehreren Produkten äquivalent über eine Konkatenation der entsprechenden Tensoren geschrieben werden können, und letztere dann zu (höherwertigen) Tensoren kontraktiert werden können. Die Vektoren der Entitäten sind prinzipiell dünn und nur an bestimmten Stellen besetzt, so daß sich die Tensoren stets zu wesentlich kleineren Gebilden als die der Größe 32x32x32 reduzieren. Da bei einem Spinorprodukt zwei Multiplikationen stattfinden ist das Ergebnis quadratisch von der Operator-Entität abhängig.
Geometrische Algebra liefert die den geometrischen Berechnungen zugrunde liegenden Gleichungen, die typischerweise linear oder quadratisch in den betrachteten Parametern sind und ohne trigonometrische Funktionen auskommen. Die erhaltenen Gleichungen lassen sich schließlich in Matrixnotation darstellen, so daß sich gängige Standardmethoden in gewohnter Weise anwenden lassen.
Stochastisches Schätzen
Der realisierte Algorithmus zur Parameterschätzung arbeitet mit den Bedingungsgleichungen der geometrischen Algebra. Das verwendete Schätzverfahren nimmt allerdings an, daß Beobachtungen und Parameter ein spezielles Modell erfüllen müssen ? das lineare Gauß-Helmert Modell. Dies ist, wie für der Mehrzahl aller Schätzprobleme, nicht gegeben, so daß eine Linearisierung der (hier höchstens quadratischen) Bedingungsgleichungen durchgeführt werden muß. Aufgrund der nur lokalen Gültigkeit einer Linearisierung muß die Lösung iterativ berechnet werden. Es erfordert weiterhin eine grobe initiale Schätzung, die zuvor über andere Verfahren ermittelt werden muß. Als nennenswertes Nebenprodukt ergibt sich die Unsicherheit des geschätzten Elements in Form einer Kovarianzmatrix über die Parameter.
|
Dies ist die erste Anwendung der Parameterschätzung: Schätzung eines Kreises in 3D aus einer Menge von unsicheren Punkten.
Oben: Der Schlauch um den perspektivisch dargestellen Kreis spiegelt dessen Unsicherheit wieder, die sich aus den Unsicherheiten und der räumlichen Verteilung der beobachteten (roten) Punkte ergibt. Mitte: Verschiedene Ansichten einer anderen Kreisschätzung. Unten: Linien als spezielle Kreise mit unendlichem Radius können in der gleichen Art und Weise geschätzt werden. |
Ziel der zweiten Anwendung war es eine starre 3D-Transformation (Pose) zu finden, die eine Punktwolke fixer Punkte möglichst gut auf eine Punktwolke unsicherer Punkte bewegt. Die fixen Punkte gelten dabei als Modell, während die unsicheren Punkte die Beobachtungen repräsentieren. Es wird angenommen, daß die Anzahl der Punkte in den Wolken übereinstimmt und daß die jeweiligen Korrespondenzen bekannt sind, d.h. welcher Punkt in Wolke A gehört zu welchem Punkt in Wolke B.
Das Prinzip ist unten dargestellt, wobei die entsprechende Transformation im Bild mit einem 'M' gekennzeichnet ist. Sie bewegt, d.h. rotiert und verschiebt, den hinteren Würfel auf den vorderen. Die Translation ist durch den geraden Pfeil veranschaulicht an dessem Fußende das violette Kreisscheibensegment die zugehörige Rotation (Winkel) andeutet. In diesem Beispiel spannen die Punkte einen Würfel auf. Wie bei der Kreisschätzung wurde auch hier eine Unsicherheit für die Transformation M berechnet, sie ist jedoch schwer zu visualisieren.
Im Rahmen der perspektivischen Pose-Schätzung ist die starre 3D-Transformation gesucht, die ein 3D-Punktmodell (eines Objekts) so bewegt, daß es mit 2D-Bildpunkten im Einklang steht, daß also die bewegten 3D-Punkte unter perspektivischer Projektion (Annahme einer Lochbildkamera mit bekannter Geometrie) möglichst gut auf die 2D-Bildpunkte abgebildet werden. Die algebraischen Bedingungsgleichungen der Schätzung wurden hierzu jedoch so formuliert, daß die Abstände der durch M bewegten Punkte von den korrespondierenden Projektionsstrahlen der Bildpunkte minimal sein sollen. Das Prinzip ist in der unteren Grafik gezeigt, wo das Dreiecksmodell in die Projektionsstrahlen 'gefittet' wird. Die Bildpunkte liegen an den Schnittpunkten mit der Bildebene.
Neu ist, daß die Unsicherheiten der Bildpunkte (Beobachtungen) mittels Standardfehlerfortpflanzung auf die Projektionsstrahlen übertragen werden, die hernach als neue Beobachtungen dienen. Die Fehlerfortpflanzung wird in geometrischer Algebra durchgeführt, da dort die Bildung der Projektionsstrahlen leicht bewerkstelligt werden kann und weil aufgrund der Bilinearität des geometrischen Produkts keine Terme zweiter Ordung entstehen und die Fehlerfortpflanzung dadurch exakt ist.
Eine Weiterführung der Pose-Schätzung liegt in der Verwendung panoramischer Bilder, wie sie katadioptrische Kameraysteme (Bild unten links) verwenden. Dabei erhält eine herkömmliche CCD-Kamera einen Spiegelaufsatz, der alle Lichtstrahlen, die den Brennpunkt des Spiegels treffen würden, reflektiert und in ein Bündel achsparalleler Strahlen verwandelt. Es ergeben sich omnidirektionale Bilder (Bild unten rechts, Eingangshalle).
Im Fall eines parabolischen Spiegels läßt sich die Abbildungsgeometrie eines katadiotrischen Kamerasystems über zwei Kugeln modellieren: Lichtstrahlen, die den Brennpunkt des Spiegels passieren würden (also einen Bildpunkt erzeugen würden), werden mit einer konzentrischen Projektionskugel geschnitten. Eine Inversion der Schnittpunkte an einer größeren exzentrischen Kugel liefert dann die Bildpunkte. Diese Operationen eignen sich, in geometrischer Algebra ausgeführt zu werden. Der Unterschied zum Lochkamera-Fall besteht hauptsächlich in der Inversion. Die Vorgehensweise ist identisch: Die unsicheren 2D-Bildpunkte werden per Inversion 'zurück' auf die Projektionskugel gebracht - dabei erhalten sie der Abbildungsgeometrie entsprechende 3D-Unsicherheiten. Anschließend werden die Projektionsstrahlen gebildet - wieder unter Beachtung der Fehlerfortpflanzung - die dann als neue Beobachtungen fungieren. Die Methodik der Pose-Schätzung mit Projektionskugel 'S' zeigt folgende Grafik (Inversionskugel nicht eingezeichnet, 'F' bezeichnet den Brennpunkt des parabolischen Spiegels, die Bildebene ist durch das Schachbrettmuster angedeutet):
Eine aktuelle Erweiterung besteht darin, nicht mit Modellpunkten und Projektionsstrahlen, sondern mit Modelllinien und Projektionsebenen zu arbeiten; Inzidiert eine durch M bewegte Modelllinie mit ihrer korrespondierenden Projektionsebenen, dann sind die Bilder unter Projektion identisch. Dieses Verfahren ist noch stabiler als das Punkt-Linie Verfahren, da viele Bildpunkte für eine Linie sprechen, sich Linien gut aus Bildern extrahieren lassen (Achtung - Weltlinien werden in katadioptrischen Bildern zu Kreissegmenten) und weil Einsatzorte solcher Kameraysteme de facto aus Linien bestehen.
Nachstehend finden sich Skriptdateien für die 'Schätzung geometrischer Entitäten und Operatoren aus unsicheren Daten in der geometrischen Algebra des konformen Raumes'. Um mit den Skripten zu arbeiten wird die Software CLUCalc benötigt. Diese kann unter http://www.clucalc.info/ heruntergeladen werden. Zur vollen Nutzung von CLUCalc braucht man außerdem LaTeX (http://www.miktex.org/).
Beispielskripte Fit circle und Motor estimation.