Interaktive Erzeugung von 3D Gesichtsmodellen aus einer Fotografie im Auftrag der LOOXIS GmbH

Danksagung

An dieser Stelle möchten die Autoren ihren Dank an einige wichtige Personen ausdrücken.

Peter Brendebach

Ich danke hiermit den betreuenden Professoren Dr. Ulrich Schwanecke und Dr. Peter Barth. Ihr Engagement in Form von hilfreichen Ideen und konstruktiver Kritik hat maßgeblich zum Gelingen dieser Arbeit beigetragen. Weiterhin danke ich meinen Eltern, die mich stets in allen meinen Entscheidungen und Vorhaben unterstützt haben. Abschließend möchte ich all denen danken, die mich während der Entstehungszeit dieser Arbeit begleitet und unterstützt haben.

Frank Walkowski

An dieser Stelle bedanke ich mich bei allen, die mich bei der Erstellung dieser Arbeit unterstützt haben. Insbesondere möchte ich mich bei meinen Professoren Dr. Ulrich Schwanecke und Dr. Peter Barth für die Betreuung meiner Diplomarbeit bedanken. Ihre Ideen und Tipps haben jederzeit zur Verbesserung dieser Arbeit beigetragen. Meinen Eltern möchte ich an dieser Stelle dafür danken, dass sie mir dieses Studium ermöglicht haben. Zum Abschluss danke ich meinem Bruder und meiner Freundin Nadia für ihre Unterstützung während des gesamten Studiums.

Zu guter Letzt möchten wir uns bei den geduldigen Korrekturlesern Christian Rathemacher und Eva Brendebach bedanken.

Inhaltsverzeichnis

1 Einleitung 1

1.1 Motivation 1

1.2 Zielsetzung 2

1.3 Aufbau der Arbeit 2

2 3D Gesichtsmodelle aus Fotograﬁen 5

2.1 Shape-from-X 9

2.2 Statistisches Modell 10

2.3 Kombination von Shape-from-Shading und statistischem Modell 11

3 Grundlagen 15

3.1 Koordinatensysteme 15

3.1.1 Kartesische Koordinaten 16

3.1.2 Kugelkoordinaten 17

3.1.3 Geographische Koordinaten 18

3.1.4 Zylindrische Koordinaten 20

3.2 Digitale Bildverarbeitung 21

3.2.1 Partielle Ableitungen von Bildern 23

3.2.2 Punktoperationen 24

3.2.3 Nachbarschaftsoperationen 24

3.3 Beschreibung von Oberﬂächen 29

3.3.1 Höhenfelder 30

3.3.2 Punktwolken 32

vii

Inhaltsverzeichnis

3.3.3 Polygonale Netze 34

4 Rekonstruktion mittels Shape-from-Shading 39

4.1 Reﬂektionsverhalten von Oberﬂächen 39

4.1.1 Diﬀerentielle Raumwinkel 40

4.1.2 Relevanz des Einfallwinkels für die Lichtintensität 41

4.1.3 Strahldichte und Bestrahlungsstärke 43

4.1.4 Lichtmessung mit Kameras 43

4.1.5 Bidirectional Reﬂectance Distribution Function 46

4.1.6 Das Lambertsche Gesetz 50

4.2 Shape-from-Shading 52

4.2.1 Bestehende Shape-from-Shading-Verfahren 53

4.3 Konzept 55

4.4 Vorverarbeitung der Fotograﬁen 56

4.4.1 Intensitäten und Alphakanal ermitteln 57

4.4.2 Lambertsche Reﬂektion korrigieren 57

4.4.3 Bildgradienten berechnen 66

4.5 Das Shape-from-Shading-Framework 68

4.5.1 Die Rückstrahlfunktion der Abbildung als harte Bedingung 68

4.5.2 Die Glättung der Oberﬂäche als weiche Bedingung 71

4.5.3 Initialisierung 72

4.6 Integrieren des Normalenfeldes 73

4.6.1 Orthogonale Projektionen 73

4.6.2 Die Fourier-Transformation 74

4.6.3 Integration 75

4.7 Aufbereiten der Höhenfelder 79

5 Statistisches Modell für Oberﬂächennormalen 81

5.1 Grundlagen zur Analyse von dreidimensionalen Laserscans 82

5.1.1 Dreidimensionale Laserscans 82

5.1.2 Projektionen 85

5.1.3 Eigenwerte und Eigenvektoren 90

5.1.4 Hauptkomponentenanalyse 93

5.1.5 Mittelwertbildung von Einheitsvektoren 100

5.2 Statistische Modelle für Gesichter 106

viii

Inhaltsverzeichnis

5.2.1 Eigenbilder und Eigengesichter 106

5.2.2 Dreidimensionale statistische Modelle 107

5.3 Aufbau des statistischen Modells 111

5.4 Korrespondenzbestimmung 117

5.4.1 Optischer Fluss von Bildfolgen 118

5.4.2 Hinzuziehen von Nachbarschaften 125

5.4.3 Bildpaare 128

5.4.4 Grob-zu-fein-Strategie 130

5.4.5 Korrespondenzbestimmung zwischen 3D Scans 141

5.4.6 Glätten der Vektorfelder 144

5.5 Bestimmung von Normalenfeldern 148

5.5.1 Ausrichten der Trainingsdaten 148

5.5.2 Ermitteln der Normalenfelder 150

5.6 Analysieren der Normalenfelder 153

5.6.1 Bestimmen eines mittleren Normalenfelds 153

5.6.2 Überführen in einen linearen Raum 154

5.6.3 Ermitteln der Modelleigenschaften 155

6 Modellgestütze Rekonstruktion 161

6.1 Rekonstruktion durch Shape-from-Shading und Glätten der Ober-

ﬂäche 161

6.2 Rekonstruktion durch Projektion auf den Modellraum 163

6.3 Kombination des Shape-from-Shading mit dem statistischen Modell 164

7 Realisierung 167

7.1 Architektur 167

7.1.1 Aufbau des Modells 168

7.1.2 Rekonstruktion der Gesichtsmodelle 170

7.2 Umsetzung 174

7.2.1 Hardware 174

7.2.2 Software 175

8 Tests und Bewertung 177

8.1 Aufbau des Modells 178

8.1.1 Korrespondenzbestimmung 180

8.1.2 Visualisierung der Eigengesichter 182

ix

Inhaltsverzeichnis

8.2 Rekonstruktion der Gesichtsmodelle mit den verschiedenen Algo-

rithmen 183

8.2.1 Rekonstruktion mittels Shape-from-Shading 185

8.2.2 Projektion auf den Modellraum 187

8.2.3 Kombination des Shape-from-Shading mit dem statistischen

Modell 189

8.3 Experimente 192

8.3.1 Drehung des Kopfes 192

8.3.2 Änderung der Beleuchtungsrichtung 195

8.3.3 Perspektivische Verzerrung 197

8.4 Rekonstruktion aus Fotograﬁen 200

9 Zusammenfassung und Ausblick 207

Abbildungsverzeichnis 209

Literaturverzeichnis 219

x

Kapitel 1

Einleitung

1.1 Motivation

Die Firma Looxis vermarktet eine Technologie, mit der es möglich ist Gesichter von Personen in einem Glasblock darzustellen. Hierfür wird das Gesicht des Kunden mit einem 3D-Scanner erfasst, ein Gesichtsmodell berechnet und, falls notwendig, nachbearbeitet. Dieses wird anschließend in optisches Glas gelasert.

Das Verfahren bringt zwei Einschränkungen mit sich. Zum Einen ist der 3D-Scanner eine hohe Investition und zum Anderen muss die zu scannende Person vor Ort sein. Ist der Glasblock als Geschenk gedacht und soll die zu beschenkende Person selbst in den Glasblock gelasert werden, muss diese anwesend sein. Somit

ist das Geschenk keine Überraschung mehr.

Aus diesem Grund ist die Entwicklung eines Verfahrens, mit dem es möglich ist aus einem Passbild ein Gesichtsmodell zu erstellen, für den Kunden als auch für die Firma Looxis von Interesse. Es genügt, ein Passbild per E-Mail oder Post an Looxis zu senden. Außerdem ist der Vertriebsweg über einen Onlineshop möglich. Im Falle eines Geschenks ist der Überraschungseﬀekt noch vorhanden, da nur ein Passbild der zu beschenkenden Person benötigt wird.

Das Verfahren soll den 3D-Scanner ergänzen und somit die Produktionskosten verringern. In Kooperation mit der FH-Wiesbaden soll im Rahmen dieser Diplomarbeit die Basis für ein solches Verfahren geschaﬀen werden.

1

1 Einleitung

1.2 Zielsetzung

Das Ziel dieser Arbeit ist es, ein Verfahren zu entwickeln, welches die Rekonstruktion eines 3D-Gesichtsmodells aus einem einzigen Passbild ermöglicht. Hierfür werden zwei verschiedene Herangehensweisen untersucht und schließlich kombiniert. Zum Einen wird ein Shape-from-Shading-Framework beschrieben, welches aus Fotograﬁen Gesichtsmodelle rekonstruiert. Zum Anderen wird ein statistisches

Modell vorgestellt, welches vorhandene Gesichtsmodelle analysiert und sich sinn- voll in das Shape-from-Shading-Framework integrieren lässt. Das Verfahren soll daraufhin bewertet und analysiert werden ob sich solch eine Kombination für die Rekonstruktion von Gesichtsmodellen eignet. Abschließend soll gezeigt werden, welche zukünftigen Schritte notwendig sind um die Rekonstruktion zu verbessern.

1.3 Aufbau der Arbeit

Die Arbeit ist folgendermaßen aufgebaut. In Kapitel 2 wird anhand der menschlichen Wahrnehmung ein Konzept für ein Verfahren zur Rekonstruktion von 3D-Gesichtsmodellen aus einzelnen Fotograﬁen aufgebaut. Das Verfahren besteht aus einer Kombination von Shape-from-Shading und einem statistischen Modell. Grundlagen, die zum Verständnis der anschließenden Kapitel notwendig sind, werden in Kapitel 3 vermittelt. In Kapitel 4 wird ein Shape-from-Shading-Framework vorgestellt. Es ermöglicht, verschiedene Bedingungen in die Rekonstruktion zu integrieren. Kapitel 5 zeigt, wie sich ein statistisches Modell berechnen lässt. Es wird erläutert welche Eigenschaften es besitzt und wie es verwendet wird. Wie sich das Framework mit dem statistischen Modell kombinieren lässt, zeigt Kapitel 6. Weiterhin wird in Kapitel 7 die Architektur des umgesetzten Verfahrens erläutert. Außerdem wird beschrieben, welche Programmiersprachen und Bibliotheken eingesetzt wurden. Die Ergebnisse und verschiedene Experimente werden in Kapitel 8 vorgestellt. Abschließend wird in Kapitel 9 die Arbeit zusammengefasst und ein Ausblick über mögliche Erweiterungen und Verbesserungen des Verfahrens gegeben.

Diese Arbeit wurde von Peter Brendebach und Frank Walkowski verfasst. Tabelle 1.3 zeigt, welche Kapitel und Abschnitte welchem Autor zuzuordnen sind. Die Bereiche der Arbeit, welche gemeinschaftlich angefertigt wurden, sind nicht

2

1.3 Aufbau der Arbeit

in der Tabelle aufgeführt.

Peter Brendebach Frank Walkowski

Abschnitte 2.1 2.2

3.3 3.1, 3.2

4

5

6.1 6.2

7.1. 2, 7.2 7.1.1

8.2. 1, 8.3.1, 8.3.2 8.1, 8.2.2, 8.2.3, 8.3.3

3

1 Einleitung

4

Kapitel 2

3D Gesichtsmodelle aus Fotograﬁen

Das Sehen ist das wichtigste Werkzeug des Menschen um seine Umwelt wahrzunehmen. Deswegen wurde schon viel Mühe und Zeit in die Aufgabe investiert, Computern das Sehen zu lehren. Diese Aufgabe ist nicht trivial, obwohl das Sehen an sich nicht schwierig ist. Kameras, die Bilder ihrer Umwelt aufnehmen können, gibt es schon lange. Der problematische Teil besteht in der Interpretation der Bilder. Dies zeigt sich zum Beispiel darin, dass der Mensch trotz jahrelangem Training noch immer mit optischen Täuschungen verwirrt werden kann.

Eine der wohl bekanntesten optischen Täuschung ist der Ames-Raum [IA68]. Die Personen in Abbildung 2.1 sind ähnlich groß. Durch den besonderen Aufbau des Raumes hat man jedoch den Eindruck, dass die linke Person kleiner ist. Der Betrachter hat das Gefühl, dass sich beide Personen auf gleicher Höhe beﬁnden. Dies ist jedoch nicht der Fall. Die linke Person steht deutlich weiter hinten als die rechte Person. Durch die scheinbar parallel verlaufenden Muster auf dem Boden wird das Gehirn getäuscht.

In Abbildung 2.2(a) sind Kreise mit verschiedenen Farbverläufen zu sehen. Durch diese Farbverläufe hat man das Gefühl, dass es sich um dreidimensionale Strukturen [LB00; LT04] handelt. Bei einem Hell-Dunkel-Verlauf bekommt man den Eindruck, als seien die Kreise nach außen gewölbt. Eine solche Wölbung bezeichnet man als konvex. Ein Verlauf von Dunkel nach Hell suggeriert hingegen, dass es sich um nach innen gewölbte Kreise handelt. Hierbei spricht man von einer konkaven Wölbung. Die Bedeutung von konvex und konkav ist in Abbildung 2.2(b)

5

2 3D Gesichtsmodelle aus Fotograﬁen

Abbildung 2.2: Hell-Dunkel-Verläufe vermitteln den Eindruck einer Wölbung. Dunkel-Hell-Verläufe vermitteln dagegen den Eindruck eines Lochs. Bild angelehnt an:

[Smi07].

6

verdeutlicht. Die Interpretation der Wölbung ist auf das visuelle System des Menschen zurückzuführen. Solange keine weiteren Lichtquellen bekannt sind, geht der Mensch davon aus, dass das Licht von oben kommt. Daraus lässt sich schließen, dass der Mensch den Schattenwurf eines Objekts bei der Rekonstruktion der dreidimensionalen Form beachtet.

Eine weitere Funktionsweise des menschlichen Sehens lässt sich anhand Abbildung 2.3 zeigen. Das linke Bild stellt eine Gesichtsmaske dar, welche von oben

beleuchtet ist. Auf der rechten Seite ist die selbe Gesichtsmaske abgebildet, je- um 180 ^◦ gedreht. Durch diese Drehung schaut man von hinten in die Maske.

Die Lichtquelle beﬁndet sich bei beiden Bildern links oben. Diese Illusion ist unter anderem als Gregorys Maske [Gre97] bekannt. Obwohl das Licht von oben kommt und man wie im vorherigen Absatz beschrieben eine konkave Erscheinung des Gesichts erwartet, glaubt man ein von unten beleuchtetes Gesicht zu sehen [PB04]. Gesichter sind im Normalfall nicht nach innen gewölbt. Das Gehirn interpretiert das Bild daher anders als es tatsächlich enstanden ist. Dadurch kann man sagen, dass das Gehirn ein Bild nicht nur anhand des Schattenwurfs rekonstruiert. Es besitzt vielmehr ein riesiges Erinnerungsvermögen bereits gesehener Dinge, mit dem es ein Bild abgleicht.

Das Gehirn verwendet also verschiedene Verfahren um Bilder zu interpretieren. Diese funktionieren so gut, dass es sich sogar aus abstrakten Abbildung, wie zum Beispiel einer Zeichnung, eine räumliche Szene aufbauen kann. Solche Zeichnungen beinhalten nicht immer bekannte Objekte. Das Gehirn kann trotz alledem auch solche abstrakte Objekte interpretieren. Hierfür versucht das Gehirn die abstrakten Abbildungen in eine möglichst einfache und bekannte Ordnung zu bringen, um somit die Objekte auf dem Bild zu erkennen.

7

2 3D Gesichtsmodelle aus Fotograﬁen

Abbildung 2.4: Das menschliche Gehirn kann anhand einer Ansammlung von Punkten die

abgebildeten Objekte rekonstruieren, ohne diese direkt zu erkennen. In dem

nächst nur schwarze Flecken in verschiedenen Formen und Größen. Das menschliche Gehirn kann nun aus diesen Punkten die abgebildeten Objekte rekonstruieren und sich die Szene räumlich vorstellen. Hierfür versucht es bekannte Strukturen in dem Bild zu ﬁnden. Es gleicht sein Erinnerungsvermögen mit den Bildinformationen ab und interpretiert zum Beispiel Schattierungen oder Konturen. Weitere Informationen hierzu sind in [SM00] zu ﬁnden.

Aus den bisher aufgeführten Punkten lassen sich einige Dinge schließen. Das Gehirn kombiniert mehrere Verfahren zur Rekonstruktion einer Szene. Je nach Aufbau und Inhalt der Szene verwendet es dazu die am besten geeigneten Verfahren. Im besten Fall liefern die Augen eine Sequenz von Stereopaaren, die es untersuchen kann. Bei der Interpretation eines Stereopaars, oder auch nur einem Bild, verwendet das Gehirn sein Wissen über das bisher Gesehene um Formen zu rekonstruieren.

Die folgenden Abschnitte beschreiben die technischen Abstraktionen der vorgestellten Verfahren, welche das Gehirn verwendet um dreidimensionale Formen zu rekonstruieren. Darauf aufbauend wird gezeigt, wie solche Abstraktionen kombiniert werden können um Gesichtsmodelle aus einer einzelnen Fotograﬁe zu rekonstruieren.

8

2.1 Shape-from-X

Aus den Sequenzen von Stereopaaren, die dem Gehirn zur Verfügung stehen, lassen sich verschiedene zu verwendende Informationen einzeln betrachten. Die technischen Abstraktionen der Verfahren, welche auf den jeweiligen verwendeten Informationen beruhen, werden Shape-from-X -Verfahren [ZTCS99] genannt. Hierbei ist das X durch die jeweilige Art der Abstraktion zu ersetzen.

liche Verzerrung des Musters der Oberﬂäche kann die Form rekonstruiert werden. Dieses Verfahren ﬁndet nur bei Objekten mit einem bekannten oder sich wiederholenden Muster Verwendung.

2 3D Gesichtsmodelle aus Fotograﬁen

• Shape-from-Contour : Hier werden nur die Umrisse eines Objektes zur Re-

auf Grund von fehlenden Informationen nicht möglich. Es stehen nur einzelne Fotograﬁen zur Verfügung. Verfahren, die auf Stereopaaren aufbauen oder mit Bewegung arbeiten, können deswegen ausgeschlossen werden. Des Weiteren sollen Gesichter rekonstruiert werden. Die Farbe eines Gesichts ist zu gleichmäßig um daraus Rückschlüsse auf seine Oberﬂäche ziehen zu können. Die Verwendung von Shape-from-Texture ist deswegen ebenfalls nicht möglich. Shape-from-Shadow liefert als alleiniges Verfahren zu wenige Informationen um ein komplettes Gesicht zu modellieren. Wird der Schattenwurf allerdings nicht berücksichtigt, kann dass das Resultat stark beeinﬂussen.

Shape-from-Shading ist somit der vielversprechendste Weg Gesichtsmodelle aus Fotograﬁen zu rekonstruieren.

2.2 Statistisches Modell

Das Gehirn verfügt über ein großes Erinnerungsvermögen. Mit diesem kann das Gehirn beispielsweise Gesichter erkennen. Wie bereits gezeigt, beruht die Erkennung unter anderem auf der Form des Gesichts. Das Gehirn muss sich also nicht nur Abbildungen von Gesichtern merken können, sondern auch ihre Form und deren Eigenschaften.

Unter der Annahme, dass sich das Gehirn nur die wichtigsten Formen und Eigenschaften merkt, kann man einem Computer dieses Erinnerungsvermögen beibringen. Eine Möglichkeit besteht in der Verwendung eines statistischen Modells. Ein solches Modell ermöglicht die Rekonstruktion der Form von Objekten aus einer Kombination von wiederkehrenden Eigenschaften.

Ein statistisches Modell geht davon aus, dass die nachzubildenden Objekte Ähnlichkeiten aufweisen. Dies ist bei Gesichtern der Fall. Die Anordnung und Größe

10

2.3 Kombination von Shape-from-Shading und statistischem Modell

von Augen, Nase, Mund und Ohren stehen in einem festen Verhältnis zueinander und lassen daher nur wenige Unterschiede zu. Es bietet sich also an, ein statistisches Modell zur Rekonstruktion eines Gesichts aus einer Fotograﬁe heranzuziehen. Ein statistisches Modell für Gesichter wird aus Beispielgesichtern erstellt. Die Aussagekraft des Modells ist daher von den verwendeten Gesichtern abhängig. Das Modell stellt eine sinnvolle Ergänzung eines Rekonstruktionsverfahrens dar.

2.3 Kombination von Shape-from-Shading und

statistischem Modell

In der Dissertation von Smith [Smi07] ist ein Verfahren beschrieben, welches sowohl auf einem Modell als auch auf einem Shape-from-Shading-Verfahren aufbaut. Dabei wird ein statistisches Modell iterativ an das zu rekonstruierende Gesicht angepasst. Ein Shape-from-Shading-Verfahren ergänzt nach jeder Iteration das rekonstruierte Gesicht um die Merkmale, die das Modell nicht darstellen kann. Damit werden die Vorteile beider Verfahren bestens ausgenutzt und ihre Nachteile umgangen. In Abbildung 2.5 ist der schematische Aufbau des Verfahrens zu sehen.

Ausgangssituation ist eine Fotograﬁe, welche ein frontal beleuchtetes und aufgenommenes Gesicht zeigt. Auf das Gesicht werden verschiedene Techniken der digitalen Bildverarbeitung angewendet. Darauf folgt die Rekonstruktion des Gesichts. Hier werden in jeder Iteration die optimalen Parameter des statistischen Modells ermittelt. Mit diesen lässt sich ein Gesicht, durch Kombination der im Modell gespeicherten Eigenschaften menschlicher Gesichter, rekonstruieren. Durch Verwendung eines Shape-from-Shading-Verfahrens wird das Gesicht um individuelle Eigenschaften ergänzt, welche sich durch das Modell nicht abbilden lassen. Dieser Vorgang wird wiederholt, bis sich von einer Iteration zur nächsten nur noch geringfügige Änderungen ergeben. Ist dies der Fall, muss das Ergebnis nachbearbeitet werden, um es als 3D-Objekt speichern zu können.

Der Aufbau des statistischen Modells ﬁndet dabei in einem von der Rekonstruktion unabhängigem Prozess statt. Dies ist in Abbildung 2.6 dargestellt. Ist das statistische Modell einmal berechnet, kann es immer wieder verwendet werden. Es ist notwendig die beiden Abläufe zu trennen, da der Aufbau des Modells

11

2 3D Gesichtsmodelle aus Fotograﬁen

Abbildung 2.5: Schematischer Aufbau für die Rekonstruktion eines Gesichtsmodells aus einer

Portraitfotograﬁe.

12

2 3D Gesichtsmodelle aus Fotograﬁen

abhängig vom Umfang der Gesichtsdatenbank sehr lange dauern kann. Ein weiterer Vorteil dieser Unterteilung besteht darin, dass weniger Speicherplatz benötigt wird. Das statistische Modell enthält nicht mehr die kompletten Beispielgesichter, sondern nur noch deren wichtigsten Eigenschaften. Die Datenmenge des Modells ist dadurch kleiner als die der Datenbank. Zur Rekonstruktion ist nur noch das Modell notwendig und die Datenbank muss nicht mehr zur Verfügung stehen.

14

Kapitel 3

Grundlagen

In diesem Kapitel sollen mathematische Grundlagen vermittelt werden, die für die beiden Kapitel 4 und 5 relevant sind. Es handelt sich hierbei zunächst um die Repräsentation von Geometrie in verschiedenen Koordinatensystemen. Weiterhin ist ein Grundwissen über digitale Bildverarbeitung notwendig um mit Gesichtsfotograﬁen zu arbeiten. Schließlich werden verschiedene Oberﬂächenrepräsentationen vorgestellt, welche zur Darstellung und Verarbeitung von dreidimensionalen Gesichtsmodellen dienen.

3.1 Koordinatensysteme

Ein Punkt lässt sich durch Angabe seiner Position in einem Koordinatensystem im Raum beschreiben. Die Angabe einer solchen Position geschieht über ein n- dimensionalesTupel. Die Dimension des Koordinatensystemes, in dem der Punkt dargestellt wird, hat gleichermaßen die Dimension n. Ein Tupel beinhaltet die Koordinaten, welche die Position beschreiben. In der folgenden Gleichung entspricht p dem Punkt und x, y, z den Koordinaten des Punktes: ⎛ ⎞

3 Grundlagen

Durch Verbinden verschiedener Punkte in einem Raum entsteht eine Linie oder ein Polygon. Der sogenannte Ursprung eines Koordinatensystemes ist der Punkt, in dem alle Komponenten des n-Tupels Null sind. Daher bezeichnet ihn auch als Nullpunkt des Koordinatensystems.

Es gibt eine Vielzahl verschiedener Koordinatensysteme. In dieser Arbeit werden sogenannte orthogonale Koordinatensysteme verwendet. Orthogonal bedeutet, dass ihre Koordinatenachsen senkrecht aufeinander stehen. Eine weitere Eigenschaft solcher Systeme ist, dass die Abstände zwischen den Koordinateneinheiten konstant sind. Die Positionsangabe einer Koordinate kann in verschiedenen Systemen angegeben werden. Umrechnungen, die für diese Arbeit notwendig sind, werden in den einzelnen Abschnitten beschrieben.

3.1.1 Kartesische Koordinaten

In Abbildung 3.1 ist ein zweidimensionales kartesisches Koordinatensystem dargestellt. Der Schnittpunkt der Achsen des Koordinatensystemes entspricht dem Nullpunkt. Ein Punkt wird durch ein zweidimensionales Tupel (x, y) mit x, y ∈ R beschrieben. Die durch die Abszisse (x-Achse) und Ordinate (y-Achse) aufgespannte Ebene ist in vier Bereiche aufgeteilt. Diese sogenannten Quadranten sind in Abbildung 3.1 bezeichnet.

Abbildung 3.1: Der in dem Bild eingetragene Punkt wird durch das Tupel (2, 1) beschrieben.

Um dreidimensionale Positionen zu beschreiben, erweitert man das Koordinatensystem um die Applikate (z-Achse). In diesem dreidimensionalen Raum gibt es rechts- sowie linkshändige Koordinatensysteme. Sie unterscheiden sich in ihrer Orientierung.

16

Applikate. Je nachdem welches System benutzt wird, zeigt der Mittelﬁnger nach der sogenannten Rechten-Hand-Regel in eine andere z-Richtung. Die Rechten-Hand-Regel lässt sich in Abbildung 3.2 nachvollziehen.

Abbildung 3.2: Bei den dreidimensionalen kartesischen Koordinatensystemen wird zwischen

links- und rechtshändigen Systemen unterschieden.

3.1.2 Kugelkoordinaten

Ein Punkt auf einer Kugel lässt sich durch den Abstand zum Mittelpunkt r und den zwei Winkeln α und θ bestimmen. Bei α handelt es sich um den Azimutwinkel und bei θ um den Polarwinkel. Beﬁnden sich die Punkte auf einer Einheitskugel, kann der Radius r vernachlässigt werden, da bei einer Einheitskugel immer r = 1 gilt.

Abbildung 3.3 zeigt einen Punkt auf solch einer Einheitskugel. Die Winkelangaben erfolgen meist im Bogenmaß. Der Gültigkeitsbereich ist für α ∈ {0 . . . 2π} und für θ ∈ {0 . . . π}. Der Winkel α gibt an, auf welchem Längengrad sich der Punkt p beﬁndet. Ergänzend hierzu beschreibt der Winkel θ den Breitengrad. Punkt p liegt dann in dem Schnittpunkt der beiden Kreise, welche durch die Winkel bestimmt

17

3 Grundlagen

Abbildung 3.3: Ein Punkt p in Kugelkoordinaten wird durch zwei Winkel α und θ beschrieben.

werden.

Um einen Punkt p = (x, y, z), der in kartesischen Koordinaten vorliegt, in einem Kugelkoordinatensystem darzustellen, verwendet man die folgendenden Transfor- mationen:

x

Die Umwandlung der Kugelkoordinaten in kartesische Koordinaten erfolgt durch:

z = r cos α.

3.1.3 Geographische Koordinaten

Von geographischen Koordinaten wird gesprochen, wenn sie einen Punkt auf der

Erde beschreiben. Dabei ist die Erde in 360 ^◦ Längengrade λ und 180 ^◦ Breitengrade

ϕ aufgeteilt. Auch hier besteht ein Koordinatentupel aus zwei Winkeln.

18

Um diesen zu beschrieben wird λ entlang des Äquators gezählt. Der Breitengrad von p ergibt sich aus dem zugehörigen Winkel ϕ und hat einen willkürlich gewählten Nullmeridian. Der Schnittpunkt der durch die Winkel beschriebenen Kreise entspricht dem Punkt p. Die Winkelangaben erfolgen hierbei meist in Grad und

sind in den Gültigkeitsbereichen λ ∈ {−180 ^◦ , . . . , 180 ^◦ } und ϕ ∈ {−90 ^◦ , . . . , 90 ^◦ }

deﬁniert. Ein geographisches Koordinatensystem und der Punkt p sind in Abbildung 3.4 dargestellt.

Abbildung 3.4: Ein Punkt in Geographischen Koordinaten wird durch zwei Winkel beschrie-

tem nur in dem Gültigkeitsbereich der Winkel. In dieser Arbeit sind alle Winkelangaben in Bogenmaß angegeben. Daher sind die Gütigkeitsbereiche als λ ∈ ^{π π} {−π, . . . , π} und ϕ ∈ {− 2 } festgelegt. 2 , . . . ,

Um Kugelkoordinaten in geographische Koordinaten zu überführen kann folgende Beziehung deﬁniert werden: π

3 Grundlagen

Für die umgekehrte Richtung gilt: π

2

3.1.4 Zylindrische Koordinaten

Eine weitere Beschreibung von Punkten im dreidimensionalen Raum kann mit zylindrischen Koordinaten erfolgen. Sie setzten sich aus einem Winkel φ, einer Höhenangabe h und einem Radiuswert r zusammen. Die drei Komponenten sind für einen Beispielpunkt in Abbildung 3.5 eingetragen.

Abbildung 3.5: Ein Punkt in zylindrischen Koordinaten wird durch ein Radius r, einem Winkel

φ und einer Höhe h beschrieben.

Der Radius r beschreibt den Abstand zur y-Achse zum Punkt p. Der Winkel φ beschreibt die Drehung in der zx-Ebene. Die zugehörige Entfernung zur Ebene wird durch die Höhe h repräsentiert.

Die Transformationen eines Punktes p zwischen kartesischem und zylindrischem Koordinatensystem sind durch

20

3.2 Digitale Bildverarbeitung

und umgekehrt durch

gegeben.

3.2 Digitale Bildverarbeitung

Bilder liegen in der Regel als kontinuierliches Signal vor. Damit es digital verarbeitet werden kann, muss es in ein diskretes digitales Wertefeld überführt werden. Ein solches Wertefeld ist ein zweidimensionales Gitter, in welchem ein Punkt als Pixel oder Bildpunkt bezeichnet wird. Durch Diskretisieren, dass heißt Abtasten eines kontinuierlichen Signals, kann ein Bild als zweidimensionales Wertefeld abgespeichert werden. In diesem Wertefeld repräsentiert ein Pixel die Bestrahlungsstärke, welches der Intensität des abgetasteten Signals entspricht.

Die mathematische Repräsentation eines Bildes wird durch eine Bildfunktion I dargestellt. Für ein Grauwertbild beschreibt I(x, y) die Intensität eines Bildpunktes der Position (x, y). Ein Farbbild F (x, y) besteht aus drei Funktionen und wird daher auch vektorwertige Funktion genannt: ⎛ ⎞

durch ein (x, y)-Tupel mit x ∈ {0, . . . , X res } und y ∈ {0, . . . , Y res } identiﬁzierbar. Der Helligkeitswert eines Bildpunktes ergibt sich daher aus I(x, y).

Bis auf die Randpixel, besitzt jeder dieser Helligkeitswert eine 4er-, bzw. 8er-Nachbarschaft. Spricht man von einer 4er-Nachbarschaft, sind damit die vertikal und horizontal anliegenden Pixel gemeint. Bei der 8er-Nachbarschaft kommen die diagonal benachbarten Pixel um den Helligkeitswert hinzu. Diese Nachbarschaften sind in Abbildung 3.7 verdeutlicht.

21

3 Grundlagen

22

3.2.1 Partielle Ableitungen von Bildern

Hat man ein Helligkeitsbild I gegeben, dann gibt die partielle Ableitung eines Bildpunktes (x, y) die Richtung und Stärke des steilsten Anstiegs an. Möchte man also von einem Bildpunkt (x, y) berechnen, in welche Richtung und wie Steil der Anstiegs der Helligkeitswerte ist, verwendet man eine partielle Ableitung. Ein Gradient ist ein mathematischer Operator, mit welchem ein Vektorfeld ermittelt werden kann, welches die Richtungen der steilsten Anstiege beinhaltet. Bei Bildern lassen sich die Gradienten aus den partiellen Ableitungen in x- und y-Richtung zusammensetzen. Um die Ableitung anzunähern kann für einen Bildpunkt die Rückwärtsdiﬀerenz, Vorwärtsdiﬀerenz oder symmetrische Diﬀerenz gebildet werden.

sem Beispiel wurde eine symmetrische Ableitung gebildet. Hierfür wird zwischen dem vorherigen und nachfolgenden Intensitätswert die Diﬀerenz gebildet. Dies entspricht einer Annäherung der Steigung in x-Richtung des betrachteten Intensitätswert.

Formal ausgedrückt ergeben sich für die erste partielle Ableitung in x-Richtung

∂I

∂x die folgenden Annäherungen [Jä02]:

I(x, y) − I(x − 1, y)

3 Grundlagen

Wendet man diese Ableitungen auf einen Bildpunkt an, ergeben sich verschiedene Eﬀekte. Unter Verwendung der Rück- bzw. Vorwärtsdiﬀerenz wird der Punkt um einen halben Bildpunkt verschoben. Wendet man solch eine Ableitung auf ein ganzes Bild an, wird das komplette Bild um einen halben Bildpunkt verschoben. Möchte man ein Bild weiterverabeiten, ist diese Auswirkung meist unerwünscht. Bei der symmetrischen Diﬀerenz gibt es keine Verschiebung. Hierbei werden nur die Helligkeitswerte eines Bildpunktes verändert.

3.2.2 Punktoperationen

Bei Punktoperationen ist der resultierende Helligkeits- oder Farbwert eines Bildpunktes ausschließlich von seinem ursprünglichen Helligkeits- beziehungsweise Farbwert abhängig. Es werden daher keine benachbarten Bildpunkte in solche Operationen einbezogen. Solche Punktoperationen sind zum Beispiel Helligkeitskorrekturen, Kontrastverstärkung oder auch die Umwandlung von einem Farb- in ein Graustufenbild. Um ein Bild zu verändern, werden meist Hilfsmittel wie das Histogramm herangezogen. Das Histogramm eines Bildes ist die statistische Häuﬁgkeit der Grauwerte beziehungsweise der Farbwerte. Eine nähere Betrachtung von Punktoperationen ist in [Jä02] zu ﬁnden.

3.2.3 Nachbarschaftsoperationen

Bei Nachbarschaftsoperationen wird die Umgebung des betrachteten Bildpunktes berücksichtigt. Sie werden auch als Faltungsoperationen bezeichnet. Dies bedeutet, dass sich ein Pixel eines neuen Bildes aus einer gewichteten Summe von benachbarten Pixeln des Ursprungbildes zusammensetzt. Es entsteht eine lineare und translationsinvariante Abbildung des Eingangsbildes.

Hierbei spricht man von einer Faltung oder auch Konvolution. Sie bildet zwei Funktionen f und g auf eine neue Funktion ab. Als Operator wird meist das ∗ Symbol verwendet. Eine neue Funktion h entsteht daher durch f ∗ g. Faltungen sind assoziativ und kommutativ. Dies bedeutet, dass f ∗ (g ∗ h) = (f ∗ g) ∗ h und f ∗ g = g ∗ f gilt. Mathematisch ist die Faltung für zwei zweidimensionalen Funktionen folgendermaßen deﬁniert:

24

ist diese Deﬁnition in der Praxis nicht verwendbar. Für den diskreten Fall sieht die Faltung ähnlich aus:

unterschiedliche Größen besitzen, welche abhängig von ihrem Einsatzgebiet und dem gewünschten Eﬀekt ist.

Der Ursprung der Maske g wird bei einer Filterung mit einer ungeraden Maskengröße über den zu ﬁlternden Bildpunkt der Bildfunktion I gelegt. Die nun übereinanderliegenden Punkte werden miteinander multipliziert und aufsummiert. Im Normalfall ist der Filter deutlich kleiner als das Bild und arbeitet daher lokal. Dieser Vorgang ist in Abbildung 3.9 dargestellt. Die in dem Beispiel verwende-

Abbildung Das 3 × 3-Maske gefaltet.

jeden Bildpunkt gelegt und der neue Wert berechnet.

te Maske ist eine 3 × 3 Glättungsmaske. Für jeden Punkt im Eingangsbild wird nun durch Multiplikation und Addition der Wert für den Punkt im neuen Bild

25

3 Grundlagen

berechnet.

In den Randbereiche des Bildes werden Bildpunkte verwendet, die außerhalb des Bildbereiches liegen. Dieses Problem ist zum Beispiel bei x = 0 und y = 0 der Fall und ist in Abbildung 3.9 nachvollziehbar. Um es zu beheben, gibt es verschiedene Möglichkeiten.

Bei der Berechnung des neuen Bildes kann der Randbereich, für den die Faltung nicht ausführbar ist, ausgelassen werden. Dies hat zur Folge, dass das Bild kleiner wird. Bei einer 5 × 5-Maske würden an jedem Rand zwei Bildpunkte verloren gehen. Bei vielen Anwendungen ist das jedoch unerwünscht und die Bildgröße soll beibehalten werden. Die zweite Möglichkeit besteht darin, die Intensitäten des Eingangsbildes zu übernehmen. Würde man das Bild glätten und daraufhin auf Kanten untersuchen, könnten in den Randbereichen Strukturen exisitieren, welche keine Kanten darstellen. Bei der dritten Möglichkeit werden die Randbereiche mit einem konstanten Wert aufgefüllt. Stellt man sich das Eingangsbild als periodische Funktion vor, können die fehlenden Werte mit denen des unteren und oberen sowie rechten und linken Bildrandes aufgefüllt werden.

Partielle Ableitungen von Bildern mit einer Faltung

Die partiellen Ableitungen von Bildern können durch eine Faltung berechnet werden. Wie in Abschnitt 3.2.1 gezeigt, wird zwischen Rückwärtsdiﬀerenz, Vorwärtsdiﬀerenz und symmetrischer Diﬀerenz unterschieden. Da für diese Arbeit nur die symmetrische Diﬀerenz relevant ist, wird diese im Folgenden näher betrachtet.

Die Maske für eine diskrete symmetrische Ableitung im eindimensionalen Fall ist:

2

Legt man diese Maske auf einen konkreten Wert, von welchem die Ableitung ermittelt werden soll, wird der vorherige Wert und der nachfolgende jeweils gleich gewichtet und die Diﬀerenz berechnet. Dies entspricht der symmetrischen Ableitung aus Abschnitt 3.2.1. Die diskrete partielle Ableitung für den zweidimensio-

26

nalen Fall ist daher: ⎤ ⎡ ⎤ ⎡

Lineare Glättungsﬁlter

Glättungsﬁlter mitteln die Intensitäten der Bildpunkte in einem kleinen Bereich. Die einfachste Form ein geglättetes Intensitätenbild zu erhalten besteht darin, alle Bildpunkte innerhalb der Maske zu addieren und den resultierenden Wert durch die Anzahl der aufsummierten Pixel zu teilen. Ein solcher Filter wird als Rechteckﬁlter bezeichnet und stellt die einfachste Glättung dar. Typische Größen für Filtermasken im zweidimensionalen Fall sind (3 × 3), (5 × 5), (7 × 7) . . .. Für einen 3 × 3 großen Filterkern ergibt sich daraus: ⎡ ⎤

Bilder, die mit solch einer Maske geglättet werden, wirken weich und verschwommen.

Eine weitere Möglichkeit stellt eine unterschiedliche Gewichtung der Bildpunkte je nach Lage dar. In Abbildung 3.9 ist eine solche Glättungsmaske gezeigt. Im Gegensatz zu den Rechteckﬁltern wird hier das Zentrum am stärksten gewichtet. Die 4er-Nachbarschaft wird schwächer als das Zentrum, jedoch stärker als die restlichen Bildpunkte gewichtet. Diese Maske enthält die Werte der diskreten Binomialverteilung und ist als Binomialﬁlter bekannt [Jä02]. Die Filterkoeﬃzienten können anhand des Pascalschen Dreiecks [CG98] hergeleitet werden, welches den Binomialkoeﬃzienten entspricht. Die Varianz gibt hierbei die eﬀektive Breite der Maske für die Glättung an. Aus Gründen der Symmetrie können nur Binome mit gerader Ordnung, beginnend bei 2, verwendet werden. Für den eindimensionalen Fall ergibt sich für eine Glättung mit dem Binom der Ordnung 2:

27

3 Grundlagen

Möchte man ein Bild glätten, benötigt man eine zweidimensionale Filtermaske. Ein zweidimensionaler Binomialﬁlter entsteht durch Faltung eines horizontalen eindimensionalen Binomialﬁlter mit einem vertikalen eindimensionalen Binomialﬁlter. Der Binomialﬁlter der Ordnung 2 entspricht einer 3 × 3-Maske: ⎤ ⎤ ⎡ ⎡

⎥

⎦

Da die Maske aus einer Faltung zweier eindimensionaler Binomialﬁlter entsteht, kann man anstatt eines zweidimensionalen Filters auch zwei eindimensionale Filterungen hintereinander anwenden. Daher spricht man auch davon, dass ein Binomialﬁlter separabel ist.

Geht die Ordnung des Filters gegen unendlich, erhält man folgende Funktion:

u ² + v 2

Hierbei entspricht σ der Standardabweichung der Gauß-Funktion und gibt die Größe der Filtermaske an. Je größer σ ist, desto größer ist die Dämpfung hoher Frequenzbereiche. Das Bild wird somit stärker geglättet. Durch σ lassen sich beliebig große Glättungsﬁlter konstruieren. Eine nähere Betrachtung ist in [Tö05] zu ﬁnden.

28

3.3 Beschreibung von Oberﬂächen

Wenn man 3D-Objekte bearbeiten und manipulieren möchte, muss man eine geeignete Art für deren Darstellung auswählen. Hierbei lassen sich Geometrie und Topologie einer Oberﬂäche unterscheiden. Die Geometrie beschreibt die Position von expliziten Punkten einer Oberﬂäche. Die Topologie hingegen beschreibt die Zusammenhänge zwischen diesen Punkten. Zusätzlich müssen die Farben und die Normalen einer Oberﬂäche dargestellt werden können.

Die Farben der Oberﬂäche werden in der Computergraﬁk meistens über Texturen bestimmt. Dafür muss die Oberﬂäche in ein zweidimensionales Koordinatensystem abgebildet werden. In diesem Koordinatensystem bezeichnet (0, 0) die linke untere Ecke und (1, 1) die rechte obere Ecke der Textur. Für die Achsen sind die Bezeichungen u und v üblich. An jedem Punkt der Oberﬂäche muss eine Texturkoordinate bekannt sein, die festlegt, welche Stelle der Textur sich an diesem Punkt beﬁndet.

Als Normale wird der Vektor bezeichnet, der im rechten Winkel zur Tangentialebene an einem bestimmten Punkt der Oberﬂäche steht. Dieser kann bei einer kontinuierlichen Oberﬂäche aus den Geometrie- und Topologieinformationen der Oberﬂäche berechnet werden. Das zusätzliche Speichern der Normalen erweist sich jedoch oft als vorteilhaft.

In der Computergraﬁk sollen Oberﬂächen häuﬁg nur von einer Seite sichtbar sein. Dadurch können zum Beispiel bei der Darstellung der Oberﬂäche Ressourcen gespart werden, da nur eine Seite beim Rendern berücksichtigt werden muss. Welche Seite der Oberﬂäche sichtbar ist, wird ebenfalls durch die Normale beschrieben. Sie gibt somit die Neigung und die Oberseite der Oberﬂäche an einer bestimmten Stelle an.

Handelt es sich um diskretisierte Oberﬂächen, muss es keine eindeutige Normale zu einem Teilstück der Oberﬂäche geben. Sie muss dementsprechend zusätzlich deﬁniert werden. In der Computergraﬁk hat man darüber hinaus häuﬁg den Wunsch einen anderen Normalenvektor als den korrekt berechneten anzugeben. Dadurch lassen sich verschiedene Eﬀekte bei der Darstellung der Oberﬂäche erzielen. Bei der Schattierung einer Oberﬂäche wird nicht die Topologie und Geometrie der Oberﬂäche, sondern deren Normalen verwendet. Es ist so zum Beispiel möglich, auf einer komplett planaren Fläche den Eindruck eines Reliefs zu erwecken.

29

3 Grundlagen

Zur Deﬁnition von Oberﬂächen gibt es verschiedene Darstellungsformen, von denen häuﬁg mehrere zum Bearbeiten eines Problems notwendig sind.

3.3.1 Höhenfelder

Bei der expliziten Darstellung dreidimensionaler Formen wird jeweils einem (x, y)-Tupel in einem Raster ein z-Wert zugeordnet (siehe Abbildung 3.10). Die allgemeine Form lautet:

f (x, y) = z mit x,y,z ∈ R.

Oberﬂächen dieser Art werden auch 2,5-dimensionale Oberﬂächen genannt. Sie haben den Nachteil, dass keine vertikalen Tangenten dargestellt werden können. In diesem Fall müsste man einem (x, y)-Tupel zwei z-Werte zuordnen, was nicht möglich ist. Da durch Rotieren des Höhenfeldes dieser Fall eintreten könnte, wird diese Art der Darstellung auch als nicht rotationsinvariant bezeichnet. Um zum Beispiel eine komplette Kugel darstellen zu können, muss sie in Segmente unterteilt werden.

Es ist jedoch eine der am einfachsten verständlichen Darstellungsarten. Sind die (x, y)-Tupel diskretisiert und besitzen einen beschränkten Wertebereich, kann die Oberﬂäche durch Aufzählen aller Werte, statt durch ein Bildungsgesetz, beschrieben werden.

Die Abbildung der Oberﬂäche auf ein zweidimensionales Texturkoordinatensystem ist hier sehr einfach. Da es sich um eine 2,5D-Darstellung handelt, enthält die Oberﬂäche, aus Richtung der z-Achse betrachtet, keinen Überschneidungen.

30

Sie kann also einfach orthogonal in Richtung z projiziert werden, um ein perfektes Texturmapping zu erhalten.

Ein häuﬁges Anwendungsgebiet für die explizite Darstellung sind Terrainmodelle. Hier beschreibt das (x, y)-Tupel das jeweilige Raster und der z-Wert die entsprechende Höhe einer Landschaft.

Normalenfelder

Höhenfelder können als zweidimensionale Graustufenbilder betrachtet werden. Der Helligkeitswert in einem bestimmten Pixel stellt dann die jeweilige Höhe an dieser Position im Höhenfeld dar. In Abschnitt 3.2.1 wurde gezeigt, wie digitale Abbildungen partiell abgeleitet werden können, um deren Gradienten zu berechnen. Dies ist auch für Höhenfelder möglich. Man erhält dann die Steigungen der Oberﬂäche an einer bestimmten Stelle in x oder y-Richtung, p(x, y) und q(x, y). Der Vektor der senkrecht auf p(x, y) und q(x, y) steht, entspricht der Flächennormale n(x, y). Ein Normalenfeld kann also als die Ableitung eines Höhenfeldes betrachtet werden. In Abbildung 3.11 ist der Zusammenhang zwischen Normale und Gradienten aufgezeigt.

berechnen, kann das Kreuzprodukt für Vektoren verwendet werden:

n(x, y) = p(x, y) × q(x, y).

Es ist auch möglich, eine Normale n(x, y) wieder in die Oberﬂächengradienten an dieser Stelle aufzuteilen. Dies erfolgt über folgende Gleichungen:

31

3 Grundlagen

−n(x, y) x

Zu jedem Höhenfeld ist ein eindeutiges Normalenfeld gegeben. Umgekehrt muss dies nicht der Fall sein. Man spricht von integrierbaren und nichtintegrierbaren Normalen- oder Gradientenfeldern. Ein nicht integrierbares Normalenfeld beschreibt also nicht eindeutig eine bestimmte Oberﬂäche. Es lässt sich leicht anhand der Gradientfelder erkennen, ob das zugehörige Normalenfeld integrierbar ist. Ab-

A nach Punkt B genommen wird, ergibt sich in Punkt B der gleiche z-Wert. In Abbildung 3.13 ist ein nicht integrierbares Gradientenfeld dargestellt. Je nachdem welchen der beiden durch stärker gezeichnete Pfeile markierten Pfade von A nach B man entlang geht, erhält man unterschiedliche Werte für z. Diese Unterscheiden sich in diesem Fall um den Fehler f .

3.3.2 Punktwolken

Objekte können als Punktwolken der Form

P = {(x 1 , y 1 , z 1 ), (x 2 , y 2 , z 2 ), . . . , (x n , y n , z n )}

beschrieben werden (siehe Abbildung 3.14). Hier wird nur die Geometrie einer Oberﬂäche gespeichert. Durch die fehlenden Topologieinformationen sind viele Ar-

32

beitsschritte wie zum Beispiel Verformen oder Verfeinern nicht möglich. Deswegen müssen sie zum Bearbeiten meistens in andere Darstellungsformen umgewandelt werden. Es handelt sich dabei immer um diskretisierte Objekte. Eine kontinuierliche Art Punktwolken zu deﬁnieren gibt es nicht. Sie werden häuﬁg als Eingangs-oder Ausgangsdaten verwendet. Die Beschreibung der Farbwerte als Projektion auf eine 2D-Abbildung ist hier ebenfalls möglich. Es muss dann zu jedem Punkt eine entsprechende Texturkoordinate gespeichert werden. Es ist hier allerdings üblicher, den Farbwert direkt mit dem Punkt abzuspeichern.

33

3 Grundlagen

3.3.3 Polygonale Netze

Die am weitesten verbreitete Art zur Darstellung von 3D-Objekten in der Computergraﬁk ist ein polygonales Netz (siehe Abbildung 3.15). Ein Polygon ist ein Vieleck. Es besteht demnach aus mindestens drei Eckpunkten (vertices), die durch Kanten (edges) verbunden sind. Ein Polygon des Netzes wird auch als Facette (face) bezeichnet. Es gilt als konvex, wenn jede mögliche Verbindung zwischen zwei Punkten des Polygons komplett in ihm liegt. In Abbildung 3.16 sind zwei Polygone dargestellt. Bei dem linken handelt es sich um ein konvexes Polygon, das rechte entspricht dieser Anforderung nicht. Des Weiteren werden sie in planare und nicht planare Polygone unterteilt. Bei einem planaren Polygon liegen alle Eckpunkte in einer Ebene wie in Abbildung 3.17 zu erkennen ist. Ist ein Polygon nicht planar, hat das zur Folge, dass die beschriebene Oberﬂäche nicht eindeutig ist. In Abbildung 3.18 sind beide Möglichkeiten aufgezeigt, wie ein Polygon mit

vier Eckpunkten unterteilt werden kann. Es ergeben sich zwei unterschiedliche Oberﬂächen.

34

Drahtgittermodell genannt. Oft werden als Polygone nur Dreiecke verwendet. Diese haben zwei Vorteile gegenübere anderen Polygonen. Dreiecke sind immer konvex und liegen zwangsläuﬁg in einer Ebene.

y

z zum Beispiel ein Höhenfeld. Es werden komplexe Datenstrukturen benötigt um diese zu verwalten. Das Bestimmen von Texturkoordinaten für Polygonnetze erweist sich schwieriger als zum Beispiel für ein Höhenfeld. Eine einzige Projektion in den zweidimensionalen Raum reicht hier meistens nicht aus um ein komplettes Netz abzubilden. Es muss zu jedem Eckpunkten im Netz eine Position auf der Textur gespeichert werden.

Es gibt verschiedene Möglichkeiten Polygonnetze zu beschreiben. Eine Möglichkeit ist zum Beispiel das facettenzentrierte Deﬁnieren von Polygonen. Es werden sowohl Eckpunkte, Normalenvektoren als auch die Texturkoordinaten in getrennten Listen gespeichert. Die einzelnen Facetten können dann aus den Indizes der einzelnen Listen zusammengebaut werden. Ein Polygonnetz P kann somit folgen-

35

3 Grundlagen

dermaßen beschrieben werden:

^T , (x 2 , y 2 , z 2 ) ^T , . . . , (x n , y n , z n ) ^T Eckpunkte v = (x 1 , y 1 , z 1 ) ,

Texturkoordinaten vt =

Normalenvektoren vn =

Facetten f = (v 1 , vt 1 , vn 1 ), (v 2 , vt 2 , vn 2 ), . . . , (v n , vt n , vn n ) ,

f 1 , f 2 , . . . , f n Polygonnetz P = .

Ein Dateiformat, welches diese Technik verwendet, ist das obj-Dateiformat. Dieses wurde von der Firma Wavefront Technologies entwickelt, und hat sich als oﬀenes Dateiformat sehr schnell verbreitet. Es hat den Vorteil, dass es sehr speichereﬃzient ist. Das Polygonnetz wird letztendlich nur aus Indizes zusammengebaut. Dadurch müssen mehrfach verwendete Koordinaten nur einmal gespeichert werden. Allerdings sind Aufgaben wie zum Beispiel das Finden benachbarter Polygone hier sehr zeitaufwändig.

Deswegen gibt es Strukturen, die für das Arbeiten mit Polygonnetzen besser geeignet sind. Eine häuﬁg verwendete Datenstruktur dieser Art ist die doppelt verkettete Kantenliste (Half-Edge-Data-Structure) [Yam02]. Wie in Abbildung 3.19

gezeigt, werden hier nur Halbkanten verwendet um die Topologie des Polygonnet-

36

zes zu beschreiben. Jeweils zwei Halbkanten bilden eine komplette Kante. Jede Halbkante gehört zu genau einem Eckpunkt. Dieser enthält außerdem seine Koordinaten, die entsprechende Texturkoordinate und eine Normale. Jeder Eckpunkt merkt sich alle Halbkanten, die an ihm beginnen. So erreicht man schnell alle Facetten, die an einen Eckpunkt angrenzen. Jede Halbkante zeigt auf die jeweils nächste Halbkante der selben Facette. Da dies immer gegen den Uhrzeigersinn erfolg, ist die Vorderseite der Facette festgelegt. Liegt eine Halbkante am Rand der Oberﬂäche, zeigt sie auf sich selbst. Über die jeweiligen Partnerhalbkanten erreicht man schnell die Nachbarfacetten.

37

3 Grundlagen

38

Kapitel 4

Rekonstruktion mittels

Shape-from-Shading

In diesem Kapitel wird ein Verfahren zur Rekonstruktion von Oberﬂächen mit Hilfe von Shape-from-Shading vorgestellt. Zu diesem Zweck muss geklärt werden, wie man das Reﬂektionsverhalten einer Oberﬂäche beschreibbar machen kann. Danach folgen einige Details zu der Problemstellung des Shape-from-Shading und bestehenden Lösungsansätzen. In den darauf folgenden Abschnitten wird ein Framework zur Rekonstruktion vorgestellt, und Schritt für Schritt erläutert.

4.1 Reﬂektionsverhalten von Oberﬂächen

Triﬀt Licht auf eine Oberﬂäche, kann dieses in verschiedener Weise mit ihr interagieren. In der Realität tritt dabei immer eine Kombination aus Brechung und Reﬂektion auf.

Eine reﬂektierende Oberﬂäche strahlt das Licht zurück. Wird das Licht gebrochen (transmitted), wird es an der anderen Seite der Oberﬂäche abgestrahlt. Außerdem kann es absorbiert, das heißt geschluckt werden. Es wird in diesem Fall in Wärme umgewandelt und ist in keiner Weise mehr als Licht zu sehen. Da es

39

4 Rekonstruktion mittels Shape-from-Shading

sich bei Licht um Energie handelt, gilt der Satz der Energieerhaltung:

Licht Licht Licht Licht.

Unabhängig davon, ob das Licht gebrochen oder reﬂektiert wird, kann es bei diesem Vorgang mehr oder weniger gestreut werden. Das heißt, dass die Oberﬂäche matt oder spiegelnd erscheinen kann. In Abbildung 4.1 sind die drei Komponenten, Absorbtion, Streuung und Spiegelung, aus denen sich eine Reﬂektion zusammensetzt dargestellt.

Um mit dem Rückstrahlverhalten einer Oberﬂäche rechnen zu können, muss man ihr Verhalten mathematisch erklärbar machen. Dafür gibt es viele verschiedene Modelle, welche die Realität mehr oder weniger genau abstrahieren.

4.1.1 Diﬀerentielle Raumwinkel

Um das Reﬂektionsverhalten einer Oberﬂäche zu deﬁnieren, ist die Menge an Licht, die von einem bestimmten Punkt aus gesehen werden kann, relevant. Man spricht von einer Menge, da Licht als Energie pro Fläche gemessen wird.

Hierfür ist der Ausdruck des diﬀerentiellen Raumwinkels von Bedeutung. Ein Raumwinkel ω ist das räumliche Gegenstück zu einem Bogenwinkel in der Ebene. Er ist als der Quotient zwischen einer Teilﬂäche S auf einer Kugel und dem

40

Quadrat des Radius r der Kugel deﬁniert:

Da sich der Raumwinkel aus dem Verhältnis zweier Flächen ergibt, ist er eigentlich dimensionslos. Um ihn trotzdem in mathematischen Formeln kennzeichnen zu können, hat er die Einheit Steradiant [sr] erhalten.

Da bei der Lichtmessung die eintreﬀende Menge an Licht aus einer bestimmten Richtung betrachtet werden soll, wählt man einen entsprechend kleinen, diﬀerenzierten Raumwinkel. Dieser Raumwinkel wird als diﬀerentieller Raumwinkel dω bezeichnet:

Meistens handelt es sich bei diﬀerentiellen Raumwinkeln um Winkel auf einer

Einheitskugel. In diesem Fall wird r ² = 1.

4.1.2 Relevanz des Einfallwinkels für die Lichtintensität

Bei der Messung der Lichtintensität ist nicht die tatsächliche Größe einer strahlenden Oberﬂäche von Bedeutung. Es ist nur die Größe der Oberﬂäche, die von einem bestimmten Punkt aus gesehen wird relevant. Dieser Eﬀekt wird als Verkürzung, oder foreshortening bezeichnet.

In der linken Abbildung triﬀt Licht mit der Intensität I = 1 senkrecht auf eine

41

4 Rekonstruktion mittels Shape-from-Shading

Oberﬂäche. Der Winkel zwischen der Richtung des eintreﬀenden Lichts und der

¹ Flächennormale beträgt θ = 0. Es wird auf die Länge x = cos 0 = 1 verteilt.

Auf der rechten Seite triﬀt der Lichtstrahl mit dem Winkel θ zur Oberﬂächen- 1

normale ein. Die Fläche, auf die das Licht verteilt wird, ist um den Faktor cos(θ)

größer. Entsprechend nimmt die durch das Licht erzeugte Helligkeit der Oberﬂäche um den Faktor cos(θ) ab.

Dieser Eﬀekt gilt nicht nur für die Neigung einer beleuchteten Oberﬂäche, die durch weniger Lichtstrahlen getroﬀen wird. Auch die Neigung der Lichquelle, die entsprechend weniger Lichstrahlen in eine bestimmte Richtung aussendet, muss beachtet werden. Ein gutes Beispiel hierfür ist der Raumwinkel, den eine geneigte, strahlende Oberﬂäche in Bezug auf einen bestimmten Punkt einer beleuchteten Oberﬂäche einnimmt. In Abbildung 4.3 ist die Oberﬂäche A um den Winkel α in

Bezug auf den Punkt P geneigt. Für die Berechnung des Raumwinkels ω muss die Fläche dementsprechend mit dem Faktor cos α multipliziert werden:

42

4.1.3 Strahldichte und Bestrahlungsstärke

Die Strahldichte oder radiance bezeichnet die Lichtenergie, die von einem Punkt P in eine bestimmte Richtung θ, α abgestrahlt wird. Sie wird in Watt pro Fläche und Raumwinkel angegeben:

das Licht nicht mit dem passierten Medium interagiert. Das heißt man geht von einem Vakuum aus. Die gleiche Strahldichte, die einen Punkt P 1 in Richtung Punkt P 2 verlässt, kommt an P 2 aus Richtung P 1 an.

Will man berechnen, wieviel Licht an einer bestimmten Stelle einer Oberﬂäche aus einer bestimmten Richtung mit dem diﬀerenziellen Raumwinkel dω eintriﬀt, muss allerdings der Einfallswinkel und die daraus resultierende Verkürzung der Oberﬂäche berücksichtigt werden. Deswegen wurde zusätzlich der Begriﬀ der Bestrahlungsstärke (oder irradiance) eingeführt. Die Bestrahlungsstärke ergibt sich aus der eintreﬀenden Strahldichte multipliziert mit dem entsprechenden diﬀerentiellen Raumwinkel multipliziert mit dem Kosinus des Einfallwinkels:

Richtungen, aus denen Licht auf eine Oberﬂäche strahlen kann, liegen auf einer Halbkugel über der Oberﬂäche. Es ist nun möglich die gesamte eintreﬀende Lichtenergie an einer bestimmten Stelle der Oberﬂäche durch integrieren über diese Hemisphäre zu berechnen.

4.1.4 Lichtmessung mit Kameras

Beschäftigt man sich mit der Rekonstruktion von Oberﬂächen aus Fotograﬁen, muss geklärt werden, ob man von der Helligkeit in einem bestimmten Bildpunkt der Fotograﬁe überhaupt Rückschlüsse auf die tatsächliche Helligkeit an dem abgebildeten Punkt der Oberﬂäche schließen kann.

43

4 Rekonstruktion mittels Shape-from-Shading

In Abbildung 4.4 ist der schematische Aufbau einer Kamera dargestellt. Hierbei könnte es sich sowohl um eine digitale als auch um eine analoge Kamera handeln. Der Unterschied kann auf das verwendete lichtempﬁndliche Medium reduziert werden. Dieses ist in der Abbildung durch Π gekennzeichnet und liegt im Abstand f hinter der Linse. Dieser Abstand wird als Fokuslänge bezeichnet. Linse und optisches Medium liegen parallel und zentriert zueinander. Die Achse, die beide in der Mitte verbindet, wird optische Achse genannt. Die Mitte der Linse wird als optische Mitte O bezeichnet. Lichstrahlen, die diesen Punkt schneiden, werden durch die Linse nicht gebrochen. Ein Punkt P , der um den Abstand z von der

Kamera entfernt ist, wird auf einen Punkt P abgebildet. Er liegt im Schärfe- der Kamera. Durch Ändern der Fokuslänge der Kamera lässt sich dieser Bereich manipulieren. Dies ändert aber nichts an den grundlegenden mathematischen Zusammenhängen, und kann hier vernachlässigt werden.

Abbildung 4.5: Zusammenhang zwischen der Strahldichte einer Oberﬂäche und der eintreﬀen-

44

ferentiellen Fläche ∂A auf einer strahlenden Oberﬂäche auf den Punkt P mit der diﬀerentiellen Fläche A auf dem optischen Medium der Kamera dargestellt.

Die eintreﬀende Lichtintensität auf dem Medium ist abhängig vom diﬀerentiellen Raumwinkel ∂ω. Dieser beschreibt die Strahldichte unter Berücksichtung des

Einfallwinkels α, mit welcher der Punkt P von der optischen Mitte aus projiziert

wird. Durch den Strahlensatz entspricht ∂ω ebenfalls dem Winkel, der beschreibt, welche verkürzte Fläche der strahlenden Oberﬂäche von der optischen Mitte aus gesehen werden kann. Er kann wie folgt berechnet werden:

∂A cos α

2 = z 2 . ∂ω = cos ^α cos α

Diese Gleichung kann umformuliert werden, um das Verhältnis der beiden diﬀe- Flächen ∂A und ∂A zueinander auszudrücken: 2

cos α ∂A z

∂A = . (4.1)

cos β f

Der Raumwinkel Ω beschreibt den Teil des Lichtes, der von Punkt P aus auf die

π a d ² berechnet werden. Linse der Kamera triﬀt. Die Fläche der Linse kann über Für die Berechnung von Ω ergibt sich damit: d 2

d ² cos α π π ³ α. z 2 = Ω = cos (4.2)

4 4 z

cos α

Man kann nun die Energie ∂P , die von der Fläche ∂A in Richtung der Linse der Kamera abgestrahlt wird, durch die Strahldichte L der Oberﬂäche ausdrücken. Sie entspricht der Strahlungsdichte der Oberﬂäche L multipliziert mit dem Raumwinkel, den die Linse aus Sicht der Oberﬂäche einnimmt, Ω multipliziert mit der abstrahlenden diﬀerenzierten Fläche ∂A verkürzt durch den Abstrahlwinkel β.

∂P = LΩ∂A cos β.

Mit Gleichung (4.2) für Ω ergibt sich: d 2

π ³ α cos β. L∂A cos ∂P =

4 z

4 Rekonstruktion mittels Shape-from-Shading

Die Energie ∂P wird durch die Linse auf die Fläche ∂A projiziert. Es handelt

sich dabei um das einzige Licht, welches diese Stelle erreicht. Deswegen lässt sich die, auf dieser Stelle eintreﬀende, Lichtintensität folgendermaßen berechnen: 2

^∂A Ersetzt man hier ∂A durch (4.1) erhält man: 2

In der Fotograﬁe beschreibt diese Gleichung die Lichtstärke des Objektivs der Kamera. Es lassen sich zwei wichtige Schlussfolgerung aus ihr ziehen. Sie zeigt, dass die Lichtintensität L an einem bestimmten Punkt einer Oberﬂäche proportional zur Intensität dieses Punktes nach der Abbildung durch eine Kamera ist. Das heißt, dass die Bildintensitäten, die durch die Fotograﬁe gegeben sind, wirklich Rückschlüsse auf die tatsächliche Helligkeit der Oberﬂäche an dieser Stelle zum Zeitpunkt der Aufnahme zulassen. Außerdem lässt sich erkennen, dass der Term cos α, welcher die in der Kamera auftretende Verkürzung durch den Einfallwinkel auf dem optischen Medium beschreibt, durch seine vierfache Potenz gewichtet ist. Die Auswirkungen dieses Faktors sind also so gering, dass sie im Weiteren vernachlässigt werden können.

4.1.5 Bidirectional Reﬂectance Distribution Function

In der Computergraﬁk werden Beleuchtungsmodelle benutzt um Oberﬂächen Eigenschaften für das Rendering zuzuweisen. Beim Rendern werden aus den 3D-Daten einer Szene, der Beleuchtung und den Oberﬂächeneigenschaften 2D Abbildungen generiert. Beim Shape from Shading soll aus 2D-Abbildungen sowie Approximationen der Beleuchtungssituation und der Oberﬂächeneigenschaften die 3D-Szene rekonstruiert werden.

Beleuchtungsmodelle werden in lokale und globale Beleuchtungsmodelle unterteilt. Globale Beleuchtungsmodelle (global illumination) beschreiben, wie sich Licht ausbreitet. Hiermit sind Raytracing und Radiosity sowie diverse Varianten gemeint [FP03]. Lokale Beleuchtungsmodelle beschreiben, wie Licht mit einer

46

Oberﬂäche reagiert. Von Bedeutung sind hier der Einfall- und der Betrachterwinkel sowie die Flächennormale an der entsprechenden Stelle der Oberﬂäche. Man spricht von einer Bidirectional scattering distribution function (BSDF). Mit ihr werden sowohl Reﬂektion als auch Brechung beschrieben. Die BSDF kann in eine reﬂektierende und eine brechende Funktion aufgeteilt werden. Man erhält dann

die Bidirectional reﬂectance distribution function (BRDF) [NRH ⁺ 22] und die Bi- transmittance distribution function (BTDF). In Abbilddung 4.6 ist eine Oberﬂäche mit reﬂektierendem und brechendem Anteil dargestellt. Im weiteren Verlauf der Arbeit ist nur die BRDF von Bedeutung.

winkel sowie die Flächennormale werden als Einheitsvektoren N mit den

Kugelkoordinaten (θ L , α L ), (θ V , α V ) und (θ N , α N ) dargestellt. Gibt man Einfalls-und Betrachterwinkel im lokalen Kugelkoordinatensystems der Flächennormale an, ergibt sich für den Einfallwinkel:

(θ i , α i ) = (θ N − θ L , α N − α L ),

47

4 Rekonstruktion mittels Shape-from-Shading

48

und für den Betrachterwinkel:

(θ o , α o ) = (θ N − θ V , α N − α V ).

tierter Strahldichte an. Sie lautet:

Dabei beschreibt L i (θ i , α i ) cos(θ i )dω die eintreﬀende Bestrahlungsstärke aus Richtung (θ i , α i ) und L o (θ o , α o ) die Strahldichte in Richtung (θ o , α o ). Die reﬂektierte Strahldichte in eine bestimmte Richtung L o (θ o , α o ), die aus der Bestrahlungsstärke L i (θ i , α i ) cos(θ i )dω erfolgt, lässt sich dann folgendermaßen bestimmen:

die resultierend aus dem kompletten einfallenden Licht reﬂektiert wird. Diese lässt sich durch Integrieren über die gesamte Hemisphäre Ω möglicher Bestrahlungsrichtungen berechnen:

dingungen erfüllt werden. Sie muss das Gesetz der Helmholz-Reziprozität und das Gesetz der Erhaltung der Energie erfüllen.

Richtung des Lichts umkehrbar sein muss. Dies ist der Fall, wenn Einfallswinkel

49

4 Rekonstruktion mittels Shape-from-Shading

und Betrachterwinkel vertauscht werden können:

p(θ i , α i , θ o , α o ) = p(θ o , α o , θ i , α i ).

In Abbildung 4.8 ist dieser Fall dargestellt. Das Gesetz der Erhaltung der Energie besagt, dass Energie weder verloren gehen, noch dazugewonnen werden kann. Das heißt im Falle einer BRDF, dass das Integral über das komplette einfallende Licht immer größer oder gleich dem Integral über das reﬂektierte Licht sein muss:

Ω Ω

Ein kleinerer Wert für das reﬂektierte Licht ist erlaubt, da Licht auch absorbiert werden kann.

Da eine BRDF von vier Winkeln (θ i , α i , θ o , α o ) abhängig ist, handelt es sich um eine vierdimensionale Funktionen. Man könnte nun für jede mögliche Kombination dieser Winkel einen Wert speichern und so die Eigenschaften der Oberﬂäche genau deﬁnieren. Dies ist in der Praxis aber wegen der immensen Datenmengen nicht oder nur begrenzt möglich. Stattdessen wählt man mehr oder weniger komplexe mathematische Funktionen, die die Realität approximieren. Diese fungieren dann als Bildungsgesetz der BRDF. Beispiele hierfür sind das Phong- [FP03] oder das Torrance-Sparrow-Beleuchtungsmodell [Bli77].

4.1.6 Das Lambertsche Gesetz

Geht man davon aus, dass das Licht, welches an einem Punkt der Oberﬂäche eintriﬀt, gleichmäßig in alle Richtungen abgestrahlt wird, erhält man folgende BRDF:

p Lambert (θ i , α i , θ o , α o ) = p.

Diese beschreibt eine perfekt diﬀuse Oberﬂäche. Sie ist weder vom Einfalls- noch vom Rückstrahlwinkel des Lichts abhängig. Licht aus jeder beliebigen Richtung der Hemisphäre wird gleichmäßig in alle Richtungen der Hemisphäre abgestrahlt. Das Licht wird also gestreut. Es steht p für das intrinsische Rückstrahlvermögen der Oberﬂäche an diesem Punkt, welches Albedo genannt wird. Dieser Wert liegt

50

zwischen Null und eins. Die Diﬀerenz zwischen der Albedo und eins ist der Teil des Lichts, der von der Oberﬂäche absorbiert wird.

Die gesehene Helligkeit an diesem Punkt der Oberﬂäche ist also lediglich von der Verkürzung der Oberﬂäche aus Sicht der Lichtquelle abhängig. Das bedeutet, dass die gesehene Lichtintensität der Oberﬂäche alleine von dem Term cos(θ i ) abhängt. Dies ist als das Lambertsche Gesetz bekannt.

51

4 Rekonstruktion mittels Shape-from-Shading

4.2 Shape-from-Shading

Es gibt viele verschiedene Ansätze um Shape-from-Shading zu realisiern. Das grundlegende Prinzip ist aber immer das gleiche. Es muss eine Oberﬂäche erstellt werden, die bei gleicher Beleuchtung und gleichem Blickwinkel in jedem Punkt die gleiche Helligkeit erzeugt.

Das Problem besteht darin, dass für jedes Pixel im Bild nur ein Grauwert zur Verfügung steht. Um eine Oberﬂäche zu beschreiben sind aber mindestens zwei Werte pro Vertex notwendig. Diese entsprechen zum Beispiel den zwei Gradienten in x- und y-Richtung (siehe Abschnitt 3.3.1). Es handelt sich bei der Berechnung somit um ein unterbestimmtes System. Das lässt sich an Abbildung 4.9 leicht

erkennen. Beide Halbkugeln erzeugen von oben beleuchtet und abgebildet das selbe Bild. Bei komplexeren Oberﬂächen gibts es entsprechend viele Formen, die das gleiche Bild erzeugen. Geht man von einer orthographischen Projektion aus, sind es sogar unendlich viele, da hier die Tiefenwerte für die Projektion nicht relevant sind. Das heißt, dass jede beliebige Skalierung in Richtung der Kamera keinen Unterschied in der Abbildung hervorruft. Man spricht von konvex/konkav Vieldeutigkeit (Bas-Relief Ambiguity ) [BKY97].

Das menschliche Gehirn löst dieses Problem, indem es Annahmen über die Lichtquelle oder das Objekt selbst triﬀt. Es geht zum Beispiel davon aus, dass Tageslicht von oben kommen oder ein Gesicht nach außen gewölbt sein muss.

Bei mathematischem Shape-from-Shading ist deswegen immer mindestens eine

52

weitere Bedingung zur Rekonstruktion notwendig. Diese muss sicherstellen, dass eine zusammenhängende, natürliche Form entsteht.

4.2.1 Bestehende Shape-from-Shading-Verfahren

Zum erstenmal erwähnt wurde Shape-from-Shading von J. van Diggelen im Jahre 1951 [Dig51]. Ziel war es, die Oberﬂäche des Mondes nicht mehr ausschließlich durch den Schattenwurf sondern durch die gesamten Helligkeitswerte der Mondlandschaft zu rekonstruieren.

Propagation Methoden

Unter Propagation Methoden versteht man Verfahren, bei denen die Form der Oberﬂäche von einem bestimmten Punkt aus über die ganze Fläch propagiert wird. Der erste der sich dem Problem genauer widmete und den Namen Shapefrom-Shading prägte, war Horn [Hor70; Hor81]. Er deﬁniert das Problem als das Lösen von nichtlinearen partiellen Diﬀerentialgleichungen erster Ordnung (PDE). Durch die Bildrückstrahlfunktion der Oberﬂäche werden die Oberﬂächennormalen mit den in der Fotograﬁe gemessenen Helligkeiten verknüpft. Löst man diese Gleichungssysteme, lässt sich die Form der Oberﬂäche Schritt für Schritt rekonstruieren. Später zeigt Horn [Hor90], wie man diese Methode durch Characteristic Strips verbessern kann. Bei den characteristic strips handelt es sich um optimierte Pfade, entlang denen die Oberﬂäche rekonstruiert werden kann. Sie werden anhand der Bildgradienten ermittelt. Dieser Ansatz enthält allerdings einige Schwächen. Zum Einen sind in jedem linienbasierten Integrationsverfahren Fehler unumgänglich. Dazu kommt, dass das Finden der Characteristic Strips selbst sehr schwierig ist. Prados und Faugeras [PF04] zeigen, dass Shape-from-Shading bei perspektivischer Projektion und frontaler Beleuchtung, ein korrekt gestelltes Problem ist. Sie benutzen eine Viscosity Solution [CIL92] um die PDEs zu lösen. Dieses Verfahren gilt heute als state of the art im Bereich des Shape-from-Shading.

Globale Methoden

Globale Verfahren beziehen die gesamten Bildintensitäten in die Berechnung mit ein. Die Lösung erfolgt über die Minimierung eines Funktionals. Einer der be-

53

4 Rekonstruktion mittels Shape-from-Shading

kanntesten Ansätze überhaupt ist der von Horn und Brooks [HB86]. Hier sind die Begriﬀe der harten und der weichen Bedingung von Bedeutung. Eine harte Bedingung muss bei der Berechnung durchgesetzt werden. Die weiche Bedingung ergänzt fehlende Informationen, muss aber aus Gründen der Minimierung der Funktion nicht zwingend durchgesetzt werden. Als harte Bedingung dient bei diesem Rekonstruktionsverfahren die Bedingung der Glattheit der Oberﬂäche. Das Erfüllen der Bildrückstrahlfunktion ist nur als weiche Bedingung einzuhalten. Ansätze, die über eine harte Bedingung die Glattheit der Oberﬂäche erzwingen, haben deswegen oft zur Folge, dass die ermittelte Oberﬂäche zu weich und detailarm ist. Außerdem sind sie iterativ, benötigen somit ein Konvergenzkriterium, und sind oft sehr langsam. Ein ähnlicher Ansatz von Frankot und Chellapa [FC88] stellt sicher, dass die Normalen integrierbar sein müssen (siehe Abschnitt 3.3.1). Das Problem zu weicher Oberﬂächen überwinden Worthington und Hancock [WH99], indem sie die Erfüllung der Bildrückstrahlfunktion als harte Bedingung realisieren. Lee und Kuo [LK93] ermitteln die Oberﬂächentiefe direkt. Sie nähern ein Netz aus Dreiecken unter Beachtung einer Festigkeitsbedingung an die Helligkeitswerte der Oberﬂäche an. Dies reduziert die Berechnung auf das Lösen eines lineraren Gleichungssystems, hat aber neue Fehler durch die Linearisierung der Bildrückstrahlfunktion zur Folge.

Lokale Methoden

Lokale Methoden gehen davon aus, dass die Oberﬂäche lokal an eine Kugel angenähert werden kann. Lee und Rosenfeld [LR85] benutzen die ersten Ableitungen der linearen Annäherung der Bildrückstrahlfunktion um die lokale Oberﬂächentopographie zu ermitteln. Pentland [Pen90] geht ebenfalls von einer lokal runden Oberﬂäche aus, benutzt aber die ersten und zweiten Ableitungen zur Rekonstruktion. Dies soll die Genauigkeit der rekonstruierten Oberﬂäche erhöhen, führt aber zu einer erhöhten Empﬁndlichkeit gegenüber Rauschen in den Eingangsbildern. Tsai und Shah [TS94] berechnen die Normalen der Oberﬂäche mit Hilfe einer Jacobi Matrix [Kü05]. Dadurch muss nur noch ein lineares Gleichungssystem pro Pixel gelöst werden. Dieses Verfahren ist einfach zu implementieren, aber ebenfalls sehr empﬁndlich gegenüber Rauschen.

54

4.3 Konzept

In Abbildung 4.10 ist der komplette Ablauf der Rekonstruktion eines Gesichtes aus einer Fotograﬁe dargestellt. Als Grundlage für diesen Prozess dient eine Fotograﬁe eines Gesicht. Auf diesem werden verschiedene Techniken der Bildverarbeitung angewendet. Ziel ist es, den Informationsgehalt des Bildes auf die Intensitäten (Graustufen) zu reduzieren, Bildstörungen zu entfernen und die Bildgradienten zu ermitteln. Diese 2D-Abbildung wird dann verwendet um ein initales Normalenfeld zu erstellen. Das hier vorgestellte Shape-from-Shading-Framework [WH99] arbeitet mit Normalenfeldern. Ein Normalenfeld beschreibt nur die Steigungen einer Oberﬂäche im Raum. Es kann dementsprechend als erste partielle Ableitung eines Höhenfeldes betrachtet werden. Deswegen muss es nach der Rekonstruktion integriert werden, um wieder Höhenwerte zu erhalten. Dieses Höhenfeld besitzt als explizite Darstellung einer Oberﬂäche im Raum allerdings nur 2,5D (siehe Abschnitt 3.3.1). Um das rekonstruierte Gesicht weiter verarbeiten zu können, ist es notwendig, es in eine 3D-Darstellung zu überführen. Es wird in ein Polygonnetz (siehe Abschnitt 3.3.3) umgewandelt. Hier sind nun alle notwendigen Daten enthalten um es als OBJ Datei zu exportieren.

55

4 Rekonstruktion mittels Shape-from-Shading

Abbildung 4.10: Aufbau des Verfahrens zur Oberﬂächenrekonstruktion mittels Shape-from-Shading.

4.4 Vorverarbeitung der Fotograﬁen

Die Ausgangssituation bildet eine Fotograﬁe von einem Gesicht. Dieses muss exakt von vorne belichtet und abgebildet sein.

Für das Shape-from-Shading sind die Helligkeitswerte sowie deren Änderungen von Bedeutung. Ein Alphakanal hilft alle Operationen zur Rekonstruktion auf Bereiche, die das Gesicht abbilden, zu beschränken. Farbwerte spielen keine Rolle.

56

4.4.1 Intensitäten und Alphakanal ermitteln

Bei den verwendeten Fotograﬁen handelt es sich um Bilder im RGB-Farbraum. Das heißt, dass die Rot-, Grün- und Blauanteile getrennt vorliegen. Es handelt sich hierbei um ein additives Farbmodell. Alle drei Grundfarben addieren sich zu Weiß.

Da nur die Lichtintensitäten des Fotos benötigt werden, wählt man ein Farbmodell, bei dem diese in einem getrennten Kanal gespeichert ist.

Das HSI Farbmodell setzt sich ebenfalls aus drei Kanälen zusammen. Diese stehen für Farbwert (hue), Sättigung (saturation) und Lichtintensität (intensity). Die Intensität I wird dabei folgendermaßen berechnet:

3

Diese entspricht nicht unbedingt der vom Menschen gesehenen Helligkeit, da das menschliche Auge verschiedene Farben unterschiedlich hell wahrnimmt [Sto02]. Diese gesehenen Unterschiede würden das Ergebnis aber verfälschen.

Es wird davon ausgegangen, dass das Gesicht vor einem schwarzen Hintergrund abgebildet ist. Dadurch lässt sich leicht erkennen, welche Teile des Fotos zum Gesicht gehören und welche nicht. Diese Werte werden in einem extra Kanal abgelegt.

4.4.2 Lambertsche Reﬂektion korrigieren

Das in Abschnitt 4.5 beschriebene Shape-from-Shading-Verfahren basiert auf dem Lambertschen Gesetz als Bildrückstrahlfunktion. In [RKH05] wird ein Verfahren beschrieben, mit dem es möglich ist aus einzelnen Fotograﬁen die Bildrückstrahlfunktion zu bestimmen. Diese kann dann dazu verwendet werden, ein perfektes Lambertsches Verhalten zurück auf die Fotograﬁe zu mappen. Dadurch ist es möglich ein auf dem Lambertschen Gesetz basierendes Shape-from-Shading auf eine Fotograﬁe einer Oberﬂäche anzuwenden, welche ein komplexeres Rückstrahlverhalten aufweist.

Das in [RKH05] beschriebene Verfahren stellt einige Bedingungen an die Oberﬂäche, auf welche das Lambertsche Verhalten abgebildet werden soll, und an

57

4 Rekonstruktion mittels Shape-from-Shading

die Fotograﬁe dieser Oberﬂäche. Das Verfahren funktioniert nur für Fotograﬁen, bei denen Betrachterwinkel und Lichtquelle übereinstimmen. Dies ist allerdings keine Einschränkung, da das in Abschnitt 4.5 vorgestellte Shape-from-Shading-Verfahren die selbe Anforderung an die Abbildung stellt. Dieser Fall wird in Abbildung 4.11 dargestellt.

Die Reﬂektionseigenschaften der Oberﬂäche müssen schon vor der Korrektur ein monotones und isotropes Verhalten aufweisen. Ein isotropes Verhalten ist gegeben, wenn die Rückstrahlfunktion unabhängig von der Rotation der Oberﬂäche um den Vektor in Richtung der Lichtquelle ist. Das heißt, in Abbildung 4.11 spielt der Winkel α für die Intensität der Oberﬂäche keine Rolle. Oberﬂächenrückstrahlfunktionen, die abhängig von diesem Winkel, sind werden als anisotrop bezeichnet. Zum Beispiel gebürstetes Metall, Satin oder Haare weisen anisotropes Verhalten auf. Außerdem muss sie monoton fallend in Abhängigkeit von Betrachterwinkel zu Normalenwinkel sein. Der Unterschied zwischen einem Reﬂektionsverhalten nach Lambert und einer monoton fallenden, isotropen Bildrückstrahlfunktion ist in Abbildung 4.12 dargestellt. Durch das feste Verhältnis zwischen Intensität und Winkel θ (siehe Abschnitt 4.1.6) lässt das Lambertsche Gesetz nur eine komplett diﬀuse Oberﬂäche zu. Im Fall einer monoton fallenden, isotropen Bildrückstrahlfunktion sind dagegen Unregelmäßigkeiten wie zum Beispiel Glanzpunkte möglich,

58

2 2

Abbildung 4.12: Monoton fallendes, isotropes Reﬂektionsverhalten (rechts) und Reﬂektions-

solange die in 4.12 gezeigte Kurve monoton fallend ist.

Um Lambertsches Verhalten auf eine Abbildung zurückprojizieren zu können, ist es notwendig, die reale Rückstrahlfunktion der abgebildeten Oberﬂäche zu kennen, um diese dann realistisch verändern zu können. Im Folgenden wird beschrieben, wie es unter bestimmten Einschränkungen möglich ist, die Rückstrahlfunktion aus einer einzelnen Fotograﬁe einer Oberﬂäche zu ermitteln.

In Abschnitt 4.1.5 wurde die BRDF als Beschreibung für das Reﬂektionsverhalten von Oberﬂächen vorgestellt. Sie gibt das Verhältnis zwischen eintreﬀendem und abgestrahlten Licht an einer bestimmten Stelle der Oberﬂäche an. Sie wird durch die Gleichung (4.4) beschrieben. Das Verhältnis zwischen der Lichtintensität an einem bestimmten Punkt der Oberﬂäche und der Intensität in einem bestimmten Bildpunkt nach deren Abbildung ist durch Formel (4.3) deﬁniert. Daraus lässt sich schließen, dass die Intensität I u eines Bildelements u proportional zu der abgestrahlten Lichtmenge L o (θ o , α o ) an einer bestimmten Stelle der Oberﬂäche sein muss. Dies lässt sich durch folgende Gleichung ausdrücken: 2

⁴ α. I u = L o (θ o , α o ) cos

4 f

Der Winkel α beschreibt den Winkel zwischen optischer Achse und dem Vektor, der von der optischen Mitte auf die Stelle des optischen Mediums zeigt (siehe 4.1.4), auf die ein bestimmter Punkt einer Oberﬂäche abgebildet wird. Geht man davon aus, dass die betrachtete Oberﬂäche nur einen kleinen, zentrierten

Teil der Fotograﬁe ausmacht, wird cos ⁴ α ≈ 1. Man kann die Gleichung (4.4.2)

59

4 Rekonstruktion mittels Shape-from-Shading

mit Hilfe der BRDF (4.4) folgendermaßen umschreiben:

I u = γL o (θ o , α o ) = γp(θ i , α i , θ o , α o ) cos θ i dω

mit d 2

Da der Betrachterwinkel und die Lichtquelle übereinstimmen müssen, ergibt sich:

α = α i = α o .

Geht man weiterhin davon aus, dass die Lichquelle unendlich weit von der Oberﬂäche entfernt ist, ist sie an jedem Punkt der Oberﬂäche konstant. Das heißt, dass L i (θ i , α i ) durch einen konstanten Wert k ersetzt werden kann. Die BRDF ist folglich nur noch von der Flächennormale an einer bestimmten Stelle der Oberﬂäche abhängig:

L o (θ, α)

p(θ, α) = k .

cos θdω

Die Lichtintensitäten in der Fotograﬁe sind dementsprechend proportional zu:

1

L o (θ, α) = p(θ, α) cos θdω.

k

Daraus kann man schließen, dass es in diesem Fall reicht, die von der Oberﬂäche abgestrahlten Lichtintensitäten L o (θ, α) zu berechnen, um die gesamte Rückstrahlfunktion der Oberﬂäche zu ermitteln. Sind die Normalen der Oberﬂäche bekannt, ist L o (θ, α) leicht zu berechnen. Es ist mit I die Helligkeit an einer bestimmten Stelle der abgebildeten Oberﬂäche mit der Normale (θ, α) gegeben. Die Funktion L o ist dann gegeben durch:

Das Ermitteln von L o kann durch eine Projektion der Oberﬂäche auf eine Einheitskugel dargestellt werden. Hierfür wird an jedem Punkt der Oberﬂäche die Helligkeit an diesem Punkt auf die Stelle der Einheitskugel mit den Winkeln α und θ der zugehörigen Normale projiziert. Das heißt, dass Helligkeiten an Punkten der Oberﬂäche mit identischer Normale auf den selben Punkt der Einheitskugel

60

abgebildet werden. Dies ist gewollt, da unter den gegebenen Bedingungen Punkte mit der selben Normale auch die gleiche Helligkeit haben. Es gehen somit keine Informationen verloren.

einer Einheitskugel darzustellen. Dies ist in Abbildung 4.13 dargestellt. Dafür sind Kenntnisse über die Normalen der Oberﬂäche notwendig. Diese sind allerdings nicht gegeben.

Es handelt sich hier aber, wie oben beschrieben, um eine Oberﬂäche mit monotonem und isotropen Verhalten. Außerdem sind die Positionen des Betrachters und der Lichtquelle bekannt und identisch. Dadurch lassen sich die benötigten Informationen über die Oberﬂäche einschränken.

Die Einheitskugel wird so rotiert, dass ihre Achse parallel zur Richtung des Betrachters verläuft. Das heißt, dass Normalen die in Richtung des Betrachers zeigen auf den Pol der Kugel mit θ = 0 abgebildet werden. Da Lichtquelle und Betrachterrichtung identisch sind, handelt es sich hierbei auch gleichzeitig um die

^π größte Helligkeit der Oberﬂäche. Normalen mit θ ≥ 2 sind von der Lichtquelle

abgewendet und haben deswegen eine Helligkeit von null. Da es sich um eine monotone Rückstrahlfunktion handelt, kann man also davon ausgehen das die

^π Helligkeitswerte auf der Einheitskugel von θ = 0 bis θ = 2 monoton fallen.

Es handelt sich weiterhin um eine isotrope Oberﬂäche. Das heißt, die Rückstrahlfunktion ist unabhängig von der Rotation um den Vektor der in Richtung

61

4 Rekonstruktion mittels Shape-from-Shading

der Lichtquelle zeigt. Diese ist mit der Richtung des Betrachters identisch, und die Rotation um diesen Vektor entspricht einer Veränderung von α bei der Projektion auf der Einheitskugel. Man kann also davon ausgehen, dass Positionen auf der Einheitskugel mit dem selben Wert für θ und unterschiedlichem Wert für α die selbe Helligkeit aufweisen.

Es ist also nur wichtig den Winkel θ der Oberﬂächennormalen zu ermitteln, um deren Rückstrahlfunktion zu erhalten. Im Folgenden wird gezeigt, wie die Bildgradienten der Fotograﬁe der Oberﬂäche verwendet werden können, um diesen Winkel zu berechenen.

Hierzu projiziert man die Einheitskugel auf eine Ebene (siehe Abbildung 4.14). Dabei gilt: (x, y) = (sin θ cos α, sin θ sin α).

Die Helligkeit ˆ I an der Position (x, y) in der Abbildung der Einheitskugel ist gegeben durch: ˆ I(sin θ cos α, sin θ sin α) = γL o (θ, α). (4.5)

Die Bildgradienten der Abbildung der Einheitskugel hängen folgendermaßen mit der Rückstrahlfunktion L o (θ, α) zusammen: ∂ ˆ ∂Lo(θ,α)

Dabei bezeichnet J die Jacobi Matrix für die Transformation von der Einheitsku-

62

gel auf die Bildebene [Kü05]: ∂x ∂(sin θ cos α)

Diese Verbindung zwischen den Bildgradienten der Oberﬂäche auf der Abbildung und den Ableitungen der Rückstrahlfunktion kann verwendet werden um ein Mapping zwischen den Helligkeiten der Abbildung und der Einheitskugel zu realisieren. Zu diesem Zweck geht man davon aus, dass die Oberﬂäche lokal an eine Kugel angenähert werden kann, welche mit der selben Rückstrahlfunktion gerendert wurde. Eine bestimmte Stelle auf der Oberﬂäche und auf der Kugel besitzen dann den selben Helligkeitsgradienten.

berechnen. Dies entspricht der symmetrischen Diﬀerenz aus Abschnitt 3.2.1.

Korrespondenzen zwischen der Abbildung der Oberﬂäche und der Einheitskugel können nun durch Finden der Position (x, y) auf der Projektion der Einheitskugel hergestellt werden. Dies ist gegeben durch den selben Gradienten in beiden Abbildungen: ∇I(x, y) = ∇ ˆ I(sin θ cos α, sin θ sin α).

Damit weiß man auf welche Position (θ, α) der Einheitskugel die Helligkeit I an der Stelle (x, y) der Abbildung der Oberﬂäche projiziert werden muss. Es ist dafür nicht nötig die Normalen der Oberﬂäche zu kennen.

Es ist allerdings nicht einfach die Gradienten der Abbildung genau zu bestimmen. Da es sich um eine diskrete Abbildung handelt, kann sich die Helligkeit von Pixel zu Pixel stark verändern. Dies ist in Abbildung 4.15 dargestellt. Auf der linken Seite ist ein stark vergrößerter Ausschnitt eines diskreten Bildes zu sehen. Die Bildgradienten verlaufen hier in alle möglichen Richtungen. Auf der rechten Seite ist das Bild in einer Größe dargestellt, in der einzelne Pixel nicht mehr zu erkennen sind. Hier ergibt sich ein Bildgradient der von rechts nach links verläuft. Dies wäre der Gradient der die Form der Oberﬂäche beschreibt und hier von Interesse ist. Er muss, wie in der Abbildung gezeigt nicht unbedingt den Gradienten

63

4 Rekonstruktion mittels Shape-from-Shading

auf Pixelebene entsprechen, da diese auch durch Rauschen im Bild hervorgerufen werden können. Um einen solchen Gradienten sicher zu bestimmen, sind allerdings aufwendige Verfahren, die mit starker Glättung oder großen Filtermasken arbeiten, notwendig. Das hätte ein stark verfälschtes Ergebnis für L o (θ, α) zu Folge Deswegen ist es besser sich auf Oberﬂächen mit isotropischem Verhalten zu beschränken. Hier gilt:

α

Das heißt, die Ableitung der Rückstrahlfunktion bleibt gleich, bei sich veränderndem Winkel α. Es muss also nur der entsprechende Winkel θ ermittelt werden, um die L o (θ, α) zu berechnen.

Es lässt sich eine erzeugende Funktion g(θ) aufstellen, welche die Helligkeit für einen gegebenen Winkel θ berechnet. 2π θ

Das äussere Integral beschreibt das Integrieren über den kompletten Bereich des Winkel α der Einheitskugel. Für jeden möglichen Winkel α wird im inneren Integral der Funktion über die Gradienten der Rückstrahlfunktion in Richtung θ bis zu einem gesuchten Wert von θ integriert. Es werden also für einen bestimmten Winkel θ alle Gradienten der Einheitskugel bis zum Erreichen des entsprechenden Winkels aufsummiert und man erhält die Helligkeit, die zu diesem Winkel gehört.

Mit Hilfe der Funktion g(θ) und Gleichung (4.5) kann die Länge des Gradienten der Projektion der Einheitskugel berechnet werden.

cos θ ∂θ ∂ sin θ

64

Löst man diese Diﬀerentialgleichung erhält man:

Da ˆ I = γg(θ) ist, kann man diese Gleichung folgendermaßen umschreiben: 1

Das heißt, es ist mit dem Integrieren über die Kehrwerte der ansteigenden Bildgradienten der Projektion der Einheitskugel möglich, den Winkel θ auf der Einheitskugel zu bestimmen. Die Gradienten in der Projektion der Einheitskugel entsprechen denen der Fotograﬁe selbst. Deswegen kann das Integral (4.6) als Summe über die diskreten Bildgradienten der Fotograﬁe umgeschrieben werden. Sie müssen dafür sortiert und ihren entsprechenden Helligkeitswerten in der Abbildung zugeordnet werden. Möchte man den Winkel θ zu einer bestimmten Helligkeit l in der Abbildung ausrechnen, ist das über folgende Gleichung möglich:

l

m=0

Hat man den Winkel θ(l), der zu einer bestimmten Helligkeit l gehört ermittelt, ist es einfach den Helligkeitswert bei Lambertscher Reﬂektion zu berechnen. Dieser ist, wie in Abschnitt 4.1.6 gezeigt wurde, über cos θ(l) gegeben.

4 Rekonstruktion mittels Shape-from-Shading

Seite nach dem Remappen des Verhaltens der Oberﬂäche nach dem Lambertschen Gesetz abgebildet. Mit diesem Verfahren ist es nicht nur möglich glänzende Flächen aus Fotograﬁen von Gesichtern zu entfernen. Es wird vielmehr ein korrektes Verhalten nach dem Lambertschen Gesetz simuliert. Dadurch wird die gesamte

^π Skala möglicher Helligkeiten mit einem Winkel θ von 0 bis 2 auf die Abbildung der

Oberﬂäche gemappt. Die Oberﬂäche wird an den Rändern dunkel und an den Flächen die frontal zur Kamera stehen heller. Da das Shape-from-Shading-Verfahren, welches in dieser Arbeit vorgestellt wird, von einem Reﬂektionsverhalten nach Lambert ausgeht, ist eine bessere Rekonstruktion des Gesichtes möglich.

4.4.3 Bildgradienten berechnen

Bildgradienten sind Vektoren die an jedem Pixel in die Richtung des größten Anstiegs der Intensität der direkten Nachbarn zeigen. Die Länge der Gradienten gibt Aufschluss über die stärke des Anstiegs.

Mathematisch gesehen handelt es sich hierbei um die ersten partiellen Ableitungen der Bildfunktion in x-Richtung und y-Richtung. Wie in Kapitel 3.2.1 gezeigt kann man die Berechnung der Gradienten in x und y-Richtung mit zwei Faltungen beschreiben:

⎡ ⎤ ⎡ ⎤

⎢ ⎣

Diese Faltungskerne sind allerdings sehr anfällig für Rauschen im Bild. Deswegen ist es sinnvoll, sie mit einem Glättungsﬁlter zu kombinieren. Verkettet man die Gradientenﬁlter mit dem jeweils anders orientierten Gauß-Filter, erhält man die

66

zwei Kerne des Sobelﬁlters [Tö05].

⎤ ⎡ ⎡ ⎤ ⎡ ⎤

Richtung p(x, y) und y-Richtung q(x, y) an der Stelle (x, y) im Bild berechnet werden:

Die Gradienten werden im Folgenden für die Initialisierung des Normalenfeldes benötigt.

67

4 Rekonstruktion mittels Shape-from-Shading

4.5 Das Shape-from-Shading-Framework

Das eigentliche Shape-from-Shading basiert auf Normalenfeldern. Dies ist sinnvoll, da ein Shape-from-Shading-Verfahren immer nur Informationen über die Oberﬂächenorientierung liefern kann.

In [WH99] wird ein Framework vorgestellt, welches die Rückstrahlfunktion der Abbildung als harte Bedingung in einem iterativen Shape-from-Shading-Verfahren durchsetzt. Harte Bedingung bedeutet, dass diese auf jedenfall durchgesetzt werden muss. Durch sie wird nach jeder Iteration sichergestellt, dass sich jede Normale der Oberﬂäche an einer Position beﬁndet, die bei gleicher Beleuchtung wieder die selbe Helligkeit erzeugt. Eine weitere Bedingung stellt sicher, dass eine geschlossene, glatte Oberﬂäche entsteht. Diese Bedingung wird als weiche Bedingung bezeichnet.

4.5.1 Die Rückstrahlfunktion der Abbildung als harte Bedingung

Es wird davon ausgegangen, dass die zu rekonstruierende Oberﬂäche orthogonal abgebildet wurde. Das Bild ist durch die Funktion I(x, y) deﬁniert. Das heißt, dass bei Pixel (x, y) die Helligkeit I(x, y) gegeben ist. Es wird aus dieser Abbildung ein Normalenfeld n(x, y) rekonstruiert (siehe Abschnitt 3.3.1). Die entsprechende Oberﬂächennormale zu der Stelle (x, y) in der Abbildung I(x, y) ist n(x, y). Jede Normale ist durch die zwei Winkel α und θ im jeweiligen lokalen Kugelkoordinatensystem deﬁniert (siehe Abschnitt 3.1.2). Dieser Aufbau ist in Abbildung 4.18

Abbildung 4.18: Vorausgesetzter Aufbau bei der Abbildung der Oberﬂäche zur Rekonstruk-

68

dargestellt. Hier bezeichnet L den Vektor, der in Richtung der Lichtquelle zeigt. Die Richtung des Betrachters wird durch V beschrieben. Beide sind identisch und zeigen in Richtung z des karthesischen Koordinatensystems. Die lokalen Kugelkoordinaten sind so deﬁniert, dass dies den Winkeln θ = 0 und α = 0 entspricht. Es wird von einer Oberﬂäche mit Lambertschen Verhalten ausgegangen (siehe Abschnitt 4.1.6). Deswegen hängt die Helligkeiten der Oberﬂäche nur von zwei Werten ab. Es handelt sich hierbei um den Winkel θ der Normale, welcher gleichzeitig dem Winkel zwischen Normale und Lichtquelle entspricht, und die Albedo p.

Nach dem Lambertschen Gesetz ergibt sich deswegen an der Position (x, y) mit dem Winkel θ(x, y) der Normalen n(x, y) :

gen. Deswegen hat diese keinen Einﬂuss auf die Helligkeit der Oberﬂäche:

I(x, y) = cos (θ(x, y)) .

Diese Gleichung kann nach θ umgestellt werden:

θ(x, y) = arccos (I(x, y)) .

Es ist also möglich den Winkel θ einer Normale der Oberﬂäche zu rekonstruieren. Zum Ermitteln des Winkels α stehen nicht genügend Informationen zur Verfügung.

Geometrisch gesehen kann man damit den Kegel bestimmen, auf welchem sich die Normale beﬁnden muss. Dieser hat als Achse die Lichtquelle L und als halben Öﬀnungswinkel den Winkel θ(x, y). Der Winkel α gibt die Lage auf diesem Kegel an. Dies ist in Abbildung 4.19 dargestellt. Solange die Normale auf diesem Kegel liegt, ist das Lambertsche Gesetz erfüllt.

Ziel ist es nun, diese Erkenntnis in einem iterativen Shape-from-Shading-Verfahren zu verwenden. Dazu braucht man eine Möglichkeit die Normale nach jeder Iteration auf die nächstliegende Position auf dem Kegel zurück zu rotieren. Damit ist das Lambertsche Gesetz als harte Bedingung realisiert.

4 Rekonstruktion mittels Shape-from-Shading

Abbildung 4.19: Shape-from-Shading unter Annahme einer rein diﬀusen Oberﬂäche.

70

Abbildung 4.20 sieht man, dass sie um den Winkel ϕ und die Achse a rotiert werden muss. Der Winkel ϕ kann folgendermaßen berechnet werden:

ϕ = |θ(x, y) − arccos (I(x, y)) |.

Dies ist die Diﬀerenz zwischen dem aktuellen Polarwinkel der Normale ˜ n und dem

nach dem Lambertschen Gesetz berechneten, korrekten Winkel. Die Achse a um die die Normal gedreht werden soll liegt im rechten Winkel zu der Normale ˜ n und

zur Lichtquelle L. Sie kann demnach über das Kreuzprodukt der beiden Vektoren berechnet werden:

werden, welche die Normale ˜ n auf den Kegel zurückrotiert. ⎛ ⎞

c + u ² c −ws + uvc vs + uwc

⎟

⎠

mit

= 1 − c, s = sin(φ).

Lambertschen Gesetz möglichen Positionen zu rotieren, lautet:

iterativen Prozess anzuwenden.

4.5.2 Die Glättung der Oberﬂäche als weiche Bedingung

Die weiche Bedingung hat die Aufgabe sicherzustellen, dass eine zusammenhängende glatte Oberﬂäche entsteht. Ein sehr einfacher Ansatz dies zu erreichen besteht in einer einfachen Glättung der Oberﬂäche. Hierbei wird die geglättete Normale ˜ n an der Stelle (x, y) aus den vier benachbarten Normalen n(x + 1, y),

71

4 Rekonstruktion mittels Shape-from-Shading

n(x, y + 1), n(x − 1, y) und n(x, y − 1) gemittelt:

4

Werden in einem Algorithmus nicht nach jeder Iteration alle Normalen auf den vom Lambertschen Gesetz vorgegeben Kegel zurückrotiert, führt diese Bedingung zu einer ebenen Fläche.

4.5.3 Initialisierung

Es wurde gezeigt, wie das Lambertsche Gesetz verwendet werden kann, um den Polarwinkel θ zu bestimmen. Ein einfacher Ansatz zur Bestimmung des Azimutwinkels α zur Ermittlung eines initialen Normalenfeldes ist die Annahme einer komplett konvexen Oberﬂäche. Dies triﬀt zwar auf ein menschliches Gesicht nicht zu, ist aber als Initialisierung ausreichend.

Bei einer konvexen Oberﬂäche, die das Licht nach dem Lambertschen Gesetz reﬂektiert, liegt der Azimutwinkel α in Richtung des Helligkeitsgradienten. Dies wird in Abbildung 4.21 deutlich. Links ist die Abbildung einer Oberﬂäche mit eingezeichneten Bildgradienten dargestellt. In der Mitte ist ein Querschnitt dieser Oberﬂäche dargestellt. Die Helligkeit gibt den Öﬀnungswinkel des Kegels möglicher Normalen an. Bei einer konvexen Oberﬂäche liegen die Normalen in Richtung der Gradienten auf dem Kegel. Das heißt, dass der Winkel α der Ausrichtung des Gradienten entspricht.

72

4.6 Integrieren des Normalenfeldes

Die rekonstruierten Normalenfelder müssen in Höhenfelder umgewandelt werden. In Abschnitt 3.3.1 wurde gezeigt, dass je nachdem welcher Integrationspfad gewählt wird, die Ergebnisse sehr unterschiedlich sein können. Deswegen ist es sinnvoll ein globales Integrationsverfahren zu wählen, das den entstehenden Fehler minimiert. In [FC88] ist ein solches Verfahren beschrieben. Mit Hilfe eine Fouriertransformation wird ein Funktional minimiert, welches die Integrierbarkeit der Gradientfelder sicherstellt. Dieses Verfahren wird in [WK02] vereinfacht und durch zusätzliche Parameter ergänzt.

4.6.1 Orthogonale Projektionen

Unter Orthogonalen Projektionen [Jä02] versteht man die Transformation einer Funktion in eine neue orthogonale Funktionsbasis. Diese sollte leicht durchzuführen und muss umkehrbar sein. Durch diese Abbildung auf einen neuen Deﬁnitionsbereich können bestimmte Aufgaben besser erledigt werden. In der digitalen Bildverarbeitung wird sie zum Beispiel für verschiedene Verfahren der Bildrestauration, Bildkompressionen sowie Filteroperationen verwendet.

Entscheidend bei einer orthogonalen Projektion ist die gewählte Funktionsbasis. Um einen n-dimensionalen Funktionraum aufzuspannen, müssen dafür n verschiedene zueinander orthogonale Basisvektoren gefunden werden. Die Basisvektoren sind dabei orthogonal, wenn ihr Skalarprodukt Null ist.

Eine Funktion kann entweder durch Angabe ihres Bildungsgesetzes oder durch Aufzählen aller Werte deﬁniert werden. Für ein Bild ist ein Bildungsgesetz meistens nicht bekannt. Handelt es sich um ein Graustufenbild, wird es deshalb durch eine Matrix mit allen Grauwerten deﬁniert. Dieser Matrix besitzt M × N Elemente, das heißt soviele Elemente wie Pixel. Es muss also ein M × N -dimensionaler Funktionsraum aufgespannt werden.

4 Rekonstruktion mittels Shape-from-Shading

Man sieht, wie es aus den vier Basisbildern und den vier entsprechenden Werten aufgebaut wird. Hierbei handelt es sich um die einfachste denkbare orthogonale Basis für eine Abbildung. Diese können als eine Matrix B verstanden werden, an der zu jedem Pixel i, j das entsprechnede Basisbild B ij steht. Mathematisch ist dies gegeben durch:

I = g 00 · B 00 + g 01 · B 01 + g 10 · B 10 + g 11 · B 11 .

Hierbei wird der Grauwert in Pixel i, j durch g ij bezeichnet. Als Summe umgeschrieben erhält man:

M −1 N −1

Durch Multiplizieren aller Werte mit einer neuen Basis kann eine Funktion auf diese abgebildet werden. Die Rücktransformation erfolgt dann über die inverse Basis

B ⁻¹ . Bekannte Basen sind zum Beispiel die Fourier-Basis oder die Kosinusbasis.

4.6.2 Die Fourier-Transformation

Bei der diskreten Fouriertransformation wird eine Basis aus periodischen Funktionen verwendet. Diese besitzen unterschiedliche Frequenzen und einen diskreten Deﬁnitionsbereich [Tö05].

Da die transformierte Funktion durch unterschiedliche Frequenzen und Amplituden deﬁniert wird, spricht man von der Darstellung im Frequenzraum. Die ursprüngliche Form wird Repräsentation im Ortsraum genannt. In dieser Arbeit werden Funktionen im Frequenzraum durch einen tiefgestelltes F gekennzeichnet, zum Beispiel I F .

Für eine zweidimensionale Funktion I(x, y) wie eine Abbildung mit M × N Pixel ist die orthogonale Basis der Fouriertransformation deﬁniert durch: ux

vy −i2π B xy (u, v) = exp . +

M N

74

mit der inversen Transformation:

der Berechnung der Fouriertransformation auf quadratischen Bildern mit N =

M = 2 ^x lässt sich eine Divide-and-Conquer -Strategie formulieren. Dies reduziert

den Aufwand pro Pixel auf O(log N ) und den Gesamtaufwand für ein Bild der

Größe N × N auf O(N ² log N ). Dieses Variante der Diskreten Fouriertransforma-

4.6.3 Integration

Gegeben sind die Oberﬂächengradienten in x und y-Richtung, p(x, y) und q(x, y). Diese entsprechen der ersten partiellen Ableitungen der gesuchten Funktion über die Höhenwerte Z(x, y). Sie hängen dementsprechend folgendermaßen zusammen:

∂x

und

4 Rekonstruktion mittels Shape-from-Shading

nach kann Z(x, y) durch die Minimierung folgender Funktion berechnet werden:

Z x − p

Ω

Diese Kostenfunktion wird im Verfahren, welches in [FC88] beschrieben wird, verwendet. Es werden die fehlerhaften Gradienten p(x, y) und q(x, y) mit den gesuchten, integrierbaren partiellen Ableitungen der Zielfunktion Z(x, y) in Bezug gebracht. Sie beschreibt das Integral über die Summe der Quadrate der Diﬀerenz zwischen gegebenen und gesuchten Gradienten an jeder Position der Gradientenfelder. Es wird also der durch das Quadrat gewichtete Unterschied zwischen den rekonstruierten und den optimalen Gradientenfeldern berechnet.

Das Integrieren über diese Kostenfunktion liefert bereits wesentlich bessere Ergebnisse als lokale Verfahren zur Integration, ist aber stark abhängig von verrauschten Daten. Außerdem entstehen große Fehler bei plötzlichen Änderungen der Orientierung.

Deswegen wird es in [WK02] um zwei parametrisierte Terme erweitert:

Z x − p

Ω

Der zweite Term ist dabei eine Annäherung an die ersten partiellen Ableitungen der gesuchten Oberﬂäche. Durch die Minimierung dieses Terms werden große Steigungen unterdrückt und damit die Fläche der Oberﬂäche minimiert. Wie stark sich dieser Term auf das Ergebnis auswirkt, wird durch γ bestimmt. Der dritte Summand der Funktion beschreibt die zweiten partiellen Ableitungen der Oberﬂäche. Durch seine Minimierung werden zu starke Oberﬂächenkrümmungen verhindert. Er wird durch μ gewichtet. Durch diese zwei zusätzlichen Terme liefert die Funktion auch bei verrauschten Daten glatte Oberﬂächen.

Nun soll W minimiert werden um Z(x, y) zu berechnen. Zur Minimierung wird nicht, wie es häuﬁg der Fall ist, die Variationsrechnung [Jä02] verwendet, sondern die Fouriertransformation. Diese lautet für die reelle, zweidimensionale Funktion

76

Z(x, y):

Ω

mit der Rücktransformation:

Ω Ω

Er besagt, dass das Integral über das Quadrat einer Funktion im Ortsraum identisch mit dem Integral über das Quadrat dieser Funktion im Frequenzraum ist.

Es sind p F (u, v) und q F (u, v) die Gradienten p(x, y) und q(x, y) im Frequenzraum. Mithilfe des Satzes nach Plancherel und den Ableitungsregeln der Fouriertransformation lässt sich die Zielfunktion W (4.12) folgendermaßen umschreiben:

W =

2π Ω

Mithilfe der Konjugierten von Z F (u, v), p F (u, v) und q F (u, v), Z ^∗ F (u, v), p ^∗ F (u, v)

77

4 Rekonstruktion mittels Shape-from-Shading

und q ^∗ F (u, v), kann W folgendermaßen erweitert werden.

² Z F Z ^{∗ ∗ ∗ ∗} F − iuZ F p W = u F + iuZ F p F + p F p ^F 2π Ω

² Z F Z ^{∗ ∗ ∗ ∗} F − ivZ F q + v F + ivZ F q F + q F q F dudv

1 ² + v 2 ^∗ + γ u Z F Z F dudv

2π ^Ω

1 ⁴ + 2u ² v ² + v 4 ^∗ u Z F Z + μ F dudv.

2π Ω

Durch Ableiten von W nach Z F und Z ^∗ F erhält man die Bedingungen für das Minimum von W : 2 Z

² Z ∗ ∗ ² Z ∗ ∗ ² + v 2 ∗ ² + v 2 ^∗ F − iup F − ivq 0 =u F + v F + γ u Z F + μ u ^F 2

² + v ^{2 2} + v 2 ^{∗ ∗ ∗} F − iup F − ivq = (1 + γ) u + μ u F , Z

und: 2 Z F

² Z F + iup F + v ² Z F + ivq F + γ ² + v ^{2 2} + v ² Z F + μ u u 0 =u

2

² + v ^{2 2} + v ² = (1 + γ) u + μ u Z F + iup F + ivq F .

Durch Addieren und Subtrahieren dieser beiden Bedingungen erhält man folgendes Gleichungssystem: 2

² + v ^{2 2} + v 2 ^{∗ ∗} F ) − iu (p F − p F ) − iv (q F − q F ∗) + μ u (Z F + Z 0 = (1 + γ) u

2

² + v ^{2 2} + v 2 ^{∗ ∗} (Z F − Z F ) + iv (q F + q F ∗) . 0 = (1 + γ) u + μ u F ) + iu (p F + p

Dieses kann man nach Z F (u, v) auﬂösen und erhält:

² (1 + γ) (u ² + v ² ) + μ (u ² + v ² )

mit (u, v) = (0, 0).

Die gesuchten Höhenwerte der Oberﬂäche Z(x, y) lassen sich nun über die inverse Fouriertransformation (4.11) berechnen. Da ein Gradientenfeld keine Information über die absolute Höhe einer Oberﬂäche liefert, ist es logisch, dass der erste Wert (u, v) = (0, 0) nicht deﬁniert ist.

78

4.7 Aufbereiten der Höhenfelder

handelt, muss dieses Verfahren für die Anwendung ebenfalls diskretisiert werden. Deswegen muss die Fourietransformation (4.10) durch ihr diskretes Pendant (4.8) ersetzt werden.

Die Funktionen p(x, y) und q(x, y) besitzen einen Deﬁnitionsbereich von x ∈ 0, . . . , M und y ∈ 0, . . . , N. Im Frequenzraum werden diese Bereiche auf ein Intervall der Sinusfunktion, u ∈ 0, . . . , 2π und v ∈ 0 . . . , 2π transformiert. Dementsprechend berechnen sich u und v in Gleichung (4.12) durch:

2πu 2πv 2 Z F (u, v) =

^{2 2 2 2} (1 + γ) sin + sin + μ sin + sin M N M N

−iu p F (u, v) − iv q F (u, v)

=

² (1 + γ) (u ² + v ² ) + μ (u ² + v ² )

mit (u, v) = (0, 0).

Die Rücktransformation erfolgt nun über die Inverse Diskrete Fouriertransformation (4.9).

4.7 Aufbereiten der Höhenfelder

Die Darstellung als Höhenfeld ist ausreichend, um alle Informationen, die aus dem Shape-from-Shading-Verfahren gewonnen werden können, abzubilden. Da nur Höhenwerte zu einer 2D-Abbildung berechnet werden, entspricht dies genau einem 2,5D-Datensatz.

Weiteren möglichen Bearbeitungsschritten genügt diese Darstellung aber nicht mehr zwingend. Möglichkeiten zur weiteren Bearbeitung sind zum Beispiel Veränderungen an dem Objekt zur Korrektur, Anfügen weiterer Objekte wie Hals oder Hinterkopf oder Veränderungen an Texturkoordinaten und Textur. Hierfür

79

4 Rekonstruktion mittels Shape-from-Shading

muss die explizite 2,5D-Darstellung des Objektes in eine Darstellung als 3D-Polygonnetz (siehe Abschnitt 3.3.3) umgewandelt werden. Dieses Polygonnetz kann dann über ein geeignetes Dateiformat in 3D-Visualisierungs- und Animationssoftware weiterverarbeitet werden. Hierfür bietet sich das obj-Format an (siehe Abschnitt 3.3.3).

80

Kapitel 5

Statistisches Modell für

Oberﬂächennormalen

In Kapitel 4 wurde eine Methode vorgestellt, welche Schattierungen einer Fotograﬁe benutzt um ein dreidimensionales Gesicht zu rekonstruieren. Es resultiert ein Normalenfeld, welches die Oberﬂäche beschreibt. Um dieses Normalenfeld zu verbessern, kann man Vorwissen über die Form und Eigenschaften von Gesichtern verwenden. Hierfür wird ein statistisches Modell aufgebaut, welches diese Informationen beinhaltet.

Im Folgenden werden zunächst Grundlagen für den Aufbau eines solchen Modells behandelt. Dazu gehören zum Einen die verwendeten Daten, welche als dreidimensionale Laserscans vorliegen. Zum Anderen werden geeignete Methoden zur Verarbeitung und Analyse dieser Daten beschrieben. Im Anschluss folgt ein Überblick über bisherige Ansätze und Verfahren zur Erstellung eines statistischen Modells für Gesichter. Darauf aufbauend wird das in dieser Arbeit untersuchte Verfahren eingeleitet. Es gliedert sich in verschiedene Schritte, welche in Zusammenhang gebracht werden. Dazu gehört die Korrespondenzbestimmung, die dazu dient Laserscans in Abhängigkeit zueinander zu bringen. Mit diesen Abhängigkeiten lassen sie sich deckungsgleich ausrichten. Eine anschließende Projektion dient dazu, die Normalenfelder der Laserscans zu erhalten. Abschließend werden sie so analysiert, dass sie in das Shape-from-Shading-Framework integriert werden können.

81

5 Statistisches Modell für Oberﬂächennormalen

5.1 Grundlagen zur Analyse von dreidimensionalen

Laserscans

Zunächst werden Eigenschaften der verwendeten Laserscans erläutert. Für die Verarbeitung dieser sind zunächst zwei Projektionsarten relevant. Die Laserscans müssen zum Einen auf eine Ebene projiziert werden um ein Normalenfeld zu erhalten. Zum Anderen dient eine weitere Art der Projektion dazu die Normalenfelder für eine Analyse aufzubereiten. Weiterhin ist es notwendig die wichtigsten Eigenschaften der Laserscans zu ermitteln, welche das statistische Modell repräsentieren. Eigenwerte und Eigenvektoren bilden die Grundlage für die Hauptkomponentenanalyse, welche verwendet wird um Eigenschaften der Scans zu ermitteln. Für die Hauptkomponentenanalyse sind Mittelwerte von Mengen relevant. Hierbei wird zwischen zwei Möglichkeiten unterschieden, die in dem letzten Abschnitt beschrieben werden.

5.1.1 Dreidimensionale Laserscans

Die in dieser Arbeit verwendeten dreidimensionalen Laserscans stammen vom Max-Planck-Institut (MPI). Es handelt sich um Beispieldatensätze aus einer 3D-Face-Database [MMPI]. Die Datenbank besteht aus insgesamt 200 Laserscans,

welche mit einem Cyberware ^™ Scanner angefertig wurden. Für Hochschul- und

Universitätsarbeiten stehen die Beispieldatensätze [MPI] frei zur Verfügung. Die wichtigsten Eigenschaften des Scanverfahrens werden im Folgenden herausgestellt.

Der Aufbau des Scanners ist in Abbildung 5.1 dargestellt. Die zu scannende Person sitzt auf einem unbeweglichen Stuhl. Der Arm des Scanners ist an einer Achse der Vorrichtung befestigt. Diese beﬁndet sich oberhalb des Kopfes der Testperson. Er rotiert um den Stuhl und zeichnet zylindrische Koordinaten und Farbwerte des Gesichts auf. Die Lichtquelle für den Scanvorgang beﬁndet sich in dem Scanarm, sodass die Beleuchtung für jede Aufnahme gleich ist. Wie später gezeigt wird, ist diese sogenannte Helligkeitskonstanz für das verwendete Verfahren äußerst wichtig.

Der Scanarm zeichnet für eine Einstellung das Proﬁl des Gesichts in 512 Höhenschritten h auf. Der Abstand zwischen jedem Höhenschritt beträgt 0, 615 mm.

Während eines Scanvorgangs rotiert er um 360 ^◦ um den Kopf, damit dieser kom-

82

plett erfasst werden kann. Die Rotation ist gleichmäßig auf 512 Winkelschritte φ aufgeteilt. Pro Aufnahme entsteht ein Datensatz, der einen Radiuswert r und die dazugehörigen Farbanteile R, G und B beinhaltet:

r(h, φ), R(h, φ), G(h, φ), B(h, φ), h,φ ∈ {0, . . . , 511}.

Um alle Daten in einem zylindrischen Koordinatensystem darzustellen, wird jedem r ein Farbwert (R, G, B) zugeordnet. In Abbildung 5.2 ist auf der linken Seite eine solche Darstellung gezeigt. Abschnitt 3.1.4 beschreibt, wie sich zylindrische Koordinaten in ein dreidimensionales kartesisches Koordinatensystem transformieren lassen. Diese Transformation entspricht dem Aufklappen des Zylinders. Man erhält ein zweidimensionales Feld, welches jeweils aus 512 Schritten in x- und y-Richtung besteht.Jeder Position (x, y) ist ein Radiuswert r und ein Farbwert (R, G, B) zugeordnet. Um diese beiden zweidimensionalen Felder anzuzeigen, können die Radiuswerte beispielweise normiert werden, sodass ein Grauwertbild entsteht, wie in Abbildung 5.2 dargestellt. Im Weiteren werden die Laserscans somit als Texturen interpretiert.

5 Statistisches Modell für Oberﬂächennormalen

x

Abbildung 5.2: Bei einem Scanvorgang werden Radius- und Farbwerte aufgenommen. Sie las-

84

plette Hinterkopf. Das resultiert aus der zugrundeliegenden Vorverarbeitung der Datensätze. Hierbei werden im ersten Schritt die durch den Scanvorgang enstandenen Löcher gefüllt, welche im Haar- und Augenbereich eines Kopfes auftreten. Zusätzlich wurden die Köpfe beschnitten, sodass nur noch die reinen Gesichtsdaten vorhanden sind, wie in Abbildung 5.2 zu sehen. Durch das Beschneiden werden störende Kopfbereiche entfernt, wie die Haare und der Hinterkopf. Die Köpfe unterscheiden sich nach dem Scanvorgang in ihrer Position und Orientierung. Da dies für die weitere Verarbeitung wichtig ist, werden sie so gut wie möglich aufeinander ausgerichtet. Diese Vorverarbeitungsschritte sind in [Bla00] ausführlich diskutiert.

5.1.2 Projektionen

In der Computergraﬁk wird häuﬁg mit dreidimensionalen Objekten gearbeitet. Ein Problem liegt hierbei in der Darstellung der Objekte, welche in der Regel auf einer zweidimensionalen Bildschirmoberﬂäche stattﬁndet. Dafür ist eine Umrechnung der 3D-Objektkoordinaten in 2D-Bildschirmkoordinaten erforderlich. Die Umrechnung kann durch eine Projektion der 3D-Koordinaten auf eine Ebene geschehen. Gängige Methoden stellen die Zentral- und Parallelprojektion dar.

Ein spezielles Anwendungsgebiet von Projektionen besteht in der Kartograﬁe. Die Problematik liegt hier generell darin die Erde auf einer Karte abzubilden. Ein Kriterium ist dadurch gegeben, dass die Erde ein Ellipsoid ist. Die Form des zu projizierenden 3D-Objekts ist somit bekannt. Eine mögliche Anforderung besteht darin, die gesamte Erde auf einer einzelnen Karte darzustellen. Alternativ sollen Längenverhältnisse erhalten bleiben, um beispielsweise Seewege zu vermessen. Daraus resultieren Kartenprojektionen, die auf unterschiedliche Anforderungen ausgelegt sind.

Zentral- und Parallelprojektion

Die Zentralprojektion bildet ein dreidimensionales Objekt perspektivisch auf eine Bildebene ab. Im Projektionszentrum werden alle Projektionsstrahlen zusammengeführt. Anhand der Strahlen ﬁndet die Zuordung zwischen dem Objekt und der Bildebene statt. Verdeckte Objektbereiche werden nicht projiziert. In Abbildung 5.3 ist dies verdeutlicht.

85

5 Statistisches Modell für Oberﬂächennormalen

Abbildung 5.3: Bei einer Zentralprojektion treﬀen sich die Strahlen im Projektionszentrum.

Das abgebildete Objekt wird perspektivisch verzerrt.

Eine für diese Arbeit relevante Projektionsart ist die Parallelprojektion. Hierbei beﬁndet sich das Projektionszentrum im Unendlichen. Die Projektionsstrahlen verlaufen somit parallel. Dies führt zu einer Abbildung, in der keinerlei perspektivische Verzerrung vorhanden ist. Zudem bleiben die relativen Größenverhältnisse des projizierten Objekts erhalten. Die orthograﬁsche Parallelprojektion wird anhand der Skizze in Abbildung 5.4 erläutert. Sie ist durch eine Projektionsrichtung

Abbildung 5.4: Ein Punkt p wird bei einer orthograﬁschen Parallelprojektion abhängig von

dem Winkel γ zwischen Projektionsrichtung r und der Strecke zwischen pE

r und einer Projektionsebene E deﬁniert. Es soll der Punkt p auf E projiziert werden. Der zugehörige Bildpunkt ist p E . Um diesen Punkt zu bestimmen benötigt man den Winkel γ zwischen r und der Strecke zwischen p E und p o . Der Punkt p o

86

entspricht der orthogonalen Projektion und ist ein Spezialfall der orthograﬁschen Projektion von p auf E. Hierbei ist die Projektionsrichtung r senkrecht zu E. Eine schematische Darstellung der orthogonalen Parallelprojektion ist in Abbildung 5.5 zu sehen. In [HB94] ist eine nähere Betrachtung der vorgestellten Projektionen zu

Abbildung 5.5: Bei der Orthogonalprojektion beﬁndet sich das Projektionszentrum im unend-

ﬁnden.

Kartenprojektionen

Kartenprojektionen werden dazu verwendet gekrümmte Oberﬂächen der dreidimensionalen Erde auf eine zweidimensionale Karte zu übertragen. Die Erde ist ein Ellipsoid, jedoch wird in vielen Bereichen eine Kugel als Rechengrundlage verwendet. Es gibt eine Vielzahl von solchen Kartenprojektionen, wobei sich die meisten in drei grobe Gruppen aufteilen lassen. Bei diesen Gruppen handelt es sich um die Zylinderprojektionen, die Kegelprojektionen und die Azimutalprojektionen. Beispiele hierfür sind in Abbildung 5.6 gegeben. Nähere Informationen über die Entstehung, Herleitungen und Eigenschaften der im Folgenden beschriebenden kartograﬁschen Projektionen sind in [Sny83] zu ﬁnden.

Im weiteren Verlauf der Arbeit sind die Azimutalprojektionen von Bedeutung. Hierbei berührt die Projektionsebene die Kugel nur an einem Punkt. Die meisten Azimutalprojektionen sind echte perspektivische Projektionen. Sie haben ein Projektionszentrum und können geometrisch konstruiert werden. Somit eignen sie sich für kreisförmige Gebiete, wie die Pole der Erde. Die gnomonische und stereograﬁsche Projektion sind Beispiele für echte Azimutalprojektionen. Anhand dieser lässt sich in Abbildung 5.7 das Prinzip der echten Projektionen darstellen.

87

5 Statistisches Modell für Oberﬂächennormalen

Abbildung 5.6: In der Kartograﬁe wird grob zwischen Zylinder-, Kegel- und Azimutalprojek-

Abbildung 5.7: Bei den echten Azimutalprojektionen gibt es immer einen Punkt, welcher dem

Ursprung aller Projektionsstrahlen entspricht.

88

sondern rein mathematische Abbildungen. Im Folgenden wird die mittelabstandstreue Azimutalprojektion für eine Einheitskugel betrachtet. Der Punkt, an welchem die Projektionsebene die Kugel berührt, wird als Berührungspunkt b bezeichnet. Möchte man also einen Punkt p auf eine Ebene projizieren, benötigt man zunächst b um die Ebene zu bilden. Man spricht von einer Projektion von p an b. Die Punkte p und b beﬁnden sich in einem geographischen Koordinatensystem. Ihre Position wird durch den Längengrad λ und den Breitengrad ϕ beschrieben. Der zugehörige Punkt p T auf der Tangentialebene ist durch die Koordinaten (x, y) deﬁniert.

Für die Umrechnungen zwischen der Kugel und der Tangentialebene mittels mittelabstandstreuer Azimutalprojektion gilt:

cos ϕ p sin(λ p − λ b ),

^c Die Komponente k der Gleichung wird als k = sin(c) berechnet. Für c gilt cos(c) =

sin ϕ b sin ϕ p +cos ϕ b cos ϕ p cos(λ p −λ b ). Die Azimutalprojektion lässt sich mit dem Operator A wie folgt formulieren:

Abbildung 5.8: Bei der Projektion eines Punktes mit der mittelabstandstreuen Azimuthalpro-

bp und bpT gleich.

schen b und p ist mit dem zwischen b und p T identisch. Die Projektion von der Tangentialebene auf die Einheitskugel bezeichnet man als inverse Projektion. Wird ein auf der Tangentialebene abgebildeter Punkt zurück auf die Kugel projiziert,

89

5 Statistisches Modell für Oberﬂächennormalen

so entspricht er wieder dem ursprünglichen Punkt. Sind p und b identisch, so gilt x = 0 und y = 0, da b dem Ursprung des lokalen Koordinatensystems der Tangentialebene entspricht. Für die inverse Projektion gilt:

⎧ wobei

2

^{x π} ω = wenn ϕ b = ⎪ ⎪ ⎪ ⎩ −y 2

^{x π} wenn ϕ b = −

y 2

x ² + y ² gilt. Für die inverse Azimutalprojektion kann nun der Operator und c =

A ⁻¹ deﬁniert werden: ⁻¹ A ^(ϕ b ^,λ b ) ((x, y)) = (ϕ p , λ p ).

5.1.3 Eigenwerte und Eigenvektoren

Lineare Abbildungen lassen sich durch Matrizen beschreiben. Ihre geometrischen Eigenschaften sind hierbei jedoch nicht oﬀensichtlich. Sie lassen sich bestimmen indem man Vektoren betrachtet, welche ihre Richtung durch diese Abbildung nicht verändern. Man bezeichnet solche Vektoren als ﬁxierte Richtungen. In diesem Fall wird ein von Null verschiedener Vektor r durch eine Matrix A auf ein Vielfaches seiner selbst abgebildet. Zwischen ihnen besteht folgender Zusammenhang:

Ar = λr. (5.3)

Der Faktor λ ist eine reelle Zahl ungleich Null und gibt den Skalierungsfaktor des Vektors r an. Im n-dimensionalen Raum gibt es höchstens n Vektoren, welche die Gleichung (5.3) erfüllen. Man spricht hierbei von den Eigenvektoren der Matrix A. Der jeweilige Skalierungsfaktor eines Eigenvektors r wird als der zugehörige Eigenwert λ bezeichnet.

Um die Eigenvektoren und Eigenwerte einer Matrix zu bestimmen wird zunächst in Gleichung (5.3) die Einheitsmatrix E eingeführt. Somit ist für Glei-

90

chung (5.3) folgende Umformung möglich:

[A − λE]r = 0. (5.4)

Daher bildet [A − λE] einen von Null verschiedenen Vektor r auf den Nullvektor ab. Um die Eigenwerte zu ermitteln gilt:

n

i=1

Die Auswertung von Gleichung (5.5) führt zu einem Polynom nten Grades von λ, wobei n der Ordnung des linearen Systems aus Gleichung (5.4) entspricht. Man nennt dieses Polynom das charakteristische Polynom der Matrix A. Die Nullstellen des Polynoms entsprechen den Eigenwerten von A. Um die zugehörigen Eigenvektoren zu erhalten wird Gleichung (5.3) durch Einsetzten der Eigenwerte gelöst. Im Folgenden wird die Bedeutung der Nullstellen und Eigenschaften einer symmetrischen Matrix herausgestellt.

Die Bedeutung der Nullstellen lässt sich an einem Polynom zweiten Grades, also einer quadratischen Gleichung verdeutlichen. Solch eine Gleichung besitzt entweder keine, eine oder zwei Nullstellen. Gibt es keine Nullstellen, so existiert auch keine ﬁxierte Richtung. Dies ist zum Beispiel bei einer Rotation der Fall, da jeder Vektor gedreht wird und somit seine Richtung ändert. Eine Rotation ist in Abbildung 5.9(b) dargestellt. Die Scherung ist eine Abbildung, welche nur eine ﬁxierte Richtung erhält. Dies bedeutet, dass aus dem Polynom nur eine Nullstelle resultiert. In Abbildung 5.9(c) ist eine Scherung und die ﬁxierte Richtung dargestellt. Als Vergleich zeigt Abbildung 5.9(a) das Bild ohne Transformation.

In dieser Arbeit ist es wichtig, dass alle Eigenwerte reell sind. Allgemein lässt sich sagen, dass symmetrische Matrizen immer reelle Eigenwerte besitzten. Für

solche Matrizen gilt A = A ^T . Die Anzahl der Nullstellen entspricht somit der Dimension von A.

Nun wird eine Eigenschaft der Eigenvektoren einer solchen symmetrische Matrix erläutert. Es seien die beiden Gleichungen für die Eigenwerte und Eigenvektoren einer symmetrischen Matrix A gegeben:

Ar 1 = λ 1 r 1

5 Statistisches Modell für Oberﬂächennormalen

(a) Ohne Transformation (b) Rotation (c) Scherung

Abbildung 5.9: Je nach angewandter Transformation ergeben sich unterschiedlich viele ﬁxierte

Richtungen.

und Ar 2 = λ 2 r 2 . (5.7)

Zunächst kann man Gleichung (5.7) um r ^T 1 erweitern:

^{T T} r 1 Ar 2 = λ 2 r 1 r 2 . (5.8)

Es wird vorerst nur die linke Seite betrachtet und r ^T 1 A zu (A ^T r 1 ) ^T umgestellt:

^{T T T} r 1 Ar 2 = (A r 1 ) r 2 .

Da A symmetrisch ist, gilt:

^{T T T} r 1 ) r 2 = (Ar 1 ) r 2 . (A

Unter Verwendung von Gleichung (5.6) folgt weiterhin:

^{T T} r 2 = (λ 1 r 1 ) r 2 . (Ar 1 )

Die Klammerung um λ 1 r 1 kann vernachlässigt werden, da λ 1 ein Faktor ist und es somit keinen Unterschied macht ob man ihn transponiert:

^{T T} (λ 1 r 1 ) r 2 = λ 1 r 1 r 2 .

Die rechte Seite der Gleichung (5.8) wird nun wieder mit λ 1 r ^T 1 r 2 in eine Gleichung

92

gebracht, sodass man

^{T T} λ 1 r 1 r 2 = λ 2 r 1 r 2

erhält. Durch weitere Umformung erhält man:

^T (λ 1 − λ 2 )r 1 r 2 = 0. (5.9)

In der Regel gilt λ 1 = λ 2 . Die Eigenvektoren r 1 und r 2 müssen daher orthogonal zueinander stehen, damit Gleichung (5.9) erfüllt ist. Weitere Informationen zu Eigenwerten und Eigenvektoren sind in [FH01] zu ﬁnden.

5.1.4 Hauptkomponentenanalyse

Große Datenmengen müssen häuﬁg geeignet analysiert werden um signiﬁkanten Eigenschaften zu ermitteln. Geometrisch betrachtet handelt es sich hierbei um die Ausdehnungen einer Datenmenge im Raum. Für Grauwertbilder von Gesichtern kann man sie sich als die extremsten Helligkeiten der Bilder vorstellen. Signiﬁkante Eigenschaften sind hierbei also durch sehr hohe und sehr niedrige Grauwerte bestimmt. Formal ausgedrückt spannen diese Eigenschaften einen Grauwertraum auf, welcher sämtliche Grauwerte der Bilder beinhaltet. Um solche Eigenschaften zu bestimmen, kann eine Hauptkomponentenanalyse (engl. Principal Component Analysis) verwendet werden. In der Bildverarbeitung spricht man auch von der Karhunen-Loéve-Transformation [FP03]. Zunächst folgt ein anschauliches Beispiel, welches die Bedeutung der Hauptkomponentenanalyse geometrisch verdeutlicht. Im nächsten Schritt wird anhand von Grauwertbildern gezeigt, wie sich mit dieser Analyse signiﬁkante Eigenschaften der Bilder berechnen lassen. Schließlich kann der durch die Bilder aufgespannte Grauwertraum mit den berechneten Eigenschaften reduziert werden.

Geometrische Veranschaulichung

Gegeben sei eine zweidimensionale Punktmenge, welche in Abbildung 5.10 dargestellt ist. Um die Ausdehnung dieser Menge möglichst einfach zu beschreiben, kann man eine Gerade durch die Menge legen. Die Richtung der Geraden muss sich dazu an der Ausdehnung orientieren. Abbildung 5.11 zeigt zwei Möglichkeiten diese Gerade zu wählen. Es ist zu erkennen, dass sich die Geraden in Richtung der

93

5 Statistisches Modell für Oberﬂächennormalen

1. Achse

2. Achse

Abbildung 5.10: Eine Punktmenge im zweidimensionalen Raum.

1. Achse 1. Achse

2. Achse 2. Achse

(a) (b)

Abbildung 5.11: Zwei Möglichkeiten um eine neue Achse durch die Punktmenge zu legen.

94

größten Ausdehnung der Punktmenge orientiert. Die optimale Lösung besteht jedoch in der Ausgleichsgeraden der Menge. Sie ist so deﬁniert, dass die Summe der Abstände zwischen den Punkten und der Geraden minimal ist. Abbildung 5.12(a) zeigt diese Ausgleichsgerade. In Abbildung 5.12(b) sind die Abstände der Punk-

te zu der Geraden dargestellt. Die Ausgleichsgerade bezeichnet man als die erste

(a) Die durch eine

Abbildung 5.12: Eine Hauptachse wird so bestimmt, dass die Summe der Abstände zu den

Punkten minimal ist.

Hauptkomponente oder -achse der Punktmenge. Die erste Hauptkomponente beschreibt somit die größte Ausdehnung der Punktmenge.

Analytische Bestimmung

Die Berechnung der Hauptkomponenten erfolgt nun anhand von Helligkeitsbildern. Es sei eine Menge von Helligkeitsbildern I gegeben:

I = {I k |k = 1, . . . , K} .

Jedes Bild besitzt die Auﬂösung N = X res × Y res , wobei X res die horizontale und Y res die vertikale Auﬂösung beschreibt. Ein Grauwert im kten Bild wird mit I k (x, y) notiert.

Möchte man diese Bilder analysieren, besteht ein erster Ansatz darin, den mittleren Helligkeitswert eines Bildpunktes (x, y) zu berechnen. Fasst man die Hellig-

95

5 Statistisches Modell für Oberﬂächennormalen

keitswerte der K Bilder von einem Bildpunkt (x, y) = (i) zusammen, so lassen sich die Helligkeitswerte als Menge H i betrachten.

¹ h ¹ k = I k (i = 1) ∈ R |k = 1, . . . , K H 1 =

Der Mittelwert ¯ h 1 berechnet sich durch die Summe der einzelnen Helligkeiten dividiert durch K: K

K

Er beschreibt die durchschnittliche Helligkeit. Dieser Mittelwerte wird auch als arithmetisches Mittel oder Erwartungswert bezeichnet. Alleine betrachtet ist er jedoch nicht besonders aussagekräftig, da verschiedene Mengen den selben Mittelwert haben können, obwohl sie sich in ihrer Ausdehnung unterscheiden. In Abbildung 5.13 sind zwei solche Mengen und ihre Mittelwerte gezeigt. Es ist zu

Abbildung 5.13: Der mittlere Grauwert der beiden Mengen ist gleich, obwohl sie sich in ihren

dunkelsten und hellsten Werten unterscheiden.

erkennen, dass beide Mengen den selben mittleren Grauwert besitzen. Sie unterscheiden sich jedoch bedeutend in ihren dunkelsten und hellsten Werten.

Um den Bereich, welchen die Grauwerte abdecken, zu beschreiben verwendet man die Varianz. Sie beschreibt die durchschnittliche Abweichung aller Helligkeitswerte bezüglich des mittleren Grauwerts von H 1 . Die Varianz var(H 1 ) ist somit ein Maß für die Streuung der Helligkeitswerte. K

K

Durch das Quadrieren der Abstände wird vermieden, dass sich negative und positive Diﬀerenzen gegenseitig aufheben. Zieht man die Wurzel der Varianz, erhält man die Standardabweichung s: K

96

Sie besitzt die selbe Einheit wie H 1 .

Mit der Varianz lässt sich nun für jeden Bildpunkt i berechnen, wie stark sein Grauwert vom mittleren Grauwert des Bildpunktes abweicht. Dies sagt jedoch nichts darüber aus, wie die Grauwerte der gesamten Bilder voneinander abhängen. Möchte man diese Abhängigkeiten untersuchen, bestimmt man die Kovarianz. Hierfür wird eine zweite Menge H 2 hinzugenommen, welche wiederum die Helligkeitswerte eines zweiten Bildpunktes der K Helligkeitsbilder darstellt:

¹ H 2 = {h ² k = I k (i = 2) ∈ R |k = 1, . . . , K}.

Die Kovarianz cov(H 1 , H 2 ) beschreibt nun, wie stark die Helligkeitswerte der beiden Bildpunkte H 1 und H 2 zusammenhängen: K

K

Die Bedeutung der Kovarianz lässt sich in drei Fälle unterscheiden:

sich die Kovarianzmatrix aufstellen. Hierfür werden nun die Mengen {H i |i = 1, . . . , N} der einzelnen Bildpunkte betrachtet. Die Kovarianzmatrix Cov der Mengen bildet sich wie folgt: ⎛ ⎞

Die Matrix beinhaltet die paarweisen Kovarianzen der Bildpunkte i. Auf der Hauptdiagonalen von Cov beﬁnden sich die Varianzen der Mengen, da cov(H i , H i ) = var(H i ) gilt. Eine Kovarianzmatrix ist per Deﬁnition stets symmetrisch. Weiterhin

97

5 Statistisches Modell für Oberﬂächennormalen

lässt sie sich so diagonalisieren, dass die Diagonalmatrix wieder die Varianzen enthält [KZ95]. Sämtliche Skalarprodukte der Spalten einer Diagonalmatrix ergeben Null. Sie deﬁniert somit die Orthonormalbasis von Cov. Da sich auf der Diagonalen die Varianzen beﬁnden, welche die Streuung der Grauwerte beschreibt, spannt diese Orthonormalbasis den Grauwertraum der Bilder auf. Wie in Abschnitt 5.1.3 gezeigt, ist die Orthonormalbasis einer symmetrischen Matrix durch ihre Eigenvektoren bestimmt. Die zugehörigen Eigenwerte bestimmen die Länge der Eigenvektoren. Der Eigenvektor zum größten Eigenwert von Cov beschreibt somit die größte Ausdehnung des Grauwertraums. Er stellt die erste Hauptkomponente der Helligkeitswerte der K Grauwertbilder dar. Die weiteren Hauptkomponenten ergeben sich aus den Eigenvektoren, welche zu den absteigend sortierten Eigenwerten gehören. Die Reihenfolge der Eigenwerte bestimmt somit die Ordnung der Hauptkomponenten.

Zusammenfassend lässt sich nun die Bedeutung der Hauptkomponenten von Grauwertbildern erläutern. Die erste Hauptkomponente beinhaltet N Grauwerte, welche sich am deutlichsten von den N durchschnittlichen Grauwerten der Bilder unterscheiden. Sie beschreibt somit ein Bild, das sehr große und kleine Helligkeitswerte besitzt. Mit absteigender Ordnung nähern sich die Helligkeitswerte der Hauptkomponenten immer mehr den durchschnittlichen Grauwerten an.

In Abbildung 5.14 sind 16 Grauwertbilder dargestellt. Ihre sechs wichtigsten Hauptkomponenten sind in Abbildung 5.15 gezeigt. Es es ist erkennen, dass die ersten vier Hauptkomponenten einen deutlichen Helligkeitsunterschied besitzen. Es werden sehr helle und dunkle Bereiche des Bildes herausgestellt, da diese vom Durchschnittsgesicht am stärksten abweichen. Die letzten beiden hingegen weisen weniger Helligkeitsunterschiede auf. Sie besitzen hauptsächlich mittlere Grauwerte.

Datenreduktion

Untersucht man Bilder auf ihre Eigenschaften mittels einer Hauptkomponentenanalyse, entspricht die Anzahl der resultierenden Hauptkomponenten der Anzahl der Bilder. Für sehr viele Bilder entsteht somit eine große Menge von Hauptkomponenten, welche zur weiteren Verarbeitung dienen. Eine sehr große Menge kann sich nachteilig auf Laufzeiten von Algorithmen auswirken. Weiterhin weisen

98

Abbildung 5.14: Die 16 Bilder dienen als Basis für eine Hauptkomponentenanalyse. Bildnach-

Abbildung 5.15: Die ersten beiden Spalten beinhaltet sehr große und kleine Grauwerte. Die

beiden Hauptkomponenten in der dritten Spalte unterscheiden sich weniger

5 Statistisches Modell für Oberﬂächennormalen

Hauptkomponenten mit absteigender Ordnung immer weniger Unterschiede untereinander als auch zum Durchschnittsbild auf. Es ist daher sinnvoll, nicht mit allen Komponenten weiter zu arbeiten.

Häuﬁg wird eine Hauptkomponentenanalyse eingesetzt um zunächst die Eigenschaften einer Datenmenge zu ermitteln und anschließend nur die wichtigsten zu verwenden. Ein solcher Ansatz ist beispielsweise in [TP91b] zu ﬁnden. Der durch alle Hauptkomponenten aufgespannte Raum wird durch diese Reduktion in einen Unterraum abgebildet. Für einen Bildpunkt bedeutet dies, dass Grauwerte erhalten bleiben, die sich stark von seinem mittleren Grauwert unterscheiden. Im Bereich des mittleren Grauwerts sind sehr viele Grauwerte vorhanden, welche eine ähnliche Helligkeit aufweisen. Einige dieser Grauwerte werden durch Hauptkomponenten mit niedriger Ordnung repräsentiert und fallen bei einer Reduktion weg.

5.1.5 Mittelwertbildung von Einheitsvektoren

Gegeben sei eine Menge V mit m Einheitsvektoren v i mit (v i = 1):

³ V = {v i ∈ R |i = 1, . . . , m}.

Diese Menge besitzt den arithmetischen Mittelwert ¯ v.

m

i=1

Dieser Mittelwert minimiert die Summe der euklidischen Abstände von V , sodass

m

ⁱ⁼¹ gilt. Dies lässt sich dadurch begründen, dass die Nullstelle der Ableitung von Gleichung (5.12) gerade Gleichung (5.11) entspricht. Formal ausgedrückt wird

m m ^{i=1 i=1}

^m ¹ Durch Umformen erhält man als Nullstelle ¯ v = i=1 v i .

m

Eine Möglichkeit Einheitsvektoren zu betrachten besteht darin, sie als Punkt-

100

menge P mit Kugelkoordinaten auf einer Einheitskugel S ² darzustellen.

² P = {p i = (θ, α) ∈ S |i = 1, . . . , m}

Abbildung 5.16 zeigt, dass sich diese Punkte an den Berührungspunkten der Nor- mit der Oberﬂäche der Einheitskugel beﬁnden. Eine Einheitskugel S ² ent-

Abbildung Einheitsvektoren

spricht einer Riemannschen Mannigfaltigkeit. Sie dient im Allgemeinen der mathematischen Beschreibung einer gekrümmten Fläche oder eines höherdimensionalen gekrümmten Gebildes. Eine ausführliche Behandlung der Theorie der Riemannschen Mannigfaltigkeit ist beispielsweise in [Car92] zu ﬁnden.

Die Position von Punkten auf einer Einheitskugel werden durch Kugelkoordinaten repräsentiert. Die Punkte werden also durch zwei Winkel dargestellt, sodass der Mittelwert nicht mit Gleichung (5.11) ermittelt werden.

Eine Herangehensweise zur Berechnung der Mittelwerte von P besteht darin,

S ² in einen euklidischen Raum zu überführen [Fle04; Smi07]. Diese Überführung

ist für eine Mannigfaltigkeit durch den Einbettungssatz von Whitney (siehe beispielweise [BJ73]) deﬁniert. Für die Einbettung der Einheitskugel in einen quadratischen Raum wird der Überführungsoperator

2 2 → R Φ : S

5 Statistisches Modell für Oberﬂächennormalen

deﬁniert. Der Operator Φ kann beispielweise durch eine Projektion realisiert werden kann. Bei der Projektion müssen die Abstände, welche zur Mittelwertsberech- relevant sind, erhalten bleiben. Ein Punkt auf S ² ist somit in den euklidischen Raum R ² abbildbar. Der Mittelwert μ Φ kann nun wieder als der Punkt deﬁniert

werden, welcher die Summe der quadrierten Abstände von P Φ minimiert:

m

² . Φ(p) − Φ(p i ) μ Φ = arg min (5.13)

p∈S ² i=1

Um μ Φ zu berechnen ist zunächst die Rücküberführung eines Punktes von R ² nach S ² notwendig. Diese wird durch den Operator

^{2 2} π : R → S

deﬁniert. Für den Operator muss gelten, dass er q auf einen Punkt p ∈ S ² abbildet,

sodass die Abstände zwischen q und p im euklidischen Raum minimal sind. Auch π kann durch eine Projektion deﬁniert werden, welche zu der Projektion Φ die Inverse bildet. Dies ist durch

² Φ(p) − q π(q) = arg min

p∈S 2

erfüllt. Basierend auf den eingeführten Operatoren lässt sich μ Φ in gleicher Weise wie in Gleichung (5.11) berechnen:

m

i=1

Man spricht bei μ Φ von dem extrinsischen Mittelwert von P . Durch die Überführung in einen euklidischen Raum entspricht die Mittelswertberechnung aus Gleichung (5.14) der Berechnung aus Gleichung (5.11). Fasst man μ Φ wieder als Vektor auf, so ist er identisch mit ¯ v. Aus beiden Gleichungen resultiert somit der selbe Mittelwert.

In Abbildung 5.17(a) ist die extrinsische Mittelwertbildung schematisch dargestellt. Die Einheitskugel wurde zur Veranschaulichung auf einen Kreis abstrahiert. Die euklidischen Abstände sind als Pfeile markiert. Als arithmetisches Mittel ergibt sich der weiße Punkt, welcher durch die Rückprojektion auf den Kreis in den

102

Abbildung 5.17: Schematischer Aufbau des intrinsischen und extrinsischen Mittels. Bild an-

mit × makierten extrinsischen Mittelwert μ Φ überführt wird. Betrachtet man nun Abbildung 5.17(b) so fällt auf, dass sich der Mittelwert, welcher auf den tatsächlichen Abständen beruht, an einer anderen Stelle beﬁndet. Er wird als intrinsischer Mittelwert μ bezeichnet. Um μ zu berechnen, müssen die gekrümmten Abstände auf der Kugeloberﬂäche verwendet werden.

Auf einer Riemannschen Mannigfaltigkeit ist die kürzeste Strecke zwischen zwei Punkten eine Geodäte. In einer Ebene ist die Geodäte eine Gerade, auf einer Einheitskugel eine Kurve. Um einen solchen gekrümmten Abstand zu berechnen, verwendet man die Riemannsche Metrik [Car92]. Zunächst wird die Tangential- T b S ² deﬁniert, welche S ² im Punkt b berührt. Der Ursprung von T beﬁndet sich in b. Ein beliebiger Punkt p auf T b S ² lässt sich mit seinem Ortsvektor p beschreiben. Mit einer sogenannten exponential map kann p auf S ² abgebildet werden und entspricht daher dem π Operator. Den resultierenden Punkt auf S ² bezeichnet man mit Exp b (p). Von b ausgehend liegt Exp b (p) in Richtung von p und ist mit einem Abstand von p entfernt. Das Prinzip der exponential map ist in Abbildung 5.18 dargestellt.

Um einen Ortsvektor auf T b S ² aus einem Punkt Exp b (p) zu erhalten, verwendet

man die log map. Sie bildet daher die inverse Operation zur Exp b und wird mit Log b bezeichnet. Es gilt somit:

Log b (Exp b (p)) = p.

5 Statistisches Modell für Oberﬂächennormalen

² auf Abbildung 5.18: Eine exponential map bildet einen Ortvektor p der Tangentialebene T b S

² ab. Die Länge des Ortsvektors einen Punkt Exp b (p) auf der Einheitskugel S

entspricht dabei dem Abstand zwischen Exp b (p) und b. Seine Richtung bleibt

ebenfalls erhalten.

Die log map entspricht dem Φ Operator.

Für die Abbildungen exponential map und log map wird nun eine mathematische Beschreibung gesucht. Zu berücksichtigen ist hierbei, dass Abstände und Richtungen durch die Abbildungen erhalten bleiben. In Abschnit 5.1.2 wurde bereits eine Azimutalprojektion erläutert, welche diese Bedingungen erfüllt. Da hierfür geographische Koordinaten Voraussetzung sind, muss P zu P G konvertiert werden:

² P G = {p ^G i = (ϕ, λ) ∈ S |i = 1, . . . , m}.

Für die exponential map wird im Folgenden die inverse mittelabstandstreue Azimutalprojektion verwendet:

⁻¹ Exp b (p) = A b (p).

Als log map lässt sich die mittelabstandstreue Azimutalprojektion verwenden:

Log b (Exp b (p)) = A b (Exp b (p)).

Der Abstand zwischen zwei Punkten p ^G 1 und p ^G 2 auf der Einheitskugel S ² kann

nun unter Verwendung der log map berechnet werden. Fasst man den Punkt p ^G 1

als Berührungspunkt von T an S ² auf, erhält man die Tangentialebene T ^p ^G 1 S ² .

104

(p ^G 2 ) bestimmt man den Ortsvektor von p ^G 2 auf T ^p ^G 1 S ² . Durch Abbildung Log ^p ^G 1

Der Abstand zwischen p ^G 1 und p ^G 2 entspricht der Länge des Ortsvektors, sodass gilt: d(p ^G 1 , p ^G 2 ) = Log ^p ^G 1

chungen (5.12) und (5.13) als Minimierungsproblem auﬀassen:

m

ⁱ⁼¹ Dieser Punkt kann nicht analytisch gefunden werden. Zur Berechnung von μ kann ein Gradientenverfahren verwendet werden [FLPJ04; Pen99]. Dafür ist eine Startschätzung μ für den ersten Iterationsschritt j = 0 notwendig. Der extrinsische Mittelwert μ Φ stellt einen guten Startwert μ (j=0) = μ Φ für das Verfahren dar. Die Schätzung μ (j) wird in jedem Iterationsschritt verbessert. Die nächste Iteration berechnet sich wie folgt:

m

i=1

Die Punkte werden zunächst anhand des aktuell geschätzten Mittelwerts auf die Tangentialebene projiziert. Anschließend bildet man das arithmetische Mittel der projizierten Punkte. Dieses Mittel kann von dem Mittel des letzten Iterationsschritts abweichen. Das Abgleichen dieser Abweichung mit einem Schwellwert ε dient als Konvergenzkriterium. Es ist erreicht, wenn

gilt. Der Algorithmus zur Bestimmung des intrinsischen Mittelwerts lässt sich wie in Algorithmus 5.1 zusammenfassen.

Abschließend kann man sagen, dass der intrinsische Mittelwert mehr der tatsächlichen mittleren Normale entspricht als der extrinsische Mittelwert. Dies lässt sich dadurch begründen, dass die tatsächlichen Abstände zwischen den Punkten auf der Einheitskugel als Berechnungsgrundlage dienen.

105

5 Statistisches Modell für Oberﬂächennormalen

Algorithmus 5.1 Berechnung des intrinsischen Mittelwertes der Punktmenge P Input: Punktmenge P , Extrinsischer Mittelwert μ ^Φ Output: Intrinsischer Mittelwert μ 1: μ (j=0) = μ Φ

2: repeat

m

1

3: 4: j = j + 1 5:

6: until μ < ε

5.2 Statistische Modelle für Gesichter

Menschliche Gesichter besitzten die verschiedensten Eigenschaften. Es werden jedoch nicht alle Eigenschaften benötigt um einen Großteil sämtlicher Gesichter nachzubilden. Stattdessen reicht eine Kombination signiﬁkanter Gesichtsmerkmale für die Nachbildung aus. Diese Gesichtsmerkmale lassen sich in einem sogenannten Gesichtsraum zusammenfassen.

Das Bilden eines Gesichtsraums entspricht der Grundidee von modellbasierten Ansätzen zur Rekonstruktion von Gesichtern. Hierbei werden die wichtigsten Gesichtseigenschaften ermittelt und in einem statistischen Modell zusammengefasst. Durch eine Analyse werden Gemeinsamkeiten und markante Partien von Beispielgesichtern herausgeﬁltert. Diese Beispielgesichter werden im Folgenden als Trainingsdaten oder Trainingsgesichter bezeichnet. Für ein zweidimensionales Modell bestehen sie typischerweise aus einer Reihe verschiedener Gesichtsfotograﬁen, während bei einem dreidimensionales Modell eine Menge von 3D Laserscans Verwendung ﬁndet.

5.2.1 Eigenbilder und Eigengesichter

Für den Menschen ist es ohne Weiteres möglich, eine Vielzahl von verschiedenen Gesichtern zu erkennen. In [FP03] ist beschrieben, dass in [Kir87] davon ausgegangen wird, dass das menschliche Gehirn nur wenige Gesichter hierfür benötigt. Dies entspricht der Idee einer Hauptkomponentenanalyse. Sie dient dazu, die wichtigsten Eigenschaften der Trainingsdaten zu ermitteln. Die resultierenden Hauptkomponenten werden als Eigenbilder bezeichnet.

106

Verwendung. Die Versuche und Tests, welche in [FP03] beschrieben sind, zeigen, dass nur die ersten 40 Hauptkomponenten für die Rekonstruktion der Trainingsdaten benötigt werden. In diesen sind die markantesten Merkmale der Gesichter zusammengefasst. Redundante Informationen werden hingegen vernachlässigt. Auf diese Weise sind anstatt der 115 × N Grauwerte nur noch 40 × N notwendig. Dies entspricht einer hohen Datenreduktion und weiterverarbeitende Verfahren können daher eﬃzienter arbeiten.

Das Prinzip der Eigenbilder wird von [TP91b] aufgegriﬀen und dient als Basis für die sogenannte Eigengesicht-Methode. Diese Methode dient zur Gesichtserkennung in Bildern. Auch hier werden die Unterschiede zwischen den Trainingsdaten mittels einer Hauptkomponentenanalyse untersucht. In Abbildung 5.15 sind Eigengesichter dargestellt.

Die Idee der Eigengesicht-Methode ist es, das zu erkennende Gesicht mit einer Kombination aus Eigengesichtern nachzubilden. Zur Erkennung muss das Gesicht zunächst lokalisiert und anschließend als eines der Trainingsgesichter identiﬁziert werden. Da bei der Reduktion der Hauptkomponenten vor allem redundante Informationen vernachlässigt werden, kann durch Kombination der Eigengesichter jedes der Trainingsgesichter erkannt beziehungsweise nachgebildet werden. Um nun ein Gesicht in einem Bild zu erkennen, werden die kombinierten Gesichter mit dem Eingangsbild verglichen. Über ein Fehlermaß lässt sich entscheiden, ob es sich um das zu erkennende Gesicht handelt.

Daher kann man abschließend sagen, dass bei der Eigengesicht-Methode das zu erkennende Bild rekonstruiert wird. Der beschriebene Ansatz ist für Bilder ausgelegt und eignet sich somit nicht für die Rekonstruktion dreidimensionaler Gesichtsmodelle.

5.2.2 Dreidimensionale statistische Modelle

Die ersten Beschreibungen eines Modells für dreidimensionale Gesichtsscans sind in [AGR96a; AGR96b] zu ﬁnden. Als Trainingsdaten für das Modell dienen 200

Laserscans, welche mit einem Cyberware ^™ Scanner aufgenommen wurden. Mit

eine Hauptkomponentenanalyse werden die wichtigsten Eigenschaften und Unterschiede zwischen den Laserscans ermittelt. Diese Hauptkomponenten werden statt

107

5 Statistisches Modell für Oberﬂächennormalen

Eigengesichtern, beziehungsweise Eigenbildern nun Eigenköpfe genannt. Hierbei gibt es verschiedene Bedingungen die erfüllt sein müssen um das Verfahren erfolgreich zur Rekonstruktion von Gesichtsmodellen aus Fotograﬁen zu verwenden:

• der Kopf muss frontal in die Kamera schauen und

• die Lichtquelle muss bekannt sein.

Das Verfahren rekonstruiert ein Gesichtsmodell, indem durch eine Linearkombination der Eigenköpfe das Gesicht angenähert wird. Der Ansatz von [AGR96a] beachtet hierbei als einziges Kriterium die Gesichtsform. Es können daher nur Formen entstehen, welche durch die Trainingsdaten abgedeckt sind. Man spricht hierbei auch davon, dass man an den Gesichtsraum der Trainingsdaten gebunden ist.

In [BV99] ist ein Verfahren beschrieben, welches eine ähnliche Herangehensweise wie [AGR96a] besitzt. Hierbei werden jedoch neben den Geometriedaten die Oberﬂächenfarben, die den Texturen der Laserscans entsprechen, berücksichtigt. Das Verfahren dient zur Rekonstruktion von Gesichtsmodellen aus einzelnen Fotograﬁen. Im ersten Schritt wird aus den Trainingsdaten ein Modell gebildet. Hierfür ist die sogenannte Korrespondenz zwischen den Laserscans notwendig. Sie beschreibt gemeinsame Gesichtspunkte zweier Gesichtsmodelle, wie beispielsweise die Nasenspitze. Damit ist es möglich linear zwischen den Gesichtern zu interpolieren ohne sie zu verzerren. Ein Beispiel für solch eine Interpolation ist in Abbildung 5.19 dargestellt. In der Abbildung entspricht das erste und das letzte

Abbildung 5.19: Mit einer Korrespondenz zwischen Gesichtern lassen sich durch lineare Inter-

Gesicht jeweils einem Beispielgesicht aus den Trainingsdaten. Die Zwischengesichter entstehen durch Interpolation, bei welcher die Beispielgesichter unterschiedlich gewichtet werden.

108

ten zu allen anderen Laserscans berechnet. Durch dieses Vorgehen kann zwischen allen Gesichtern interpoliert werden, da für alle die Korrespondenz zum Referenzgesicht bekannt ist. Im nächsten Schritt wird nun eine Hauptkomponentenanalyse auf die Form-, als auch auf die Texturdaten angewendet. Sie werden getrennt betrachtet um möglichst unabhängig ihre signiﬁkantesten Eigenschaften zu ermitteln. Hierbei gehen die Korrespondenzen nicht verloren, sodass man zwischen den Hauptkomponenten linear interpolieren kann. Das daraus resultierende Modell wird in [BV99] als Morphable Model bezeichnet, da man Interpolation auch als Morphing bezeichnen kann. Wie stark Form und Textur der Trainingsdaten in das aktuelle Gesicht einﬂießen wird anhand von Gesichtsparametern beschrieben.

Um nun ein Gesicht zu rekonstruieren wurde in [BV99] ein Algorithmus entwickelt, welcher eine Fotograﬁe iterativ annähert. Dazu initialisiert man das Gesichtsmodell zu Beginn mit dem Durchschnittsgesicht von allen vorhandenen Trainingsdaten. Darauf aufbauend richtet man es grob auf das zu rekonstruierende Gesicht aus. Diese Startwerte bilden den Ausgangspunkt für den Rekonstruktionsprozess. In einem Synthese-durch-Analyse-Verfahren (siehe [BV99]) wird zunächst ein Bild generiert, welches dem Gesicht des aktuellen Iterationsschritts entspricht. Für diesen Renderprozess werden die Gesichts- und Renderparameter verwendet. Die Renderparametern beschreiben die Lichtposition, -stärke, -farbe, sowie die Kameraeinstellungen. Die initialen Werte für die Renderparameter werden von dem Benutzer geschätzt. Durch einen Vergleich des gerenderten Gesichtsbildes mit der vorliegenden Fotograﬁe lässt sich entscheiden, welche Parameter anzupassen sind. Der Algorithmus ist beendet, wenn der Fehler zwischen dem gerenderten und dem zu rekonstruierenden Bild minimal ist. Eine Rekonstruktion ist mit vielen Berechnungen verbunden, da die Ermittlung der Parameter nur durch die Minimierung von Fehlerfunktionen möglich ist.

Die Ergebnisse dieses Verfahrens sind sehr gut, solange sich das zu rekonstruierende Gesicht bei der Aufnahme unter keinen extremen Lichtverhältnissen wie Über- oder Unterbelichtung befand. Weiterhin resultiert aus einem stark spiegelnden Gesicht kein zufriedenstellendes Ergebnis. Die rekonstruierten Gesichtmodelle weisen dann nur wenig oder gar keine Ähnlichkeit mit dem tatsächlichen Gesicht auf. Der Grund für diese Schwäche liegt bei dem verwendeten Beleuchtungsmodell der Synthese. In [BV99] dient dazu das Phong-Modell, welches sich aus einer

109

5 Statistisches Modell für Oberﬂächennormalen

ambienten, diﬀusen und spiegelnden Komponente zusammen setzt. Es entspricht nicht der Realität und es ist nicht möglich, realistische Beleuchtungen von Gesichtsbildern nachzustellen. Eine weitere Einschränkung ist durch das Prinzip des Morphable Model gegeben, welches nur Zwischengesichter bilden kann. Somit kann man keine Gesichtseigenschaften rekonstruieren, welche in keinem der Trainingsdaten vorhanden sind. Daher sind die Ergebnisse prinzipiell von den Trainingsdaten abhängig. Dies gilt für alle statistischen Modelle, die auf einer Hauptkomponentenanalyse basieren, da nur Eigenschaften abgebildet werden, die auch in den Trainingsdaten vorhanden sind.

110

5.3 Aufbau des statistischen Modells

Ein statistisches Modell bildet die wichtigsten Merkmale der Trainingsdaten nach. Die in Abschnitt 5.2 eingeführten statistischen Modelle entsprechen entweder zweidimensionalen Modellen für Gesichtsbilder oder dreidimensionalen Modellen für Laserscans. Im Folgenden wird ein Modell vorgestellt, welches die Oberﬂächennormalen der in Abschnitt 5.1.1 beschriebenen Laserscans analysiert. Oberﬂächennormalen bieten einen hohen Informationsgehalt, da sie im Gegensatz zu Graustufenbildern, gegen Beleuchtungsänderungen invariant sind. Mit dem in Kapitel 4 vorgestellten Framework ist es möglich Normalenrichtungen aus einem Bild zu rekonstruieren. Das statistische Modell verbessert die Rekonstruktion, indem es die Oberﬂächennormalen der Trainingsdaten analysiert und einen Abgleich mit den Normalenrichtungen zur Verfügung stellt.

In Abbildung 5.20 sind die Schritte zum Aufbau eines statistischen Modells für Oberﬂächennormalen zu sehen. Die Vorgehensweise ist grob in drei Schritte unterteilt, welche im Folgenden näher betrachtet werden.

Wie bereits erwähnt, dienen als Trainingsdaten dreidimensionale Laserscans. Es wurde gezeigt, dass sich die Scans als zweidimensionale Felder auﬀassen lassen. Mit diesen Feldern ist es möglich, wieder auf die Gesichtsmodelle zu schließen.

Im ersten Schritt wird die Korrespondenzbestimmung durchgeführt. Die Korrespondenz drückt einen Zusammenhang zwischen zwei Bildern aus. Sie beschreibt, wie man ein Bild verändern muss, sodass die Strukturen der Bilder übereinstimmen. Es gibt verschiedene Herangehensweisen um die Korrespondenz zwischen zwei Bildern zu ermitteln. Das Verfahren von [BSP93; Bey96] liefert sehr zuverlässige Ergebnisse. Bei diesem Ansatz markiert der Benutzer interaktiv zusammengehörige Punkte in den Bildern. Mit den Punkten lässt sich die Korrespondenz zwischen den Bildern bestimmen. Es gibt Verfahren, welche ähnlich gute Ergebnisse erzielen und die Korrepondenz ohne Benutzerinteraktion bestimmen. Im Folgenden werden nun zwei Verfahren vorgestellt, welche die Korrespondenz automatisch bestimmen.

Zum Einen gibt es die merkmalsbasierte Korrespondenzanalyse. Hierbei werden zunächst Filter auf die Ausgangsbilder angewendet. Mit diesen Filtern lassen sich wichtige Bildmerkmale ﬁnden. In [KKS96] ist ein solches Verfahren beschrieben. Der zugehörige Algorithmus heißt Shirai-Algorithmus. Mit verschiedenen Filtern

111

5 Statistisches Modell für Oberﬂächennormalen

Abbildung 5.20: Der Aufbau eines Modells für Oberﬂächennormalen lässt sich grob in drei

Schritte aufteilen. Es wird zunächst der sogenannte optische Fluss zwischen

112

extrahiert der Algorithmus Kanten, sodass zwei Kantenbilder entstehen. Sie werden daraufhin untersucht. Bei ihrer Untersuchung werden homogene Bildbereiche nicht beachtet, da sie keine Strukturen besitzen. Die Korrespondenzberechnug basiert somit nur auf gradlinigen Strukturen. Gesichter bestehen im Normalfall hauptsächlich aus homogenen Partien, wie der Stirn und der Wangenregion. Sie weisen also nur selten Kanten auf. Aus diesem Grund kann eine merkmalsbasierte Korrespondenzanalyse nicht erfolgreich verwendet werden.

Eine weitere Möglichkeit die Korrespondenz zwischen zwei Bildern zu bestimmen sind ﬂussfeldbasierte Verfahren. Für jeden Bildpunkt wird hierbei eine Verschiebung ermittelt, welche die Bewegung eines Bildpunkts vom ersten zum zweiten Bild beschreibt. Dazu werden die Unterschiede zwischen den Helligkeitswerten der Bilder analysiert. Als Ergebnis resultiert der sogenannte optische Fluss. Er wird durch ein Vektorfeld repräsentiert, wie in Abbildung 5.21 dargestellt. Zur

Abbildung 5.21: Das Rechteck bewegt sich zwischen den Bildern ein Stück nach rechts. Der

optische Fluss ist ein Feld aus Vektoren, welche die Verschiebung des Recht-

Übersichtlichkeit Vektoren beschreibt die Verschiebung eines Bildpunktes zwischen den Bildern. Die Verschiebung kann auch aus ihrer Richtung und der zugehörigen Geschwindigkeit zusammengesetzt werden.

Der optische Fluss lässt sich auf unterschiedliche Weise ermitteln. Ein guter Überblick ist in [BB95] zu ﬁnden. Einige Ansätze bestimmen für jeden Bildpunkt eine eigene Verschiebung. Andere hingegen untersuchen Pixelblöcke und ordnen diesen eine Verschiebung zu. Hierbei erhalten alle Bildpunkte eines Blocks den selben Verschiebungsvektor. Im Folgenden werden die Ideen dreier typischer Verfahren zur Berechnung des optischen Flusses erläutert.

113

5 Statistisches Modell für Oberﬂächennormalen

In [Cam95] und [Ana87] wird der optische Fluss basierend auf Block-Korrelation ermittelt. In aufeinanderfolgenden Bildern wird die Helligkeit von Pixelblöcken verglichen. Den Verschiebungsvektor eines Pixelblocks erhält man indem man den ähnlichsten Pixelblock des zweiten Bildes bestimmt. Die Länge und Richtung des Verschiebungsvektors ist nun abhängig von dem korrespondierenden Pixelblock.

Die frequenzbasierten Methoden stellen eine weitere Möglichkeit zur Berechnung des optischen Flusses dar. Hierbei wird er mit Hilfe einer Fouriertransformation berechnet. Ein Beispiel ist das Verfahren aus [FJ90], welches die Verschiebungen für Pixelblöcke mittels Phasen-Korrelation bestimmt. Dazu werden die Ortsfrequenzen von Pixelblöcken in verschiedenen Bildern miteinander verglichen. Die unterschiedlichen Positionen übereinstimmender oder zumindest ähnlicher Blöcke dienen wie bei der Block-Korrelation zur Bestimmung eines Verschiebungsvektors.

Gesichter sind fein strukturiert und unterscheiden sich oft nur in kleinen Bereichen. Somit stimmen nur selten ganze Pixelblöcke zweier Gesicher überein. Die beschriebenen blockbasierten Verfahren sind daher nicht vielversprechend um die Korrespondenz zwischen Gesichtern zu bestimmen.

Eine weitere Möglichkeit den optische Fluss zu ermitteln besteht in diﬀerentiellen Methoden. In [HS81] und [LK81] werden solche Verfahren vorgestellt. Als Grundlage für die Bestimmung der Verschiebungen dienen die Gradienten der Bilder. Dabei wird für jeden Bildpunkt des ersten Bildes der nächstliegende Punkt mit gleicher Helligkeit im zweiten Bild gesucht.

Im Gegensatz zu blockbasierten Verfahren lässt sich also mit diﬀerentiellen Methoden für jeden Bildpunkt des ersten Bildes ein korrespondierender Punkt im zweiten Bild zuweisen. Daher ist für jeden Bildpunkt eines Gesichts ein Verschiebungsvektor vorhanden. Eine solche Verbindung bezeichnet man als eins-zu-eins-Korrespondenz. Da Gesichter sich in jedem Bildpunkt unterscheiden können, ist ein solches Verfahren eine gute Möglichkeit die Korrespondenz zu bestimmen.

Um das Korrespondenzproblem für alle Trainingsdaten zu lösen wird zunächst ein Referenzgesicht gewählt. Die Korrespondenzbestimmung ist zwar robust, jedoch kann es noch immer zu Fehlern kommen, wenn die Gesichtsstrukturen sich zu stark unterscheiden. Das Referenzgesicht sollte also dem Durchschnittsgesicht der dreidimensionalen Gesichtsscans ähneln. Daraufhin wird zwischen dem Referenzgesicht und jedem Trainingsgesicht der optische Fluss berechnet.

114

wie es verzerrt werden muss, damit es mit dem Referenzgesicht korrespondiert. Dieses Verzerren wird als Ausrichten bezeichnet und gehört zum Schritt Aufbau der Normalenfelder aus Abbildung 5.20. Um die Oberﬂächennormalen zu erhalten, darf bei der Ausrichtung nur die Form der Gesichtsmodelle verändert werden.

Im nächsten Schritt bildet man die Oberﬂächennormalen auf eine zweidimensionale Ebene ab um sie geeignet analysieren zu können. Dazu muss eine auf das Anwendungsgebiet abgestimmte Projektion gefunden werden. Es wird davon ausgegangen, dass die Aufnahmen der Gesichtsfotograﬁen ohne perspektivische Verzerrung entstanden sind. Weiterhin ist die Kameraposition relativ zum Gesicht zu beachten, welche sich bei der Aufnahme der Fotograﬁen frontal vor dem Gesichter beﬁndet. Mit diesen beiden Annahmen lässt sich die Projektion der Gesichtsmodelle genauer deﬁnieren. Wie in Abbildung 5.22 zu sehen ist, beﬁndet sich die Projektionsebene frontal vor dem Gesicht. Die Abbildung des Gesichts auf die Ebene entspricht einer orthogonalen Projektion. Nach der Projektion wer-

Abbildung Die

Ebene ermittelt. Die Projektionsebene beﬁndet sich dabei frontal vor dem

Gesicht.

den die Normalenrichtungen in ein Normalenfeld rasterisiert. Alle Normalenfelder sind deckungsgleich, da gleiche Gesichtsstrukturen immer die selben Positionen besitzen.

Der letzte Schritt des Verfahrens besteht in der Analyse der Normalenfelder. Die Normalenfelder setzen sich aus Einheitsvektoren zusammen und können somit als Punkte auf einer Einheitskugel dargestellt werden. Das Ziel besteht darin,

115

5 Statistisches Modell für Oberﬂächennormalen

die wichtigsten Gesichtseigenschaften, sogenannten Eigengesichter, zu ermitteln. Eine Hauptkomponentenanalyse eignet sich um signiﬁkante Eigenschaften einer Datenmenge zu bestimmen. Um die Analyse auf Normalenfelder anzuwenden, müssen sie als Punktdaten auf einer Ebene vorliegen. Zunächst werden mittlere Normalen deﬁniert, anhand welcher die Normalenfelder in einen linearen Raum überführt werden. Die Überführung geschieht durch eine Projektion der Punkte auf eine Einheitskugel. Um diese Überführung zu vollziehen, werden die Punkte von der Einheitskugel mit einer mittelabstandstreuen Azimutalprojektion (siehe Abschnitt 5.1.2) auf eine Ebene abgebildet. Schließlich lassen sich mit der Hauptkomponentenanalyse die Modelleigenschaften ermitteln.

116

5.4 Korrespondenzbestimmung

Die Korrespondenzbestimmung zwischen den Trainingsdaten ist der erste Schritt beim Aufbau des statistischen Modells. Dabei soll für jeden Punkt des Referenzgesichts der jeweilige Punkt in den Trainingsdaten bestimmt werden. Eine solche Verknüpfung der Gesichter beschreibt welche Gesichtsstrukturen zueinander gehören.

Der Unterschied zwischen dem Überlagern von Gesichtern mit und ohne Korrespondenz ist in Abbildung 5.23 verdeutlicht. In diesem Beispiel soll ein neues Bild

Abbildung 5.23: Um zwei Gesichter aufeinander auszurichten reicht es nicht aus die Bilder

übereinander zu lagern. Wie das Bild zeigt, resultiert als Ergebnis bei solch

entstehen, in welchem jedes Gesicht zur Hälfte einﬂießt. Mischt man die Farbwerte der beiden Bilder ohne die Korrespondenz zwischen ihnen zu beachten, erhält man ein verschwommenes Bild in dem die Gesichtsstrukturen sich nicht decken. Verwendet man zur Mischung der Gesichter stattdessen den optischen Fluss, welcher aus der Korrespondenzberechnung resultiert, entsteht ein neues Gesicht. Dieses lässt sich nicht von einem echten Gesicht unterscheiden. Gesichtsstrukturen wie

117

5 Statistisches Modell für Oberﬂächennormalen

Augen, Mund, Nase und Ohren liegen an der selben Position. Es ist also möglich, durch Verschieben der Gesichtsstrukturen diese in Korrespondenz miteinander zu bringen.

Da dieses Verfahren für zweidimensionale Bilder ausgelegt ist, werden die Trainingsdaten, wie in Abschnitt 5.1.1 beschrieben, als Texturen aufgefasst. Hat man die Korrespondenz zwischen den Texturen ermittelt, lassen sich die Trainingsdaten ähnlich wie in Abbildung 5.23 aufeinander ausrichten.

Im Folgenden wird ein Überblick über die notwendigen Schritte der verwendeten Korrespondenzbestimmung zwischen dreidimensionalen Laserscans gegeben. Ausgangssituation ist der optische Fluss von Bildfolgen nach [HS81]. Hierbei lassen sich jedoch nur sehr kleine Bewegungen und nicht alle Verschiebungsrichtungen ermitteln. Um sämtliche Verschiebungsrichtungen von kleinen Bewegungen zu erkennen, wird das Verfahren nach [LK81] um das Hinzuziehen von Nachbarschaften erweitert. Darauf aufbauend wird gezeigt, wie sich Bildpaare anstatt der Bildfolgen verarbeiten lassen. Damit sich auch große Bewegungen bestimmen lassen, ﬁndet in [BAHH92] eine sogenannte grob-zu-fein-Strategie Verwendung. Der optische Fluss wird hierbei für unterschiedliche Auﬂösungen berechnet und so Schritt für Schritt verfeinert. In [Bla00] wird dieses Verfahren aufgegriﬀen um die Korrespondenzbestimmung zwischen dreidimensionalen Scans zu ermitteln. Hierfür werden für alle Texturen optische Flüsse mit der grob-zu-fein-Strategie unter Verwendung von Nachbarschaften bestimmt. Die resultierenden optischen Flüsse werden anschließend zu einem einzelnen optischen Fluss gemischt. Mit diesem lassen sich die Trainingsdaten aufeinander ausrichten. Um das Verfahren zu verbessern wird im letzten Schritt eine Glättung der Verschiebungsfelder integriert.

5.4.1 Optischer Fluss von Bildfolgen

Betrachtet man nur zwei Bilder einer Bildfolge, kann das menschliche Gehirn ohne Weiteres Rückschlüsse auf die dreidimensionale Szene ziehen. Es kann die Bewegungen der Objekte und die Kamerabewegung zwischen den Bildern beschreiben ohne zusätzliche Informationen zu benötigen. Der optische Fluss ist ein Analyseverfahren mit welchem solche Rückschlüsse beschreibar sind.

Bilder einer Videosequenz sind meist sehr ähnlich, sodass sich die Positionen der abgebildeten Objekte nur geringfügig unterscheiden. In Abbildung 5.24 sind

118

zwei aufeinanderfolgende Bilder einer Sequenz dargestellt. Bei der Aufnahme wur-

Abbildung Der

gering. Bildnachweis: [Gro]

de das Blatt mit dem Schachbrettmuster im Bild bewegt, während die Kamera still stand. Dieses Beispiel verdeutlicht, dass die Unterschiede zwischen zwei Bilder einer Bildfolge nur minimal sind. Betrachtet man nun Bilder von verschiedenen Gesichtern, so treten deutlich größere Unterschiede auf. Statt einem kleinen Bewegungsunterschied besitzen sie eine andere Form und Erscheinung. Jedoch ﬁnden sich in Gesichtern generell ähnliche Strukturen, wie Augen, Ohren, Nase und Mund wieder. Aufgrund dieser Ähnlichkeiten lässt sich der optische Fluss sowohl für Bildfolgen als auch für die Texturen der Trainingsdaten auf gleiche Weise verwenden.

Eine der ersten Anwendungen für einen optischen Fluss besteht in der Bewegungserkennung in einer Bildfolge. Im Folgenden wird eine Bildfolge I(x, y, t) mit fortlaufendem t, wie in [HS81] beschrieben, betrachtet. Für zwei aufeinander folgende Bilder wird das zugehörige Vektorfeld v gesucht.

In diesem ist für jedes Pixel im Bild zum Zeitpunkt t der Verschiebungsvektor zum entsprechenden Pixel im Bild zum Zeitpunkt t+t vermerkt. Das Vektorfeld beschreibt also, wie man das Bild zum Zeitpunkt t verändern muss um das Bild zum Zeitpunkt t + t zu erhalten.

119

5 Statistisches Modell für Oberﬂächennormalen

Unterschied zwischen optischem Fluss und Bewegungsfeld

Ein optischer Fluss und somit das Verschiebungsfeld unterscheidet sich von einem Bewegungsfeld (engl. motion ﬁeld). Ein Bewegungsfeld gibt die tatsächliche Bewegung der Objekte im Bild an und lässt sich nicht direkt aus einer Bildfolge ableiten. Wie in Abbildung 5.25 zu sehen, gleicht der optische Fluss bei einer um die eigene Achse rotierenden Spirale nicht dem Bewegungsfeld. Der Grund hierfür

Abbildung 5.25: Wird eine Spirale rotiert, repräsentiert ein Bewegungsfeld die tatsächliche

Bewegung. Die sichtbare Bewegung, welche der optische Fluss darstellt, ﬁndet

jedoch nach oben statt. Bild angelehnt an: [CS]

liegt in der Berechnung der Verschiebungsvektoren, die sich nur an den Helligkeitswerten im Bild orientieren. Die Verschiebungsvektoren beschreiben also nur die optische Bewegung im Bild. Stellt man sich eine rotierende Spirale vor, so bewegen sich die Streifen nach oben. Die eigentliche Bewegung ﬁndet jedoch in Richtung der Rotation statt. In Abbildung 5.25 entspricht dies einer tatsächlichen Bewegung nach rechts.

Diﬀerentielle Ermittlung von Verschiebungsvektoren

Ausgangspunkt für die Berechnung der Verschiebungsvektoren ist eine Diﬀerenzfunktion d(x, y). Der Helligkeitsunterschied d(x, y) zwischen zwei Bildpunkten I(x, y, t) und I(x, y, t + t) lässt sich folgendermaßen beschreiben:

d(x, y) = I(x + v x t, y + v y t, t + t) − I(x, y, t).

120

Durch die Geschwindigkeit (v x , v y ) ^T abhängig vom Zeitschritt t wird die Ver- des Bildpunktes beachtet. Der Helligkeitswert von Bildpunkt (x, y) zum Zeitpunkt t beﬁndet sich also zum Zeitpunkt t + t am Ort (x + v x t, y + v y t).

Die Helligkeitswerte der Bilder können sich zwischen zwei Zeitschritten ändern. Diﬀerentielle Verfahren zur Berechnung des optischen Flusses gehen davon aus, dass diese Änderungen ausschließlich durch die Relativbewegung zwischen der Kamera und der betrachteten Szene zustande kommt. Es wird angenommen, dass die Szene für jedes Bild exakt gleich beleuchtet ist. Man spricht hierbei von einer Helligkeitskonstanz. Der optische Fluss ist somit ausschließlich durch die kontinuierliche Bewegung der Bildpunkte mit gleichen Helligkeitswerten bestimmt. Die Diﬀerenz d(x, y) der beiden Pixel muss also Null sein, sodass die folgende Bedingung erfüllt ist:

0 = I(x + v x t, y + v y t, t + t) − I(x, y, t). (5.17)

Gilt Gleichung (5.17), ist die Helligkeitskonstanz erfüllt. Sie wird im Folgenden als Bedingung angenommen.

In Bildfolgen sind die Unterschiede zwischen den Bildern meist nur minimal. Es wird angenommen, dass ein Pixel sich zwischen den Bildern nur leicht verschiebt. Den Ausdruck I(x + v x t, y + v y t, t + t) aus Gleichung (5.17) kann man unter dieser Annahme durch eine Taylorreihenentwicklung annähern. Setzt man also anstatt I(x + v x t, y + v y t, t + t) die Annäherung ein, erhält man:

Dabei sind in Γ ⁽²⁾ die Glieder der Taylorreihenentwicklung mit Ordnung ≥ 2

zusammengefasst. Aus dieser Gleichung lässt sich die die sogenannte Helligkeitskonstanzgleichung (engl. Optical Flow Constraint Equation) herleiten. Es wird angenommen, dass die Annäherung der Taylorreihe nach dem ersten Glied ausreicht. Die restlichen Glieder kann man vernachlässigen und die Helligkeitskonstanzglei-

121

5 Statistisches Modell für Oberﬂächennormalen

chung ergibt somit

Die Ableitungen Eine Möglichkeit die Ableitungen in [HS81] zu ﬁnden.

Durch Umformung der Helligkeitskonstanzgleichung (5.19) erhält man T

Durch diese Darstellung erkennt man, dass alle Verschiebungsvektoren, welche die Helligkeitskonstanzgleichung erfüllen, auf einer Geraden orthogonal zum Gradientenvektor liegen. Diese Gerade beﬁndet sich in dem durch v x und v y aufgespannten

^{∂I ∂I} Geschwindigkeitsraum. Der Gradientenvektor setzt sich aus ∂x und ∂y zusammen.

In Abbildung 5.26 ist dies nochmals veranschaulicht. Die Helligkeitskonstanzglei-

Abbildung Die Verschiebungsvektoren, welche die Helligkeitskonstanzgleichung er-

chung bedingt, dass die Vektoren des optischen Flusses v x , v y auf der Helligkeitskonstanzline liegen müssen. Da der Verschiebungsvektor aus zwei Unbekannten besteht, reicht Gleichung (5.19) nicht aus um ihn zu bestimmen. Nur wenn einer der Gradienten Null ist, lässt sich die Gleichung eindeutig lösen. Die nicht eindeutige Lösbarkeit der Helligkeitskonstanzgleichung wird als Aperturproblem oder Blendeproblem bezeichnet.

122

Schwächen des Verfahrens

Das Aperturproblem ist in Abbildung 5.27 dargestellt. Es zeigt eine Kante, welche

(a) (b) (c)

Abbildung 5.27: Da nicht das komplette Bild (a) betrachtet wird, sondern nur ein Ausschnitt

(b) des Bildes, entsteht das Aperturproblem. Obwohl p1 der richtige Punkt

wäre, wird p2 als korrespondierender Punkt gefunden.

sich ein Stück nach rechts und ein Stück nach oben bewegt. Im optimalen Fall beschreibt ein für diese Kante bestimmter Verschiebungsvektor genau diese Bewegung. Die menschliche Wahrnehmung verarbeitet das komplette Bild und kann ohne Weiteres feststellen, dass der zu p 0 zugehörige Bildpunkt p 1 sein muss. Die Idee des optischen Flusses basiert auf dem Vergleich von Helligkeitswerten. Daher wird der jeweils nächstliegende Bildpunkt mit gleicher Helligkeit gesucht. Der Helligkeitswert von p 2 entspricht dem von p 0 und liegt am nächsten. Daher wird dieser als korrespondierender Punkt gefunden und die vertikale Verschiebung der Kante wird nicht erkannt.

Neben dem Aperturproblem gibt es noch weitere Umstände, welche die Berechnung des optischen Flusses einschränken. Im Folgenden werden zwei Beispiele gezeigt, in denen die Verschiebungsvektoren nicht korrekt berechnet werden können. In [HS81] ist gezeigt, dass für eine rotierende Lambertsche Kugel mit einer fest positionierten Lichtquelle keine Bewegung sichtbar ist. In Abbildug 5.28 ist das resultierende Vektorfeld der Kugel zu sehen, welches keine Verschiebungen beinhaltet. Rotiert man stattdessen die Lichtquelle um eine sich nicht bewegende Lambertsche Kugel, bewegt sich der Reﬂektionskegel der Kugel. Das zugehörige Vektorfeld beinhaltet nun Bewegungen, die in der Szene nicht vorhanden waren. Es ist für die Berechnung also äußerst wichtig, dass die Helligkeitskonstanz erfüllt ist.

Die Ergebnisse hängen stark von den Helligkeitsmustern und Strukturen der im Bild vorhandenen Objekte ab. Der optische Fluss kann aufgrund des Apertur-

123

5 Statistisches Modell für Oberﬂächennormalen

Abbildung 5.28: Da sich die Helligkeitswerte im linken Bild bei der Kugelrotation nicht ver- wird keine Bewegung erkannt. Im rechten Bild verändern sich die

124

problems nur dann genau bestimmt werden, wenn die Objektbewegung im Bild

∂I ∂I

parallel zu einem der Helligkeitsgradienten ∂x oder ∂y verläuft.

Daraus lässt sich schließen, dass der optische Fluss die lokal sichtbare Richtungsänderungen und Geschwindigkeiten der Helligkeitsmuster von Bildfolgen beschreibt. Der optische Fluss entspricht nur dann dem tatsächlichen Bewegungsfeld, wenn die Objekte genügend strukturiert sind und das Aperturproblem nicht auftritt. Deshalb wird der optische Fluss oft nur als Annäherung an das tatsächliche Bewegungsfeld betrachtet.

5.4.2 Hinzuziehen von Nachbarschaften

Um das Aperturproblem zu beheben wird in [LK81] die Helligkeitskonstanzgleichung um eine Nachbarschaft für die Berechnung der Verschiebungsvektoren erweitert. Es wird angenommen, dass ein Vektorfeld lokal betrachtet glatt ist. Dies bedeutet, dass alle Verschiebungsvektorn v(x, y) der Nachbarschaft identisch sind. Die Größe der betrachteten Nachbarschaft wird durch die Region R deﬁniert. Statt einer einzelnen Helligkeitskonstanzgleichung sind nun R×R Gleichungen gegeben. In dieser Arbeit wird R = 5 gesetzt, woraus sich 25 Gleichungen für jeden Bildpunkt ergeben: ⎤ ⎡ ⎤ ⎡

⎢ ⎢ ⎢ ⎢ ⎣ t

Bis auf den Verschiebungsvektor v(x, y), sind alle Komponenten der Gleichung bekannt. Das Gleichungssystem besitzt somit mehr Gleichungen als Unbekannte und ist daher überbestimmt. Erweitert man die Helligkeitkonstanzgleichung (5.19) um ihre Nachbarschaften, erhält man die Fehlergleichung: ∂I(x,y) 2 → min .

Um das Gleichungssystem (5.20) zu lösen, minimiert man die Fehlergleichung (5.21). Auf diese Weise lässt sich die Verschiebung v(x, y) ermitteln. Ein Minimum der Fehlerfunktion E kann man bestimmen, indem man die partiellen Ableitungen

125

5 Statistisches Modell für Oberﬂächennormalen

∂ vx E und ∂ vy E Null setzt. ∂I(x,y) ∂I(x, y)

und ∂I(x,y) ∂I(x, y)

Durch Ableiten der Fehlerfunktion aus Gleichung (5.21) nach v x , v y erhält man das lineare Gleichungssystem Wv = b, (5.22)

wobei

und

gilt. In W werden die Gradienten der x- und y-Richtung quadriert und über die Nachbarschaften aufsummiert. Daher nennt man die symmetrische Matrix W auch den mittleren quadratischen Gradient eines Bildpunktes I(x, y).

Die Matrix W ist eine symmetrische 2 × 2-Matrix. Ihre Spalten deﬁnieren ein

^T gilt. Der Vektor a 2 wird ana- ∂ x I ² , [a 1 , a 2 ]-System, wobei a 1 = ∂ x I · ∂ y I

log gebildet. Sollten diese beiden Vektoren linear unabhängig voneinander sein, spricht man von einer Matrix mit vollem Rang. Bei einer 2 × 2-Matrix ist dies der Fall, wenn Rang(W) = 2 ist. Das bedeutet, dass der Rang einer Matrix der Anzahl der linear unabhängigen Spaltenvektoren entspricht. Besitzt W vollen Rang, lässt sich die Matrix invertieren und somit das lineare Gleichungssystem (5.22)

lösen. Hierfür wird W ⁻¹ mit Gleichung (5.22) multipliziert.

Da WW ⁻¹ nach [FH01] der Einheitsmatrix entspricht, folgt daraus:

⁻¹ v = W b. (5.25)

Ist einer der Eigenwerte einer 2 × 2-Matrix gleich Null, so besitzt diese Matrix den Rang 1. Ist dies der Fall, besteht das Aperturproblem auch in der Region R.

126

Dies liegt daran, dass die Gradienten ∇I(x, y) mit x, y ∈ R linear abhängig sind.

Eine 2 × 2-Matrix besitzt den Rang Null, wenn beide Eigenwerte Null sind. Dies geschieht zum Beispiel in homogen Gesichtsbereichen, welche keine Struktur besitzen. In dem betrachteten Bereich ist keine Verschiebung feststellbar. Es kann zum Einen sein, dass gar keine Bewegung für den betrachteten Bildpunkt stattgefunden hat. Zum Anderen ist es möglich, dass die Nachbarschaft des Bildpunktes nicht genügend struktiert ist um die Verschiebung zu erkennen. Dies ist in Abbildung 5.29 verdeutlicht. Da keine Verschiebung erkannt wurde, erhalten

Abbildung 5.29: In Beispiel (a) hat sich im Bild nur das Rechteck bewegt. Für den roten Punkt

hat keine Bewegung stattgefunden. In Beispiel (b) hat sich die betrachtete

die Komponenten v x , v y des Verschiebungsvektors den Wert Null.

In beiden Fällen ist W singulär. Daher kann für Gesichter nicht davon ausgegangen werden, dass W immer invertierbar ist. Auch wenn W keinen vollen Rang besitzt, kann man mit der Methode der kleinsten Fehlerquadrate [FP03] eine Lösung für Gleichung (5.22) ﬁnden. Hierbei wird ein Vektor ¯ v gesucht, welcher

den Ausdruck b − W¯ v bezüglich der euklidischen Norm minimiert. Hat W vollen Rang, so ist die Lösung von Gleichung (5.25) dieselbe wie bei der Methode der kleinsten Fehlerquadrate. Es existiert also stets eine Lösung für Gleichung (5.22). Formal bedeutet dies:

² → min .

Wv − b

Mit einer Singulärwertzerlegung [PTVF92] lässt sich eine Lösung für v x und v ^y ermitteln.

Das Verfahren aus [LK81] beschreibt die Verschiebung von jedem Bildpunkt eines Bildes zum nächstliegenden Bildpunkt des darauﬀolgenden Bildes. Es kommt

127

5 Statistisches Modell für Oberﬂächennormalen

häuﬁg vor, dass Bilder sich wiederholende Strukturen enthalten, wie in Abbildung 5.30 dargestellt. In diesem Fall werden Bildpunkte in Korrespondenz gebracht, welche nicht zusammen gehören. Ein weiteres Problem weisen große Be-

Abbildung Im

Beispiel (b) ist die Bewegung zu groß und wird nicht erkannt.

wegungen auf. Diese werden nicht erkannt, wenn die Nachbarschaften zu klein ist und es kommt zu Fehlern bei der Korrespondenzbestimmung.

5.4.3 Bildpaare

Das bisher beschriebene Vektorfeld v beschreibt die Verschiebung zwischen zwei Bildern in einer fortlaufenden Bildfolge. Ziel ist es jedoch die Korrespondenz zwischen verschiedenen Gesichtsbildern zu ermitteln. Wie in Abschnitt 5.4.1 gezeigt, ähneln sich zwei Bilder in einer Bildfolge stark. Gesichter haben hingegen unterschiedliche Größen und die Anordnung von Mund, Nase und Augen weichen von Gesicht zu Gesicht voneinander ab. Faktoren wie die Beleuchtung bei der Aufnahme erschweren die Korrespondenzbestimmung.

Um den Unterschied zwischen der Korrespondenzbestimmung für Bildfolgen und Bildpaaren in den nächsten Schritten zu verdeutlichen, werden einige bisher verwendeten Bezeichnungen angepasst. Anstatt von einer Bildfolge I(x, y, t) mit fortlaufendem t, wird nun von einem Bildpaar I 1 und I 2 gesprochen. Für dieses Bildpaar ist das Vektorfeld s gesucht. x(x, y)

Das Feld s entspricht dem bisher verwendeten Vektorfeld v. Dieses beinhaltet

128

die Verschiebungsvektoren zwischen den korrespondierenden Punkten I 1 (x, y) und I 2 (x+x(x, y), y+y(x, y)). Durch diese Gegebenheiten kann die Gleichung (5.17) zu

I 1 (x, y) = I 2 (x + x(x, y), y + y(x, y)) (5.26)

umformuliert werden, sodass sie nun für Bildpaare gilt. Die Bilder aus der Bildfolge lassen sich mit einem Bildpaar formal gleich behandeln, indem man I 1 (x, y) = I(x, y, t) und I 2 (x, y) = I(x, y, t + t) setzt. Anders ausgedrückt geht man nun davon aus, dass das Bild I 1 dem ersten Bild und Bild I 2 dem zweiten Bild in einer Bildfolge entspricht. Die zeitliche Ableitung ∂ t I wird durch die Diﬀerenz der Helligkeitswerte eines Bildpaares angenähert:

1 ∂ t I ≈ (I 2 (x, y) − I 1 (x, y)).

t

Bei Bildpaaren existiert kein tatsächlicher zeitlicher Abstand, sodass t = 1 ist. Nach [BV03] wird die Ableitung ∂ y I analog zu ∂ x I gebildet:

4

Aus Gründen der Symmetrie, wie in Abschnitt 3.2.1 beschrieben, wird mit einer symmetrischen Diﬀerenz gearbeitet. Es handelt sich hierbei jedoch nicht nur um ein Bild, sondern um ein Bildpaar von welchem die Ableitung gebildet werden soll. In jedem Bild wird die symmetrischen Diﬀerenz ermittelt und anschließend

1 2 gewichtet. jede Ableitung eines Bildes mit

Ein wichtiger Unterschied zwischen einer Bildfolge und einem Bildpaar mit verschiedenen Gesichtern ist, dass sich die globale Helligkeit zwischen den Gesichtern stark unterscheiden kann. Da die Korrespondenzbestimmung auf der Helligkeitskonstanz basiert, könnte man annehmen, dass die Ergebnisse der Korrespondenzberechnung ungenügend sind. Dies ist jedoch nicht der Fall, denn die Helligkeitskonstanz muss nur innerhalb eines Bildes gelten. Es ist also wichtig, dass die globale Helligkeit für ein einzelnes Bild konstant ist. Gradienten sind nicht von einer globalen Helligkeit abhängig. Da diese als Rechengrundlage für die Verschiebungsvektoren dienen, sind Unterschiede der globalen Helligkeit nicht von Bedeutung. Abbildung 5.31 verdeutlicht diesen Sachverhalt. Der Ausschnitt zeigt den Über-

129

5 Statistisches Modell für Oberﬂächennormalen

Abbildung 5.31: Es sind zwei Ausschnitte von unterschiedlichen Gesichtern dargestellt. Es

handelt sich hierbei um die rechte Augenbraue. Ein Gradient verläuft immer

gang von Haut zu der Augenbraue in zwei verschiedenen Gesichtern. Der Gradient verläuft bei beiden Bilder in die selbe Richtung, weil die Augenbrauen in beiden Bildern dunkler sind als die Haut. Daher ist das bisher vorgestellte Verfahren auch für Bildpaare I 1 , I 2 geeignet.

5.4.4 Grob-zu-fein-Strategie

Unterschiede zwischen Bildpaaren von Gesichtern können relativ groß sein. Daher kann der in [LK81] beschriebene Algorithmus Probleme haben, die richtigen Korrespondenzen zu ﬁnden. Um dieses Problem zu lösen wird eine sogenannte grob-zu-fein-Strategie [BAHH92] verwendet. Dazu wird eine Pyramide mit einer Reihe von Bildern in unterschiedlichen Auﬂösungsstufen gebildet. Beispiele für solche Auﬂösungspyramiden sind die Gauß- und die Laplacepyramide [BA83].

Im Folgenden werden zunächst die beiden Pyramidenformen erläutert. Der darauf folgende Abschnitt befasst sich mit der sogenannten Rückwärts-Warp-Operation, welche für die grob-zu-fein-Strategie notwendig ist. Abschließend wird gezeigt, wie eine solche Auﬂösungspyramide in [BAHH92] verwendet wird um Korrespondenzen zwischen Bildpaaren zu bestimmen.

Gauß- und Laplacepyramide

Eine Gaußpyramide besteht aus M Stufen wobei im Folgenden die unterste Stufe mit G 0 notiert wird. Die restlichen Stufen sind mit abnehmender Auﬂösung mit

130

G 1 , . . . , G M −1 durchnummeriert. Gebildet werden diese aus einem Eingangsbild I, welches eine Auﬂösung von X res × Y res mit X res = Y res besitzt.

Die unterste Stufe der Gaußpyramide entspricht dem Eingangsbild, sodass G 0 = I gilt. Um nun die nächst höhere Stufe zu berechnen, wird G 0 mit einer Gaußmaske geglättet. Eine Beschreibung einer solchen Glättung ist in Abschnit 3.2.3 zu ﬁnden. Anschließend wird die Auﬂösung reduziert indem nur jeder zweite Bildpunkt abgetastet wird. Die Glättung ist wichtig um sogenannte Alias-Eﬀekten zu verhindern die sonst entstehen können. Der Alias-Eﬀekt wird häuﬁg auch als Treppenstufen-Eﬀekt bezeichnet. Dieser Eﬀekt kann zu Kanten führen, welche nicht vorhandenen Strukturen im Bild vortäuschen. Bei der Berechnung des optischen Flusses würden solche Kanten zu Fehlern bei der Korrespondenzbestimmung führen. Eine nähere Betrachtung des Alias-Eﬀekt ist in [FP03] zu ﬁnden. Ein Bild wird vor jeder Reduktion geglättet. Das Glätten und das Unterabtasten kann man zu einem Schritt zusammenfassen, wobei man diesen Vorgang als reduce-Operation bezeichnet. Der Aufbau der Gaußpyramide lässt sich formal wie folgt beschreiben:

Deﬁniert man nun eine Filtermaske F mit der Größe 5 × 5 für die Glättung, lässt sich die Pyramide durch

ermitteln. Um eine Stufe G m der Pyramide zu erhalten, glättet man nur jeden zweiten Bildpunkt, welchen man für das neue Bild der nächsten Stufe G m verwendet. Dadurch wird die Auﬂösung des Bildes halbiert. Je nach Größe der Filtermaske müssen die Ränder des Bildes, wie in Abschnitt 3.2.3 beschrieben, behandelt werden. Als Ergebnis resultiert nun eine Gaußpyramide, welche in Abbildung 5.32 zu sehen ist.

131

5 Statistisches Modell für Oberﬂächennormalen

Eine Laplacepyramide ergibt sich aus den Diﬀerenzen zweier Gaußpyramidenstufen. Da die Bilder der Gaußpyramide nicht die selben Auﬂösungen besitzen, lässt sich die Diﬀerenz nicht direkt bilden. Möchte man also G 0 und G 1 miteinander verrechnen, muss G 1 auf die Auﬂösung von G 0 expandiert werden. Hier ﬁndet die expand-Operation Anwendung. Das Ausgangsbild wird zuächst überabgetastet und anschließend das resultierende Bild mit einer Gaußmaske glättet. Dieser Zusammenhang kann folgendermaßen formuliert werden:

G ex m = M − 1, . . . , 1. m = expand(G m+1 ) mit

Hierbei beschreibt G ex m das expandierte Bild der Stufe m. Die Auﬂösung von G ex

m

entspricht daher der Auﬂösung von G m−1 . Für die niedrigste Pyramidenstufe G ⁰ existiert kein expandiertes Bild. Unter Verwendung von F kann das Bilden der expandierten Gaußpyramidenstufen wie folgt zusammengefasst werden: 2 2

132

Auch hier müssen die Randbereiche beachtet und geeignet verarbeitet werden. Die Darstellung in Abbildung 5.33 entspricht dem Ergebnis einer expand-Operation.

schen zwei Gaußpyramidenstufen zu berechnen. Das Resultat ist eine Stufe der Laplacepyramide. In Abbildung 5.34 ist links nochmals die Gausspyramide und rechts die aus den Diﬀerenzen entstandene Laplacepyramide zu sehen. Formal ausgedrückt ergibt sich die Laplacepyramide durch:

L m = G m − G ex m = M − 2, . . . , 0. mit m+1

Sie beinhaltet die Bildinformationen, welche durch den reduce-Vorgang verloren gegangen sind. Um ein Bild der Laplacepyramide zu erhalten, muss man also

• die Diﬀerenz aus diesen beiden Bildern berechnen.

Dies sind drei aufwändige Schritte, welche nur notwendig sind, wenn man neben der Laplacepyramide auch die Gaußpyramide benötigt. Das Reduzieren, Expandieren und die Diﬀerenzbildung sind lineare Verfahren. Möchte man nur eine Laplacepyramide bilden, kann man die genannten Schritte zu einer einzigen Faltung

133

5 Statistisches Modell für Oberﬂächennormalen

Abbildung 5.34: Durch Diﬀerenzbildung zweier Gaußpyramidenstufen entsteht die Laplace-

zusammenziehen.

Der Diﬀerence-of-Gaussian, welcher meist einfach nur als DoG bezeichnet wird, ist ein Filter, welcher für die Diﬀerenzbildung verwendet werden kann. Er beschreibt die Diﬀerenz zwischen zwei mit einem Gaußﬁlter geglätteten Bilder. Die Filterkerne F 1 und F 2 besitzten unterschiedliche Größen. Formal kann man also schreiben:

L = I · F 1 − I · F 2 = I · (F 1 − F 2 ).

In dieser Formel beschreibt F 1 − F 2 die Maske für den DoG-Filter, welcher im Folgenden mit DoG(u, v) bezeichnet wird. Wie eine solche Filtermaske entsteht, lässt sich anhand des Plots aus Abbildung 5.35 erklären. Die Graphen 1 und 2 beschreiben jeweils eine Gaußglättung, wobei sie mit unterschiedlichen Standardabweichungen σ 1 , σ 2 berechnet wurden (vergleiche Abschnitt 3.2.3). Bildet man die Diﬀerenz dieser Filterkerne, erhält man die DoG-Maske. Sie ist wie folgt deﬁniert:

u ² + v ² u ² + v 2

^{1 2} 134

Abbildung 5.35: Aus der Diﬀerenz zweier Gaußglättungen lässt sich die DoG-Filtermaske er-

Rückwärts-Warp-Operation

Die Idee eines Warps ist es, die Helligkeitswerte aus Bild I 2 so zu verschieben, dass es mit Bild I 1 deckungsgleich ist. Identische Strukturen der Bilder beﬁnden sich somit an den selben (x, y) Positionen. Beim Warping wird zwischen Vorwärts- und Rückwärts-Warp unterschieden. In dieser Arbeit ist der Rückwärts-Warp relevant und wird im Folgenden erläutert.

2 die Bildpunkte mit den selben Positionen der Bildpunkte aus I 1

betrachtet. Weiterhin wird das Vektorfeld s = (x, y) ^T benötigt, welches für

jeden Bildpunkt aus I 1 die Verschiebung zum korrespondierenden Bildpunkt in I 2 beinhaltet. Die Helligkeitswerte dieser korrespondierenden Bildpunkte werden 2 eingetragen. Dieser Vorgang lässt sich wie folgt formulieren:

2 (x, y) = I 2 (x + x(x, y), y + y(x, y)). I

Die Warp-Operation ist in Abbildung 5.36 verdeutlicht.

5 Statistisches Modell für Oberﬂächennormalen

Abbildung 5.36: Das Vektorfeld s beschreibt den optischen Fluss zwischen I1 und I2. Es drückt

daher aus, wie I2 verändert werden muss, damit sich seine Strukturen mit

zeigen somit auf keinen eindeutigen Bildpunkt in I 2 . Aus diesem Grund ist es notwendig zwischen den vier umliegenden Bildpunkten bilinear zu interpolieren. Dafür werden ihre Helligkeitswerte C 11 , C 21 , C 12 und C 22 gewichtet und zu C(x, y) aufsummiert. Für die Interpolation gilt dann:

(x 2 − x)(y 2 − y) (x − x 1 )(y 2 − y)

Die Bezeichnungen in Abbildung 5.37 stimmen denen aus Gleichung (5.27) überein. Dies ist der allgemeine Fall der bilinearen Interpolation für Helligkeitswerte. Der Abstand zwischen den Bildpunkten beträgt stets 1 Pixel. Daher kann die bilinearen Interpolation aus Gleichung (5.27) zu

C(x, y) = C 11 (1 − x)(1 − y) + C 21 x(1 − y) + C 12 (1 − x)y + C 22 xy

vereinfacht werden.

Verwenden einer Auﬂösungspyramide zur Korrespondenzbestimmung

Das in [BAHH92] beschriebene Verfahren kombiniert den Algorithmus aus [LK81] mit einer grob-zu-fein-Strategie. Hierfür wird eine Auﬂösungspyramide verwendet, welche es ermöglicht auch große Verschiebungen zwischen Bildpunkten zu erkennen.

136

Abbildung 5.37: Bei der bilinearen Interpolation wird zwischen den Helligkeitswerten der um- Eckpunkten des betrachteten Punkts C(x, y) ein gewichtetes Mittel

pyramide L 1m und L 2m mit M Stufen aufgebaut. Neben den Pyramidenbildern werden auch die Eingangsbilder I 1m und I 2m auf jeder Auﬂösungsstufe benötigt. Als Basis für die Korrespondenzbestimmung ist also Folgendes vorhanden:

m = 0, . . . , M − 1,

Für eine Pyramide mit M = 4 Stufen ist das Prinzip in Abbildung 5.38 dargestellt. Auf der kleinsten Auﬂösungsstufe m = M − 1 wird nun der optische Fluss unter Berücksichtigung von Nachbarschaften berechnet, wie in Abschnitt 5.4.2 beschrieben. Das resultierende Vektorfeld beschreibt die Verschiebungen jedes Bildpunktes von Bild L ² (M −1) zu Bild L ¹ (M −1) . Das Feld dient als Startwert für die nächst niedrigere Pyramidenstufe M − 2. Ein Problem liegt darin, dass es eine zu geringe Auﬂösung für die nächste Stufe hat. Daher muss die Auﬂösung des Vektorfelds verdoppelt werden. Ähnlich wie beim Überabtasten eines Bildes (siehe Abschnitt 5.4.4) wird jeder Verschiebungsvektor viermal verwendet. Für das Vektorfeld wird hierbei keine Glättung angewendet. Damit die Länge der Verschiebungen erhalten bleiben, müssen sie beim Wechsel in eine höhere Auﬂösungsstufe mit dem Faktor 2 skaliert werden. Dieses Prinzip ist in Abbildung 5.39 dargestellt. Nun ist es möglich das berechnete Vektorfeld auf die nächst niedrigere Pyramidenstufe des zweiten Bildes L ² (M −2) anzuwenden. Dabei wird L ² (M −2) durch eine

137

5 Statistisches Modell für Oberﬂächennormalen

Abbildung 5.38: Als Basis zur Berechnung dient das Eingangsbild in verschiedenen Auﬂö-

I1 m , m und L1 m , m .

Abbildung 5.39: Zunächst wird das Vektorfeld überabgetastet und dann mit dem Faktor 2

skaliert.

138

Rückwärts-Warp-Operation an L ¹ (M −2) angeglichen. Dieser Vorgang ist in Abbildung 5.40 dargestellt. In gleicher Weise wird nun auf jeder Auﬂösungsstufe der

Abbildung 5.40: Mit dem ermittelten optischen Fluss kann das Bild I2 durch einen Rückwärts-

I1 angeglichen

optische Fluss berechnet und anschließend das Bild der nächst niedrigeren Pyramidenstufe gewarpt. Dies wird solange fortgesetzt, bis die höchste Auﬂösungsstufe und somit die niedrigste Pyramidenstufe m = 0 erreicht ist.

In der niedrigsten Auﬂösungsstufe der Pyramide können sehr große Verschiebungen zwischen den Bildern erkannt werden. Mit steigender Auﬂösung lassen sich immer kleinere Verschiebungen erkennen. Daher ist es möglich, das Vektorfeld auf jeder neuen Stufe zu verfeinern. Das Verfeinern geschieht, indem man das überabgetastete Vektorfeld der vorherigen Stufe auf das Feld der aktuellen Stufe addiert. In Abbildung 5.41 ist dieser Vorgang veranschaulicht. Mit der beschriebenen grob-zu-fein-Strategie können nun auch große Verschiebungen zwischen zwei Gesichtsbildern erkannt werden.

139

5 Statistisches Modell für Oberﬂächennormalen

M = 3 m = 2

m = 1

m = 0

Abbildung 5.41: Bei einer grob-zu-fein-Strategie wird das Verschiebungsfeld mit jeder Stufe

verfeinert.

140

5.4.5 Korrespondenzbestimmung zwischen 3D Scans

Das bisher beschriebene Verfahren ist zur Korrespondenzbestimmung zwischen zwei Bildern geeignet. Dabei ist für jede (x, y)-Position in einem Bild I jeweils ein Helligkeitswert vorhanden. Bei den in dieser Arbeit verwendeten Scans existiert für jeden Punkt ein Farbwert RGB und ein Radiuswert r.

Betrachtet man die Farbkanäle R, G und B getrennt, erhält man vier Texturen wie in Abbildung 5.42 dargestellt. Für die Korrespondenzbestimmung zwischen

Abbildung 5.42: Ein 3D-Scan kann durch vier Texturen dargestellt werden. Dabei werden die

drei Farbkanäle R, G und B getrennt betrachtet.

zwei Laserscans nach [Bla00] werden im Folgenden alle vier Texturen berücksichtigt. Die Berechnung des optischen Flusses ﬁndet daher nicht mehr zwischen zwei einzelnen Bildern, sondern zwischen zwei vierdimensionalen Textur-Tupeln statt. Ein Bildpunkt I(x, y) wird nun durch einen vierdimensionalen Vektor repräsen- ⎛ ⎞ tiert:

Bei dem Radiuswert r hängt der Wertebereich von dem vorliegendem Laserscan ab, sodass dieser Bereich variieren kann. Aus diesem Grund wird dieser Wertebereich formal mit r behandelt, welcher vom größten bis zum kleinsten Radiuswert des Scans reicht. Damit die Farbwerte und der Radiuswert im gleichen Maß zur Berechnung des optischen Flusses beitragen, werden sie normiert. Die Farbwerte

141

5 Statistisches Modell für Oberﬂächennormalen

werden mit den Faktoren w R , w G , w B normiert, für welche gelten:

1

w R = w G = w B = 255 2 .

Der Radiuswert wird ebenfalls normiert, indem er durch seinen quadrierten Wer- (r) ² geteilt wird:

Für die Norm eines Bildpunktes I(x, y) gilt:

w r r(x, y) ² + w R R(x, y) ² + w G G(x, y) ² + w B B(x, y) ² . I(x, y) = (5.28)

Man kann den Radiuswert genauso stark in die Berechnug des Verschiebungsfeldes einﬂießen lassen wie alle Farbwerte zusammen. Dies ist möglich, indem man ihn mit dem Faktor 3 bei der Normierung gewichtet. Die Normierung des Radiuswerts lässt sich dann wie folgt deﬁnieren:

1 ² . w r = 3 · ( ) r

Da I(x, y) nun nicht mehr aus einem Helligkeitswert, sondern aus einem Vektor besteht, muss die Helligkeitskonstanzbedingung darauf angepasst werden. In Abschnitt 5.4.1 ist die Bedingung erfüllt, wenn Gleichung (5.17) gilt. Die Diﬀerenz zweier Helligkeitswerte beträgt dann Null. Bildet man die Diﬀerenz zwischen zwei Bildpunkten I 1 (x, y) und I 2 (x, y) von dreidimensionalen Laserscans, so erhält man einen Vektor I ^(I 2 ^−I 1 ) (x, y). Ob die Helligkeitskonstanzbedingung erfüllt ist, wird anhand der Länge des Vektors festgemacht. Wenn jede Vektorkomponente

(r(x, y), R(x, y), G(x, y), B(x, y)) ^T von I ^(I 2 ^−I 1 ) (x, y) gleich Null ist, so ist auch die

Länge des Vektors Null. Daraus ergibt sich, dass die Helligkeitskonstanzbedinung erfüllt ist, wenn 0 = I 2 (x + x, y + y) − I 1 (x, y)

gilt.

Auch die Fehlergleichung (5.21) muss auf ein vektorielles I erweitert werden.

Gesucht ist der Verschiebungsvektor s = (x, y) ^T , welcher die Länge des aus ∂I(x,y) ∂I(x,y) ∂I(x,y) ∂x x + ∂y y + resultierenden Vektors minimiert. Die Fehlerglei- ∂t

chung für einen Bildpunkt eines dreidimensionalen Laserscans kann unter Verwen-

142

dung der Nachbarschaft R somit als ∂I(x, y) ² ∂I(x, y) ∂I(x, y) x + y + → min E = (5.29)

∂x ∂y ∂t

x,y∈R

formuliert werden.

Durch Ableiten der Fehlerfunktion aus Gleichung (5.29) erhält man wie in Abschnitt 5.4.2 das lineare Gleichungssystem

Ws = b, (5.30)

wobei

∂ x I, ∂ t I und

gilt. Das in Matrix W enthaltene Skalarprodukt berechnen sich wie folgt:

∂ x I, ∂ y I = w r ∂ x r∂ y r + w R ∂ x R∂ y R + w G ∂ x G∂ y G + w B ∂ x B∂ y B. (5.31)

Die Skalarprodukte des Vektors b berechnen sich analog zu Gleichung (5.31). Wie sich die Ableitungen ∂ x I, ∂ y I und ∂ t I berechnen, ist in Abschnitt 5.4.3 beschrieben. Das Gleichungssystem (5.30) kann wie in Abschnitt 5.4.2 mit der Methode der kleinsten Fehlerquadrate [FP03] gelöst werden.

Durch Anpassen des Verfahrens auf ein vektorielles I(x, y) ist es nun möglich, die Korrespondenz zwischen zwei dreidimensionalen Laserscans zu bestimmen. Das Verfahren wird wiederum mit einer grob-zu-fein-Strategie kombiniert, sodass sich auch große Verschiebungen sicher erkennen lassen. Die dafür notwendigen Laplacepyramiden der Scans I 1 und I 2 bestehen in jeder Stufe aus vier Texturen. In Abbildung 5.43 sind diese Pyramiden zu sehen, wobei jede Pyramide aus fünf Stufen besteht.

143

5 Statistisches Modell für Oberﬂächennormalen

Abbildung 5.43: Zwei dreidimensionale Laserscans werden in vier Ausgangstexturen aufge- Daraus lassen sich die zugehörigen Laplacepyramiden bilden. Anhand

5.4.6 Glätten der Vektorfelder

Jedes Trainingsgesicht besitzt nun einen optischen Fluss, welcher es in Korrespondenz mit einem Referenzgesicht stellt. In Abbildung 5.44(a) ist jeder fünfte Verschiebungsvektor eines solchen optischen Flusses eingetragen. Wendet man den optischen Fluss in einem Rückwärts-Warp auf das zugrunde liegende RGB- Ausgangsbildan, erhält man das in Abbildung 5.44(c) dargestellte Bild. Das Gesicht besitzt keine glatte Oberﬂäche und feine Konturen wie Augenbrauen, Augen und Ohren besitzen keine klaren Kanten. Begründen lässt sich dies, indem man das Vektorfeld aus Abbildung 5.44(a) analysiert. In weniger strukturierten Gesichtspartien wie Wangen und Stirn verlaufen die Vektoren in keine eindeutige Richtung. Für solche Partien gibt es in kleinen Nachbarschaften nur wenige oder keine Anhaltspunkte für die Korrespondenzbestimmung. Bei der grob-zufein-Strategie können Verschiebungsvektoren daher für größere Auﬂösungsstufen nicht geeignet korrigiert und verfeinert werden. Die rechteckigen Blöcke entstehe durch das Überabtasten des Verschiebungsfelds auf jeder Auﬂösungsstufe der Pyramide.

Die Bedingung für zwei korrespondierende Bildpunkte besteht ausschließlich darin, dass sie den selben Farb- und Radiuswert besitzen. Ob es sich bei den durch das Verfahren gefundenen Korrespondenzen um tatsächlich identische Ober-

144

(a) Ungeglättetes Vektorfeld (b) Geglättetes Vektorfeld

(c) Warp-Ergebnis ohne Glättung (d) Warp-Ergebnis mit Glättung

Abbildung 5.44: Auswirkungen einer Glättung der Verschiebungsvektoren auf jeder Pyrami-

5 Statistisches Modell für Oberﬂächennormalen

ﬂächenpunkte der Gesichter handelt, sollte daher keine Rolle spielen. Möchte man die Bilder durch eine Warp-Operation aufeinander angleichen, triﬀt diese Annahme zu. Doch bei weiteren Verarbeitungsschritte, wie dem Ermitteln der Normalenrichtungen der Punkte, fallen diese Fehler ins Gewicht. Zwar passen ihre Farb-und Radiuswerte zueinander, jedoch triﬀt dies nicht auf ihre Normalenrichtungen zu. Aus diesem Grund ist es notwendig die Verschiebungsvektoren in Abhängigkeit zueinander zu setzten. Dazu kann ein Glättungsverfahren auf das Vektorfeld angewendet werden.

Glättungsverfahren

In [Bla00] ist ein Verfahren beschrieben, mit welchem die Verschiebungsvektoren in Abhängigkeit voneinander geglättet werden können. Dazu verbindet man sie durch eine Kopplung, welche in diesem Fall mit einem quadratischen Potential zwischen den vier Nachbarn jedes Vektors vergleichbar ist. Zusätzlich sind die Verschiebungsvektoren in strukturreichen Gesichtspartien durch ein weiteres Potential gekoppelt und somit stärker gewichtet. Die zusätzliche Kopplung ist darauf zurückzuführen, dass der Korrespondenzalgorithmus solche Partien gut erkennen und zuordnen kann. Die Richtungen von schwächer gewichteten Verschiebungsvektoren werden aufgrund der ersten Kopplung von benachbarten, stärker gewichteten Verschiebungsvektoren beeinﬂusst.

Eine Alternative zu dem beschriebenen Glättungsverfahren besteht in einer einfachen Glättung des Vektorfeldes. Auch hier werden die Nachbarn eines Verschiebungsvektor in Abhängigkeit zueinander gesetzt. Jedoch wird die Abhängigkeit nicht nur für die direkten vier Nachbarn deﬁniert. Es wird eine größere Region um den zu glättenden Bildpunkt betrachtet. Diese Erweiterung basiert auf einer Gaußglättung, welche in Abschnitt 3.2.3 beschrieben ist. Die Größe der Filtermaske ist bei dieser Glättung entscheidend. Zu kleine als auch zu große Filtermasken haben den Nachteil, dass sie die Vektoren entweder zu wenig oder zu stark glätten. In dieser Arbeit hat sich die Glättung mit einer 5×5-Filtermaske bewährt. Obwohl zuverlässige Korrespondenzen aus strukturreichen Gesichtspartien unnötigerweise geglättet werden und somit verloren gehen, liefert die Glättung sehr gute Ergebnisse. Die Glättung ist in den Abbildungen 5.44(b) und 5.44(d) nachvollziehbar. Auf Grund der guten Ergebnisse mit einer Gaußglättung ist auf eine Untersuchung des Glättungsverfahren aus [Bla00] verzichtet worden. Für den Korrespon-

146

denzalgorithmus zum Aufbau eines statistischen Modells wurde die beschriebene Gaußglättung integriert.

147

5 Statistisches Modell für Oberﬂächennormalen

5.5 Bestimmung von Normalenfeldern

An diesem Punkt ist die Korrespondenz zwischen den Trainingsgesichtern und einem Referenzgesicht bekannt. Zum Aufbau eines statistischen Modells müssen Normalenfelder dieser Gesichter vorhanden sein. Um solche Felder zu erhalten, werden die Oberﬂächennormalen der Trainingsgesichter zunächst aufeinander ausgerichtet. Nach der anschließenden Projektion der Gesichter auf eine Ebene ist es möglich, für jedes Trainingsgesicht ein Normalenfeld zu ermitteln.

5.5.1 Ausrichten der Trainingsdaten

Damit jedes Trainingsgesicht auf gleiche Weise ausgerichtet wird, muss ein Referenzgesicht als Vorlage dienen. Man wählt hierzu das selbe Referenzgesicht wie in Abschnitt 5.4, da für dieses bereits Verschiebungsfelder zu allen Trainingsgesichtern bestimmt wurden. Die Ausrichtung zweier Gesichter über ein Verschiebungsfeld lässt sich anhand eines Beispielgesichts aus den Trainingsdaten und dem Referenzgesicht erläutern. Abbildung 5.45 zeigt die beiden im Folgenden verwendeten Gesichter.

Abbildung 5.45: Zu sehen sind zwei Gesichtsmodelle, welche unterschiedliche Gesichtsformen

besitzen. Die Oberﬂächennormalen passen zu dem jeweiligen Gesicht.

Durch den optischen Fluss zwischen den beiden Gesichtern ist bekannt, welche

148

Punkte der Scans zusammen gehören. Die Punkte lassen sich in Geometriedaten

und Oberﬂächenormalen aufteilen. Man erhält für das Referenzgesicht M Ref den Geometrievektor M Ref Geo und den Oberﬂächennormalenvektor M Ref

Beispielgesicht M Bsp ergibt sich analog eine Aufteilung in M Bei dem Aufbau von M Bsp werden nur Punkte und Normalen beachtet, welche zu Punkten aus M Ref als korrespondierende Punkte gefunden wurden. Die Reihenfolge für die Vektoren ergibt sich aus M Ref , wobei jeder Vektor von M Ref

jeweils N Einträge besitzt. Das Prinzip ist in Abbildung 5.46 dargestellt. Durch

Abbildung 5.46: Die Geometrievektoren und Oberﬂächennormalenvektoren werden unter

Verwendung des Verschiebungsfeldes so aufgebaut, dass korrespondierende

Punkte und Normalen den selben Index erhalten.

die eins-zu-eins-Korrespondenz ist es nun möglich zwischen den Gesichtern linear zu interpolieren. Dieser Vorgang wird, wie in Abschnitt 5.2.2 erwähnt, als mor- bezeichnet. Bei einem Morph entsteht ein neues Gesicht M Neu , welches sich aus einer gewichteten Mischung von M Ref und M Bsp ergibt. Die Gewichtung erfolgt mit dem Faktor a ∈ [0, 1], welcher den Anteil von M Bsp in M Neu

ausdrückt. Ein Morph zwischen Referenz- und Beispielgesicht lässt sich als

M Neu = (1 − a) · M Ref + a · M Bsp , a ∈ [0, 1] (5.32)

formulieren.

Bei dem Morph aus Gleichung (5.32) werden alle Komponenten von M Ref und M Bsp beachtet. Ziel ist es jedoch, die Oberﬂächennormalen von M Bsp zu

149

5 Statistisches Modell für Oberﬂächennormalen

erhalten. Daher wird der Morph in

Bsp M Neu Geo = (1 − a 1 ) · M Ref Geo + a 1 · M , a 1 ∈ [0, 1]

Geo

und

Bsp M Neu Norm = (1 − a 2 ) · M Ref Norm + a 2 · M , a 2 ∈ [0, 1]

Norm

aufgeteilt. Nun kann die Geometrie getrennt von den Oberﬂächennormalen behandelt werden. Das neue Gesicht soll die Form des Referenzgesichts besitzen, sodass a 1 = 0 gesetzt wird. Die Oberﬂächennormalen sollen hingegen vom Beispielgesicht stammen. Somit gilt a 2 = 1. Durch dieses Vorgehen resultiert ein neues Gesicht

M Neu mit der Form von M Ref und den Oberﬂächennormalen von M Bsp . Das

Ergebnis für die beiden Gesichtsmodelle aus Abbildung 5.45 ist in Abbildung 5.47 zu sehen. Das ausgerichtete Beispielgesicht ist in Abbildung 5.47 im Vergleich zum Referenzgesicht dargestellt. Mit dem beschriebenen Morph lassen sich nun

Abbildung 5.47: Das neue Gesicht besitzt die Form des Referenzgesichts und die Oberﬂächen- des Beispielgesichts aus Abbildung 5.45.

alle Trainingsgesichter auf das Referenzgesicht ausrichten.

5.5.2 Ermitteln der Normalenfelder

Um aus den ausgerichteten Trainingsgesichtern Normalenfelder zu erhalten, projiziert man sie zunächst auf eine Ebene. Die Projektionsebene wird frontal vor

150

das Gesicht gelegt, wie in Abbildung 5.22 aus Abschnitt 5.3 dargestellt. In diesem Abschnitt wurde ebenfalls herausgestellt, dass eine orthogonale Projektion verwendet wird.

Ein Normalenfeld ist generell in ein gleichmäßiges Raster eingeordnet. Für die Normalen eines projizierten Gesichts triﬀt das nicht zu. Um die Gesichtspunkte in ein Raster einzuordnen ist es hilfreich, Informationen über die Entstehung der Daten heranzuziehen.

Aus Abschnitt 5.1.1 ist bekannt, dass der Abstand in y-Richtung zwischen zwei Punkten 0.615 mm beträgt. Der Abstand zwischen den Punkten in x-Richtung ist nicht genau bestimmbar und ist erfahrungsgemäß etwa doppelt so groß. In y- Richtungist somit eine feinere Auﬂösung vorhanden. Die Normalen sollten daher anhand der Abstände in y-Richtung rasterisiert werden. Man erhält Normalenfelder, wie in Abbildung 5.48 zu sehen.

(a) Referenzgesicht (b) Beispielgesicht

Abbildung 5.48: Die projizierten Gesichter weisen Lücken auf. Diese entstehen durch die un-

x- und y-Richtung bei

horizontalen Lücken behaftet. Um diese zu füllen, müssen an diesen Stellen zusätzliche Normalen deﬁniert werden. Da Gesichter eine weiche Oberﬂäche besitzen, lassen sich die fehlenden Normalen anhand ihrer Nachbarnormalen bestimmen.

151

5 Statistisches Modell für Oberﬂächennormalen

Jede fehlende Normale wird durch den Mittelwert der umliegenden Normalen ersetzt. Durch mehrmaliges Wiederholen des Füllprozesses können die Lücken komplett gefüllt werden. In Abbildung 5.49 sind die aufgefüllten Normalenfelder der Gesichter dargestellt.

(a) Referenzgesicht (b) Beispielgesicht

Abbildung 5.49: Die Lücken aus Abbildung 5.48(a) und 5.48(b) können durch Mitteln der

umliegenden Normalenrichtungen gefüllt werden.

152

5.6 Analysieren der Normalenfelder

An diesem Punkt liegt für jedes Trainingsgesicht ein auf das Referenzgesicht ausgerichtetes Normalenfeld vor. Die Aufgabe besteht nun darin, daraus das statistische Modell zu ermitteln, welches die wichtigsten Oberﬂächeneigenschaften der Gesichter beinhaltet. Zunächst werden zwei Varianten vorgestellt, wie sich ein mittleres Normalenfeld der Trainingsgesichter deﬁnieren lässt. Alle Gesichter werden daraufhin durch Projektion auf eine Ebene in einen linearen Raum abgebildet. Schließlich dient eine Hauptkomponentenanalyse zur Ermittlung der Eigenschaften der Gesichter. Die resultierenden Komponenten sind die Eigengesichter der Trainingsdaten und repräsentieren das statistische Modell für Oberﬂächennormalen.

5.6.1 Bestimmen eines mittleren Normalenfelds

Um den Mittelwert eines Normalenfelds zu ermitteln wurde in Abschnitt 5.1.5 die extrinsische und intrinsische Mittelwertbildung vorgestellt. In dieser Arbeit wurden beide Alternativen für Oberﬂächennormalen untersucht.

Die in Abschnitt 5.5.2 ermittelten Normalenfelder n k bestehen aus Einheitsnormalen. Im Folgenden wird die Einheitsnormale eines Bildpunkts (x, y) mit dem Index (i) identiﬁziert. Eine Normale bei Bildpunkt (i) im kten Trainingsgesicht wird durch den Vektor ⎛ ⎞

⎟

⎠

zusammengefasst. Korrespondierende Normalen sind über den Index (i) im Normalenfeld deﬁniert. Um die Richtungen der Einheitsnormalen zu analysieren, bietet die Darstellung als Punktmenge P (i) auf einer Einheitskugel eine geeignete Ausgangsituation. Diese Darstellung wurde bereits in Abschnitt 5.1.5 beschrieben. Für P (i) gilt in Kugelkoordinaten

P S (i) = {p ^S k (i) = (θ, α)|k = 1, . . . , K} ,

5 Statistisches Modell für Oberﬂächennormalen

während geographische Koordinaten als

P G (i) = {p ^G k (i) = (ϕ, λ)|k = 1, . . . , K}

notiert werden.

Für den extrinsischen Mittelwert μ Φ (i) ergibt sich analog zu Gleichung (5.14) folgende Berechnung:

^K

k=1

Da μ Φ (i) equivalent zu dem arithmetischen Mittel ist, wird μ Φ (i) = ¯ p G (i) gesetzt.

Dazu ermittelt man zunächst die mittlere Normale ¯ n(i): K

1

Um ¯ p G (i) zu erhalten, konvertiert man die kartesischen Koordinaten von ¯ n(i) in geographische Koordinaten.

Als Startschätzung für die Bestimmung des intrinsischen Mittelwerts μ(i) wird das extrinsische Mittel μ Φ (i) verwendet. Mit Algorithmus 5.1 wird diese Startschätzung iterativ an das intrinsische Mittel angenähert. Dazu wird in jeder Iteration j die aktuelle Schätzung μ (j) (i) mit

^K

k=1

aktualisiert.

5.6.2 Überführen in einen linearen Raum

Ein Ansatz um die Punktmengen P G zu analysieren besteht darin, Gesichtseigenschaften direkt auf der Einheitskugel zu ermitteln. In [FLPJ04] wird dieser Ansatz allgemein als Principal Geodesic Analysis (PGA) vorgestellt und in [Smi07] speziell für Gesichter vorgestellt. Sogenannte Geodäten beschreiben die Eigenschaften als Großkreise auf der Einheitskugel. Die PGA bildet somit eine Verallgemeinerung

154

der Hauptkomponentenanalyse für einen mehrdimensionalen Raum. In [FLPJ04] wird weiterhin gezeigt, wie eine Hauptkomponentenanalyse als gute Annäherung an die PGA verwendet werden kann. Voraussetzung dafür ist, dass die Punkte nah beieinander liegen. Um die Analyse durchführen zu können, müssen die Punkte zunächst in einen linearen Raum überführt werden. Da die Oberﬂächennormalen von Gesichtern ähnliche Richtungen besitzen, dient in dieser Arbeit eine Hauptkomponentenanalyse zur Bestimmung der Gesichtseigenschaften.

Damit die Abstände zwischen den Punkten erhalten bleiben, werden die Punktmengen P G mit der mittelabstandtreuen Azimutalprojektion aus Abschnitt 5.1.2 linearisiert. Die Projektion erfolgt für jede Punktmenge P G (i) separat. Somit resultieren N Punkteverteilungen P T (i), wobei jede Verteilung aus K Punkten p ^T k (i) mit kartesischen Koordinaten (x, y) besteht. Die Punkteverteilungen ergeben sich aus

² p ^T k (i) = x, y ∈ R |k = 1, . . . , K P T (i) =

mit p ^T k (i) = A b (p ^G k (i)).

Der Punkt b repräsentiert den Berührungspunkt der Tangentialebene mit der Einheitskugel. Er wird als der Mittelwert von P G (i) deﬁniert. Wie bereits gezeigt, kann man den extrinsischen und intrinsischen Mittelwert von P G (i) bestimmen. Somit gilt, dass b = μ Φ oder b = μ für die Projektion verwendet werden kann. Durch die Projektion werden die Punkte bezüglich ihres Mittelwerts zentriert. Dies ist ein notwendiger Schritt um die darauf folgende Hauptkomponentenanalyse durchzuführen. In Abbildung 5.50 ist illustriert, wie die Projektion stattﬁndet.

5.6.3 Ermitteln der Modelleigenschaften

Es wurde gezeigt, wie sich die Normalenfelder als Punktdaten in einem linearen Raum darstellen lassen. Diese sollen nun analysiert werden und somit die Modell/-eigenschaften ermittelt werden. In Abschnitt 5.1.4 wurde gezeigt, dass sich die Hauptkomponenten berechnen lassen, indem man eine Kovarianzmatrix analysiert. Die resultierenden Hauptkomponenten entsprechen dann Normalenfeldern, welche den Raum der Normalenfelder der Trainingsgesichter aufspannen. Um die N Punkteverteilungen zu analysieren, wird zunächst eine Datenmatrix

155

5 Statistisches Modell für Oberﬂächennormalen

(a) Punkteverteilung auf

der Einheitskugel.

Abbildung 5.50: Eine Punktmenge PG(i) wird linearisiert indem eine Tangentialebene an dem

Mittelwert von gebildet wird und die Punkte auf diese projiziert werden.

aufgestellt. Hierfür lassen sich die Normalenfelder als Vektoren darstellen. Ein Vektor U k repräsentiert daraufhin ein Normalenfeld, wobei sich die Punkte auf der Tangentialebene beﬁnden und somit eine Normale durch ein (x, y) Tupel auf der Ebene beschrieben ist. Für ein Normalenfeld entsteht der Vektor

^T , U k = [p ^T k (1) x , . . . , p ^T k (N ) x , p ^T k (1) y , . . . , p ^T k (N ) y ]

wobei die x- und y-Werte der N Bildpunkte getrennt betrachtet werden. Der Vektor hat somit eine Größe von 2N .

Mit den Vektoren U k kann nun eine Datenmatrix D konstruiert werden. Hierfür bildet jeder Vektor eine Spalte in D. Die erste Zeile dieser Datenmatrix beschreibt dementsprechend alle x-Komponenten des Bildpunktes mit dem Index i = 1 aus den Normalenfeldern. Die Datenmatrix D besitzt die Größe 2N × K und ist als

D = [U 1 | . . . |U k ]

deﬁniert.

Zwischen den x-Werten der Normalen zweier Bildpunkte lässt sich ihre Abhängigkeit zueinander mit der Kovarianz ausdrücken. Da die Normalen bereits

156

bezüglich ihrer Mittelwerte zentriert sind, berechnet sich die Kovarianz wie folgt:

k=1

Für die ganze Datenmatrix D resultiert somit die Kovarianzmatrix

1 ^T . Cov = DD

K

Sie beinhaltet die Kovarianzen aller möglichen Bildpunktkombinationen, wobei x- und y-Werte getrennt betrachtet werden. Die Matrix drückt somit aus, wie x- und y-Werte sowohlseparat als auch gegenseitig voneinander abhängen. Die Matrix Cov besitzt eine Größe von 2N × 2N . Der Raum, welcher von dieser Matrix aufgespannt wird, ist durch die Anzahl der Normalenfelder deﬁniert. Es handelt sich somit um einen K-dimensionalen Raum. Aus einer Hauptkomponentenanalyse von Cov würden rein theoretisch 2N Hauptkomponenten Ψ resultieren. Jedoch beschreiben dann nur die ersten K Hauptkomponenten die Ausdehnung des Raums der Normalenfelder. Die restlichen Hauptkomponenten existieren nicht, da für ihre zugehörigen Eigenwerte λ = 0 gilt. Da 2N >> K gilt, ist es sinnvoll einen anderen Weg zu ﬁnden um die K Hauptkomponenten von Cov zu ermitteln.

In [Smi07] werden die Hauptkomponenten mit der sogenannten Snap-Shot-Methode aus [Kir87] berechnet. Statt die Normalen zweier Bildpunkte in Abhängigkeit zu setzen, berechnet sich die Kovarianz hier zwischen zwei kompletten

Normalenfeldern. Die Kovarianzmatrix Cov beinhaltet dann alle paarweisen Zusammenhänge der K Normalenfelder. Sie berechnet sich wie folgt:

1 ^T D Cov = D.

K

Zu dieser Matrix existieren K Hauptkomponenten ˆ Ψ. Jedoch besitzt jede Komponente nur K Einträge und bildet deshalb kein komplettes Normalenfeld nach, wie es die Hauptkomponenten von Cov tun. Die Snap-Shot-Methode besagt, dass Ψ k von der kte Eigenvektor Ψ k von Cov dem Eigenvektor ˆ Cov multipliziert mit D entspricht:

5 Statistisches Modell für Oberﬂächennormalen

Um diese Behauptung zu beweisen, muss gezeigt werden, dass

CovD ˆ Ψ = λD ˆ Ψ

gilt, denn CovΨ = λΨ. Dieser Zusammenhang lässt sich anhand folgender Umformung nachvollziehen:

Ψ.

Die Hauptkomponenten besitzen nun wieder 2N Elemente und entsprechen daher Normalenfeldern. Um die Normalenfelder anhand ihrer Signiﬁkanz zu ordnen, benötigt man die Eigenwerte. Der kte Eigenwert λ k von Cov entspricht dem von Cov. Die Kovarianzmatrix Cov besitzt jedoch 2N Eigenwerte, wobei aber nur die ersten K ungleich Null sein können sodass

λ k = D ˆ k ≤ K λ k wenn

gilt. Andernfalls ist λ k = 0. Sortiert man nun die Normalenfelder abhängig von den Eigenwerten, so erhält man als erste Hauptkomponente das Normalefeld, welches sich am meisten vom Durchschnittsnormalenfeld unterscheidet. Die weiteren Hauptkomponenten nehmen mit absteigenden Eigenwerten auch an ihrer Signiﬁkanz ab.

Das statistische Modell für Oberﬂächenormalen ist nun erstellt. Es setzt sich aus den Hauptkomponenten der Normalenfelder zusammen, welche die Eigengesichter sind. Die Hauptkomponenten Φ werden in einer Modellmatrix M zusammengefasst: M = [Ψ 1 | . . . |Ψ k ].

Gesichter, deren Eigenschaften sich durch den Modellraum abdecken lassen, können nun mit M nachgebildet werden. Das Nachbilden erfolgt durch Kombination von gewichteten Eigengesichtern. Wie eine solche Nachbildung funktioniert wird im Folgenden gezeigt.

Gegeben sei ein Normalenfeld n, welches beispielsweise durch ein Shape-from-Shading-Verfahren ermittelt wurde. Nun soll das Modell dieses Normalenfeld so

158

gut wie möglich nachbilden. Zunächst werden hierfür die Normalen aus n als Punkte auf der Einheitskugel aufgefasst. Um sie mittels mittelabstandstreuer Azimutalprojektion auf eine Tangentialebene zu projizieren, müssen sie in geographische Koordinaten umgewandelt werden. Als Berührungspunkt für die Normalen dient der Mittelwert b des jeweiligen Bildpunktes. Aus den resultierenden Normalen als Punkte auf der Tangentialebene wird der Vektor U 0 analog zu U k gebildet.

Die Modellparameter b erhält man durch die folgende Matrixmultiplikation:

Der Vektor b hat die Länge K und beinhaltet die einzelnen Gewichte für die Eigengesichter. Bei der Multiplikation aus Gleichung (5.33) wird jede Gewichtung unabhängig von allen anderen Ermittelt. Der Parameter für den ersten Eigenvektor ergibt sich daher folgendermaßen:

b 0 = M 0|0 · U ⁰ 0|0 + M 1|0 · U ⁰ 0|1 + M 2|0 · U ⁰ 0|2 + . . . + M 2N |0 · U ⁰ 0|2N .

Multiplikation das resultierende Gewicht. Im Gegenteil dazu wird das Gewicht verringert, wenn die Komponenten unterschiedliche Vorzeichen besitzen. Aus diesem Grund werden die Eigengesichter umso stärker gewichtet, je ähnlicher sie dem nachzubildenden Normalenfeld sind.

Für jedes Eigengesicht wird solch ein Gewicht berechnet. Somit lässt sich sagen, welches Eigengesicht zu welchem Anteil mit den anderen Eigengesichtern vermischt wird. Um keine fehlerhaften Darstellungen zu erhalten, müssen die Modellparameter b normiert werden. Wegen diese Normierung können durch das Mischen nur Gesichter entstehen, die sich im Modellraum beﬁnden.

159

5 Statistisches Modell für Oberﬂächennormalen

160

Kapitel 6

Modellgestütze Rekonstruktion

In Kapitel 4 wurde ein Framework zur Rekonstruktion von Oberﬂächen mittels Shape-from-Shading vorgestellt. Hierbei ist es möglich, die Bildrückstrahlfunktion nach jedem Durchgang als harte Bedingung durchzusetzen.

In diesem Kapitel wird gezeigt, in welcher Form man das statistische Modell aus Kapitel 5 in die Rekonstruktion einbeziehen kann. Es werden drei verschiedene Algorithmen beschrieben, die aufeinander aufbauen und somit das statistische Modell schrittweise integrieren.

Zunächst wird gezeigt, wie sich mit Hilfe des Shape-from-Shading Gesichter rekonstruieren lassen. Dies soll die Funktionsweise des Frameworks verdeutlichen. Darauf aufbauend wird gezeigt, wie man die Rekonstruktion mit Shape-from-Shading durch die Integration des statistischen Modells erweitern kann. Mit diesem Wissen lässt sich zeigen, wie das statistische Modell in das iterative Shapefrom-Shading-Framework integriert werden kann.

6.1 Rekonstruktion durch Shape-from-Shading und

Glätten der Oberﬂäche

Algorithmus 6.1 beschreibt wie das in Kapitel 4 beschriebene Verfahren verwendet werden kann. Als weiche Bedingung dient hier die in Abschnitt 4.5.2 vorgestellte Methode zur Glättung der Oberﬂäche.

161

6 Modellgestütze Rekonstruktion

Algorithmus 6.1 Rekonstruktion durch Shape-from-Shading unter Glättung der Oberﬂäche

Input: Lichtquelle s, Bildintensitäten I(x, y) Output: Das durch Glättung und Shape-from-Shading angepasste Normalenfeld n(x, y) 1: Iteration t = 0

2: Initialisieren von n ^(t) (x, y) (siehe Abschnitt 4.5.3) 3: repeat

4: 5: 6:

7: until

Die Abbruchbedingung in Zeile 7 tritt ein, wenn sich von einer Iteration zur nächsten nur wenig ändert.

w ist folgendermaßen deﬁniert:

v · w = |v| · |w| · cos α.

Da Normalen normiert sind und somit die Länge eins haben, kann der Winkel

^{(t−1) (t)} aus der letzten und n zwischen einer Normale n ij aus der aktuellen Iteration ij

über

^{(t) (t−1)} n ij · n α = arccos ij

berechnet werden. Dieser Term wird quadriert um in stärker zu gewichten und über alle Normalenpaare der beiden Felder aufsummiert. Ist diese Summe kleiner als ein Wert ε ist der Algorithmus konvergiert.

Auch wenn die geglätteten Normalen immer von den zurückrotierten abweichen, muss der Algorithmus irgendwann konvergieren, da jeweils die Normalenfelder nach einer kompletten Iteration verglichen werden. Das heißt, dass der Unterschied zwischen den zurückrotierten Normalen des letzten zu den zurückrotierten Normalen des aktuellen Durchgangs minimiert wird.

162

6.2 Rekonstruktion durch Projektion auf den Modellraum

6.2 Rekonstruktion durch Projektion auf den

Modellraum

In diesem Abschnitt wird eine Vorgehensweise beschrieben, welche zeigt wie ein statistisches Modell in das Shape-from-Shading-Framework integriert werden kann. Zunächst gelten die selben Ausgangsbedingungen wie in Abschnitt 6.1. Zusätzlich wird das Modell M und das mittlere Normalenfeld ˆ n benötigt. Aus Abschnitt 5.6.1

sind mit dem extrinsischen Mittelwert μ Φ und dem intrinsischen Mittelwert μ zwei

n zu ermitteln. Neben n ^(t) wird nun auch ˜ Möglichkeiten bekannt um ˆ n ermittelt.

Es entspricht dem Normalenfeld, welches entsteht, wenn die Eigengesichter mit ihren optimalen Modellparameter zusammengesetzt werden. Die Vorgehenweise zur Rekonstruktion ist in Algorithmus 6.2 zusammengefasst.

Algorithmus 6.2 Rekonstruktion durch Shape-from-Shading unter Glättung der Oberﬂäche und anschließender Projektion auf den Modellraum

Input: Lichtquelle s, Bildintensitäten I(x, y), statistisches Modell M, mittleres Normalenfeld ˆ n

Output: Das durch Glättung und Shape-from-Shading angepasste Normalenfeld n(x, y), das durch das statistische Modell ermittelte Normalenfeld ˜ n 1: Iteration t = 0

2: Initialisieren von n ^(t) (x, y) (siehe Abschnitt 4.5.3) 3: repeat

4: 5: 6:

7: until x,y

8: Jede Normale in n ^(t) (x, y) wird mit mittelabstandstreuer Azimutalprojektion abgebildet und in U 0 gespeichert.

9: Der Vektor b mit den am besten passenden Modellparametern ist gegeben

durch b = M ^T U 0 .

10: Das am besten passende Normalenfeld kann über U = Mb ermittelt werden. 11: Zurückprojizieren der Normalen mit der inversen mittelabstandstreuen Azi- n ^(t) (x, y). mutalprojektion und Speichern in ˜

ergeben sich aus der Matrixmultiplikation (Gleichung (5.33)). Mit dieser kann nun der Vektor U = Mb gebildet werden, der das passendste Modell beschreibt. Hier-

163

6 Modellgestütze Rekonstruktion

bei werden die einzelnen Gewichtungen von b auf die Eigengesichter des Modells M angewendet. Durch Abbilden von U mit der mittelabstandstreuen Azimutalprojektion wird das Normalenfeld ˜ n ermittelt. Die Normalenrichtungen von ˜ n

beﬁnden sich alle im Modellraum.

6.3 Kombination des Shape-from-Shading mit dem

statistischen Modell

Das im letzten Abschnitt beschriebene Verfahren zur Rekonstruktion basiert vor Allem auf dem Modell. Die Ergebnisse werde nicht an die Bildrückstrahlfunktion angepasst. Daher können nur Charakteristika rekonstruiert werden, welche sich im Modellraum wiederﬁnden. Das statistische Modell wird deshalb nun direkt mit dem iterativen Shape-from-Shading-Framework kombiniert. In Algorithmus 6.3 ist die Kombination zusammengefasst.

Algorithmus 6.3 Rekonstruktion durch modellgestütztes Shape-from-Shading Input: Lichtquelle s, Bildintensitäten I(x, y), statistisches Modell M, , mittleres Normalenfeld ˆ n

Output: Das durch das statistische Modell ermittelte Normalenfeld ˜ n, das durch

Shape-from-Shading angepasste Normalenfeld n(x, y) 1: Iteration t = 0

2: Initialisieren von n ^(t) (x, y) 3: repeat

4: 5: 6:

den.

7: 8: 9:

10: until

Die optimalen Modellparameter werden nun nicht mehr nur einmal am Ende der Rekonstruktion bestimmt, sondern in jeder Iteration des Algorithmus. Danach

164

werden die Normalen jedesmal auf ihren von der Bildrückstrahlfunktion deﬁnierten Kegel zurück rotiert. Durch diese Kombination kann die bestpassende Position auf dem Kegel gefunden werden und somit die Genauigkeit der Rekonstruktion gesteigert werden. Ist der Algorithmus konvergiert, steht ˜ n(x, y) für die am besten passende Kombination der Eigengesichter des Modells. Durch n(x, y) wird das Normalenfeld beschrieben, welches durch die Durchsetzung der harten Bedingung der Rückstrahlfunktion bei gleicher Beleuchtung wieder die gleichen Helligkeitswerte erzeugen würde. Daher können auch Eigenschaften rekonstruiert werden, welche nicht von dem Modellraum abgebildet werden. Fehler des Shape-from-Shading werden durch das Modell ausgeglichen, sodass auch durch das Shape-from-Shading schlecht annäherbare Normalen rekonstruiert werden können.

165

6 Modellgestütze Rekonstruktion

166

Kapitel 7

Realisierung

Dieses Kapitel zeigt, wie sich das in den letzten Kapiteln beschriebene Verfahren zur Rekonstruktion von Gesichtern realisieren lässt. Zunächst wird gezeigt, auf welcher Architektur die entwickelte Anwendung basiert und welche Komponenten hierfür entwickelt wurden. Für welcher Hardware diese Anwendung umgesetzt wurde, ist im darauf folgenden Abschnitt herausgestellt. Zusätzlich wird die verwendete Programmiersprache und die verwendeten Bibliotheken, welche zur Implementierung verwendet wurden, deﬁniert.

7.1 Architektur

Es wurden zwei Hauptmodule entwickelt, die sich in Modellaufbau und Rekonstruktion aufteilen lassen. Zwischen diesen beiden Modulen ﬁndet keine Interaktion statt. Dennoch wurden beide Module in ein Programm integriert, damit beide auf die selben Datentypen aufbauen können. Außerdem konnten so verschiedene Hilfsklassen, die zum Beispiel der Anzeige der Objekte oder zur Berechnung allgemeiner mathematischer Probleme dienen, wiederverwendet werden.

Die einzige Schnittstelle zwischen den Modulen ist das aus dem Modellaufbau resultierende statistische Modell. Wie in Kapitel 6 gezeigt, wird dieses zur Rekonstruktion eines Gesichtsmodells aus einer Fotograﬁe verwendet. Da hier die allgemeine Architektur der Anwendung beschrieben werden soll und es keine für

167

7 Realisierung

den Ablauf der einzelnen Module notwendige Interaktion gibt, werden diese getrennt betrachtet. Es sollen jeweils die wichtigsten Architekturentscheidungen, Abläufe und Zusammenhänge herausgestellt werden.

7.1.1 Aufbau des Modells

Dieser Abschnitt beschreibt die Architektur für die Umsetzung des in Kapitel 5 beschriebenen Verfahrens. Wie in Abschnitt 5.3 beschrieben, ist der Aufbau des statistischen Modells sequentiell. Es werden zunächst die Korrespondenzen zwischen einem Referenzgesicht und allen Beispielgesichtern bestimmt. Daraus resultiert ein optischer Fluss für jedes Gesichtspaar. Um später die Normalenfelder ermitteln zu können, müssen nun alle Gesichter aus den Trainingsdaten mit dem zugehörigen optischen Fluss zwischengespeichert werden. Dies würde zu großen Datenmengen führen, welche auf manchen Rechner zu Schwierigkeiten führen können. Abbildung 7.1 zeigt eine Architektur, bei welcher dies nicht notwendig ist. Aus den vorliegenden Trainingsdaten wird dazu ein Referenzgesicht gewählt. Dieses wird einmalig geladen und an die folgenden Schritte weitergereicht. Anstatt zuerst alle optischen Flüsse zu berechnen, wird jeweils nur ein Gesicht aus den Trainingsdaten genommen und die Korrespondenz bestimmt. Mit dem resultierenden Vektorfeld wird das Gesicht ausgerichtet und anschließend projiziert. Hierraus ergibt sich das zugehörige Normalenfeld. Das projizierte Gesichtsmodell ist für die folgenden Schritte nicht mehr notwendig. Dieser Vorgang wird für jedes Gesicht aus den Trainingsdaten wiederholt, bis alle Normalenfelder bestimmt sind. Hat man alle Normalenfelder ermittelt, können sie, wie in Abschnitt 5.6.3 beschrieben, analysiert werden.

In Abbildung 7.2 ist der interne Ablauf der Korrespondenzberechnung dargestellt. Um eine Korrespondenz zu bestimmen steht die Auﬂösungspyramide des Referenzgesichts sowie ein Gesichtsmodell aus den Trainingsdaten zur Verfügung. Zunächst wird die Auﬂösungspyramide für das Gesichtsmodell ermittelt. Die folgenden Schritte werden für jede Pyramidenstufe ausgeführt. Um den Verschiebungsvektor eines Bildpunktes zu ermittelt wird, wie in Abschnitt 5.4.2 beschrieben, jeweils eine Nachbarschaft betrachtet. Hierbei ist es notwendig die Ableitungen dieser Nachbarschaften zu ermitteln, um einen Bildpunkt zu verarbeiten. Das bedeutet, dass für jeden Bildpunkt mehrmals seine Ableitung gebildet wird. Statt dessen empﬁelt es sich, die Bildableitungen auf jeder Pyramidenstufe vorzube-

168

Abbildung 7.1: Das Diagramm zeigt die einzelnen Schritte zum Aufbau des statistischen Mo-

7 Realisierung

Abbildung 7.2: Das Diagramm zeigt den internen Ablauf der Korrepondenzﬁndung.

rechnen. Dies führt im Normalfall zu einer deutlichen Verbesserung der Laufzeit der Korrespondenzbestimmung.

7.1.2 Rekonstruktion der Gesichtsmodelle

In Abbildung 7.3 ist der Ablauf der umgesetzten Rekonstruktion eines Gesichts aus einer Fotograﬁe dargestellt. Es ist zu erkennen, dass es sich hierbei um eine einfache Pipeline handelt. Jeder funktionale Block ist dabei von dem Ergebnis des letzten abhängig. Deswegen ist es sinnvoll dies in den Klassen der Anwendung auch so abzubilden.

In Abbildung 7.4 sind die zur Rekonstruktion notwendigen Klassen abgebildet. Sie entsprechen den jeweiligen Ergebnissen eines funktionalen Blocks aus Abbildung 7.3. Die einzelnen Schritte der Rekonstruktion sind jeweils als Funktion im entsprechenden Kontext der Klasse deﬁniert.

In jeder Klasse ist eine Instanz der vorherigen Klasse abgelegt und wird auch mit diesen initialisiert. Dadurch ist sichergestellt, dass jederzeit Zugriﬀ auf alle notwendigen Daten besteht. Außerdem ist es dadurch leicht möglich innerhalb der Rekonstruktion einen Schritt zurück zu gehen.

170

171

7 Realisierung

172

die in 6 vorgestellten Algorithmen 6.2 oder 6.3 erfolgen, muss das statistische Modell zur Verfügung stehen.

schriebenen Klassen verantwortlich. Das Intensitätenfeld kann als Graustufenbild über den IntensitätenfeldViewer angezeigt werden.

Die Darstellung der Normalen- und Höhenfelder sowie Polygonnetze erfolgt über einen 3D-Viewer. Dieser kann Objekte rendern, die das Interface Renderable implementieren. Die Klasse VBOObjekt realisiert Renderable. Ein VBO-Objekt ist eine Darstellungsart eines 3D-Objekts, welche komplett auf der Graﬁkkarte gespeichert werden kann. Sie kann durch ein Normalenfeld, Höhenfeld oder Polygonnetz initialisiert werden.

173

7 Realisierung

Logik und Daten Benutzeroberfläche

In Abbildung 7.6 ist der Kontrollﬂuss der Anwendung dargestellt. Zur Steuerung der Rekonstruktion steht dem Benutzer zu jedem der funktionalen Blöcke ein Panel in einem Kontrollfenster zur Verfügung. Jedes Panel erstellt sich, wenn es aktiv ist, einen Viewer zur Darstellung von Intensitätenfeld, Normalenfeld, Höhenfeld oder Polygonnetz. Es ruft außerdem die in seiner entsprechenden Logikklasse (siehe Abbildung 7.4) benötigten Funktionen auf. Das Kontrollfenster und der jeweilige Viewer bilden die Benutzeroberﬂäche der Anwendung.

7.2 Umsetzung

In diesem Abschnitt sollen die wichtigsten Aspekte der Implementierung der Anwendung erläutert werden.

7.2.1 Hardware

Das komplette Verfahren der modellgestützten Rekonstruktion soll auf einem handelsüblichen Computer lauﬀähig sein. Das heißt, dass keine spezielle kostenintensive Geräte vorausgesetzt werden. Deswegen wurden die Algorithmen so imple-

174

mentiert, dass eine Speichergrenze von maximal 1 GB nicht überschritten wird. Bei der modellgestützten Rekonstruktion handelt es sich hauptsächlich um mathematische Probleme. Auch die Darstellung der 3D-Objekte ist nicht zwingend notwendig und leicht durch jede aktuelle Graﬁkkarte zu bewältigen.

7.2.2 Software

Für die Umsetztung wurden eine geeignete Graﬁk-API und Programmiersprache gewählt werden.

OpenGL

Bei OpenGL ¹ (Open Graphics Library) handelt es sich um eine Speziﬁkation zur

Darstellung von 3D-Inhalten. Es wird seit 1992 von Silicon Graphics entwickelt und hat sich seit dem zu der am weitesten verbreiteten API für 3D- und 2D-Graﬁk entwickelt. Sie ist frei verfügbar und unabhängig von Programmiersprache und Plattform. Es handelt es sich bei OpenGL somit um die beste Wahl für den Einsatz in einer wissenschaftlichen Arbeit.

Java

Die Entscheidung für Java ² als Programmiersprache wurde aus ähnlichen Grün- wie die für OpenGL getroﬀen. Es handelt sich bei Java um eine freie und plattformunabhängige Sprache. Sie ist komplett objektorientiert und bietet alle Vorteile einer modernen Programmiersprache der dritten Generation. Java wird seit 1996 von Sun Microsystems entwickelt. Es stehen in Java eine Vielzahl von frei verwendbaren Bibliotheken zur Verfügung. Um die OpenGL API anzusprechen wurde Jogl ³ (Java OpenGL) verwendet.

Es handelt sich hierbei um ein einfaches von der Game Technology Group at Sun Microsystems entwickeltes Binding für OpenGL

Zur Berechnung einiger mathematischer Probleme wurde Jama ⁴ (Java Matrix

Package) verwendet. Es handelt sich dabei um eine Bibliothek, welche alle gängi-

¹ Quelle:

² Quelle: http://www.java.com

³ Quelle: https://jogl.dev.java.net/

⁴ Quelle: http://math.nist.gov/javanumerics/jama/

175

7 Realisierung

gen Operationen der Linearen Algebra umfasst. Jama wurde entwickelt von The MathWorks und der NIST (National Institute of Standards and Technology). In dieser Arbeit müssen große Matrizen verwaltet werden, was mit Jama gut möglich ist. Vorallem bei der Implementierung der Algorithmen hat sich Jama als gute Bibliothek für die Matrixmultiplikationen und Eigenwert- und Eigenvektorberechnung bewährt. Weiterhin bietet Jama eine Singulärwertzerlegung zum lösen von linearen Gleichungssystemen wie es bei der Berechnung des optischen Flusses aus Abschnitt 5.4 notwendig ist.

Bei einigen Aufgaben der Bildverarbeitung wurde Jai ⁵ (Java Advanced Imaging)

verwendet. Diese Bibliothek bietet mehr Funktionen als die in Java standardmäßig enthaltene API zur Bildverarbeitung. Sie wurde zum Beipiel zur Berechnung der Fouriertransformation bei der Integration der Normalenfelder aus Abschnitt 4.6 eingesetzt.

⁵ Quelle: https://jai.dev.java.net/

176

Kapitel 8

Tests und Bewertung

Dieses Kapitel befasst sich mit den Ergebnissen der in dieser Arbeit umgesetzten Algorithmen. Die Ergebnisse lassen sich in drei Bereiche aufteilen.

Zunächst wird der Aufbau des statistischen Modells analysiert. Dabei soll gezeigt werden, wie robust die Berechnung des optischen Flusses ist und wann die Korrespondenzbestimmung fehlschlägt. Darauf aufbauend lässt sich zeigen, wie die Eigengesichter für die hier verwendeten Trainingsgesichter aussehen.

Die folgenden Abschnitte setzen sich mit der Rekonstruktion von Gesichtsmodellen aus gerenderten Abbildungen auseinander. Hierfür wurde das Standardgesicht aus [MMPI] verwendet. Es wird gezeigt, wie die rekonstruierten dreidimensionalen Gesichtsmodelle aussehen. Ein Vergleich der in Kapitel 6 vorgestellten Algorithmen beschreibt die Unterschiede zwischen den Ergebnissen. Anschließend werden durch Experimente mit der Beleuchtungsrichtung, Drehung des Kopfes und perspektivischer Verzerrung die Stärken und Schwächen des entwickelten Frameworks dargestellt.

Der letzte Abschnitt befasst sich mit der Rekonstruktion von realen Fotograﬁen.

Alle Laufzeitmessungen wurden unter folgenden Rahmenbedingungen durchgeführt:

177

8 Tests und Bewertung

• Betriebssystem: Windows XP Professional.

8.1 Aufbau des Modells

Die in dieser Arbeit verwendeten dreidimensionalen Laserscans stammen aus einer am Max-Plack-Institut vorliegenden 3D Face Database [MMPI]. Von dieser Datenbank sind fünf Datensätze für wissenschaftliche Arbeiten frei verfügbar. Die fünf Laserscans bestehen aus zwei weiblichen und zwei männlichen Gesichtern, sowie dem Durchschnittsgesicht der kompletten Datenbank. In Abbildung 8.1 sind die fünf Gesichtsmodelle dargestellt.

Abbildung 8.1: Es stehen fünf Datensätze zur Verfügung. Das Referenzgesicht entspricht dem

Durchschnittsgesicht der 200 Köpfe der 3D Face Database [MMPI].

Sie sind, wie in Abschnitt 5.1.1 zusammengefasst, grob aufeinander ausgerichtet. Abbildung 8.2(a) zeigt die Texturen von zwei Beispieldatensätzen. Um die grobe Ausrichtung zu verdeutlichen, sind sie auf der rechten Seite der Abbildung überlagert dargestellt. Die zugehörigen Gesichtsmodelle der Texturen sind in Abbildung 8.2(b) ineinander gerendert um zu zeigen, dass auch die Geometriedaten aufeinander ausgerichtet sind.

Der Aufbau des statistischen Modells für diese Datensätze benötigt in etwa 100 Sekunden. Hierbei ist zu beachten, dass die Initialisierungsphase ungefähr 20 Sekunden dauert. In verschiedenen Tests waren die Laufzeiten konstant, sodass man sagen kann, dass die Laufzeit für jeden weiteren Datensatz um ungefähr 20 Sekunden zunimmt.

Alle folgenden Tests basieren auf diesen fünf Datensätzen. Die Tests zeigen, welche Ergebnisse bei der Korrespondenzbestimmung möglich sind und inwiefern

178

8 Tests und Bewertung

Einschränkungen vorhanden sind. Im letzten Abschnitt werden die Eigengesichter betrachtet, welche den Gesichtsraum des Modells ausdrücken.

8.1.1 Korrespondenzbestimmung

Der erste Test befasst sich mit der Ausrichtung der Datensätze. Hierbei wird vor Allem gezeigt, wie genau die grobe Ausrichtung sein muss, um zuverlässig Korrespondenzen zu ﬁnden. Der zweite Test untersucht die Wirkung von globalen Helligkeitsunterschieden. Anhand der resultierenden Vektorfelder und den damit gewarpten Ausgangsbildern lässt sich zeigen, dass der globale Helligkeitsunterschied nur in Grenzfällen eine Schwierigkeit darstellt. Die Laufzeiten sind konstant und variieren im Schnitt um ±3 Sekunden. Die Bestimmung der Korrespondenz zwischen zwei Datensätzen dauert ca. 20 Sekunden.

Fehlende Ausrichtung der Datensätze

Die Daten sind, wie in Abbildung 8.1 zu sehen, grob aufeinander ausgerichtet. Die ersten beiden Bilder in Abbildung 8.3 zeigen zwei Texturen. Sie sind nicht

mehr so wie bisher aufeinander ausgerichtet, denn die zweite Textur ist um 5 ◦

gedreht worden. Die beiden anderen Bilder zeigen den dazugehörigen optischen Fluss, sowie dass durch den Rückwärts-Warp veränderte Bild. Es ist zu sehen, dass die meisten Korrespondenzen stimmen und nur am rechten Ohr deutlich sichtbare Fehler auftreten.

Erhöht man die Drehung auf 10 ^◦ , stimmen die Korrespondenzen kaum noch.

Wie in Abbildung 8.4 zu sehen, stimmen nicht einmal die Ränder des Kopfes

180

überein. Die Ränder können bei der Berechnung am besten gefunden werden, da

diese eine klare Struktur darstellen. Durch die Bildung einer Laplacepyramide orientiert sich der Korrespondenzalgorithmus vor Allem an Kanten.

Skaliert man nun eines der beiden Gesichter, erhält man beispielsweise das in Abbildung 8.5 gezeigte Ergebnis. Schon bei einer kleinen Skalierung schlägt die

Korrespondenzbestimmung fehl. Dies liegt vor Allem daran, dass im zweiten Bild deutlich weniger Bildpunkte mit Farbinformationen vorhanden sind als im ersten Bild.

Globale Helligkeitsunterschiede

In Abschnitt 5.4.3 wurde beschrieben, dass der globale Helligkeitsunterschied zwischen den Gesichtern die Korrespondenzbestimmung prinzipiell nicht erschwert. Hierfür betrachtet man zunächst Abbildung 8.6. Die globale Helligkeit der beiden abgebildeten Gesichter unterscheidet sich deutlich. Es handelt sich um den größten Helligkeitsunterschied in den vorhandenen Trainingsgesichtern. Man sieht, dass der optische Fluss in fast allen Gesichtsbereichen korrekt ermittelt wird. Am unteren Rand des gewarpten Gesichts ist ein Fehler zu erkennen. Dieser kommt

181

8 Tests und Bewertung

Abbildung 8.6: Der globale Helligkeitsunterschied zwischen den beiden Texturen ist deutlich

sichtbar.

durch den deutlichen Helligkeitsunterschied zustande, welcher durch den Bart des rechten Bildes hervor gerufen wird.

Erhöht man nun künstlich die Helligkeit im linken Bild, erhält man den in Abbildung 8.7 dargestellten optischen Fluss. Es resultiert ein gewarptes Bild, welches

deutliche Fehler aufweist. Es lässt sich bewertend sagen, dass die Korrespondenzbestimmung bei sehr starken Helligkeitsunterschieden nur grob die zugehörigen Bildpunkte ermitteln kann.

8.1.2 Visualisierung der Eigengesichter

Die Eigengesichter entsprechen den in Abschnitt 5.6.3 ermittelten Hauptkomponenten der Normalenfelder. Sie beschreiben die Abweichungen zum Durchschnittsnormalenfeld der vier Beispielgesichter. Um die Eigengesichter nun darzustellen, dient als Ausgangsnormalenfeld das Durchschnittsnormalenfeld. In Abschnitt wurde gezeigt, dass es zwei verschiedene Durchschnittsnormalenfelder μ Φ (i) und μ(i) gibt.

Durch verschiedenen Tests wurde festgestellt, dass für die verwendeten Trai-

182

ningsgesichter μ Φ (i) = μ(i) gilt. Das Verwenden des intrinsischen Mittelwerts könnte für eine größere Gesichtsdatenbank die Genauigkeit verbessern. Für die Visualisierung der Eigengesichter wurde mit dem extrinsischen Mittelwert gearbeitet.

Die Richtungen der Durchschnittsnormalen werden nun so verändert, dass sie die Eigengesichter repräsentieren können. Hierzu verschiebt man ihre Punkte auf den jeweiligen Tangentialebenen in Richtung des Punktes der zugehörigen Eigengesichtsnormalen. Wie stark sie verschoben werden hängt von der Standardabweichung σ der Beispielgesichter zum Durchschnittsgesicht ab. K

Um die Eigenschaften deutlicher darzustellen wird σ(i) mit einem Faktor a ± 3 gewichtet. Auf diese Weise entstehen die Eigengesichter in Abbildung 8.8. In der mittleren Spalte ist zum Vergleich jeweils das Durchschnittsnormalenfeld dargestellt. Die Eigengesichter der linken Spalte wurden mit der Gewichtung a = −3 erstellt. Durch sie repräsentierte Merkmale wurden somit in dem Durchschnittsgesicht geschwächt. Die rechte Spalte der Abbildung zeigt die resultierende Eigengesichter für a = +3. Ihre beinhalteten Merkmale werden somit stärker heraus gestellt. Welche Merkmale in den vier Eigengesichtern enthalten sind lässt sich am besten durch einen Vergleich der ersten Spalte mit der dritten Spalte erkennen. Da für diese Arbeit nur vier Trainingsgesichter zur Verfügung standen, sind die Merkmale nicht sehr markant. Jedoch lässt sich erkennen, dass das erste Eigengesicht am stärksten vom Durchschnittsgesicht abweicht. Das vierte Eigengesicht hingegen ähnelt dem Durchschnittsgesicht. Die korrekte Funktionsweise des Modellaufbaus ist somit nachvollziehbar.

8.2 Rekonstruktion der Gesichtsmodelle mit den

verschiedenen Algorithmen

In Kapitel 6 wurden drei verschiedene Algorithmen zur Rekonstruktion vorgestellt. Die Ergebnisse dieser Algorithmen werden im Folgenden dargestellt. Hierfür wurde das Standardgesicht aus [MMPI] verwendet. Es wurde frontal beleuchtet und mit

183

8 Tests und Bewertung

1. EG

2. EG

3. EG

4. EG

Abbildung 8.8: Die resultierenden Eigengesichter der vier vorhandenen Trainingsdaten.

184

Lambertschem Verhalten gerendert. Dazu wurde eine orthograﬁsche Projektion verwendet. In Abbildung 8.9 ist das gerenderte Durchschnittsgesicht dargestellt.

8.2.1 Rekonstruktion mittels Shape-from-Shading

Bei der Rekonstruktion mittels dem in dieser Arbeit beschriebenen Shape-from-Shading können keine genauen Rekonstruktionen von Gesichtern berechnet werden. In Abildung 8.10 sind die Ergebnisse des Verfahrens dargestellt. Als Grundlage der Rekonstruktion diente das in Abbildung 8.9 dargestellte Durchschnittsgesicht.

In der der ersten Spalte von Abbildung 8.10 ist das intiale Gesicht dargestellt. Die Ergebnisse der Rekonstruktion sind nach einem, drei und zehn Iterationen in den Spalten zwei, drei und vier abgebildet.

Wie zu erwarten sind nach der Initialisierung keine starken Verbesserungen mehr zu erkennen. Dies liegt daran, da dass Shape-from-Shading sehr lokal arbeitet. Es wird nur die direkte Nachbarschaft der jeweiligen Normale verwendet, um eine glatte Oberﬂäche zu generieren. Deswegen kann man nicht erwarten, dass sich bei der Qualität der Rekonstruktion bei steigender Zahl der Iteration Verbesserung an der gesamten Form des Gesichtes ergeben.

185

8 Tests und Bewertung

Abbildung 8.10: Ergebnisse der Rekonstruktion mittels Shape-from-Shading.

186

8.2.2 Projektion auf den Modellraum

Durch Projektion eines Normalenfelds auf den Raum des statistischen Modells kann dieses in die Rekonstruktion des vorherigen Abschnitts integriert werden. Der in Abschnitt 6.2 erläuterte Algorithmus beschreibt, wie solch eine Projektion auf ein Normalenfeld angewendet werden kann. Die ersten beiden Spalten in Abbildung 8.11 zeigen das Ergebnis der reinen Shape-from-Shading-Rekonstruktion. Durch Ermitteln und Anwenden der optimalen Modellparameter erhält man ein Normalenfeld, welches durch den Modellraum abgedeckt ist. Integriert man dieses Normalenfeld, erhält man wiederum ein Gesichtsmodell. Als Eingabebild dient das in Abbildung 8.9 dargestellte Gesicht. Die resultierenden Gesichtsmodelle sind in der dritten und vierten Spalte in Abbildung 8.11 zu sehen.

Es stehen nur vier Beispieldaten als Trainingsdaten für den Aufbau des statistischen Modells zur Verfügung. Die daraus ermittelten Eigengesichter wurden in Abschnitt 5.6.3 eingeführt und in Abschnitt 8.1.2 dargestellt. Die daraus möglichen Kombinationen von realen Gesichtern sind begrenzt, da zu wenige Eigenschaften in den Eigengesichtern abgebildet sind. Dies führt dazu, dass die Gesichtsform des rekonstruierten Gesichts dem tatsächlichen Gesicht nicht ähnlich ist. Ein weiterer Grund hierfür ist die einmalige Projektion in den Modellraum ohne Weiterverabeitung des resultierenden Normalenfelds. Es können nur Formen rekonstruiert werden, die durch den Modellraum darstellbar sind. Somit gehen viele Detailinformationen verloren.

Abbildung 8.11 zeigt, dass das resultierende Gesichtsmodell deutlich mehr Tiefe besitzt, als das bei der Rekonstruktion mittels Shape-from-Shading der Fall ist. Eingedrückte Gesichtspartien wie Nase und Mund kommen als Proﬁl zum Vorschein und entsprechen eher einem realistischen Gesicht.

187

8 Tests und Bewertung

Abbildung 8.11: Die erste und zweite Spalte zeigen die Rekonstruktion des Standardkopfs

mit dem reinen Shape-from-Shading-Algorithmus. Durch Projektion auf den

188

8.2.3 Kombination des Shape-from-Shading mit dem statistischen Modell

Dieser Abschnitt bewertet die Resultate der Kombination des Shape-from-Shading-Frameworks mit dem statistischen Modell. Dies geschieht unter Verwendung des in Abschnitt 6.3 erläuterten Algorithmen. Es wird nun gezeigt wie sich das iterative Anpassen des Modells auf das resultierende Gesichtsmodell auswirkt.

Die erste Spalte in Abbildung 8.13 zeigt das initiale Gesichtsmodell, welches aus dem Durchschnittskopf ermittelt wird. In der zweiten Spalte ist das Ergebnis nach einer Iteration zu sehen. Hierbei wurde das initiale Normalenfeld auf den Modellraum projiziert und im zweiten Schritt durch die Rückrotation der Normalen auf den Kegel wieder die harte Bedingung erfüllt. Es ist ersichtlich, dass durch das Modell fehlerhafte Normalen korrigiert werden, sodass das Gesicht mehr Proﬁl aufzeigt. Durch die Erfüllung der harten Bedingung werden die Normalen wiederrum an das durch die Initialisierung geschätzte Normalenfeld angenähert. Diese wechselseitige Kombination führt mit zunehmenden Iterationen dazu, dass die Normalenrichtungen Schritt für Schritt korrigiert werden um die optimale Position auf dem Kegel zu ﬁnden. Nach drei Iterationen erhält man die dritte Spalte. Führt man den Algorithmus aus, bis sich nur noch minimale Änderungen ergeben, entsteht ein Gesichtsmodell wie es in der vierten Spalte zu sehen ist.

Die Region direkt unterhalb des Kinns ist sehr dunkel und kann daher nur schlecht rekonstruiert werden. Wie man vor Allem in den ersten drei Reihen von Abbildung 8.13 sehen kann, treten dort Fehler auf. Unter dem Kinn entsteht eine Kante, welche sich stark nach außen wölbt.

Bei allen bisherigen Rekonstruktionen sind die Ohren nach der Integration ﬂach und nur leicht nach außen gerichtet. Dies lässt sich anhand der zweiten Reihe in Abbildung 8.13 nochmals nachvollziehen. Die Ohren besitzten feine Wölbungen und Unebenheiten. Solche feinen Unterschiede sind nur schlecht zu rekonstruieren und werden bei der Integration geglättet. Dadurch erscheinen die Ohren ﬂach und ohne Struktur.

Die Proﬁlbilder der einzelnen Iterationsschritte sind in der dritten und sechsten Zeile gezeigt. An diesen lässt sich nachvollziehen, dass durch das iterative Anpassen des Normalenfelds das Proﬁl der Gesichtsmodelle markanter wird. Dies liegt vor Allem daran, dass fehlerhafte Normalenrichtungen nach und nach verbessert

189

8 Tests und Bewertung

werden.

Die Integration des statistischen Modells in ein Shape-from-Shading-Framework bringt zusammenfassend zwei Vorteile mit sich. Zum Einen werden fehlerhafte Normalenrichtungen durch das Modell korrigiert und so typische Shape-from-Shading-Schwächen ausgeglichen. Zum Anderen kann das Shape-from-Shading individuelle Eigenschaften der Gesichter rekonstruieren. Eine solche Eigenschaft ist beispielsweise eine Lachfalte, welche in Abbildung 8.12 zu sehen ist. Das zweite

Abbildung 8.12: Die rekonstruierten Gesichtsmodelle zeigen individuelle Eigenschaften, wie

beispielsweise Lachfalten.

und dritte Bild zeigen einen Ausschnitt aus dem linken Eingangsbild. Die Lachfalten sind deutlich zu erkennen, auch wenn die Textur nicht auf dem Gesichtsmodell liegt.

190

Abbildung 8.13: Durch Kombination von Shape-from-Shading mit einem statistischen Modell

entsprechen die Gesichtsmodelle mehr der Form des tatsächlichen Gesichts.

8 Tests und Bewertung

8.3 Experimente

In diesem Abschnitt werden anhand einiger Experimente die Möglichkeiten des in dieser Arbeit vorgestellten Verfahrens demonstriert. Als Grundlage der Rekonstruktionen dienen gerenderte Abbildungen des Standardgesichts aus [MMPI]. Es werden drei Bedingungen an die zur Rekonstruktion verwendeten Portraitfotograﬁen gestellt. Dabei handelt es sich um eine frontale Abbildung des Gesichts, um eine frontale Beleuchtung und um eine möglichst geringe perspektivische Verzerrung. Im Folgenden wird die Relevanz jeder dieser Bedingungen getestet, und die Resultate bei Missachtung aufgezeigt.

8.3.1 Drehung des Kopfes

Es wird bei der Rekonstruktion der Gesichtsmodelle davon ausgegangen, dass die Gesichter von vorne fotograﬁert wurden. In der ersten Spalte von Abbildung 8.14 ist das Durchschnittsgesicht aus verschiedenen Blickwinkel zu sehen. Der Vektor zwischen Kamera und Gesicht weicht um 5°, 10°, 15°, 30° und 45° von einer fontralen Darstellung ab. Diese gerenderten Bilder dienten als Grundlage für die in Spalte 2, 3 und 4 abgebildeten Rekonstruktion. Die rekonstruierten Gesichtsmodelle wurden leicht seitlich beleuchtet und mit lambertschen Verhalten gerendert.

Es ist zu erkennen, dass die Qualität mit steigendem Rotationswinkel stark abnimmt. Dies beruht auf zwei verschiedenen Ursachen. Das statistische Modell beruht nur auf den Normalen der Oberﬂäche von Gesichtern. Diese ändern ihre absoluten Werte mit Rotation des Gesichtes. Das heißt die Normalen eines rotierten Gesichtes werden nicht mehr durch das hier verwendete Modell abgebildet.

Ein zweiter Grund liegt in der Rekonstruktion von 2,5D-Daten. Ein von vorne betrachtetes Gesicht verdeckt sich an keiner Stelle selbst. Wird es gedreht, verdeckt irgendwann die Nase einen Teil der Wange. Diese Überdeckung kann aber durch das Shape-from-Shading nicht erkannt werden. Es wird also eine zusammenhängende Oberﬂäche generiert, bei der die Nase so stark geglättet wird das ihre Spitze direkt in die Wange übergeht.

Beide Eﬀekte zusammen führen schließlich zu den in Abbildung 8.14 erkennbaren Fehlern bei der Rekonstruktion. Das Ergebniss wird bei starker Rotation stark geglättet und es sind keine charakteristischen Gesichtszüge der Person mehr

192

zu erkennen.

193

8 Tests und Bewertung

Abbildung 8.14: Rekonstruktion von nicht frontal abgebildeten Gesichtern. Die erste Spalte

enthält die Eingangsbilder für die Rekonstruktion. Die zweite, dritte und

vierte Spalte enthält das resultierende Gesichtsmodell.

194

8.3.2 Änderung der Beleuchtungsrichtung

Möchte man eine Oberﬂäche mit Hilfe von Shape-from-Shading rekonstruieren, ist es wichtig zu wissen, wie die Oberﬂäche bei deren Abbildung beleuchtet wurde. Bei dem in dieser Arbeit vorgestellten Verfahren wird von einer einzelnen Lichquelle ausgegangen. Diese muss zentriert in einem möglichst großen Abstand vor dem zu rekonstruierenden Gesicht positioniert sein. In diesem Abschnitt soll gezeigt werden wie sich die Qualität der Rekonstruktion verändert wenn die Position der Lichtquelle von der vorgeschriebenen Postion abweicht.

Dazu wurde das Durchschnittsgesicht mit unterschiedlich positionierter Lichtquelle gerendert. In der ersten Spalte von Abbildung 8.15 sind diese gerenderten Bilder dargestellt. Die Lichquelle wurde bei gleichem Abstand um den Kopf rotiert, und dieser mit lambertschen Verhalten gerendert. Der Winkel zwischen der idealen Position und der tatsächlichen Lage der Lichtquelle nimmt mit jeder Zeile zu und beträgt 5°, 10°, 15°, 30° und 45°.

Man kann erkennen, dass die Genauigkeit der Rekonstruktion mit steigendem Winkel stetig abnimmt. Das Shape-from-Shading geht bei der Rekonstruktion von einer Positionierung der Lichtquelle aus Richtung der Kamera aus. Weicht sie davon ab, werden die Normalen der Oberﬂäche falsch berechnet. Beim Anpassen des statistischen Modells dienen diese Normalenfelder als Grundlage. Da diese nicht mehr korrekt sind, können sie nicht mehr durch das Modell abgebildet werden und die Rekonstruktion ist nicht möglich.

Ein weiteres Problem ist die Ausleuchtung des Gesichts. Wird das Gesicht zu stark von der Seite beleuchtet, liegen große Teile der anderen Gesichtshälfte komplett im Dunkeln. Dadurch stehen hier überhaupt keine Informationen mehr zur Rekonstruktion zur Verfügung.

Da das Modell bei einer großen Abweichung nicht an das Normalenfeld angepasst werden kann und wegen des Informationsverlust durch ein nicht komplett beleuchtetes Gesicht, ist eine qualitativ hochwertige Rekonstruktion nicht möglich. Die rekonstruierten Gesichter werden durch die großen schwarzen Flächen sehr ﬂach und durch die ungenau ermittelten Normalenfelder des Modells zusätzlich geglättet.

195

8 Tests und Bewertung

Abbildung 8.15: Rekonstruktion nicht frontal beleuchteter Gesichter. Die erste Spalte ent- die Eingangsbilder für die Rekonstruktion. Die zweite, dritte und vierte

Spalte enthält das resultierende Gesichtsmodell.

196

8.3.3 Perspektivische Verzerrung

Als dritter Punkt wird nun die Wirkung der perspektivischen Verzerrung untersucht. Das hier verwendete Modell besteht aus Normalenfeldern, die aus orthograﬁsch projizierten Gesichtsmodellen ermittelt wurden. Eine unter realen Umständen entstandene Gesichtsfotograﬁe besitzt jedoch eine perspektivische Verzerrung.

Um diese Verzerrung in Abbildung 8.17 zu simulieren wurde der Abstand zwischen Kamera und Gesichtsmodell erhöht und der Zoom der Kamera daraufhin angepasst. Die entstandenen Bilder sind in der ersten Spalte zu sehen. Es ist zu erkennen, dass das erste Bild eine starke perspektivische Verzerung besitzt und sich dann Schritt für Schritt einer orthograﬁschen Projektion annähert.

Die zugehörigen Rekonstruktionsergebnisse sind umso schlechter, je stärker die perspektivische Verzerrung ist. Dies lässt sich vor Allem an den Bilder der dritten und vierten Spalte in Abbildung 8.17 verdeutlichen. Vergleicht man die Ergebnisse in der letzten Reihe mit denen, welche unter optimalen Umständen entstanden sind, ähneln sie sich. Dies liegt daran, dass der Abstand zwischen Gesicht und Kamera sehr groß ist. Abbildung 8.16 zeigt, dass sich die Verzerrung mit zunehmendem Abstand verringert.

Abbildung 8.16: Umso größer der Abstand ist, desto geringer ist die perspektivische Verzer-

zerrung kann das Bild nicht auf das Modell angepasst werden. Daraus folgt, dass

197

8 Tests und Bewertung

das Modell die Rekonstruktion nicht in allen Bereichen des Gesichts unterstützen kann.

Abschließend kann man sagen, dass eine perspektivische Verzerrung die Rekonstruktion erschwert und die Ergebnisse deutlich ungenauer sind. Es ist also notwendig, bei den Fotograﬁen darauf zu achten, dass die Verzerrung so gering wie möglich ist.

198

Abbildung 8.17: Rekonstruktion nicht orthogonal abgebildeter Gesichter. Die erste Spalte ent- die Eingangsbilder für die Rekonstruktion. Die zweite, dritte und vierte

8 Tests und Bewertung

8.4 Rekonstruktion aus Fotograﬁen

Im vorherigen Abschnitt wurden gerenderte Bilder zur Rekonstruktion verwendet. Hier sollen nun die aus realen Fotograﬁen erzielten Ergebnisse aufgezeigt werden.

Hierfür wurde folgendes Equiptment verwendet:

• Kamera: Canon, EOS 350D,

• Objektiv: Canon, EFS 18-55mm,

• Lichtquelle: Dedolight, DLH4 Tungsten Light Head.

Die Kamera wurde in einem Abstand von 3m auf Augenhöhe des Probanten platziert. Die Lichtquelle wurde direkt neben der Kamera positioniert. Sie wurde so abgeblendet, dass nur das Gesicht ausgeleuchtet wurde. Dadurch sollte das Reﬂektieren von Licht an den Wänden des Raums verhindert werden.

In den Abbildungen 8.18, 8.19, 8.20 und 8.21 sind die jeweiligen Fotograﬁen und die rekonstruierten Ergebnisse dargestellt. In der ersten Zeile sind jeweils die Fotograﬁen abgebildet. Bei diesen wurden die Gesichter ausgeschnitten und ihre Größe an das Durchschnittsgesicht angepasst. Die Rekonstruierten Objekte sind darunter mit lambertschen Reﬂektionsverhalten abgebildet. Bei den Objekten in der linken Spalte wurde zum Rendern das Eingangsbild als Textur verwendet.

In den rekonstruierten Objekten sind deutlich die fotograﬁerten Personen zu erkennen. Dies liegt hauptsächlich an den sehr kontrollierten Bedingungen bei der Aufnahme.

In der folgenden Tabelle sind die Laufzeiten für die einzelnen Rekonstruktionen dargestellt. Zusätzlich wurden die Iterationsschritte gezählt, bis das ﬁnale Nor-

Proband 7 Proband 1 (Abbildung 8.19) Proband 2 (Abbildung 8.20) Proband 8 Proband 3 (Abbildung 8.18) Proband 5 10 22,1 (≈ 2,2) Proband 9 10 Proband 4 (Abbildung 8.21) Proband 6

200

malenfeld ermittelt wurde. Eine durchschnittliche Rekonstruktion dauert ca. 34 Sekunden und benötigt ca. 16 Iterationsschritte. Ein Iterationsschrit benötigt im Schnitt ca. 2 Sekunden. Die Laufzeiten zur Rekonstruktion eines Gesichts sind daher stabil und es gibt nur selten Ausreißer wie Proband 6 aus der Tabelle.

201

8 Tests und Bewertung

Abbildung 8.18: Rekonstruktion aus einer Fotograﬁe (Proband 3)

202

8.4 Rekonstruktion aus Fotograﬁen

Abbildung 8.19: Rekonstruktion aus einer Fotograﬁe (Proband 1)

203

8 Tests und Bewertung

Abbildung 8.20: Rekonstruktion aus einer Fotograﬁe (Proband 2)

204

8.4 Rekonstruktion aus Fotograﬁen

Abbildung 8.21: Rekonstruktion aus einer Fotograﬁe (Proband 4)

205

8 Tests und Bewertung

206

Kapitel 9

Zusammenfassung und Ausblick

Im Rahmen dieser Arbeit wurde ein Framework zur Rekonstruktion von Gesichtsmodellen aus einzelnen Portraitfotograﬁen vorgestellt. In das entwickelte Shapefrom-Shading-Framework wurde ein statistisches Modell integrieren. Dieses basiert auf Oberﬂächennormalen. Als Trainingsgesichter des Modells dienen vier 3D-Scans der [MMPI].

Es wurden drei Algorithmen zur Rekonstruktion von Gesichtsmodellen vorgestellt. Davon basiert einer auf der Glättung der Oberﬂäche als weiche Bedingung und die beiden anderen auf der Kombination von Shape-from-Shading und dem statistischen Modell. Die zweite Variante fügt nach dem Shape-from-Shading einmalig eine Abbildung auf den Modellraum hinzu. Die resultierenden Normalen müssen daher vollständig in den Trainingsgesichter vorhanden sein. Man spricht hierbei auch von einem modellorientierten Verfahren. Der andere Algorithmus ist iterativ. Hier ist das Modell die weiche oder auch statistische Bedingung des geometrischen Shape-from-Shading-Frameworks. Das Modell wird in jeder Iteration an das geschätzte Normalenfeld angepasst. Dabei müssen die angepassten Normalenfelder die harte Bedingung der Bildrückstrahlfunktion erfüllen. Dieses Verfahren konvergiert, wenn sich zwischen zwei Iterationsschritten das Normalenfeld kaum noch verändert.

Alle Algorithmen lassen sich auf einem handelsüblichen Computer ausführen. Die Ergebnisse der beiden Verfahren, welche das statistische Modell verwenden, enthalten keine typischen Shape-from-Shading-Fehler, wie zum Beispiel nach in-

207

9 Zusammenfassung und Ausblick

nen gewendete Nasen. Das erste dieser beiden Verfahren schneidet dabei deutlich schlechter ab als das zweite. Dies lässt sich vor allem damit erklären, dass das Modell einen Raum möglicher Normalenfelder aufspannt. Die resultierenden Normalenfelder müssen in diesem Raum enthalten sein, weil sie aus den im Modell gespeicherten Eigenschaften aufgebaut werden. Da die Datenbasis aus nur vier Gesichtern besteht, ist dieser Modellraum sehr begrenzt. Die Ergebnisse der Rekonstruktion, unter Verwendung einer Kombination von Shape-from-Shading und dem statistischen Modell, sind dagegen vielversprechend. Die rekonstruierten Gesichtsmodelle entsprechen den an das Verfahren gestellten Anforderungen. Die Gesichter behalten Eigenschaften, welche durch einen modellorientierten Ansatz verloren gehen. Dies bedeutet, dass trotz des Einsatzes eines statistischen Modells, individuelle Gesichtscharakteristika rekonstruiert werden können.

Die Rekonstruktion kann in einigen Bereichen verbessert und erweitert werden. Als wichtigster Punkt ist dabei das Finden einer geeignete Datenbank als Trainingsdaten des Modells zu nennen. Die vier verwendeten Gesichtscans reichen nicht aus um einen Modellraum aufzuspannen, der in der Lage ist eine Großzahl möglicher Gesicht nachzubilden. Um solch einen Modellraum aufzubauen sind mindestens 200 Gesichtscans notwendig. Dabei sollten Scans männlicher und weiblicher Gesichter zu gleichen Anteilen vorhanden sein. Daraus ergeben sich dann etwa 40 verschiedene relevante Eigengesichter. Diese beschreiben genügend Eigenschaften der Gesichter um nahezu jedes reale Gesicht nachzubilden. Darin sind dann jedoch noch immer keine Charakteristika wie individuelle Falten oder ähnliches enthalten. Um diese zu Rekonstruieren wird nach wie vor Shape-from-Shading verwendet.

Im Bereich des Shape-from-Shading gibt es ebenfalls eine Reihe von möglichen Punkten, die zu einem realistischeren Ergebnis führen. Ein solches Verfahren ist abhängig von der Genauigkeit des verwendeten Beleuchtungsmodells. Über dieses wird das Verhalten der zu rekonstruierenden Oberﬂäche deﬁniert. Weicht das Beleuchtungsmodell zu stark vom eigentlichen Verhalten der Oberﬂäche ab, ist es unmöglich eine wahrheitgetreue Oberﬂäche zu ermitteln. In dieser Arbeit wurde das Lambertsche Gesetz als Bildrückstrahlfunktion verwendet. Hierbei wird von einer perfekt diﬀusen Oberﬂäche ausgegangen. Ein Gesicht zeigt jedoch in der Realität ein wesentlich komplexeres Verhalten. Deswegen wäre ein komplexere Abstraktion des Rückstrahlverhaltens in der Lage, genauere Normalenrichtungen

208

zu ermitteln.

Ein weiteres Problem des hier beschriebenen Verfahrens besteht in der Unterteilung in Ermitteln der Oberﬂächennormalen und Integrieren der Normalenfelder. Das Problem der zu glatten Oberﬂächen beim Shape-from-Shading wurde durch das Verwenden der Bildrückstrahlfunktion als harte Bedingung umgangen. Bei der Integration werden aber ebenfalls Annahmen über die Glattheit der Oberﬂäche getroﬀen. Hier gibt es verschiedene Möglichkeiten [Smi07] das Shape-from-Shading-Verfahren so zu verändern, dass direkt ein integrierbares Normalenfeld entsteht. Dadurch müssen die Normalen beim Integrieren nicht mehr durch zusätzliche Oberﬂächenbedingungen verändert werden.

Weiterhin gehen alle Bereiche des in dieser Arbeit vorgestellten Shape-from-Shading-Verfahrens von frontaler Beleuchtung und Abbildung der zu rekonstruierenden Gesichter aus. Diese Bedingungen schränken den Einsatzbereich des Verfahrens stark ein. Es ist also sinnvoll herauszuﬁnden, in wie weit diese Einschränkungen umgangen werden können.

Die Kombination eines statistischen Modells mit einem Shape-from-Shading-Framework ist vielversprechend. Daher lässt sich abschließend sagen, dass das in dieser Arbeit untersuchte und erarbeitete Rekonstruktionsverfahren für Passfotograﬁen eine gute Grundlage für Erweiterungen bietet.

209

9 Zusammenfassung und Ausblick

210

Abbildungsverzeichnis

2.1 Der Ames-Raum ist eine optische Täuschung. Bildnachweis: [Enc]. 6

2.2 Hell-Dunkel-Verläufe vermitteln den Eindruck einer Wölbung. Dunkel- Hell-Verläufe vermitteln dagegen den Eindruck eines Lochs. Bild angelehnt an: [Smi07]. . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.3 Gregorys Maske. Bildnachweis: [Smi07]. . . . . . . . . . . . . . . . 7

2.4 Das menschliche Gehirn kann anhand einer Ansammlung von Punk- ten die abgebildeten Objekte rekonstruieren, ohne diese direkt zu erkennen. In dem Bild ist eine Szene mit einem Dalmatiner im mittleren Bildbereich zu sehen. Bildnachweis: [Tö05]. . . . . . . . . 8

211

Abbildungsverzeichnis

3.6 Jedem (x, y)-Tupel ist ein Intensitätswert I(x, y) zugeordnet. . . . 22 3.7 Ein Bildpunkt besitzt eine 4er- und eine 8er-Nachbarschaft. . . . . 22 3.8 Symmetrische Ableitung eines diskreten Bildsignals in x-Richtung. 23 3.9 Das Bild wird mit einer 3×3-Maske gefaltet. Hierfür wird die Maske über jeden Bildpunkt gelegt und der neue Wert berechnet. . . . . . 25 3.10 Darstellung einer Oberﬂäche als Höhenfeld. . . . . . . . . . . . . . 30 3.11 Zusammenhang zwischen Gradienten und Normale einer Oberﬂäche. 31 3.12 Integrierbares Gradientenfeld. . . . . . . . . . . . . . . . . . . . . . 32 3.13 Nicht integrierbares Gradientenfeld. . . . . . . . . . . . . . . . . . . 33 3.14 Darstellung einer Oberﬂäche als Punktwolke. . . . . . . . . . . . . 33 3.15 Darstellung einer Oberﬂäche als Polygonales Netz. . . . . . . . . . 34 3.16 Links konvexes Polygon, rechts nicht konvexes Polygon. . . . . . . 34 3.17 Planares Polygon. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.18 Nicht planares Polygon. . . . . . . . . . . . . . . . . . . . . . . . . 35 3.19 Half Edge Datenstruktur . . . . . . . . . . . . . . . . . . . . . . . . 36

4.1 Komponenten einer Reﬂektion. . . . . . . . . . . . . . . . . . . . . 40 4.2 Verkürzung durch den Einfallwinkel des Lichts. . . . . . . . . . . . 41 4.3 Perspektivische Verkürzung bei Raumwinkeln . . . . . . . . . . . . 42 4.4 Schematischer Aufbau einer Kamera. . . . . . . . . . . . . . . . . . 44 4.5 Zusammenhang zwischen der Strahldichte einer Oberﬂäche und der

Kamera. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.6 Unterscheidung von BRDF und BTDF. . . . . . . . . . . . . . . . 47 4.7 Geometrie einer Reﬂektion. . . . . . . . . . . . . . . . . . . . . . . 48 4.8 Gesetz der Helmholtz-Reziprozität. . . . . . . . . . . . . . . . . . . 49 4.9 Konvex/konkav Vieldeutigkeit. . . . . . . . . . . . . . . . . . . . . 52 4.10 Aufbau des Verfahrens zur Oberﬂächenrekonstruktion mittels Shapefrom-Shading. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.11 Geometrie bei der Korrektur auf lambertsches Verhalten. . . . . . . 58 4.12 Monoton fallendes, isotropes Reﬂektionsverhalten (rechts) und Reﬂektionsverhalten nach Lambert (links). . . . . . . . . . . . . . . . 59 4.13 Projektion der Intensitäten auf eine Einheitskugel. . . . . . . . . . 61 4.14 Transformation zwischen Einheitskugel und Bildebene. . . . . . . . 62 4.15 Gradienten in diskreten Abbildungen. . . . . . . . . . . . . . . . . 64

212

Abbildungsverzeichnis

5.14 Die 16 Bilder dienen als Basis für eine Hauptkomponentenanalyse. Bildnachweis: [TP91a]. . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.15 Die ersten beiden Spalten beinhaltet sehr große und kleine Grau-

stellen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.17 Schematischer Aufbau des intrinsischen und extrinsischen Mittels. Bild angelehnt an: [BWHK07]. . . . . . . . . . . . . . . . . . . . . 103 5.18 Eine exponential map bildet einen Ortvektor p der Tangentialebene T b S ² auf einen Punkt Exp b (p) auf der Einheitskugel S ² ab.

Exp b (p) und b. Seine Richtung bleibt ebenfalls erhalten. . . . . . . 104 5.19 Mit einer Korrespondenz zwischen Gesichtern lassen sich durch lineare Interpolation Zwischengesichtern bilden. . . . . . . . . . . . . 108 5.20 Der Aufbau eines Modells für Oberﬂächennormalen lässt sich grob

5.21 Das Rechteck bewegt sich zwischen den Bildern ein Stück nach

5.22 Die Normalenfelder werden durch Projektion des Gesichtsmodells

5.23 Um zwei Gesichter aufeinander auszurichten reicht es nicht aus die

214

Abbildungsverzeichnis

5.36 Das Vektorfeld s beschreibt den optischen Fluss zwischen I 1 und I 2 .

5.37 Bei der bilinearen Interpolation wird zwischen den Helligkeitswer-

Auﬂösungsstufen I 1m , I 2m und die Laplacepyramiden L 1m , L 2m . . . 138 5.39 Zunächst wird das Vektorfeld überabgetastet und dann mit dem Faktor 2 skaliert. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 5.40 Mit dem ermittelten optischen Fluss kann das Bild I 2 durch einen Rückwärts-Warp Bild I 1 angeglichen werden. . . . . . . . . . . . . 139 5.41 Bei einer grob-zu-fein-Strategie wird das Verschiebungsfeld mit jeder Stufe verfeinert. . . . . . . . . . . . . . . . . . . . . . . . . . . 140 5.42 Ein 3D-Scan kann durch vier Texturen dargestellt werden. Dabei werden die drei Farbkanäle R, G und B getrennt betrachtet. . . . . 141 5.43 Zwei dreidimensionale Laserscans werden in vier Ausgangstexturen

5.44 Auswirkungen einer Glättung der Verschiebungsvektoren auf jeder Pyramidenstufe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 5.45 Zu sehen sind zwei Gesichtsmodelle, welche unterschiedliche Ge-

5.47 Das neue Gesicht besitzt die Form des Referenzgesichts und die Oberﬂächennormalen des Beispielgesichts aus Abbildung 5.45. . . . 150

216

217

Abbildungsverzeichnis

8.12 Die rekonstruierten Gesichtsmodelle zeigen individuelle Eigenschaften, wie beispielsweise Lachfalten. . . . . . . . . . . . . . . . . . . . 190 8.13 Durch Kombination von Shape-from-Shading mit einem statisti-

8.15 Rekonstruktion nicht frontal beleuchteter Gesichter. Die erste Spal-

Verzerrung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 8.17 Rekonstruktion nicht orthogonal abgebildeter Gesichter. Die erste

8.18 Rekonstruktion aus einer Fotograﬁe (Proband 3). . . . . . . . . . . 202 8.19 Rekonstruktion aus einer Fotograﬁe (Proband 1). . . . . . . . . . . 203 8.20 Rekonstruktion aus einer Fotograﬁe (Proband 2). . . . . . . . . . . 204 8.21 Rekonstruktion aus einer Fotograﬁe (Proband 4). . . . . . . . . . . 205

218

Literaturverzeichnis

[AGR96a] Atick, J. J. ; Griffin, P. A. ; Redlich, A. N.: Statistical Approach

[AGR96b] Atick, J. J. ; Griffin, Paul A. ; Redlich, A. N.: The vocabulary of

[BAHH92] Bergen, J. R. ; Anandan, P. ; Hanna, K. J. ; Hingorani, R.: Hier-

Literaturverzeichnis

[BKY97] Belhumeur, P. ; Kriegman, D. ; Yuille, A. The bas-relief ambiguity. 1997

[Bla00] Blanz, V.: Automatische Rekonstruktion der dreidimensionalen

[BSP93] Beymer, D. ; Shashua, A. ; Poggio, T.: Example Based Image

[BV99] Blanz, V. ; Vetter, T.: A morphable model for the synthesis of 3D faces. In: Computer Graphics Proceedings (1999), S. 187-194

[BV03] Blanz, V. ; Vetter, T.: Face Recognition Based on Fitting a 3D

[BWHK07] Brun, A. ; Westin, C.-F. ; Herberthson, M. ; Knutsson, H.:

[Cam95] Camus, T. A.: Real-Time Optical Flow. 1995 ( CS-94-36). - Forschungsbericht

[Car92] do Carmo, M. P.: Riemannian Geometry. Birkhäuser, 1992

[CG98] Conway, J. H. ; Guy, R. K.: The Book of Numbers. Berlin, Heidelberg. New York : Springer, 1998. - ISBN 978-0387979939

220

221

Literaturverzeichnis

[Gre97] Gregory, R. L.: Knowledge in perception and illusion. In: Phil.

[HB86] Horn, B. K. P. ; Brooks, M. J.: The Variational Approach to Shape from Shading. In: CVGIP 33 (1986), February, Nr. 2, S. 174-208

[HB94] Hearn, D. ; Baker, M. P.: Computer graphics. Englewood Cliﬀs Prentice-Hall, 1994

[Hor70] Horn, B. K. P.: Shape From Shading: A method for optaining the

richt

[Hor81] Horn, B. K. P.: Hill Shading and the Reﬂectance Map. In: PIEEE 69 (1981), January, Nr. 1, S. 14-47

[Hor90] Horn, B. K. P.: Height and Gradient from Shading. In: IJCV 5

[Kir87] Kirby, L. S.: Turbulence and the dynamic of coherent structures. In: Quart. Appl. Math. XLV 3 (1987), S. 561-590

222

[NRH ⁺ 22] Nicodemus, F. E. ; Richmond, J. C. ; Hsia, J. J. ; Ginsberg,

Literaturverzeichnis

[Pen90] Pentland, A. P.: Shape Information from Shading: A Theory about Human Perception. In: SV 4 (1990), Nr. 3/4, S. 165-182

[Pen99] Pennec, X. Probabilities and statistics on riemannian manifolds:

[PTVF92] Press, W. H. ; Teukolsky, S. A. ; Vetterling, W. T. ; Flanne-

[RKH05] Robles-Kelly, A. Hancock, E.

Schumann, H. Mueller, W.: Visualisierung,

[Smi07] Smith, W. A. P.: Statistical Methods For Facial Shape-from-shading and Recognition, University of York, Diss., February 2007

[Sny83] Snyder, J.: Map Projections-A Working Manual. United States Government Printing, 1983. - ISBN 9998605067

[Sto02] Stone, M.: Field Guide to Digital Color. Natick, MA, USA : A. K.

[TP91a] Turk, M. ; Pentland, A. P.: Eigenfaces for Recognition. In: CogNeuro 3 (1991), Nr. 1, S. 71-96

224

Kompletter Text

Beschreibung

Ähnliche Arbeiten

Kommentare

Kommentieren

Neuigkeiten

So funktioniert's

Ähnliche Arbeiten

Facebook

Neuigkeiten

Bücher zum Thema

Autor

Kompletter Text

Beschreibung

Ähnliche Arbeiten

Kommentare

Kommentieren

Neuigkeiten

So funktioniert's

Ähnliche Arbeiten

Facebook

Neuigkeiten

Bücher zum Thema

Registrieren oder einloggen

Neu hier?

Einloggen

Die Alternative

Passwort vergessen?

Neues Passwort anfordern