Informatik
Refine
Year of publication
- 2004 (12) (remove)
Document Type
- Diploma Thesis (4)
- diplomthesis (4)
- Conference Proceeding (2)
- Doctoral Thesis (1)
- Report (1)
Language
- German (12) (remove)
Has Fulltext
- yes (12)
Is part of the Bibliography
- no (12)
Keywords
Institute
- Informatik (12)
- Biowissenschaften (1)
- Geowissenschaften (1)
- Mathematik (1)
- Senckenbergische Naturforschende Gesellschaft (1)
Zellularautomaten sind ein massiv paralleles Berechnungsmodell, das aus sehr vielen identischen einfachen Prozessoren oder Zellen besteht, die homogen miteinander verbunden sind und parallel arbeiten. Es gibt Zellularautomaten in unterschiedlichen Ausprägungen. Beispielsweise unterscheidet man die Automaten nach der zur Verfügung stehenden Zeit, nach paralleler oder sequentieller Verarbeitung der Eingabe oder durch Beschränkungen der Kommunikation zwischen den einzelnen Zellen. Benutzt man Zellularautomaten zum Erkennen formaler Sprachen und betrachtet deren generative Mächtigkeit, dann kann bereits das einfachste zellulare Modell kontextsensitive Sprachen akzeptieren. In dieser Arbeit wird die Beschreibungskomplexität von Zellularautomaten betrachtet. Es wird untersucht, wie sich die Beschreibungsgröße einer formalen Sprache verändern kann, wenn die Sprache mit unterschiedlichen Typen von Zellularautomaten oder sequentiellen Modellen beschrieben wird. Ein wesentliches Ergebnis im ersten Teil der Arbeit ist, daß zwischen zwei Automatenklassen, deren entsprechende Sprachklassen echt ineinander enthalten oder unvergleichbar sind, nichtrekursive Tradeoffs existieren. Das heißt, der Größenzuwachs beim Wechsel von einem Automatenmodell in das andere läßt sich durch keine rekursive Funktion beschränken. Im zweiten Teil der Arbeit werden Zellularautomaten dahingehend beschränkt, daß nur eine feste Zellenzahl zugelassen ist. Zusätzlich werden Automaten mit unterschiedlichem Grad an bidirektionaler Kommunikation zwischen den einzelnen Zellen betrachtet, und es wird untersucht, welche Auswirkungen auf die Beschreibungsgröße unterschiedliche Grade an bidirektionaler Kommunikation haben können. Im Gegensatz zum unbeschränkten Modell können polynomielle und damit rekursive obere Schranken bei Umwandlungen zwischen den einzelnen Modellen bewiesen werden. Durch den Beweis unterer Schranken kann in fast allen Fällen auch die Optimalität der Konstruktionen belegt werden.
Moderne Softwaresysteme gewinnen zunehmend an Komplexität und bestehen inzwischen aus einer für Menschen nicht mehr überschaubaren Menge an Quellcode-Zeilen. Die Problematik könnte damit zusammenhängen, dass Programmiersprachen als Sprachen linear orientiert sind. Es stellt sich die Frage, ob graphische Darstellungen besser geeignet wären. Durch das Hinzufügen einer zweiten Dimension könnten Vererbungshierarchien und vernetzte Zusammenhänge – wie beispielsweise Funktionsaufrufe – besser visualisiert und durch das Ausblenden von Implementierungsdetails auf einen Blick erfasst werden. In dieser Arbeit werden Möglichkeiten der Visualisierung untersucht, bei denen der Sourcecode graphisch dargestellt wird und bei denen eine Änderung in der graphischen Darstellung in einem veränderten Sourcecode resultiert. Die Kernfrage, die in dieser Arbeit untersucht werden soll, ist, ob graphisch orientierte Tools die Programmierung wesentlich beschleunigen können. Dabei wird hauptsächlich auf die Visualisierung der vernetzten Strukturen von Klassen und Methoden Wert gelegt sowie auf die automatische Generierung. Ohne eine Automatisierung muss zu viel Zeit investiert werden, um die Darstellung zu erzeugen und mit geänderten Code konsistent zu halten. Dabei werden bisherige Konzepte wie die graphische Modellierungssprache UML beschrieben und die Umsetzung in unterschiedlichen Programmen untersucht. Die Abbildung von UML-Diagrammen in Sourcecode und von Sourcecode in UMLDiagramme bereitet jedoch einige Probleme, da viele Konzepte von UML zu stark abstrahieren und eine Abbildung nicht eindeutig und teilweise nicht möglich ist. Aus diesem Grund wird aufbauend auf den vorhandenen Möglichkeiten ein neues Konzept entwickelt, das prototypisch implementiert wird. Dabei werden viele Elemente von UML genutzt und auf die gestellten Anforderungen angepasst, sodass eine automatische graphische Darstellung parallel zur Programmierung in Textform möglich ist.
Konzept und Implementierung eines Systems zur Visualisierung von Zelldifferenzierungssimulationen
(2004)
Ziel der vorliegenden Arbeit ist es, zunächst den Stand der Forschung auf dem Gebiet der Zelldifferenzierungssimulatoren und –visualisierungen zu ermitteln. Davon ausgehend wurde ein eigenes Konzept für ein Visualisierungssystem entwickelt. Es wurde in einer prototypischen Implementierung mit dem Titel D-VISION umgesetzt. Die Recherchearbeiten ergaben, dass in der Forschung bisher hauptsächlich biochemische Reaktions-Netzwerke, die mithilfe von Differentialgleichungen gelöst werden, für Zell-Simulationen benutzt werden. Der dabei verwendete Abstraktionsgrad der repräsentierten Zellen ist zu hoch, um die gestellten Anforderungen einer realistischen 3D-Darstellung der Zellen zu erfüllen. Die grundlegende Idee, die Zelldifferenzierung aufgrund ihrer Genexpression also der in den Zellen vorhandenen Substanzen zu beschreiben, wurde als Basis für das Konzept für D-VISION verwendet. Die Daten, die visualisiert werden sollen, sind die Zellen selbst, die Substanzen, die in der Zelle vorhanden sind, Substanzen an der Zellhülle und die Gene, die in einer Zelle aktiv sind. Die Visualisierung wird durch Darstellung von aufeinander folgenden Standbildern vorgenommen, in denen navigiert werden kann. Zellen werden in Form von Kugeln repräsentiert, die, um eine realistischere Ansicht zu erreichen, so deformiert werden, dass sich die Kugeloberflächen aneinander angleichen. Die Deformation bietet nicht nur in der Ansicht von außen ein natürliches Bild. Auch die Möglichkeit, ein Schnittbild durch den Zellhaufen zu erzeugen, ergibt durch die Deformation eine mit realen Mikroskopieaufnahmen vergleichbare Darstellung. Ein solches zweidimensionales Schnittbild kann durch Verschieben der Schnittebene eine stufenlose Fahrt durch die Schichten des simulierten Zellhaufens zeigen. Neben den Zellen selbst, liegt ein besonderes Augenmerk auf der Darstellung von Substanzkonzentrationen. Sie werden durch kleine Objekte (Tiny Cubes) dargestellt. Allerdings unterscheidet sich ihr Einsatz von der bisher verbreiteten Methode, volumetrische Daten durch Farbskalen zu repräsentieren. Sie geben die Stoffmengen allein durch ihre Anzahl wieder. Um Zusammenhänge mit der Zelldifferenzierung erkennbar zu machen, können bis zu drei verschiedene Stoffe gleichzeitig angezeigt werden. Der Benutzer hat die Möglichkeit, Regeln bezüglich des Zustandes von Zellen zu formulieren. Die so definierten Zellklassen, fassen Zellen gleichen Typs zusammen und ermöglichen so die Darstellung von Zelldifferenzierung. D-VISION wurde konzipiert, um auch mit Simulatoren zusammen zu arbeiten, die Grid Computing für ihre Berechnungen nutzen. Ein separater Datenaufbereiter soll die Simulationsdaten verwalten. Der entwickelte Prototyp ist flexibel genug, um auch mit einfacheren Simulatoren zusammenzuarbeiten. Auf welchem Weg die visualisierten Daten gewonnen werden, spielt keine Rolle. Auch reine Messwerte, können zu guten Bildern führen.
Die Darstellung photorealistischer Szenen durch Computer hat in Folge der Entwicklung immer effizienterer Algorithmen und leistungsfähigerer Hardware in den vergangenen Jahren gewaltige Fortschritte gemacht. Täuschend echt simulierte Spezialeffekte sind aus kaum einem Hollywood-Spielfilm mehr wegzudenken und sind zum Teil nur sehr schwierig als computergenerierte Bilder zu erkennen. Aufgrund der Komplexität von lebenden Organismen gibt es allerdings noch kein einwandfreies Verfahren, welches ein komplettes Lebewesen realistisch, sei es statisch oder in Bewegung, mit dem Computer simulieren kann. Im Bereich der Animation sind wirkungsvolle Resultate zu verzeichnen, da das Skelett eines Menschen oder Wirbeltieres durch geeignete Methoden simuliert und Bewegungen damit täuschend echt mit dem Computer nachgebildet werden können. Die Schwierigkeit, eine komplett realistische Visualisierung eines Lebewesens zu erreichen, liegt allerdings in der Darstellung weiterer Strukturen eines Organismus, die zwar nicht direkt sichtbar sind aber dennoch Einfluss auf die sichtbaren Bereiche haben. Bei diesen Strukturen handelt es sich um Muskel- und Fettgewebeschichten. Die Oberfläche von Figuren wird durch Muskeln sowohl in der Bewegung als auch in statischen Positionen deutlich sichtbar verändert. Dieser Effekt wird bisher bei der Visualisierung von Lebewesen nur unzureichend beachtet, was zu den aufgeführten nicht vollständig realistisch wirkenden Ergebnissen führt. Bei der Simulation von Muskeln wurden bis heute verschiedene Muskelmodelle entwickelt, die einen Muskel als Gesamtheit in Hinblick auf seine grundsätzlichen physikalischen Eigenschaften, wie z. B. Kraftentwicklung oder Kontraktionsgeschwindigkeit, sehr gut beschreiben. Viele Effekte des Muskels, die sich hauptsächlich auf einer tiefer liegenden Ebene abspielen, sind bis heute noch nicht erforscht, was folglich auch keine entsprechende Simulation auf dem Computer zulässt. Beschrieben werden die verschiedenen Muskeltypen (Skelett-, glatte und Herzmuskulatur) und Muskelformen (spindelförmige, einfach/doppelt gefiedert, etc.). Des weiteren wird auf die unterschiedlichen Muskelfasertypen (FTO, STO, usw.) mit ihren Eigenschaften und Funktionen eingegangen. Weitere Themen sind der strukturelle Aufbau eines Skelettmuskels, der Kontraktionsmechanismus und die Ansteuerung durch Nervenreize. Im Bereich Biomechanik, also der Forschung nach den physikalischen Vorgängen im Muskel, führte die Komplexität der Struktur und Funktionsweise eines Muskels zu einer ausgedehnten Vielfalt an Forschungsarbeiten. Zahlreiche Effekte, die bei einem arbeitenden Muskel beobachtet werden können, konnten bis heute noch nicht erklärt werden. Die Erkenntnisse, die für diese Arbeit relevant sind, sind jedoch in einem ausreichenden Maße erforscht und durch entsprechende mathematische Modelle repräsentierbar. Die Mechanik, die einem Muskel zugrunde liegt, wird auf diesen Modelle aufbauend beschrieben. Neben den Größen, die im später vorgestellten Modell verwendet worden sind, wird auch auf sonstige für biomechanische Untersuchungen relevante Eigenschaften eingegangen. Weiterhin wird dargestellt, wie verschiedene Kontraktionen (Einzelzuckung, Tetanus) mechanisch funktionieren. Für Muskelarbeit und Muskelleistung werden verschiedene Diagramme vorgestellt, welche die Zusammenhänge zwischen den physikalischen Größen Kraft, Geschwindigkeit, Arbeit und Leistung zeigen. Nach Vorstellung der ISOFIT-Methode zur Bestimmung von Muskel-Sehnen-Eigenschaften werden mathematische Formeln und Gleichungen zur Beschreibung von Kraft-Geschwindigkeits- und Kraft-Längen-Verhältnissen sowie der serienelastischen Komponente und der Muskelaktivierung, die zur Bewegungsgleichung führen, angegeben. Es folgen weitere mathematische Funktionen, welche die Aktivierungsvorgänge unterschiedlicher Muskelkontraktionen beschreiben, sowie das Muskelmodell nach Hill, welches seit vielen Jahren eine geeignete Basis für Forschungen im Bereich der Biomechanik darstellt. Bezüglich der Computergraphik wird ein kurzer Abriss gegeben, wie künstliche Menschen modelliert und animiert werden. Eine Übersicht über verschiedene Methoden zur Repräsentation der Oberfläche von Körpern, sowie deren Deformation unter Berücksichtigung der Einwirkung von Muskeln gibt die State-of-the-Art-Recherche. Neben den Oberflächenmodellen (Starrkörperdeformation, lokale Oberflächen-Operatoren, Skinning, Konturverformung, Deformation durch Keyshapes) werden auch Volumen- (Körperrepräsentation durch Primitive, Iso-Flächen) und Multi-Layer-Modelle (3-Layer-Modell, 4-Layer-Modell) vorgestellt und deren Vor- und Nachteile herausgearbeitet. Eine geeignete Repräsentation der Oberfläche, die Verformungen durch Muskelaktivität einbezieht, wurde durch die Benutzung von Pneus gekoppelt mit der Quaoaring-Technik gefunden. Dieses Verfahren, das auf Beobachtungen aus der Biologie basiert und zur Darstellung von organischen Körpern benutzt wird, ist ausgesprochen passend, um einen Muskel-Sehnen-Apparat graphisch darzustellen, handelt es sich doch hierbei auch um eine organische Struktur. Um die beiden Teilmodelle Simulation und Visualisierung zu verbinden, bietet sich die aus der Biomechanik bekannte Actionline an, die eine imaginäre Kraftlinie im Muskel und der Sehne darstellt. Die bei der Quaoaring-Methode verwendete Centerline, welches die Basis zur Modellierung des volumenkonstanten Körpers ist, kann durch die Kopplung an die physikalischen Vorgänge zu einer solchen Actionline erweitert werden. Veränderungen in der Länge und des Verlaufs der Actionline z. B. durch Muskelkontraktion wirken sich dadurch direkt auf die Form des Muskels aus und die Verbindung zur Visualisierung ist hergestellt.
In dieser Diplomarbeit wurde zunächst eine Einführung in das Gebiet der Unifikationstheorie gegeben, um dann zum Teilgebiet des Kontextmatchings zu kommen. Dieses wurde in das Gesamtgebiet der Unifikation eingeordnet. In Anlehnung an [Schm2003] wurde die Komplexität einiger Einschränkungen des Kontextmatchings betrachtet. Insbesondere wurde ein Algorithmus zur Lösung linearer Kontextmatchingprobleme in polynomieller Zeit vorgestellt. Es folgte die Einführung des Transformationsalgorithmus aus [Schm2003] zur Lösung allgemeiner Kontextmatchingprobleme, wobei nach und nach verbesserte Transformationsregeln für einzelne spezielle Problemsituationen vorgestellt wurden. Über [Schm2003] hinausgehend wurden die Regeln Split: Korrespondierende Lochpfade und Konstantenelimination vorgestellt. Im Rahmen der Diplomarbeit wurden die genannten Algorithmen in der funktionalen Programmiersprache Haskell implementiert, wobei auf eine einfache Erweiterbarkeit um neue Transformationsregeln sowie alternative Heuristiken zur Auswahl der in einem Schritt anzuwendenden Transformationsregel geachtet wurde. Die Implementierung (und damit auch die in ihr implementierten Algorithmen) wurde mit Hilfe von zufällig erzeugten Termen auf ihre Leistungsfähigkeit getestet. Hauptaugenmerk lag dabei darauf, inwiefern sich Regeln, die über die Basisregeln aus Tabelle 3.4.1 hinausgehen, positiv auf die Anzahl der Transformationsschritte auswirken. Das Ergebnis ist beeindruckend: durch die Einführung komplexerer Transformationsregeln ließen sich in unseren Testfällen bis zu 87% der Transformationsschritte einsparen, im Durchschnitt immerhin noch 83%. Speziell komplexere Kontextmatchingprobleme mit einer größeren Anzahl an Kontextvariablen profitieren hiervon. Insbesondere die Erkennung korrespondierender Positionen in Verbindung mit der Regel Split führte zu erheblichen Verbesserungen. Die implementierten Algorithmen zur Erkennung korrespondierender Positionen stellen teilweise nur ein notwendiges Kriterium für die Existenz korrespondierender Löcher dar. Dies kann zu fehlerhaften Erkennungen solcher Positionen führen. Wie sich in unseren Tests zeigte, scheint das jedoch kein gravierendes Problem zu sein, da die entsprechenden Split- Transformationen ohnehin äußerst sparsam eingesetzt werden.
Wir haben ein Softwaresystem entwickelt, das in der Lage ist, Beschreibungen von Termersetzungssystemen höherer Ordnung, deren Reduktionsregeln auf einer strukturellen operationalen Semantik basieren, einzulesen und zu interpretieren. Das System ist dabei fähig, Reduktionskontexte für die Redexsuche zu benutzen, die entweder vom Benutzer definiert werden können oder automatisch anhand der strikten Positionen berechnet werden. Außerdem dürfen Kontexte und spezielle Definitionen für Term-Mengen, die wir Domains nennen, in den Reduktionsregeln verwendet werden. Mit dem resultierenden Reduktionssystem-Format können wir somit nicht nur den „lazy“ Lambda-Kalkül, den Call-by-Value Lambda-Kalkül und verwandte, um Konstruktoren und Fallunterscheidungen erweiterte Kalküle, wie die in Kapitel 4 vorgestellten Kernsprachen KFP und PCF, darstellen, sondern auch den (in Abschnitt 4.3 vorgestellten) Call-by-Need Lambda-Kalkül, welcher sich durch die Verwendung von Kontexten innerhalb der Regeln deutlich von den anderen Kalkülen abhebt. Allerdings hält sich der Call-by-Need Lambda-Kalkül damit nicht an das in Kapitel 5 vorgestellte GDSOS-Format, das u.a. sicherstellt, dass Bisimulation eine Kongruenz ist. Wir haben dabei in Abschnitt 5.3.3 bewiesen, dass sich ein GDSOS-Reduktionssystem in ein äquivalentes strukturiertes Auswertungssystem nach Howe übersetzen lässt. Unser System ist in der Lage, die GDSOS-Bedingungen zu prüfen und gibt eine Warnung aus, falls eine der nötigen Bedingungen nicht erfüllt ist (wobei aus dieser auch gleich der Grund des Verstoßes hervorgeht). Wie wir gesehen haben, ist unser System nicht nur befähigt, die einzelnen Reduktionsschritte für kleinere Bespiele ordnungsgemäß auszuführen, sondern es ist durchaus in der Lage, auch aufwendigere KFP-Ausdrücke, wie in unserem Quicksort- Beispiel, auszuwerten.
In den Anwendungsbereichen der Mixed Reality (MR) werden die reale und die virtuelle Welt kombiniert, so dass ein Eindruck der Koexistenz beider Welten entsteht. Meist wird dabei die reale Umgebung durch virtuelle Objekte angereichert, die dem Anwender zusätzliche Informationen bieten sollen. Um die virtuellen Objekte richtig zu positionieren, muss die reale Umgebung erkannt werden. Diese Erkennung der realen Umgebung wird meist durch Bestimmung und Verfolgung von Orientierung und Positionierung der realen Objekte realisiert, was als Tracking bezeichnet wird und einen der wichtigsten Bestandteile für MR-Anwendung darstellt. Ohne die exakte Ausrichtung von realen und virtuellen Objekten, geht die Illusion verloren, dass die virtuellen Objekte Teil der realen Umgebung sind und mit ihr verschmelzen. Markerkombination Das markerbasierte Tracking ist ein Verfahren, das die Bestimmung der Positionierung von realen Objekten durch zusätzliche Markierungen in der realen Umgebung ermöglicht. Diese Markierungen können besonders gut durch Bildanalyseverfahren extrahiert werden und bieten anhand ihrer speziellen Form Positionierungsinformationen. Der Einsatz dieser Trackingtechnologie ist dabei denkbar einfache und kostengünstig. Ein breiter Anwendungsbereich ist durch den kostengünstigen Einsatz dieser Technologien gegeben, allerdings ist das Erstellen von MR-Anwendungen fast ausschließlich MR-Spezialisten vorbehalten, die über Programmierfertigkeiten und spezielle Kenntnisse aus dem MR-Bereich besitzen. Diese Arbeit beschreibt die Entwicklung und Umsetzung der Konzepte, die einem Personenkreis, der lediglich über geringe Kenntnisse von MR-Technologien und deren Anwendung verfügt, den kostengünstigen und einfachen Einsatz von markerbasierten Trackingtechnologien ermöglicht. Die im Rahmen der Arbeit durchgeführte Analyse verweist auf die problematischen Anwendungsfälle des markerbasierten Trackings, die durch die Verdeckung von Markern zustande kommen, in der Beschränkung der Markeranzahl begründet sind, oder durch die Schwankung der Trackingangaben entstehen. Diese Problembereiche sind bei der Entwicklung berücksichtigt worden und können mit Hilfe der entwickelten Konzepte vom Autor bewältigt werden. Das Konzept der Markerkategorien ermöglicht dabei den Einsatz von angepassten Filterungstechniken. Die redundante Markerkombination behebt das Verdeckungsproblem und eliminiert Schwankungen durch das Kombinieren von mehreren Trackinginformationen. Die Gütefunktion ermöglicht die Bewertung von Trackinginformationen und wird zur Gewichtung der Trackingangaben innerhalb einer Markerkombination genutzt. Das Konzept der Markertupel ermöglicht eine Wiederverwendung von Markern, durch den Ansatz der Bereichsunterteilung. Die Konzepte sind in der AMIRE-Umgebung vollständig implementiert und getestet worden. Zum Abschluss ist rückblickend eine kritische Betrachtung der Arbeit, in punkto Vorgehensweise und erreichter Ergebnisse durchgeführt worden.
Robuste Anaphernresolution
(2004)