Einführung FaceCenterPoints Zyklenberechnung VESTA-Zyklen Triangulierung Abstandsgesetz Ergebnisse Ausblick Anwendung Quellennachweise

Auch wenn die Berechnung von Oberflächen in diesem Praktikum zufriedenstellend implementiert wurde, lässt sich diese Implementation noch verbessern. Einerseits kann man versuchen, die Rechenzeit zu reduzieren, andererseits kann man darüber nachdenken, wie man mit noch weniger Speicher auskommt. Darüber hinaus lassen sich noch noch weitere Funktionalitäten hinzufügen, die insbesondere im Rahmen des ILATO-Projekts nützlich sein können. Einzelne Ideen sind im folgenden aufgeführt:

Parallelisierung:
Um Rechenzeit zu senken, ist neben einer vielleicht etwas geschickteren Strukturierung der Funktionen und Abfragen die Parallelisierung der Berechnungen das Mittel der Wahl. Da die VESTA-Zyklen in dieser Implementierung unabhängig voneinander berechnet werden, ist dies möglich. Die einzige Einschränkung dürfte darin bestehen, dass man nicht parallel an zwei nahe beieinander liegenden FCPs Berechnungen vornehmen lässt, da sie beide demselben Zyklus angehören könnten und man somit einen Zyklus doppelt berechnen könnte (die FCPs müssen mindestens einen Abstand von drei FCP-Ebenen aufweisen). Die Information darüber, ob ein Zyklus durch einen FCP läuft, wird ja in einer der Variablen visitedNorth, visitedEast, visitedSouth und visitedWest abgelegt, und bei einer Parallelisierung kann es sein, dass diese Information nicht rechtzeitig gelesen wird. Allerdings gibt es die Möglichkeit, ohne diese vier boolschen visited-Variablen auszukommen.
Speicheroptimierung:
Dieser Punkt ist vielleicht der interessanteste. Schlei spricht in seinem Paper davon, dass der von ihm entwickelte ursprüngliche VESTA-Algorithmus einen erheblichen Speicherbedarf habe, und leitet daraus die Notwendigkeit ab, eine speicheroptimierte Version des VESTA-Algorithmus zu entwickeln. Sein Vorschlag ist die von ihm als 'marching VESTA' bezeichnete Version, die er in seinem Paper ausführlich vorstellt. Auch wenn die in diesem Praktikum entwickelte Version aufgrund der Verweisstruktur mittels der Vektoren xfIndex, yfIndex und zfIndex schon relativ speichereffizient sein dürfte, lässt sich noch weiter Speicher einsparen. Folgende Möglichkeiten sind denkbar:
- Man speichert überhaupt keine FCPs ab und verzichtet gänzlich auf solche Konstrukte wie xfIndex etc. Das würde bedeuten, dass man einfach über das Skalarfeld iteriert und direkt, wenn man auf eine Grenze zwischen einem aktivem und einem inaktiven Voxel stößt, einen VESTA-Zyklus berechnet. Das Problem, das man dabei bewältigen muss, ist, dass man keine Zyklen doppelt berechnet, da man ja nirgends die Information darüber ablegt, ob ein Zyklus an einem FCP bereits berechnet und gezeichnet wurde. Das Problem lässt sich lösen, wenn man sich überlegt, in welche Richtungen man bei einem Face Center Point initial starten muss und in welche Richtungen man nicht starten darf, um alle VESTA-Zyklen zu generieren, aber keinen Zyklus doppelt zu berechnen (wenn man sich auf einer senkrechten Fläche ohne Kanten und Ecken befindet, reicht es beispielsweise aus, wenn man in nur eine Richtung startet). Ein Nachteil dieser Implementierung ist, dass man alle Vertices genau 4-mal berechnet, da genau 4 verschiedene Zyklen durch einen Face Center Point gehen. Zwar verzichtet man bei der Berechnung der VESTA-Zyklen auf eine zusätzliche Datenstruktur, aber die Mesh enthält am Ende 4-mal so viele Vertices. Das sind etwa genau so viele, wie Schleis Version des 'marching VESTA' erzeugt. Verwendet man überdies OpenMesh (wie in dieser Implementation), so würde man am Ende keine geschlossene Halbkantenliste erhalten. Man müsste die 4 Vertices dann jeweils zu einem Vertex zusammenführen - was wiederum zusätzliche Rechenzeit kosten würde.
- Man speichert die FCPs ab (in allFCP), verzichtet aber auf die Konstrukte xfIndex, yfIndex und zfIndex. Das Problem der Navigation zwischen den einzelnen FCPs könnte man dann mittels einer hash table lösen. Ob das effizient möglich ist, müsste untersucht werden.
- Man hält an der Datenstruktur dieser Implementation mit dem FCP-struct und den Vektoren xfIndex etc. fest, aber man berechnet die FCPs und diese Vektoren nicht gleich für das gesamte Skalarfeld, sondern nur für den Bereich, für den man sie zur Berechnung der VESTA-Zyklen gerade braucht - also für genau 3 Ebenen in dem Skalarfeld. Sobald man die Zyklen zwischen diesen 3 Ebenen berechnet hat, vergißt man die Werte der ersten Ebene und ersetzt sie durch die Werte der nächsten Ebene und rückt so Ebene für Ebene in dem Skalarfeld vor. Bei einer Kantenlänge von 1000 ergäbe sich dann eine Speicherersparnis von ca. 99.7 Prozent! Der Nachteil dieses Ansatzes bestünde darin, dass eine Parallelisierung nur eingeschränkt möglich ist. Trotzdem könnte dieser Ansatz der vielversprechendste sein.
Schwellwerterkennung:
Eine zusätzliche Funktionalität, die sehr nützlich wäre, ist die Ermittlung eines geeigneten Isowertes. Liegen beispielsweise Daten aus aus einem CT-Scan vor, so ist erst einmal nicht klar, welcher Isowert der geeignete Schwellenwert ist, der das Innere vom Äußeren des Objektes trennt. Die Klasse surfaceExtraction bietet momentan keine Methode an, die einen vernünfigen Isowert berechnet, und man ist zur Zeit gezwungen, durch Probieren und Anschauen sich an den besten Schwellenwert heranzutasten. Wie unterschiedlich die Ergebnisse sind, die verschiedene Schwellenwerte liefern, sieht man hier. Auch werden bei sehr vielen Schwellenwerten gar keine Isoflächen erzeugt (oder nur rudimentäre Schrumpfformen, die keine Ähnlichkeit mit dem gescannten Objekt aufweisen). Eine Möglichkeit, einen vernünftigen Isowert zu finden, bietet das Histogramm: Dort, wo ein besonders starkes Gefälle in der Häufigkeitsverteilung der Dichtewerte zu finden ist, liegt eine Stelle vor, die als Isowert in Frage kommen könnte.
Mustererkennung:
Bestimmte Dichtewerte eines Skalarfeldes gehören nicht unbedingt zu dem Objekt, das im Rahmen eines Projektes untersucht werden soll. So ist zum Beispiel bei dem Frog-Datensatz ein rechteckig geformtes, durchlöchertes Objekt zu sehen (Abb. 29 rechts), das offenkundig nicht zum Frosch gehört - möglicherweise stellt es einen Objektträger dar. Man könnte sich überlegen, ob man mittels Mustererkennung derartige Teile des Datensatzes von der Behandlung durch den VESTA-Algorithmus ausschließen kann, insbesondere die Flächen, auf denen das eigentliche Objekt ruht. Meistens befinden sie solche Flächen am Rand des Skalarfeldes und sind quaderförmig. Außerdem dürften sie in der Regel eine signifikant andere Dichte aufweisen als das Material des eigentlichen Objektes.
Ermittlung der Oberflächengüte:
Im Rahmen des ILATO-Projekts werden Objekte mithilfe eines CT-Scans teilweise nur unvollständig rekonstruiert, weil sie nicht aus allen Richtungen durchleuchtet werden, sondern der Röntgenstrahl nur aus einem begrenzten Winkel auf das Objekt eintrifft. Artefakte, die dadurch entstehen, müssen erkannt, und Oberflächen, die gut rekonstruiert worden sind, sollten beibehalten werden. Es wäre daher für dieses Projekt sinnvoll, dass man an jedem Oberflächenelement der Isofläche eine Information hinterlegt, die darüber Auskunft gibt, ob dieses Oberflächenelement als Grenzfläche zwischen Innen und Außen in Frage kommt. Folgendes Kriterium kann dazu dienen, die Güte der Oberfläche zu bestimmen: Wenn sich der Verlauf der Oberfläche robust gegenüber kleinen Änderungen des Isowertes erweist, dann ist das ein Indiz dafür, dass es sich um eine gute Rekonstruktion handelt; wenn sich die Oberfläche allerdings bei minimalen Änderungen des Isowertes dramatisch verändert, sollten die entsprechenden Oberflächenelemente verworfen werden - oder mathematischer ausgedrückt: Wenn im Histogramm der Dichtewerte ein steiler Gradient vorliegt, ist das ein Indiz dafür, dass es sich um eine gute Rekonstruktion der Oberfläche handelt.

Arbeiten eher theoretischer Natur lassen sich außerdem zu dem Vergleich zwischen VESTA-Algorithmus und 'Marching Cube'-Algorithmus schreiben. Fragen wie folgende lassen sich dazu stellen: Inwieweit lassen sich beide Algorithmen ineinander überführen? Inwieweit produzieren sie dieselben Isoflächen? Lassen sich alle Flächen, die vom VESTA-Algorithmus erzeugt werden, auch vom 'Marching Cube' erzeugen? Oder gibt es prinzipielle Unterschiede? Ist ein vergleichbarer 'Marching Cube'-Algorithmus prinzipiell schneller oder langsamer? Benötigt er genauso viel Speicher, oder benötigt er grundsätzlich weniger Speicher? Ist es vielleicht sinnvoll, die Templates des 'Marching Cube' mithilfe des VESTA-Algorithmus zu berechnen? Oder ist es besser, eine Variante des VESTA-Algorithmus zu verwenden, die sich am 'Marching Cube' orientiert (wie der 'marching VESTA' von Schlei)?

weiter

Einführung FaceCenterPoints Zyklenberechnung Vesta-Zyklen Triangulierung Abstandsgesetz Ergebnisse Ausblick Anwendung Quellennachweise