Abb. 1: Triangulation Scanner
Abb. 2: Abtastung von mehreren Positionen
Abb. 3: Ein aus mehreren Views gescanntes Objekt
Eine der zeitaufwendigsten Aufgaben der Computergrafik ist die Erzeugung geeigneter 3D Modelle. Diese werden dann in diversen Bereichen wie z.B. CAD/CAM (Computer Aided Design/ Computer Aided Manufacturing), Simulation / Animation, Visualisierung, virtuelle Realität usw. weiter verwendet. In der Vergangenheit wurde eine direkte Methode bevorzugt - Modellierung mithilfe eines Modellierungsprogramms (z.B.: Catia, Surfacer, AutoCAD für CAD/CAM Gebiet oder 3D Studio Max, Maya, Truespace, SoftImage für allgeimene Modellierung). Diese (meistens sehr teuere) Programme bieten eine riesige Vielfalt an Modellierungsmöglichkeiten, auf der anderen Seite müssen auch Nachteile erwähnt werden z.B., dass die Erzeugung komplexer Modelle extrem zeitaufwendig ist und der Designer mit den Features des Modellers sehr gut vertraut sein muss.
Ständig billigere und präzisere 3D Scanner und dadurch die Möglichkeit sogar in consumer-Bereich einer digitalen Abtastung eigener 3D-Objekte ermöglichten eine rasche Entwicklung der Objektrekonstruktion (in CAD/CAM Bereich auch reverse engineering genannt). Im Gegensatz zur direkten Modellierung wird hier ein existierendes reales Objekt verwendet, mit einem 3D Scanner abgetastet und die daraus resultierende Punktwolke soll automatisch rekonstruiert werden - je nach der Anwendung kann eine polygonale Oberfläche gebildet werden, bzw. soll die Oberfäche in kohärente Teile zerlegt und mit z.B. parametrischen Flächen approximiert werden, usw. Dieser Prozess soll nach der Angabe der Rekonstruktionsparameter automatisch laufen, mit einer geringen Interaktion durch Menschen (im idealen Fall sogar keinen). Die Schwierigkeit liegt dabei an mangelnder Information, die die 3D-Scanner liefern (meistens nur Punktwolken), am Datenvolumen (Verarbeitung von Millionen von Punkten) und schließlich an einer sehr hohen mathematischen Komplexität der Rekonstruktionsalgorithmen.
Das Forschungsziel unseres Lehrstuhls ist die Entwicklung eines Tools für eine semi-automatische Erzeugung der 3D Modelle aus Punktwolken mit Schwerpunkt CAD/CAM, Visualisierung (im Zusammenarbeit mit dem Anatomischen Institut in Göttingen) und virtuelle Realität.
Bevor die eigentliche Rekonstruktion anfangen kann, muss ein Objekt abgetastet werden. In der Abb. 1 ist das Prinzip eines Triangulation Scanners dargestellt: die Oberfläche des Objektes wird mit einem strukturierten, sind ständig ändernden Licht beleuchtet (bestrahlt) und ein Sensor (z.B. eine CCD Kamera) bestimmt nach den Änderungen des Musters auf der Objektobefläche die Abstände der Punkte von dem Scanner und dadurch die Lage im Raum.
Weitere Technologien:
Magnetoresonanz Imaging [MRI]: hier wird ein starkes Magnetfeld verwendet, um die Wasserstoffkerne aus ihrer Position abzulenken. Sie absorbieren einen Teil der ausgestrahlten Energie, die sie während der Ralaxationsphase (Rückkehr) in die ursprüngliche Position wieder ausstrahlen. Diese Energie wird gemessen und (wie bei CT) können daraus Graustufenbilder erzeugt werden.
Während der Abtastung wird die Oberfläche des Objektes (falls nötig) von mehreren Positionen des Scanners digitalisiert (Abb. 2) und schließlich werden die Scans (sog. Views) in ein gemeinsames Koordinatensystem gebracht und daraus eine Punktwolke konstruiert (Abb. 3 - sog. Registration).
|
|
|
|
Abb. 1: Triangulation Scanner |
Abb. 2: Abtastung von mehreren Positionen |
Abb. 3: Ein aus mehreren Views gescanntes Objekt |
Als Eingabe erhält man bei der Rekonstruktion lediglich eine unstrukturierte verrauschte (je nach dem Scanner) Punktwolke ohne zusätzliche Informationen (Abb. 4). Die erste Aufgabe der Rekonstruktion ist es die Punktwolke zu strukturieren, also eine geeignete Datenstruktur zu erzeugen. Die zwei am häufigsten verwendeten Datenstrukturen (Graphen) sind eine globale Triangulierung (Abb. 5) oder die k-nächsten Nachbarn. Die globale Triangulierung ist eine polygonale Approximation der Oberfläche und eignet sich für die Visualisierung, Weiterverarbeitung (Subdivision, Ausdünnen, Glätten), sogar auch für die Herstellung (es existieren CAM Maschinen, die die Oberfläche direkt aus der Triangulierung herstellen können). Jedoch die Erzeugung der globalen Triangulierung ist ein sehr komplexes und zeitaufwendiges Problem, das für eine beliebige Punktmenge nicht immer lösbar ist.
Unser Ansatz basiert auf den k-nächsten Nachbarn, die mithilfe von Medianunterteilung (sog. Bucketing) und Verteilung der Punkte in Buckets in Hashing Tabellen sehr schnell bestimmt werden können. Die erworbene Nachbarschft kann für die Schätzung der Oberflächeninformationen ersten Grades (die Normalen) und zweiten Graden (die Hauptkrümmungen) benutzt werden. Die Normalenvektoren in jeden Punkt werden mit einem zwei pass Algorithmus approximiert: im ersten Schritt wird die Ausgleichsebene (nach dem PCA [Principal Component Analysis] Prinzip) berechnet. Dadurch wird ein neues lokales Koordinatensystem festgelegt, in dem die Nachbarschaft mit einer quadratischen Fläche approximiert wird. Die Normale in dem Punkt, ist dann die transformierte Normale der quadratischen Fläche. Die Hauptkrümmungen können analog geschätzt werden.
Danach erfolgt eine normalenbasierte Segmentierung, die die Oberfläche aufgrund der Unstetigkeit im Normalenverlauf aufteilt. Durch diese Segmentierung ist es möglich die scharfen Kanten zu detekieren.. Da bei der Normalenschätzung der Punkte nahe zu scharfen Kanten die Nachbarn von beiden Seiten dieser Kante genommen werden konnten, sind diese Normalen in der Regel strak geglättet (je nach der Größe der Nachbarschaft). Wir nutzen die Information der normalenbasierten Segmentierung, um solche Punkte zu finden, ihre Nachbarschft wird modifiziert, so dass sie Punkte nur auf einer Seite der Kante enthält und die Normale wird neu geschätzt. Der Vorgang der Segmentierung mit anschließender Neuberechnung der Normalen kann mehrmals wiederholt werden.
 |
 |
|
Abb. 4: Eine unstrukturierte Punktwolke |
Abb. 5: Globale Triangulierung der Punktwolke |
 |
 |
|
Abb. 6: Segmentierung der Obefläche |
Abb. 7: CAD Repräsentation der Objektoberfläche |
Die normalenbasierte Segmentierung ermöglicht Detektion der C1 unstetigen Übergängen (scharfe Kanten, stark gekrümmte Bereiche). Zwei unterschiedliche Flächen mit einem tangentenstetigen Übergang (z.B. zwischen einem Zylinder und einer Kugel) werden als ein Segment erkannt. Um solche Grenzen zwischen geometrisch unterschiedlichen Flächen zu finden, wird eine krümmungsbasierte Segentierung durchgeführt, die die Oberfläche nach den Unstetigkeiten der Hauptkrümmungen aufteilt. Solange der Datensatz nicht verrauscht ist (künstlich erzeugte Punktwolken) bietet die krümmungsbasierte Segmentierung eine sehr gute Aufteilung der Oberfläche. Punktwolken, die durch Abtasten realer Objekte entstanden sind, enthalten immer einen gewissen Rauschpegel. Im Gegensatz zu Normalen ist die Schätzung der Hauptkrümmungen deutlich empfindlcher gegen Rauschen (Abb.8 und Abb. 9) und deshalb muss nach der krümmungsbasierten Segmentierung eine Nachverarbeitung (Postprocessing) gestartet werden.
|
|
|
|
|
|
Abb. 8: Die Hauptkrümmungen (kmin, kmax) der Punkte auf einer exakten Oberfläche |
Abb. 9: Die Hauptkrümmungen (kmin, kmax) der Punkte auf einer stark verrauschten Oberfläche |
||
Die Postprocessing-prozedur besteht aus zwei Schritten: Klassifikation der Segmente und Erweiterung der kassifizierten Segmente. Es werden fünf algebraische Flächen erkannt und weiter bearbeitet: Ebene, Kugel, Zylinder, Kegel, Torus. Die Klassifikation basiert auf den geschätzten Informationen (Nachbarschaft, Normalen, Hauptkrümmungen), von denen eine Annahme über den Flächentyp gemacht wird. Weiterhin wird eine Minimierungprozedur durchgeführt, die nach einer spezielen Parametrisierung der Fläche die Summe der Abstände der Punkte von der Oberfläche minimiert. Die Minimierungsprozedur liefert die Flächenparameter, anhand deren die Annahme über den Flächentyp akzeptiert oder abgelehnt wird und die weiter benutzt werden, um die Fläche zu erweitern. Die Erweiterungsprozedur testet, ob sich in der Nachbarschaft der Punkte im aktuelen Segment S weitere Punkte befinden, die die Flächengleichung erfüllen. Alle solche Punkte werden zu dem Segment S hinzugefügt.
 |
 |
| Abb. 10: Künstlich generierte Punktwolke verruascht mit starkem additivem Rauschen | Abb. 11: Normalenbasierte Segmentierung |
 |
 |
| Abb. 12: Krümmungsbasierte Segmentierung | Abb. 13: Nach dem ersten Postprocessing Schritt |
 |
|
| Abb. 14: Nach dem zweiten Postprocessing Schritt - die finale Segmentierung | |
Die Abbildungen 10 bis 14 illustrieren den gesamten Rekonstruktionsprozess: in der verrauschten Punktwolke (Abb. 10) werden Nachbarschaften und Oberflächeninformationen geschätzt und die normalenbasierte Segmentierung durchgeführt (Abb. 11). Wie man beobachten kann, wurde die Grenze zwischen der Kugel und dem Zylinder nicht erkannt. Dieses Problem löst teilweise die krümmungsbasierte Segmentierung (Abb. 12), die auf der anderen Seite das Objekt wegen des Rauschens in mehrere Hundert Segmente aufteilt. Die Postprocessing-prozedur räumt die kleinen Segmente auf und die großen Segmente werden klassifiziert und erweitert. Postprocessing arbeitet aufgrund vieler heuristisch geschätzen Parameter, die nicht immer eine perfekte Klassifizierung garantieren. Es ist die Aufgabe des Anwenders nach einem Postprocessing Schritt, falls nötig, die entsprechenden Parameter zu modifizieren und die Postprocessing-prozedur neu zu starten. Im nächsten Durchlauf überprüft die Prozedur, ob die klassifizierten Segmente korrekt erkannt wurden und versucht die restlichen Segmente neu zu klassifizieren. Nach dem zweiten Duchlauf wurden in dem verrauschten Objekt von der Abb. 10 alle Flächen korrekt erkannt und erweitert, so dass kein Oberflächenpunkt übrig geblieben ist (Abb. 14).
|
|
|
|
Abb. 15: Die Rekonstruktionsergebnisse |
|
Nach einer CT oder MRI Abtastung, bzw. nach physichem Aufschneiden der Präparate entsteht eine Menge der Graustufenbilder, aus denen planare geschlossene Polygone, sog. Konturen erzeugt werden können (Abb. 16). Im Gegensatz zu der Rekonstruktion aus unstrukturierten Daten liegt hier eine gewisse Anordnung (Strukturierung) der Daten in den Schnitten vor. Zweitens läßt sich das globale Rekonstruktionsproblem auf eine Zusammensetzung der lokalen Rekonstruktionen zwischen jeweils zwei benachbarten Schnitten vereinfachen.
 |
 |
| Abb. 16: Ein Schnittbild des Objektes und die entsprechenden Konturen | |
Unsere Rekonstruktion basiert auf dem Ansatz von Boissonnat: zuerst werden die Schnitte trianguliert mit einer Delaunay Triangulierung und das duale Voronoi Diagramm wird berechnet. Die Schnitte müssen danach korrigiert werden (falls nötig), so dass alle Konturkanten in der Delaunay Triangulierung enthalten sind und das interne Voronoi Skelett (die Voronoi Kanten dual zu den innerhalb der Konturen liegenden Delaunay Kanten) nicht schneiden. Anschließend wird eine Tetraedrisierung durch Verbinden der Dreiecke mit den Punkten, bzw. von zwei Dreieckskanten von zwei benachbarten Schnitten erzeugt. Dadurch entstehen drei Tetraedertypen:
 |
 |
 |
 |
| T1 Tetraeder: die Umkreismittelpunkte der Deiecke im unteren Schnit werden in den oberen Schnitt projiziert und nach dem nächsten Konturpunkt gesucht. | T2 Tetraeder: die Umkreismittelpunkte der Deiecke im oberen Schnit werden in den unteren Schnitt projiziert nach dem nächsten Konturpunkt gesucht. | T12 Tetraeder: die Delaunay Kanten beider Schnitte, deren duale Voronoi Kanten sich schneiden, werden zu Tetraedern verbunden. | Die resultierende Tetraedrisierung (nach Eliminierungsschritt) |
Da eine Tetraedrisierung der konvexen Hülle erzeugt wird, müssen Tetraeder, die sich nicht auf der Oberfläche befinden, eliminiert werden. Boissonnat hat mehrere Regeln für die Eliminierung der Tetraeder formuliert, diese jedoch garantieren nicht, dass eine konsistente Oberfläche von der Tetraedrisierung extrahiert wird, sog. fold-overs konnten nicht eliminiert werden:
 |
 |
| Abb. 17: Rekonstruktion einer Schicht mit der Boissonnat Methode | Abb. 18 Rekonstruktion einer Schicht mit unserem Ansatz |
Unser Ansatz nimmt als Input die Tetraedrisierung nach Boissonnat. Es wird ein Startdreieck gewählt (ein Dreieck der Tetraedrisierung, das sich auf der Oberfläche befindet) und seine Nachbarn werden überprüft. Man geht von der Tatsache aus, dass sich in der Nachbarschaft eines Oberflächendreiecks das nächste Oberflächendreieck befindet und dass jede Konturkante genau einmal in der Triangulierung einer Schicht zwischen zwei benachbarten Schnitten vorkommen darf. Diese Kriterien genügen, um aus der Tetraedrisierung eine konsistente Oberfläche mithilfe einer rekursiven Prozedur, die Oberflächendreiecke markiert, zu extrahieren. Die Tetraeder werden danach gelöscht.
 |
| Abb.19 : Ergebnis der Rekonstruktion |
