Lösung von Orientierungsaufgaben der Photogrammetrie mit ... · Institut für Geodäsie und Geoinformation Professur für Photogrammetrie, Nussallee 15, 53115 Bonn Masteraufgabe

Institut für Geodäsie und GeoinformationProfessur für Photogrammetrie

Lösung von Orientierungsaufgaben derPhotogrammetrie mit konvexer Optimierung

Masterarbeitim Master-Studiengang Geodäsie und Geoinformation

an der Hohen Landwirtschaftlichen Fakultät

der Rheinischen Friedrich-Wilhelms-Universität

zu Bonn

vorgelegt am 22. Dezember 2011 von

Johannes Schneidergeboren am 15.08.1985 in Kleve

Bonn 2011

Erstprüfer: Prof. Dr.-Ing. Dr. h. c.mult. Wolfgang Förstner

Zweitprüfer: Dipl.-Ing. Falko SchindlerDipl.-Ing. Lutz Roese-Koerner

Institut für Geodäsie und Geoinformation

Professur für Photogrammetrie, Nussallee 15, 53115 Bonn

Masteraufgabe

für Herrn Johannes Schneider

Lösung von Orientierungsaufgaben der Photogrammetrie mitkonvexer Optimierung

Orientierungsverfahren in der Photogrammetrie werden üblicherweise mit Hilfe der Aus-gleichungsrechnung gelöst. Wegen der Nichtlinearität der Optimierungsfunktion sind Nä-herungswerte für die unbekannten Parameter erforderlich, die mit Hilfe eines Gauß-Newton-Verfahrens iterativ verbessert werden. Konvergenz zum globalen Optimum ist bei diesemVorgehen nicht garantiert. In jüngster Zeit wurde von Kahl und Hartley (2005) vorgeschla-gen, geometrische Probleme unter Nutzung der L∞-Norm zu lösen, da sie als konvexesOptimierungsproblem formulierbar sind und so das Erreichen eines globalen Optimumsgarantieren. Hilfsmittel ist die so genannte „Second-order Cone Programming“ (SOCP),ein Spezialfall der konvexen quadratischen Optimierung.

In der Masterarbeit soll dieser Ansatz erarbeitet, im Vergleich zur Ausgleichungsrechnungdargestellt und an repräsentativen geometrischen Aufgaben aus der Photogrammetrie,zum Beispiel räumlicher Vorwärtsschnitt, räumlicher Rückwärtsschnitt und relative Ori-entierung, auf seine Leistungsfähigkeit hin untersucht werden.

Ausgegeben am: 29. April 2011Abgabetermin: 29. Dezember 2011Abgegeben am: 22. Dezember 2011

Prof. Wolfgang Förstner

1. Betreuer: Dipl.-Ing. Falko Schindler 2. Betreuer: Dipl.-Ing. Lutz Roese-Koerner

Erklärung

Hiermit erkläre ich, dass ich die vorliegende Arbeit selbstständig und ohne Benutzung andererals der angegebenen Hilfsmittel angefertigt habe. Alle Stellen, die wörtlich oder sinngemäß ausveröffentlichten oder nicht veröffentlichten Schriften entnommen wurden, sind als solche kennt-lich gemacht.

Bonn, 22. Dezember 2011

Johannes Schneider

Lösung von Orientierungsaufgaben der Photogrammetriemit konvexer Optimierung

Johannes Schneider1

Zusammenfassung

Diese Arbeit beschäftigt sich mit der Lösung von geometrischen Optimierungspro-blemen der Photogrammetrie mittels Techniken der konvexen Optimierung. DurchHartley und Schaffalitzky (2004) wurde erstmals vorgeschlagen, geometrischeProbleme durch die Minimierung der L∞-Norm der Residuen zu lösen, da sie alskonvexes Optimierungsproblem formulierbar sind und so das Erreichen des globalenMinimums garantieren. Seitdem sind stetig neue Verfahren veröffentlicht worden, mitwelchen es möglich ist, ohne Näherungswerte die geometrisch sinnvolle L∞-Lösungeiniger geometrischer Aufgabenstellungen zu bestimmen.

In der Photogrammetrie werden Orientierungsaufgaben üblicherweise mit Hilfe derAusgleichungsrechnung gelöst. Falls die Beobachtungen normalverteilten Abweichun-gen unterliegen, befindet sich der erwartungstreue Schätzer mit minimaler Varianzam globalen Minimum der L2-Kostenfunktion. Wegen der Nichtlinearität der Kos-tenfunktion sind Näherungswerte für die unbekannten Parameter erforderlich, diebspw. mit Hilfe eines Gauß-Newton-Verfahrens iterativ verbessert werden. Konver-genz zum globalen Minimum ist bei diesem Vorgehen jedoch nicht garantiert, da dieL2-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 photogramme-trischen Verfahren räumlicher Vorwärtsschnitt, Homographie-Schätzung, Bündelaus-gleichung mit bekannten Rotationen, räumlicher Rückwärtsschnitt und relative Ori-entierung, auf seine Leistungsfähigkeit hin untersucht.

Zu Beginn dieser Arbeit sind die für das Verständnis der Arbeit notwendigenGrundlagen der mathematischen Optimierung dargestellt. Es wird speziell auf diestatistische Bedeutung der Minimierung der L2- und der L∞-Norm eingegangen undaufgezeigt, wie eine Kostenfunktion mittels des Newton-Verfahrens numerisch mini-miert werden kann. Zudem werden Grundlagen zur konvexen Optimierung dargestellt,welche zum Erkennen konvexer und quasikonvexer Optimierungsprobleme dienen unddie Lösbarkeit dieser Optimierungsprobleme mittels Innerer-Punkte-Verfahren dar-legt. Die Ausführungen sind für das Verständnis der Lösungsverfahren zur Bestim-mung der L∞-Lösung notwendig.

In dieser Arbeit betrachten wir speziell drei geometrische Optimierungsproble-me, deren L∞-Lösungen durch iteratives Lösen eines konvexen Zulässigkeitsproblemsmit quadratischen Kegelrestriktionen („Second-order Cone Programm“) innerhalbeines Bisektionsverfahrens bestimmbar sind: Den räumlichen Vorwärtsschnitt, dieHomographie-Schätzung und die Bündelausgleichung bei bekannten Rotationen. Dieimplementierten Verfahren wurden auf synthetisch generierten Daten getestet und an-hand der Verteilung der Residuen unter der jeweiligen L∞-Lösung konnten die statis-tischen Eigenschaften der L∞-Schätzer verifiziert werden. Zum Vergleich des Genauig-

1E-Mail: [email protected]

mailto:[email protected]

VIII Zusammenfassung

keitsniveaus der L2- und L∞-Lösung wurde mittels einer Monte-Carlo-Simulation dieempirische Kovarianzmatrix abgeleitet, mittels welcher der Helmertsche-Punktfehlerder L2- und der L∞-Lösung verglichen werden kann. Hierbei lieferte die L2-Lösungbei normalverteilten Beobachtungsabweichungen unter verschiedenen Rauschniveausstets die qualitativ beste Lösung. Die L∞-Lösung nahm häufig ähnliche Werte wiedie L2-Lösung an und das Genauigkeitsniveau war durchgehend sehr ähnlich. DieL∞-Lösung reagiert jedoch stärker auf extreme Beobachtungsabweichungen. Bei ei-nem hohen Rauschniveau wächst der Helmertsche Punktfehler signifikant stärker anals der Punktfehler der L2-Lösung.

Falls ein Ausreißer in den Beobachtungen vorliegt, so wird die L∞-Lösung starkverfälscht, da der Ausreißer ein großes Residuum erzeugt. Zur Ausreißerdetektionbei den drei genannten Verfahren wird die von Lee et al. (2010) vorgeschlagenekonvexe SOI-Minimierung dargestellt, welche eine Lösung sucht, unter welcher dieSumme der Unzulässigkeiten gegenüber den durch die Beobachtungen aufgespann-ten Kegelrestriktionen minimal ist. Beobachtungen, welche unzulässige Restriktionenerzeugen, können dann als Ausreißer identifiziert werden. Die SOI-Minimierung hatauf den syntetisch generierten Konfigurationen stets alle generierten Ausreißer detek-tiert, jedoch wurde durchgehend eine gewisse Anzahl fälschlicherweise als Ausreißeridentifiziert.

Weiterhin wurde das von Hartley und Kahl (2009) veröffentlichte Lösungsver-fahren untersucht, mit welchem sogar Rotationen mittels einer Branch-and-Bound-Suche im dreidimensionalen Rotationsraum bestimmt werden können. Dieses Verfah-ren ermöglicht es auch die L∞-Lösung des räumlichen Rückwärtsschnitts und derrelativen Orientierung stets ohne Näherungswerte zu bestimmen. Neben der theore-tischen Aufarbeitung wurden beide Verfahren implementiert und durch Anwendungauf simulierte Datensätze getestet.

Es konnte in dieser Arbeit anhand von synthetisch generierten Datensätzen ge-zeigt werden, dass die Abweichungen zwischen der L∞-Lösung und der L2-Lösungnicht sehr groß sind. Die L∞-Lösung eignet sich daher als Näherungswert zur Initia-lisierung einer L2-Minimierung. Mittels iterativer Lösungsverfahren, wie bspw. einerBündelausgleichung, kann die L∞-Lösung durch Minimierung der L2-Kostenfunktionverbessert werden.

Die untersuchten Probleme konnten effizient durch Lösen von Second-order ConeProgrammen mittels Innere-Punkte-Verfahren gelöst werden. Zur Lösung der konve-xen Optimierungsprobleme wurde das Open-Source-Programmpaket „SeDuMi“ ver-wendet. Die Laufzeit dieser Algorithmen ist zwar bei weitem nicht so schnell wie eineKleinste-Quadrate-Schätzung, jedoch bei der Lösung nicht allzu großer Probleme an-wendbar.

Solving Photogrammetric Calibration TasksUsing Convex Optimization

Johannes Schneider1

Abstract

This thesis is concerned with solving geometric optimization problems in photo-grammetry using methods of convex optimization. Hartley und Schaffalitzky(2004) first suggested solving geometric problems by minimizing the L∞-norm ofthe residuals, so that they can be written as convex optimization problems and assuch obtain the global minimum. Since then new methods, allowing to determine thestatistically and geometrically meaningful L∞-solution without approximate values,have constantly been published.In the field of photogrammetry calibration tasks are usually solved using adjust-

ment theory. If the observations show normally distributed derivations, the unbiasedestimator with a minimal variance is at the global minimum of the L2-cost func-tion. Because of the nonlinearity of the cost function approximate values for theunknown parameters are needed. These can be improved using, for instance, theiterative Gauss-Newton’s method. This method does however not guarantee conver-gence to the global minimum as the L2-cost function can generally have several localminima.In this thesis the approach of Hartley und Schaffalitzky (2004) is described,

compared with the adjustment theory, and its capability is tested on photogramme-tric methods such as triangulation, homography estimation, bundle adjustment withknown 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 L∞-norm, and it is explained how a cost function can be numerically mini-mized using the Newton’s method. Moreover, basics concerning convex optimization,allowing to identify and to solve convex as well as quasi-convex optimization pro-blems with interior-point methods, are presented. These explanations are necessaryto understand the methods used to solve the problem of determining the L∞-solution.This thesis focuses on three geometrical optimization problems whose L∞-solutions

are determinable by solving iterativly a convex feasability problem with second ordercone constraints within a bisection method: triangulation, homography estimationand bundle adjustment with known camera orientation. The implemented methodswere tested on synthetically generated data, and the statistical properties of L∞-estimators could be verified on the basis of the distribution of residuals under thecorresponding L∞-solution. To compare the level of accuracy of the L2 and the theL∞-solution the empirical covariance matrix was deduced with the help of a Monte-Carlo simulation. This covariance matrix allows the comparison of the Helmert-pointerror of the L2 and L∞-solution. The L2-solution always showed the most certainsolution in normally distributed observation derivations on different noise levels. TheL∞-solution showed results similar to those of the L2-solution. The influence of ex-treme observation residuals is however stronger on the L∞-solution. On a high noise

1Email: [email protected]

mailto:[email protected]

X Abstract

level the Herlmert-point error has a significantly stronger influence on the point errorof the L2-solution.If observations contain an outlier, the L∞-solution is strongly influenced as the

outlier creates a big residual. Convex SOI-minimization, minimizing the sum of in-feasibilities, suggested by Lee et al. (2010), is presented as it permits the detectionof outliers in the three methods. Observations creating infeasible restrictions can beidentified as outliers. SOI-minimization has always detected all the generated outliersin the synthetically generated configurations. A certain number of true inliers werehowever wrongly identified as outliers.Furthermore, a solution method published by Hartley und Kahl (2009), al-

lowing to determine rotations by searching three-dimensional rotation space withbranch-and-bound, is presented. This branch-and-bound method permits the deter-mination of the L∞-solution of pose estimation and relative pose estimation withoutapproximate values. In addition to their theoretical presentation, both methods wereimplemented 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 L∞-solutions are not big. The L∞-solutionis therefore a suitable approximate value to initialize a L2-minimization. Iterativerefinement techniques minimizing the L2-cost function, such as bundle adjustment,can be used to improve the L∞-estimates.The examined optimization problems could efficiently be solved as second order

cone programms using interior point methods. To solve the convex optimization pro-blems the open source software package “SeDuMi” is used. The runtime of thesealgorithms is by far not as fast as least squares methods but practicable to solveproblems that are not overly big.

XI

Inhaltsverzeichnis

Seite

Notation XIII

1 Einleitung 1

1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Verwandte Arbeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.4 Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Optimierungsprobleme 5

2.1 Grundlagen der mathematischen Optimierung . . . . . . . . . . . . . . . . . . . . 5

2.2 Zielfunktionen unter der Lp-Norm . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.1 Minimierung der L2 Norm . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2.2 Minimierung der L∞ Norm . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 Das Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.4 Konvexe Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4.1 Konvexe Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4.2 Konvexe Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.4.3 Konvexe Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.4.4 Lösung konvexer Programme . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.5 Quasikonvexe Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.5.1 Quasi- und pseudokonvexe Funkionen . . . . . . . . . . . . . . . . . . . . 262.5.2 Lösung quasikonvexer Programme . . . . . . . . . . . . . . . . . . . . . . 28

3 Mehrbildgeometrie unter der L∞-Norm 31

3.1 Der räumliche Vorwärtsschnitt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.1.1 Die Kostenfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.1.2 Lösung des L∞-Optimierungsproblems . . . . . . . . . . . . . . . . . . . . 40

3.2 Bündelausgleichung bei bekannten Rotationen . . . . . . . . . . . . . . . . . . . . 43

3.3 Homographie-Schätzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.4 Ein Verfahren zur Ausreißerdetektion . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.5 Branch-and-Bound im Rotationsraum . . . . . . . . . . . . . . . . . . . . . . . . 49

XII Inhaltsverzeichnis

3.6 Der räumliche Rückwärtsschnitt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.7 Relative Orientierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4 Experimente 57

4.1 Vergleich der L∞-Lösung mit der L2-Lösung . . . . . . . . . . . . . . . . . . . . . 574.1.1 Der räumliche Vorwärtsschnitt . . . . . . . . . . . . . . . . . . . . . . . . 584.1.2 Homographie-Schätzung und Bündelausgleichung bei bekannten Rotationen 61

4.2 Detektierbarkeit von Ausreißern . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.2.1 Ausreißerdetektion beim räumlichen Vorwärtsschnitt . . . . . . . . . . . . 66

4.3 Branch-and-Bound im Rotationsraum . . . . . . . . . . . . . . . . . . . . . . . . 694.3.1 Räumlicher Rückwärtsschnitt . . . . . . . . . . . . . . . . . . . . . . . . . 694.3.2 Relative Orientierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5 Zusammenfassung und Ausblick 75

5.1 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

5.2 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

Literaturverzeichnis 77

Abbildungsverzeichnis 79

Anhang i

A Algebraische Lösung ii

B Polynomiale Methode iv

XIII

Notation

Symbol Bedeutung1 Einservektor (der Index gibt die Dimension an)A Matrix

d(·, ·) Distanzfunktion; liefert euklidische Distanz zwischen den zwei ArgumentenE Essentielle Matrix

f0(x) Zielfunktion bzw. Kostenfunktionfi(x) Funktion der Ungleichungsrestriktionen (für i ≥ 0)

γ Maximal zulässige Residuum unter der L∞-Normhj(x) Funktion der Gleichungsrestriktionen

H Homographiel BeobachtungsvektorI Einheitsmatrix (der Index gibt die Dimension an)K KalibriermatrixP Projektionsmatrixu euklidischer Bildpunkt auf Bildebeneu homogener BildpunkteU euklidischer ObjektpunktU homogener Objektpunktr ein Residuumr Residuenvektor

R(x) ResiduumsfunktionR RotationsmatrixSγ Ein durch γ aufgespannter Lorentzkegel

S(·) Erstellt schiefsymmetrische Matrix aus dem ArgumentΣ Kovarianzmatrixv Kamerastrahlx Parametervektor bzw. unbekannte OptimierungsvariablenZ Kameratranslation

∇f0(x) Gradient einer Funktion∇2f0(x) Hesse-Matrix einer Funktion

(·)a Näherungswert(·) Optimale Größe

1

1. Einleitung

1.1 Motivation

Orientierungsprobleme in der Photogrammetrie werden üblicherweise mit Hilfe der Ausglei-chungsrechnung gelöst. Hierbei wird diejenige Lösung gesucht, unter welcher die L2-Norm derVerbesserungen (daher auch Verbesserungsquadratsumme genannt) minimal ist. Die so genann-te Kleinste-Quadrate-Schätzung geht auf Gauß (1809) zurück und ist seitdem ein Standard-verfahren zur Lösung von Optimierungsproblemen geworden. In der Photogrammetrie hat sichals Standardtechnik die Bündelausgleichung etabliert, in welcher die Bestimmung aller unbe-kannten Größen der Kollinearitätsgleichung in einer einzigen strengen Ausgleichungsrechnungerfolgt (vgl. Mikhail und Ackermann 1982 oder Triggs et al. 2000). Sie bietet die fol-genden Vorteile: (i) sie kann auf eine große Menge von Problemen angewendet werden, da sieweitestgehend generell ist, (ii) sie stellt einen erwartungstreuen Schätzer mit minimaler Varianzdar, wenn die Beobachtungen normalverteilten Abweichungen unterliegen, (iii) die Erweiterungum Bedingungsgleichungen ist einfach, (iv) zur Robustifizierung kann eine robuste Kostenfunk-tion minimiert werden, z. B. nach Huber (1981), und (v) häufig ergeben sich dünnbesetzteNormalgleichungssysteme, welche effizient gelöst werden können.Wegen der Nichtlinearität der Optimierungsaufgabe sind genügend gute Näherungswerte für

die unbekannten Parameter erforderlich, die bspw. mit Hilfe eines Newton-Verfahrens iterativverbessert werden. Konvergenz zum globalen Optimum ist bei diesem Vorgehen jedoch nichtgarantiert, da die Verbesserungsquadratsumme mehrere lokale Minima aufweisen kann (vgl. Ab-bildung 1).

x

globalesMinimum

lokaleMinima

f0(x)

( )

(a) Eine Funktion f0(x) mit mehreren lokalen Minima.

x

Minimum

f0(x)

( )

(b) Eine konvexe Funktion f0(x).

Abbildung 1: Darstellung einer willkürlichen Funktion (a), welche über ihrem Definitionsbereich mehrereMinima besitzt. Bei einem numerischen Minimierungsverfahren wie dem Newton-Verfahrenmuss der Näherungswert für die optimale Lösung innerhalb des eingeklammerten Intervallsbekannt sein, da die Lösung sonst in ein lokales Minimum konvergiert. Bei einer konvexenFunktion 1(b) konvergiert die Lösung stets im globalen Minimum, da keine lokalen Minimaexistieren. Das Newton-Verfahren wird ausführlich in Abschnitt 2.3 beschrieben und dieexakte Definition einer konvexer Funktion erfolgt in Abschnitt 2.4

.

Unter der Erkenntnis, dass viele Optimierungsprobleme der Photogrammetrie unter der L∞-Norm konvex sind, wurden in jüngster Zeit im Bereich der Computer Vision Lösungsmöglichkei-ten veröffentlicht, welche stets global optimale Lösungen liefern. Zentrale geometrische Aufga-benstellungen der Photogrammetrie, zum Beispiel der räumliche Vorwärtsschnitt, der räumlicheRückwärtsschnitt und die Homographie-Schätzung, können als quasikonvexe Optimierungspro-

2 1. Einleitung

bleme umgeformt werden. Diese können mittels des so genannten „Second-order Cone Program-ming“ (SOCP), welches eine Standardtechnik in der konvexen Optimierung darstellt, effizientgelöst werden. Im Gegensatz zum klassischen Ansatz der Kleinsten-Quadrate-Schätzung, garan-tiert die Verwendung der L∞-Norm global optimale Schätzwerte, jedoch unter der Annahme,dass die Beobachtungen einer begrenzten Gleichverteilung unterliegen.

1.2 Aufgabenstellung

In dieser Arbeit sollen die Grundlagen der konvexen Optimierung erarbeitet werden, welchespeziell zur Identifikation und Lösung von Second-order Cone Programmen befähigen. Aufbauendauf diesen Grundlagen soll der von Hartley und Schaffalitzky 2004 vorgeschlagene Ansatzzur Lösung photogrammetrischer Aufgabenstellung als konvexe Optimierungsprobleme durch Mi-nimierung der L∞-Norm theoretisch dargestellt und untersucht werden. Die L∞-Verfahren zurLösung des räumlichen Vorwärtsschnitts, der Homographie-Schätzung, der Bündelausgleichungmit bekannten Rotationen, des räumlichen Rückwärtsschnitts und der relativen Orientierungsollen theoretisch dargestellt und implementiert werden, so dass diese mittels generierten Da-tensätzen im Vergleich zur L2-Lösung der Ausgleichungsrechnung auf ihre Leistungsfähigkeituntersucht werden können. Da die L∞-Lösung anfällig gegen Ausreißer ist, soll zudem die Mög-lichkeit der Robustifizierung oder der Ausreißerdetektion dargestellt und untersucht werden.

1.3 Verwandte Arbeiten

Die mathematischen Grundlagen der konvexen Optimierung werden bereits seit etwa einemJahrhundert theoretisch untersucht. In den 40er Jahren wurde mit der Entwicklung effizienterAlgorithmen zur Lösung verschiedener Klassen von Optimierungsproblemen begonnen. NeuesInteresse an der konvexen Optimierung wurde erreicht, als erkannt wurde, dass Innere-Punkte-Verfahren, welche zur Lösung linearer Programme entwickelt wurden, auch zur Lösung konvexernicht-linearer Programme verwendet werden können. Mit dem von Hartley und Schaffalitz-ky (2004) veröffentlichten Ansatz zur Formulierung photogrammetrischer Aufgabenstellungenals konvexe Optimierungsprobleme mit Second-order Cone Restriktionen, wurde im Bereich derComputer Vision die globale Optimierung Gegenstand intensiver Forschung.

Kahl (2005) und Ke und Kanade (2005) veröffentlichten unabhängig voneinander ein Lö-sungsverfahren zur Bestimmung der L∞-Lösung für den räumlichen Vorwärtsschnitt, die Homo-graphie-Schätzung und die Bündelausgleichung bei bekannten Kamerarotationen, in welchemiterativ konvexe Zulässigkeitstests innerhalb eines Bisektionsverfahren gelöst werden. Es stelltbis zum heutigen Zeitpunkt das Standardverfahren zur Bestimmung der L∞-Lösung dieser Pro-bleme dar, da es effizient und einfach zu implementieren ist.Geometrische Verfahren, in welcher die Rotationsmatrix der äußeren Orientierung einer Kame-

ra bestimmt werden müssen, können nicht innerhalb eines Bisektionsverfahrens gelöst werden.Hartley und Kahl (2009) schlagen ein Branch-and-Bound-Verfahren im dreidimensionalenRotationsraum zur Minimierung der nicht-konvexen Kostenfunktion vor, in welchem iterativkonvexe Zulässigkeitsprobleme gelöst werden. Dieses Verfahren ermöglicht die Lösung des räum-lichen Rückwärtsschnitts und der relativen Orientierung.Die Möglichkeit der Berücksichtigung des stochastischen Modells der beobachteten Bildpunkte

bei den Kegelrestriktionen legen Ke und Kanade (2006) dar.Der vermeintliche Nachteil der Anfälligkeit der L∞-Norm gegenüber Ausreißern kann jedoch

gerade zur Detektion von Ausreißern ausgenutzt werden, wie es Lee et al. (2010) durch die

1.4. Aufbau der Arbeit 3

konvexe Minimierung der Summe der Unzulässigkeiten zeigen. Einen anderen Ansatz für denUmgang mit Ausreißern verfolgen ?? durch Robustifizierung der Zielfunktion, wodurch eine glo-bal optimale Lösung jedoch nicht mehr gewährleistet wird.

Agarwal et al. (2006) zeigen, dass mittels eines Branch-and-Bound-Verfahrens stets die glo-bale L2-Lösung für den räumlichen Vorwärtsschnitt und die Homographie-Schätzung bestimmtwerden kann. Jedoch bleibt dieses Verfahren aufgrund der Komplexität lediglich auf Problemenmit niedrig dimensionalen Lösungsräumen anwendbar.

1.4 Aufbau der Arbeit

In Kapitel 2 werden zum Verständnis der Ausführungen dieser Arbeit die notwendigen Grund-lagen zur mathematischen Optimierung dargestellt. Es wird speziell auf die statistische Bedeu-tung der Minimierung der L2- und der L∞-Norm eingegangen und aufgezeigt, wie eine Kos-tenfunktion mittels des Newton-Verfahrens numerisch minimiert werden kann. Zudem werdenGrundlagen zur konvexen Optimierung dargestellt, welche zum Erkennen konvexer und quasi-konvexer Optimierungsprobleme dienen und die Lösbarkeit dieser Optimierungsprobleme mittelsInnerer-Punkte-Verfahren darlegen.Anschließend werden in Kapitel 3 die in dieser Arbeit untersuchten Lösungsverfahren zur Be-

stimmung der L∞-Lösung photogrammetrischer Aufgabenstellungen vorgestellt: Das sind derräumliche Vorwärtsschnitt, die Homographie-Schätzung, die Bündelausgleichung bei bekanntenKamerarotationen, der räumliche Rückwärtsschnitt und die relative Orientierung. Anhand desräumlichen Vorwärtsschnitts wird die durch den Abbildungsprozess resultierende Residuums-funktion dargestellt und aufgezeigt, warum die L2-Kostenfunktion mehre Minima besitzen kann.Da die L∞-Norm anfällig gegenüber Ausreißern ist, wird zudem ein Verfahren zur Ausreißerde-tektion dargestellt.In Kapitel 4 werden alle implementierten Verfahren auf synthetisch generierten Daten getestet,

auf ihre Eigenschaften untersucht und teilweise statistisch ausgewertet und mit der entsprechen-den L2-Lösung verglichen.Abschließend wird die Arbeit in Kapitel 5 zusammengefasst und es wird ein Ausblick auf

weitere mögliche Untersuchungen gegeben.

5

2. Optimierungsprobleme

In diesem Abschnitt werden einige Grundlagen der mathematischen Optimierung erläutert, wel-che zum Verständnis der nachfolgenden Abschnitte dieser Arbeit benötigt werden. Hierzu werdenwir in Abschnitt 2.1 zunächst die allgemeine Problemstellung und wichtige Begriffe der mathe-matischen Optimierung einführen. In Abschnitt 2.2 werden wir die statistische Bedeutung derMinimierung von Lp-Normen und in Abschnitt 2.3 das Newton-Verfahren zur numerischen Lö-sung nichtlinearer Gleichungssysteme. Anschließend werden wir in Abschnitt 2.4 speziell auf all-gemeine konvexe Optimierungsprobleme und die Lösung dieser mittels Innere-Punkte-Verfahreneingehen. In Abschnitt 2.5 zeigen wir, wie quasikonvexe Optimierungsprobleme stets auf konvexeOptimierungsprobleme überführt werden können. Die in diesem Abschnitt zusammengestelltenInformationen entstanden vornehmlich in Anlehnung an das Buch über die konvexe Optimierungvon Boyd und Vandenberghe (2004).

2.1 Grundlagen der mathematischen Optimierung

Das Gebiet der mathematischen Optimierung beschäftigt sich damit, optimale Parameter ei-nes Systems aus einer Menge möglicher Alternativen zu finden. Hierbei bedeutet „optimal“ imeinfachsten Falle, dass eine reale Zielfunktion minimiert oder maximiert wird, wobei nur die Va-riablen ausgewertet werden dürfen, welche sich innerhalb einer zulässigen Menge befinden. DieGeneralisierung der Optimierungstheorie und -techniken umfasst ein sehr großes Feld der an-gewandten Mathematik. Optimierungsprobleme stellen sich in generell allen wissenschaftlichenDisziplinen, in denen aufgrund eines Systemverhaltens auf unbekannte Parametern geschlossenwerden muss, wie u. a. in den Natur-, Ingenieur- und Wirtschaftswissenschaften (vgl. bspw. Gillet al. 1981 und Bonnans et al. 2006).Die generelle Formulierung eines mathematischen skalaren Optimierungsproblems kann durch

minimiere f0(x)

u.d.N. fi(x) ≤ 0, i = 1, ..., nhj(x) = 0, j = 1, ..., p

(2.1)

beschrieben werden. Ziel ist es, den optimalen Parametervektor x ∈ Rm zu bestimmen, mit wel-chem zum einen die Zielfunktion f0(x) den kleinstmöglichen Wert annimmt und zum anderendie Ungleichungsrestriktionen fi(x) ≤ 0 und Gleichungsrestriktionen hj(x) = 0 nicht verletztwerden. Es können beliebig viele Restriktionen durch Gleichungs- und Ungleichungsbedingun-gen an die Parameter formuliert werden. Wenn das Optimierungsproblem keine Restriktionenaufweist, spricht man von einem unrestringierten Optimierungsproblem, bei welchem die Lösungvon x Werte auf dem gesamten vorgegebenen Definitionsbereich annehmen kann. Die Definiti-onsmenge D eines Optimierungsproblems ist die Schnittmenge aller Parameterwerte, die sowohlauf der Zielfunktion als auch auf allen Bedingungsfunktionen definiert ist

D =

n⋂i=0

Dfi ∩p⋂j=0

Dhj . (2.2)

Ein Punkt x ∈ D, welcher alle Nebenbedingungen erfüllt, wird als zulässig bezeichnet. DieMenge aller Punkte {x∈D | fi(x)≤0, i= 1, ..., n, hj(x) = 0, j= 1, ..., p} ist die zulässige Menge.Falls die zulässige Menge leer ist, wird das Optimierungsproblem als unzulässig bezeichnet.Maximierungsprobleme können ohne Beschränkung der Allgemeinheit durch Minimierung der

6 2. Optimierungsprobleme

negativen Zielfunktion beschrieben werden. Die skalare Zielfunktion f0 wird häufig auch Kos-tenfunktion genannt. Ein Optimierungsproblem, bei welchem die Werte mehrerer Zielfunktionengleichzeitig zu optimieren sind, wird Vektoroptimierung oder auch Pareto-Optimierung genannt.In dieser Arbeit werden wir jedoch nur Optimierungsprobleme behandeln, bei welchen eine ska-lare Zielfunktion f0 : Df0 ∈ Rm → R minimiert werden soll.

Beispiel 1. Stigler (1945) modellierte ausgewogene Ernährungspläne, welche aus m verfüg-baren Nahrungsmitteln zu unbekannten Teilen zusammengesetzt werden sollten. Die Kosten derjeweiligen Nahrungsmittel seien im m×1-Vektor c und die unbekannten Anteile der jeweiligenNahrungsmittels im m×1-Vektor x enthalten. Die Anteile der Nahrungsmittel sollten so gewähltwerden, dass die Kosten so gering wie möglich sind. Die zu minimierenden Kostenfunktion er-gibt sich demnach durch f0(x) = cTx. In einem ausgewogenen Ernährungsplan sollten jedochgewisse Anteile bi an Grundbestandteilen enthalten sein. Im Nahrungsmittel j seien aij Einhei-ten des gewünschten i-ten Bestandteils (bspw. Vitamine, Eiweiß) vorhanden. Das restringierteMinimierungsproblem lautet dann

minimiere cTx

u.d.N.∑m

j=1 aijxi ≥ bi, i = 1, ..., n.(2.3)

Der Definitionsbereich des Optimierungsproblems x ∈ Rm+ stellt eine implizite Restriktion andas Vorzeichen von x dar, da eine negative Nahrungsaufnahme nicht möglich ist. Diese kann auchexplizit als Ungleichungsrestriktion xi ≥ 0, i = 1, ..., p eingeführt werden. In der Standardformeiner Problemformulierung werden die Funktionen fi und hi dermaßen formuliert, dass die rechteSeite der Gleichungs- und Ungleichungsbedingungen Null ist, was stets durch Subtraktion derrechten Seite erreicht werden kann.Unter der Verwendung vektorwertiger Funktionen für die Nebenbedingungen f i(x) : Rm →

Rni bzw. hi(x) : Rm → Rpi und expliziter Restriktionen erhalten wir das äquivalente Minimie-rungsproblem der Form

minimiere cTx

u.d.N. −(Ax− b) � 0−x � 0 .

(2.4)

Für zwei Vektoren x = [x1, ..., xm]T und y = [y1, ..., ym]T wird als elementweiser Vergleichs-operator xi ≤ yi für alle i = 1, ...,m dann x � y verwendet.In diesem Beispiel liegt eine lineare Zielfunktion mit linearen Ungleichungsrestriktionen vor.

Wir werden in Abschnitt 2.4 sehen, dass es sich daher um ein so genanntes „lineares Programm“handelt, welches mit Techniken der konvexen Optimierung gelöst werden kann.

2.2 Zielfunktionen unter der Lp-Norm

Bei einem skalaren Optimierungsproblems wird die optimale Lösung durch die Minimierung ei-ner skalaren Zielfunktion f0(x) bestimmt. Liegt ein Satz von Beobachtungen l ∈ Rn vor, so wollenwir die Parameter x ∈ Rm des deterministischen Modells finden, welche die Beobachtungen un-ter einem angenommenen stochastischen Modell bestmöglich wiedergeben. Das deterministischeModell entspricht bei photogrammetrischen Aufgabenstellungen z. B. dem modellierten Abbil-dungsprozess eines Objektpunktes auf die Bildebene. Das stochastische Modell beinhaltet dieAnnahme darüber, welcher Verteilung die Modellabweichungen der Beobachtungen unterliegen.Unter einem mit xa parametrisierten Modell können die Modellbeobachtungen l

aberechnet

werden, z. B. durch Rückprojektion eines durch die Koordinaten xa parametrisierten Objekt-

2.2. Zielfunktionen unter der Lp-Norm 7

punktes auf die Bildebene. Wie gut die Parametrisierung xa des Modells zu den Beobachtungenpasst, kann dann durch eine geeignete Metrik im Beobachtungsraum formuliert werden. Hierzuwird meist eine aus der Lp-Norm abgeleitete Metrik verwendet. Die zu minimierende Zielfunktionergibt sich dann durch

f0(x) = ||r||p =

(n∑i=1

|ri|p)1/p

, (2.5)

wobei ri das i-te Element des Residuenvektors r = l − laist. So liefert bspw. die L2-Norm

||r||2 = (r21 +r2 + ...+r2

n)1/2 die euklidische Länge oder die L1-Norm ||r||1 = |r1|+ |r2|+ ...+ |rn|die Manhatten-Länge von r. Für p → ∞ ergibt sich für endlich-dimensionale Residuenvektorendie L∞-Pseudonorm ||r||∞ = max {|r1|, |r2|, ..., |rn|}.Im Folgenden werden wir auf die L2- und die L∞-Normen eingehen, welche für die Optimie-

rungsprobleme in dieser Arbeit Verwendung finden. Bei der Notation werden wir im Folgendenkeinen tiefgestellten Index für die L2-Norm verwenden: Der Normierungsoperator ||·|| ohne Indexentspricht im Folgenden stets der L2-Norm || · ||2.

2.2.1 Minimierung der L2 Norm

Unter der Annahme, dass die Residuen normalverteilt sind und um Null streuen (also ri ∼N(0, σ2)), ist die Wahrscheinlichkeitsverteilung der Beobachtungen l bei gegebenem wahren Be-obachtungsvektor l durch

P ( l | l ) = z

n∏i=1

exp

(−||li − li||

2

2σ2

)(2.6)

gegeben, wobei z die Gesamtwahrscheinlichkeit auf Eins normiert und σ2 die Varianz der Re-siduen ist. Durch Minimierung des Logarithmus von (2.6) über l

akann gezeigt werden, dass

diejenigen Modellbeobachtungen ladie Wahrscheinlichkeit für die Beobachtungen l maximieren,

welche f0 =∑n

i=1 r2i = ||l− l

a||2 minimieren. Daher entspricht die kleinste-Quadrate Lösung der

Maximum-Likelihood Schätzung, wenn die Beobachtungen voneinander unabhängig sind undweißem Rauschen unterliegen. Am globalen Minimum der Zielfunktion

f0(x) = ||r|| = (l− la)T(l− l

a) (2.7)

befindet sich der erwartungstreue Lösungsvektor x mit minimaler Varianz.

2.2.2 Minimierung der L∞ Norm

Unter der Annahme, dass die Residuen einer Wahrscheinlichkeitsverteilung der Form

P ( l | l ) = zn∏i=1

exp

(−

((li − li)

σ

)p)(2.8)

folgen, entspricht diejenige Lösung der Maximum-Likelihood Schätzung, welche f0(x) =∑n

i=1 ||ri||pminimiert. Die Wahrscheinlichkeitsverteilung (2.8) entspricht für p→∞ der durch σ begrenztenGleichverteilung von l um l. Unter der L∞-Norm ist daher die Wahrscheinlichkeit der Beob-achtungen, deren absoluten Residuen kleiner als σ sind, gleich groß, für die anderen beträgt sieNull. Die Minimierung der L∞-Norm liefert den Lösungsvektor x, unter welchem alle absolutenResiduen ri kleiner als σ sind, so dass alle Beobachtungen eine Wahrscheinlichkeit ungleich Null


besitzen. Die Maximum-Likelihood Schätzung entspricht dann dem Parametervektor x, welcherdie Zielfunktion

f0(x) = ||r||∞ = maxi|l− l

a| (2.9)

minimiert. Die Minimierung des maximalen Residuums wird häufig daher auch als Minimax-Optimierung bezeichnet.

2.3 Das Newton-Verfahren

Das Newton-Verfahren ist ein Standardverfahren zur numerischen Lösung von nichtlinearenGleichungssystemen. Die grundlegende Idee dieses Verfahrens ist es, eine zu minimierende Ziel-funktion f0 in der Nähe einer aktuellen Näherung x(ν) durch eine lokale Approximation f0 zuersetzen. Die Minimierung von f0 liefert eine verbesserte Näherung x(ν+1), welche als Ausgangs-punkt für einen weiteren Verbesserungsschritt dient. Dieses Vorgehen wird iterativ fortgesetzt,bis bspw. die Änderung der Näherungslösungen zweier aufeinander folgenden Iterationen einefestgesetzte Schranke unterschreitet (vgl. bspw. Bonnans et al. 2006, Kap. 4).Die Approximation f0 von f0 durch eine Taylor-Reihe zweiter Ordnung an einer Stelle x lautet

f0(x+ ∆x) = f0(x) +∇f0(x)T∆x+1

2∆xT∇2f0(x)∆x (2.10)

und stellt eine quadratische Funktion in ∆x dar. Die quadratische Funktion besitzt ein ein-deutiges globales Minimum, wenn die Hesse-Matrix ∇2f0(x) positiv definit ist. Bei konvexenFunktionen ist dies stets der Fall, wie wir in Abschnitt 2.4.2 sehen werden. Liegt also eine positivdefinite Hesse-Matrix ∇2f0(x) vor, so hat die quadratische Funktion f0 nur genau ein Minimuman der Stelle x+∆x. In Abbildung 2 ist eine zu minimierende Funktion f : R→ R zusammen mitihre Approximation f0, welche ausgehend vom Punkt x durch eine Taylorreihe zweiter Ordnunggegeben ist, dargestellt. Gesucht ist derjenige Schritt ∆x, welcher f0(x+ ∆x) minimiert.

f0

f0~

f0(x)

x(n)

f0(x(n)+Dx)

x(n+1) = x(n)+Dx

Abbildung 2: Der Graph einer zu minimierenden Funktion f : R → R ist als durchgezogene und ihreApproximation f0 durch eine Taylorreihe zweiter Ordnung ausgehend von einem Startpunktx als gestrichelte Linie dargestellt. Durch die Addition des Newton-Schritt ∆x zu x erhaltenwir denjenigen Punkt, an welchem f0 minimal ist (nach Boyd und Vandenberghe 2004).

Wir bezeichnen ∆x als Newton-Schritt, unter welchem f0(x + ∆x) minimal ist. Die notwen-dige Bedingung für ein Extremum fordert, dass der Gradient an dieser Stelle Null ist. Da diequadratische Funktion f0 nur ein Extremum besitzt, stellt die notwendige Bedingung somit auchstets eine hinreichende Bedingung dar:

∇f0(x+ ∆x) = ∇f0(x) + ∆x∇2f0(x) = 0 . (2.11)

2.3. Das Newton-Verfahren 9

Wir erhalten den optimalen Newton-Schritt somit durch Lösen des linearen Gleichungssystems

∆x = −∇2f0(x)−1∇f0(x) . (2.12)

Ist die Hesse-Matrix ∇2f0(x) positiv definit, so gilt dies auch für die inverse Hesse-Matrix undwir erhalten ∇f0(x)T∆x < 0, falls ∇f0(x) 6= 0. Daher ist ∆x stets eine Abstiegsrichtung,bis Konvergenz erreicht wird. In Algorithmus 1 ist das reguläre Newton-Verfahren schematischdargestellt.

Algorithmus 1 : Das Newton-Verfahren.

Daten :x . . . Startpunktε . . . Toleranzmaxiter . . . Maximale Anzahl an Iterationen

for iter = 1 : maxiter do1

// Berechnung des Newton-Schrittes2

∆x := −∇2f(x)−1∇f(x) ;3

// Berechnung des Newton-Dekrements4

λ2 := ∇f(x)T∇2f(x)−1∇f(x) ;5

// Abbruchskriterium6

if λ2/2 < ε then7

return x;8

end9

// Optional: Modifizierte Schrittweite10

Bestimmung des Faktors t mittels „Backtracking“, sonst t = 111

// Aktualisiere Lösung12

x := x+ t∆x;13

end14

return x;15

Das Newton-Dekrement

λ(x) =(∇f0(x)T∇2f0(x)−1∇f0(x)

)1/2(2.13)

an der Stelle x dient als Abbruchskriterium. Der in der Abbruchbedingung verwendete Wert12λ

2 entspricht der Differenz zwischen dem Funktionswert der Näherungslösung f0(x) und demFunktionswert der minimierten Approximation f0(x+ ∆x), wie es durch Einsetzten von (2.12)in (2.10) leicht zu zeigen ist.Falls die Zielfunktion f nur ein einziges Minimum besitzt, liefert das Newton-Verfahren stets

die global optimale Lösung. Andernfalls entscheidet die Wahl des Startpunktes x(0) zu welcherLösung das Verfahren konvergiert, da stets eine Abstiegsrichtung von der aktuellen Näherungverwendet wird.Es gibt viele Abwandlungen des Newton-Verfahrens, welche sich auf das Konvergenzverhalten

auswirken. So wird bspw. beim gedämpften Newton-Verfahren zur Steigerung der Konvergenz-geschwindigkeit in jeder Iteration ein den Newton-Schritt vergrößernder Faktor t bestimmt. ZurSchrittweitenbestimmung wird hierzu häufig das so genannte Backtracking-Verfahren verwen-


det, so dass übermäßig kleine Schritte vermieden werden (vgl. John E. Dennis 1996). In derKonvergenzphase wird schließlich der Faktor auf t→ 1 gedämpft.Zudem existieren Verfahren, welche die Richtung des Newton-Schrittes manipulieren. Falls die

Hesse-Matrix bspw. nicht positiv definit ist, wird nach dem Ansatz von Levenberg und Marquardtein möglichst kleines λ > 0 bestimmt und auf die Hauptdiagonale der Hesse-Matrix hinzu addiert,so dass ∇2f0(x) + λIm positiv definit ist (vgl. Levenberg 1944 und Marquardt 1963).Anschließend wird eine Abstiegsrichtung s aus dem linearen Gleichungssystem(

∇2f0(x) + λIm)

∆x = −∇f0(x) (2.14)

bestimmt. Für λ→ 0 entspricht s dem optimalen Newton-Schritt ∆x und für λ→∞ weist s inRichtung des negativen Gradienten. Die Abstiegsrichtung des Levenberg-Marquardt-Verfahrensstellt somit einen Kompromiss zwischen dem Newton-Verfahren und den so genannten Gradien-tenabstiegsverfahren dar.

2.4 Konvexe Optimierung

Im Folgenden werden wir uns mit der konvexen Optimierung beschäftigen, welche ein Spezi-alfall des oben eingeführten skalaren Optimierungsproblems (2.1) darstellt. Ein konvexes Op-timierungsproblem zeichnet sich durch die folgenden drei Eigenschaften aus (vgl. Boyd undVandenberghe 2004):

1. die Zielfunktion f0(x) ist konvex,2. eventuelle Ungleichungsbedingungen fi(x) sind konvexe Funktionen und3. eventuelle Gleichungsrestriktionen hi(x) sind affin.

Die wesentliche Eigenschaft solch eines konvexen Optimierungsproblems ist es, dass ein zulässi-ges lokales Minimum aufgrund dieser Eigenschaften stets dem globalen Minimum entspricht. Beikonvexen Optimierungsproblemen ist daher das Erreichen eines globalen Optimums mit einembeliebigen zulässigen Startpunkt x(0) sichergestellt.Im Folgenden werden wir zunächst in Abschnitt 2.4.1 Eigenschaften konvexer Mengen und

in Abschnitt 2.4.2 konvexer Funktionen darstellen. Anschließend erfolgt in Abschnitt 2.4.3 eineEinteilung konvexer Optimierungsprobleme aufgrund der abbildenden Eigenschaften der Ziel-und Restriktionsfunktionen in verschiedene Programme. Zur Lösung spezieller Problemstellun-gen der konvexen Optimierung werden wir in Abschnitt 2.4.4 das Grundprinzip der Inneren-Punkte-Verfahren erörtern, wobei wir speziell auf das Barriere-Verfahren eingehen werden. Füreine breitere und detailliertere Darstellung der konvexen Optimierung sei auf die Darlegungenvon Boyd und Vandenberghe 2004 hingewiesen, welche als Grundlage für die folgenden Aus-führung verwendet wurden.

2.4.1 Konvexe Mengen

Eine Menge C ⊆ Rm ist konvex, falls

αx+ (1− α)y ∈ C mit 0 ≤ α ≤ 1 (2.15)

für alle x,y ∈ C gilt. Diese Definition lässt sich geometrisch einfach veranschaulichen: JedeVerbindungslinie zwischen zwei beliebigen Punkten der Teilmenge C eines reelen VektorraumesRm muss vollständig in C liegen. Demgegenüber beinhalten affine Mengen alle Punkte, welchesich auf einer unbeschränkten Linien durch zwei Punkte eines Vektorraumes befinden. Somit

2.4. Konvexe Optimierung 11

ist jede affine Menge generell auch eine konvexe Menge, dies gilt jedoch nicht andersherum. InAbbildung 3 ist ein Beispiel und ein Gegenbeispiel für konvexe Mengen dargestellt.

x1

x2

(a) Eine konvexeMenge.

x1

x2

(b) Eine nicht-konvexeMenge.

xa

x

zulässige Menge

Niveauliniender Zielfunktion

(c) Der direkte Pfad vom Startpunkt xa zumOptimum x liegt nicht in der zulässigen Menge.

Abbildung 3: Darstellung einer konvexen (a) und einer nicht-konvexen Menge (b) sowie der Problematiknicht konvexer zulässiger Mengen bei der Optimierung (c).

Alternativ kann eine Menge C als konvex bezeichnet werden, wenn diese jede endliche Kon-vexkombination

x =

n∑i=1

αixi mit 0 ≤ αi undn∑

i=1

αi = 1 (2.16)

für alle xi ∈ C enthält. Eine Konvexkombination kann als gewichtete Mittelbildung interpretiertwerden.Bei den in Abschnitt 2.4.3 behandelten restringierten Optimierungsproblemen werden stets nur

Punkte aus einer bestimmten Teilmenge des Rm als mögliche Lösungsvektoren zugelassen. Fallsdie zulässige Menge nicht leer ist, dann existiert stets eine optimale Lösung. Die Forderung, dasses sich hierbei um eine konvexe Menge handelt, wird bei vielen Optimierungsverfahren zwingendvorausgesetzt. In Abbildung 3(c) wird diese Notwendigkeit schnell ersichtlich: Die schraffierteFläche stellt eine nicht konvexe zulässige Menge dar und die elliptischen Kurven repräsentierendas Niveau einer Kostenfunktion im R2. Bei nicht konvexen Mengen ist nicht sichergestellt, dasses einen direkten Pfad vom Startpunkt zum gesuchten Minimum gibt, welches somit bspw. mittelsdes Newton-Verfahrens nicht gefunden werden könnte. Im Folgenden werden einige besonderekonvexe Mengen, die in unserem Zusammenhang von Interesse sind, dargestellt.

Der verallgemeinerte Kegel

Eine Menge K ⊆ Rm wird als konvexer Kegel bezeichnet, wenn

αx+ βy ∈ K mit 0 ≤ α, β (2.17)

für alle x,y ∈ K gilt. Geometrisch bedeutet dies, dass zwei beliebige nicht-negative homogenePunkte des m-dimensionalen Kegels K stets einen zweidimensionalen Kegel aufspannen, dervollständig in K liegt (vgl. Abbildung 4(a)).Ein Kegel kann unter einer beliebigen Norm || · || aus dem Rm aufgespannt werden. Die konvexe

Menge K eines Normkegels ist definiert durch

K = { (x, t) | ||x|| ≤ t } ∈ Rm+1 (2.18)

für alle x ∈ Rm.Ein Kegel unter der L2-Norm wird als Lorentzkegel oder als quadratischer Kegel bezeichnet,

häufig wird im Kontext der Optimierung jedoch der englische Begriff Second-order Cone ver-


wendet. In Abbildung 4(b) ist der Lorentzeinheitskegel im R3 dargestellt. In Abbildung 4(c) istder Rand des Einheitskegels in der (x1, x2)-Ebene mit t = 1 unter der L1-, L2- und L∞-Normdargestellt. Das Innere eines Kegel ist unter jeder beliebigen Metrik eine konvexe Menge.

x1

x2

0

(a) Ein durch x1 und x2 im R2

aufgespannter Lorentzkegel.(b) Rand des Lorentzkegels

K = {(x1, x2, t) | || [x1 x2]T ||2 ≤ t}.

1

1

1

1

1

1

||x||1

||x||2

||x||

8

(c) Öffnung eines L1-, L2- undL∞-Normkegels.

Abbildung 4: Darstellung eines Lorentzkegel imR2 (a) und des Randes eines Lorentz-Einheitskegels imR3

(b). Zudem ist die Öffnung eines Einheitsnormkegels in der t = 1 Ebene unter verschiedenenNormen dargestellt (c).

Positiv (semi)definite Kegel sind eine Teilmenge der symmetrischen Matrizen S. Die Mengealler reellen symmetrischen m×m-Matrizen M sei gegeben durch

Sm = { M ∈ Rm×m | MT = M }, (2.19)

wobei Sm einen Vektorraum der Dimensionm(m+1)/2 aufspannt. Zur expliziten Kennzeichnungvon Mengen positiv semidefiniter und definiter Marizen verwenden wir die Notation

Sm+ = { M ∈ Sm | xTMx � 0 } bzw. Sm++ ={ M ∈ Sm | xTMx � 0 } (2.20)

für jeden Vektor x ∈ Rm\0. Die Menge Sm+ bildet einen konvexen Kegel, da für jedes α, β ≥ 0und zwei beliebige Matrizen A,B ∈ Sm+ stets αA + βB ∈ Sm+ gilt. Dies folgt aus den Beding-ungen in (2.20) und gilt somit analog für Sm++. In Abbildung 5 sind die Grenzen eines positivsemidefiniten und eines positiv definiten Kegels aus dem S2 im R3 dargestellt.

(a) Die positiv semidefinite Matrix [0 0; 0 1]aus dem S2+ im R3.

(b) Die positiv definite Einheitsmatrix[1 0; 0 1] aus dem S2++ im R3.

Abbildung 5: Darstellung einer positiv semidefiniten (a) und einer positiv definiten Matrix (b) aus demS2 im R3.


Als einen eigentlichen Kegel bezeichnen wir einen konvexen Kegel K ⊆ Rm, der die folgendenEigenschaften aufweist:

• K ist abgeschlossen (d. h. durch seinen Rand begrenzt),• K ist ein spitzer Kegel (d. h. K ∩ −K = {0}) und• das Innere von K ist nicht-leer (d. h. K ist kein Strahl).

Beispiele für echte Kegel ist jeder Orthant

K = { x ∈ Rm | 0 ≤ eixi mit ei = {−1,+1} fur alle i = 1, ...,m } (2.21)

oder jeder semidefinite Kegel K ∈ Sm+ . Mittels eines echten Kegels K können wir eine Halbord-nung

x �K y ⇔ y − x ∈ K (2.22)

bzw. die dazugehörige Striktordnung

x ≺K y ⇔ y − x ∈ K◦ (2.23)

auf dem Rm definieren, wobei K◦ dem Inneren von K entspricht. Mit K = R+ entsprichtdiese verallgemeinerte Ordnungsrelation der gewöhnlichen ≤ bzw. < Beziehungen. Mit K =Rm+ verwenden wir keinen tiefgestellten Index: Für zwei Vektoren x = [x1, ..., xm]T und y =[y1, ..., ym]T entspricht dann x � y dem elementweisen Vergleichsoperator xi ≤ yi für alle i =1, ...,m.

Hyperebenen, Halbräume und Polyeder

Eine Hyperebene hat die Form

A = { x | aTx− b = 0 } mit x ∈ Rm. (2.24)

Geometrisch kann a ∈ Rm\0 als Normalenvektor der Hyperebene und b ∈ R als der kleinsteAbstand der Hyperebene zum Ursprung interpretiert werden, wie es in Abbildung 6(a) für eineHyperebene im R2 dargestellt ist, wo diese einer Geraden entspricht. Da Hyperebenen affin sind,sind sie ebenfalls konvex.Ein Halbraum

H = { x | aTx− b ≤ 0 }. (2.25)

ist die konvexe Teilmenge des durch eine Hyperebene geteilten RaumesRm (vgl. Abbildung 6(b)).Halbräume sind konvex, jedoch niemals affin.Ein Polyeder P ist eine Punktmenge aus dem Rm, welche sich durch ein lineares Gleichungs-

und Ungleichungssystem mit endlich vielen Hyperebenen begrenzen lässt:

P ={x | aTi x− bi ≤ 0, cTj x− dj = 0 mit i = 1, ..., n und j = 1, ..., p

}(2.26)

={x | Ax � b, Cx = d mit A ∈ Rn×m und C ∈ Rp×m

}. (2.27)

Ein Polyeder ist stets konvex, da die Schnittmenge P =⋂ni=1Hi ∩

⋂pj=1Aj endlich vieler Halb-

räume Hi und Hyperebenen Aj , welche stets konvex sind, auch stets wieder eine konvexe Mengeergibt. In Abbildung 6(c) ist ein Polyeder als Schnittmenge von fünf Halbräumen im R2 darge-stellt.


x2

x1

b

a

A

(a) Eine Hyperbene A im R2

a

H

(b) Ein Halbraum H im R2

a1

a5

a4

a3

a2

P

(c) Ein Polyeder P im R2

Abbildung 6: Veranschaulichung der im Text eingeführten konvexen Mengen im R2: Eine Hyperebene A(a), ein Halbraum H (b) und ein durch fünf Hyperebenen begrenztes Polyeder P (c) (nachBoyd und Vandenberghe 2004).

2.4.2 Konvexe Funktionen

Eine konvexe Funktion f : X → R bildet eine konvexe Teilmenge X ⊆ Rm auf R ab, so dass

f (αx+ (1− α)y) ≤ αf (x) + (1− α)f (y) mit 0 ≤ α ≤ 1 (2.28)

für alle x,y ∈ X gilt. Anschaulich bedeutet die Definition: Die Funktionswerte zwischen zweiPunkten x und y liegen unterhalb oder auf der Verbindungsgeraden der beiden Funktionswerte anf(x) und f(y). Die Verbindungsgerade zweier Funktionswerte darf sich somit niemals mit demFunktionsgraphen schneiden (vgl. Abbildung 7). Lineare Funktionen sind somit auch konvex,da die Verbindungslinie ihrer Funktionswerte exakt auf dem Graphen verlaufen und ihn somitniemals schneiden.

x1 x2ax1+(1-a)x2

af(x1)+(1-a)f(x2)

(a) Eine konvexe Funktion

x1 x2ax1+(1-a)x2

(b) Eine nicht-konvexe Funtion

Abbildung 7: Darstellung einer konvexen (a) und einer nicht-konvexen Funktion (b) f(x) : R→ R: EineFunktion ist konvex, wenn jede Verbindungslinie zwischen zwei beliebigen Funktionswertenstets über oder auf dem Funktionsgraphen einer Funktion liegt.

Konvexe Funktionen sind stets kontinuierlich und weisen über ihren gesamten Definitionsbe-reich eine nicht-negative Krümmung auf. Ihre Hesse-Matrix ist somit stets positiv (semi-)definit.Hieraus ergibt sich die besondere Bedeutung konvexer Funktionen für Minimierungsprobleme:Zum einen besitzt eine konvexe Zielfunktion nur genau ein eindeutiges lokales Minimum, welchessomit dem globalen Minimum entspricht. Die notwendige Bedingung für ein Vorliegen eines Mi-nimums ist das Vorliegen eines kritischen Punktes, bei welchem ∇f(x) = 0 ist. Diese notwendigeBedingung ist bei konvexen Funktionen zugleich eine hinreichende Bedingung, da aufgrund derKrümmungseigenschaften Sattelpunkte nicht auftreten können. Zum anderen führt jede appro-


ximierte Abstiegsrichtung in einem iterativen Lösungsverfahren zum globalen Minimum, so dassbspw. im Newton-Verfahren ein beliebiger zulässiger Startpunkt verwendet werden kann.Als interessantes Beispiel konvexer Funktionen auf dem Rm wollen wir die bereits in Ab-

schnitt 2.2 eingeführte Normfunktion f(x) = ||x||p nennen, die für jedes p ≥ 1 stets konvex aufRm ist.

2.4.3 Konvexe Programme

Ein konvexes Optimierungsproblem besitzt die Form

minimiere f0(x)

u.d.N. fi(x) ≤ 0, i = 1, ..., nhj(x) = aTj x− bj = 0, j = 1, ..., p ,

(2.29)

wobei zum einen die Zielfunktion f0(x) und die Ungleichungsfunktionen fi(x) konvex und zumanderen die Gleichungsfunktionen hj(x) affin sind.Die zulässige Menge ergibt sich aus der Schnittmenge der Definitionsmenge des Optimierungs-

problems D = ∩ni=1Dfi ∩ ∩pj=1Dhj mit den m konvexen Subniveaumengen {x | fi(x) ≤ 0} und

den p konvexen Hyperebenen {x | aTj x = bj}. Da die Schnittmenge konvexer Mengen stets wie-der konvex ist (vgl. Boyd und Vandenberghe 2004, S. 36), ist die zulässige Menge konvexerOptimierungsprobleme ebenfalls konvex.1 Die fundamentale Eigenschaft konvexer Optimierungs-probleme ist, dass nur ein einziges globales Minimum und keine lokalen Nebenminima existieren.In Abbildung 8 ist der Zusammenhang zwischen einer konvexen Zielfunktion und einem konvexenDefinitionsbereich, welcher einen einzigen optimalen Punkt x enthält, im R2 skizziert.

D

f0(x)

f0(xmin)

xmin

Abbildung 8: Die zulässige Lösungsmenge eines konvexen Optimierungsproblems ist konvex. Die optimaleLösung des Problems x befindet sich auf dem Definitionsbereich D, wo die Zielfunktionminimal und die Lösung zulässig ist.

Durch Betrachtung der abbildenden Eigenschaften der jeweiligen Zielfunktion f0 und der Ne-benbedingungen f i und hj lassen sich konvexe Optimierungsprobleme verschiedenen Klassen zu-ordnen. Die konvexe Optimierung beinhaltet u. a. die wohlbekannte kleinste-Quadrate-Schätzung(als Quadratisches Programm) und Lineare Programme (vgl. Beispiel 1) als Spezialfälle. Hierbeiist „Programm2“ als Synonym zu „Optimierungsproblem“ zu verstehen.

1Es können sich auch durch nicht konvexe Restriktionen konvexe Mengen ergeben. Solche konvexe Optimierungs-probleme werden dann häufig als abstrakte konvexe Optimierungsprobleme bezeichnet.

2Die Verwendung des Begriffes „Programm“ im Kontext der mathematischen Optimierung ist historisch begrün-det: Gegenstand der ersten Anwendungen der Optimierung war es einen militärischen Aktionsplan (englisch:„program of actions“) zu erstellen.


Skalare Optimierungsprobleme.

minimiere f0(x)

u. d.N. f i(x) � 0, i = 1, ..., nhj(x) = 0, j = 1, ..., p

(2.30)

mit der Zielfunktion f0 : Rm → R und den Restriktionen f i : Rm → Rki und hj : R

m → Rkj .

Konvexe Optimierung.

minimiere f0(x)

u.d.N. f i(x) � 0, i = 1, ..., n

aTjx = bj , j = 1, ..., p,

(2.31)

wobei f0(x) und f i(x) konvexe Funktionen und hj(x) affine Funktionen sind.

Lineare Programme (LP).

minimiere cTx+ d

u. d.N. Gx ≤ h

Ax = b,

(2.32)

wobei G ∈ Rn×m und A ∈ Rp×m. Sowohl die Zielfunktion f0(x) als auch dieUngleichungsrestriktionen f i(x) sind affin.

Quadratische Programme (QP).

minimiere 12xTPx+ qTx+ r

u. d.N. Gx ≤ h

Ax = b,

(2.33)

wobei P ∈ Sm+ , G ∈ Rn×m und A ∈ Rp×m. Die Zielfunktion f0(x) ist quadratisch und dieUngleichungsrestriktionen f i(x) sind affin.

Second-order Cone Programme (SOCP).

minimiere fTx

u. d.N. ‖Aix+ bi‖2 ≤ cTi x+ d

Fx = g,

(2.34)

wobei f0(x) linear ist und Ai ∈ Rki×m und F ∈ Rp×m. Durch jede Ungleichungsrestriktionfi wird ein m-dimensionaler Lorentzkegel aufgespannt

Semidefinite Programme (SDP).

minimiere cTx

u. d.N. x1F 1 + x2F 2 + ...+ xmFm + G � 0Ax = b,

(2.35)

wobei F 1, ...,Fm,G ∈ Sk und A ∈ Rp×m.

...

...

Abbildung 9: Darstellung der Einordnung der konvexen Optimierung innerhalb der allgemeinen Optimie-rung mittels der abbildenden Eigenschaften der Zielfunktion und der Bedingungsfunktio-nen. Einige Spezialfälle, welche mit maßgeschneiderten Algorithmen effizient gelöst werdenkönnen, sind mit steigender Komplexität dargestellt.


In Abbildung 9 sind vier Spezialfälle der konvexen Optimierung mit steigender Komplexitätmit ihren Unterscheidungsmerkmalen dargestellt:• Lineare Programme (kurz LP) weisen eine lineare Zielfunktion und lineare Restriktionen

auf. Die zulässige Menge eines LP beschreibt einen Polyeder. Die optimale zulässige Lösungder zu minimierenden Funktion cTx+b liegt stets so weit wie möglich in Richtung des Vek-tors −c auf dem Rand des Polyeders, wie es die geometrische Interpretation in Abbildung10(a) darstellt.• Quadratische Programme (kurz QP) besitzen im Gegensatz zu linearen Programmen eine

quadratische Zielfunktion der Form 12x

TPx+qTx+ r. Die zulässige Menge wird bei einemLP durch einen Polyeder beschrieben, der optimale Punkt liegt jedoch entweder am Randder zulässigen Menge oder am Minimum der Zielfunktion, wenn dieses im Inneren liegt(vgl. Abbildung 10(b)). Ein QP stellt eine Verallgemeinerung eines LP dar, da mit P = 0ein QP in ein LP überführt werden kann.• Ein so genanntes „Second-order Cone Programm“ (kurz SOCP) weist wie ein LP eine lineare

Zielfunktion auf, besitzt jedoch Ungleichungsrestriktionen der Form ||Ax+ b||2 ≤ cTx+ d.Die zulässige Menge wird daher durch einen bzw. mehrere Lorentzkegel begrenzt (vgl.Abschnitt 2.4.1). Falls A = 0 ist, so liegt ein einfaches LP vor.• Semidefinite Programme (kurz SDP) stellen eine Verallgemeinerung der SOCP dar. Die

zulässige Menge wird durch die Schnittmenge der aus den positiv semidefiniten MatrizenF i mit i = 1, ...,m geformten verallgemeinerten Kegel beschrieben. Falls alle F i und GDiagonalmatrizen sind, so liegt ein LP vor.

Px

-c

(a) Geometrische Darstellung eines LP

P

x

f0(x)

D-

(b) Geometrische Darstellung eines QP

Abbildung 10: Die Abbildung stellt die Geometrie eines LP (a) und eines QP (b) dar. Die zulässige Mengehat bei beiden Programmen die Form eines Polyeders P. Da die Zielfunktion cTx eines LPlinear ist, ist jede Niveaufläche orthogonal zu c. Der optimale Punkt x ∈ P liegt so weitwie möglich in Richtung −c. Bei einem QP ist die Zielfunktion konvex quadratisch. Fallsdas Minimum der Zielfunktion nicht innerhalb von P liegt, so liegt der optimale Punktx auf einer begrenzenden Hyperebene, und zwar dort, wo der Gradient der Zielfunktionsenkrecht zu dieser Hyperebene steht (nach Boyd und Vandenberghe 2004).

Alle hier vorgestellten Programme sind Spezialfälle der konvexen Optimierung und können effi-zient mittels Innerer-Punkte-Verfahren gelöst werden. Für eine detailliertere Betrachtung konve-xer Programme mit Beispielen sei an dieser Stelle auf Boyd und Vandenberghe 2004, Kap. 4,hingewiesen.

2.4.4 Lösung konvexer Programme

In diesem Abschnitt wollen wir speziell auf das Barriere-Verfahren zur Lösung konvexer Pro-gramme eingehen. Das vorgestellte Barriere-Verfahren ist ein Innere-Punkte-Verfahren und dient


vornehmlich der Motivation bzw. Einführung solcher Verfahren. Deutlich bessere Eigenschaftenweisen so genannte „primal-duale Innere-Punkte-Verfahren“ auf, welche dem Barrieren-Verfahrenzwar ähnlich sind, aber einige Vorteile aufweisen, weshalb diese in den meisten effizienten Lö-sungsprogrammen wie bspw. „SeDuMi“ (vgl. Sturm 1999) verwendet werden. Für eine aus-führliche Einführung verweisen wir wieder auf das Buch Boyd und Vandenberghe (2004),Kap. 11.Innere-Punkte-Verfahren stellen eine Klasse von Algorithmen zur Lösung von Optimierungs-

aufgaben dar. Sie wurden zur Lösung linearer und quadratischer Programme entwickelt, siekönnen jedoch auch zur Lösung allgemeiner nicht linearer Programme und semidefiniter Pro-gramme eingesetzt werden. Im Vergleich zu den traditionelleren Simplex-Verfahren, zu denenbspw. die Active-Set-Methoden gehören, zeichnen sich Innere-Punkte-Verfahren vor allem durchbessere theoretische Eigenschaften und schnellere Konvergenz für sehr große dünnbesetzte Pro-bleme aus. Im Gegensatz zu Simplex-Verfahren, welche entlang der Kanten eines die zulässigMenge begrenzenden Polyeders die optimale Lösung suchen (vgl. Gill et al. 1981, S. 167 ff.),versuchen Innere-Punkte-Verfahren einen Pfad zur optimalen Lösung durch das „Innere“ des Po-lyeders zu finden, so dass Innere-Punkte-Verfahren in Polynomialzeit lösbar sind (vgl. Wright2005).Wir betrachten im Folgenden ein konvexes Optimierungsproblem, welches Ungleichungsrestrik-

tionen aufweist,

minimiere f0(x)

u.d.N. fi(x) ≤ 0, i = 1, ..., nAx = b ,

(2.36)

und nehmen an, dass für dieses Problem eine optimale Lösung x existiert. Den dazu gehörigenoptimalen Wert der Zielfunktion f0(x) bezeichnen wir als p.

Die Lagrange-duale Funktion

Der Grundgedanke der Lagrange-Dualität ist es, die Restriktionen eines Optimierungsproblemsdurch eine Erweiterung der Zielfunktion um eine gewichtete Summe von Bedingungsfunktionenzu berücksichtigen. Die zum generellen Minimierungsproblem (2.1) gehörende LagrangefunktionL : Rm ×Rn ×Rp → R lautet

L(x,λ,ν) = f0(x) +n∑i=1

λifi(x) +

p∑j=1

νjhj(x) (2.37)

mit den Lagrange-Multiplikatoren λi und νj , welche sich jeweils auf die i-te Ungleichungs- bzw. j-te Gleichungsrestriktion beziehen. Die Vektoren λ ∈ Rn und ν ∈ Rp ergänzen den Lösungsvektorx ∈ Rm mit dem erweiterten Definitionsbereich DL = D ×Rn ×Rp.Die Lagrange-duale Funktion g : Rn × Rp → R ist der minimale Wert der Lagrangefunktion

über x:

g(λ,ν) = infx∈D

L(x,λ,ν) = infx∈D

f0(x) +n∑i=1

λifi(x) +

p∑i=j

νjhj(x)

. (2.38)

Wenn die Lagrange-Funktion an einer Stelle x nach unten unbegrenzt ist, nimmt die dualeLagrange-Funktion den Wert −∞ an. Da die duale Lagrange-Funktion das punktweise Infinumvon affinen Funktionen von λ und ν ist, ist diese stets konkav3.

3Eine Funktion f(x) ist konkav, falls −f(x) konvex ist, also Bedingung (2.28) für −f(x) erfüllt wird.


Die duale Lagrange-Funktion liefert eine untere Grenze für den optimalen Wert p für eingenerelles Optimierungsproblem der Form (2.1), da für jedes λ � 0 und jedes ν

g(λ,ν) ≤ p (2.39)

gilt. Diese wichtige Eigenschaft ergibt sich durch den Umstand, dass für jeden zulässigen Punktx zum einen jeder Term λifi(x) ≤ 0 und zum anderen jeder Term νjhj(x) = 0 sein muss.Das duale Problem zum in diesem Zusammenhang genannten primalen Problem (2.1) lautet

maximiere g(λ,ν)

u.N. b. λ � 0 .(2.40)

Den optimalen Wert des dualen Problems bezeichnen wir mit d, welcher die beste untere Grenzefür den optimalen Wert des primären Problems p darstellt. Das Paar (λ,ν) wird als dual zulässigbezeichnet, wenn sowohl λ � 0 als auch g(λ,ν) > −∞ erfüllt sind und das Paar (λ, ν) wird alsdual optimal bezeichnet, wenn diese optimal für das duale Problem sind.Nach dem schwachen Dualitätssatz ist der optimale Wert d jeder dualen Lösung mindestens so

groß wie der Wert jeder primalen Lösung (vgl. Boyd und Vandenberghe 2004, S. 225). DieDifferenz p − d wird als Dualitätslücke bezeichnet. Falls die Differenz Null beträgt, dann liegtstarke Dualität vor und aus der Lösung des dualen Problems ergibt sich unmittelbar die Lösungdes primalen Problems.

KKT-Bedingungen

Jede optimale primale Lösung x und ihre duale Lösung (λ, ν), welche keine Dualitätslückeaufweisen, erfüllen stets die Bedingungen

fi(x) ≤ 0 , i = 1, ..., n (2.41)hj(x) = 0 , j = 1, ..., p (2.42)

λi ≥ 0 , i = 1, ..., n (2.43)

λifi(x) = 0 , i = 1, ..., n (2.44)

∇f(x) +∑n

i=1 λi∇fi(x) +∑p

j=1 νj∇hj(x) = 0 . (2.45)

Diese so genannten Karush-Kuhn-Tucker-Bedingungen (kurz KKT-Bedingungen) stellen einenotwendige Bedingung an die Optimalität einer Lösung eines nicht linearen Optimierungspro-blems dar (vgl. Boyd und Vandenberghe 2004, S. 243 f.). Falls ein konvexes Optimierungspro-blem vorliegt, so stellen die KKT-Bedingungen sogar hinreichende Bedingungen für eine optimaleLösung dar. Seien nun also zum einen sowohl die Zielfunktion f0 als auch die Ungleichungsre-striktionen fi konvex und zum anderen die Gleichungsrestriktionen hj affin, so dass ein konvexesOptimierungsproblem vorliegt, so sind die Punkte x, λ und ν, welche die KKT-Bedingungen desOptimierungsproblems erfüllen, stets auch die primal und dual optimalen Punkte ohne Duali-tätslücke.Betrachten wir die einzelnen Bedingungen etwas genauer: Die ersten beiden Bedingungen for-

dern, dass die Lösung x primal zulässig ist. Die vierte Bedingung wird als komplementäre Schlupf-bedingung bezeichnet: Falls die i-te Ungleichungsbedingung an einem optimalen Punkt x nichtaktiv ist, also fi(x) < 0 beträgt, dann ist der i-te optimale Lagrange-Multiplikator stets λi = 0.Falls sich jedoch die Lösung x am Rand der zulässigen Menge befindet mit fi(x) = 0, so beträgtdieser aufgrund der dritten Bedingung λi ≥ 0. Daher ist die Lagrange-Funktion (2.37) bei kon-vexen Optimierungsproblemen L(x, λ, ν) stets eine konvexe Funktion, da die Summe konvexerTerme stets eine konvexe Funktion ergibt. Die fünfte Bedingung fordert, dass der Gradient der


Lagrange-Funktion über x an der Stelle x Null ist, was wie bereits genannt, nur bei konvexenFunktionen eine hinreichende Bedingung für ein Optimum darstellt.

Die logarithmische Barrieren-Funktion

Unser Ziel ist es, ein durch Ungleichungen restringiertes Problem der Form (2.36) durch einProblem, welches lediglich Gleichungsrestriktionen aufweist, zu approximieren, so dass diesesbspw. mittels des Newton-Verfahren gelöst werden kann. Mittels der Indikatorfunktion

I(u) =

{0 fur u ≤ 0

∞ fur u > 0(2.46)

kann das Optimierungsproblem zu

minimiere f0(x) +∑n

i=1 I(fi(x))

u.d.N. Ax = b(2.47)

umgeschrieben werden. Hierbei bestraft die Indikatorfunktion Lösungen, welche die Unglei-chungsrestriktionen verletzten, innerhalb der Zielfunktion. Das umformulierte Problem besitztdann keine Ungleichungsrestriktionen mehr, jedoch ist die Zielfunktion nicht mehr differenzier-bar, wodurch das Newton-Verfahren nicht angewendet werden kann. Der Grundgedanke desBarrieren-Verfahrens ist es, die Indikatorfunktion I durch eine differenzierbare Funktion

It(u) = −(1/t) log(−u) (2.48)

zu approximieren. Die Funktion It ist konvex und wird ∞ für u > 0. In Abbildung 11 ist dieIndikatorfunktion I und deren Approximation It für verschiedene Werte von t dargestellt. Jegrößer t wird, desto exakter wird die Approximation.

−3 −2.5 −2 −1.5 −1 −0.5 0 0.5 1−5

0

5

10

u

I t(u)

Abbildung 11: Die gestrichelte Linie beschreibt die Indikatorfunktion I(u) und die durchgezogenen Linienbeschreiben It(u) = −(1/t) log(−u) für t = 0.5, t = 1 und t = 2. Je größer t ist, destobesser wird I(u) durch It(u) approximiert (nach Boyd und Vandenberghe 2004).

Mittels der so genannten logarithmischen Barriere-Funktion zum Problem (2.47)

φ(x) = −n∑i=1

log(−fi(x)) , (2.49)

welche über allen Punkten, die den Ungleichungsrestriktionen genügen, definiert ist, können wir


das ursprüngliche Problem durch

minimiere tf0(x) + φ(x)

u.d.N. Ax = b(2.50)

approximieren. In Abbildung 11 wurde bereits gezeigt, dass für t → ∞ die Approximation derIndikatorfunktion exakter wird. Jedoch weist die Hesse-Matrix der Zielfunktion für zu große t anden Grenzen der zulässigen Menge zu abrupte Änderungen auf, wodurch sich die Minimierungmittels des Newton-Verfahrens als schwierig erweist. Dieses Problem kann umgangen werden,indem das Problem (2.50) iterativ gelöst wird, indem in jeder Iteration der Parameter t vergrößertwird, und die Lösung aus der vorhergegangenen Iteration als Startpunkt im Newton-Verfahrenverwendet wird.

Der zentrale Pfad

Die Zielfunktion von Problem (2.50) sei nun differenzierbar, so dass das Problem grundsätzlichmittels des Newton-Verfahrens lösbar ist. Für ein t > 0 sei x∗t die Lösung des Problems desjeweiligen Iterationsschrittes.Als zentraler Pfad wird die Menge aller zentralen Punkte x∗t für t > 0 bezeichnet. Die zentralen

Punkte sind alle streng zulässig, erfüllen also zum einen Ax∗t = b sowie fi(x∗t ) < 0 und zumanderen existiert ein ν ∈ Rp, so dass die Zentralitätsbedingung

t∇f0(x∗t ) +∇φ(x∗t ) + ATν = 0 (2.51)

erfüllt wird.

Beispiel 2. Betrachten wir ein lineares Programm mit Ungleichungsrestriktionen:

minimiere cTx

u.d.N. Ax � b .(2.52)

Die logarithmische Barrieren-Funktion ist dann gegeben durch

φ(x) = −n∑i=1

log(−bi − aTi x) , (2.53)

wobei aTi und bi die Zeilen von A bzw. b sind. Mit dem Gradienten der Barrieren-Funktion

∇φ(x) =n∑i=1

1

bi − aTi xai (2.54)

lautet die Zentralitätsbedingung

tc+

n∑i=1

1

bi − aTi xai = tc+ Ad = 0 (2.55)

mit d ∈ Rn und den Elementen di = 1/(bi − aTi x).

Die Zentralitätsbedingung aus Beispiel 2 kann anschaulich interpretiert werden: Der Gradient∇φ(x∗t ) am zentralen Punkt x∗t muss parallel zum Vektor c sein, damit die Addition der beidenTerme den Nullvektor ergibt. Das heißt, dass die Hyperebene cTx∗t die Tangente zur Niveaulinievon φ(x) an der Stelle x∗t ist. Abbildung 12 verdeutlicht grafisch den Zusammenhang zwischendem zentralen Pfad und der Zentralitätsbedingung des im Beispiel 2 dargestellten linearen Pro-


gramms mit n = 6 Hyperebenen und einem m = 2 dimensionalen Lösungsraum.

xxt=10

c

Abbildung 12: Darstellung des zentralen Pfades eines LP mit n = 6 Hyperebenen, welche den m = 2dimensionalen Lösungsraum begrenzen. Die gestrichelten Linien stellen die Niveauliniender logartihmischen Barrieren-Funktion φ(x) dar. Der zentrale Pfad konvergiert zum opti-malen Punkt x für t→∞. Zudem ist der zentrale Punkt, welcher sich für t = 10 auf demzentralen Pfad ergibt, dargestellt. Die Zentralitätsbedingung lässt sich in diesem Beispielgeometrisch interpretieren: Die Hyperebene cTx∗ ist stets die Tangente zu der Niveaulinievon φ(x) durch x, wie es hier für t = 10 dargestellt ist (nach Boyd und Vandenberghe2004).

Aus der Zentralitätsbedingung (2.51) kann eine wichtige Eigenschaft des zentralen Pfades ab-geleitet werden: Jeder zentrale Punkt xt besitzt einen dualen zulässigen Punkt und somit eineuntere Grenze für p. Für ein dual zulässiges Paar (λt, νt) definieren wir ausgehend von denKKT-Bedingungen (2.41) bis (2.45) und dem aktuellem t die weicheren Bedingungen

λi,t = − 1

tfi(xt)und νt = νt , (2.56)

welche mit t→∞ den originalen KKT-Bedingungen entsprechen. Da die Lagrangefunktion

L(x,λ,ν) = f0(x) +n∑i=1

λifi(x) + νT(Ax− b) (2.57)

durch xt mit dem dual zulässigen Paar λ = λ und ν = ν minimal ist, ist die duale Funktionfinit und liefert

g(λt, νt) = f0(xt) +n∑i=1

λi,tfi(xt) + νTt (Axt − b) (2.58)

= f0(xt)− n/t . (2.59)

Die Dualitätslücke, welche sich mit der Lösung xt und dem dual zulässigen Paar (λ, ν) ergibt,beträgt demnach n/t.

Das Barrieren-Verfahren

Eine Lösung xt ist demnach n/t-supoptimal. Mit t → ∞ konvergiert die Lösung xt zu einemoptimalen Punkt, welcher keine Dualitätslücke aufweist. Für t = m/ε erhalten wir eine Lösung,welche bis auf die Größenordnung von ε exakt ist:

minimiere (m/ε)f0(x) + φ(x)

u.d.N. Ax = b .(2.60)


Diese Formulierung erlaubt es uns, die optimale Lösung x des Problems mit der maximalenAbweichung von der richtigen Lösung ε mittels des Newton-Verfahrens iterativ zu bestimmen.Der Newton-Schritt ∆x und die dazugehörigen dualen Variable ν ergeben sich dann durch daslineare Gleichungssystem[

∇2f0(x) +∇2φ(x) AT

A 0

] [∆xν

]= −

[∇f0(x) +∇φ(x)

0

]. (2.61)

Dieses Verfahren wurde in den 60er Jahren unter dem Namen „sequential unconstrained mini-mization technique“ vorgestellt (vgl. Fiacco und McCormick 1990, S. 4 ff.), heute wird diesesVerfahren jedoch meist als Barrieren-Verfahren bezeichnet. Im Algorithmus 2 sind die Grundzügedieses Verfahrens dargestellt.

Algorithmus 2 : Das Barrieren-Verfahren.

Daten :x(0) . . . streng zulässiger Punktvektort(0) > 0 . . . Glattheit der Barrieren-Funktionµ > 1 . . . Konvergenzgeschwindigkeitε > 0 . . . Toleranzmaxiter . . . Maximale Anzahl an Iterationen


// Bestimmung des zentralen Punktes2

Bestimme xt durch Lösung von Problem 2.60 mit Startpunkt x;3

// Setze neue Lösung4

x := xt;5

// Abbruchbedingung6

if m/t < ε then7

return x;8

end9

// Vergrößere t10

t := µt11

end12

return x;13

Die Wahl des Parameters µ wirkt sich direkt auf das Konvergenzverhalten aus. Falls µ kleinist (also nahe bei 1 liegt), dann vergrößert sich t in jeder Iteration nur um einen kleinen Betrag.Einerseits liegt dann für das geringfügig geänderte Problem ein guter Startpunkt für das Newton-Verfahren vor, welches folglich schnell konvergiert, andererseits wird die Dualitätslücke wegendes langsamen Konvergenzverhaltens von t nur sehr langsam reduziert, wodurch viele Lösungenauf dem zentralen Pfad bestimmt werden müssen. Falls ein großes µ gewählt wird, liegt diegegenteilige Situation vor.Die im Abschnitt 2.4.3 eingeführten linearen und quadratischen Programme weisen die Form

von (2.36) auf. Optimierungsprobleme wie SOCPs oder SDPs erfüllen für generalisierte Unglei-chungsrestriktionen i. a. nicht die erforderliche Form. Das dargestellte Barrieren-Verfahren kannjedoch auf Programme mit generalisierten Ungleichungen der Form fi(x) �Ki 0, i = 1, ..., n er-weitert werden, indem der Logarithmus in der logarithmischen Barriere-Funktion (2.49) durch


einen verallgemeinerten Logarithmus ψ für einen eigentlichen Kegel K ersetzt wird:

φ(x) = −n∑i=1

ψi(−fi(x)). (2.62)

Der verallgemeinerte Logarithmus ψ : Rq → R für K ⊆ Rq muss die folgenden Eigenschaftenaufweisen: Zum einen muss ψ streng konkav, geschlossen und zweimal differenzierbar sein undzum anderen muss eine Konstante θ > 0 existieren, so dass für alle y �K 0 und alle s > 0

ψ(sy) = ψ(y) + φ log s (2.63)

gilt. Somit verhält sich ψ wie eine Logarithmusfunktion auf jedem beliebigen Strahl durch denKegel K.

Bestimmung einer zulässigen Lösung

Das Barrieren-Verfahren benötigt einen streng zulässigen Punkt x(0) als Startpunkt. Falls solchein Punkt nicht bekannt ist, muss eine vorausgehende Bestimmung erfolgen, welche als Phase Ibezeichnet wird. Ein in der Phase I gefundener zulässiger Punkt wird dann als Startpunkt x(0)

bspw. im vorgestellten Barrieren-Verfahren verwendet, welches dann als Phase II bezeichnet wird.Es gibt mehrere verschiedene Phase I-Verfahren, welche unterschiedliche Eigenschaften aufwei-

sen. Im Folgenden werden wir ein einfaches Phase I-Verfahren für konvexe Optimierungsproblemevorstellen, bei welchen die Restriktionen

fi(x) ≤ 0, i = 1, ..., n und Ax = b (2.64)

in x ∈ R konvex bzw. affin sind.Das Ziel ist es einen streng zulässigen Punkt zu finden, welcher den Restriktionen genügt.

Unter dem so genannte Phase I-Optimierungsproblem

minimierex, s

s

u. d.N. fi(x) ≤ s, i = 1, ..., n

Ax = b

(2.65)

kann die Variable s als eine maximale Grenze für die Unzulässigkeit eines Punktes x gegen-über den Ungleichungsrestriktionen interpretiert werden, wobei es das Ziel ist, eine maximaleUnzulässigkeit kleiner Null zu erreichen. Das vorliegende Optimierungsproblem ist stets strengzulässig, wenn wir für x einen Startpunkt x(0) wählen, welcher die Gleichungsrestriktion Ax = berfüllt, und für s einen Wert größer maxni=1 fi(x

(0)) verwenden. Daher ist es stets möglich dasBarriere-Verfahren zur Lösung des Problems zu verwenden.Wir definieren s als den gefundenen optimalenWert des konvexen Phase I-Optimierungsproblems

(2.65). Ausgehend vom Vorzeichen des minimalen Wertes s können drei Fälle unterschieden wer-den. Falls s < 0, dann existiert eine streng zulässige Lösung, welche die Bedingungen (2.64)erfüllt. Sobald dies eintritt, kann die Phase I-Optimierung abgebrochen werden. Falls s > 0,dann existiert keine zulässige Lösung, welche den Restriktionen (2.64) genügt. Für den Fall, dasss = 0 ist, existiert eine zulässige Lösung, die jedoch nicht streng zulässig ist.Dieses Vorgehen kann auch zur Lösung so genannter Zulässigkeitsprobleme angewendet werden.

Bei Zulässigkeitsproblemen wird geprüft, ob unter gewissen Restriktionen eine zulässige Mengeexistiert, d. h. ob überhaupt ein Punkt x existiert, unter welchem s < 0 ist.

2.5. Quasikonvexe Optimierung 25

Primal-duale Innere-Punkte-Verfahren

Das Barriere-Verfahren funktioniert in der Regel nur bei kleinen Optimierungsproblemen zu-verlässig, bei welchen eine gute Näherung x vorliegt und bei welchen eine nicht zu niedrigeToleranz ε gefordert wird. Aufgrund dieser einschränkenden Eigenschaften wird dieses Verfah-ren jedoch meist nicht verwendet. So genannte primal-duale Innere-Punkte-Verfahren sind demBarrieren-Verfahren sehr ähnlich, weisen nach Boyd und Vandenberghe (2004), S. 609, jedochdie folgenden Unterschiede auf:• Es wird nur eine Iterationsschleife benötigt. Mittels des Newton-Schrittes werden sowohl

die primalen als auch die dualen Größen verbessert.• Die Bestimmung der Abstiegsrichtung erfolgt durch Anwendung des Newton-Verfahren

auf modifizierte KKT-Bedingungsgleichungen, welche die primalen und dualen Residuenberücksichtigen, so dass eine so genannte primal-duale Suchrichtung bestimmt wird.• Die iterativ bestimmten primalen und dualen Schätzgrößen sind bis zur Konvergenzphase

nicht zwangsläufig zulässig. Daher kann lediglich eine ersatzweise Dualitätslücke berechnetwerden, welche für zulässige Lösungen jedoch der tatsächlichen Dualitätslücke entspricht.

Für einige Standardproblemklassen, wie u. a. die in Abschnitt 2.4.3 dargestellten Spezialfälle, wei-sen maßgeschneiderte primal-duale Innere-Punkte-Verfahren wesentlich effizientere Eigenschaf-ten als das Barrieren-Verfahren auf. Ein weiterer Vorteil dieser Verfahren ist, dass sie auch zurLösung von Optimierungsaufgaben angewendet werden können, die keine streng zulässigen Lö-sungen fordern. Auf eine detailliertere Beschreibung solcher Verfahren wollen wir an dieser Stelleverzichten und wieder auf das Buch Boyd und Vandenberghe (2004), S. 609 ff., verweisen.Primal-duale Innere-Punkte-Verfahren sind in einigen frei zugänglichen Software-Paketen im-

plementiert worden. Im Rahmen dieser Arbeit verwenden wir zur Lösung konvexer Optimierungs-probleme das Open-Source-Softwarepaket SeDuMi4, mit welchem konvexe Optimierungsproble-me über symmetrische Kegel gelöst werden können. Hierbei werden die jeweiligen Eigenschaftenlinearer, quadratischer, kegelförmiger oder semidefiniter Restriktionen oder der Kombinationdieser im Lösungsalgorithmus zur effizienten Lösung ausgenutzt (vgl. Sturm 1999). Die darge-stellten Optimierungsprobleme (2.32) bis (2.35) sind alle mit SeDuMi lösbar. SeDuMi bieteteine Schnittstelle zu MATLAB und zeichnet sich durch eine effiziente Lösung dünnbesetzterOptimierungsprobleme mit vielen Unbekannten aus (vgl. Sturm 2002).

2.5 Quasikonvexe Optimierung

Falls die zu minimierende Zielfunktion nicht konvex, sondern lediglich quasikonvex ist, so liegtein quasikonvexes Optimierungsproblem vor. Die Standardform eines quasikonvexen Optimie-rungsproblems lautet

minimiere f0(x)

u.d.N. fi(x) ≤ 0, i = 1, ..., nAx = b ,

(2.66)

wobei die Zielfunktion f0 quasikonvex und jede Ungleichungsrestriktion fi konvex ist.In diesem Abschnitt werden wir zum einen die Eigenschaften quasikonvexer Funktionen darstel-

len und zum anderen zeigen, wie quasikonvexe Optimierungsprobleme stets auf eine Reihe kon-vexer Optimierungsprobleme reduziert werden können, welche dann mit den in Abschnitt 2.4.4dargestellten Verfahren gelöst werden können.

4Projekt-Webseite: http://sedumi.ie.lehigh.edu; letzter Zugriff am 15. November 2011.


2.5.1 Quasi- und pseudokonvexe Funkionen

Eine Subniveaumenge Sα einer Funktion f : D ⊆ Rm → R ist definiert als

Sα = {x ∈ D | f(x) ≤ α} . (2.67)

Die Subniveaumenge konvexer Funktionen bildet für jedes beliebige α aufgrund der Krümmungs-eigenschaften konvexer Funktionen stets eine konvexe Menge. Der Umkehrschluss, dass Funktio-nen, deren Subniveaumengen für jedes α konvex sind, somit auch konvexe Funktionen sind, istnicht möglich. Jedoch weisen solche Funktionen wie konvexe Funktionen lediglich ein Minimumauf. In Abbildung 13 sind drei verschiedene Funktionen mit ihren Subniveaumengen dargestellt.

{ x | fi(x) < a } x

fi(x)

a

(a) Sα einer konvexen Funktion.

{ x | fi(x) < a } x

fi(x)

a

(b) quasikonvexe Funktion

{ x | fi(x) < a } x

fi(x)

a

(c) nicht-konvexe Funktion

Abbildung 13: In (a) ist die Subniveumenge einer konvexen, in (b) einer quasikonvexen und in (c) einerbeliebigen Funktion mit zwei Minima dargestellt. Die Subniveaumenge Sα einer konvexenoder quasikonvexen Funktion ist stets konvex.

Eine Funktion f : D ⊆ Rm → R wird quasikonvex genannt, falls die Subniveaumenge

Sα = {x ∈ D | f(x) ≤ α} (2.68)

für alle α ∈ R konvex ist. Quasikonvexe Funktionen sind eine Verallgemeinerung konvexer Funk-tionen. Sie dürfen negative Krümmungen aufweisen, besitzen jedoch stets nur ein Minimum.Alternativ kann eine quasikonvexe Funktion durch eine Variation der so genannten Jensenschen

Ungleichung charakterisiert werden: Eine Funktion f : D ⊆ Rm → R ist nur dann quasikonvex,wenn D konvex ist und

f(αx+ (1− α)y) ≤ max {f(x), f(y)} mit 0 ≤ α ≤ 1 (2.69)

für alle x,y ∈ D gilt (vgl. Boyd und Vandenberghe 2004, S. 98). Anschaulich fordert dieUngleichung, dass einer der Funktionswerte der Endpunkte eines beliebigen Geradenabschnittesstets größer ist, als alle Funktionswerte entlang dieses Geradenabschnittes. In Abbildung 14 sindbeide Definitionsansätze grafisch dargestellt.Da quasikonvexe Funktionen mehrere stationäre Punkte aufweisen können (z. B. an Sattelpunk-

ten), ist die für konvexe Optimierungsprobleme hinreichende Optimalitätsbedingung ∇f(x) = 0für quasikonvexe Optimierungsprobleme nicht hinreichend. Eine Lösung x aus der zulässigenMenge D eines quasikonvexen Optimierungsproblems ist optimal, falls

∇f(x)T(y − x) > 0 fur alle y ∈ D\x (2.70)

gilt. Diese Definition umschließt jedoch nicht jeden optimalen Punkt, da sie verlangt, dass derGradient von f0 nicht Null werden darf. Im Gegensatz zum konvexen Fall ist ∇f0(x) = 0 somit


a

Sa={ f (x)< a}

f (x)

x

max{ f (x1), f (x2)}

xx1 x2

f (x)

Abbildung 14: Grafische Darstellung der beiden Definitionen (2.68) (links) und (2.69) (rechts) zur Über-prüfung der Konvexität.

keine hinreichende Bedingung. Ein Gradientenabstiegsverfahren konvergiert daher evtl. nichtzum globalen Minimum.Wir wollen zusätzlich pseudokonvexe Funktionen einführen: Eine Funktion f : D ⊆ Rm → R

ist pseudokonvex falls

∇f(x)T(y − x) ≥ 0 ⇒ f(y) ≥ f(x) (2.71)

für alle x,y ∈ D gilt. Dies bedeutet, dass, falls an einer Stelle x ein stationärer Punkt mit∇f(x) = 0 vorliegt, an keiner Stelle anderen Stelle y der Funktionswert kleiner ist als f(x).Ein stationärer Punkt einer pseudokonvexen Funktion entspricht demnach stets dem globalenMinimum. Dies ermöglicht die Anwendung von Gradientenabstiegsverfahren zur Bestimmungdes globalen Minimums.Konvexe Funktionen sind stets auch pseudokonvexe Funktionen. Jedoch ist die Hessematrix

einer pseudokonvexen Funktion nicht zwangsläufig positiv (semi)definit, so dass ein Newton-Schritt in die falsche Richtung laufen kann. In Abbildung 15(a) ist eine quasikonvexe, jedoch nichtpseudokonvexe Funktion dargestellt und in Abbildung 15(b) ist eine pseudokonvexe Funktion,jedoch nicht konvexe Funktion abgebildet.

(a) Eine quasikonvexe, aber nichtpseudokonvexe Funktion

(b) Eine pseudokonvexe, aber nichtkonvexe Funktion

Abbildung 15: Darstellung einer quasikonvexen Funktion, die jedoch nicht pseudokonvex ist, in (a) undDarstellung einer pseudokonvexen Funktion, die nicht konvex ist, in (b). Die Abbildungenwurden aus Olsson und Kahl (2010) übernommen.


2.5.2 Lösung quasikonvexer Programme

Ein quasikonvexes Optimierungsproblem kann im Gegensatz zu konvexen Optimierungspro-blemen mehrere lokal optimale Lösungen aufweisen, die nicht global optimal sind. Ein Abstiegs-verfahren führt somit nicht garantiert zum globalen Minimum. In diesem Abschnitt werden wirzeigen, wie ein quasikonvexes Optimierungsproblem auf die Lösung einer Reihe konvexer Zuläs-sigkeitsprobleme reduziert werden kann, welche eine global optimale Lösung garantieren.Zunächst definieren wir hierzu eine beliebige konvexe Funktion φt : Rm → R, welche die

Bedingung

φt(x) = f0(x)− t ≤ 0 (2.72)

erfüllt und in t nicht anwächst, so dass stets φs(x) ≤ φt(x) mit s > t gilt. Es sei p der Funktions-wert der optimalen Lösung x des Optimierungsproblems (2.66). Falls das Zulässigkeitsproblem

finde x

u.d.N. φt(x) ≤ 0fi(x) ≤ 0, i = 1, ..., nAx = b

(2.73)

eine zulässige Lösung besitzt, dann ist p ≤ t. Falls das Zulässigkeitsproblem jedoch unzulässig ist,dann können wir darauf schließen, dass p > t ist. Durch Lösen des konvexen Zulässigkeitsproblems(2.73) (vgl. Phase I-Verfahren in Abschnitt 2.4.4 auf Seite 24) können wir dies für beliebige Wertefür t überprüfen.Ein quasikonvexes Optimierungsproblems der Form (2.66) kann nach diesem Ausschlussverfah-

ren innerhalb eines Bisektionsverfahren gelöst werden (vgl. Algorithmus 3). Grundsätzlich findenBisektionsverfahren immer dann Anwendung, wenn ein Problem gelöst werden kann, indem esin zwei etwa gleichgroße Teilprobleme zerlegt wird, die dann einzeln für sich behandelt werdenkönnen. Zur Anwendung dieses Verfahrens muss ein Intervall [l, u] bekannt sein, welches denoptimalen Wert p enthält. In jedem Bisektionsschritt überprüfen wir, ob eine zulässige Lösungfür t = (l + u)/2 existiert. Falls das Problem zulässig ist, verwenden wir die untere Hälfte alsneues Intervall und falls das Problem unzulässig ist, verwenden wir die obere Hälfte. In jedemBisektionsschritt wird daher das Intervall, in welchem sich p befindet, um die Hälfte verkleinert,bis der optimale Wert bis auf eine vorgegebene Toleranz ε genau bestimmt ist.Die Länge eines Intervalls nach k Iterationen beträgt (u− l)2−k. Die Anzahl der notwendigen

Iterationen für eine vorgegebenes ε beträgt daher exakt dlog2((u− l)/ε)e.


Algorithmus 3 : Bisektionsverfahren für eine quasikonvexe Optimierung.

Daten :[l, u] . . . obere und untere Grenze für Intervall, welches p enthältε . . . Toleranz mit ε > 0

maxiter = dlog2((u− l)/ε)e;1


t := (l + u)/2;3

Bestimme eine Lösung x des Zulässigkeitsproblems (2.73);4

if zulässige Lösung existiert then5

x = x;6

u := t;7

else8

l := t;9

end10

end11

return x12

31

3. Mehrbildgeometrie unter der L∞-Norm

Üblicherweise werden überbestimmte Probleme der Photogrammetrie mit Verfahren gelöst,welche die Lösung liefern, unter welcher die Residuen zu den Beobachtungen unter der L2-Normminimal sind. Falls die Modellabweichungen unabhängig und normalverteilt sind, stellt dieseLösung eines Optimierungsproblems die Maximum-Likelihood-Schätzung mit minimaler Varianzdar (vgl. Abschnitt 2.2).In diesem Abschnitt werden wir fünf Aufgabenstellungen der Photogrammetrie betrachten,

welche mittels Methoden der konvexen Optimierung durch Minimierung der L∞-Norm gelöstwerden können. Speziell werden wir zunächst drei Optimierungsprobleme betrachten, welcheinnerhalb eines Bisektionsverfahrens gelöst werden können: In Abschnitt 3.1 werden wir denräumlichen Vorwärtsschnitt darstellen und zeigen, warum unter der L2-Norm mehrere lokaleMinima existieren können und unter der L∞-Norm stets nur ein globales Minimum existiert.Wir werden ein Lösungsverfahren ausführlich darstellen, welches die optimale Lösung für dasL∞-Optimierungsproblem garantiert. Dieses Verfahren kann zudem zur Lösung einer Bündel-ausgleichung verwendet werden, wenn die Rotationsmatrizen der äußeren Orientierung der Ka-meras bekannt sind, was wir in Abschnitt 3.2 ausführen werden. Anschließend werden wir inAbschnitt 3.3 die Homographie-Schätzung betrachten und zeigen, dass dieses Verfahren ebenfallszur Schätzung von Transformationen verwendet werden kann. Für die genannten drei Problemewerden wir in Abschnitt 3.4 ein Verfahren darstellen, welches ebenfalls mittels Methoden derkonvexen Optimierung zur Ausreißerdetektion verwendet werden kann.Falls die rotatorische Orientierung der Kameras nicht bekannt ist, können die entsprechen-

de Rotationsmatrizen in einem so genannten „Branch-and-Bound-Verfahren“ bestimmt werden,welches in Abschnitt 3.5 beschrieben ist. Durch Anwendung dieses Verfahrens, kann eine Lö-sung für den räumlichen Rückwärtsschnitt und die relative Orientierung gefunden werden, unterwelcher die L∞-Norm minimal ist. Das Verfahren zur Lösung des räumlichen Rückwärtsschnittswird in Abschnitt 3.6 und das Verfahren zur Lösung der relativen Orientierung in Abschnitt 3.7dargestellt.

3.1 Der räumliche Vorwärtsschnitt

Eine perspektivisch abbildende Kamera kann als eine lineare Abbildung P3 → P2 vom pro-jektiven Objektraum in die projektive Bildebene modelliert werden. Im Folgenden seien ein SatzProjektionsmatrizen Pj von j = 1, ..., J Kameras bzw. Kamerastandpunkten gegeben, welcheimplizit die innere und äußere Orientierung beinhalten

Pj = KjRj [I 3| −Zj ] (3.1)

mit der Kalibriermatrix Kj , der Rotationsmatrix Rj und dem Translationsvektor Zj . Ein Ob-jektpunkt U = [U ;V ;W ; 1] sei durch N Bildpunkte uj = [uj , vj , 1] auf den Bildebenen derKameras Pj beobachtet worden. Der Abbildungsvorgang eines Objektpunktes als Bildpunkt aufder Bildebene kann durch die Kollinearitätsgleichung

λjuj = PjU (3.2)

modelliert werden, wobei der Skalar λj die freie Skalierung im projektiven Raum repräsentiert.Beim räumlichen Vorwärtsschnitt werden mittels vollständig orientierter Kameras, d. h. dass die

Projektionsmatrizen Pj bekannt sind, die unbekannten 3D-Koordinaten eines in mindestens zwei

32 3. Mehrbildgeometrie unter der L∞-Norm

Bildern beobachteten Objektpunktes U bestimmt. Würde ein Objektpunkte zum einen fehlerfreials Bildpunkt abgebildet und zum anderen die Position im Bild fehlerfrei identifiziert werdenkönnen, dann könnten die 3D-Koordinaten eines Objektpunktes einfach durch die Verschneidungder aus den korrespondierenden Bildpunkten abgeleiteten Raumstrahlen erfolgen. Da sowohl diephysikalische Abbildung als auch die Beobachtung eines Bildpunktes gewissen Unsicherheitenunterliegen, schneiden sich die korrespondierenden Raumstrahlen bei bereits zwei Kameras imAllgemeinen jedoch nicht (vgl. Abbildung 16(a)).

P1

P2

u1

u2

u3

P3

(a) Unsichere Raumstrahlen

P1 P3

P2

u1

u1

U

d1

u2

u2

d2

u3

u3d3

(b) Optimale Lösung

Abbildung 16: Darstellung des räumlichen Vorwärtsschnitts mit drei Kameras: (a) Die Raumstrahlen,welche aus den beobachteten Bildpunkten uj eines Objektpunktes U und den bekanntenProjektionsmatrizen Pj abgeleitet werden können, schneiden sich bei bereits zwei Kamerasi. a. nicht in einem Punkt; (b) Eine unter gewissen Optimalitätskriterien beste Lösung Uerzeugt die Residuen dj zwischen uj und der Rückprojektion uj .

3.1.1 Die Kostenfunktion

Aus diesem Grund ist es notwendig einen Objektpunkt U zu finden, welcher „möglichst nahe“an die beobachteten Bildpunkte uj projiziert wird. Nähe wird hierbei meist im Sinne von Kostendefiniert, welche minimal sein sollen. Die unter einer Lösung U anfallenden Kosten ergeben sichdurch die Länge eines Residuenvektors r = [r1, r2, ..., rN ]T unter einer Metrik. Die einzelnenResiduen rj des Residuenvektors können bspw. durch die Residuumsfunktion in der Bildebene

Rj(x) = d( PjU,uj ) = rj (3.3)

beschrieben werden, wobei d( ·, · ) die euklidische Distanz zwischen zwei Bildpunkten zurückgibt(vgl. Abbildung (b)). Der beim räumlichen Vorwärtsschnitt zu bestimmende Parametervektorx beinhaltet im Folgenden die euklidischen Koordinaten des unbekannten Objektpunktes U =[x; 1]. Die Residuumsfunktion einer perspektivisch abbildenden Kamera kann dann formuliert

3.1. Der räumliche Vorwärtsschnitt 33

werden durch

Rj(x) =

√√√√(pT1jU

pT3jU− uj

)2

+

(pT

2jU

pT3jU− vj

)2

(3.4)

=

√√√√((pT1j − ujpT

3j)U

pT3jU

)2

+

((pT

2j − vjpT3j)U

pT3jU

)2

(3.5)

=

√√√√((pT1j − ujpT3j)x+ p1j − ujp3j

pT3jx+ p3j

)2

+

((pT2j − vjpT3j)x+ p2j − vjp3j

pT3jx+ p3j

)2

(3.6)

mit der 3×4-Projektionsmatrix

Pj =

pT1j

pT2j

pT3j

=

pT1j p1j

pT2j p2j

pT3j p3j

.Die Form in Gleichung (3.6) kann in die kompaktere Form

Rj(x) =||Ajx+ bj ||2cTj x+ dj

(3.7)

überführt werden mit

Aj2×3

=

[pT1j − ujpT3jpT2j − vjpT3j

], bj

2×1

=

[p1j − ujp3j

p2j − vjp3j

], cTj

1×3

= pT3j und dj1×1

= p3j .

Die Chiralität eines Objektpunktes zu der Bildebene einer Kamera kann mittels der BedingungcTj x+dj > 0 berücksichtigt werden5, sodass sich eine zulässige Lösung vor den Kameras befindenmuss. Die Gleichung (3.7) beschreibt dann die Mantelfläche eines spitzen Lorentzkegels (vgl.Abschnitt 2.4.1).Die Ungleichung ||Ajx + bj ||2 ≤ Rj(x)(cTj x + dj) definiert geometrisch einen Second-order

Cone im dreidimensionalen Raum. Der Kegel steht mit der Spitze auf dem Projektionszentrumder Kamera j und öffnet sich aufgrund der Chiralitätsbedingung nur in Richtung der Bildebene,so dass ein echter konvexer Kegel vorliegt. Der Kegel schneidet die Bildebene mit dem RadiusRj(x) um den beobachteten Bildpunkt uj (vgl. Abbildung 17).Da sich die Residuumsfunktion Rj(x) aufgrund ihres dreidimensionalen Definitionsbereichs

nicht für alle x darstellen lässt, werden wir einen beliebigen Punkt x(t) = x0 + t∆x betrachten,welcher sich entlang einer geraden Linie vor einer Kamera bewegt. Wir erhalten dann einen ein-dimensionalen Querschnitt der Funktion, welcher durch die Variable t parametrisiert ist. Bewegtsich der 3D-Punkt x(t) entlang einer geraden Linie, die nicht durch das Projektionszentrumführt, so wandert sein Bildpunkt auch auf einer geraden Linie im Bild (vgl. Abbildung 18(a)).Der Bildpunkt wird der Beobachtung ui näher kommen und sich ab einem gewissen Punkt wiederentfernen. Die Residuumsfunktion Rj(t) hat nach (3.5) die Form

Rj(t) =

√(at+ b)2 + (ct+ d)2

(et+ g)2. (3.8)

5Hierzu muss die Projektionsmatrix Pj dermaßen normiert sein, dass die Determinante der linksseitigen 3×3-Blockmatrix von Pj positiv ist.


(a) Das Residuum rj als Radius eines Kreises in derBildebene um den beobachteten Bildpunkt uj .

(b) Die Mantelfläche des durch das Residuum rjaufgespannten Kegels zweiter Ordnung.

Abbildung 17: Darstellung des Residuums rj (a), welches den Radius in der Bildebene beschreibt, mitwelchem ein Kegel zweiter Ordnung (b) aufgespannt wird.

Die Funktion wird unendlich auf der Bildebene bei t = −g/e und ist asymptotisch zu (a2 +c2)/g2 für t → ∞. In Abbildung 18(b) ist der Graph für solch eine Funktion mit t > −g/edargestellt. Es ist zu erkennen, dass Rj(t) und somit auch Rj(x) nicht konvex sind, jedochbesitzt die Funktion nur ein einziges Minimum, wenn der Definitionsbereich auf Objektpunktevor der Kamera begrenzt wird.

x(t) = x0+tDx

u

u

r

(a) Bewegung eines Objektpunktes auf einerRaumgeraden und ihre Abbildung auf der Bildebene.

0 1 2 3 4 5 6 7 80

0.5

1

1.5

2

2.5

3

t

Rj(t)

(b) Die Residuumsfunktion Rj(t) als eindimensionalerQuerschnitt durch Rj(x).

Abbildung 18: (a): Bei einer geradentreu abbildenden Kamera wird eine Raumgerade als Gerade auf derBildebene abgebildet; (b): Die dargestellte Funktion ist Rj(t) =

((t− 1)2 + 1/6

)/(1/3t2).

Die Residuumsfunktion besitzt vor der Kamera stets nur ein einziges Minimum, ist nichtkonvex, aber besitzt stets die Eigenschaften einer pseudokonvexen Funktion (vgl. Olssonund Kahl 2010).

Jede Lp-Norm stellt eine Metrik dar, welche invariant gegenüber projektiven Transformatio-nen im Objektsystem und Ähnlichkeitstransformationen in den Bildebenen ist. Im Folgendenwerden wir die Lösung des räumlichen Vorwärtsschnitts unter Minimierung der L2- und derL∞-Norm betrachten. Da die Lösung invariant gegenüber den oben genannten Transformationenist, müssen die Bildkoordinaten nicht normiert werden, wie es bei allen algebraischen Metho-den notwendig ist. Bei diesen werden algebraische Kostenfunktionen minimiert, welche zwar dasProblem vereinfachen können, deren Lösung jedoch keine geometrische oder statistische Bedeu-tung hat. In Anhang A wird aufgezeigt, warum diese linearen Verfahren nicht zuverlässig sind.Unter diese Verfahren fällt auch die häufig bei zwei Bildern angewendete geometrische Lösung,bei welcher derjenige Punkt gesucht wird, welcher in der Mitte der kürzesten Verbindung beider


Raumstrahlen liegt. Die statistische Bedeutung einer Schätzgröße, unter welcher die L2- oder dieL∞-Norm von r minimal ist, wurde bereits in Abschnitt 2.2 genannt und ist daher Lösungenanderer Verfahren i. a. vorzuziehen.

Mehrere Minima in der L2-Kostenfunktion, ein einziges in der L∞-Kostenfunktion

Üblicherweise wird in diesem Kontext „möglichst nahe“ im Sinne einer kleinsten-Quadrate Lö-sung interpretiert, da im Falle unabhängiger, normalverteilter Modellabweichungen diese derMaximum-Likelihood Lösung mit minimaler Varianz entspricht. Die zu minimierende Kosten-funktion ergibt sich dann durch die L2-Norm des Residuenvektors

f0(x) = ||r||2 =

N∑j=1

Rj(x)2

1/2

. (3.9)

Wie wir in Abbildung 18 gesehen haben, ist die Residuumsfunktion nicht konvex, jedoch istdiese stets pseudokonvex, wie es durch Olsson und Kahl (2010) bewiesen wurde. Die Sum-me konvexer Funktionen liefert als Ergebnis wieder eine konvexe Funktion mit einem Minimum(vgl. Boyd und Vandenberghe 2004, S. 79). Pseudokonvexität hingegen bleibt unter der Sum-me pseudokonvexer Funktionen nicht erhalten, so dass die L2-Kostenfunktion mehrere Minimabesitzen kann (vgl. Abbildung 19(b)).Die Zielfunktion unter der L∞-Norm ergibt sich durch das punktweise Maximum jeder einzelnen

Residuumsfunktion

f0(x) = ||r||∞ =N

maxj=1

Rj(x) . (3.10)

Das punktweise Maximum quasikonvexer (also auch pseudokonvexer) Funktionen ergibt stetswieder eine quasikonvexe Funktion (vgl. Boyd und Vandenberghe 2004, S. 101 f.). In Abbil-dung 19(c) wird diese Eigenschaft an einem Beispiel deutlich, bei welchem die L2-Kostenfunktionzwei Minima besitzt.

t

R1(t) R2(t)

(a) Zwei pseudokonvexeResiduumsfunktionen.

R12(t)+R2

2(t)

t

R1(t) R2(t)

(b) Die resultierendeL2-Kostenfunktion.

maxRj(t)j=1,2

t

R1(t) R2(t)

(c) Die resultierendeL∞-Kostenfunktion.

Abbildung 19: Darstellung zweier pseudokonvexer Residuumsfunktionen R1(x) und R2(x) (a), die unterder L2-Norm zwei Minima aufweisen (b). Unter der L∞-Norm wird stets eine quasikonvexeFunktion erzeugt, die nur ein Minimum besitzt (c).

Hartley und Sturm (1997) haben gezeigt, wie die Zielfunktion des räumlichen Vorwärts-schnitts mit zwei Bildern unter der L2-Norm als rationale Polynomfunktion 6. Grades beschriebenwerden kann. Da ein Polynom 6. Grades bis zu drei Minima besitzen kann, garantiert ein itera-tives Gradientenabstiegsverfahren somit keine Konvergenz im globalen Minimum. Nach der dortvorgestellten „polynomischen Lösung“ kann das globale Minimum durch Auswertung der Kos-tenfunktion an stationären Punkten identifiziert werden (vgl. Anhang B). In Abbildung 20 sind


zwei Zielfunktionen eines Vorwärtsschnitts mit zwei Bildern dargestellt, welche mehrere Minimaaufweisen.

0.6

0.8

1

1.2

1.4

1.6

1.8

−1.5 −1 −0.5 0 0.5 1 1.5

(a) Kostenfunktion mit drei Minima

0.2

0.4

0.6

0.8

1

1.2

−1.5 −1 −0.5 0 0.5 1 1.5

(b) Kostenfunktion mit zwei Minima

Abbildung 20: Zwei L2-Kostenfunktionen beim räumlichen Vorwärtsschnitt: (a) zeigt eine Kostenfunk-tion mit drei Minima und (b) zeigt, dass selbst bei fehlerfreien Beobachtungen mehrereMinima auftreten können. Die Beispiele wurden sinngemäß von Hartley und Sturm(1997) übernommen, jedoch wurden nicht die Aufnahmekonfiguration genannt, die dieseKostenfunktionen erzeugen.

Weiterhin haben Stewénius et al. (2005) gezeigt, dass der räumliche Vorwärtsschnitt mit dreiBildern algebraisch dem Lösen eines Polynoms 47. Ordnung entspricht, und dass die Ordnung fürweitere Bilder kubisch anwächst. Daher kann die L2-Kostenfunktion aufgrund der vielen theore-tisch möglichen Extrema eine komplexe Oberfläche besitzen, bei welcher iterative Löser in lokaleMinima konvergieren können. Neben dem hohen Rechenaufwand treten bei der polynomischenLösung bei vielen Bildern jedoch numerische Schwierigkeiten auf, so dass diese nur für kleineProblemstellungen anwendbar bleibt.Im Folgenden wollen wir eine Beispielkonfiguration für einen Vorwärtsschnitt mit drei Bildern

betrachten, bei welcher in der L2-Kostenfunktion drei lokale Minima auftreten, wohingegen dieL∞-Kostenfunktion nur ein globales Minimum aufweist, wie es von Kahl und Hartley (2008)veröffentlicht wurde. Aus Darstellungsgründen seien die drei Kameras und der unbekannte Ob-jektpunkt in der z = 0 Ebene, so dass ein überbestimmter ebener Vorwärtsschnitt vorliegt. DieProjektionsmatrix der ersten Kamera sei gegeben durch P1. Die zweite und dritte Kamera er-halten wir durch Rotation der ersten Kamera zum einen um +120◦ und zum anderen um −120◦

jeweils um den Ursprung mittels der Rotationsmatrix R . Die drei Projektionsmatrizen

P1 =

[−3 1 −8−1 −3 −6

], P2 = P1R und P3 = P1RT

beschreiben die lineare Abbildung P2 7→ P1. In allen drei Bildern sei der Bildpunkt uj = [3; 1]beobachtet worden. Der korrespondierende Strahl der ersten Kamera ist die Linie y = −1, da sichalle Punkte der Form U = [x;−1; 1] auf uj abbilden. Die korrespondierenden Strahlen der beidenanderen Kameras ergeben sich durch Rotation von ±120◦ um den Ursprung, welcher somit dasSymmetriezentrum darstellt.In Abbildung 21 ist die Kameraanordnung mit den beobachteten Kamerastrahlen und der

daraus resultierenden L2- und L∞-Kostenfunktionen als Konturplot dargestellt. Die L2-Kosten-funktion besitzt drei Minima jeweils an den Schnittpunkten zweier Strahlen. Betrachten wir dieProjektion des Ursprungs, so ist diese von jedem beobachteten Bildpunkt 1.66 entfernt, so dassdie L2-Norm für diesen Punkt etwa

√3 · 1.662 = 8.66 beträgt. Der Punkt (0,2) wird auf Kamera

2 und 3 exakt auf den Bildpunkt 3 abgebildet und auf Kamera 1 um 2.5 von der Beobachtungentfernt. Die L2-Norm beträgt an diesem Schnittpunkt daher nur 2.5. Aufgrund der dreifachenSymmetrie sind die Kosten an den zwei anderen Schnittpunkten gleich groß. Da die L2-Normeinzelne hohe Residuen nicht so stark bestraft wie die L∞-Norm, gibt es L2-Lösungen, derenKosten geringer sind als im Ursprung, wo sich das Minimum der L∞-Kostenfunktion befindet.


−4 −3 −2 −1 0 1 2 3−3

−2

−1

0

1

2

3

4

x−Achse

y−A

chse

(a) L2-Kostenfunktion

−4 −3 −2 −1 0 1 2 3−3

−2

−1

0

1

2

3

4

x−Achse

y−A

chse

(b) L∞-Kostenfunktion

Abbildung 21: Darstellung der Kostenfunktionen des im Text eingeführten ebenen Vorwärtsschnitts mitdrei Bildern als Konturplots: Je dunkler die Fläche, desto geringer sind die Kosten für dieseLösung. Die L2-Kostenfunktion in (a) weist drei Minima jeweils an den Schnittpunktenzweier Raumstrahlen auf. Die L∞-Kostenfunktion in (b) besitzt hingegen nur ein einzigesMinimum im Symmetriezentrum. Jede Kamera ist durch einen Kreis gekennzeichnet undihre Aufnahmerichtung durch einen kleinen Pfeil, die beobachteten Raumstrahlen sinddurch die großen Pfeile dargestellt. Es ist nur der Bereich vor den drei Kameras dargestellt,begrenzt durch die eingezeichneten Geraden durch die Bildebenen. Das Beispiel wurdesinngemäß aus Kahl und Hartley (2008) übernommen.

Die Beispiele, welche in Abbildung 20 und 21 aufgeführt worden sind, zeigen, dass die Kosten-funktionen im Lösungsraum durchaus mehrere Minima besitzen können. Iterative Löser benötigendaher ausreichend gute Näherungswerte, so dass die auf Gradienten basierenden Suchrichtungennicht in ein lokales Minimum führen. Es ist jedoch darauf hinzuweisen, dass solche Konfiguratio-nen beim räumlichen Vorwärtsschnitt sehr selten auftreten (vgl. Olsson und Kahl 2010), unddass die Konstellation in Abbildung 21 bereits durch kleine Verschiebungen oder Drehungen derKameras die L2-Kostenfunktion nur noch ein Minimum aufweist.

Berücksichtigung nicht gleichgenauer und korrelierter Bildpunktkoordinaten

Bisher sind wir davon ausgegangen, dass die Unsicherheit in den beobachteten Bildpunktenunabhängig und identisch verteilt ist. Die Genauigkeit, mit welcher ein Bildpunkt identifiziertund beobachtet werden kann, ist jedoch vor allem von der Intensitätsverteilung in der Umgebungdes Bildpunktes abhängig. Hierdurch kommt es i. a. zu richtungsabhängigen und korrelierten Un-sicherheiten. Das stochastische Modell eines beobachteten Bildpunktes wird daher häufig durcheine vollbesetzte 2×2-Kovarianzmatrix beschrieben

Σujuj =

[σ2uj σujvj

σujvj σ2vj

], (3.11)

wodurch alle Bildpunkte gegenseitig unkorreliert sind, jedoch die Koordinaten eines Bildpunkteskorreliert sein können (vgl. McGlone 2004, S. 853 f.). Die richtungsabhängige Unsicherheit inder Lage eines Bildpunktes sollte daher durch Gewichtung der Distanz zwischen des beobachtetenBildpunktes u und des rückprojizierten Bildpunktes u mittels der Inversen der Kovarianzmatrix


als Metrik bei der Residuumsfunktion Rj(x) berücksichtigt werden:

Rj(x) = ||uj − uj ||Σ−1ujuj

=(

(uj − uj)TΣ−1ujuj (uj − uj)

)1/2. (3.12)

Da Σujuj symmetrisch und positiv definit ist, erhalten wir durch eine SingulärwertzerlegungΣujuj = UjDjUj . Die Inverse ergibt sich in der faktorisierten Form durch

Σ−1ujuj = UjD−1

j Uj = Σ−1/2ujuj Σ−1/2T

ujuj mit Σ−1/2ujuj

= U jD−1/2j .

Die Matrix Σ−1/2ujuj stellt eine affine Transformation dar, welche einen Bildpunkt derart dekorre-

liert, so dass das Rauschen jedes Bildpunktes isotrop, identisch und unabhängig verteilt ist (vgl.Ke und Kanade 2006). Die transformierten Bildpunkte ergeben sich durch

u′j =

[u′

v′

]= Σ−1/2

ujuj

[uv

]und u′j = Σ−1/2

ujuj

[pT

1jUpT

2jU

]/pT

3jU .

Die mittels der Kovarianzmatrix Σujuj gewichtete Residuumsfunktion besitzt folglich die Form

Rj(x) =

∥∥∥∥Σ−1/2ujuj

([pT1j − ujpT3jpT2j − vjpT3j

]x+

[p1j − ujp3j

p2j − vjp3j

])∥∥∥∥pT3jx+ p3j

=‖Ajx+ bj‖cTj x+ dj

(3.13)

mit

Aj2×3

= Σ−1/2ujuj

[pT1j − ujpT3jpT2j − vjpT3j

], bj

2×1

= Σ−1/2ujuj

[p1j − ujp3j

p2j − vjp3j

], cTj

1×3

= pT3j und dj1×1

= p3j .

In Abbildung 22 ist die Geometrie der γ-Subniveaumenge dargestellt.

Abbildung 22: Die Form und Größe eines gewichteten Lorentzkegels ergibt sich durch das Residuum Rjund die Kovarianzmatrix Σujuj

auf der Bildebene.

Residuumsfunktion aus Winkelabweichungen

Der oben dargestellten Kostenfunktion (3.7) bzw. (3.13) liegen die Residuen zugrunde, welchedurch die Rückprojektion eines Objektpunktes U auf die Bildebene entstehen. Mittels der be-kannten Rotationsmatrizen der äußeren Orientierung kalibrierter Kameras kann alternativ derTangens des Winkels θj zwischen einem beobachteten Raumstrahl vj = RT

j K−1j uj und einem den

Objektpunkt U projizierenden Strahl vj = U −Zj als Residuum verwendet werden

Rj(x) = | tan θj | =| sin θj |cos θj

=‖vj × vj‖2vTj vj

=‖vj × (U −Zj)‖2vTj (U −Zj)

, (3.14)


wobei die Annahme getroffen wird, dass der Betrag des Winkels θj kleiner als π/2 ist, da dieTangensfunktion sonst nicht monoton anwächst.Durch die Minimierung der Winkelabweichungen wird i. a. ein geringfügig anderes Ergebnis er-

zielt. Die Form der Residuumsfunktion (3.14) beschreibt jedoch wie die Residuumsfunktion (3.7)die Mantelfläche eines Lorentzkegels

Rj(x) =‖S(vj)x− S(vj)Zj‖2

vTj x− vTj Zj=‖Ajx+ bj‖2cTj x+ dj

(3.15)

mit

Aj3×3

= S(vj), bj3×1

= −S(vj)Zj , cTj1×3

= vTj sowie dj1×1

= −vTj Zj

und ist ebenfalls i. a. nicht konvex, jedoch stets quasikonvex. S(vj) erzeugt eine schiefsymme-trische Matrix, deren Zeilen eine zum Vektor vj senkrechte Ebene aufspannen. Daher wird derLorentzkegel hier nicht auf der Bildebene im R2, sondern auf der Tangentialebene der Einheits-kugel an der Beobachtung vj mit dem Radius tanφj im R3 aufgespannt (vgl. Abbildung 23).

(a) Die Residuumsfunktion Rj(x) gibt den Abstandzwischen vj und vj auf der Tangentialebene der

Einheitskugel an vj zurück.

(b) Die Lösungmenge, welche das Residuum Rj(x)erzeugt, beschreibt die Mantelfläche eines

Lorentzkegels.

Abbildung 23: Geometrische Interpretation der auf den Winkelabweichungen basierenden Residuums-funktion (3.15).

Die Gewichtung der aus den Winkelabweichungen resultierenden Residuen durch eine Kovari-anzmatrix lässt sich in ähnlicher Weise wie bei den zuvor dargestellten Residuen in der Bildebenedurchführen. Durch Fehlerfortpflanzung erhalten wir die 3×3-Kovarianzmatrix des sphärisch nor-mierten Vektors vj durch

Σvjvj = RTj K−1

j

[Σujuj 02

0T2 1

]K−Tj Rj (3.16)

und die gewichtete Residuumsfunktion lautet

Rj(x) =‖Σ−1/2

vjvj (S(vj)x− S(vj)Zj) ‖2vTj x− vTj Zj

=‖Ajx+ bj‖2cTj x+ dj

(3.17)


mit

Aj3×3

= Σ−1/2vjvj S(vj), bj

3×1

= −Σ−1/2vjvj S(vj)Zj , cTj

1×3

= vTj und dj1×1

= −vTj Zj .

3.1.2 Lösung des L∞-Optimierungsproblems

Die Zielfunktion unter der L∞-Norm ergibt sich durch das punktweise Maximum jeder einzelnenResiduumsfunktion

f0(x) = ||r||∞ =N

maxj=1

Rj(x) . (3.18)

Eine quasikonvexe Funktion besitzt stets eine konvexe Subniveaumenge (vgl. Abschnitt 2.5.1).Die γ-Subniveaumenge von f0(x)

Sγ =

{x | N

maxj=1

Rj(x) ≤ γ}

=N⋂j=1

Sγ,j (3.19)

ist konvex, da die Schnittmenge konvexer Mengen, das sind hier die Subniveaumengen Sγ,j , stetswieder eine konvexe Menge ergibt (vgl. Boyd und Vandenberghe 2004, S. 36). Somit bildetdas punktweise Maximum der quasikonvexen Residuumsfunktionen Rj(x) stets auch wieder einequasikonvexe Funktion.Wir formulieren das quasikonvexe L∞-Optimierungsproblem durch

minimiereN

maxj=1

||Ajx+ bj ||2cTj x+ dj

u.d.N. cTj x+ dj > 0, j = 1, ..., N.

(3.20)

Die zulässige Menge ist durch die affine Nebenbedingung cTj x+ dj ≥ 0 auf Objektpunkte vorden Bildebenen beschränkt. Die durch N strikte Ungleichungen begrenzten Halbräume bildenkeine kompakte Menge, d. h. dass sie nicht beschränkt oder abgeschlossen sind wie bspw. einPolyeder. Dennoch erlauben uns zum einen die konvexen Eigenschaften des Problems eine Folgezu finden, welche zum Infimum strebt, was letzten Endes von Interesse ist (vgl. Olsson undKahl 2010), und zum anderen können in einer Implementierung die strikten Ungleichungendurch cTj x+ dj ≥ ε ersetzt werden, wobei ε eine sehr kleine Zahl größer Null ist.Da f0(x) durch einen punktweisen Operator aus einer Funktionsschar konstruiert wird, ist

diese nicht überall stetig differenzierbar (vgl. Abbildung 19(c)). Klassische Minimierungsverfah-ren, welche wie bspw. das Newton-Verfahren auf den Gradienten der zu minimierenden Funktionberuhen, sind daher nicht anwendbar. Solche Verfahren können selbst an stetig differenzierba-ren Stellen fehlschlagen, da die Suchrichtung den Funktionsverlauf nicht zuverlässig beschreibenwürde. Da der Lösungsraum beim Vorwärtseinschneiden eines einzigen Objektpunktes lediglichdreidimensional ist, ist das Minimierungsproblem jedoch relativ einfach. Hartley und Schaf-falitzky (2004) haben zur Minimierung von (3.20) anstelle von Gradienten zufällig generierteSuchrichtungen ausgewertet. Das Konvergenzverhalten ist dann jedoch unklar und dieses Ver-fahren ist bei höher dimensionalen Lösungsräumen kaum anwendbar.Durch Kahl (2005) wurde erstmals vorgeschlagen, das quasikonvexe Optimierungsproblem

(3.20) in ein konvexes Zulässigkeitsproblem zu überführen, welches mittels eines eindimensionalenBisektionsalgorithmus gelöst werden kann (vgl. Abschnitt 2.5.2). Durch die Einführung einer


weitern Minimierungsvariablen γ kann das Problem in das äquivalente Problem

minimierex, γ

γ

u.d.N.||Ajx+ bj ||2cTj x+ dj

≤ γ, j = 1, ..., N

cTj x+ dj > 0, j = 1, ..., N

(3.21)

umgeschrieben werden.Diese Formulierung lässt sich anschaulich interpretieren: Eine zulässige Lösung x muss sich

innerhalb der Schnittmenge Sγ aller Kegel Sγ,j befinden, welche durch den Radius γ auf der Bil-debene bzw. Tangentialebene an den jeweiligen Beobachtungen aufgespannt werden. Die Schnitt-menge entspricht der Schnittmenge aller durch γ begrenzten Subniveaumengen Sγ,j . Die optimaleLösung x ist derjenige Punkt, in welchem sich alle Kegel unter einem minimalen γ schneiden. InAbbildung 24 ist diese geometrische Interpretation der Optimierungsaufgabe dargestellt.

...

min. g

Sg = O

...

g

Sg = x

(3.21)

Lösung von

Abbildung 24: Geometrische Interpretation des räumlichen Vorwärtsschnitts: Die Kegelgröße wird durchγ festgelegt. Für jeden Punkt in Sγ,j ist der Reprojektionsfehler kleiner als γ. Falls dieSchnittmenge Sγ nicht leer ist, so existiert ein Punkt x′, an welchem die Zielfunktionf0(x′) ≤ γ ist. Die Minimierung von f0(x) ist daher äquivalent zur Minimierung von γunter der Bedingung, dass die Schnittmenge aller Kegel nicht leer ist.

Sowohl die zu minimierende lineare Zielfunktion als auch die affinen Chiralitätsbedingungenstellen konvexe Funktionen dar. Die j Nebenbedingungen ||Ajx+ bj ||2 − γ(cTj x+ dj) < 0 sindjedoch nicht konvex in den Minimierungsvariablen x und γ, somit stellt (3.21) in dieser Formu-lierung kein konvexes Optimierungsproblem dar. Durch die Wahl eines festen γ > 0 kann dasOptimierungsproblem jedoch in ein konvexes Zulässigkeitsproblem überführt werden, welchesdurch j Kegel zweiter Ordnung restringiert ist:

finde x

u.d.N. ||Ajx+ bj ||2 − γ(cTj x+ dj) < 0, j = 1, ..., N.(3.22)

Falls die durch ein γ aufgespannten Kegel zu schmal sind, besitzen diese keine gemeinsameSchnittmenge und es existiert keine zulässige Lösung, unter welcher das maximale Residuumkleiner als γ ist. Andernfalls, wenn γ ausreichend groß ist, so dass sich alle Kegel schneiden,muss sich die optimale Lösung x in ihrer Schnittmenge Sγ befinden. In einem Bisektionsverfahren


können wir über variierende γ den minimalen Wert γ suchen, unter welchem S∞γ nicht leer istbzw. eine zulässige Lösung existiert.Zur Initialisierug des in Abschnitt 2.5.2 beschriebenen Bisektionsverfahren muss ein abgeschlos-

senes Intervall [γmin, γmax] festgelegt werden, welches γ enthält. In jeder ν-ten Iteration wird dasZulässigkeitsproblem (3.22) mit γ(ν) = (γmin + γmax)/2 gelöst. Falls eine beliebige zulässige Lö-sung x(ν) existiert, so befindet sich γ in der unteren Hälfte des Suchintervalls, so dass es auf[γmin, γ

(ν)] verkleinert werden kann. Andernfalls befindet sich γ in der oberen Hälfte [γ(ν), γmax].Da sich das maximale Residuum aus der gefundenen zulässigen Lösung x(ν) ermitteln lässt,kann das kleinere Intervall [γ(ν),maxNj=1Rj(x

(ν))] für den folgenden Iterationsschritt verwendetwerden.Das Bisektionsverfahren kann abgebrochen werden, sobald das Suchintervall eine vorgegebene

Toleranz ε unterschreitet. Es ist zu beachten, dass somit die optimale Lösung x innerhalb vonmaximal dlog2((u − l)/ε)e Iterationen garantiert erreicht wird. Die Anzahl der Iterationen isthierbei nicht von der Dimension des Parametervektors x abhängig. Dieses Verfahren eignet sichdaher auch zur Bestimmung vieler unbekannter Objektpunkte.Das konvexe Zulässigkeitsproblem (3.22) kann mittels eines Innere-Punkte-Verfahren gelöst

werden. Wir verwenden zur Lösung das Open-Source-Software-Paket SeDuMi, welches anfäng-lich von Sturm (1999) entwickelt wurde. In diesem wird das äquivalente konvexe Second-orderCone Programm

minimierex, s

s

u.d.N. ||Ajx+ bj ||2 − γ(ν)(cTj x+ dj) ≤ s, j = 1, ..., N(3.23)

gelöst. Die Minimierungsvariable s lässt sich geometrisch als Abstand zu den durch γ(ν) auf-gespannten Kegel interpretieren, wie es in Abbildung 25 dargestellt ist. Liefert die Minimierungein optimales s ≤ 0, so liegt die Lösung innerhalb aller Kegel und ist somit zulässig. Andernfallsexistiert keine zulässige Lösung unter dem aktuellen γ(ν), das heißt, dass nicht alle Restriktionenerfüllt werden können, und somit die Schnittmenge aller Kegel leer ist. Zur Initialisierung kannein beliebiger Startpunkt x(0) gewählt werden, mit welchem ein zulässiges s(0) berechnet werdenkann.

x

g(v)

s

Sg,j

Abbildung 25: Falls s > 0 ist, so existiert keine zulässige Lösung im Zulässigkeitsproblem (3.22). Die Op-timierungsvariable s im Second-order Cone Programm (3.23) stellt den zu minimierendenmaximalen Abstand eines Punktes x zu allen quadratischen Kegeln dar. In der Abbildungist der Punkt x dargestellt, welcher den maximalen Abstand zur j-ten Lorentzkegel Sγ,jaufweist. Zu allen anderen Lorentzkegel ist der Abstand entweder gleich groß oder kleiner.

Vereinfachung auf ein lineares Programm

Ke und Kanade (2007) schlagen zur Vereinfachung des Minimierungsproblems (3.23) dieMöglichkeit vor, die Residuen in der Bildebene bzw. in der Tangentialebene anstatt durch die

3.2. Bündelausgleichung bei bekannten Rotationen 43

euklidische Distanz durch die Manhattan-Distanz zu bestimmen. Die Restriktionen des Zuläs-sigkeitsproblems vereinfachen sich dann geometrisch auf Kegel erster Ordnung, deren Öffnungunter der L1-Norm beschrieben wird:

minimierex, s

s

u.d.N. ||Ajx+ bj ||1 − γ(ν)(cTj x+ dj) ≤ s, j = 1, ..., N.(3.24)

Dieses Optimierungsproblem stellt ein lineares Programm dar, welches aufgrund der geringerenKomplexität effizienter als ein Second-order Cone Programm mittels Mehtoden der konvexenOptimierung lösbar ist. Falls die Residuen in der Bildebene minimiert werden, kann das Problemformuliert werden durch

minimierex, s

s

u.d.N. G jx+ hj � s14, j = 1, ..., N(3.25)

mit

G j4×3

=

pT1j+pT2j−pT3j(uj+vj+γ(ν))

pT1j+pT2j+pT3j(uj−vj−γ(ν))

pT1j+pT2j+pT3j(vj−uj−γ(ν))

pT1j+pT2j+pT3j(uj+vj−γ(ν))

und hj4×1

=

p1j+p2j−p3j(uj+vj+γ

(ν))

p1j+p2j+p3j(uj−vj−γ(ν))

p1j+p2j+p3j(vj−uj−γ(ν))

p1j+p2j+p3j(uj+vj−γ(ν))

. (3.26)

Der Nachteil der Vereinfachung des L∞-Optimierungsproblems auf ein lineares Programm liegtdarin, dass die Residuumsfunktion in der Bildebene keinen Kreis sondern ein Viereck beschreibt,was keiner typischen Verteilung der Abweichungen eines beobachteten Bildpunktes entspricht.Zudem kann eine eventuell bekannte Kovarianzmatrix eines beobachteten Bildpunktes nicht sinn-voll berücksichtigt werden, um die häufig auftretenden Korrelationen zwischen den Koordinatenzu beschreiben. Die Vereinfachung auf ein lineares Programm ist auch bei den folgenden geome-trischen Problemen durchführbar, jedoch werden wir sie aufgrund der genannten Nachteile nichtweiter berücksichtigen.

3.2 Bündelausgleichung bei bekannten Rotationen

Das vorgestellte Verfahren zur Lösung des räumlichen Vorwärtsschnitt durch Minimierung derResiduen unter der L∞-Norm kann zudem zur Lösung etwas komplexerer Probleme angewen-det werden. In diesem Abschnitt werden wir zeigen, dass mittels dieses Verfahrens auch dieL∞-Lösung einer Bündelausgleichung bestimmt werden kann, wenn die Rotationsmatrizen deräußeren Orientierungen aller Kameras bekannt sind. Diese können bspw. während der Bildauf-nahmen durch Inertialsensoren oder ein Gyroskop gemessen worden sein oder aber auch in einemvorangehenden Schritt bestimmt werden, etwa durch eine lineare kleinste-Quadrate Ausgleichungauf der Basis berechneter relativer Rotationen (vgl. Martinec und Pajdla 2007). Die Bestim-mung der relativen Orientierung unter Minimierung der L∞-Norm werden wir in Abschnitt 3.7betrachten.Bei der Bündelausgleichung bei bekannten Rotationen wollen wir die unbekannten Kamera-

translationen der äußeren Orientierung Zj und die unbekannten Objektpunktkoordinaten U i

bestimmen. Hierzu seien i = 1, ..., I Objektpunkte Ui durch j = 1, ..., J Kameras als Bildpunk-te uij beobachtet worden. Der funktionale Zusammenhang zwischen den Beobachtungen undden Unbekannten kann wie beim räumlichen Vorwärtsschnitt mittels der Kollinearitätsgleichung


λijuij = PjUi beschrieben werden. Wir parametrisieren die homogenen Größen Pj und Ui so,dass

λijuij = [ K jRj | tj ] Ui mit tj = −RjZj und Ui = [U i; 1 ] (3.27)

gilt. Objektpunkte, welche numerisch im Unendlichen liegen, können somit nicht bestimmt wer-den.

uij

Ui

Zj

Zj'

uij'

U1

U2UI

...

Abbildung 26: Bei der Bündelausgleichung mit bekannten Rotationen werden neben den unbekannteni = 1, ..., I Objektpunkten U i die j = 1, ..., J unbekannten Kameratranslationen Zj be-stimmt. Die Unbekannten werden in einer Bündelausgleichung unter Einbeziehung allerBeobachtungen bestimmt. Es ist bei diesem Verfahren nicht notwendig, dass alle Objekt-punkte durch alle Kameras beobachtet worden sind.

Die Residuumsfunktion Rij(x) zu einem beobachteten Bildpunkt uij lässt sich in der gleichenForm wie die Residuumsfunktion des räumlichen Vorwärtsschnitt (3.6) darstellen

Rij(x) =

∥∥∥∥[ pT1pT2]U i +

[t1jt2j

]− (pT3U i + t3j)uij

∥∥∥∥2

pT3U i + t3j=‖Aijxij + bij‖2cTijxij + dij

(3.28)

mit

Aij2×6

=

[pT1j−uijpT3j 1 0 −uijpT2j−vijpT3j 0 1 −vij

], bij

2×1

= 02, cTij1×6

=[pT3j 0 0 1

]und dij

1×1

= 0,

wobei xij = [U i; tj ] ist.Die auf den Winkelabweichungen θij(x) zwischen den beobachteten und rückprojizierenden

Kamerastrahlen basierende Residuumsfunktion beschreibt in analoger Weise den Lorentzkegel

Rij(x) = tan θij =‖S(vij)U i − S(vij)Zj‖2

vTijU i − vTijZj=‖Aijxij + bij‖2cTijxij + dij

(3.29)

mit

Aij3×6

=

[S(vij)−S(vij)

], bij

3×1

= 03, cTij1×6

=[vTij −vTij

]und dij

1×1

= 0 .

Alle unbekannten Objektpunkte und Kameratranslationen seien im Folgenden im Parameter-vektor x ∈ Rm enthalten. Jede Beobachtung restringiert den Lösungsraum durch einen sechs-dimensionalen Lorentzkegel Sγ,ij im m-dimensionalen Lösungsraum. Die Geometrie des Opti-

3.3. Homographie-Schätzung 45

n−m I=2 I=3 I=4 I=5 I=6 I=7 I=8 I=9 I=10

J = 2 0 1 2 3 4 5 6 7 8J = 3 1 3 6 9 12 15 18 21 24J = 4 2 6 11 16 21 26 31 36 41J = 5 3 9 16 23 30 37 44 51 58

Tabelle 1: Jeder in einer Kamera beobachtete Bildpunkt uij eines abgebildeten Objektpunktes liefertzwei Beobachtungen. Jeder zu bestimmende Objektpunkt Ui und jede unbekannte Kame-ratranslation Zj erzeugt jeweils drei unbekannte Parameter. Es müssen zur Lagerung vierGleichungsrestriktionen auf die Parameter eingeführt werden, bspw. durch die Vorgabe vonvier Koordinaten. Falls kein Konfigurationsdefekt vorliegt und die Redundanz n−m>0 beträgt,so liegt ein Optimierungsproblem vor, welches durch die Minimierung der L∞-Norm gelöstwerden kann.

mierungsproblems ist aufgrund der höher dimensionalen Kegelrestriktionen nicht anschaulichdarstellbar, jedoch numerisch in gleicher Weise wie der räumliche Vorwärtsschnitt mittels einesInnere-Punkte-Verfahrens lösbar.Die Optimalität einer solchen Lösung ist jedoch einleuchtend: Gesucht ist diejenige Lösung x,

unter welcher γ den kleinstmöglichen Wert annimmt, unter der Bedingung, dass jeder auf dem je-weiligen Projektionszentrum Zj stehende Kegel Sγ,ij den jeweiligen Objektpunkt U i beinhaltet.Analog zur L∞-Lösung des räumlichen Vorwärtsschnitts kann auch hier das Optimierungspro-blem durch (3.21) formuliert werden und mittels iterativer Lösung des Zulässigkeitsproblems(3.22) in einem Bisektionsverfahren gelöst werden.Durch die bekannten Rotationen der äußeren Orientierung der Kameras ist die rotatorische Ori-

entierung im Referenzsystem festgelegt. Da die beobachteten Bildpunkte jedoch nur Richtungs-informationen liefern, kann das Richtungsnetz lediglich bis auf eine unbekannte 3D-Translationund einen unbekannten Maßstab bestimmt werden. Ohne Einführung von Bedingungen kann esdurch den Optimierungsalgorithmus durch die Mehrdeutigkeiten in der Lösung zu extrem großenSchätzwerten für die Koordinaten kommen, wodurch die numerische Genauigkeit verloren geht.Die einfachste Möglichkeit, das Referenzsystem eindeutig zu lagern, ist die Position des Pro-

jektionszentrums bspw. der ersten Kamera durch Z1 = 03 und die der zweiten Kamera in eineAchsrichtung durch bspw. Z2 = [1; ∗; ∗] festzulegen, wobei * eine unbekannte Variable kennzeich-net. Die Anzahl der unbekannten Parameter beträgt dann m= 3J+3I−4. In Tabelle 1 ist dieRedundanz r = n−m dargestellt, wenn alle Objektpunkte in allen Bildern beobachtet wordensind, demnach also n = 2IJ Beobachtungen vorliegen. Dies muss jedoch nicht der Fall sein, wie esbspw. bei der von Tomasi und Kanade (1992) vorgeschlagenen direkten Methode zur Lösungeiner Bündelausgleichung durch Faktorisierung notwendig ist, solange kein Konfigurationsdefekt6

vorliegt.

3.3 Homographie-Schätzung

In diesem Abschnitt wollen wir zeigen, dass das in Abschnitt 3.1.2 eingeführte Verfahren auchzur Schätzung von Transformationen angewendet werden kann. Eine Homographie ist eine inver-tierbare Transformation im projektiven Raum, welche Geraden wieder als Geraden abbildet. Sostehen bspw. zwei perspektivische Abbildungen der gleichen Raumebene durch eine Homogra-phie in Relation. Die Bestimmung der Homographie zwischen zwei Bildern hat einige wichtigepraktische Anwendungen in der Bildverarbeitung, wie bspw. die Bildrektifizierung und die Bild-

6Ein Konfigurationsdefekt liegt bspw. vor, wenn nicht alle Kameras ausreichend durch beobachtete Objektpunkteverknüpft sind, so dass der Maßstab nicht übertragen werden kann (vgl. bspw. Snavely et al. 2008).


registrierung (vgl. Szeliski 2006).Es seien N Objektpunkte in zwei Bildern beobachtet worden, welche auf einer Raumebene A

liegen. Die korrespondierenden Bildpunkte bezeichnen wir im ersten Bild mit ui und im zweitenBild mit u′i, wie es in Abbildung 27 dargestellt ist. Das funktionale Modell der Transformationlautet

λiui = Hu′i mit H =

hT1

hT2

hT3

=

x1 x2 x3

x4 x5 x6

x7 x8 1

, (3.30)

wobei wir das letzte Element von H aufgrund der Homogenität auf 1 festlegen. Diese Wahl kannjedoch nicht getroffen werden, wenn der Ursprung [0; 0; 1] eines Bildes im anderen in einem Punktim Unendlichen [u; v; 0] abgebildet wird, da dann das letzte Element h33 = 0 wäre, welches nichtauf 1 skalierbar ist. Diese Möglichkeit kann umgangen werden, indem jeweils eine Translation imersten und im zweiten Bild auf alle Bildpunkte angewendet wird, so dass eine Punktkorrespondenzin beiden Bildern im Ursprung liegt (vgl. Kahl und Hartley 2008). Dann ist es nicht möglich,dass h33 = 0 wird.

H

ui

u'i

A

Kamera 1

Kamera 2

Abbildung 27: Eine Homographie H beschreibt bspw. die Transformation im projektiven Raum zwischenallen korrespondierenden Bildpunkten ui ↔ u′i, welche die perspektive Abbildung vonObjektpunkten auf einer Raumebene A sind.

Die Residuumsfunktion Ri(x) = d(ui,Hu′i) eines korrespondierenden Punktpaares ui ↔ u′ibeschreibt auch hier in Abhängigkeit von der Parametrisierung von H einen Lorentzkegel

Ri(x) =

√√√√(hT1 u′ihT

3u′i

− ui

)2

+

(hT

2 u′ihT

3u′i

− vi

)2

(3.31)

=

√(hT

1 u′i − uihT3u′i

)2+(hT

2 u′i − vihT3u′i

)2hT

3u′i

(3.32)

=

∥∥∥∥u′i [hT1 h2

]−[uivi

]u′i h

T3

∥∥∥∥2

u′i hT

3

=‖Aix+ bi‖cTi di

(3.33)

mit

Ai2×8

=

[ ′u Ti 0T3 −ui ′u T

i

0T3′u Ti −vi ′u T

i

], bi

2×1= −ui, cTi

1×8=[0T6 u

′T]

und di = 11×1

,

wobei u′i euklidisch normiert ist. Bei mehr als vier korrespondierenden Bildpunkten liegt ein

3.4. Ein Verfahren zur Ausreißerdetektion 47

Optimierungsproblem vor. Die L∞-Schätzung der Homographie H kann wie die L∞-Schätzungfür den räumlichen Vorwärtsschnitt bestimmt werden. Das Optimierungsproblem (3.21) wirdhier durch jede Punktkorrespondenz ui ↔ u′i durch die achtdimensionalen Lorentzkegel (3.31)restringiert. Da jede Beobachtung effektiv nur einen fünfdimensionalen Kegel im Lösungsraumerzeugt, werden vier verschiedene Punktkorrespondenzen benötigt, um die Homographie zwi-schen zwei Ebenen zu bestimmen. Die Bestimmung von H kann durch eine iterative Lösung desZulässigkeitsproblems (3.22) in einem Bisektionsverfahren erfolgen.

Weitere projektive Transformationen und Projektionen

Neben der Homographie-Schätzung können mittels dieses Verfahrens auch andere perspektiveTransformationen oder Abbildungen bestimmt werden, wie bspw. die Projektion P3 7→ P2. DieBestimmung der 3×4-Projektionsmatrix P aus bekannten Objektpunkten Ui und deren abge-bildeten Bildpunkten ui mit i = 1, ..., N wird häufig „direkte lineare Transformation“ (DLT)genannt und stellt ein sehr ähnliches Problem wie die Homographie-Schätzung dar. Die Abbil-dung erfolgt durch

λiui = PUi mit P =

x1 x2 x3 x4

x5 x6 x7 x8

x9 x10 x11 1

(3.34)

und die resultierende Residuumsfunktion ergibt sich in gleicher Weise wie bei der Homographie-Schätzung. In der englischsprachigen Literatur wird die Lösung nach P häufig als „camera re-sectioning“ bezeichnet (vgl. bspw. Olsson und Kahl 2010). Sie ist nicht mit dem räumlichenRückwärtsschnitt zu verwechseln, auf welchen wir in Abschnitt 3.6 eingehen werden.

3.4 Ein Verfahren zur Ausreißerdetektion

Eine große Schwachstelle bei der L∞-Optimierung liegt in der Anfälligkeit gegenüber Ausrei-ßern in den Beobachtungen. Falls Ausreißer vorliegen, richtet sich die L∞-Lösung lediglich nachdiesen, ohne zu berücksichtigen, wie viele „gute“ Beobachtungen vorliegen. Zur Ausschließungmöglichst vieler Ausreißer wird daher häufig das RANSAC-Verfahren (vgl. Fischler und Bol-les 1981) vor einer Optimierung angewendet. Es ist jedoch bisher nicht bekannt, wie es auf einMehrbild-Rekonstruktionsproblem wie die Bündelausgleichung angewendet werden kann, ohne esin Zwei- oder Dreibild-Rekonstruktionsprobleme zu unterteilen. Hierdurch wird nicht garantiert,dass alle Ausreißer aus allen Bildkorrespondenzen eliminiert werden.

Sim und Hartley (2006) zeigten, dass durch die iterative Optimierung und Aussonderungder Beobachtung mit dem größten Residuum bei den oben genannten Problemen alle Ausreißererfolgreich detektiert werden können. Solange das größte Residuum größer als ein festgelegterSchwellwert ist, so muss die L∞-Lösung durch mindestens einen Ausreißer verfälscht sein. Dergrößte Nachteil der iterativen Ausreißerelimination besteht in der langen Berechnungsdauer.Probleme mit vielen Parametern, wie bspw. die Lösung der vorgestellten Bündelausgleichungmit vielen unbekannten Kamerapositionen und Objektpunkten, sind für dieses Verfahren meistzu aufwendig (vgl. Lee et al. 2010).

Ke und Kanade (2007) schlagen vor, die Zielfunktion zu robustifizieren, indem sie anstelledes maximalen Residuums das m-t größte Residuum minimieren. Bei m = N/2, wobei N dieAnzahl der beobachteten Bildpunkte ist, entspricht dieses Optimierungsproblem dem so genann-ten Medianschätzer. Dieses Problem führt zu einem ganzzahligen Optimierungsproblem, welchesdurch die Minimierung der Summe der Unzulässigkeiten approximiert und innerhalb des Bisekti-onsverfahrens nach Algorithmus 3 gelöst werden kann. Durch dieses Vorgehen ist die Zielfunktion


jedoch nicht mehr zwangsläufig quasikonvex, so dass dieses Verfahren keine global-optimale Lö-sung garantiert. Zudem ist die Detektion aller Ausreißer nicht garantiert.In diesem Abschnitt wollen wir auf das von Lee et al. (2010) entwickelte Verfahren zur De-

tektion von Ausreißern eingehen. Bei diesem wird, wie in dem von Ke und Kanade (2007)vorgeschlagenen Verfahren, die Summe der Unzulässigkeiten minimiert, jedoch in einem der Op-timierung vorangehenden Schritt. Die Formulierung des Optimierungsproblems führt auf einSecond-order Cone Programm, welches mittels einem Innere-Punkte-Verfahren gelöst werdenkann.

Formulierung eines konvexen Optimierungsproblems zur Ausreißerdetektion

Inlier7 stellen im Allgemeinen die größte Teilmenge aller Beobachtungen dar, welche untergewissen geometrischen Bedingungen eine einzige Lösung unterstützen. Das entsprechende re-stringierte Optimierungsproblem entspricht daher der Maximierung der Anzahl der Inlier undstellt ein L0-Minimierungsproblem dar. Die Problemformulierung führt auf ein so genanntesganzahliges lineares Programm, welches eine nicht kontinuierliche Zielfunktion besitzt und dahernicht ohne weiteres lösbar ist.

Lee et al. (2010) schlagen vor, dieses Problem durch eine L1-Minimierung der Unzulässig-keiten zu relaxieren. Die Minimierung der Summe der Unzulässigkeiten, im Folgenden kurz SOIfür die englische Bezeichnung „sum of infeasabilities“ genannt (vgl. Boyd und Vandenberghe2004, S. 580), ist dem Zulässigkeitsproblem (2.73) sehr ähnlich, es wird jedoch für jede Unglei-chungsrestriktion eine Hilfsvariable angesetzt, welche nur positive Werte oder den Wert Nullannehmen darf. Für die oben eingeführten und durch quadratische Kegel restringierten Optimie-rungsprobleme ergibt sich das SOI-Problem

minimierex,s

s1 + s2 + ...+ sN

u.d.N. ||Ajx+ bj ||2 − γ(cTj x+ dj) ≤ sjsj ≥ 0, j = 1, ..., N.

(3.35)

Die Lösung des Second-order Cone Programms liefert zum einen den Lösungsvektor x und denUnzulässigkeitsvektor s = [s1; ...; sN ]. Wie zuvor dient die positive Konstante γ als maximalerSchwellwert für ein Residuum. Falls die Summe

∑Ni=1 si unter einem γ Null ist, so ist auch das

Zulässigkeitsproblem (3.23) unter diesem γ zulässig.Die SOI-Minimierung liefert uns jedoch neben der Aussage über die Zulässigkeit des originären

Problems zudem eine Aussage über die Zulässigkeit jedes einzelnen beobachteten Bildpunktesunter einem maximalen Residuumsschwellwert γ. Falls ein sj > 0 ist, so liegt die Lösung xaußerhalb des Kegels Sγ,j , wobei sj den Abstand angibt (vgl. Abbildung 28). Das Residuum desj-ten Bildpunktes ist demnach unter x größer als das maximal zulässige γ und kann daher alsAusreißer betrachtet werden.Diese Problemformulierung relaxiert das L0-Minimierungsproblem durch Minimierung der L1-

Norm der Unzulässigkeiten. Die Zielfunktion des ursprünglichen Optimierungsproblems unterder L0-Pseudonorm lautet

‖s‖0 =N∑j=1

s0j =

N∑j=1

I(sj) mit I(sj) =

{0 fur sj = 0

1 fur sj > 0(3.36)

und minimiert nicht die Summe der einzelnen Unzulässigkeiten sj , sondern die Anzahl der ver-

7Als ein Inlier wird ein beobachteter Bildpunkt bezeichnet, welcher keinen Ausreißer darstellt, also einer unter-stellten Verteilung folgt und keinen extremen Wert annimmt.

3.5. Branch-and-Bound im Rotationsraum 49

Sg,1

Sg,2 Sg,3

Sg,4

s

ss

x

(a) Der Wert von s im Zulässigkeitsproblem (3.23) istoptimal, wenn es keinen Punkt x gibt, dessen größterAbstand zu allen Kegeln Sγ,j kleiner ist als s zu x.

x

Sg,1

Sg,2 Sg,3

Sg,4

s4

(b) Der Vektor s im SOI-Problem (3.35) ist optimal,wenn es keinen Punkt x gibt, dessen Abstände sj zu den

Kegeln Sγ,j in der Summe kleiner ist als ||s||1 zu x.

Abbildung 28: Gegenüberstellung und geometrische Interpretation des Zulässigkeitsproblems (3.23) aufSeite 42 und des SOI-Problems (3.35), welches eine äquivalente Aussage über die Existenzeiner zulässigen Lösung x liefert. Da beim SOI-Optimierungsproblem jeder Kegelrestrik-tion eine Hilfsvariable sj zugeordnet ist, liefert s eine Aussage darüber, welche Beobach-tungen Restriktionen erzeugen, die von anderen Restriktionen unter einem Schwellwert γnicht unterstützt werden.

letzten Restriktionen. Die originären Eigenschaften bleiben jedoch erhalten, da aufgrund derForm der L1-Zielfunktion diese robust gegen einige größere Werte von sj ist, so dass möglichstviele Elemente von s eine Null annehmen und folglich als Inlier gelten.Es ist zu beachten, dass die SOI-Minimierung eine Lösung x findet, welche von der Mehrzahl

der Restriktionen unterstützt wird, und somit die Elimination aller Ausreißer garantiert. DerFall, dass eine Lösung durch eine Mehrzahl von Ausreißern unterstützt wird, ist i. a. aufgrundder Charakteristik von Ausreißern auszuschließen. Jedoch hat die Minimierung der L1-Norm stattder L0-Pseudonorm von s zur Folge, dass bei einer großen Unzulässigkeit sj eines Ausreißers dieUnzulässigkeit eigentlicher Inlier Werte größer Null annehmen können.Das von Lee et al. (2010) vorgeschlagene zweistufige Verfahren zur Minimierung der L∞-Norm

sieht vor, zunächst mittels eines Schwellwertes γ die SOI-Minimierung (3.35) durchzuführen undanschließend lediglich mit den Inliern die L∞-Lösung im Bisektionsverfahren unter Prüfung desZulässigkeitsproblems (3.23) zu bestimmen.

3.5 Branch-and-Bound im Rotationsraum

Das in Abschnitt 3.1.2 dargestellte Verfahren kann, wie wir in den vorigen Abschnitten gese-hen haben, zur Bestimmung der global optimalen L∞-Lösung eines räumlichen Vorwärtsschnitts,einer Bündelausgleichung oder einer Homographie-Schätzung verwendet werden. Bei der Pro-blemformulierung der Bündelausgleichung haben wir angenommen, dass die Rotationsparameterder äußeren Orientierung bekannt sind, da diese nicht durch eine bilineare Form explizit imunbekannten Parametervektor darstellbar sind. Bei der Schätzung der acht Parameter einer Ho-mographie werden implizit die fünf Parameter der relativen Orientierung und die drei Parameter


der beobachteten Raumebene geschätzt. Die Bestimmung der äußeren Orientierung mittels einesräumlichen Rückwärtsschnitts oder die Bestimmung der relativen Orientierung zwischen zweiKameras können mittels der vorgestellten binären Suche nicht durchgeführt werden. Die Be-stimmung der vollständigen äußeren Orientierung konnte bisher lediglich durch Schätzung derElemente der Projektionsmatrix erfolgen, was dem Ansatz der Lösung einer DLT entspricht (vgl.Hartley und Zisserman 2004, Kap. 7).In diesem Abschnitt wollen wir das von Hartley und Kahl (2009) vorgeschlagene Verfahren

darstellen, welches mittels einer Branch-and-Bound Suche diejenige Kamerarotation findet, wel-che die L∞-Kostenfunktion minimiert. Durch die Suche über alle möglichen Rotationen, könnenOptimierungsprobleme wie bspw. der räumliche Rückwärtsschnitt oder die Bestimmung der rela-tiven Orientierung auf quasikonvexe Probleme mit gegebener Rotationsmatrix reduziert werden,deren L∞-Lösung mittels Standardlösern wie SeDuMi bestimmt werden kann. Bis zum heutigenZeitpunkt stellt dieses Verfahren das einzige Lösungsverfahren dar, welches für diese Problemeeine in Polynomialzeit optimale Lösung unter der L∞-Kostenfunktion liefert.Im Folgenden werden wir ausschließlich den Fall kalibrierter Kameras berücksichtigen, so dass

die Kalibriermatrix als Einheitsmatrix angenommen werden kann. Anstelle eines beobachtetenBildpunktes u auf der Bildebene werden wir den jeweiligen Kamerastrahl v auf der Einheits-sphäre, welche die Richtung vom Projektionszentrum Z zum Objektpunkt U beschreibt, zurProblemformulierung verwenden. Ein Kamerastrahl v lässt sich berechnen durch

v =R(U −Z)

‖R(U −Z)‖2, (3.37)

wobei R die Rotationsmatrix der äußeren Orientierung darstellt.Falls die Rotationsmatrix R unbekannt ist, lässt sich der Vektor R(U −Z) nicht linear in den

unbekannten Parametern von R ausdrücken. Die Residuumsfunktion

Ri(x) = tan∠ (vi,R(U −Z)) =‖vi × vi(x)‖2vTi vi(x)

(3.38)

liefert somit unter Hinzunahme eines konstanten Schwellwertes γ keine konvexe Restriktion. Esist in diesem Zusammenhang wichtig zu bemerken, dass, falls die Rotationsmatrix R bekannt ist,die Größen U und Z mittels des in Abschnitt 3.1.2 beschriebenen Verfahren bestimmbar sind.Die Bestimmung der unbekannten Rotationsmatrix kann, wie es in Hartley und Kahl (2009)

gezeigt wurde, durch eine Branch-and-Bound Suche über alle möglichen Rotationen durchgeführtwerden. Jede mögliche Kamerarotation kann als dreidimensionaler Vektor dargestellt werden,welcher die Richtung der Rotationsachse r und die Länge des Rotationswinkels α ≤ π besitzt.Der dreidimensionale Suchraum ist folglich auf das Innere und dem Rand einer Kugel B3

π mitdem Radius π im R3 beschränkt. Die Kugel B3

π kann durch den Würfel C3π = [−π, π]3 mit der

halben Seitenlänge π im R3 eingeschlossen werden (vgl. Abbildung 29(a)). Diese Repräsentationist zwar redundant, da Punkte außerhalb von B3

π die gleichen Rotationen beschreiben wie Punkteinnerhalb von B3

π, jedoch stellt dies kein Problem dar, wie wir später sehen werden.Da es unmöglich ist, alle Rotationen in endlicher Zeit auszuwerten, unterteilen wir den gesamten

Suchraum in kubische Blöcke, wobei jeder Block Dj eine Teilmenge aller möglichen Rotationenenthält. Diese Aufspaltung entspricht dem so genannten Branch-Schritt. Der Würfel C3

π eignetsich auf Grund seiner kubischen Form für eine einfache Einteilung in kubische Blöcke Dj mit derhalben Seitenlänge σ (vgl. Abbildung 29(b)). Das auf den verkleinerten Suchraum Dj begrenzteOptimierungsproblem lautet dann

minimiereR∈Dj ,x

Nmaxi=1

Ri(x), i = 1, ..., N. (3.39)


B3

p

Dj

p

p

B3

p

Dj

p

B3p

Dj

p

C3p

(a) Der Würfel C3π schließt die Kugel

B3π vollständig ein.

R

s

s

Dj

(b) Ein kubischer Block Dj besitzt diehalbe Seitenlänge σ.

Abbildung 29: Darstellung des Rotationsraumes B3π, worin jede mögliche Rotation durch ihre Winkel-

Achsen-Repräsentation eindeutig darstellbar ist. Durch die Eingrenzung durch den WürfelC3π beschreiben einige Punkte außerhalb von B3

π die gleiche Rotation wie innerhalb vonB3π, jedoch ermöglicht diese Menge eine praktikable Einteilung in kubische Teilblöcke Dj .

Anschließend wird im Bound-Schritt für jede Teilmenge Dj bestimmt, ob in ihr eine Rotationexistieren kann, welche eine Lösung liefert, die geringere Kosten als γmin erzeugt. Zur Beantwor-tung dieser Frage formulieren wir das Optimierungsproblem (3.39) in ein konvexes Zulässigkeits-problem um. Hierzu bestimmen wir zunächst die Rotationsmatrix R aus dem Mittelpunkt einesWürfels Dj , wobei Blöcke, die keinen Punkt des B3

π enthalten, ausgeschlossen werden können. ImZulässigkeitstest verwenden wir nun R als konstante Rotation und γmin als das maximal zulässigeResiduum. Um alle Rotationen in Dj zu berücksichtigen, führen wir eine Unschärfe rD für denSchwellwert γmin ein:

∠(vi,R(U i −Z)) ≤ ∠(vi, R(U i −Z)) + ∠(R(U i −Z), R(U i −Z)) (3.40)

≤ γmin + d∠(R, R) (3.41)≤ γmin + rD. (3.42)

Hierbei beschreibt d∠(R, R) den Winkel θ, der Werte im Bereich 0 ≤ θ ≤ π der Rotation RR−1

annehmen kann. Mit dieser Restriktion gibt ein Zulässigkeitstest darüber Auskunft, ob es imRahmen dieser Unschärfe möglich ist, dass mittels einer Rotation in Dj eine Lösung existiert,die geringere Kosten als γmin erzeugt. Zur Festlegung von rD kann sich die folgende Eigenschaftzu Nutze gemacht werden: Die größte Winkeldistanz zwischen allen Rotationen im Block Dj zuder Rotation R

rD = maxDj

d∠(R,RDj ) (3.43)

ist stets kleiner oder gleich groß wie die euklidische Distanz zwischen den jeweiligen Vektorender Rotationsachsen- und Rotationswinkel-Repräsentation. Somit gilt stets die Ungleichung

rD ≤√

3σ. (3.44)

Hartley und Kahl (2009) führen den Beweis für diese Aussage über die entsprechende vier-


dimensionale Quaternionen-Repräsentation, welche zu der dreidimensionalen Rotationswinkel-und Rotationsachsen-Repräsentation durch eine mitteabstandstreuen Azimutalprojektion(cos α2 , sin

α2 r) 7→ αr in Relation steht. Bei dieser Projektion entstehen solche Verzerrungen, wie

bei der Abplattung der oberen Hälfte eines durchgeschnittenen Tennisballs, was zu der Unglei-chung (3.44) führt.Mittels dieser Eigenschaft kann nun für jeden Block überprüft werden, ob die zu minimierende

Kostenfunktion einen Wert kleiner γmin mit einer Rotation aus Dj annehmen kann. Die ent-sprechende Formulierung des Zulässigkeitstests werden wir für den räumlichen Rückwärtsschnittund die Bestimmung der relativen Orientierung in den folgenden Abschnitten 3.6 und 3.7 explizitdarstellen.Die Branch-and-Bound-Schritte werden iterativ auf die Blöcke Dj fortgesetzt, welche den Zu-

lässigkeitstest bestehen, so dass eine gefundene Lösung mit den geringsten Kosten zu einer immergenaueren Approximation der optimalen Lösung wird. Dieses Verfahren wird abgebrochen, so-bald die halbe Seitenlänge eines Blocks eine vorgegebene Größe ε unterschreitet, so dass dieL∞-Lösung der Rotationsmatrix mindestens bis auf den Rotationswinkel ε richtig ist.Es ist zu beachten, dass die Kostenfunktion über die Rotationen im B3

π nicht konvex ist undmehrere lokale Minima aufweisen kann. Da das Branch-and-Bound-Verfahren jedoch auf demgesamten Rotationsraum angewendet wird und jedes lokale Minima durch kleinere Blöcke auf-gelöst wird, kann stets das global minimale γmin identifziert werden. Das angewendete Branch-and-Bound-Verfahren ist im Algorithmus 4 dargestellt.

3.6 Der räumliche Rückwärtsschnitt

Die Bestimmung der äußeren Orientierung kalibrierter Kameras mittels beobachteter Richtun-gen zu Objektpunkten, deren Koordinaten bekannt sind, wird als räumlicher Rückwärtsschnittbezeichnet. Im Folgenden seien i = 1, ..., N solcher Objektpunkte U i durch die Kamerastrahlenvi beobachtet worden. Die zu bestimmende äußere Orientierung enthält die KameratranslationZ und die Kamerarotationsmatrix R . Das zu lösende L∞-Optimierungsproblem lautet

minimiereR ,Z

Nmaxi=1

∠(vi,R(U i −Z), i = 1, ..., N . (3.45)

Dieses Optimierungsproblem des räumlichen Rückwärtsschnitt kann mittels des in Ab-schnitt (3.5) skizzierten Branch-and-Bound-Verfahrens gelöst werden. Das in diesem Verfahrenfür die iterativ verkleinerten Suchräume Dj zu lösende Zulässigkeitsproblem lautet

findeR ,Z

Z

u.d.N. R ∈ Dj

∠(vi,R(U i −Z)) ≤ γmin, i = 1, ..., N ,

(3.46)

welches in dieser Form jedoch nicht gelöst werden kann, da die unbekannten Rotationsparameternicht in einer konvexen Funktion darstellbar sind. Ein etwas unschärferes, aber lösbares Problemlautet mit festem R aus dem Mittelpunkt von Dj

finde Z

u.d.N. ∠(vi,R(U i −Z)) ≤ γmin +√

3σ, i = 1, ..., N .(3.47)

Falls ein zulässiges Z existiert, so ist die Rotationsmatrix R bis auf maximal den Rotationswinkel√3σ die Rotationsmatrix R , welche mit Z ein kleineres maximales Residuum als γmin erzeugt.

3.6. Der räumliche Rückwärtsschnitt 53

Algorithmus 4 : Branch-and-Bound Verfahren zur Rotationsbestimmung

Daten :v . . . beobachtete Kamerastrahlenf0(x,R) . . . L∞-Kostenfunktionx(0) . . . beliebig gute Startlösungκ . . . in jeder Iteration wird ein zulässiger Wüfel in κ3 Teilwürfel zerlegtε . . . Maximale Abweichung der Lösung zur optimalen Lösung mit ε > 0

Ergebnis :x . . . optimale Lösung bzgl. L∞-KostenfunktionR . . . optimale Rotationsmatrix bzgl. L∞-Kostenfunktion

// Optimale Lösung durch beliebige Startlösung initialisieren1

R := I 3, x := x(0);2

// Bestimme Kosten der Startlösung3

γmin := f0(x, R) ;4

// halbe Seitenlänge eines Würfels5

σ(0) = π/κ;6

// Anzahl Iterationen die für eine bis auf ε richtige Lösung benötigt werden7

νmax = dlogκ (2π/ε)e;8

for ν = 1 : νmax do9

σ(ν) = σ(ν−1)/κ;10

Teile jeden zulässigen Würfel D(ν−1)j in κ3 Teilwürfel D(ν)

j ;11

for j = 1 : anzahl(Dj) do12

// Bestimme Rotationsmatrix aus Mittelpunkt rj = αjrj13

Rj = I 3 + sinαjS(rj) + (1− cosαj)S(rj)2;14

// Falls Würfel Dj Schnittmenge mit B3π hat15

if αj −√

3σ(ν) ≤ π then16

Löse Zulässigkeitsproblem: Existiert eine Rotation in Dj ,17

unter welcher eine zulässige Lösung xj ein kleineresmaximales Residuum als γmin erzeugt?

if zulässige Lösung xj existiert then18

γj = f0(xj ,Rj);19

if γj ≤ γmin then20

R := R ;21

x := xj ;22

εmin := γj ;23

end24

Merke Block D(ν)j für nächste Iteration ν + 1;25

end26

end27

end28

end29

return x, R30


Im Grunde entspricht das Zulässigkeitsproblem (3.47) dem Zulässigkeitsproblem des räumli-chen Vorwärtsschnitts (3.22) auf Seite 41, was durch Umformulierung deutlich wird:

finde x

u.d.N. ||Aix+ bi||2 − (γmin +√

3σ)(cTi x+ di) < 0, i = 1, ..., N.(3.48)

mit x = Z sowie

Ai3×3

= −S(vi)R, bi3×1

= S(vi)RU i, cTi1×3

= −vTi R und dj1×1

= vTi RU i .

Dieses Problem kann folglich in analoger Weise als Second-order Cone Programm gelöst werden.

3.7 Relative Orientierung

Die gegenseitige Orientierung zweier Kameras wird als relative Orientierung bezeichnet. Siewird durch eine Rotationsmatrix R und einen Translationsvektor t beschrieben. Da es sich beider relativen Orientierung um ein aus Richtungen rekonstruiertes photogrammetrisches Modellhandelt, ist der Maßstab von t beliebig.Wir behandeln wieder den Fall kalibrierter Kameras: Es seien i = 1, ..., N korrespondieren-

de Kamerastrahlen vi ↔ v′i beobachtet worden. Die Bedingung, dass sich die Kamerastrahlenschneiden, kann durch die projektive Koplanaritätsbedingung

vTi Ev′i = 0 (3.49)

beschrieben werden. Eine direkte Lösung für die so genannte Essentielle Matrix E liefert bspw. der5-Punkte-Algorithmus nach Nistér (2004), aus welcher anschließend die relative Orientierungextrahiert werden kann. Hierbei sind bis zu zehn verschiedene Lösungen möglich, was deutlichzeigt, dass dieses Problem weder konvex noch quasikonvex ist, da der 5-Punkte-Algorithmus eineexakte Lösung liefert, welche sowohl unter der L2- als auch unter der L∞-Kostenfunktion Nullist.Das durch Hartley und Kahl 2009 vorgeschlagene Verfahren zur Bestimmung der L∞-

Lösung der relativen Orientierung ist das erste Verfahren, welches eine im statistischen Sinneoptimale Lösung liefert. Ungleich dem Ansatz von Nistér (2004) basiert dieses jedoch auf derResiduumsfunktion (3.38) und nicht auf der Koplanaritätsbedingung (3.49).Im Grunde stellt das Problem eine Bündelausgleichung mit zwei Kameras dar. Das zu lösende

L∞-Optimierungsproblem lautet

minimiereRj ,Zj

maxi,j

∠ (vij ,Rj(U i −Zj)) , i = 1, ..., N und j = 1, 2 . (3.50)

Zur Behebung des Datumdefekts kann das Objektsystem in der ersten Kamera gelagert werden,so dass R1 = I 3 und Z1 = 03 sind. Die äußere Orientierung der zweiten Kamera mit derRotationsmatrix R und dem Translationsvektor Z beschreibt dann die relative Orientierung derzweiten Kameras zur ersten, bei welcher wir im Folgenden den Index weg lassen. Die unbekanntenObjektpunkteU i stellen Modellparameter dar, die zur Formulierung der Restriktionen notwendigsind, jedoch bei der Bestimmung der relativen Orientierung nicht von Interesse sind.Das Optimierungsproblem kann ebenfalls mittels des in Abschnitt (3.5) skizzierten Branch-

and-Bound-Verfahrens gelöst werden. Das für die iterativ verkleinerten Suchräume Dj zu lösende

3.7. Relative Orientierung 55

Zulässigkeitsproblem lautet

findeR ,Z

Z

u.d.N. R ∈ Dj

∠ (vi,U i) ≤ γmin

∠ (v′i,R(U i −Z)) ≤ γmin, i = 1, ..., N .

(3.51)

Ein etwas unschärferes aber lösbares Problem mit festem R aus dem Mittelpunkt von Dj lautet

finde Zu.d.N. ∠ (vi,U i) ≤ γmin

∠(v′i,R(U i −Z)

)≤ γmin +

√3σ, i = 1, ..., N .

(3.52)

Zu beachten ist hier, dass die erste Restriktion mit der des Problems (3.51) exakt übereinstimmtund die zweite Restriktion mit der Unschärfe

√3σ abgeschwächt worden ist, um alle Rotationen

R ∈ Dj zu berücksichtigen. Falls ein zulässiges Z existiert, so ist die Rotationsmatrix R bisauf maximal den Rotationswinkel

√3σ diejenige Rotationsmatrix R , welche mit Z ein kleineres

maximales Residuum als γmin erzeugt.Im Grunde entsprechen die Kegelrestriktionen des (3.52) denen, welche sich bei der Bünde-

lausgleichung bei bekannten Rotationen ergeben (vgl. Residuumsfunktion (3.29) auf Seite 44).Durch Umformulierung erhalten wir das Zulässigkeitsproblem

finde x

u.d.N. ||Ai1xi + bi1||2 − γmin(cTi1xi + di1) < 0

||Ai2xi + bi2||2 −(γmin +

√3σ)(cTi2xi + di2

)< 0, i = 1, ..., N.

(3.53)

mit xi = [U i;Z] und x = [U1; . . . ;UN ;Z] sowie

Ai13×6

= [S(vi) 03] , bi13×1

= 03, cTi11×6

=[vTi 0T3

], di1

1×1= 0 und

Ai23×6

=[S(v′i)R −S(v′i)R

], bi2

3×1= 03, cTi2

1×6=[v′i RT −v′i RT

], di2

1×1= 0,

welches mittels des in Abschnitt 3.1.2 dargestellten Verfahren als Second-order Cone Programmgelöst werden kann.Da der Maßstab der Kameratranslation Z nicht eindeutig ist, kann zusätzlich eine Restrik-

tion eingeführt werden oder dem Lösungs-Algorithmus die zahlenmäßige Festlegung überlassenwerden.

57

4. Experimente

In diesem Abschnitt werden wir die vorgestellten Verfahren zur Lösung photogrammetrischerOptimierungsprobleme durch Minimierung der L∞-Kostenfunktion mittels simulierter Daten-sätze untersuchen. In Abschnitt 4.1 werden wir zum einen die unter der L2- und der L∞-Norm minimierten Residuen betrachten und zum anderen die Genauigkeit der L2-Lösung desräumlichen Vorwärtsschnitts, der Homographie-Schätzung und der Bündelausgleichung bei be-kannten Rotationen mit der jeweiligen L∞-Lösung vergleichen. Anschließend untersuchen wirdie SOI-Minimierung zur Detektion von Ausreißern in Abschnitt 4.2 auf ihre Leistungsfähig-keit untersuchen. In Abschnitt 4.3 betrachten wir abschließend das implementierte Branch-and-Bound-Verfahren zur Bestimmung der L∞-Lösung der äußeren Orientierung beim räumlichenRückwärtsschnitt sowie der relativen Orientierung bei beobachteten korrespondierenden Punk-ten betrachten.

Hinweise zur Implementierung

Zur Lösung der konvexen Optimierungsprobleme verwenden wir das Open-Source-Softwarepaket SeDuMi in der Version 1.38. Die simulierten Szenen und Experimente wurdenin Matlab implementiert. Als Standardwerte bei der Bisektion verwenden wir die• maximale Anzahl Iterationen maxiter = 10• maximale Abweichung zur richtigen Lösung ε = 10−6

• das Suchintervall [γmin, γmax] = [0, 3] pel.Vor der Ausführung des Bisektionsverfahrens wird mittels eines Zulässigkeitstest überprüft, ob

eine Lösung unter dem übergebenen γmax existiert. Falls dies nicht der Fall ist, wird γmax solangeum den Faktor Zwei vergrößert, bis eine zulässige Lösung existiert. Das maximale Residuum unterdieser Lösung wird dann als γmax im Bisektionsverfahren verwendet.Die Bestimmung der L2-Lösung erfolgt mittels eines Gauß-Markov-Modells, welches auf der

so genannten minimalen Repräsentation projektiver Größen basiert (vgl. Förstner 2010). ZurInitialisierung der iterativen Minimierung des lineares Ersatzmodells wird die L∞-Lösung alsNäherungslösung verwendet.

4.1 Vergleich der L∞-Lösung mit der L2-Lösung

Zur Überprüfung der statistischen Eigenschaften der L∞-Lösung, welche mittels der vorgestell-ten Verfahren bestimmt wird, wenden wir die implementierten Verfahren auf simulierte Datenan. Die Ergebnisse werden wir vergleichend denen der L2-Lösung gegenüberstellen.Wir werden zum einen die bei der Lösung des räumlichen Vorwärtsschnitts unter der L2-

und der L∞-Norm minimierten Residuen betrachten. Da sowohl die Bündelausgleichung mitbekannten Rotationen als auch die Homographie-Schätzung mittels desselben Verfahrens gelöstwerden, gelten die für den räumlichen Vorwärtsschnitt dargestellten Erkenntnisse in analogerWeise auch für die anderen Verfahren.Zum anderen werden wir die Genauigkeit der L∞-Lösung mit der L2-Lösung vergleichen. Hierzu

verwenden wir eine Monte-Carlo Simulation, da die L∞-Kostenfunktion innerhalb eines Bisek-tionsverfahrens minimiert wird und keine geschlossene Formel zur Bestimmung der L∞-Lösungexistiert, so dass es schwierig ist, eine Aussage über die Qualität der Lösung zu treffen.

8Herunterladbar auf der Projekt-Webseite: http://sedumi.ie.lehigh.edu; letzter Zugriff am 5. November 2011.

http://sedumi.ie.lehigh.edu

58 4. Experimente

Abbildung 30: Darstellung der generierten Szene: Auf einer Kugel sind 170 Kameras platziert, welche aufihren Mittelpunkt ausgerichtet sind. Im Mittelpunkt befindet sich ein Würfel, in welchem27 Objektpunkte gitterförmig angeordnet sind. Jeder Objektpunkt wird als Bildpunkt injeder Kamera abgebildet, sodass 4590 berechnete Bildpunkte vorliegen.

4.1.1 Der räumliche Vorwärtsschnitt

Zur Erzeugung einer hohen Redundanz betrachten wir eine Szene, in welcher 27 Objektpunktevon 170 Kameras beobachtet werden. Die Kameras sind auf einer Kugel um diese Objektpunkteverteilt (vgl. Abbildung 30). Die auf der Bildebene abgebildeten Objektpunkte werden durch zu-fällige Abweichungen verrauscht und dienen als beobachtete Bildpunkte. Hierzu addieren wir aufjede Koordinate der 4590 generierten Bildpunkte eine normalverteilte Abweichung ε ∼ N(0, σ2)mit σ = 3 pel.Die Redundanz beträgt bei den 27 zu bestimmenden Objektpunkten und den 4590 beob-

achteten Bildpunkten r = 2 · 4590 − 3 · 27 = 9099, es liegt demnach ein hoch redundantesOptimierungsproblem vor. Wir bestimmen zunächst die L∞-Lösung innerhalb des Bisektions-verfahrens, welches abgebrochen wird, sobald die optimale Lösung γ bis auf ε = 10−6 richtigbestimmt ist. Anschließend bestimmen wir die L2-Lösung, wobei die L∞-Lösung als Näherungs-lösung zur Linearisierung verwendet wird. Auch hier iterieren wir solange, bis der betragsmäßiggrößte Beobachtungszuschlag kleiner als 10−6 ist.Da wir das Residuum als die euklidische Distanz zwischen dem beobachten Bildpunkt und der

in die Bildebene projizierten Lösung definiert haben, stellen wir sowohl die Residuen der L∞-als auch der L2-Lösung in dieser Form dar.In Abbildung 31 sind die unter der L2-Lösung resultierenden Residuen in einem Histogramm

und zur besseren visuellen Überprüfung, ob die Residuen der Normalverteilung folgen, in einemWahrscheinlichkeitsnetz dargestellt. Die Residuen zeigen im Wahrscheinlichkeitsnetz ein linearesVerhalten und sind daher näherungsweise normalverteilt. Der Mittelwert der Residuen ist nichtsignifikant von Null verschieden und der posteriori Varianzfaktor liegt näherungsweise bei Eins,bestätigt also das stochastische Modell der generierten Daten. Die L2-Lösung stellt also eineerwartungstreue Schätzung mit minimaler Varianz dar.Die unter der L∞-Lösung resultierenden Residuen sind im Histogramm in Abbildung 32 dar-

gestellt. Es ist zu erkennen, dass die L∞-Lösung eine ähnliche Verteilung der Residuen wie dieL∞-Lösung erzeugt. Anhand des Wahrscheinlichkeitsnetzes der Normalverteilung ist jedoch zuerkennen, dass die Residuen nicht normalverteilt sind. Über einen weiten Bereich des Wahr-scheinlichkeitsnetzes zeigen die Residuen zwar ein nahezu lineares Verhalten, an den Flankenjedoch nicht. Dieses Verhalten ist bei der Minimierung normalverteilter zufälliger Fehler unterder L∞-Norm zu erwarten, da hierdurch die Wahrscheinlichkeit der Residuen unter einer sym-

4.1. Vergleich der L∞-Lösung mit der L2-Lösung 59

−10 −5 0 5 100

100

200

300

400

500

Residuen in Pixel

Häu

figke

it

−10 −5 0 5 10

0.0010.0030.01 0.02 0.05 0.10 0.25

0.50

0.75 0.90 0.95 0.98 0.99

0.9970.999

Residuen in Pixel

Wah

rsch

einl

ichk

eit

Abbildung 31: Darstellung der Verteilung der Residuen in einem Histogramm (links) und in einem Wahr-scheinlichkeitsnetz der Normalverteilung mit N(0, 32) (rechts) nach Minimierung der L2-Kostenfunktion. Die Residuen sind normalverteilt.

−10 −5 0 5 100

100

200

300

400

500

Residuen in Pixel

Häu

figke

it

−10 −5 0 5 10

0.0010.0030.01 0.02 0.05 0.10 0.25

0.50

0.75 0.90 0.95 0.98 0.99

0.9970.999

Residuen in Pixel

Wah

rsch

einl

ichk

eit

Abbildung 32: Darstellung der Verteilung der Residuen in einem Histogramm (links) und in einem Wahr-scheinlichkeitsnetz der Normalverteilung mit N(0, 32) (rechts) nach Minimierung der L∞-Kostenfunktion. Die Residuen sind nicht normalverteilt, jedoch näherungsweise.

metrischen Gleichverteilung mit unterer und oberer Grenze maximiert wird (vgl. Abschnitt 2.2).Die Verteilung der Residuen wird daher an den Flanken gestutzt, da die Normalverteilung dortweniger Wahrscheinlichkeitsmasse aufweist als die Gleichverteilung.

Auswirkung auf die Genauigkeit der Lösung

Im Folgenden untersuchen wir die Auswirkung auf die Genauigkeit der Lösung, wenn die zu-fälligen Fehler normalverteilt sind, die Residuen jedoch unter der L∞-Norm minimiert werden.Da die L∞-Kostenfunktion innerhalb eines Bisektionsverfahrens minimiert wird und keine ge-schlossene Formel zur Bestimmung der L∞-Lösung existiert, ist es schwierig, Aussagen über dieQualität der Lösung zu treffen. Zudem müssten die geometrischen Ungleichungsrestriktionen,

60 4. Experimente

0 1 2 3 40

0.2

0.4

0.6

0.8

1

1.2

1.4

σ in Pixel

Pun

ktfe

hler

in M

eter

n

Helmertscher Punktfehler (L∞)

Helmertscher Punktfehler (L2)

Max. Abweichung (L∞)

Max. Abweichung (L2)

(a) zufällige Abweichung ε ∼ N(0, σ2)

0 2 4 6 8 100

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

σ in Pixel

Pun

ktfe

hler

in M

eter

n





(b) zufällige Abweichung ε ∼ U(−σ, σ)

Abbildung 33: Darstellung des mittels einer Monte-Carlo Simulation bestimmten Helmertschen Punkt-fehlers der L2- und L∞-Lösung eines räumlichen Vorwärtsschnitts, sowie der maximalenAbweichung beider Lösungen zum wahren generierten Objektpunkt. Die generierte Szeneist im Text beschrieben. Die zufälligen Abweichungen, welche zum Verrauschen der ge-nerierten Bildpunkte auf die Bildpunktkoordinaten hinzu addiert wurden, wurden einmalunter der Normalverteilung N(0, σ2) (a) und einmal unter der Gleichverteilung U(−σ, σ)(b) generiert.

welche das Innere-Punkte-Verfahren bei der Lösung maßgeblich beeinflussen, bei einer theore-tischen Genauigkeitsaussage berücksichtigt werden. Aufgrund dieser Unzulänglichkeiten werdenwir im Folgenden Genauigkeitsaussagen mittels einer Monte-Carlo Simulation ableiten.Wir verwenden die gleiche Szene, wie in Abbildung 30, jedoch mit nur 50 Kameras und nur

einem Objektpunkt, welcher sich im Mittelpunkt der Kugel befindet. Mittels eines Zufallsgenera-tors erzeugen wir die verrauschten Beobachtungen 1000 Mal mit normalverteilten Abweichungenund lösen den räumlichen Vorwärtsschnitt jeweils unter Minimierung der L2- und der L∞-Norm.Aus der Verteilung der 1000 verschiedenen Schätzungen bestimmen wir die empirische Kovari-anzmatrix aus allen L2- und L∞-Lösungen.Die dargestellte Monte-Carlo Simulation führen wir für verschiedene Standardabweichungen

σ = 0.2, 0.4, 0.6, ..., 4 pel durch, unter welchen die Beobachtungen verrauscht werden. Hierdurchkann die Genauigkeit über variierende Rauschniveaus betrachtet werden. In Abbildung 33(a)ist der Helmertsche Punktfehler, welcher sich aus der Spur der Kovarianzmatrix ergibt, überdie variierenden Standardabweichungen dargestellt. Es ist zu beobachten, dass der Punktfehlerder L2- und L∞-Lösung linear mit steigender Standardabweichung anwächst, wobei der L∞-Punktfehler, wie zu erwarten, etwas stärker anwächst.Zudem ist in Abbildung 33(a) die maximale Abweichung der L∞-Lösung und der L2-Lösung

zum wahren generierten Objektpunkt dargestellt. Auch diese wächst mit steigendem Rauschennäherungsweise linear an. Da normalverteilte Beobachtungsabweichungen auch extreme Werteannehmen können und sich die L∞-Lösung stets nach der größten Beobachtungsabweichungrichtet, beschreibt die entsprechende Kurve einen zackigeren Verlauf. Der Einfluss auf die L2-Lösung ist hingegen nicht so stark, wie durch den glatteren Verlauf erkennbar ist.Falls die zufälligen Fehler einer Gleichverteilung folgen, ist die Qualität der L∞-Lösung eine

bessere Schätzung als die der L2-Lösung. Dies wird in Abbildung 33(b) deutlich. Die Ergeb-nisse wurden durch die Ausführung der oben beschriebene Monte-Carlo Simulation in analoger


Weise ermittelt, jedoch wurden die Beobachtungsabweichungen nicht mittels einer Normalver-teilung generiert, sondern mittels der symmetrischen Gleichverteilung U(−σ, σ), so dass σ diebetragsmäßig größte Abweichung darstellt.Es ist jedoch darauf hinzuweisen, dass sich die Ergebnisse nicht in hohem Maße unterscheiden.

Lediglich die Anwesenheit von extremen Beobachtungsabweichungen beeinflusst die L∞-Lösungin besonderem Maße. Relativierend muss jedoch angemerkt werden, dass auch die L2-Lösungnicht robust gegen solche Ausreißer reagiert. Wir werden eine bei der Minimierung der L∞-Kostenfunktion notwendige Ausreißerdetektion in Abschnitt 4.2 untersuchen.

Grund für ähnliche Lösung

In Abbildung 34 ist die L2- und L∞-Kostenfunktion beim ebenen Vorwärtsschnitt unter ver-schiedenen Kamerakonfigurationen als Konturplot dargestellt. Es ist zu erkennen, dass sich dieNiveaulinien unter den verschiedenen Kamerakonfigurationen sehr ähnlich verhalten. In den ers-ten beiden Konfigurationen liegt kein überbestimmtes Problem vor und es existiert jeweils eineexakte L2- und L∞-Lösung, unter welcher die jeweilige Kostenfunktion Null ist. Je spitzer derWinkel wird, unter welchem sich die Kamerastrahlen schneiden, desto niedriger werden die Kos-ten sowohl in der L2- als auch in der L∞-Kostenfunktion in Richtung der positiven y-Achse.Das Genauigkeitsniveau, mit welchem der Objektpunkt bestimmt werden kann, wird daher inähnlicher Weise durch die Kamerakonfiguration beeinflusst.In der dritten Konfiguration wird der Objektpunkt zudem von einer dritten Kamera beob-

achtet, so dass keine Lösung existiert, unter welcher die entsprechende Kostenfunktion Null ist.Die Niveaulinien besitzen auch hier in der L2- und L∞-Kostenfunktion eine ähnliche Form, sodass sich zum einen die optimalen L2- und L∞-Lösungen nicht wesentlich unterscheiden undzum anderen das Genauigkeitsniveau ähnlich ist. Je schwerer die Schnittbedingungen der Ka-merastrahlen jedoch verletzt werden, desto größer wird die Diskrepanz zwischen der L2- undL∞-Lösung, da die Abweichungen bei der L2-Norm quadratisch in die Kostenfunktion einge-hen und die L∞-Norm minimal ist, wo die größte Abweichung am kleinsten ist. Daher wird dieL∞-Lösung in noch höheren Maße von Ausreißern beeinflusst, als die L2-Norm.

4.1.2 Homographie-Schätzung und Bündelausgleichung bei bekannten Rotationen

Zur Überprüfung, ob die oben genannten Eigenschaften der L∞-Lösung des räumlichen Vor-wärtsschnitts auch für die L∞-Lösungen gelten, welche die implementierten Lösungsverfahrenzur Bestimmung der Homographie und der Lösung einer Bündelausgleichung bei bekannten Ka-merarotationen liefern, werden wir auch diese Verfahren mittels einer Monte-Carlo Simulationuntersuchen. Wir beginnen mit der Homographie-Schätzung, anschließend werden wir die Bün-delausgleichung behandeln.

Homographie-Schätzung

Wir haben zum Testen der Homographie-Schätzung eine Szene konstruiert, in welcher 20 aufeiner Raumebene liegende Objektpunkte als Bildpunkte auf der Bildebene zweier gegenseitig ver-drehter Kameras abgebildet werden (vgl. Abbildung 35(b)). Die gerechneten Bildpunkte verrau-schen wir wie oben mit verschiedenen Standardabweichungen σ = 0.1, 0.2, ..., 1 pel und bestim-men mittels einer Monte-Carlo Simulation unter 1000 Wiederholungen für jedes Rauschniveaueine L2- und eine L∞-Lösung aus den korrespondierenden Punkten. Die aus der Verteilung derjeweiligen 1000 Lösungen abgeleitete Kovarianzmatrix dient anschließend zur Bestimmung desHelmertschen Punktfehlers, welcher in Abbildung 35(a) dargestellt ist. Zudem ist dort die größteAbweichung zwischen den Lösungen und dem wahren generierten 8×1-Lösungsvektor aufgetra-gen. Es ist auch hier zu beobachten, dass der Punktfehler der L2- und L∞-Lösung näherungsweise

62 4. Experimente

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

x−Achse

y−A

chse

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

x−Achse

y−A

chse

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

x−Achse

y−A

chse

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

x−Achse

y−A

chse

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

x−Achse

y−A

chse

0 2 4 6 8 100

1

2

3

4

5

6

7

8

9

10

x−Achse

y−A

chse

Abbildung 34: Darstellung der L2-Kostenfunktionen (linke Spalte) und L∞-Kostenfunktionen (rechteSpalte) beim räumlichen Vorwärtsschnitt unter verschiedenen Konfigurationen als Kon-turplot: In der ersten Zeile schneiden sich die Kamerastrahlen in einem nahezu rechtenWinkel, in der zweiten Zeile schneiden sie sich unter einem schleifenden Schnitt. Sowohldie L2- als auch die L∞-Lösung ist unter einem schleifenden Schnitt schlecht bestimmt,die jeweiligen Kostenfunktionen weisen sehr ähnliche Eigenschaften auf.

linear mit steigender Standardabweichung anwächst. Der Punktfehler der L∞-Lösung wächst, wiees aufgrund des normalverteilten Rauschens auf den Beobachtungen zu erwarten ist, etwas stärkeran.


0 0.2 0.4 0.6 0.8 10

10

20

30

40

50

60

70

80

σ in Pixel

Qua

lität

smaß





cam2

cam1

Abbildung 35: Darstellung des mittels einer Monte-Carlo Simulation bestimmten Helmertschen Punkt-fehlers der L2- und L∞-Lösung einer Homographie-Schätzung, sowie der maximalen Ab-weichung beider Lösungen zum wahren generierten 7×1-Lösungsvektor (links). Das gene-rierte Rauschen auf den Beobachtungen folgt der Normalverteilung N(0, σ2). Zudem istdie generierte Szene dargestellt (rechts).

Jedoch sind die L2-Lösungen von den L∞-Lösungen hinsichtlich ihrer Qualität nicht wesentlichverschieden, wie es auch bei anderen getesteten Aufnahmekonfigurationen durchgehend der Fallwar. Kahl und Hartley (2008) erhielten das gleiche Ergebnis bei der Untersuchung des RMS-Fehlers, welcher aus den Differenzen zwischen den transformierten und beobachteten Bildpunktenin der Bildebene der zweiten Kamera berechnet wurde. Die L∞-Lösung, die L2-Lösung und sogardie Lösung eines linearen Algorithmus wiesen nach Anwendung auf einen Realdatensatz einedurchgehend ähnliche Qualität auf.

Bündelausgleichung mit bekannten Rotationen

Zur Untersuchung der Bündelausgleichung mit bekannten Rotationen wurden 18 Objektpunktegeneriert, die von einer Kamera von 16 Standpunkten aus beobachtet wurden. Die Trajektorie derKamera entspricht hierbei einer Schleife um die Objektpunkte herum, wie es in Abbildung 36 dar-gestellt ist. Die gerechneten Bildpunkte wurden wieder mit σ = 0.2, 0.4, ..., 3 pel verrauscht undes wurden mittels einer Monte-Carlo Simulation unter 1000 Wiederholungen für jedes Rauschni-veau eine L2- und eine L∞-Lösung bestimmt.Das Koordinatensystem, in welchem sich die zu schätzenden Größen - das sind die unbekannten

Objektpunkte und Kameratranslationen - befinden, ist nur durch die Rotationsmatrizen deräußeren Orientierungen festgelegt, daher muss über die Lage des Ursprungs und die Skalierungverfügt werden. Als Ursprung verwenden wir das Projektionszentrum der ersten Kamera und derMaßstab wird durch die Basislänge zwischen der ersten und zweiten Kamera festgelegt, so dasszum einen Z1 = 03 und zum anderen ||Z2 − Z1||2 = 1 gilt. Bei der L2-Lösung führen wir einefreie Bündelausgleichung durch, welche auf die Näherungswerte der L∞-Lösung aufgefeldert wird.Zur anschließenden Vergleichbarkeit verschieben und skalieren wir die bestimmten Objektpunkteund Kameratranslationen dermaßen durch eine 3D-Translation und einen Skalierungsfaktor, sodass die Lagerung der L2-Lösung identisch zur Lagerung der L∞-Lösung ist.Die aus den 1000 Lösungen abgeleiteten Kovarianzmatrizen der Objektpunkte U i und der

Kameratranslationen Zj dienen zur Bestimmung des Helmertschen Punktfehlers, welcher in Ab-bildung 37 dargestellt ist. Zudem ist dort auch wieder die größte Abweichung zwischen den 1000

64 4. Experimente

Abbildung 36: Darstellung der generierten Szene, auf welcher eine Bündelausgleichung mit bekanntenRotationen zur Minimierung der L∞-Norm angewendet wird. Es werden 18 Objektpunktevon 16 Kamerastandpunkten, welche sich auf einer schleifenförmigen Trajektorie befinden,beobachtet.

Lösungen und dem wahren generierten Lösungsvektor dargestellt. Es ist auch hier zu beobachten,dass sowohl der Punktfehler der L2- als auch der L∞-Lösung näherungsweise linear mit steigen-der Standardabweichung anwächst. Der Punktfehler der L∞-Lösung wächst, wie es auch beimräumlichen Vorwärtsschnitt und der Homographie-Schätzung unter normalverteiltem Rauschender Fall war, etwas stärker an. Zudem sind die maximalen Abweichungen der L∞-Lösungen zuder wahren Lösung teilweise wesentlich größer als die der L2-Lösung.Zur Initialisierung einer L2-Bündelausgleichung, welche genügend gute Näherungswerte zur

Bestimmung eines linearen Ersatzmodells benötigt, scheint die L∞-Lösung grundsätzlich geeignetzu sein, falls keine Ausreißer vorliegen. Die Anfälligkeit gegenüber groben Abweichungen wird anden teilweise hohen maximalen Abweichungen der L∞-Lösungen in Abbildung 37 deutlich.

4.2. Detektierbarkeit von Ausreißern 65

4.2 Detektierbarkeit von Ausreißern

Falls Ausreißer in den Beobachtungen nicht eliminiert werden, so wird die L∞-Lösung grund-sätzlich grob verfälscht, da ein Ausreißer stets das maximale Residuum liefert. Die Anzahl derBeobachtungen, welche dem üblichem Messrauschen unterliegen, wirkt sich dann auf die L∞-Lösung nicht positiv aus. Die L2-Lösung wird durch die Existenz von Ausreißern ebenfalls starkbeeinflusst, da die Residuen quadratisch in die Kostenfunktion eingehen. Eine Robustifzierungder Kostenfunktion oder eine vorangehende Eliminierung der Ausreißer ist daher bei beiden

0 0.5 1 1.5 2 2.5 30

2

4

6

8

10

σ in Pixel

Qua

lität

smaß

in M

eter





(a) Darstellung des Helmertschen Punktfehlers und der maximalen Abweichung der L2- undL∞-Lösungsvektoren von der wahren Lösung, welche alle Objektpunkte U i beinhaltet.

0 0.5 1 1.5 2 2.5 30

2

4

6

8

10

σ in Pixel

Qua

lität

smaß

in M

eter





(b) Darstellung des Helmertschen Punktfehlers und der maximalen Abweichung der L2- undL∞-Lösungsvektoren von der wahren Lösung, welche alle Kameratranslationen Zj beinhaltet.

Abbildung 37: Darstellung des mittels der im Text beschriebenen Monte-Carlo Simulation bestimmtenHelmertschen Punktfehlers der L2- und L∞-Lösung sowohl der Objektpunkte U i 37(a) alsauch der Kameratranslationen Zj 37(b). Zudem ist die maximale Abweichung sowohl der1000 L2- als auch der 1000 L∞-Lösungen zu der wahren Lösung dargestellt. Es wurdenzufällige Abweichungen, welche der Normalverteilung N(0, σ2) folgen, auf die generiertenBildpunktkoordinaten hinzu addiert.

66 4. Experimente

Optimierungsproblemen zwingend notwendig.In diesem Abschnitt untersuchen wir die Leistungsfähigkeit der in Abschnitt 3.4 dargestell-

ten Ausreißerdetektion, welche ein konvexes Optimierungsproblem darstellt. Wir beschränkenuns in diesem Abschnitt auf die Ausreißerdetektion beim räumlichen Vorwärtsschnitt, welcheanschauliche Ergebnisse liefert. Die Ausreißerdetektion bei der Homographie-Schätzung und derBündelausgleichung bei bekannten Rotationen ist durch das gleiche Optimierungsproblem mitjeweils anderen Restriktionen durchführbar und besitzt daher die gleichen Eigenschaften einerSOI-Minimierung. Wir verwenden syntetisch generierte Datensätze, um die Leistungsfähigkeitder Ausreißerdetektion zu untersuchen.

4.2.1 Ausreißerdetektion beim räumlichen Vorwärtsschnitt

Zum Testen der implementierten SOI-Minimierung zur Ausreißerdetektion beim räumlichenVorwärtsschnitt wurde eine Szene generiert, in welcher ein Objektpunkt von zehn Kameras be-obachtet wird. Die Kameras sind auf einem Kreis mit dem Radius von 10 m um den Objektpunktangeordnet. Die gerechneten Koordinaten aller Bildpunkte werden mit σ = 1 pel verrauscht. DieKoordinaten eines Bildpunktes werden durch zufällige Werte im Intervall ±[10, 50] pel gestört, sodass ein Ausreißer vorliegt. Das maximal zulässige Residuum wird mit dem Schwellwert γ = 3 pelfestgelegt. Die Szene ist mit den generierten Kameras, dem Objektpunkt und den durch die Be-obachtungen erzeugten Kegelrestriktionen in Abbildung 38(a) dargestellt.

cam5

cam4

cam6

cam3

cam7

cam2

cam8

cam9

cam1

cam10

(a) Lorentzkegel der generierten Bildpunkte.

1 2 3 4 5 6 7 8 9 100

10

20

30

40

50

60

Bildpunktindex

Rep

roje

ktio

nsfe

hler

in P

ixel

(b) Residuen aller Bildpunkte unter L∞-Lösung.

Abbildung 38: Darstellung der im Text eingeführten Szene, in welcher zehn Kameras einen Objektpunktbeobachten. Die gerechneten Bildpunkte wurden mit σ = 1 pel verrauscht und der Bild-punkt der zweiten Kamera wurde grob verfälscht, so dass sich die zehn resultierendenKegelrestriktionen unter γmax = 3 pel nicht schneiden (a). Die Residuen unter der L∞-Lösung, welche ohne die nach der SOI-Minimierung detektierten Ausreißer bestimmt wur-de, sind in (b) dargestellt. Neben dem zweiten Bildpunkt wurde auch der siebte Bildpunktals Ausreißer identifiziert (rot umkreist), welcher jedoch unter der L∞-Lösung ein Residu-um kleiner als γmax besitzt (rote Linie).

Die Minimierung der Summe der Unzulässigkeiten nach (3.35) auf Seite 48 liefert eine Lösung,die von acht Bildpunkten unterstützt wird und von zwei Bildpunkten nicht. Die Summe derUnzulässigkeiten ist minimal, wenn die durch den zweiten und siebten Bildpunkt aufgestelltenKegelrestriktionen verletzt werden, mit den optimalen Minimierungsvariablen s2 = 0.6014 unds7 = 8.0514. Tatsächlich ist nur der siebte Bildpunkt ein Ausreißer.Anschließend bestimmen wir die L∞-Lösung ohne die detektierten Ausreißer. In Abbil-

4.2. Detektierbarkeit von Ausreißern 67

dung 38(b) sind die unter der Lösung anfallenden Residuen aller Bildpunkte einschließlich derdetektierten Ausreißer (rot umkreist) dargestellt. Es ist zu erkennen, dass der fälschlicherweiseals Ausreißer detektierte siebte Bildpunkt unter dieser Lösung einen geringeren Reprojektions-fehler aufweist, als das für die Ausreißerdetektion maximal zulässige Residuum γmax (rote Linie).Dies zeigt, dass die SOI-Minimierung, welche die L1-Norm der Unzulässigkeiten minimiert, le-diglich eine Approximation der Minimierung der L0-Pseudonorm der Unzulässigkeiten ist, daeine Lösung existiert, unter welcher mit γmax nur eine Restriktion verletzt wird. Es ist an dieserStelle wichtig zu erwähnen, dass jedoch bei allen untersuchten Konfigurationen stets alle Aus-reißer detektiert worden sind und nur einige Inlier als Ausreißer fälschlicherweise identifiziertwurden. Falls der Reprojektionsfehler eines detektierten Ausreißers kleiner als γmax ist, so kannder Bildpunkt bspw. für eine folgende L2-Minimierung wieder verwendet werden.In Abbildung 39 sind die Ergebnisse eines weiteren Experiments zur SOI-Minimierung zur

Ausreißerdetektion dargestellt. Dieses Mal wurden 100 Kameras auf einer Raumebene generiert,welche einen Objektpunkt beobachten. Von den 100 gerechneten Bildpunkten werden 10 % wieoben mit zufälligen gleichverteilten Abweichungen im Intervall ±[10, 50] pel gestört, zu allen an-deren wird ein normalverteiltes Rauschen mit σ = 1 pel hinzu addiert. Die durch die generiertenBildpunkte resultierenden Kegelrestriktionen sind in Abbildung 39(a) dargestellt. In der neben-stehenden Abbildung 39(b) sind die Residuen aller Bildpunkte unter der L∞-Lösung, welcheohne die detektierten Ausreißer bestimmt wurde, dargestellt. Auch hier wurden alle zehn ge-nerierten Ausreißer und einige Inlier als Ausreißer identifiziert (rot umkreist). Die sieben falschidentifizierten Ausreißer besitzen nach der L∞-Optimierung ein Residuum kleiner γmax (rote

(a) Lorentzkegel der generierten Bildpunkte.

0 10 20 30 40 50 60 70 80 90 1000

10

20

30

40

50

60

70

Bildpunktindex

Rep

roje

ktio

nsfe

hler

in P

ixel

(b) Residuen aller Bildpunkte unter L∞-Lösung.

Abbildung 39: Darstellung der im Text eingeführten Szene, in welcher 100 Kameras einen Objektpunktbeobachten. Es werden 100 mit σ = 1 pel verrauschte Bildpunkte berechnet, wobei zehnBildpunkte grob verfälscht werden (a). Die Residuen unter der L∞-Lösung, welche ohnedie 17 identifizierten Ausreißer (rot umkreist) bestimmt wurde, sind in (b) dargestellt. Hierist zu erkennen, dass alle sieben fälschlicherweise als Ausreißer identifizierten Bildpunkteunter der L∞-Lösung ein Residuum kleiner als γmax besitzen (rote Linie).

68 4. Experimente

Linie).Zur statistischen Untersuchung der Leistungsfähigkeit der SOI-Minimierung unter unterschied-

lich großen Ausreißeranteilen, führen wir die Ausreißerdetektion jeweils 1000 Mal durch, wobeidas normalverteilte Rauschen und die gleichverteilten Abweichungen jedesmal erneut zufällig ge-neriert werden. Zudem werden die Bildpunkte, welche durch die groben Abweichungen gestörtwerden, zufällig ausgewählt, so dass der Ausreißeranteil stets 10, 20, 30, 40 oder 50% beträgt.In Abbildung 40(a) ist die mittlere Anzahl der als Inlier identifizierten Bildpunkte gegenüber

dem Ausreißeranteil dargestellt. Bei einem Ausreißeranteil von 10% wurden bspw. im Mittel 86Inlier gefunden. Da die Anzahl der wahren Inlier jedoch 90 aus 100 betrug, wurden näherungs-weise nur 86/90 ≈ 96 % aller wahren Inlier durch die SOI-Minimierung als Inlier bestätigt. Diemittleren Verhältnisse zwischen der Anzahl der identifizierten Inlier zur Anzahl der wahren Inlierin Prozent ist für die verschiedenen Ausreißerraten in Abbildung 40(b) dargestellt. Es ist anhandder Abbildungen deutlich zu erkennen, dass der Anteil der als Ausreißer identifizierten wahrenInlier abhängig von der Größe des Ausreißeranteils ist.

10 20 30 40 500

10

20

30

40

50

60

70

80

90

100

Ausreißeranteil in Prozent

Mitt

lere

Anz

ahl d

er a

ngen

omm

enen

Inlie

r

(a) links

10 20 30 40 500

10

20

30

40

50

60

70

80

90

100

Ausreißeranteil in Prozent

Mitt

lere

s V

erhä

ltnis

zw

isch

enA

nzah

l ide

ntifi

zier

ter

Inlie

r zu

Anz

ahl w

ahre

r In

lier

(b) rechts

Abbildung 40: Darstellung der statistischen Untersuchung der SOI-Minimierung des im Text und in Ab-bildung 39 dargestellten Datensatzes. In (a) ist die mittlere Anzahl der Bildpunkte, wel-che nach 100 Wiederholungen der SOI-Minimierung als Inlier identifiziert wurden, unterverschiedenen Ausreißeranteilen dargestellt. Alle Ausreißer wurden stets als solche identi-fiziert. In (a) ist der mittlere prozentuale Anteil der identifizierten Inlier zu den wahrenInlieren unter verschiedenen Ausreißeranteilen abgebildet.

Zu beachten ist, dass durch die SOI-Minimierung zwar die detektierten Ausreißer einige wahreInlier beinhalten, jedoch wurden in allen Experimenten stets alle wahren Ausreißer detektiert.Zudem ist die SOI-Minimierung mit einem geeigneten Schwellwert γmax nur einmal vor derBestimmung der L∞-Lösung durchzuführen, wobei zur Minimierung kein Bisektionsverfahrennotwendig ist.


4.3 Branch-and-Bound im Rotationsraum

In Abschnitt 3.5 wurde der von Hartley und Kahl (2009) vorgeschlagene Branch-and-BoundAlgorithmus vorgestellt, mit welchem es gelingt, die Rotationsmatrix der äußeren Orientierungbeim räumlichen Rückwärtsschnitt sowie die Rotationsmatrix der relativen Orientierung zu be-stimmen, unter welcher die Residuen unter der L∞-Norm minimal sind. Der implementierteAlgorithmus 4 wurde zur Bestimmung der L∞-Lösung beim räumlichen Rückwärtsschnitt undbei der relativen Orientierung auf einigen synthetisch generierten Datensätzen durchgeführt. Inunserer Implementierung wird jeder zulässige Block Dj in 3×3×3 Teilblöcke unterteilt. AndereUnterteilungen lieferten bis auf kleine numerische Abweichungen stets das gleiche Ergebnis.Die Konvergenzgeschwindigkeit des Algorithmus wird vornehmlich durch die Abdeckung aller

Raumrichtungen durch die beobachteten Kamerastrahlen beeinflusst. Falls gute Schnittbedin-gungen vorliegen, können wesentlich mehr Teilblöcke in einer Iteration ausgeschlossen werden.Die schnellste Konvergenzgeschwindigkeit konnte daher bei omnidirektionalen Kameras erreichtwerden.Im Folgenden werden wir den räumlichen Rückwärtsschnitt und die relative Orientierung zweier

Kameras jeweils auf einer generierten Szene testen und einige Eigenschaften aufzeigen.

4.3.1 Räumlicher Rückwärtsschnitt

Zum Testen des Algorithmus zur Bestimmung der L∞-Lösung des räumlichen Rückwärts-schnitts, haben wir eine Szene mit einer perspektiven Kamera und sechs Objektpunkten, welcheauf der Kamera als Bildpunkte abgebildet werden, generiert (vgl. Abbildung 41). Die Bild-punkte werden anschließend mit σ = 1 pel verrauscht, in Kamerastrahlen umgerechnet und demLösungsalgorithmus 4 übergeben. Zudem übergeben wir κ = 3, so dass in jeder Iteration einzulässiger Würfel in neun Teilwürfel zerlegt wird, die beliebige Startlösung für die Kameratrans-lation x(0) = 03 und die minimale Auflösung der optimalen Lösung mit ε = 1.7 · 10−4, was etwa0.01◦ entspricht.

−50

5 05

10−2

0

2

4

6

8

10

12

y−axis

U3

U6

U2

U5

U1

U4

Abbildung 41: Darstellung der generierten Objektpunkte und der generierten Kamera, deren äußere Ori-entierung durch einen räumlichen Rückwärtsschnitt unter Minimierung der L∞-Norm be-stimmt werden soll.

In Abbildung 42 sind die nach den ersten vier Iterationen zu testenden Teilblöcke im Rotati-onsraum dargestellt, bei welchen es nicht auszuschließen ist, dass dort eine Rotation existiert,unter welcher die L∞-Kostenfunktion einen kleineren Wert annimmt, als unter der bisher bes-

70 4. Experimente

−180° −90° 0° 90° 180°−180°

−90°0°

90°180°

−180°

−90°

0°

90°

180°

rx

ry

r z

(a) 1. Iteration

−180° −90° 0° 90° 180°−180°

−90°0°

90°180°

−180°

−90°

0°

90°

180°

rx

ry

r z

(b) 2. Iteration

−180° −90° 0° 90° 180°−180°

−90°0°

90°180°

−180°

−90°

0°

90°

180°

rx

ry

r z

(c) 3. Iteration

−180° −90° 0° 90° 180°−180°

−90°0°

90°180°

−180°

−90°

0°

90°

180°

rx

ry

r z

(d) 4. Iteration

Abbildung 42: Iterationsweise Darstellung des Rotationsraums nach den ersten vier Branch-and-BoundIterationen. Innerhalb der Teilblöcke befindet sich die Rotation, unter welcher die L∞-Kostenfunktion minimal ist.

ten Lösung. Anhand der Abbildung 42(b) ist deutlich zu erkennen, dass die zu minimierendeKostenfunktion im Rotationsraum weder konvex noch quasikonvex ist, da die Teilblöcke keinezusammenhängende Menge bilden. Die übrig gebliebenen Teilblöcke sind als eine Approximationder Subniveaumenge der L∞-Kostenfunktion, welche unter den Kosten der bisher besten Lösungentsteht, interpretierbar. Somit liegen i. a. mehrere lokale Minima im Rotationsraum vor.In Abbildung 43 sind die Kegelrestriktionen nach der dritten bis sechsten Iteration der bis

dahin besten Lösung im Koordinatensystem der Objektpunkte dargestellt. Sie bieten eine an-schauliche geometrische Interpretation der Minimierung der L∞-Kostenfunktion: Bei der Suchenach der optimalen äußeren Orientierung werden die durch die beobachteten Kamerastrahlen


−5

0

5 0

5

10

15

20

−2

0

2

4

6

8

10

12

U3U3

y−axis

U2U2

U6U6U5U5

U1U1

U4U4

x−axis

z−ax

is

(a) 3. Iteration

−50

5 0

5

10

15

20

−2

0

2

4

6

8

10

12

y−axis

U6U6

U3U3U2U2

U5U5

U1U1

U4U4

x−axis

z−ax

is

(b) 4. Iteration

−50

5 0

5

10

15

20

−2

0

2

4

6

8

10

12

y−axis

U3U3

U6U6

U2U2

U5U5U4U4

U1U1

x−axis

z−ax

is

(c) 5. Iteration

−50

5 0

5

10

15

20

−2

0

2

4

6

8

10

12

y−axis

U3U3

U6U6

U2U2

U5U5

U1U1

U4U4

x−axis

z−ax

is

(d) 6. Iteration

Abbildung 43: Iterationsweise Darstellung der Lorentzkegel, welche als Kegelrestriktionen im Zulässig-keitstest der bis dahin besten Lösung dienen. Die Lorentzkegel der dritten bis sechstenBranch-and-Bound Iteration sind im Koordinatensystem der Objektpunkte dargestellt.

vorgegebenen Kegelrestriktionen dermaßen positioniert, dass diese alle Objektpunkte beinhaltenund alle Lorentzkegel mit einem möglichst minimalen Radius aufgespannt werden.Die Geschwindigkeit des Branch-and-Bound-Verfahrens ist abhängig von der Anzahl der zu tes-

tenden Blöcke im Rotationsraum. Ein Teilblock wird für die weitere Betrachtung ausgeschlossen,wenn die Restriktionen nicht erfüllt werden können. Im Schnitt ergaben sich unter den genanntenEinstellungen pro Iteration etwa sechs zu untersuchende Teilblöcke. Da die Teilblöcke in jederIteration kleiner werden, nimmt auch die Konvergenzgeschwindigkeit zur optimalen L∞-Lösungdrastisch ab, wodurch der Rechenaufwand deutlich ansteigt. Daher ist es notwendig, die Größen-ordnung, mit welcher die optimale Lösung von der bestimmten Lösung übereinstimmen soll, imvorhinein abzuschätzen. Das oben genannte ε = 1.7 ∗ 10−4 wurde in neuen Iterationen erreicht,es mussten insgesamt 60 Zulässigkeitstests gelöst werden.

72 4. Experimente

4.3.2 Relative Orientierung

Analog zum räumlichen Rückwärtsschnitt wollen wir nun das implementierte Verfahren zur Be-stimmung der L∞-Lösung für die relative Orientierung zweier Kameras aus korrespondierendenPunkten betrachten. Zu diesem Zweck haben wir eine Szene mit zwei unterschiedlich orientiertenKameras und neun Objektpunkten generiert, welche auf beiden Kamera als Bildpunkte abgebil-det werden (vgl. Abbildung 44).

−5 0 5 10 15 20 25

−10

0

100

5

10

15

20

25

cam2

U3U6U9

x−axis

U2U5U8

cam1

U1U4

U7

y−axis

z−ax

is

Abbildung 44: Darstellung der generierten Objektpunkte und der generierten Kamera, deren äußere Ori-entierung durch einen räumlichen Rückwärtsschnitt unter Minimierung der L∞-Norm be-stimmt werden soll.

Die Bildpunkte werden wie beim letzten Beispiel mit σ = 1 pel verrauscht, in Kamerastrahlenumgerechnet und dem Lösungsalgorithmus 4 übergeben. Wir übergeben auch hier wieder κ = 3,so dass in jeder Iteration ein zulässiger Würfel in 9 Teilwürfel zerlegt wird. Als Startlösung fürdie Kameratranslation verwenden wir wieder x(0) = 03 und für die minimale Auflösung deroptimalen Lösung ε = 1.7 · 10−4. Zur Festlegung des Datums halten wir die erste Kamera imUrsprung des Koordinatensystems fest und geben die x-Koordinate der Kameratranslation derzweiten Kamera mit 20 vor, so dass Schätzgrößen mit der generierten Szene vergleichbar sind.Die in den ersten vier Iterationen zu testenden Teilblöcke im Rotationsraum sind in Abbil-

dung 45 dargestellt. Anders als beim dargestellten Beispiel des räumlichen Rückwärtsschnittssteigt die Anzahl der zu testenden Teilblöcke in jeder Iteration stark an. In dem dargestelltenBeispiel betrug die Anzahl in der fünften bis zur neunten Iteration 28, 30, 41, 84 und 146.Der Grund für die große Anzahl der zu testenden Teilblöcke liegt zum einen darin, dass Lösun-gen, die weit entfernt von der optimalen Lösung liegen, dennoch relativ kleine Kosten erzeugen,und zum anderen, dass die beobachteten Kamerastrahlen der generierten perspektiven Kameraaufgrund ihrer Schnittbedinungen keine günstigen Restriktionen darstellen. Da die Konvergenz-geschwindigkeit abhängig von der Anzahl der zu testenden Teilblöcke und von der Anzahl derPunktkorrespondenzen sehr langsam sein kann, wurde von Hartley und Kahl 2009 zudem eineMöglichkeit aufgezeigt, wie das durch Lorentzkegel restringierte Zulässigkeitsproblem mit 3n+ 2Optimierungsvariablen, wobie n der Anzahl der Punktkorrespondenzen entspricht, umformuliertwerden kann, so dass dieses in einem linearen Programm mit nur zwei Optimierungsvariablengelöst werden kann. Aufgrund der Aufwendigkeit der Implementation wurde diese Möglichkeitjedoch nicht getestet.In Abbildung 46 sind die Kegelrestriktionen der Zulässigkeitstests, welche in der dritten, vier-

ten, fünften und sechsten Iteration die beste Lösung lieferten, dargestellt. Sie bieten eine an-schauliche geometrische Interpretation der Bestimmung der optimalen L∞-Lösung: Da die erste


−180° −90° 0° 90° 180°−180°

−90°0°

90°180°

−180°

−90°

0°

90°

180°

rx

ry

r z

(a) 1. Iteration

−180° −90° 0° 90° 180°−180°

−90°0°

90°180°

−180°

−90°

0°

90°

180°

rx

ry

r z

(b) 2. Iteration

−180° −90° 0° 90° 180°−180°

−90°0°

90°180°

−180°

−90°

0°

90°

180°

rx

ry

r z

(c) 3. Iteration

−180° −90° 0° 90° 180°−180°

−90°0°

90°180°

−180°

−90°

0°

90°

180°

rx

ry

r z

(d) 4. Iteration

Abbildung 45: Iterationsweise Darstellung des Rotationsraums nach den ersten vier Branch-and-BoundIterationen. Innerhalb der Teilblöcke befindet sich die Rotation, unter welcher die L∞-Kostenfunktion minimal ist.

Kamera im Ursprung sowohl translatorisch als auch rotatorisch fixiert ist, werden die Kegel-restriktionen durch den Radius aufgespannt, unter welchem alle Objektpunkte in den Kegelnliegen. Da der Zulässigkeitstest eines Teilblocks Auskunft darüber geben soll, ob eine Rotation indiesem Teilblock existieren kann, unter welchem alle Objektpunkte in den Kegeln liegen, weisendiese einen entsprechend größeren Radius auf.

74 4. Experimente

−5 0 5 10 15 20 25

−10

0

100

5

10

15

20

25

cam2

U3U9U6

x−axis

U2U5

U8

cam1

U1

U4

y−axis

U7

z−ax

is

(a) 3. Iteration

−5 0 5 10 15 20 25

−10

0

100

5

10

15

20

25

cam2

U3U6U9

x−axis

U2U5

cam1

U8U1

U4U7

y−axis

z−ax

is

(b) 4. Iteration

−5 0 5 10 15 20 25

−10

0

100

5

10

15

20

25

cam2

U3U6U9

x−axis

U2U5

cam1

U8U1U4U7

y−axis

z−ax

is

(c) 5. Iteration

−5 0 5 10 15 20 25

−10

0

100

5

10

15

20

25

cam2

U3U6U9

x−axis

U2U5

cam1

U8U1U4U7

y−axis

z−ax

is

(d) 6. Iteration

Abbildung 46: Iterationsweise Darstellung der Lorentzkegel, welche als Kegelrestriktionen im Zulässig-keitstest der bis dahin besten Lösung dienen. Die aus den Beobachtungen der erstenKamera abgeleiteten Lorentzkegel sind aufgrund der Datumsdefinition fixiert und dieLorentzkegel der zweiten Kamera sind entsprechend der aktuellen Lösung der relativenOrientierung gelagert.

75

5. Zusammenfassung und Ausblick

5.1 Zusammenfassung

In dieser Arbeit wurden Lösungsverfahren für einige geometrische Aufgaben aus der Photo-grammetrie dargestellt und untersucht, welche eine global optimale Lösung unter Nutzung derL∞-Norm garantieren. Wir haben gezeigt, dass der räumliche Vorwärtsschnitt, die Homographie-Schätzung, die Bündelausgleichung bei bekannten Rotationen, die relative Orientierung und derräumliche Rückwärtsschnitt als quasikonvexe Optimierungsprobleme mit quadratischen Kegelre-striktionen („Second-order Cone Programme“) überführt werden können, welche mittels Innerer-Punkte-Verfahren lösbar sind. Zudem wurde zur Detektion von Ausreißern ein konvexes Opti-mierungsverfahren untersucht, welches durch die dargestellte SOI-Minimierung die Anzahl derAusreißer approximativ minimiert.Zu Beginn dieser Arbeit wurden die für das Verständnis der Arbeit notwendigen Grundlagen

zur mathematischen Optimierung dargestellt. Es wird speziell auf die statistische Bedeutungder Minimierung der L2- und der L∞-Norm eingegangen und aufgezeigt, wie eine Kostenfunk-tion mittels des Newton-Verfahrens numerisch minimiert werden kann. Zudem werden Grund-lagen zur konvexen Optimierung dargestellt, welche zum Erkennen konvexer und quasikonvexerOptimierungsprobleme dienen und die Lösbarkeit dieser Optimierungsprobleme mittels Innerer-Punkte-Verfahren darlegen.Das vorgestellte Lösungsverfahren für den räumlichen Vorwärtsschnitt, die Homographie-

Schätzung und die Bündelausgleichung bei bekannten Rotationen basiert auf einem Bisekti-onsverfahren, in welchem das maximale Residuum iterativ minimiert wird. Die implementiertenVerfahren wurden auf synthetisch generierten Daten getestet und anhand der Verteilung der Re-siduen unter der jeweiligen L∞-Lösung konnten die statistischen Eigenschaften der L∞-Schätzerverifiziert werden. Zum Vergleich des Genauigkeitsniveaus der L2- und L∞-Lösung wurde mit-tels einer Monte-Carlo-Simulation die empirische Kovarianzmatrix abgeleitet, mittels welcher derHelmertsche-Punktfehler der L2- und der L∞-Lösung verglichen werden kann. Hierbei lieferte dieL2-Lösung bei normalverteilten Beobachtungsabweichungen unter verschiedenen Rauschniveausstets die qualitativ beste Lösung. Die L∞-Lösung nahm häufig ähnliche Werte wie die L2-Lösungan und das Genauigkeitsniveau war durchgehend sehr ähnlich. Die L∞-Lösung reagiert jedochstärker auf extreme Beobachtungsabweichungen. Bei einem hohen Rauschniveau wächst der Hel-mertsche Punktfehler signifikant stärker an als der Punktfehler der L2-Lösung.Falls ein Ausreißer in den Beobachtungen vorliegt, so wird die L∞-Lösung stark verfälscht,

da der Ausreißer ein großes Residuum erzeugt. Zur Ausreißerdetektion bei den drei genanntenVerfahren wurde 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 dieBeobachtungen aufgespannten Kegelrestriktionen minimal ist. Beobachtungen, welche unzulässi-ge Restriktionen erzeugen, können dann als Ausreißer identifiziert werden. Die SOI-Minimierunghat auf den synthetisch 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 darge-

stellt, mit welchem sogar Rotationen mittels einer Branch-and-Bound-Suche im dreidimensiona-len Rotationsraum bestimmt werden können. Dieses Verfahren ermöglicht es auch die L∞-Lösungdes räumlichen Rückwärtsschnitts und der relativen Orientierung stets ohne Näherungswerte zubestimmen. Neben der theoretischen Aufarbeitung wurden beide Verfahren implementiert unddurch Anwendung auf simulierte Datensätze getestet.Ein Vorteil der L∞-Optimierung liegt darin, dass keine Näherungswerte benötigt werden, da bei

76 5. Zusammenfassung und Ausblick

der L∞-Optimierung stets eine quasikonvexe Kostenfunktion mit nur einem Minimum vorliegt.Zudem besitzt die L∞-Lösung im Gegensatz zu direkten algebraischen Lösungsverfahren eineklare geometrische Bedeutung.Es konnte in dieser Arbeit anhand von synthetisch generierten Datensätzen gezeigt werden, dass

die Abweichungen zwischen der L∞-Lösung und der L2-Lösung nicht sehr groß sind. Die L∞-Lösung eignet sich daher als Näherungswert zur Initialisierung einer L2-Minimierung. Mittelsiterativer Lösungsverfahren, wie bspw. einer Bündelausgleichung, kann die L∞-Lösung durchMinimierung der L2-Kostenfunktion verbessert werden.Ein klarer Kritikpunkt an der L∞-Minimierung der Residuen ist, dass diese stark von Ausrei-

ßern beeinflusst wird. Im Grunde richtet sich die L∞-Lösung ausschließlich nach den „schlech-ten“ Daten. Die L∞-Minimierung erscheint für viele Anwendungen in diesem Licht zunächstunbrauchbar, jedoch ist auch die gewöhnliche Kleinste-Quadrate-Schätzung, bei welcher die L2-Norm minimiert wird, auch in besonderem Maße durch Ausreißer beeinträchtigt. Die in dieserArbeit vorgestellten Lösungsverfahren sind daher nur auf Datensätze anwendbar, welche bereitsvon Ausreißern bereinigt worden sind, bspw. mittels der vorgestellten und untersuchten SOI-Minimierung zur Ausreißerdetektion.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 Optimierungsproblemewurde das Open-Source-Programmpaket „SeDuMi“ verwendet. Die Laufzeit dieser Algorithmenist zwar bei weitem nicht so schnell wie eine Kleinste-Quadrate-Schätzung, jedoch bei der Lösungnicht allzu großer Probleme anwendbar.

5.2 Ausblick

Das Potential der konvexen Optimierung zur Lösung geometrischer Problemstellungen der Pho-togrammetrie ist keineswegs erschöpft. Neue Anwendungsgebiete werden zur Zeit durch aktiveForschung vor allem im Bereich der Computer Vision immer wieder entdeckt.Eine interessante Zielsetzungen für zukünftige Forschungen ist bspw. ein Lösungsverfahren,

welches eine durch die L∞-Kostenfunktion eingegrenzte L2-Kostenfunktion minimiert, um eineglobal optimale L2-Lösungen zu garantieren.Die Minimierung der L∞-Kostenfunktion liefert aufgrund der resultierenden Kegelrestriktionen

eine geometrisch interpretierbare Lösung, da diese von allen Beobachtungen unterstützt werdenmuss. Im Grunde richtet sich die L∞-Lösung daher ausschließlich nach den „schlechten“ Daten.Die Detektion von Ausreißern durch Betrachtung der Schnittmenge der durch die Beobachtungenaufgespannten Kegelrestriktionen, ist eine geometrisch sinnvolle Herangehensweise, die durch dieSOI-Minimierung approximiert werden kann. Dieses Verfahren kann jedoch nicht auf den vorge-stellten räumlichen Rückwärtsschnitt oder die relative Orientierung übertragen werden, da hierneben einer oberen Grenze für das maximal zulässige Residuum zusätzlich die Rotationsmatrixnäherungsweise bekannt sein müsste. Zur Ausreißerdetektion bei der Rotationsschätzung unterder L∞-Norm ist bisher noch kein Verfahren bekannt.Zudem können Objektpunkte, die sehr weit entfernt sind bzw. numerisch im Unendlichen liegen,

mittels der in dieser Arbeit vorgestellten Verfahren nicht bestimmt werden.Es verbleibt noch viel zu erforschen, vor allem der Umgang mit Ausreißern und die Beschleu-

nigung der Lösungsverfahren.

77

Literaturverzeichnis

Agarwal, S., M. K. Chandraker, F. Kahl, D. J. Kriegman und S. Belongie (2006)Practical Global Optimization for Multiview Geometry. In: Proceedings of the Ninth Euro-pean Conference on Computer Vision, 592–605.

Bonnans, J. Frédéric, Jean Charles Gilbert, Claude Lemaréchal und Claudia A.Sagastizábal (2006) Numerical Optimization: Theoretical and Practical Aspects (Univer-sitext). Springer-Verlag New York, Inc., Secaucus, NJ, USA.

Boyd, Stephen und Lieven Vandenberghe (2004) Convex Optimization. Cambridge Uni-versity Press.

Fiacco, A.V. und G.P. McCormick (1990) Nonlinear programming: sequential unconstrainedminimization techniques. Classics in applied mathematics. Society for Industrial and AppliedMathematics.

Fischler, Martin A. und Robert C. Bolles (1981) Random sample consensus: a paradigmfor model fitting with applications to image analysis and automated cartography. Commun.ACM, 24:381–395.

Förstner, W. (2010) Minimal Representations for Uncertainty and Estimation in ProjectiveSpaces. In: Proc. of Asian Conference on Computer Vision.

Gauß, Karl Friedrich (1809) Theoria Motus Corporum Coelestium in Sectionibus ConicusSolem Ambientieum. F. Perthes and I. H. Besser, New York.

Gill, P.E., W. Murray und M.H. Wright (1981) Practical optimization. Academic Press.Hartley, R. und F. Schaffalitzky (2004) L∞ Minimization in Geometric Reconstruction

Problems. In: IEEE Conference on Computer Vision and Pattern Recognition, Band 1,I–504 – I–509 Vol.1.

Hartley, R. I. und A. Zisserman (2004) Multiple View Geometry in Computer Vision. Cam-bridge University Press, ISBN: 0521540518, second. Ausgabe.

Hartley, Richard und Peter Sturm (1997) Triangulation. Computer Vision and ImageUnderstanding, 68(2):146–157.

Hartley, Richard I. und Fredrik Kahl (2009) Global Optimization through RotationSpace Search. International Journal of Computer Vision, 82:64–79.

Huber, P.J. (1981) Robust statistics. Wiley series in probability and mathematical statistics.Probability and mathematical statistics. John Wiley and Sons.

John E. Dennis, Robert B. Schnabel (1996) Numerical Methods for Unconstrained Opti-mization and Nonlinear Equations. Society for Industrial Mathematics.

Kahl, Fredrik (2005) Multiple View Geometry and the L∞-Norm. In: Proceedings of theTenth IEEE International Conference on Computer Vision - Volume 2, ICCV ’05. IEEEComputer Society, Washington, DC, USA, 1002–1009.

Kahl, Fredrik und Richard Hartley (2008) Multiple-View Geometry Under the L∞-Norm.IEEE Transactions on Pattern Analysis and Machine Intelligence, 30:1603–1617.

Ke, Qifa und Takeo Kanade (2005) Quasiconvex Optimization for Robust Geometric Re-construction. In: Proceedings on the 10th International Conference on Computer Vision,986–993.

Ke, Qifa und Takeo Kanade (2006) Uncertainty Models in Quasiconvex Optimization forGeometric Reconstruction. In: IEEE Computer Society Conference on Computer Vision andPattern Recognition, Band 1, 1199 – 1205.

78 Literaturverzeichnis

Ke, Qifa und Takeo Kanade (2007) Quasiconvex Optimization for Robust Geometric Recon-struction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29:1834–1847.

Lee, Hyunjung, Yongduek Seo und Sang Wook Lee (2010) Removing Outliers by Mini-mizing the Sum of Infeasibilities. Image and Vision Computing, 28:881–889.

Levenberg, K. (1944) A Method for the Solution of Certain Non-Linear Problems in LeastSquares. Quarterly Journal of Applied Mathmatics, 2(2):164–168.

Marquardt, Donald W. (1963) An Algorithm for Least-Squares Estimation of NonlinearParameters. SIAM Journal on Applied Mathematics, 11(2):431–441.

Martinec, Daniel und Tomás Pajdla (2007) Robust Rotation and Translation Estimationin Multiview Reconstruction. In: CVPR.

McGlone, J. Chris (Hrsg.) (2004) Manual of Photogrammetry. American Society for Photo-grammetry and Remote Sensing, Bethesda (Maryland), 5.. Ausgabe.

Mikhail, E.M. und F.E. Ackermann (1982) Observations and least squares. University Pressof America.

Nistér, David (2004) An Efficient Solution to the Five-Point Relative Pose Problem. IEEETrans. Pattern Anal. Mach. Intell., 26(6):756–777.

Olsson, Carl und Fredrik Kahl (2010) Generalized Convexity in Multiple View Geometry.Journal of Mathematical Imaging and Vision, 38:35–51.

Sim, Kristy und Richard Hartley (2006) Removing Outliers Using The L∞ Norm. In: Pro-ceedings of the 2006 IEEE Computer Society Conference on Computer Vision and PatternRecognition - Volume 1. IEEE Computer Society, Washington, DC, USA, 485–494.

Snavely, Noah, Steven M. Seitz und Richard Szeliski (2008) Skeletal sets for efficientstructure from motion. In: Proc. Computer Vision and Pattern Recognition.

Stewénius, H., F. Schaffalitzky und D. Nistér (2005) How Hard is Three-View Trian-gulation Really? In: IEEE International Conference on Computer Vision (ICCV), Band 1.Beijing China, 686–693.

Stigler, George J. (1945) The Cost of Subsistence. Journal of Farm Economics, 27(2):303–314.

Sturm, J. F. (2002) Implementation of Interior Point Method for Mixed Semidefinite and Se-cond Order Cone Optimization Problems. Optimization Methods and Software, 17(6):1105–1154.

Sturm, Jos F. (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetriccones. Optimization Methods and Software, 11-12:625–653.

Szeliski, Richard (2006) Image alignment and stitching: a tutorial. Found. Trends. Comput.Graph. Vis., 2:1–104.

Tomasi, Carlo und Takeo Kanade (1992) Shape and Motion from Image Streams underOrthography: a Factorization Method. International Journal of Computer Vision, 9(2):137–154.

Triggs, Bill, Philip F Mclauchlan, R Hartley und Andrew W Fitzgibbon (2000)Bundle Adjustment - A Modern Synthesis. Vision algorithms theory and practice, 34099:298–372.

Wright, Margaret H. (2005) The interior-point revolution in optimization: history, recentdevelopments, and lasting consequences. Bulletin of the American Mathematical Society(New Series), 42:39–56.

79

Abbildungsverzeichnis

1 Darstellung einer Funktion, welche mehrere Minima besitzt, und einer konvexenFunktion, bei welcher die Lösung stets ins globale Minimum konvergiert. . . . . . 1

2 Darstellung des Newton-Schritts zur Minimierung einer Funktion, welcher sich ausder Taylorreihe zweiter Ordnung ergibt. . . . . . . . . . . . . . . . . . . . . . . . 8

3 Darstellung einer konvexen und einer nicht-konvexen Menge und die Problematikkonvexer Mengen bei der Optimierung. . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Abbildung eines Lorentzkegels im R2 und des Randes eines Lorentz-Einheitskegelsim R3 sowie die Öffnung eines Einheitsnormkegels unter verschiedenen Normen. . 12

5 Darstellung einer positiv semidefiniten und einer positiv definiten Matrix. . . . . 126 Eine Hyperebene, ein Halbraum und ein durch fünf Hyperebenen begrenztes Po-

lyeder sind konvexe Mengen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 Darstellung einer konvexen und einer nicht-konvexen Funktion. . . . . . . . . . . 148 Darstellung der zulässigen konvexen Lösungsmenge eines konvexen Optimierungs-

problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Einordnung der konvexen Optimierung innerhalb der allgemeinen Optimierung. . 1610 Die Abbildung stellt die Geometrie eines LP und eines QP dar. . . . . . . . . . . 1711 Darstellung der Indikatorfunktion I(u) und ihrer Approximation It(u) unter ver-

schiedenen t. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2012 Darstellung des zentralen Pfades und der Barrieren-Funktion eines LP. . . . . . . 2213 Die Subniveaumenge sowohl einer konvexen als auch einer quasikonvexen Funktion

ist stets konvex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2614 Überprüfung der Konvexität von Funktionen. . . . . . . . . . . . . . . . . . . . . 2715 Abgrenzung zwischen quasikonvexen und pseudokonvexen Funktionen. . . . . . . 2716 Darstellung des räumlichen Vorwärtsschnitts mit drei Kameras: Die Raumstrahlen

schneiden sich bei bereits zwei Kameras i. a. nicht in einem Punkt. . . . . . . . . 3217 Darstellung des Residuums, welches den Radius in der Bildebene beschreibt, mit

welchem ein Kegel zweiter Ordnung aufgespannt wird. . . . . . . . . . . . . . . . 3418 Bei einer geradentreu abbildenden Kamera wird eine Raumgerade als Gerade auf

der Bildebene abgebildet; Die Residuumsfunktion ist stets eine pseudokonvexeFunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

19 Die zwei pseudokonvexen Residuumsfunktionen weisen unter der L2-Norm zweiMinima auf. Unter der L∞-Norm existiert nur ein Minimum. . . . . . . . . . . . 35

20 Zwei L2-Kostenfunktionen beim räumlichen Vorwärtsschnitt: Eine zeigt drei Mi-nima und die andere besitzt selbst bei fehlerfreien Beobachtungen mehrere Minima. 36

21 L2- und L∞-Kostenfunktionen eines ebenen Vorwärtsschnitts mit drei Bildern: L2-Kostenfunktion weist drei Minima auf, die L∞-Kostenfunktion besitzt hingegennur ein einziges Minimum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

22 Die Form und Größe eines gewichteten Lorentzkegels ergibt sich durch das Resi-duum Rj und die Kovarianzmatrix Σujuj auf der Bildebene. . . . . . . . . . . . . 38

23 Geometrische Interpretation der auf den Winkelabweichungen basierenden Resi-duumsfunktion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

24 Geometrische Interpretation der L∞-Optimierung des räumlichen Vorwärtsschnitts. 4125 Geometrische Interpretation eines durch quadratische Kegel restringierten Zuläs-

sigkeitsproblems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4226 Grafische Darstellung einer Bündelausgleichung mit bekannten Kamerarotationen. 4427 Grafische Darstellung einer Homographie-Schätzung. . . . . . . . . . . . . . . . . 4628 Gegenüberstellung und geometrische Interpretation des Zulässigkeitsproblems

(3.23) und des SOI-Problems (3.35) . . . . . . . . . . . . . . . . . . . . . . . . . . 4929 Darstellung des Rotationsraumes B3

π, welcher sich im Würfel C3π befindet. . . . . 51

80 Abbildungsverzeichnis

30 Darstellung der generierten Szene zur Erzeugung einer hohen Redundanz beimräumlichen Vorwärtsschnitt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

31 Darstellung der Verteilung der Residuen in einem Histogramm und in einemWahr-scheinlichkeitsnetz nach Minimierung der L2-Kostenfunktion. Die Residuen sindnormalverteilt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

32 Darstellung der Verteilung der Residuen in einem Histogramm und in einemWahr-scheinlichkeitsnetz nach Minimierung der L∞-Kostenfunktion. Die Residuen sindnur näherungsweise normalverteilt. . . . . . . . . . . . . . . . . . . . . . . . . . . 59

33 Darstellung des Helmertschen Punktfehlers sowie der maximalen Abweichung derL2- und L∞-Lösung eines räumlichen Vorwärtsschnitts, bestimmt mittels einerMonte-Carlo Simulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

34 Darstellung der L2- und L∞-Kostenfunktionen beim ebenen Vorwärtsschnitt unterverschiedenen Konfigurationen als Konturplot. . . . . . . . . . . . . . . . . . . . . 62

35 Darstellung des Helmertschen Punktfehlers und der maximalen Abweichung derL2- und L∞-Lösung einer Homographie-Schätzung, bestimmt mittels einer Monte-Carlo Simulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

36 Darstellung der generierten Szene, auf welcher eine Bündelausgleichung mit be-kannten Rotationen zur Minimierung der L∞-Norm angewendet wird. . . . . . . 64

37 Darstellung des mittels einer Monte-Carlo Simulation bestimmten HelmertschenPunktfehlers der L2- und L∞-Lösung sowohl der Objektpunkte U i als auch derKameratranslationen Zj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

38 Darstellung der generierten Szene zur Ausreißerdetektion sowie der Residuen unterder L∞-Lösung, welche ohne die nach der SOI-Minimierung detektierten Ausreißerbestimmt wurden. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

39 Darstellung der generierten Szene zur statistischen Untersuchung der Ausreißerde-tektion. Zudem sind die Residuen unter der L∞-Lösung, welche ohne die nach derSOI-Minimierung detektierten Ausreißer bestimmt wurden, aus einer Stichprobedargestellt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

40 Darstellung der Ergebnisse der statistischen Untersuchung der SOI-Minimierung. 6841 Darstellung der generierten Objektpunkte und der generierten Kamera, deren äu-

ßere Orientierung durch einen räumlichen Rückwärtsschnitt unter Minimierungder L∞-Norm bestimmt werden soll. . . . . . . . . . . . . . . . . . . . . . . . . . 69

42 Iterationsweise Darstellung des Rotationsraums nach den ersten vier Branch-and-Bound Iterationen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

43 Iterationsweise Darstellung der Lorentzkegel, welche als Kegelrestriktionen im Zu-lässigkeitstest der bis dahin besten Lösung dienen. . . . . . . . . . . . . . . . . . 71

44 Darstellung der generierten Objektpunkte und der generierten Kamera, deren äu-ßere Orientierung durch einen räumlichen Rückwärtsschnitt unter Minimierungder L∞-Norm bestimmt werden soll. . . . . . . . . . . . . . . . . . . . . . . . . . 72

45 Iterationsweise Darstellung des Rotationsraums nach den ersten vier Branch-and-Bound Iterationen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

46 Iterationsweise Darstellung der Lorentzkegel, welche als Kegelrestriktionen im Zu-lässigkeitstest der bis dahin besten Lösung dienen. . . . . . . . . . . . . . . . . . 74

47 Darstellung der Residuen in der Bildebene der ersten Kamera (a) und der zweitenKamera (a) beim Vorwärtsschnitt mittels der algebraischen Lösung. Bei dem imText beschriebenen und in (c) skizzierten Beispiel einer Vorwärtsbewegung . In . iii

i

Anhang

ii A. Algebraische Lösung

A. Algebraische Lösung

Zur Bestimmung eines unbekannten Objektpunktes U mittels n korrespondierender Bildpunk-te uj finden unter anderem lineare Verfahren Anwendung. Diese algebraischen Verfahren stellenwohl die einfachste Möglichkeit dar, einen Vorwärtsschnitt zu lösen. Die homogene Kollinea-ritätsgleichung (3.2) kann umgeschrieben werden zu PjU − λjuj = 0. Da diese linear in denUnbekannten λj und U ist, gilt das Gleichungssystem Ax = 0

P1 u1

P2 u2...

. . .Pn un

U−λ1

−λ2...−λn

= 0 . (A.1)

Eine Möglichkeit zur Lösung nach x ist die Minimierung von ||Ax|| unter der Bedingung, dass||x|| = 1 ist. Die Lösung ist dann der Einheitsvektor zum kleinsten Eigenwert der Matrix ATAund kann bspw. durch eine Singulärwertzerlegung oder durch das Jacobi-Verfahren bestimmtwerden.Diese Methode schließt bei der Lösung sowohl Bildpunkte- als auch Objektpunkte im Unend-

lichen nicht aus. Ein Nachteil dieser Methode ist es, dass sie nicht invariant gegenüber affinenTransformationen ist (vgl. Hartley und Sturm 1997). Eine Beschränkung auf euklidischeObjektpunkte liefert eine affin invariante Lösung, die Verwendung von Punkten im Unendli-chen ist dann jedoch nicht mehr möglich. Die homogene Kollinearitätsgleichung (3.2) liefert mitu = [u; v; 1] und U = [U ;V ;W ; 1] die drei Gleichungen

λjuj = pT1jU , λjvj = pT

2jU und λj = pT3jU . (A.2)

Durch den Übergang auf euklidische Objektpunkte U = [U ; 1] erhalten wir für jeden beobach-teten Bildpunkt durch die Elimination von λj die zwei Gleichungsbedingungen

ujpT3jU + ujp3j = pT1jU + p1j und vjp

T3jU + vjp3j = pT2jU + p2j . (A.3)

Das lineare Gleichungssystem besitzt dann die Form Ax− b = 0

pT11 − u1pT31

pT11 − v1pT31

pT12 − u2pT32

pT12 − v2pT32

...pT1n − unpT3npT1n − vnpT3n

U −

p11 − u1p31

p21 − v1p31

p12 − u2p32

p22 − v2p32...

p1n − unp3n

p2n − vnp3n

= 0 (A.4)

und ist bspw. mittels einer Pseudo-Inversen oder einer Singulärwertzerlegung nach x zu lösen.Der jedoch größte Nachteil und der Grund für Ungenauigkeiten dieser linearen Verfahren ist,

dass die zu minimierende Zielfunktion ||Ax|| bzw. ||Ax − b|| keinen geometrische und somitauch keine statistische Bedeutung hat. Der Fehler ε = (ujp

T3j − pT1j)U + ujp3j − p1j unter einer

Lösung für U entspricht nicht dem Residuum zwischen den beobachteten Bildpunkten und derProjektion von U . Dies hat zur Folge, dass dieses Verfahren fehlschlägt, wenn die Entfernung derObjektpunkte zu den jeweiligen Kameras unterschiedlich sind. Zur Verdeutlichung wollen wir einBeispiel aufzeigen, wie es bei einer Vorwärtsfahrt einer Kamera auftreten kann.

A. Algebraische Lösung iii

Betrachten wir zwei Kameras, die entlang der z-Achse ausgerichtet sind, die erste Kamerabefindet sich am Ursprung und die zweite auf der z-Achse bei z = −10. Die Projektionsmatrizender Kameras lauten

P1 =

500 0 0 00 500 0 00 0 1 0

und P2 =

500 0 0 00 500 0 00 0 1 10

(A.5)

und der zu bestimmende Objektpunkt U = [1; 1; 2] läge im Sichtfeld vor beiden Kameras, jedochwesentlich näher zur ersten Kamera. Die projizierten Bildpunkte sind dann u1 = [250; 250] undu2 = [41.66; 41.66]. Nehmen wir nun an, die beobachteten Bildpunkte seien um bis zu ±1 Pixelvon den wahren Bildpunkten verschieden, was einen sehr geringes Rauschen simuliert. Verwendenwir nun die gestörten Bildpunkte zum Lösen von (A.1) um den Objektpunkt U zu bestimmen.Der bestimmte Objektpunkt wird dann wieder in das Bild projiziert, um das Residuum zubestimmen. Unter der beschriebenen Konfiguration beträgt dann das Residuum im Bild derersten Kamera bis zu etwa 300 Pixel, wohingegen das Residuum im Bild der zweiten Kamerawesentlich kleiner ist. In Abbildung 47 sind die maximalen Residuen in den beiden Bildern gegendie maximale Entfernung vom wahren Bildpunkt dargestellt.

0 0.5 1 1.5 20

50

100

150

200

250

300

350

Maximale Verschiebung in Pixel

Max

imal

es R

esid

uum

in P

ixel

(a) Residuen Bild 1

0 0.5 1 1.5 20

1

2

3

4

5

6

Maximale Verschiebung in Pixel

Max

imal

es R

esid

uum

in P

ixel

(b) Residuen Bild 2

z

yU

Kamera 1 Kamera 2

z=0 z=-10

(c) Skizze zur Konfiguration

Abbildung 47: Darstellung der Residuen in der Bildebene der ersten Kamera (a) und der zweiten Kamera(a) beim Vorwärtsschnitt mittels der algebraischen Lösung. Bei dem im Text beschriebenenund in (c) skizzierten Beispiel einer Vorwärtsbewegung . In

Die starken Abweichungen der maximalen Residuen in beiden Bildern zeigen, dass das alge-braische Verfahren kein zuverlässiges Verfahren darstellt. Wenn die Bildpunkte mit bis zu 0.9Pixel gestört werden, wird der Objektpunkt sogar hinter beiden Kameras bestimmt. Daher istdieses Verfahren selbst zur Initialisierung für iterative Verfahren nicht ratsam.

iv B. Polynomiale Methode

B. Polynomiale Methode

In diesem Abschnitt leiten wir eine L2-Kostenfunktion für den räumlichen Vorwärtsschnitt mitzwei Bildern her, welche nur von einem einzigen Parameter abhängig ist. Diese Formulierung derKostenfunktion wurde erstmalig in Hartley und Sturm (1997) veröffentlicht. Ein unbekannterObjektpunkte U im Objektraum sei in zwei Kameras i = 1, 2 mit den bekannten Projektions-matrizen Pi auf die Bildebene als Bildpunkt ui durch U = Piui abgebildet. Wir nehmen an,dass die Projektionsmatrizen exakt bekannt sind und die Bildpunkte eine gewisse Unsicherheitaufweisen. Somit schneiden sich die beiden korrespondierenden Raumstrahlen i. a. nicht, so dasses notwendig ist eine beste Lösung unter einem angenommen stochastischen Modell zu finden.Häufig wird der Mittelpunkt der gemeinsamen Lotlinie der beiden Raumstrahlen berechnet, wasjedoch keine optimale Lösung darstellt, sobald die Kameras den Objektpunkt unter verschiede-nen Winkeln und Entfernungen aufnehmen. Zudem ist dieses Verfahren bei der projektiven bzw.affinen Rekonstrukion9 einer Szene nicht anwendbar.Da zwei korrespondierende Bildpunkte u1 ↔ u2 eine gewisse Unsicherheit aufweisen, wird die

Koplanaritätsbedingung

uT1 Fu2 = 0 (B.1)

i. a. nicht erfüllt, wobei F die 3×3 Fundamentalmatrix ist. Hierbei wird die Bedingung formuliert,dass ein Bildpunkt ui auf der durch einen korrespondierenden Bildpunkt erzeugten Epipolarlinieli = Fui′ liegen muss. Unter der Annahme von normalverteilten Modellabweichungen werden dieoptimalen Bildpunkte ui gesucht, welche die Kostenfunktion

K(u) = d(u1, u1)2 + d(u2, u2)2 (B.2)

unter der Nebenbedingung (B.1) minimieren, wobei d(·, ·) die euklidische Distanz zwischen denbeiden Argumenten liefert. Sobald die optimalen Lösungen für die Bildpunkte ui gefunden wur-den, kann der Objektpunkt U durch einen räumlichen Vorwärtsschnitt bestimmt werden, da sichdie korrespondierenden Raumstrahlen dann schneiden. Betrachten wir nun die korrespondieren-den Epipolarlinien l1 und l2, dann sind die orthogonalen Projektionen von u1 auf l1 und u2 aufl2 die Bildpunkte u1 und u2, welche die Kostenfunktion (B.2) minimieren. Wir können demnachdas Minimierungsproblem umschreiben, indem wir ohne Nebenbedingung die Kostenfunktion

K(l) = d(u1, l1)2 + d(u2, l2)2 (B.3)

minimieren, wobei l1 und l2 alle korrespondieren Epipolarlinien annehmen können. Sobald dieoptimalen Lösungen für die Epipolarlinien li gefunden wurden, sind die optimalen Bildpunkteui die orthogonalen Projektionen von ui auf li. Die Minimierung der Kostenfunktion (B.3) kannüber nur eine einzige Variable erfolgen, indem die möglichen Epipolarlinien l1(t) im ersten Bilddurch einen Parameter t parametrisiert werden. Mittels der Fundamentalmatrix F ergibt sich diekorrespondierende Epipolarlinie l2(t) im zweiten Bild. Die Kostenfunktion des Minimierungspro-blem kann schließlich explizit durch einen einzigen Parameter t formuliert werden

K(l(t)) = d(u1, l1(t))2 + d(u2, l2(t))2. (B.4)

Zur weiteren Betrachtung der Kostenfunktion vereinfachen wir zunächst die Konfiguration,indem wir die korrespondierenden Bildpunkte u1 ⇔ u2 in den Ursprung [0 0 1]T und die Epipole

9Bei der projektiven oder affinen Rekonstruktion wird die 3D-Szene bis auf eine unbekannte Transformationrekonstruiert.

B. Polynomiale Methode v

auf die X-Achse auf den Punkt e1 = [1 0 f1]T bzw. e2 = [1 0 f2]T des jeweiligen Bildsystemstransformieren, wobei fi die Kamerakonstante der i-ten Kamera ist. Die Quadratsumme derDistanzfunktionen ist invariant gegenüber der hierzu notwendigen Translation und Rotation, dieFundamentalmatrix muss jedoch angepasst werden. Sei die Transformationsmatrix des jeweiligenBildes durch

Mi = RiTi =

cos θi − sin θi 0sin θi cos θi 0

0 0 1

1 0 −ui,10 1 −ui,20 0 1

(B.5)

gegeben, so ergibt sich die Fundamentalmatrix des transformierten Bildes durch F = Mi′F0Mi,wobei F0 die untransformierte Fundamentalmatrix ist. Nach der Transformation gilt F1e1 =(eT2 F2)T = 0, somit hat die Fundamentalmatrix die besondere Form

F =

f1f2d −f2c −f2d−f1b a b−f1d c d

. (B.6)

Betrachten wir nun eine Epipolarlinie im ersten Bild, welche durch den Punkt p1 = [0, t, 1]T

und den Epipol e1 läuft, ist gegeben durch l1(t) = p1 × e1 = [tf, 1,−t]T. Mittels derFundamentalmatrix ergibt sich die korrespondierende Epipolarlinie l2 im zweiten Bild durchl2(t) = Fp1 = [−f2(ct + d), at + b, ct + d]T. Die quadrierte Distanz vom Ursprung zu l1(t) bzw.l2(t) ergibt sich dann durch

d(u, l1(t))2 =t2

1 + (tf)2bzw. d(u, l1(t))2 =

(ct+ d)2

(at+ b)2 + f22 (ct+ d)2

. (B.7)

Die zu minimierende Kostenfunktion kann demnach mittels als Polynom über t beschriebenwerden durch

K(t) =t2

1 + (tf)2+

(ct+ d)2

(at+ b)2 + f22 (ct+ d)2

. (B.8)

Die Minima und Maxima von K(t) treten dort auf, wo die Ableitung K(t)′ = 0 ist. Die Ableitungist ein Polynom 6. Grades, welches bis zu sechs Nullstellen, demnach drei Minima aufweisen kann.Das absolute Minimum kann gefunden werden, wenn die Kostenfunktion (B.8) für alle Nullstellenausgewertet wird. Dieses Verfahren zur Bestimmung des globalen Minimums unter Verwendungder L2-Norm wird in Hartley und Sturm (1997) vorgeschlagen und als „polynomiale Methode“benannt.

Documents

Lösung von Orientierungsaufgaben der Photogrammetrie mit ... · Institut für Geodäsie und Geoinformation Professur für Photogrammetrie, Nussallee 15, 53115 Bonn Masteraufgabe