Geometry, constraints and computation of the trifocal tensor

Abstract

The topic of this thesis is the trifocal tensor, which describes the relative orientation (or epipolar geometry) of three uncalibrated images. So it plays the same role for three images as the fundamental matrix plays for two. The trifocal tensor is a homogenous valence-(1,2) tensor, which means that it can be represented as a 3×3×3 cube of numbers. It is of particular interest because of the following properties: ? The trifocal tensor can be determined linearly from corresponding points and lines in three images; the latter are not useable for the fundamental matrix. Consequently the trifocal tensor provides a tool to determine the relative orientation of three images without requiring approximate values. This orientation can be used to initialize a subsequent bundle block adjustment. Furthermore, the chances of running into critical configurations for determining the trifocal tensor is much smaller than for two images and the fundamental matrix. The only practically relevant critical configuration for computing the trifocal tensor happens if all corresponding image features arise from a common plane in space. After determining the trifocal tensor, the basis vectors and rotation matrices of the relative orientation of the three images can be extracted easily if the interior orientation of the images is known. If the interior orientation is unknown, but the same for all three images, then, in general, this common interior orientation can be retrieved also. If n = 3 images are given, then many unrelated trifocal tensors are computed. Before all n images can be used simultaneously, the individual basis vectors and rotation matrices derived from the unrelated tensors must be transformed into one common system. ? The transfer relations associated with the trifocal tensor can be used to transfer the content (points and lines) of two source images into the other one (the target image). If the target image is a real image, the transferred position of features can be used to initialize a matching technique in the target image. If the target image is virtual with a given orientation, then the transfer relations can be used to form the content of this new image by transferring pixel by pixel. This process is called novel view synthesis or image formation. In this thesis we concentrate on the first issue of determining the trifocal tensor. Each triple of points provides 4 equations, called trilinearities, which are linear in the tensor elements and each corresponding triple of lines provides 2 linear equations. Since the tensor is made up of 27 elements, at least 7 points, 13 lines or a proper combination are needed for a direct linear solution of the trifocal tensor. There are, however, some drawbacks associated with this linear solution. The trifocal tensor is made up of 27 elements, but it only has 18 degrees of freedom. Consequently its elements have to satisfy 8 internal constraints, besides the fixing of the scale ambiguity, to represent a valid trifocal tensor. These constraints are in generally not satisfied by the direct linear solution. Another drawback is that the direct linear solution does not minimize the errors in the original point and line measurements (so-called reprojection error) but some other quantities (so-called algebraic error). These drawbacks can be prevented by determining a valid trifocal tensor by minimizing reprojection error. The so-called Gauss-Helmert model provides a general environment for such constrained adjustment tasks. The determination of a valid trifocal tensor in the Gauß-Helmert model can be done basically in two ways: By parameterizing the tensor using its 27 elements and introducing the 8 internal constraints together with the scale fixing, or by using an alternative parameterization for the trifocal tensor that has 18 degrees of freedom. Several sets of constraints and alternative parameterizations have been proposed over the years and the most important ones are reviewed in this thesis. Most of these constraints and parameterizations are derived from the so-called tensorial slices, which are 3×3 matrices that can be sliced out of the tensor. Due to their great importance these tensorial slices are investigated thoroughly in this thesis. Using these tensorial slices we derive two new sets of constraints together with a simple geometric interpretation, and also a new alternative parameterization for the trifocal tensor. For computing a valid trifocal tensor by minimizing reprojection error in the Gauß-Helmert model it is important to have a consistent representation for the trifocal tensor. The parameterization using the projection matrices proposed by Hartley is the simplest way for such a consistent representation. This parameterization is applicable as long as (i) not all three projection centers coincide and (ii) the first projection center is different from the other two. If all image features arise from a common plane in space, the trifocal tensor can not be computed uniquely. Therefore the minimum thickness of the object points used to compute the trifocal tensor is investigated; i.e. what is the minimum deviation of the object points from a common plane, so that the computation is still possible? This investigation will be done empirically for different image configurations and different numbers of corresponding points. In these investigations we further consider the effect on the computed tensor if the internal constraints are considered or neglected, and if algebraic error or reprojection error is minimized. The findings of these empirical investigations can be summarized in the following way: For image configurations with strong geometry, like in the case of convergent terrestrial images or in the case of aerial images, the direct linear solution (algebraic error without constraints) for the trifocal tensor and the valid tensor from the Gauß-Helmert model (reprojection error with constraints) are practically the same. Concerning the minimum thickness unexpected small values were found already for 10 point correspondences. If the number of points increases, the minimum thickness gets even smaller. For the mentioned configurations and 15 point correspondences the computation of the trifocal tensor is still successful for a minimum thickness of the object points of about 1% of the camera distance (normal angle camera with assumed noise in the images of 1 pixel). For image configurations with weak geometry, like collinear projection centers with congruent viewing directions, much more point correspondences are required and the direct linear solution fails more often for small thicknesses of the object points than the valid solution from the Gauß-Helmert model. From these empirical investigations we come to the conclusion that minimizing reprojection error and considering the internal constraints is actually not necessary if the image configuration has a strong geometry ? especially if one is only interested in initial values for a subsequent bundle block adjustment. However, if a general tool for providing such initial values is aimed for, which does not have any restrictions on the image geometry and also handles weak con- figurations, then the Gauß-Helmert model minimizing reprojection error must be applied.

Das Thema dieser Arbeit ist der Trifokal-Tensor, der die relative Orientierung (oder Epipolargeometrie) von drei unkalibrierten Bildern beschreibt. In diesem Sinne ist der Tensor eine Erweiterung der Fundamental-Matrix, welche die relative Orientierung von zwei unkalibrierten Bildern beschreibt. Der Trifokal-Tensor ist ein homogener Tensor der Stufe 3; dem gemäß kann er als 3×3×3 Zahlenwürfel dargestellt werden. Aufgrund der folgenden Eigenschaften ist dieser Tensor von besonderem Interesse: ? Der Trifokal-Tensor kann in linearer Weise aus gegebenen Punkt- und Linienkorrespondenzen in drei Bildern bestimmt werden; letztere sind für die Bestimmung der Fundamental- Matrix nicht verwendbar. Aus diesem Grund stellt der Trifokal-Tensor ein Werkzeug für die Bestimmung der relativen Orientierung von drei Bildern dar, für das keine Näherungswerte benötigt werden. Diese so gefundene Orientierung kann dann als Startwert für eine anschließende Bündelblockausgleichung verwendet werden.Weiters ist dieWahrscheinlichkeit auf eine gefährliche Konfiguration zu treffen, die keine eindeutige Bestimmung des Tensors erlaubt, wesentlich geringer als für zwei Bilder und ihre Fundamental-Matrix. Die einzige praktisch relevante gefährliche Situation entsteht nur dann, wenn alle korrespondierenden Bildpunkte und -linien von einer gemeinsamen Ebene stammen. Nachdem der Trifokal-Tensor bestimmt wurde, können die Basisvektoren und Rotationsmatrizen der relativen Orientierung der drei Bilder einfach extrahiert werden ? wenn die innere Orientierung bekannt ist. Ist diese unbekannt, aber ident für alle drei Bilder, so kann diese gemeinsame innere Orientierung ebenfalls im Allgemeinen bestimmt werden. Sind n = 3 Bilder gegeben, so werden mehrere unzusammenhängende Trifokal-Tensoren berechnet. Bevor alle n Bilder gemeinsam weiterverarbeitet werden können, müssen die einzelnen unzusammenhängenden Basisvektoren und Rotationsmatrizen in ein gemeinsames System transformiert werden. ? Die sogenannten Transferbeziehungen, die sich aus dem Trifokal-Tensor ableiten lassen, können verwendet werden, um den Inhalt (Punkte und Geraden) von zwei Quellbildern in ein anderes Bild ? das Zielbild ? zu transferieren. Falls dieses Zielbild eine echtes Bild ist, dann können die transferierten Positionen verwendet werden um ein Matching-Verfahren zu starten. Falls dieses Zielbild eine virtuelles Bild mit gegebener Orientierung darstellt, dann kann der Inhalt dieses neuen Bildes mit Hilfe der Transferrelationen Pixel für Pixel aus den beiden Quellbildern aufgebaut werden. Dieser Vorgang wird im Englischen als novel view synthesis oder image formation bezeichnet. In dieser Arbeit wird der erste Punkt ? die Berechnung des Trifokal-Tensors ? näher behandelt. Jedes Triple von korrespondierenden Punkten liefert 4 Gleichungen, die sogenannten Trilinearitäten, welche linear in den 27 Tensorelementen sind. Jedes Tripel von korrespondierenden Geraden liefert 2 lineare Gleichungen. Demzufolge benötigt man mindestens 7 Punkte, 13 Geraden oder eine passende Kombination um den Trifokal-Tensor direkt bestimmen zu können. Mit dieser direkten linearen Lösung für den Trifokal-Tensor sind allerdings ein paar Nachteile verbunden. Der Trifokal-Tensor besteht zwar aus 27 Elementen, jedoch besitzt er nur 18 Freiheitsgrade. Aus diesem Grund müssen die Tensorelemente 8 interne Bedingungen erfüllen, neben der Festlegung des Tensormaßstabes, um einen gültigen Trifokal-Tensor zu repräsentieren. Diese Bedingungen werden im Allgemeinen von der direkten linearen Lösung nicht erfüllt. Ein weiterer Nachteil ist, dass die direkte lineare Lösung nicht die Fehler in den originalen Bildbeobachtungen minimiert (die sogenannten Residuen), sondern den sogenannten algebraischen Fehler. Diese Nachteile kann man beseitigen, wenn man einen gültigen Trifokal-Tensor über die Minimierung der Bildresiduen berechnet. Das sogenannte Gauß-Helmert Modell stellt eine allgemeine Umgebung für derartige bedingte Ausgleichungsaufgaben dar. Die Berechnung eines gültigen Trifokal-Tensor im Gauß-Helmert Modell kann in zwei Arten realisiert werden: Indem der Trifokal-Tensor durch seine 27 Elemente repräsentiert wird und die 8 internen Bedingungen gemeinsam mit der Festlegung des Maßstabes zusätzlich ins Gauß-Helmert Modell aufgenommen werden; oder indem der Trifokal-Tensor durch eine andere alternative Parametrisierung, die genau 18 Freiheitsgrade hat, dargestellt wird. Verschiedene Gruppen von Bedingungen und unterschiedliche Parametrisierungen wurden in der Vergangenheit publiziert, und die wichtigsten davon werden in dieser Arbeit zusammengefasst. Die meisten dieser Bedingungen und Parametrisierungen leiten sich aus den sogenannten Tensorschnitten ab. Dabei handelt es sich um 3×3 Matrizen, die aus dem Tensor sozusagen herausgeschnitten werden können. Aufgrund ihrer hohen Bedeutung werden diese Tensorschnitte in dieser Arbeit sehr genau untersucht. Mit ihrer Hilfe werden zwei neue Gruppen von Bedingungen, die auch eine einfache geometrische Interpretation erlauben, und eine neue alternative Parametrisierung für den Trifokal-Tensor hergeleitet. Um nun einen gültigen Trifokal-Tensor im Gauß-Helmert Modell über die Minimierung der Bildresiduen berechnen zu können, ist es wichtig eine konsistente Repräsentierung für den Tensor zu besitzen. Die von Hartley vorgeschlagene Parametrisierung mit Hilfe der Projektionsmatrizen ist die einfachste Möglichkeit für solch eine konsistente Repräsentierung. Diese Parametrisierung ist anwendbar solange (i) nicht alle drei Projektionszentren zusammenfallen und (ii) das erste Projektionszentrum verschieden von den anderen beiden ist. Wenn alle Korrespondenzen in den drei Bildern von einer gemeinsamen Ebene stammen, dann kann der Trifokal-Tensor nicht eindeutig bestimmt werden. Aus diesem Grund wird in dieser Arbeit die minimaler Dicke der Objektpunkte untersucht; d.h. was ist die minimal notwendige Abweichung von einer gemeinsamen Ebene, sodass der Trifokal-Tensor immer noch erfolgreich berechnet werden kann? Diese Untersuchung wird empirisch anhand verschiedener Bildkonfigurationen und unterschiedlicher Punktanzahl durchgeführt. In diesen Untersuchungen werden weiters die Unterschiede im berechneten Trifokal-Tensor behandelt, die entstehen wenn die internen Bedingungen berücksichtigt werden oder nicht, und wenn algebraische Fehler oder Bildresiduen minimiert werden. Die Erkenntnisse dieser empirischen Untersuchungen können wie folgt zusammengefasst werden: Für Bildkonfigurationen mit guter Geometrie, wie im Fall von konvergenten terrestrischen Aufnahmen oder im Fall von Luftbildern, stimmt die direkte lineare Lösung (algebraischer Fehler ohne Bedingungen) für den Tensor praktisch mit dem gültigen Tensor, der im Gauß- Helmert Modell (Bildresiduen mit Bedingungen) geschätzt wird überein. Für diese Konfigurationen mit guter Geometrie wurden auch erstaunlich geringe minimale Dicken bereits bei der Verwendung von 10 korrespondierenden Punkten gefunden. Nimmt die Anzahl der Punkte zu, so wird auch die minimale Dicke kleiner. Für die erwähnten Konfigurationen und 15 Punkttripel war die Berechung des Tensors für eine minimale Dicke von etwa 1% der Aufnahmeentfernung immer noch erfolgreich (Normalwinkel Aufnahmen und angenommenes Bildrauschen von 1 Pixel). Für Bildkonfigurationen mit schwacher Geometrie, wie im Fall von kollinearen Projektionszentren mit zusammenfallenden Blickrichtungen, ist eine deutlich größere Punkteanzahl ist notwendig und die direkte lineare Lösung versagt viel häufiger bei kleinen Objektdicken als die gültige Lösung übers Gauß-Helmert Modell. Diese empirischen Untersuchungen führen uns zum Schluss, dass für Konfigurationen mit guter Geometrie die Minimierung der Bildresiduen und die Berücksichtigung der internen Bedingungen eigentlich nicht notwendig ist ? besonders dann nicht, wenn man nur an Näherungswerten für eine anschließende Bündelblockausgleichung interessiert ist. Benötigt man jedoch ein allgemeines Werkzeug, das Näherungswerte für die Bildorientierungen liefert und keine Einschränkungen an die Bildkonfiguration setzt und auch bei schwächerer Geometrie funktioniert, so ist die Lösung übers Gauß-Helmert Modell zu realisieren.