Wie kann man das Viereck in ein Rechteck entfernen?

tl; dr: Mathematisches Problem in der projektiven Geometrie: Wie findet man eine 4x4-Kameramatrix, die eine Projektion wie unten dargestellt liefert, so dass sich die Punkte A, B, C, D irgendwo an den Rändern der Gerätebox befinden (z. B. OpenGL-normalisiertes Gerät) Koordinaten), und die Ecken der Einheitskiste fallen entlang der Strahlen EA, EB, EC, ED irgendwo vernünftig?

(Dies kann ein Sonderfall sein, möglicherweise einer Homographie, einer Perspektive und / oder einer Kollineation. Die Terminologie ist nicht bekannt.)

Ausarbeitung

Angesichts eines viereckigen ABCD im Ansichtsfenster gibt es meiner Meinung nach eine eindeutige (?) Transformation, die es wieder einem Rechteck zuordnet. Wie im Bild unten zu sehen: Das viereckige ABCD im Ansichtsfenster fungiert als physisches 'Fenster', und wenn wir es wieder einem Rechteck zuordnen, erscheint es verzerrt.

(Das Feld rechts steht für NDC, über das ich später spreche.)

Ziel ist es, schnell das Bild rechts zu erhalten. Wir könnten jeden Punkt strahlenverfolgen, um das Bild zu erhalten (was ich getan habe), aber ich würde OpenGL oder andere projektive Techniken bevorzugen, weil ich Dinge wie Überblendung, Grundelemente usw. nutzen wollte.

erster Versuch

Ich glaube, ich kann das Problem lösen, die 3x4- Kameramatrix zu finden , die die 3 + 1-dimensionale homogene Koordinate im 3-Raum (links) erzeugt und auf die 2 + 1-dimensionalen homogenen Koordinaten im 2-Raum (auf) projiziert das Recht). Man kann dies unter Verwendung der direkten linearen Transformation lösen , um ein Gleichungssystem Ba=0für die unbekannten Einträge ader Kameramatrix zu erhalten, und das System unter Verwendung der Singularwertzerlegung lösen(SVD). Ich würde die Vektoren EA, EB, EC, ED (wobei E Ihr physisches Auge oder die Kamera im Weltraum ist) als Punkte im Vorbild und (0,0), (1,0), (1) nehmen , 1), (0,1) oder so etwas wie die Punkte im Nachbild, und jedes Punktepaar würde ein paar lineare Gleichungen ergeben, die in die SVD eingesteckt werden können. Die resultierende Matrix würde EA -> (0,0) usw. abbilden (vorausgesetzt, es gibt genügend Freiheitsgrade, dh wenn die Lösung eindeutig ist, was ich nicht sicher bin, siehe Anmerkung [a].)

Aber zu meinem Leidwesen funktioniert OpenGL nicht so. OpenGL projiziert 3d nicht direkt auf 2d mit einer 3x4-Matrix. OpenGL erfordert "normalisierte Gerätekoordinaten" (NDC), die dreidimensionale Punkte sind. Nach dem Projizieren in NDC wird alles im Feld 'Einheit' von (-1, -1, -1,1) bis (1,1,1,1) gezeichnet. Alles außerhalb wird abgeschnitten (da es sich um homogene Koordinaten handelt: Jeder Punkt (x, y, z, w) wird nur dann auf dem Bildschirm angezeigt, wenn die ersten drei Koordinaten von (x / w, y / w, z / w) vorliegen , 1) befinden sich innerhalb der Einheitenbox von -1 bis 1).

Die Frage lautet also: Gibt es eine vernünftige Transformation, die einen seltsam aussehenden Quader in homogenen Koordinaten abbildet (insbesondere den links gezeichneten Quader mit ABCD (vordere Punkte) und A'B'C'D '(hintere Punkte, versteckt)? hinter vorderen Punkten)) zum Einheitswürfel, zB mit einer 4x4-Matrix? Wie macht man das?

was ich versucht habe

Ich habe etwas Stärkeres ausprobiert: Ich habe ABCD und A'B'C'D 'wie ein normales pyramidenförmiges Frustrum (z. B. gl frustrum) aussehen lassen (dh in diesem hypothetischen Aufbau würde auf dem Bild links nur ein schwarzes Rechteck überlagert sein es, kein Viereck), und verwendete dann die DLT / direkte lineare Transformation, um nach der angeblichen 4x4-Matrix zu lösen. Als ich es versuchte, schien es jedoch nicht genügend Freiheitsgrade zu geben ... Die resultierende 4x4-Matrix ordnete nicht jeden Eingabevektor jedem Ausgabevektor zu. Bei Verwendung von A, B, C, D, A '(5 Paare von Vektoren vor und nach der Transformation) erhalte ich / fast / das gewünschte Ergebnis ... die Vektoren werden korrekt abgebildet, aber zum Beispiel B', C ', D' werden (3,3,1,1) anstelle von (-1, -1,1,1) zugeordnet und von OpenGL abgeschnitten. Wenn ich versuche, einen sechsten Punkt hinzuzufügen (6 Punktepaare für die zu projizierende 4x4-Matrix), Meine Lösung scheint entartet zu sein (Nullen, Unendlichkeiten). Mit wie vielen Freiheitsgraden habe ich es hier zu tun, und ist dies mit einer 4x4-Matrix möglich, die die üblichen 4 Vektoren (3 + 1-dimensionale homogene Koordinatenvektoren) abbildet, die wir kennen und lieben?

zufällige kleine Gedanken

Ich vermute, dass es nicht möglich ist, einen beliebigen Quader mit einer 4x4-Matrix einem beliebigen Quader zuzuordnen, obwohl ich verwirrt bin, weil ich dachte, dass es möglich ist, ein konvexes Viereck mit einer Matrix wie in einem anderen konvexen Viereck in 2d abzubilden , sagen wir, Photoshop? ... kann / kann dies nicht mit einer projektiven Transformation durchgeführt werden? Und wie verallgemeinert es sich auf 3D? ...... Auch angesichts des fehlgeschlagenen Versuchs, eine 4x4-Matrix zu finden, sagt die lineare Algebra, wir sollten nicht erwarten, dass eine NxN-Matrix im besten Fall mehr als N linear unabhängige Punkte auf N Zielpunkte abbildet, aber ich finde das irgendwie homogen Koordinaten betrügen dies, weil es eine versteckte Kolinearität gibt? Ich denke nicht?

eine andere Lösung?

Ich denke, man könnte vielleicht auch die folgende hässliche Sache machen, bei der man eine typische Frustrum-Kamera-Projektionsmatrix verwendet, die 2D-Punkte findet, die den Ecken entsprechen, und dann eine 2D-perspektivische Verzerrungshomographie durchführt, aber wenn dies nach dem Rendern der Pixel geschehen sollte (zB Photoshop) Dann würde es Probleme mit der Auflösung geben ... Vielleicht könnte man hypothetisch eine Matrix finden, um diese Transformation auf der XY-Ebene im NDC-Raum durchzuführen, und sie dann mit der normalen frustrumbasierten Matrix zusammensetzen?

(Anmerkung [a]: Freiheitsgrad: ABCD kann weiter eingeschränkt werden, um das Nachbild einer projektiven Transformation zu sein, die auf ein Rechteck einwirkt, wenn dies erforderlich ist ... das heißt, das schwarze Rechteck auf der linken Seite könnte so sein das Ergebnis der Projektion eines Bilderrahmen-Clipart-Modells)

Ich denke, die Lösung sucht nach der projektiven Transformation, die die vier Punkte korrekt transformiert.

dh

wobei und$x' = [x_0, x_1, 1]$$y = [\frac{y'_0}{y'_2}, \frac{y'_1}{y'_2}]$

$P$ ist eine 3x3-Matrix mit 9 Einträgen. Aufgrund der endgültigen Normalisierung ist es bis zur Skalierung einzigartig und hinterlässt 8 Freiheitsgrade, die eindeutig durch die 8 durch die Korrespondenz gegebenen Gleichungen bestimmt werden (2 pro Punktpaar).

Jetzt können Sie Algebra verwenden, um dies zu tun, oder einfach OpenCVs verwenden getPerspectiveTransform:).

Schauen Sie sich auch die homnogenen Koordinaten auf Wikipedia an, um sich mit dem Konzept vertraut zu machen.

Ich habe meine eigene Frage durch die Implementierung der direkten linearen Transformation gelöst . Der Beispielabschnitt auf Wikipedia war mein Anwendungsfall.

Um die Gleichungen zu erhalten, stecken Sie die Matrizen (z. B. [x1 x2 x3 x4; x5 x6 x7 x8; x9 x10 x11 x12]) in Ihr bevorzugtes Computeralgebrasystem wie SageMath, lösen Sie die erforderliche Matrixgleichung wie abgebildet, kopieren Sie die Lösungen in Bezug auf Variablen in Ihren Code und passen Sie die Formatierung an.

Man könnte dann die Lösung an seinen Anwendungsfall anpassen, indem man bestimmte Dimensionen entsprechend skaliert oder ignoriert (z. B. die Tiefe / z-Koordinate in der Matrix der normalisierten Gerätekoordinaten entsprechend dem Anwendungsfall ignoriert).

Sie benötigen eine SVD-Zerlegungsfunktion oder -Bibliothek in Ihrer Sprache.