TUD Logo

TUD Home » ... » CGV Teaching Archive » WS 09/10 » Computergraphik (Hauptseminar) WS 0910

Computer Graphics

Computergraphik (Hauptseminar) WS 0910

WS 08/09, 0/2/0, HS-INF, IST

Dozent, Betreuer

Prof. Dr. S. Gumhold
Dipl. Medieninf. Sören König

Computergraphik (Hauptseminar)

Numerische Algorithmen in der Computergraphik

Di 3. DS, INF E009

Termine

  • 13.10.09 Vorbesprechung und Themen- und Aufgabenverteilung, Einführungfolien
  • bis 3.11 Termin für erstes Treffen mit Betreuer (Sören König) per Mail oder direkt (Raum 2107) ausmachen (Ziel: Themeneingrenzung und Paperwahl)
  • weitere Termine nach Bedarf per Mail oder direkt ausmachen
  • eine Woche vor dem Vortragstermin: finale Besprechung des Vortrages (Vortrag muss vollständig ausgearbeitet sein)
  • 19.01.10: Vortrag von Stephan Reinicke und Frank Harnisch
  • 26.01.10: Vortrag von Claudia Zimmer und Mathieu Floiras
  • 02.02.10: Vortrag von Annett Ungethüm und Ron Hiepel
  • Abgabe der schriftlichen Ausarbeitung bis 09.02.10

 

Scheinerwerb

Für den Scheinerwerb sind folgende Leistungen zu erbringen:
  • Halten eines Vortrages mit anschließender Diskussion zu einem der unten aufgeführten Themen
  • Erarbeitung einer schriftlichen Ausarbeitung
  • Regelmäßige Teilnahme am Seminar

Hinweise zum Vortrag:

Die Folien müssen eine Woche vor dem Termin fertig gestellt und mit dem Betreuer durchgesprochen sein.
Der Vortrag soll aus einem Grundlagenteil und einem angewandten Teil bestehen:

Grundlagenteil:

  • Problematik durch ein oder zwei selbstgewählte Beispiele in der Computergraphik motivieren
  • allgemeine Problemformalisierung
  • Vorstellung aktueller Algorithmen/Verfahren sowie verfügbare Implementierungen (Bibliotheken), Stolpersteine bei der Benutzung etc. (Rausfinden durch eigenes Ausprobieren und Anwenden)
  • Die Motivation bzw. Zusammenfassung soll möglichst gut und kompakt auf ein oder zwei Folien anhand eines eigenen Bildes/eigener Grafik/Folienanimation visualisiert werden.

Angewandter Teil:

  • Vorstellung eines aktuellen CG-Papers, in dem die vorgestellte Technik eine wichtige Rolle spielt (Auswahl des Papers vorher zusammen mit zugeteiltem Betreuer abstimmen)

Hinweise zur schriftliche Ausarbeitung:

  • Inhaltliche Aufbereitung des für den Vortrag erarbeiteten Wissens in einem schriftlichen Dokument.
  • Der Umfang sollte 10 bis max. 20 Seiten betragen.
  • Abgabe des schriftlichen Teils am Ende des Semesters.
  • Erarbeitung des Dokuments möglichst in Latex.

Themen

1. Lineare Gleichungssysteme, Spezielle Matrixklassen, Matrixfaktorisierung und direkte Löser (Stephan Reinicke)

Wie findet man zu einer Matrixtransformation die Rücktransformation?
Wie berechnet man globale Beleuchtungseffekte (Radiosity-Gleichung)?
Wie kalibriert man eine perspektivische Lochkamera anhand von Korrespondenzen in 3D und im Bild?
Wie findet man die passende Bildtransformation (Homographie) um Einzelbilder zu einem Panoramabild zusammenzusetzen?

All diese Fragen sind Beispielprobleme die zur Aufstellung und Lösung eines oder mehrerer linearen Gleichungssysteme führen. Doch nicht alle Gleichungssysteme benötigen denselben Aufwand beim Lösen. Oft lassen sich spezielle Matrixstrukturen identifizieren, welche eine effiziente Lösung ermöglichen. Für allgemeine Matrizen wird dann beim direkten Lösen eine Zerlegung in ein Produkt von speziellen Matrizen gesucht, um das allgemeine Problem auf einige wenige einfach zu lösende spezielle Probleme zu vereinfachen.

 

2. Singulärwertzerlegung und Eigenwertprobleme (Frank Harnisch)

Wie löst man überbestimmte/unterbestimmte Gleichungssystemen (Least Squares und Normalengleichung)?
Wie bestimmt man Oberflächennormalen in einem 3D Scan?
Wie findet man optimale Transformationen um Teil-3D-Scans aneinander auszurichten?
Wie zerlegt man zusammengesetzte Transformationen wieder in Einzeltransformationen?
Wie kann man höherdimensionale Daten z.B. Bilder mittels SVD reduzieren bzw. komprimieren?
Was ist Hauptkomponentenanalyse (PCA) und wie identifiziert man Hauptstreurichtungen in räumlichen Messdaten?
Wie berechnet man effizient Matrixpotenzen?

Die zwei wichtigsten Matrixfaktorisierungen sind die Singulär- und Eigenwertzerlegung, da sie nicht nur zum reinen Lösen eines Gleichungssystems benutzt werden können, sondern auch die meisten Informationen über die Eigenschaften einer Matrix wie z.B. den Rang oder den Kern offenbaren. Weiterhin spielen sie eine wichtige Rolle beim approximativen  und beim numerisch stabilen Lösen von über- und unterbestimmten Gleichungssystemen, wie sie oft beim Fitten eines linearen Modells in eine Menge von Messdaten entstehen.

 

3. Krylov-Unterraummethoden - Iterative Löser für Gleichungssysteme und Eigenwertprobleme

Wie realisiere ich eine stabile Stoffsimulation in Echtzeit?
Wie funktioniert Spektrales Clustering?

Krylov-Unterräume bilden die Basis für einige der effizientesten iterativen Verfahren (CG und GMRES) zum Lösen extrem großer, dünnbesetzter Gleichungssysteme sowie dem iterativen Bestimmen einiger Eigenvektoren und -werte. (Arnoldi- und Lanczosmethode). Es ergeben sich interessante Querbeziehungen zwischen dem Lösen eines linearen Gleichungssystems und der quadratischen Programmierung.

 

4. Fast Fourier Transform (FFT) (Claudia Zimmer)

Wie faltet man ein Bild schnell mit einer großen Filtermaske?
Wie multipliziert man effizient zwei Polynome hohen Grades?
Wie detektiert man Orientierungen von Kanten in Bildern und Volumen?
Wie entrauscht, entwackelt oder schärft man Bilder?
Wie berechnet man Tiefe aus der Unschärfe in Bildern?
Wie hält man unterschiedliche Texturen in Bildern auseinander?

All diese Probleme vereint die Verwendung der diskreten Fourier Transformation, welche mittels der schnellen Fourier Transformation (FFT) von Cooley und Tukey effizient berechnet werden kann.  Da es sich bei der DFT im Wesentlichen um eine Multiplikation mit einer Matrix (der Fourier-Matrix) handelt, ist die FFT eigentlich nur ein Trick die spezielle Struktur der Fourier-Matrix auszunutzen um dieses Produkt zu beschleunigen.

 

5. Fast Multipole Method (FMM), Fast Gaussian Transform (FGT), ...

Wie bekommt man Mean-Shift-Clustering effizient implementiert?
Wie wertet man die Summe über eine Menge von Kernelfunktionen effizient an einer vielzahl von
Positionen aus?

Die Fast Multipole Method ist ähnlich der FFT auch im Wesentlichen nur ein Trick um eine
Multiplikation mit einer allgemeineren Klasse von Matrizen (Kernelmatrizen) zu beschleunigen. Diese Erkenntnis wird momentan in einer Vielzahl von Algorithmen, wie z.B. dem Mean-Shift-Clustering eingesetzt, um eine schnellere Berechnung zu ermöglichen und kann auch in der Computergraphik z.B. in der Oberflächenrekonstruktion oder in bestimmten  Physiksimulationsproblemen verwendet werden.

 

6. Minimaler Schnitt und Maximaler Fluss in Graphen

Wie berechnet man 3D Stereorekonstruktionen mittels Graphcut?
Wie berechnet man hochqualitative Segmentierungen von Bildern und Volumendaten?

Einige interessante Computervision-Probleme wie z.B. die Stereorekonstruktion oder die Segmentierung lassen sich als ein spezielles, diskretes Energieoptimierungsproblem formulieren, welches sich auf die Berechnung eine minimalen Schnittes in einem Graphen reduzieren lässt. Das besondere an diesen sog. Graphcut-Verfahren ist, das sich oft global optimale Lösungen finden lassen.

 

7. Linear Programming, Quadratic Programming (Mathieu Florias)

Wie berechnet man den Abstand zweier polygonaler Netze?
Wie berechnet man Scheinkräfte bei ruhendem Kontakt mit Reibung in einer Physikengine?
Was funktioniert das Simplexverfahren?

Bei der linearen Programmierung ist eine lineare Zielfunktion unter Nebenbedingungen (Gleichungen und Ungleichungen) zu optimieren. Der Raum der möglichen Lösungen, welcher durch die Nebenbedingungen eingeschränkt ist, bildet einen diskreten, konvexen Polyeder. Am häufigsten kommt das Simplexverfahren zum Einsatz, was  eine geschickte Suchstrategie auf der Oberfläche des Lösungsraumpolyeders darstellt. Dabei muss dieser jedoch nicht vollständig und explizit berechnet werden. Ersetzt man die die lineare Zielfunktion durch eine quadratische Funktion so erhält man ein QP (Quadratic Programming)-Problem.

 

8. Nichtlineare Optimierung  (Gradient Descent, Newton's method, Levmar, downhill simplex) (Annett Ungethüm)

Wie kann ich geometrisch z.B. einen Zylinder oder eine Kugel in eine Menge von Punkten einpassen?
Wie bestimme ich ein Kameramodell mit Verzeichnungsparametern?
Wie berechnet man die inverse Kinematik von einem Roboterarm?

Die Minimierung von nichtlinearen Funktionen ist ein häufiges Standardproblem, welches typischerweise mit einem sog. Line-Search-Verfahren gelöst werden kann. Dabei geht man von einer initialen Schätzung aus, welche dann iterativ verbessert wird. Die unterschiedlichen Verfahren unterscheiden sich meist nur in der Wahl der Verbesserungsrichtung und in der Bestimmung der Schrittweite.


9. Sampling Methoden: Random Sampling, Stratified Sampling und die Monte Carlo Methode

Wie löst man komplizierte Integrale mittels Sampling Techniken (wie z.B. die Renderinggleichung)?
Wie berechnet man komplizierte Flächen oder Volumina?

Komplizierte Integrale können mittels zufälliger Abtastung sehr einfach berechnet werden.
Problematisch ist jedoch die Frage wie viele Abtastwerte notwendig sind und wie man diese am besten wählt, um möglichst schnell ein möglichst genaues Ergebnis zu erhalten. Besonders knifflig wird es, wenn die Dimensionalität des Definitionsbereiches sehr hoch ist.

 

10. Dynamic Programming (Ron Hiepel)

Wie kann ich BSpline-Kurven effizient auswerten?
Wie kann ich Sequenzen optimal aufeinander matchen (Sequencealignment) (z.B. bei der
Korrespondenzsuche bei der Stereorekonstruktion)?
Wie matche ich längste gemeinsame Teilsequenzen?

Viele Methoden beherbergen in ihrer algorithmischen Struktur bestimmte redundante Zwischenberechnungen. Dynamic Programming ist ein algorithmisches Designmuster, welches auf die Wiederverwendung bzw. Vorberechnung solcher redundanter Zwischenergebnisse abzielt und somit eine möglichst schnelle Berechnung ermöglicht.


11. Optimierung mit Methoden der Variationsrechnung

Wie finde ich krümmungsminimale Kurven oder Flächen?
Wie berechne ich  deformationsminimale Verschiebungsfelder zwischen zwei Bildern, Volumen oder 3D Scans? (Anwendung Tracking, Registrierung, Morphing)
Wie berechnet man hochqualitative 3D-Rekonstruktionen aus mehreren Bildern?
Wie segmentiert man Bild oder Volumendaten möglichst optimal?

Mithilfe der Variationsrechnung lassen sich Probleme formulieren dessen Lösung  Funktionen (z.B. ein skalares oder vektorielles Feld oder eine Kurve) sind.
Dabei wird zunächst ein Energiefunktional aufgestellt, welches die gewünschten Anforderungen an die gesuchte Zielfunktion modelliert. Diese kann dann mittels des Euler-Lagrange-Formalismus in eine partielle Differentialgleichung überführt und mit Standardtools z.B. durch finite Differenzen diskretisiert und gelöst werden. Die momentan besten Verfahren zur Berechnung eines optischen Flusses zwischen zwei Bildern, oder der Stereorekonstruktion basieren auf dieser Methodik.

Ergebnis

Materialien

Gesammelte Paper-Links zu diversen Computergrafikkonferenzen.

Literatur allgemein


Last modified: 1st Feb 2010, 2.56 PM
Author: Dr.-Ing. Wilfried Mascolus