Perspektive-und-Punkt

Das Perspective -n -Point- Problem (PnP) ^{[ 1 ]} befasst sich mit der Schätzung der Kamerapose anhand von n 3D-Punkten in der Welt und deren entsprechenden 2D-Projektionen in einem Bild. Die Kamerapose besitzt sechs Freiheitsgrade (DOF): Rotation (Rollen, Nicken und Gieren) und Translation der Kamera relativ zu einem Ursprungspunkt in der Welt. Dieses Problem stammt aus der Kamerakalibrierung und findet vielfältige Anwendungen in der Computer Vision und anderen Bereichen wie 3D-Tracking , Robotik und Augmented Reality . ^{[ 2 ]} Für n = 3 existiert eine gängige Lösung, P3P genannt, und für den allgemeinen Fall n ≥ 3 sind zahlreiche Lösungen verfügbar . Eine Lösung für n = 2 existiert, wenn die Orientierungen der Merkmale an den beiden Punkten bekannt sind. ^{[ 3 ]} Implementierungen dieser Lösungen sind als Open-Source-Software verfügbar.

Gegeben seien n 3D-Punkte in einem Weltkoordinatensystem, deren zugehörige 2D-Bildprojektionen sowie die kalibrierten intrinsischen Kameraparameter. Bestimmen Sie die 6- DOF -Pose der Kamera in Form ihrer Rotation und Translation relativ zur Welt. Dies folgt dem Perspektivprojektionsmodell für Kameras.

${\displaystyle s\,p_{c}=K\,[\,R\,|\,T\,]\,p_{w}}$Die

Dabei ist der homogene Weltpunkt , der entsprechende homogene Bildpunkt, die Matrix der intrinsischen Kameraparameter (wobei und die skalierten Brennweiten sind, der Schiefeparameter, der manchmal als 0 angenommen wird, und der Hauptpunkt), ein Skalierungsfaktor für den Bildpunkt und und die gewünschte 3D-Rotation bzw. 3D-Translation der Kamera (extrinsische Parameter), die berechnet werden. Dies führt zu folgender Gleichung für das Modell: ${\displaystyle \textstyle p_{w}={\begin{bmatrix}x&y&z&1\end{bmatrix}}^{T}}$${\displaystyle \textstyle p_{c}={\begin{bmatrix}u&v&1\end{bmatrix}}^{T}}$${\displaystyle \textstyle K}$${\displaystyle \textstyle f_{x}}$${\displaystyle f_{y}}$${\displaystyle \textstyle \gamma }$${\displaystyle \textstyle (u_{0},\,v_{0})}$${\displaystyle \textstyle s}$${\displaystyle \textstyle R}$${\displaystyle \textstyle T}$

${\displaystyle s{\begin{bmatrix}u\\v\\1\end{bmatrix}}={\begin{bmatrix}f_{x}&\gamma &u_{0}\\0&f_{y}&v_{0}\\0&0&1\end{bmatrix}}{\begin{bmatrix}r_{11}&r_{12}&r_{13}&t_{1}\\r_{21}&r_{22}&r_{23}&t_{2}\\r_{31}&r_{32}&r_{33}&t_{3}\\\end{bmatrix}}{\begin{bmatrix}x\\y\\z\\1\end{bmatrix}}}$Die

Es gibt einige grundlegende Aspekte des Problems, die allen Lösungen des P n P-Problems gemeinsam sind. Die meisten Lösungen gehen davon aus, dass die Kamera bereits kalibriert ist. Somit sind ihre intrinsischen Eigenschaften, wie Brennweite , Hauptbildpunkt, Schiefeparameter und weitere Parameter, bereits bekannt. Einige Methoden, wie UP n P ^{[ 4 ]} oder die direkte lineare Transformation (DLT) des Projektionsmodells, bilden Ausnahmen von dieser Annahme, da sie sowohl diese intrinsischen Parameter als auch die extrinsischen Parameter schätzen, welche die Kameraposition bestimmen, die das ursprüngliche P n P-Problem zu ermitteln sucht.

Bei jeder Lösung des PnP-Problems dürfen die gewählten Punktkorrespondenzen nicht kollinear sein. Darüber hinaus kann PnP mehrere Lösungen besitzen, und die Auswahl einer bestimmten Lösung erfordert eine Nachbearbeitung der Lösungsmenge . RANSAC wird häufig in Kombination mit PnP-Verfahren eingesetzt, um die Lösung robust gegenüber Ausreißern in der Menge der Punktkorrespondenzen zu machen. P3P-Verfahren setzen rauschfreie Daten voraus, die meisten PnP-Verfahren hingegen Gaußsches Rauschen in der Menge der Ausreißer.

Im folgenden Abschnitt werden zwei gängige Methoden zur Lösung des P n P-Problems beschrieben, die auch in Open-Source-Software leicht verfügbar sind, sowie die Verwendung von RANSAC zur Behandlung von Ausreißern im Datensatz .

Für n = 3 liegt das P n P-Problem in seiner minimalen Form als P3P vor und kann mit drei Punktkorrespondenzen gelöst werden. Allerdings liefert P3P mit nur drei Punktkorrespondenzen bis zu vier reelle, geometrisch zulässige Lösungen. Bei geringem Rauschen kann eine vierte Korrespondenz verwendet werden, um Mehrdeutigkeiten zu beseitigen. Die Problemstellung ist wie folgt.

Sei P der Projektionspunkt der Kamera, A , B und C seien 3D-Weltpunkte mit zugehörigen Bildpunkten u , v und w . Sei X = |PA| , Y = |PB| , Z = |PC| , , , , , , , , , , . Dadurch entstehen die Dreiecke PBC , PAC und PAB , aus denen wir ein hinreichendes Gleichungssystem für P3P erhalten: ${\displaystyle \alpha =\angle BPC}$${\displaystyle \beta =\angle APC}$${\displaystyle \gamma =\angle APB}$${\displaystyle p=2\cos \alpha }$${\displaystyle q=2\cos \beta }$${\displaystyle r=2\cos \gamma }$${\displaystyle a'=|AB|}$${\displaystyle b'=|BC|}$${\displaystyle c'=|AC|}$

${\displaystyle {\begin{cases}Y^{2}+Z^{2}-YZp-b'^{2}&=0\\Z^{2}+X^{2}-XZq-c'^{2}&=0\\X^{2}+Y^{2}-XYr-a'^{2}&=0\\\end{cases}}}$Die

Die Lösung des P3P-Systems liefert bis zu vier geometrisch zulässige reelle Lösungen für R und T. Die älteste veröffentlichte Lösung stammt aus dem Jahr 1841. ^{[ 5 ]} Ein aktueller Algorithmus zur Lösung des Problems sowie eine Lösungsklassifizierung wurden 2003 in der IEEE Transactions on Pattern Analysis and Machine Intelligence- Veröffentlichung von Gao et al. vorgestellt. ^{[ 6 ]} Eine Open-Source-Implementierung von Gaos P3P-Solver ist im Modul calib3d von OpenCV in der Funktion solvePnP verfügbar . ^{[ 7 ]} Seitdem wurden mehrere schnellere und genauere Versionen veröffentlicht, darunter Lambda Twist P3P ^{[ 8 ]} , das 2018 mit einer 50-fach höheren Geschwindigkeit und einer 400-fach geringeren Anzahl numerischer Fehler Bestleistungen erzielte. Lambda Twist ist als Open Source in OpenMVG und unter https://github.com/midjji/pnp verfügbar .

Efficient P n P (EP n P) ist eine Methode, die von Lepetit et al. in ihrer 2008 im International Journal of Computer Vision veröffentlichten Arbeit ^{[ 9 ]} entwickelt wurde und das allgemeine Problem von P n P für n ≥ 4 löst . Diese Methode basiert auf der Annahme, dass jeder der n Punkte (Referenzpunkte) als gewichtete Summe von vier virtuellen Kontrollpunkten dargestellt werden kann. Die Koordinaten dieser Kontrollpunkte sind somit die Unbekannten des Problems. Ausgehend von diesen Kontrollpunkten wird die endgültige Kameraposition berechnet.

Zur Veranschaulichung des Prozesses ist zunächst festzuhalten, dass jeder der n Referenzpunkte im Weltkoordinatensystem und die zugehörigen Bildpunkte gewichtete Summen der vier Kontrollpunkte sind. Die Gewichte werden, wie unten dargestellt, pro Referenzpunkt normalisiert. Alle Punkte werden in homogener Form ausgedrückt. ${\displaystyle p_{i}^{w}}$${\displaystyle p_{i}^{c}}$${\displaystyle c_{j}^{w}}$${\displaystyle c_{j}^{c}}$

${\displaystyle p_{i}^{w}=\sum _{j=1}^{4}{\alpha _{ij}c_{j}^{w}}}$

${\displaystyle p_{i}^{c}=\sum _{j=1}^{4}{\alpha _{ij}c_{j}^{c}}}$

${\displaystyle \sum _{j=1}^{4}{\alpha _{ij}}=1}$

Daraus ergibt sich die Ableitung der Bildreferenzpunkte.

${\displaystyle s_{i}\,p_{i}^{img}=K\sum _{j=1}^{4}{\alpha _{ij}c_{j}^{c}}}$Die

Wo befinden sich die Bildreferenzpunkte mit den Pixelkoordinaten ? Der homogene Bildkontrollpunkt hat die Form . Durch Umstellen der Bildreferenzpunktgleichung ergeben sich die folgenden zwei linearen Gleichungen für jeden Referenzpunkt: ${\displaystyle p_{i}^{img}}$${\displaystyle {\begin{bmatrix}u_{i}&v_{i}&1\end{bmatrix}}^{T}}$${\displaystyle \textstyle c_{j}^{c}={\begin{bmatrix}x_{j}^{c}&y_{j}^{c}&z_{j}^{c}\end{bmatrix}}^{T}}$

${\displaystyle \sum _{j=1}^{4}{\alpha _{ij}f_{x}x_{j}^{c}+\alpha _{ij}(u_{0}-u_{i})z_{j}^{c}}=0}$

${\displaystyle \sum _{j=1}^{4}{\alpha _{ij}f_{y}y_{j}^{c}+\alpha _{ij}(v_{0}-v_{i})z_{j}^{c}}=0}$Die

Mithilfe dieser beiden Gleichungen für jeden der n Referenzpunkte lässt sich das System bilden, wobei . Die Lösung für die Kontrollpunkte existiert im Nullraum von M und wird wie folgt ausgedrückt: ${\displaystyle \textstyle Mx=0}$${\displaystyle \textstyle x={\begin{bmatrix}c_{1}^{c^{T}}&c_{2}^{c^{T}}&c_{3}^{c^{T}}&c_{4}^{c^{T}}\end{bmatrix}}^{T}}$

${\displaystyle x=\sum _{i=1}^{N}{\beta _{i}v_{i}}}$

Dabei ist die Anzahl der Nullsingulärwerte in und jeder ist der zugehörige rechte Singulärvektor von . kann zwischen 0 und 4 liegen. Nach der Berechnung der Anfangskoeffizienten wird der Gauss-Newton -Algorithmus zu deren Verfeinerung verwendet. Anschließend werden die R- und T- Matrizen berechnet, die den Reprojektionsfehler der Weltreferenzpunkte und ihrer entsprechenden Bildpunkte minimieren . ${\displaystyle N}$${\displaystyle M}$${\displaystyle v_{i}}$${\displaystyle M}$${\displaystyle N}$${\displaystyle \beta _{i}}$${\displaystyle p_{i}^{w}}$${\displaystyle p_{i}^{c}}$

Diese Lösung ist komplex und funktioniert im allgemeinen Fall von P n P sowohl für planare als auch für nicht-planare Kontrollpunkte. Open-Source-Software-Implementierungen dieser Methode finden sich im Modul „Camera Calibration and 3D Reconstruction“ von OpenCV in der Funktion „ solvePnP “ ^{[ 7 ]} sowie im von Lepetit et al. auf ihrer Website CVLAB an der EPFL veröffentlichten Code ^{[ 10 ]} .${\displaystyle O(n)}$

Diese Methode ist nicht robust gegenüber Ausreißern und schneidet im Allgemeinen im Vergleich zu RANSAC P3P mit anschließender nichtlinearer Verfeinerung schlecht ab.

SQPnP wurde von Terzakis und Lourakis in einem Beitrag zur ECCV 2020 beschrieben. ^{[ 11 ]} Es handelt sich um einen nichtminimalen, nichtpolynomialen Löser, der P n P als nichtlineares quadratisches Programm formuliert. SQPnP identifiziert Bereiche im Parameterraum der 3D-Rotationen (d. h. der 8-Sphäre ), die eindeutige Minima enthalten, wobei garantiert wird, dass mindestens eines davon das globale Minimum ist. Jedes regionale Minimum wird mittels sequentieller quadratischer Programmierung berechnet, die mit den nächstgelegenen orthogonalen Approximationsmatrizen beginnt .

SQPnP bietet eine vergleichbare oder sogar höhere Genauigkeit als moderne Polynom-Löser, ist global optimal und rechentechnisch sehr effizient, da es praktisch linear mit der Anzahl der eingegebenen Punkte n skaliert. Eine optimierte C++-Implementierung ist auf GitHub verfügbar und wurde auch nach OpenCV portiert sowie in das Modul „Kamerakalibrierung und 3D-Rekonstruktion“ ( Funktion „SolvePnP “) integriert. ^{[ 12 ]}

P n P ist fehleranfällig, wenn Ausreißer in der Menge der Punktkorrespondenzen vorhanden sind. Daher kann RANSAC in Verbindung mit bestehenden Lösungen verwendet werden, um die endgültige Lösung für die Kamerapose robuster gegenüber Ausreißern zu machen. Eine Open-Source-Implementierung von P n P-Methoden mit RANSAC findet sich im Modul „Kamerakalibrierung und 3D-Rekonstruktion“ von OpenCV in der Funktion ` solvePnPRansac` . ^{[ 12 ]}

• Kameraresektion
• Konsens der Zufallsstichprobe
• Visuelle Odometrie
• Python OpenCV solvePnP

• OpenCV-Kamerakalibrierungs- und 3D-Rekonstruktionsmodul
• Das CVLAB der EPFL: EPnP