Johannes Schneider and Falko Schindler and Thomas Läbe and Wolfgang Förstner, "Bundle Adjustment for Multi-camera Systems with Points at Infinity", In ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. I-3, pp. 75-80. 2012.

• Abstract
• BibTeX
• DOI
• Download

We present a novel approach for a rigorous bundle adjustment for omnidirectional and multi-view cameras, which enables an efficient maximum-likelihood estimation with image and scene points at infinity. Multi-camera systems are used to increase the resolution, to combine cameras with different spectral sensitivities (Z/I DMC, Vexcel Ultracam) or - like omnidirectional cameras - to augment the effective aperture angle (Blom Pictometry, Rollei Panoscan Mark III). Additionally multi-camera systems gain in importance for the acquisition of complex 3D structures. For stabilizing camera orientations - especially rotations - one should generally use points at the horizon over long periods of time within the bundle adjustment that classical bundle adjustment programs are not capable of. We use a minimal representation of homogeneous coordinates for image and scene points. Instead of eliminating the scale factor of the homogeneous vectors by Euclidean normalization, we normalize the homogeneous coordinates spherically. This way we can use images of omnidirectional cameras with single-view point like fisheye cameras and scene points, which are far away or at infinity. We demonstrate the feasibility and the potential of our approach on real data taken with a single camera, the stereo camera FinePix Real 3D W3 from Fujifilm and the multi-camera system Ladybug3 from Point Grey.

@inproceedings{Schneider2012Bundle,
  author = {Schneider, Johannes and Schindler, Falko and L\"abe, Thomas and F\"orstner, Wolfgang},
  title = {Bundle Adjustment for Multi-camera Systems with Points at Infinity},
  booktitle = {ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences},
  year = {2012},
  volume = {I-3},
  pages = {75--80},
  doi = {10.5194/isprsannals-I-3-75-2012}
}

Johannes Schneider and Falko Schindler and Wolfgang Förstner, "Bündelausgleichung für Multikamerasysteme", In Proceedings of the 31th DGPF Conference. 2011.

• Abstract
• BibTeX
• Download

Wir stellen einen Ansatz für eine strenge Bündelausgleichung für Multikamerasysteme vor. Hierzu verwenden wir eine minimale Repräsentation von homogenen Koordinatenvektoren für eine Maximum-Likelihood-Schätzung. Statt den Skalierungsfaktor von homogenen Vektoren durch Verwendung von euklidischen Grössen zu eliminieren, werden die homogenen Koordinaten sphärisch normiert, so dass Bild- und Objektpunkte im Unendlichen repräsentierbar bleiben. Dies ermöglicht auch Bilder omnidirektionaler Kameras mit Einzelblickpunkt, wie Fisheyekameras, und weit entfernte bzw. unendlich ferne Punkte zu behandeln. Speziell Punkte am Horizont können über lange Zeiträume beobachtet werden und liefern somit eine stabile Richtungsinformation. Wir demonstrieren die praktische Umsetzung des Ansatzes anhand einer Bildfolge mit dem Multikamerasystem ?Ladybug3? von Point Grey, welches mit sechs Kameras 80 % der gesamten Sphäre abbildet.

@inproceedings{Schneider2011Bundelausgleichung,
  author = {Schneider, Johannes and Schindler, Falko and F\"orstner, Wolfgang},
  title = {B\"undelausgleichung f\"ur Multikamerasysteme},
  booktitle = {Proceedings of the 31th DGPF Conference},
  year = {2011}
}

Johannes Schneider, "Lösung von Orientierungsaufgaben der Photogrammetrie mit konvexer Optimierung". Thesis at: University of Bonn. 2011.

• Abstract
• BibTeX
• Download
• Download Poster

Summary
This thesis is concerned with solving geometric optimization problems in photogrammetry using methods of convex optimization. Hartley und Schaffalitzky (2004) first suggested solving geometric problems by minimizing the Linfty-norm of the residuals, so that they can be written as convex optimization problems and as such obtain the global minimum. Since then new methods, allowing to determine the statistically and geometrically meaningful Linfty-solution without approximate values, have constantly been published.
In the field of photogrammetry calibration tasks are usually solved using adjustment theory. If the observations show normally distributed derivations, the unbiased estimator with a minimal variance is at the global minimum of the L2-cost function. Because of the nonlinearity of the cost function approximate values for the unknown parameters are needed. These can be improved using, for instance, the iterative Gauss-Newton's method. This method does however not guarantee convergence to the global minimum as the L2-cost function can generally have several local minima.
In this thesis the approach of Hartley und Schaffalitzky (2004) is described, compared with the adjustment theory, and its capability is tested on photogrammetric methods such as triangulation, homography estimation, bundle adjustment with known camera orientation, pose estimation and relative pose estimation.
At the beginning of this thesis, the necessary basics of mathematical optimization are explained. Special focus is put on the statistical meaning of minimizing the L2-and the Linfty-norm, and it is explained how a cost function can be numerically minimized using the Newton's method. Moreover, basics concerning convex optimization, allowing to identify and to solve convex as well as quasi-convex optimization problems with interior-point methods, are presented. These explanations are necessary to understand the methods used to solve the problem of determining the Linfty-solution.
This thesis focuses on three geometrical optimization problems whose Linfty-solutions are determinable by solving iterativly a convex feasability problem with second order cone constraints within a bisection method: triangulation, homography estimation and bundle adjustment with known camera orientation. The implemented methods were tested on synthetically generated data, and the statistical properties of Linfty-estimators could be verified on the basis of the distribution of residuals under the corresponding Linfty-solution. To compare the level of accuracy of the L2- and the Linfty-solution the empirical covariance matrix was deduced with the help of a Monte-Carlo simulation. This covariance matrix allows the comparison of the Helmert-point error of the L2 and Linfty-solution. The L2-solution always showed the most certain solution in normally distributed observation derivations on different noise levels. The Linfty-solution showed results similar to those of the L2-solution. The influence of extreme observation residuals is however stronger on the Linfty-solution. On a high noise level the Herlmert-point error has a significantly stronger influence on the point error of the L2-solution.
If observations contain an outlier, the Linfty-solution is strongly influenced as the outlier creates a big residual. Convex SOI-minimization, minimizing the sum of infeasibilities, suggested by Lee et al. (2010), is presented as it permits the detection of outliers in the three methods. Observations creating infeasible restrictions can be identified as outliers. SOI-minimization has always detected all the generated outliers in the synthetically generated configurations. A certain number of true inliers were however wrongly identified as outliers.
Furthermore, a solution method published by Hartley und Kahl (2009), allowing to determine rotations by searching three-dimensional rotation space with branch-and-bound, is presented. This branch-and-bound method permits the determination of the Linfty-solution of pose estimation and relative pose estimation without approximate values. In addition to their theoretical presentation, both methods were implemented and tested by applying them on synthetic data sets.
On the basis of synthetically generated data sets it could be shown in this thesis that the differences between the L2- und Linfty-solutions are not big. The Linfty-solution is therefore a suitable approximate value to initialize a L2-minimization. Iterative refinement techniques minimizing the L2 -cost function, such as bundle adjustment, can be used to improve the Linfty-estimates.
The examined optimization problems could effciently be solved as second order cone programms using interior point methods. To solve the convex optimization problems the open source software package "SeDuMi" is used. The runtime of these algorithms is by far not as fast as least squares methods but practicable to solve problems that are not overly big.
Zusammenfassung
Diese Arbeit beschäftigt sich mit der Lösung von geometrischen Optimierungsproblemen der Photogrammetrie mittels Techniken der konvexen Optimierung. Durch Hartley und Schaffalitzky (2004) wurde erstmals vorgeschlagen, geometrische Probleme durch die Minimierung der Linfty-Norm der Residuen zu lösen, da sie als konvexes Optimierungsproblem formulierbar sind und so das Erreichen des globalen Minimums garantieren. Seitdem sind stetig neue Verfahren veröffentlicht worden, mit welchen es möglich ist, ohne Näherungswerte die geometrisch sinnvolle Linfty-Lösung einiger geometrischer Aufgabenstellungen zu bestimmen.
In der Photogrammetrie werden Orientierungsaufgaben üblicherweise mit Hilfe der Ausgleichungsrechnung gelöst. Falls die Beobachtungen normalverteilten Abweichungen unterliegen, befindet sich der erwartungstreue Schätzer mit minimaler Varianz am globalen Minimum der L2-Kostenfunktion. Wegen der Nichtlinearität der Kostenfunktion sind Näherungswerte für die unbekannten Parameter erforderlich, die bspw. mit Hilfe eines Gauß-Newton-Verfahrens iterativ verbessert werden. Konvergenz zum globalen Minimum ist bei diesem Vorgehen jedoch nicht garantiert, da die L2-Kostenfunktion i. a. mehrere lokale Minima besitzen kann.
In dieser Masterarbeit wird der Ansatz von Hartley und Schaffalitzky (2004) dargestellt, mit der Ausgleichungsrechnung verglichen und an den photogrammetrischen Verfahren räumlicher Vorwärtsschnitt, Homographie-Schätzung, Bündelausgleichung mit bekannten Rotationen, räumlicher Rückwärtsschnitt und relative Orientierung, auf seine Leistungsfähigkeit hin untersucht.
Zu Beginn dieser Arbeit sind die für das Verständnis der Arbeit notwendigen Grundlagen der mathematischen Optimierung dargestellt. Es wird speziell auf die statistische Bedeutung der Minimierung der L2- und der Linfty-Norm eingegangen und aufgezeigt, wie eine Kostenfunktion mittels des Newton-Verfahrens numerisch minimiert werden kann. Zudem werden Grundlagen zur konvexen Optimierung dargestellt, welche zum Erkennen konvexer und quasikonvexer Optimierungsprobleme dienen und die Lösbarkeit dieser Optimierungsprobleme mittels Innerer-Punkte-Verfahren darlegt. Die Ausführungen sind für das Verständnis der Lösungsverfahren zur Bestimmung der Linfty-Lösung notwendig.
In dieser Arbeit betrachten wir speziell drei geometrische Optimierungsprobleme, deren Linfty-Lösungen durch iteratives Lösen eines konvexen Zulässigkeitsproblems mit quadratischen Kegelrestriktionen ("Second-order Cone Programm") innerhalbeines Bisektionsverfahrens bestimmbar sind: Den räumlichen Vorwärtsschnitt, die Homographie-Schätzung und die Bündelausgleichung bei bekannten Rotationen. Die implementierten Verfahren wurden auf synthetisch generierten Daten getestet und anhand der Verteilung der Residuen unter der jeweiligen Linfty-Lösung konnten die statistischen Eigenschaften der Linfty-Schätzer verifiziert werden. Zum Vergleich des Genauigkeitsniveaus der L2- und Linfty-Lösung wurde mittels einer Monte-Carlo-Simulation die empirische Kovarianzmatrix abgeleitet, mittels welcher der Helmertsche-Punktfehler der L2- und der Linfty-Lösung verglichen werden kann. Hierbei lieferte die L2-Lösung bei normalverteilten Beobachtungsabweichungen unter verschiedenen Rauschniveaus stets die qualitativ beste Lösung. Die Linfty-Lösung nahm häufig ähnliche Werte wie die L2-Lösung an und das Genauigkeitsniveau war durchgehend sehr ähnlich. Die Linfty-Lösung reagiert jedoch stärker auf extreme Beobachtungsabweichungen. Bei einem hohen Rauschniveau wächst der Helmertsche Punktfehler signifikant stärker an als der Punktfehler der L2-Lösung.
Falls ein Ausreißer in den Beobachtungen vorliegt, so wird die Linfty-Lösung stark verfälscht, da der Ausreißer ein großes Residuum erzeugt. Zur Ausreißerdetektion bei den drei genannten Verfahren wird die von Lee et al. (2010) vorgeschlagene konvexe SOI-Minimierung dargestellt, welche eine Lösung sucht, unter welcher die Summe der Unzulässigkeiten gegenüber den durch die Beobachtungen aufgespannten Kegelrestriktionen minimal ist. Beobachtungen, welche unzulässige Restriktionen erzeugen, können dann als Ausreißer identifiziert werden. Die SOI-Minimierung hat auf den syntetisch generierten Konfigurationen stets alle generierten Ausreißer detektiert, jedoch wurde durchgehend eine gewisse Anzahl fälschlicherweise als Ausreißer identifiziert.
Weiterhin wurde das von Hartley und Kahl (2009) veröffentlichte Lösungsverfahren untersucht, mit welchem sogar Rotationen mittels einer Branch-and-Bound-Suche im dreidimensionalen Rotationsraum bestimmt werden können. Dieses Verfahren ermöglicht es auch die Linfty-Lösung des räumlichen Rückwärtsschnitts und der relativen Orientierung stets ohne Näherungswerte zu bestimmen. Neben der theoretischen Aufarbeitung wurden beide Verfahren implementiert und durch Anwendung auf simulierte Datensätze getestet.
Es konnte in dieser Arbeit anhand von synthetisch generierten Datensätzen gezeigt werden, dass die Abweichungen zwischen der Linfty-Lösung und der L2-Lösung nicht sehr groß sind. Die Linfty-Lösung eignet sich daher als Näherungswert zur Initialisierung einer L2-Minimierung. Mittels iterativer Lösungsverfahren, wie bspw. einer Bündelausgleichung, kann die Linfty-Lösung durch Minimierung der L2-Kostenfunktion verbessert werden.
Die untersuchten Probleme konnten effizient durch Lösen von Second-order Cone Programmen mittels Innere-Punkte-Verfahren gelöst werden. Zur Lösung der konvexen Optimierungsprobleme wurde das Open-Source-Programmpaket "SeDuMi" verwendet. Die Laufzeit dieser Algorithmen ist zwar bei weitem nicht so schnell wie eine Kleinste-Quadrate-Schätzung, jedoch bei der Lösung nicht allzu großer Probleme anwendbar.

@mastersthesis{Schneider2011Losung,
  author = {Schneider, Johannes},
  title = {L\"osung von Orientierungsaufgaben der Photogrammetrie mit konvexer Optimierung},
  school = {University of Bonn},
  year = {2011},
  note = {Betreuung: Prof. Dr.-Ing. Dr. h.c. mult. Wolfgang F\"orstner, Dipl.-Ing. Falko Schindler, Dipl.-Ing. Lutz Roese-Koerner}
}

Johannes Schneider, "Untersuchung von Farbinvarianten für die Erzeugung von Merkmalsdeskriptoren". Thesis at: Department of Photogrammetry, University of Bonn. 2009.

• Abstract
• BibTeX

Summary
This bachelor thesis treats the subject of colour invariants with special regards to their purpose as feature descriptors for region matching. Hence, a structured review of the theoretical content of the article by [Burghouts and Geusebroek, 2009] is given and three of the colour invariants presented in this article are implemented for the SIFT-based matching and empirically evaluated. As an introduction into the subject the theoretical basics of colour constancy are presented with a primary emphasis on the explication of the term "Colour Invariance". Thus, the physical derivation of colour invariants is shown. A computed value for the colour invariants can be obtained by the use of the Gaussian colour model. The implementation of the colour based Colour-SIFT-descriptors is carried out on the basis of measured RGB-values. The colour gradients are used instead of the intensity gradients for the detection and the feature description in the SIFT-method. In this thesis three different Colour-SIFT are presented and tested: The W-colour-SIFT, which is invariant to changes in illumination intensity, the C-colour-SIFT, which is furthermore invariant to shadow and shading and the H-colour-SIFT, which is in addition to the properties mentioned above invariant to highlights. The applicability of images with colour invariant gradients for feature description is tested by two implementation methods of a Colour-SIFT: The COL-method matches regions in relation to their respective colour gradients without using intensity gradients. The COL+ INT-method extracts regions in relation to intensity as well as colour gradients. For every extracted region a descriptor on the basis of its intensity gradients and its colour gradients is defined. For the test of these descriptors the basic framework of the evaluation by Mikolajczyk and Schmid is adopted. The evaluation tests the feature descriptors' discriminative power and invariance. The application of the SIFT implementation published by Lowe allows a direct comparison to the implemented Colour-SIFT. The result of the test shows the advantage of the C-colour-SIFT, invariant to shadow and shading, concerning the matching of images under changing illumination directions. Also concerning changes in viewpoint the C-colour-SIFT obtained better results than the SIFT. The H-colour-SIFT cannot fulfil the high expectations due to its high level of invariance. Especially in changing colour temperatures the H-colour-SIFT is very instable. The lack of intensity information seriously affects the discriminative power. The W-colour-SIFT does not come to any significantly better results than the SIFT provided by Lowe.
Zusammenfassung
Diese Arbeit beschäftigt sich mit Farbinvarianten insbesondere unter dem Aspekt der Nutzung dieser zur Merkmalsdeskription bei der Punktzuordnung. Hierzu wird die Arbeit von [Burghouts and Geusebroek, 2009] theoretisch aufgearbeitet und drei der dort vorgestellten Farbinvarianten werden für die Zuordnung mit SIFT-Deskriptoren implementiert und empirisch evaluiert. Zur Einführung in die Thematik werden die theoretischen Grundlagen der Farbinvarianz dargestellt, wobei vor allem der Begriff "Farbinvarianz" erläutert wird. Anschließend wird die physikalische Herleitung der Farbinvarianten aufgezeigt. Um die Farbinvarianten rechentechnisch bestimmbar zu machen, wird das Gaußsche Farbmodell verwendet. Die Implementierung der farbbasierten Colour-SIFT-Deskriptoren wird auf der Grundlage gemessener RGB- Werte durchgeführt. Die Farbgradienten werden im SIFT-Verfahren anstatt der Intensitätsgradienten für die Detektion und die Merkmalsdeskription verwendet. Es werden in dieser Arbeit drei verschiedene Colour-SIFT vorgestellt und untersucht: Der gegen Änderungen in der Beleuchtungsintensität invariante W-colour-SIFT, der C-colour-SIFT, welcher zudem invariant gegenüber Schatten ist und der H-colour-SIFT, welcher neben den genannten Eigenschaften zudem gegen Glanzlichteffekte invariant ist. Die Eignung der farbinvarianten Gradientenbilder zur Merkmalsdeskription wird durch zwei Verfahren der Implementierung eines Colour-SIFT untersucht: Das Verfahren COL ordnet Punkte basierend auf den jeweiligen Farbgradienten zu, ohne die Intensitätsgradienten zu verwenden. Das Verfahren COL+ INT extrahiert Regionen aus der Verteilung der Intensitäts- und Farbgradienten. Für jede extrahierte Region wird jeweils ein Merkmalsdeskriptor auf Grundlage der Intensitätsgradienten als auch der Farbgradienten bestimmt. Zur Untersuchung dieser Deskriptoren werden die Verfahren zur Evaluation von Mikolajczyk und Schmid verwendet. Die Merkmalsdeskriptoren werden auf die diskriminative Leistungsfähigkeit und Invarianz untersucht. Die Anwendung der von Lowe veröffentlichten SIFT-Implementierung erlaubt einen direkten Vergleich zu den implementierten Colour-SIFT. Das Ergebnis der Untersuchung zeigt den Vorzug des schatteninvarianten C-colour-SIFT bei der Zuordnung von Bildern, bei denen sich die Beleuchtungsrichtung ändert. Auch bei der Änderung der Aufnahmerichtung erzielte der C-colour-SIFT bessere Ergebnisse als der SIFT. Der H-colour-SIFT kann jedoch die hohen Erwartungen auf Grund des hohen Grades an Invarianz nicht erfüllen. Dieser ist vor allem bei Änderungen in der Farbtemperatur sehr instabil. Als problematisch erweist sich das vollständige Fehlen der Intensitätsinformation bei dieser Farbinvarianten. Der W-colour-SIFT erzielt keine signifikant besseren Ergebnisse als der von Lowe veröffentlichte SIFT.

@mastersthesis{Schneider2009Untersuchung,
  author = {Schneider, Johannes},
  title = {Untersuchung von Farbinvarianten f\"ur die Erzeugung von Merkmalsdeskriptoren},
  school = {Department of Photogrammetry, University of Bonn},
  year = {2009},
  note = {Betreuung: Prof. Dr.-Ing. Wolfgang F\"orstner, Dipl.-Ing. Susanne Wenzel}
}