Untersuchung von PnP-Algorithmen für photogrammetrische Anwendungen

Dauer der Arbeit: 6 Monate
Abgabe: Februar 2015
Betreuer:Tobias Heuchel (Trimble Germany, Geospatial Division)
Prüfer: Prof. Dr.-Ing. Norbert Haala

In dieser Arbeit werden die PnP-Algorithmen, die die Pose der Kamera aus gegebenen Passpunkten schätzen, im Computer-Vision-Bereich untersucht. Statt der Poseschätzung spricht man in der Photogrammetrie häufig von der Bestimmung der äußeren Orientierung. Die Bildorientierung ist ein wichtiger Schritt im ganzen photogrammetrischen Auswerteprozess. Erst nach der Bildorientierung ist die photogrammetrische Punktbestimmung möglich.

In der Photogrammetrie gibt es schon Standardverfahren zur Festlegung der äußeren Orientierung. Im Falle eines einzelnen Bildes ist der räumliche Rückwärtsschnitt einzusetzen. Bei einem Bildverband bevorzugt man jedoch die Bündelblockausgleichung. Diese Standardverfahren sind relativ rechenaufwändig und benötigen immer Näherungswerte. Im Gegensatz dazu liefern PnP-Algorithmen direkte Lösungen ohne Näherungswerte und orientieren sich häufig an Echtzeitanwendungen. PnP ist die Abkürzung für „Perspective n Points“. Für n gegebene Passpunkte, die perspektiv auf der Bildebene abgebildet werden, ist die Pose (Rotation und Translation) der Kamera bezüglich des Objektkoordinatensystems zu schätzen. PnP-Algorithmen finden Anwendungen in vielen Bereichen: Robotik, Augmented Reality, Navigation, 3D-Rekonstruktion etc. Es lohnt sich, die neusten PnP-Algorithmen mit guter Genauigkeit und relativ wenig Rechenaufwand für die photogrammetrischen Anwendungen zu untersuchen.

Zuerst wird eine Reihe von PnP-Algorithmen kurz untersucht. Die verschiedenen Algorithmen werden klassifiziert (vgl. Abbildung 1). Anschließend werden zwei Algorithmen (REPPnP [1] und gP+s [2]) mit besonderen Eigenschaften ausgewählt. Die beiden Algorithmen werden ausführlich untersucht und in C++ implementiert. Danach testet man die implementierten Algorithmen mit synthetischen und realen Datensätzen.

Der erste implementierte Algorithmus REPPnP (Robust Effizient Prokrustes PnP) [1] ist eine robuste Lösung für die Poseschätzung eines einzelnen Bildes. Traditionell wird die Direct-Linear-Transformation (DLT) mit RANSAC eingesetzt. Im Vergleich dazu entwickelt REPPnP eine unterschiedliche Strategie. Basierend auf einem algebraischen Fehler werden die Ausreißer iterativ eliminiert. Diese Elimination ist viel schneller als das RANSAC, weil keine Reprojektionsfehler berechnet werden müssen. Mit bis zu 60% Ausreißern liefert dieser Algorithmus noch eine stabile Lösung. Des Weiteren hat REPPnP eine lineare Komplexität. Die Berechnung mit 1000 Punkten dauert nur unter 2 Millisekunden (intel CORE i7-4710HQ). Der Grund für die relativ wenige Rechenzeit liegt an der innovativen Idee, dass die gegebenen n Punkte als gewichtete Summe von vier virtuellen Passpunkten ausgedrückt werden. Aus den Koordinaten von den vier Passpunkten kann die Pose wiederherstellt werden. Dadurch reduziert sich der Rechenaufwand. Darüber hinaus ist die Genauigkeit von REPPnP besser als DLT+RANSAC. Der Algorithmus REPPnP kann z.B. in SLAM (simultaneous localization and mapping) bzw. für die Näherungswertbeschaffung in SfM (Structure from Motion) eingesetzt werden.

Der zweite implementierte Algorithmus gP+s (Generalized Pose and Scale) [2] bestimmt die Pose und den internen Maßstab einer generalisierten Kamera. Unter einer generalisierten Kamera versteht man ein Multikamerasystem oder mehrere Bilder, die zu unterschiedlichen Zeitpunkten von einer Kamera aufgenommen sind. Die relativen Orientierungen zwischen den gegebenen Bildern sind schon in einem Modellkoordinatensystem bekannt. Gesucht ist die Transformation von dem Modellsystem in Objektkoordinatensystem (vgl. Abbildung 2). Die erste Besonderheit des Algorithmus ist, dass ein Passpunkt nur in einzelnen Bildern beobachtet werden muss. Die Mehrfachmessung bzw. automatische Punktübertragung in verschiedenen Bildern sind nicht notwendig. Die weitere Besonderheit ist, dass diese Methode die Gröbnerbasis-Technik [3] einsetzt. Mit Hilfe der Gröbnerbasis können nicht-lineare Probleme ohne Näherungswerte direkt gelöst werden. Außer Multikamerasystem kann gP+s auch für die Registrierung bzw. die Georeferenzierung von Punktwolken eingesetzt werden.

[1] L. Ferraz, X. Binefa und F. Moreno-Noguer. Very Fast Solution to the PnP Problem with Algebraic Outlier Rejection. Conference in Computer Vision and Pattern Recognition (CVPR), 2014.

[2] J. Ventura, C. Arth, G. Reitmayr und D. Schmalstieg. A Minimal Solution to the Generalized Pose-and-Scale Problem. Conference in Computer Vision and Pattern Recognition (CVPR), 2014.

[3] Z. Kukelova, M. Bujnak, und T. Pajdla. Automatic Generator of Minimal Problem Solvers. European Conference on Computer Vision (ECCV), 2008.