Sprachen

Graphaeology.NET - SS 2006, WS 2006/07

Thema: 
Entwurf und Entwicklung eines Systems zur Rekonstruktion archäologischer Artefakte basierend auf multiplen dreidimensionalen Scans zum Zweck einer netzbasierten Visualisierung.
Zeitraum: 
SS 2006, WS 2006/07
Umfang: 
8 SWS pro Semester
Veranstalter: 

Dipl.-Inform. Claus-Peter Alberts, Informatik VII (Graphische Systeme),
OH16, R.101, Tel.:6134, E-Mail: Claus-Peter.Alberts@cs.uni-dortmund.de
Dipl.-Inform. Martin Wawro, Informatik VII (Graphische Systeme),
OH16, R.120, Tel.: 6344, E-Mail: Martin.Wawro@uni-dortmund.de

Einzelpräsentation: 
9.2.06 in der OH 14, Raum 104, um 14.30 Uhr
Teilnehmer: 
1. Chachaj Adam
2. Frenzel David
3. Garstka Jens
4. Hasebein Anke
5. Kerbitz Rudolf A.
6. Hüntler Timo
7. Petke Matthias
8. Rabe Garvin
9. Ruppelt Mark
10. Schowe Benjamin
11. Sun Peihua
12. Vossebein Dennis
13. Zimmermann Christian
Thematik: 

Das Scannen von dreidimensionalen Objekten hat viele Anwendungsbereiche. In der Medizin werden beispielsweise Hüftgelenke vor der Operation computergest�tzt rekonstruiert, Gesichter von Patienten bei der Korrektur von Augenfehlstellungen vermessen oder Kieferabdrücke in Dentallabors zur automatischen Erstellung von Inlays digitalisiert. In der Industrie werden 3D Modelle erfasst, ummanuell gefertigte Objekte z.B. f�r Simulationszwecke in den Rechner zu transferieren oder diese mit gegebenen CAD-Modellen zu vergleichen. Als weiteres Beispiel befassen sich Historiker u.a. damit, historische Stätten und Objekte zu digitalisieren und diese virtuell zugänglich zu machen. Das Vermessen von ganzen Höhlensystemen oder das Digitalisieren von durch Künstler gefertigten Tonfiguren in der Filmindustrie zwecks Computeranimation sind weitere Beispiele. Fast allen 3D Scans ist dabei gemein, dass Objekte (Abb. 1a) mehrfach aus unterschiedlichen Richtungen erfasst werden, wobei jede Abtastung ein 2.5-dimensionales Höhen-/Gebirgsmodell liefert (Abb. 1c).

(a) (b) (c) (d)

Abbildung 1: (a) Beispiel eines (Spielzeug-)Objekts. (b) Abtastung mittels eines taktilen Scanners. (c) Zwei Höhenmodelle, nebeneinander und ausgerichtet. (d) Zusammengesetztes Objekt.

Um ein komplettes 3D Modell zu erhalten, müssen die einzelnen Scans zusammengefügt werden (Abb. 1d). Ist bekannt, wie die einzelnen Abtastungen zueinander im Raum liegen, d.h. wie ihre Koordinatensysteme im realen Raum anzuordnen sind, ist dies mittels affiner Abbildungen, entsprechende Präzision der Informationen vorausgesetzt, einfach. In der Industrie werden daher Drehteller, auf denen die zu scannenden Objekte platziert werden, oder entsprechende (optische oder andere) Trackingsysteme zur Bestimmung der Scannerposition und -orientierung eingesetzt. Aufgrund der erforderlichen Präzision haben diese allerdings den Nachteil, sehr kostspielig zu sein. Ferner können tonnenschwere Skulpturen auch nicht einfach in einen Scanner gestellt werden und Trackingsysteme zur Erfassung frei positionierbarer Scanner überschreiten ihre Grenze bei 10 oder 20 Meter großen Statuen. Manuelles Tracking mittels Maßband und Winkelmesser liefert zwar erste Anhaltspunkte, ist aber sehr ungenau. Hinzu kommt, dass kleinere, stationäre Scanner, wie derzeit am Lehrstuhl für Graphische Systeme genutzt (Abb. 1 b), nur eine Scanrichtung zulassen und somit das Objekt f�r multiple Scans manuell gedreht werden muss. Das Zusammensetzen der einzelnen Scans, genauer die Ausrichtung der einzelnen Koordinatensysteme zueinander, wird Registrierung genannt. Hierbei unterscheidet man zwischen einer (initialen) Grob- und einer anschließenden Feinregistrierung. W�hrend es f�r letztere ein anerkanntes Verfahren gibt [4], sind automatische Ansätze f�r erstere nicht zufriedenstellend [8]. Eine manuelle Grobregistrierung kann hingegen bei umfangreichen Scans mehrere Wochen in Anspruch nehmen. Zufriedenstellende automatische Ansätze wären also wünschenswert.

Das von der Projektgruppe zu entwickelnde System soll eine automatische Grobregistrierung mit graphisch interaktiver Kontrolle und Korrekturmöglichkeit realisieren. Nachdem die einzelnen Scans registriert worden sind, erfolgt die Triangulierung einer passenden Oberfläche für das Gesamtobjekt [1] (Abb. 1d). Hierfür kann am Lehrstuhl VII verwendete Software eingesetzt werden. Bei der anschließenden Verarbeitung ist in Teilen der Archäologie hierbei besonders der Erhalt von Keilschriften (Abb. 2a) und Siegelabrollungen (Abb. 2b) von Interesse.

(a) (b) (c)

Abbildung 2: (a) Beispiel für Keilschrift. (b) Ein Abrollsiegel. (c) Kenntlichmachung des Siegels.

Um einem weiten Kreis von (Sprach-) Wissenschaftlern Zugang zu entsprechenden Artefakten zu ermöglichen, sollen diese im Internet virtuell zur Verfügung gestellt werden [6]. Die Projektgruppe soll ein entsprechendes Client/Server-Konzept implementieren. Die anfallenden Datenmengen sind allerdings relativ gro�. F�r hochauflösende Scans können durchaus 250MB anfallen, was selbst bei einer DSL-Anbindung zu einer Geduldsprobe wird, von 56K Modems ganz zu schweigen. Die Lösung hierfür liegt in der Reduktion, d.h. Vergröberung des Oberflächennetzes [10]. Während die Keilschriften auch bei reduzierten Netzen, abhängig vom Reduktionsgrad, recht gut zu erkennen sind, verschwinden kleinere Konturen, wie z.B. Siegelabdrücke, relativ schnell. Eine weitere Aufgabe der Projektgruppe besteht somit darin, solche Abdrücke vor der Reduktion zu bewahren. Scharfe Kanten innerhalb der Geometrie können hier als Merkmale dienen. Diese sollen durch Ausnutzung von Abtastinformationen [2], der Struktur eines (2.5D) Oberflächennetzes [9] oder ggf. auch durch Diffusion [7] mit einem zu implementierenden (semi-)automatischen System gewonnen werden. Obwohl bei entsprechendem Ansatz die Datenmenge auf diese Weise drastisch reduziert werden kann, bleibt diese f�r langsame Netzanbindungen immer noch (zu) groß. Hierdurch begründet erscheint eine angepasste Übertragung des dargestellten Objekts, je nachdem wie weit der Betrachter davon entfernt ist, sinnvoll (Abb. 3). Hier soll eine partielle Übermittlung abhängig vom aktuellen Augenpunkt und seiner Veränderung von einem Objekt-Server an einen View-Client in einer level-of-detail Hierarchie [5] erfolgen. Der View-Client soll betriebssystemunabhängig realisiert werden.

Abbildung 3: Beispiel für die unterschiedlichen Sichtweisen eines Objekts beim level-of-detail Ansatz.

Das System soll mit objektorientierten Software-Entwurfsmethoden entwickelt werden [3]. Dabei sollen entsprechende Werkzeuge zum Einsatz kommen, beispielsweise Together. Der Entwurf der Client-Server-Technologie soll durch Harel-Automaten und Petri-Netze [3] unterstützt werden. Eine effiziente Verarbeitung der umfangreichen Daten kann nur durch eine leistungsfähige Software gewährleistet werden. Aufgrund der Rechenkomplexität der Registrierung empfiehlt sich hierfür C++. Die restlichen Komponenten könnten zwar theoretisch beispielsweise auch in Java/Swing/Java3D implementiert werden, mit den rechenintensiven Teilen als native Methoden, es bietet sich aber auch hier aus Effizienzgründen eine Implementierung in C++/Qt/OpenGL an. Eine etwaige "Betriebssystemunabh�ngigkeit" des View-Clients bliebe hierbei auch gewahrt.

Teilnahmevorraussetzungen:

Legende: [V] vorausgesetzt, [W] wünschenswert
  • Vorlesung Mensch-Maschine-Interaktion bzw. Graphische Systeme. [V]
  • Vorlesungen Geometrisches Modellieren, Digitale Bildverarbeitung, Effiziente Algorithmen, Künstliche Intelligenz [W]
  • Kenntnisse in objektorientierter Programmierung und einer einschlägigen Programmiersprache, z.B. Java oder C++. [W]

Minimalziele:

  • Dokumentierter Systementwurf.
  • Analyse und Bewertung verschiedener Methoden zur Grobregistrierung.
  • Dokumentierte Implementierung eines Prototypen zur Rekonstruktion eines, unter Berücksichtigung von Merkmalen (bzgl. Schriften und Siegeln) reduzierten, Objektes.
  • Dokumentierte Implementierung eines Client/Server-Systems zur Darstellung der rekonstruierten Objekte auf der Basis von (interaktiv) vordefinierten Auflösungsstufen.
  • Demonstration der Funktionalität anhand mehrerer gescannter Objekte.

Literatur:

[1] S. Abramowski und H. M�ller. Geometrisches Modellieren. BI-Wissenschaftsverlag, 1992.
[2] C.-P. Alberts. Surface Reconstruction from Scan Paths. Future Generation Computer Systems, Vol. 20, No. 8, 2004, 1285_1298.
[3] H. Balzert. Lehrbuch der Software-Technik. Spektrum Akad. Verlag, 2000.
[4] P.J. Besl und N.D. MacKay. A Method for Registration of 3D Shapes. IEEE Transactions on Pattern Analysis and Machine intelligence, Vol. 14, No. 2, 1992, 239_259.
[5] L. DeFloriani und P. Magillo. Multiresolution Mesh Representation: Models and Data Structures. In: A. Iske, E. Quak und M.S. Floater (Edt.). Tutorials on Multiresolution in Geometric Modelling. Springer, 2002, 363_418.
[6] http://www.hethiter.net
[7] P. Perona und J. Malik. Scale-Space and Edge Detection using Anisotropic Diffusion. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, No. 7, 1990, 629_639.
[8] P. Pingi, A. Fasano, P. Cignoni, C. Montani und R. Scopigno. Exploiting the Scanning Sequence for Automatic Registration of large Sets of Range Maps. EUROGRAPHICS 2005, Vol. 24, No. 3, 2005.
[9] C. Rössl, L. Kobbelt und H.-P. Seidel. Extraction of Feature Lines on triangulated Surfaces using Morphological Operators. Proceedings of the AAAI Symposium on Smart Graphics, 2000, 71_75.
[10] W.J. Schroeder, J.A. Zarge und W.E. Lorensen. Decimation of Triangle Meshes. Computer Graphics, Vol. 26, No. 2, 1992, 65_70.

Rechtliche Hinweise:

Die Ergebnisse der Projektarbeit inklusive der dabei erstellten Software sollen der Fakultät für Informatik uneingeschränkt zur freien Forschung zur Verfügung stehen. Darüber hinaus sind keine Einschränkungen der Verwertungsrechte an den Ergebnissen der Projektgruppe und keine Vertraulichkeitsvereinbarungen vorgesehen.