Interaktive Erzeugung von 3D Gesichtsmodellen aus einer Fotografie im Auftrag der LOOXIS GmbH - www.looxis.com

Inhaltsverzeichnis

1 Einleitung
1.1 Motivation
1.2 Zielsetzung
1.3 Aufbau der Arbeit

2 3D Gesichtsmodelle aus Fotografien
2.1 Shape-from-X
2.2 Statistisches Modell
2.3 Kombination von Shape-from-Shading und statistischem Modell

3 Grundlagen
3.1 Koordinatensysteme
3.1.1 Kartesische Koordinaten
3.1.2 Kugelkoordinaten
3.1.3 Geographische Koordinaten
3.1.4 Zylindrische Koordinaten
3.2 Digitale Bildverarbeitung
3.2.1 Partielle Ableitungen von Bildern
3.2.2 Punktoperationen
3.2.3 Nachbarschaftsoperationen
3.3 Beschreibung von Oberflächen
3.3.1 Höhenfelder
3.3.2 Punktwolken
3.3.3 Polygonale Netze

4 Rekonstruktion mittels Shape-from-Shading
4.1 Reflektionsverhalten von Oberflächen
4.1.1 Differentielle Raumwinkel
4.1.2 Relevanz des Einfallwinkels für die Lichtintensität
4.1.3 Strahldichte und Bestrahlungsstärke
4.1.4 Lichtmessung mit Kameras
4.1.5 Bidirectional Reflectance Distribution Function
4.1.6 Das Lambertsche Gesetz
4.2 Shape-from-Shading
4.2.1 Bestehende Shape-from-Shading-Verfahren
4.3 Konzept
4.4 Vorverarbeitung der Fotografien
4.4.1 Intensitäten und Alphakanal ermitteln
4.4.2 Lambertsche Reflektion korrigieren
4.4.3 Bildgradienten berechnen
4.5 Das Shape-from-Shading-Framework
4.5.1 Die Rückstrahlfunktion der Abbildung als harte Bedingung
4.5.2 Die Glättung der Oberfläche als weiche Bedingung
4.5.3 Initialisierung
4.6 Integrieren des Normalenfeldes
4.6.1 Orthogonale Projektionen
4.6.2 Die Fourier-Transformation
4.6.3 Integration
4.7 Aufbereiten der Höhenfelder

5 Statistisches Modell für Oberflächennormalen
5.1 Grundlagen zur Analyse von dreidimensionalen Laserscans
5.1.1 Dreidimensionale Laserscans
5.1.2 Projektionen
5.1.3 Eigenwerte und Eigenvektoren
5.1.4 Hauptkomponentenanalyse
5.1.5 Mittelwertbildung von Einheitsvektoren
5.2 Statistische Modelle für Gesichter
5.2.1 Eigenbilder und Eigengesichter
5.2.2 Dreidimensionale statistische Modelle
5.3 Aufbau des statistischen Modells
5.4 Korrespondenzbestimmung
5.4.1 Optischer Fluss von Bildfolgen
5.4.2 Hinzuziehen von Nachbarschaften
5.4.3 Bildpaare
5.4.4 Grob-zu-fein-Strategie
5.4.5 Korrespondenzbestimmung zwischen 3D Scans
5.4.6 Glätten der Vektorfelder
5.5 Bestimmung von Normalenfeldern
5.5.1 Ausrichten der Trainingsdaten
5.5.2 Ermitteln der Normalenfelder
5.6 Analysieren der Normalenfelder
5.6.1 Bestimmen eines mittleren Normalenfelds
5.6.2 Überführen in einen linearen Raum
5.6.3 Ermitteln der Modelleigenschaften

6 Modellgestütze Rekonstruktion
6.1 Rekonstruktion durch Shape-from-Shading und Glätten der Ober- fläche
6.2 Rekonstruktion durch Projektion auf den Modellraum
6.3 Kombination des Shape-from-Shading mit dem statistischen Modell

7 Realisierung
7.1 Architektur
7.1.1 Aufbau des Modells
7.1.2 Rekonstruktion der Gesichtsmodelle
7.2 Umsetzung
7.2.1 Hardware
7.2.2 Software

8 Tests und Bewertung
8.1 Aufbau des Modells
8.1.1 Korrespondenzbestimmung
8.1.2 Visualisierung der Eigengesichter
8.2 Rekonstruktion der Gesichtsmodelle mit den verschiedenen Algo- rithmen
8.2.1 Rekonstruktion mittels Shape-from-Shading
8.2.2 Projektion auf den Modellraum
8.2.3 Kombination des Shape-from-Shading mit dem statistischen Modell
8.3 Experimente
8.3.1 Drehung des Kopfes
8.3.2 Änderung der Beleuchtungsrichtung
8.3.3 Perspektivische Verzerrung
8.4 Rekonstruktion aus Fotografien

9 Zusammenfassung und Ausblick

Abbildungsverzeichnis

Literaturverzeichnis

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 Überraschungseffekt 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 Diplom- arbeit die Basis für ein solches Verfahren geschaffen werden.

1.2 Zielsetzung

Das Ziel dieser Arbeit ist es, ein Verfahren zu entwickeln, welches die Rekonstruk- tion eines 3D-Gesichtsmodells aus einem einzigen Passbild ermöglicht. Hierfür werden zwei verschiedene Herangehensweisen untersucht und schließlich kombi- niert. Zum Einen wird ein Shape-from-Shading-Framework beschrieben, welches aus Fotografien 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 mensch- lichen Wahrnehmung ein Konzept für ein Verfahren zur Rekonstruktion von 3D- Gesichtsmodellen aus einzelnen Fotografien 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, wer- den in Kapitel 3 vermittelt. In Kapitel 4 wird ein Shape-from-Shading-Framework vorgestellt. Es ermöglicht, verschiedene Bedingungen in die Rekonstruktion zu in- tegrieren. 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 Kapi- tel 6. Weiterhin wird in Kapitel 7 die Architektur des umgesetzten Verfahrens erläutert. Außerdem wird beschrieben, welche Programmiersprachen und Biblio- theken eingesetzt wurden. Die Ergebnisse und verschiedene Experimente werden in Kapitel 8 vorgestellt. Abschließend wird in Kapitel 9 die Arbeit zusammen- gefasst und ein Ausblick über mögliche Erweiterungen und Verbesserungen des Verfahrens gegeben.

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

Abbildung in dieser Leseprobe nicht enthalten

Kapitel 2

3D Gesichtsmodelle aus Fotografien

Das Sehen ist das wichtigste Werkzeug des Menschen um seine Umwelt wahr- zunehmen. 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 befinden. 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 be- zeichnet 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)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Der Ames-Raum ist eine optische Täuschung. Bildnachweis: [Enc].

Abbildung in dieser Leseprobe nicht enthalten

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].

verdeutlicht. Die Interpretation der Wölbung ist auf das visuelle System des Men- schen 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 drei- dimensionalen Form beachtet.

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

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Gregorys Maske. Bildnachweis: [Smi07].

beleuchtet ist. Auf der rechten Seite ist die selbe Gesichtsmaske abgebildet, je- doch um 180◦gedreht. Durch diese Drehung schaut man von hinten in die Maske. Die Lichtquelle befindet 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 Ge- sichts 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 abstrak- ten Abbildungen in eine möglichst einfache und bekannte Ordnung zu bringen, um somit die Objekte auf dem Bild zu erkennen.

Eine solche abstrakte Zeichnung ist in Abbildung 2.4 zu sehen. Man erkennt zu-

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Das menschliche Gehirn kann anhand einer Ansammlung von Punkten 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].

nächst nur schwarze Flecken in verschiedenen Formen und Größen. Das menschli- che 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 finden. Es gleicht sein Erinnerungsvermögen mit den Bildinforma- tionen ab und interpretiert zum Beispiel Schattierungen oder Konturen. Weitere Informationen hierzu sind in [SM00] zu finden.

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 Ver- fahren. 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 vorge- stellten Verfahren, welche das Gehirn verwendet um dreidimensionale Formen zu rekonstruieren. Darauf aufbauend wird gezeigt, wie solche Abstraktionen kombi- niert werden können um Gesichtsmodelle aus einer einzelnen Fotografie zu rekon- struieren.

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 techni- schen Abstraktionen der Verfahren, welche auf den jeweiligen verwendeten Infor- mationen beruhen, werden Shap e-from-X -Verfahren [ZTCS99] genannt. Hierbei ist das X durch die jeweilige Art der Abstraktion zu ersetzen.

- Shap e-fr om-Shading: Beim Shap e-fr om-Shading wird die Helligkeit einer Oberfläche verwendet um Rückschlüsse auf ihre Form zu ziehen. Dabei ist das Wissen über die Reflektionseigenschaften der jeweiligen Oberfläche von großer Bedeutung. Es wird versucht eine Oberfläche zu generieren, die unter gleichen Lichtverhältnissen die selben Helligkeitswerte aufweist. Da dieser Vorgang dem genauen Gegenteil von Rendervorgängen in der Computergra- fik entspricht, wird er auch als R everse R en derin g bezeichnet.
- Shap e-fr om-Stereo: Die 3D-Informationen werden aus mindestens zwei Ab- bildungen aus verschiedenen Blickwinkeln rekonstruiert. Sollten die Positio- nen der Kameras nicht bekannt sein, können sie durch verschiedene Kalibrie- rungsverfahren ermittelt werden. Zur Rekonstruktion muss ein korrespon- dierender Punkt in beiden Bildern gefunden werden. Nun kann die genaue Position des Punktes im Raum über Triangulierung [FP03] bestimmt wer- den.
- Shap e-from-Motion: Ähnlich wie bei Shap e-fr om-Stereo wird auch hier mit mehreren Bildern gearbeitet. Diese sind allerdings aus einer Bewegung her- aus entstanden und haben deswegen meist geringfügigere Unterschiede als richtige Stereopaare. Dafür kann das Wissen über die Bewegung in die Be- rechnung integriert werden. Dem Menschen stehen etwa 20 Bilder pro Se- kunde zur Verfügung.
- Shap e-from-Textur e: Bei der 3D-Rekonstruktion durch Shape-f r om -Textur e wird versucht, die Textur einer Oberfläche zu analysieren. Durch die räum- liche Verzerrung des Musters der Oberfläche kann die Form rekonstruiert werden. Dieses Verfahren findet nur bei Objekten mit einem bekannten oder sich wiederholenden Muster Verwendung.
- Shap e-fr om-Shadow: Shap e-fr om-Shadow ist eines der ältesten, technisch realisierten Verfahren zur Rekonstruktion von 3D-Informationen. Es wird nur der Schattenwurf eines Objektes verwendet, um Rückschlüsse auf die Oberfläche zu ziehen. Verwendet wurde es zum Beispiel zur Rekonstruktion der Mondoberfläche vor der ersten Mondlandung.
- Shap e-from-Contour: Hier werden nur die Umrisse eines Objektes zur Re- konstruktion verwendet. Dadurch sind ebenfalls viele Bilder des Objektes aus verschiedenen Perspektiven nötig um das komplette Modell zu erhalten.

Durch die Aufgabenstellung dieser Arbeit sind die meisten dieser Methoden auf Grund von fehlenden Informationen nicht möglich. Es stehen nur einzelne Fotografien 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 Oberfläche ziehen zu können. Die Verwendung von Shap e-from-Textur e ist deswegen ebenfalls nicht möglich. Shap e-fr om-Shadow lie- fert als alleiniges Verfahren zu wenige Informationen um ein komplettes Gesicht zu modellieren. Wird der Schattenwurf allerdings nicht berücksichtigt, kann dass das Resultat stark beeinflussen.

Shap e-fr om-Shading ist somit der vielversprechendste Weg Gesichtsmodelle aus Fotografien 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 Erken- nung 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 Ei- genschaften merkt, kann man einem Computer dieses Erinnerungsvermögen bei- bringen. 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 Ähn- lichkeiten aufweisen. Dies ist bei Gesichtern der Fall. Die Anordnung und Größe 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 statis- tisches Modell zur Rekonstruktion eines Gesichts aus einer Fotografie heranzu- ziehen. 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 so- wohl 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 Nach- teile umgangen. In Abbildung 2.5 ist der schematische Aufbau des Verfahrens zu sehen.

Ausgangssituation ist eine Fotografie, welche ein frontal beleuchtetes und auf- genommenes Gesicht zeigt. Auf das Gesicht werden verschiedene Techniken der digitalen Bildverarbeitung angewendet. Darauf folgt die Rekonstruktion des Ge- sichts. 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 individu- elle 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 nach- bearbeitet werden, um es als 3D-Objekt speichern zu können.

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

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.6: Zeitlicher Ablauf der Rekonstruktion.

abhängig vom Umfang der Gesichtsdatenbank sehr lange dauern kann. Ein weite- rer 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.

Kapitel 3

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 Re- präsentation von Geometrie in verschiedenen Koordinatensystemen. Weiterhin ist ein Grundwissen über digitale Bildverarbeitung notwendig um mit Gesichtsfoto- grafien zu arbeiten. Schließlich werden verschiedene Oberflächenrepräsentationen vorgestellt, welche zur Darstellung und Verarbeitung von dreidimensionalen Ge- sichtsmodellen 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 - dimensionales Tupel. Die Dimension des Koordinatensystemes, in dem der Punkt dargestellt wird, hat gleichermaßen die Dimension n. Ein Tupel beinhaltet die Ko- ordinaten, welche die Position beschreiben. In der folgenden Gleichung entspricht p dem Punkt und x, y, z den Koordinaten des Punktes:

Abbildung in dieser Leseprobe nicht enthalten

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 wer- den sogenannte orthogonale Koordinatensysteme verwendet. Orthogonal bedeu- tet, dass ihre Koordinatenachsen senkrecht aufeinander stehen. Eine weitere Ei- genschaft solcher Systeme ist, dass die Abstände zwischen den Koordinatenein- heiten 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 dar- gestellt. 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) aufge- spannte Ebene ist in vier Bereiche aufgeteilt. Diese sogenannten Quadranten sind in Abbildung 3.1 bezeichnet.

Abbildung in dieser Leseprobe nicht enthalten

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

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

Der Unterschied zwischen den beiden Systemen besteht in der Richtung der Applikate. Je nachdem welches System benutzt wird, zeigt der Mittelfinger nach der sogenannten Rechten-Hand-Regel in eine andere z-Richtung. Die Rechten- Hand-Regel lässt sich in Abbildung 3.2 nachvollziehen.

Abbildung in dieser Leseprobe nicht enthalten

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. Befinden 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 Winkelanga- ben 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 befindet. Ergänzend hierzu beschreibt der Winkel θ den Breitengrad. Punkt p liegt dann in dem Schnittpunkt der beiden Kreise, welche durch die Winkel bestimmt

Abbildung in dieser Leseprobe nicht enthalten

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

werden.

Abbildung in dieser Leseprobe nicht enthalten

Die Umwandlung der Kugelkoordinaten in kartesische Koordinaten erfolgt durch:

x = r sin α cos θ, y = r sin α sin θ, 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.

Der Winkel λ gibt den Längengrad an, auf welchem sich der Punkt p befindet. 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ähl- ten 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◦}

definiert. Ein geographisches Koordinatensystem und der Punkt p sind in Abbil- dung 3.4 dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

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

Dieses Koordinatensystem unterscheidet sich von dem Kugelkoordinatensys- tem nur in dem Gültigkeitsbereich der Winkel. In dieser Arbeit sind alle Win- kelangaben in Bogenmaß angegeben. Daher sind die Gütigkeitsbereiche als λ ∈

{− π ,... , π } und ϕ ∈ {− π ,.. . , π } festgelegt.

Um Kugelkoordinaten in geographische Koordinaten zu überführen kann fol- gende Beziehung definiert werden:

Abbildung in dieser Leseprobe nicht enthalten

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 in dieser Leseprobe nicht enthalten

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

x = r cos φ, y = h,

z = r sin φ

und umgekehrt durch

r = , x 2 + z 2 ,

Abbildung in dieser Leseprobe nicht enthalten

3.2 Digitale Bildverarbeitung

Bilder liegen in der Regel als kontinuierliches Signal vor. Damit es digital verarbei- tet 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 abgespei- chert 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 Bildpunk- tes der Position (x, y). Ein Farbbild F (x, y) besteht aus drei Funktionen und wird daher auch vektorwerti ge Funktion genannt:

Abbildung in dieser Leseprobe nicht enthalten

In Abbildung 3.6 ist ein Intensitätenbild dargestellt. Jede Position im Bild ist durch ein (x, y)-Tupel mit x ∈ {0 ,... , X res} und y ∈ {0 ,... , Y res} identifizierbar. 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.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.6: Jedem (x, y)-Tupel ist ein Intensitätswert I (x, y) zugeordnet.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.7: Ein Bildpunkt besitzt eine 4er- und eine 8er-Nachbarschaft.

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ärtsdifferenz, Vorwärtsdifferenz oder symmetrische Differenz gebildet wer- den.

In Abbildung 3.8 sind die Intensitätswerte in x -Richtung eingetragen. In die-

I(x,y) Abbildung in dieser Leseprobe nicht enthalten

x

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.8: Symmetrische Ableitung eines diskreten Bildsignals in x-Richtung.

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

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

∂I

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

Rückwärtsdifferenz: I (x, y) − I (x − 1 , y)

Vorwärtsdifferenz: I (x, y) − I (x + 1 , y)

Wendet man diese Ableitungen auf einen Bildpunkt an, ergeben sich verschiedene Effekte. Unter Verwendung der Rück- bzw. Vorwärtsdifferenz 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 Differenz 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 Bild- punktes ausschließlich von seinem ursprünglichen Helligkeits- beziehungsweise Farb- wert abhängig. Es werden daher keine benachbarten Bildpunkte in solche Ope- rationen einbezogen. Solche Punktoperationen sind zum Beispiel Helligkeitskor- rekturen, 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- figkeit der Grauwerte beziehungsweise der Farbwerte. Eine nähere Betrachtung von Punktoperationen ist in [Jä02] zu finden.

3.2.3 Nachbarschaftsoperationen

Bei Nachbarschaftsoperationen wird die Umgebung des betrachteten Bildpunk- tes berücksichtigt. Sie werden auch als Faltungsoperationen bezeichnet. Dies be- deutet, 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 definiert:

Abbildung in dieser Leseprobe nicht enthalten

Bilder liegen jedoch meist in einer diskreten Darstellung I (x, y) vor und somit ist diese Definition in der Praxis nicht verwendbar. Für den diskreten Fall sieht die Faltung ähnlich aus:

Abbildung in dieser Leseprobe nicht enthalten

Die Funktion g wird als Filter, Filterkern oder Maske bezeichnet. Sie kann unterschiedliche Größen besitzen, welche abhängig von ihrem Einsatzgebiet und dem gewünschten Effekt ist.

Der Ursprung der Maske g wird bei einer Filterung mit einer ungeraden Masken- größe über den zu filternden Bildpunkt der Bildfunktion I gelegt. Die nun über- einanderliegenden 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 in dieser Leseprobe nicht enthalten

Abbildung 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.

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

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 wer- den. Wie in Abschnitt 3.2.1 gezeigt, wird zwischen Rückwärtsdifferenz, Vorwärts- differenz und symmetrischer Differenz unterschieden. Da für diese Arbeit nur die symmetrische Differenz relevant ist, wird diese im Folgenden näher betrachtet.

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

Abbildung in dieser Leseprobe nicht enthalten

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

nalen Fall ist daher:

Abbildung in dieser Leseprobe nicht enthalten

Lineare Glättungsfilter

Glättungsfilter 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 Rechteckfilter 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:

Abbildung in dieser Leseprobe nicht enthalten

Bilder, die mit solch einer Maske geglättet werden, wirken weich und verschwom- men.

Eine weitere Möglichkeit stellt eine unterschiedliche Gewichtung der Bildpunk- te je nach Lage dar. In Abbildung 3.9 ist eine solche Glättungsmaske gezeigt. Im Gegensatz zu den Rechteckfiltern wird hier das Zentrum am stärksten gewich- tet. 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 Bi- nomialverteilung und ist als Binomialfilter bekannt [Jä02]. Die Filterkoeffizienten können anhand des Pascalsche n Dr eiecks [CG98] hergeleitet werden, welches den Binomialkoeffizienten entspricht. Die Varianz gibt hierbei die effektive 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:

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

Da die Maske aus einer Faltung zweier eindimensionaler Binomialfilter entsteht, kann man anstatt eines zweidimensionalen Filters auch zwei eindimensionale Fil- terungen hintereinander anwenden. Daher spricht man auch davon, dass ein Bi- nomialfilter separabel ist.

Abbildung in dieser Leseprobe nicht enthalten

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 be- liebig große Glättungsfilter konstruieren. Eine nähere Betrachtung ist in [Tö05] zu finden.

3.3 Beschreibung von Oberflächen

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

Die Farben der Oberfläche werden in der Computergrafik meistens über Tex- turen bestimmt. Dafür muss die Oberfläche in ein zweidimensionales Koordina- tensystem 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 Oberfläche muss eine Tex- turkoordinate bekannt sein, die festlegt, welche Stelle der Textur sich an diesem Punkt befindet.

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

In der Computergrafik sollen Oberflächen häufig nur von einer Seite sichtbar sein. Dadurch können zum Beispiel bei der Darstellung der Oberfläche Ressour- cen gespart werden, da nur eine Seite beim Rendern berücksichtigt werden muss. Welche Seite der Oberfläche sichtbar ist, wird ebenfalls durch die Normale be- schrieben. Sie gibt somit die Neigung und die Oberseite der Oberfläche an einer bestimmten Stelle an.

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

Zur Definition von Oberflächen gibt es verschiedene Darstellungsformen, von denen häufig mehrere zum Bearbeiten eines Problems notwendig sind.

3.3.1 Höhenfelder

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.10: Darstellung einer Oberfläche als Höhenfeld.

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:

Abbildung in dieser Leseprobe nicht enthalten

Oberflächen dieser Art werden auch 2,5-dimensionale Oberflä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 unter- teilt 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 Oberfläche durch Aufzählen aller Werte, statt durch ein Bildungsgesetz, be- schrieben werden.

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

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

Ein häufiges Anwendungsgebiet für die explizite Darstellung sind Terrainmo- delle. 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 Abbil- dungen 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- flä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 Gradi- enten aufgezeigt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.11: Zusammenhang zwischen Gradienten und Normale einer Oberfläche.

Um aus den Oberflächengradienten p (x, y) und q (x, y) die Normale n (x, y) zu berechnen, kann das Kreuzprodukt für Vektoren verwendet werden:

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.12: Integrierbares Gradientenfeld.

bildung 3.12 zeigt ein integrierbares Gradientenfeld. Egal welcher Pfad von Punkt 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

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.13: Nicht integrierbares Gradientenfeld.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.14: Darstellung einer Oberfläche als Punktwolke.

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 kontinuier- liche Art Punktwolken zu definieren gibt es nicht. Sie werden häufig 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.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.15: Darstellung einer Oberfläche als Polygonales Netz.

3.3.3 Polygonale Netze

Die am weitesten verbreitete Art zur Darstellung von 3D-Objekten in der Com- putergrafik 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 plana- re 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 Oberflä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 Oberflächen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.16: Links konvexes Polygon, rechts nicht konvexes Polygon.

Durch Aneinanderhängen vieler Polygone erhält man ein polygonales Netz, auch Drahtgittermodell genannt. Oft werden als Polygone nur Dreiecke verwendet. Die- se haben zwei Vorteile gegenübere anderen Polygonen. Dreiecke sind immer konvex und liegen zwangsläufig in einer Ebene.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.17: Planares Polygon.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.18: Nicht planares Polygon.

Ein Polygonnetz kann nicht über eine einzelne Funktion definiert werden, wie zum Beispiel ein Höhenfeld. Es werden komplexe Datenstrukturen benötigt um diese zu verwalten. Das Bestimmen von Texturkoordinaten für Polygonnetze er- weist 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öglich- keit ist zum Beispiel das facettenzentrierte Definieren von Polygonen. Es werden sowohl Eckpunkte, Normalenvektoren als auch die Texturkoordinaten in getrenn- ten Listen gespeichert. Die einzelnen Facetten können dann aus den Indizes der einzelnen Listen zusammengebaut werden. Ein Polygonnetz P kann somit folgen-

dermaßen beschrieben werden:

Abbildung in dieser Leseprobe nicht enthalten

Ein Dateiformat, welches diese Technik verwendet, ist das obj-Dateiformat. Dieses wurde von der Firma W avef r o nt T echno l ogies entwickelt, und hat sich als offenes Dateiformat sehr schnell verbreitet. Es hat den Vorteil, dass es sehr spei- chereffizient ist. Das Polygonnetz wird letztendlich nur aus Indizes zusammenge- baut. Dadurch müssen mehrfach verwendete Koordinaten nur einmal gespeichert werden. Allerdings sind Aufgaben wie zum Beispiel das Finden benachbarter Po- lygone hier sehr zeitaufwändig.

Deswegen gibt es Strukturen, die für das Arbeiten mit Polygonnetzen besser ge- eignet sind. Eine häufig verwendete Datenstruktur dieser Art ist die doppelt ver- kettete Kantenliste (Half-Edg e -Data-Stru c tur e) [Yam02]. Wie in Abbildung 3.19

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.19: Half Edge Datenstruktur

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

zes zu beschreiben. Jeweils zwei Halbkanten bilden eine komplette Kante. Jede Halbkante gehört zu genau einem Eckpunkt. Dieser enthält außerdem seine Koor- dinaten, 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 Oberfläche, zeigt sie auf sich selbst. Über die jeweiligen Partnerhalbkanten erreicht man schnell die Nachbarfacetten.

Kapitel 4

Rekonstruktion mittels Shape-from-Shading

In diesem Kapitel wird ein Verfahren zur Rekonstruktion von Oberflächen mit Hilfe von Shape-from-Shading vorgestellt. Zu diesem Zweck muss geklärt werden, wie man das Reflektionsverhalten einer Oberflä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 Fra- mework zur Rekonstruktion vorgestellt, und Schritt für Schritt erläutert.

4.1 Reflektionsverhalten von Oberflächen

Trifft Licht auf eine Oberfläche, kann dieses in verschiedener Weise mit ihr inter- agieren. In der Realität tritt dabei immer eine Kombination aus Brechung und Reflektion auf.

Eine reflektierende Oberfläche strahlt das Licht zurück. Wird das Licht ge- brochen (tr ansmitted), wird es an der anderen Seite der Oberflä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

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

eintreffendes Licht

reflektiertes

=

Licht

gebrochenes

+

Licht

absorbiertes

+

Licht .

Unabhängig davon, ob das Licht gebrochen oder reflektiert wird, kann es bei diesem Vorgang mehr oder weniger gestreut werden. Das heißt, dass die Ober- fläche matt oder spiegelnd erscheinen kann. In Abbildung 4.1 sind die drei Kom- ponenten, Absorbtion, Streuung und Spiegelung, aus denen sich eine Reflektion zusammensetzt dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.1: Komponenten einer Reflektion.

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

4.1.1 Differentielle Raumwinkel

Um das Reflektionsverhalten einer Oberfläche zu definieren, 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 differentiellen Raumwinkels von Bedeutung. Ein Raumwinkel ω ist das räumliche Gegenstück zu einem Bogenwinkel in der Ebe- ne. Er ist als der Quotient zwischen einer Teilfläche S auf einer Kugel und dem

Quadrat des Radius r der Kugel definiert:

S

Abbildung in dieser Leseprobe nicht enthalten

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 eintreffende Menge an Licht aus einer bestimmten Richtung betrachtet werden soll, wählt man einen entsprechend kleinen, differen- zierten Raumwinkel. Dieser Raumwinkel wird als differentieller Raumwinkel dω bezeichnet:

Abbildung in dieser Leseprobe nicht enthalten

Meistens handelt es sich bei differentiellen Raumwinkeln um Winkel auf einer Einheitskugel. In diesem Fall wird r 2= 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 strahlen- den Oberfläche von Bedeutung. Es ist nur die Größe der Oberfläche, die von einem bestimmten Punkt aus gesehen wird relevant. Dieser Effekt wird als Verkürzung, oder for eshorte ning bezeichnet.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.2: Verkürzung durch den Einfallwinkel des Lichts.

In Abbildung 4.2 ist dies für den Fall einer beleuchteten Fläche dargestellt. In der linken Abbildung trifft Licht mit der Intensität I = 1 senkrecht auf eine

Oberfläche. Der Winkel zwischen der Richtung des eintreffenden Lichts und der

Abbildung in dieser Leseprobe nicht enthalten

Auf der rechten Seite trifft der Lichtstrahl mit dem Winkel θ zur Oberflächen- normale ein. Die Fläche, auf die das Licht verteilt wird, ist um den Faktor 1 größer. Entsprechend nimmt die durch das Licht erzeugte Helligkeit der Oberfläche um den Faktor cos(θ) ab.

Dieser Effekt gilt nicht nur für die Neigung einer beleuchteten Oberfläche, die durch weniger Lichtstrahlen getroffen 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 Oberfläche in Bezug auf einen bestimmten Punkt einer beleuchteten Oberfläche einnimmt. In Abbildung 4.3 ist die Oberfläche A um den Winkel α in

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.3: Perspektivische Verkürzung bei Raumwinkeln

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

A cos α ω = .

z 2

4.1.3 Strahldichte und Bestrahlungsstärke

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

Abbildung in dieser Leseprobe nicht enthalten

In den meisten Fällen genügt es in der Computergrafik davon auszugehen, dass das Licht nicht mit dem passierten Medium interagiert. Das heißt man geht von einem Vakuum aus. Die gleiche Strahldichte, die einen Punkt P 1in Richtung Punkt P 2verlässt, kommt an P 2aus Richtung P 1an.

Will man berechnen, wieviel Licht an einer bestimmten Stelle einer Oberfläche aus einer bestimmten Richtung mit dem differenziellen Raumwinkel dω eintrifft, muss allerdings der Einfallswinkel und die daraus resultierende Verkürzung der Oberfläche berücksichtigt werden. Deswegen wurde zusätzlich der Begriff der Be- strahlungsstärke (oder irr adiance) eingeführt. Die Bestrahlungsstärke ergibt sich aus der eintreffenden Strahldichte multipliziert mit dem entsprechenden differen- tiellen Raumwinkel multipliziert mit dem Kosinus des Einfallwinkels:

irradiance = L (P, θ, α) cos θd ω.

Diese Darstellung des Lichts hat einen entscheidenden Vorteil. Alle möglichen Richtungen, aus denen Licht auf eine Oberfläche strahlen kann, liegen auf einer Halbkugel über der Oberfläche. Es ist nun möglich die gesamte eintreffende Lich- tenergie an einer bestimmten Stelle der Oberfläche durch integrieren über diese Hemisphäre zu berechnen.

4.1.4 Lichtmessung mit Kameras

Beschäftigt man sich mit der Rekonstruktion von Oberflächen aus Fotografien, muss geklärt werden, ob man von der Helligkeit in einem bestimmten Bildpunkt der Fotografie überhaupt Rückschlüsse auf die tatsächliche Helligkeit an dem ab- gebildeten Punkt der Oberfläche schließen kann.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.4: Schematischer Aufbau einer Kamera.

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 lichtempfindliche Medium reduziert wer- den. Dieses ist in der Abbildung durch Π gekennzeichnet und liegt im Abstand f hinter der Linse. Dieser Abstand wird als Fokuslänge bezeichnet. Linse und op- tisches 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 t abgebildet. Er liegt im Schärfe- bereich der Kamera. Durch Ändern der Fokuslänge der Kamera lässt sich dieser Bereich manipulieren. Dies ändert aber nichts an den grundlegenden mathemati- schen Zusammenhängen, und kann hier vernachlässigt werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.5: Zusammenhang zwischen der Strahldichte einer Oberfläche und der eintreffen- den Bestrahlungsstärke auf dem optischen Medium einer Kamera.

In Abbildung 4.5 ist der Vorgang der Abbildung eines Punktes P mit der dif- ferentiellen Fläche ∂A auf einer strahlenden Oberfläche auf den Punkt P t mit der differentiellen Fläche A tauf dem optischen Medium der Kamera dargestellt. Die eintreffende Lichtintensität auf dem Medium ist abhängig vom differentiel- len Raumwinkel ∂ω. Dieser beschreibt die Strahldichte unter Berücksichtung des Einfallwinkels α, mit welcher der Punkt P t von der optischen Mitte aus projiziert wird. Durch den Strahlensatz entspricht ∂ω ebenfalls dem Winkel, der beschreibt, welche verkürzte Fläche der strahlenden Oberfläche von der optischen Mitte aus gesehen werden kann. Er kann wie folgt berechnet werden:

Abbildung in dieser Leseprobe nicht enthalten

Diese Gleichung kann umformuliert werden, um das Verhältnis der beiden diffe- rentiellen Flächen ∂A und ∂A tzueinander auszudrücken:

Abbildung in dieser Leseprobe nicht enthalten

Der Raumwinkel Ω beschreibt den Teil des Lichtes, der von Punkt P aus auf die Linse der Kamera trifft. Die Fläche der Linse kann über π d 2 berechnet werden.

Für die Berechnung von Ω ergibt sich damit:

Abbildung in dieser Leseprobe nicht enthalten

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 Oberfläche ausdrücken. Sie entspricht der Strahlungsdichte der Oberfläche L multipliziert mit dem Raum- winkel, den die Linse aus Sicht der Oberfläche einnimmt, Ω multipliziert mit der abstrahlenden differenzierten Fläche ∂A verkürzt durch den Abstrahlwinkel β.

∂P = L Ω ∂A cos β.

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

π. d.2

Abbildung in dieser Leseprobe nicht enthalten

Die Energie ∂P wird durch die Linse auf die Fläche ∂A tprojiziert. Es handelt sich dabei um das einzige Licht, welches diese Stelle erreicht. Deswegen lässt sich die, auf dieser Stelle eintreffende, Lichtintensität folgendermaßen berechnen:

Abbildung in dieser Leseprobe nicht enthalten

Ersetzt man hier ∂A

durch (4.1) erhält man:

Abbildung in dieser Leseprobe nicht enthalten

In der Fotografie beschreibt diese Gleichung die Lichtstärke des Objektivs der Ka- mera. Es lassen sich zwei wichtige Schlussfolgerung aus ihr ziehen. Sie zeigt, dass die Lichtintensität L an einem bestimmten Punkt einer Oberfläche proportional zur Intensität dieses Punktes nach der Abbildung durch eine Kamera ist. Das heißt, dass die Bildintensitäten, die durch die Fotografie gegeben sind, wirklich Rückschlüsse auf die tatsächliche Helligkeit der Oberflä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 Einfallwin- kel 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 Reflectance Distribution Function

In der Computergrafik werden Beleuchtungsmodelle benutzt um Oberflächen Ei- genschaften für das Rendering zuzuweisen. Beim Rendern werden aus den 3D- Daten einer Szene, der Beleuchtung und den Oberflächeneigenschaften 2D Abbil- dungen generiert. Beim Shape from Shading soll aus 2D-Abbildungen sowie Ap- proximationen der Beleuchtungssituation und der Oberflächeneigenschaften die 3D-Szene rekonstruiert werden.

Beleuchtungsmodelle werden in lokale und globale Beleuchtungsmodelle un- terteilt. Globale Beleuchtungsmodelle (global illumination) beschreiben, wie sich Licht ausbreitet. Hiermit sind Ray tra c in g und Radiosity sowie diverse Varian- ten gemeint [FP03].