Universität Stuttgart
Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1
Browse
Search Results
Item Open Access Interactive volume rendering in virtual environments(2003) Schulze-Döbold, Jürgen Peter; Ertl, Thomas (Prof. Dr.)This dissertation is about the interactive visualization of volume data in virtual environments. Only data on regular grids will be discussed. Research was conducted on three major topics: visualization algorithms, user interfaces, and parallelization of the visualization algorithms. Because the shear-warp algorithm is a very fast CPU-based volume rendering algorithm, it was investigated how it could be adapted to the characteristics of virtual environments. This required the support of perspective projection, as well as specific developments for interactive work, for instance a variable frame rate or the application of clipping planes. Another issue was the improvement of image quality by the utilization of pre-integration for the compositing. Concerning the user interface, a transfer function editor was created, which was tailored to the conditions of virtual environments. It should be usable as intuitively as possible, even with imprecise input devices or low display resolutions. Further research was done in the field of direct interaction, for instance a detail probe was developed which is useful to look inside of a dataset. In order to run the user interface on a variety of output devices, a device independent menu and widget system was developed. The shear-warp algorithm was accelerated by a parallelization which is based on MPI. For the actual volume rendering, a remote parallel computer can be employed, which needs to be linked to the display computer via a network connection. Because the image transfer turned out to be the bottleneck of this solution, it is compressed before being transferred. Furthermore, it will be described how all the above developments were combined to a volume rendering system, and how they were integrated into an existing visualization toolkit.Item Open Access Computational and logical aspects of infinite monoids(2003) Lohrey, Markus; Diekert, Volker (Prof. Dr.)The present work contains a treatise of several computational and logical aspects of infinite monoids. The first chapter is devoted to the word problem for finitely generated monoids. In particular, the relationship between the the computational complexity of the word problem and the syntactical properties of monoid presentations is investigated. The second chapter studies Cayley-graphs of finitely generated monoids under a logical point of view. Cayley-graphs of groups play an important role in combinatorial group theory. We will study first-order and monadic second-order theories of Cayley-graphs for both groups and monoids. The third chapter deals with word equations over monoids. Using the graph product operation, which generalizes both the free and the direct product, we generalize the seminal decidability results of Makanin on free monoids and groups to larger classes of monoids.Item Open Access Integration von Data Mining und Online Analytical Processing : eine Analyse von Datenschemata, Systemarchitekturen und Optimierungsstrategien(2003) Schwarz, Holger; Mitschang, Bernhard (Prof. Dr.-Ing. habil.)Die technischen Möglichkeiten, Daten zu erfassen und dauerhaft zu speichern, sind heute so ausgereift, dass insbesondere in Unternehmen und anderen Organisationen große Datenbestände verfügbar sind. In diesen Datenbeständen, häufig als Data Warehouse bezeichnet, sind alle relevanten Informationen zu den Organisationen selbst, den in ihnen ablaufenden Prozessen sowie deren Interaktion mit anderen Organisationen enthalten. Vielfach stellt die zielgerichtete Analyse der Datenbestände den entscheidenden Erfolgsfaktor für Organisationen dar. Zur Analyse der Daten in einem Data Warehouse sind verschiedenste Ansätze verfügbar und erprobt. Zwei der wichtigsten Vertreter sind das Online Analytical Processing (OLAP) und das Data Mining. Beide setzen unterschiedliche Schwerpunkte und werden bisher in der Regel weitgehend isoliert eingesetzt. In dieser Arbeit wird zunächst gezeigt, dass eine umfassende Analyse der Datenbestände in einem Data Warehouse nur durch den integrierten Einsatz beider Analyseansätze erzielt werden kann. Einzelne Fragestellungen, die sich aus diesem Integrationsbedarf ergeben werden ausführlich diskutiert. Zu den betrachteten Fragestellungen gehört die geeignete Modellierung der Daten in einem Data Warehouse. Bei der Bewertung gängiger Modellierungsansätze fließen insbesondere die Anforderungen ein, die sich durch den beschriebenen Integrationsansatz ergeben. Als Ergebnis wird ein konzeptuelles Datenmodell vorgestellt, das Informationen in einer Weise strukturiert, die für OLAP und Data Mining gleichermaßen geeignet ist. Im Bereich der logischen Modellierung werden schließlich diejenigen Schematypen identifiziert, die die Integration der Analyseansätze geeignet unterstützen. Im nächsten Schritt sind die für Data Mining und OLAP unterschiedlichen Systemarchitekturen Gegenstand dieser Arbeit. Deren umfassende Diskussion ergibt eine Reihe von Defiziten. Dies führt schließlich zu einer erweiterten Systemarchitektur, die die Schwachstellen beseitigt und die angestrebte Integration geeignet unterstützt. Die erweiterte Systemarchitektur weist eine Komponente zur anwendungsunabhängigen Optimierung unterschiedlicher Analyseanwendungen auf. Ein dritter Schwerpunkt dieser Arbeit besteht in der Identifikation geeigneter Optimierungsansätze hierfür. Die Bewertung der Ansätze wird einerseits qualitativ durchgeführt. Andererseits wird das Optimierungspotenzial der einzelnen Ansätze auch auf der Grundlage umfangreicher Messreihen gezeigt.Item Open Access Validierung komponentenbasierter Software für Echtzeitsysteme(2003) Fleisch, Wolfgang; Göhner, Peter (Prof. Dr.-Ing. Dr. h.c.)Der Anteil und die Bedeutung von Software bei der Entwicklung von Echtzeitsystemen wächst sehr stark. Gleichzeitig werden die Entwicklungszyklen für Software-Produkte zunehmend kürzer, was sich immer häufiger in ausgelieferter fehlerhafter Software widerspiegelt. Durch die Verwendung vorgefertigter Software-Komponenten kann nach dem Baukastenprinzip bei der Konstruktion neuer Produkte die Produktivität und die Qualität erheblich gesteigert werden. Aber auch wenn durch den Einsatz geprüfter, betriebsbewährter Software-Komponenten viele Fehler vermieden werden, muss eine aus Komponenten zusammengesetzte Software auch in Zukunft mit geeigneten Prüfverfahren validiert werden, weil beim Zusammenspiel der Komponenten weiterhin Fehler entstehen können. In der vorliegenden Arbeit wird dazu ein Prüfverfahren zur Validierung komponentenbasierter Software für Echtzeitsysteme entwickelt, das das dynamische Verhalten von komponentenbasierter Software gegenüber den Anforderungen aus Anwendersicht überprüft. Die Anforderungen werden zu Beginn der komponentenbasierten Softwareentwicklung als Anwendungsfälle spezifiziert. Mit Hilfe von erweiterten UML Sequenzdiagrammen werden die Anwendungsfälle systematisch in eine formale, automatisiert prüfbare Notation überführt, die auch die Spezifikation von Echtzeitanforderungen explizit unterstützt. Da beim Entwurf von komponentenbasierter Software bereits vollständig spezifizierte Software-Komponenten verwendet werden, kann das Verhalten schon in der frühen Entwurfsphase mit Hilfe von Simulation validiert werden. Die Verwendung von Simulation hat den Vorteil, dass auch ohne die in der Praxis meist spät verfügbaren Bestandteile des technischen Prozesses und des Automatisierungsrechnersystems eine Prüfung des simulierten Verhaltens der komponentenbasierten Software durchgeführt werden kann. Anhand festgelegter Prüfkriterien wird dann das simulierte Verhalten der komponentenbasierten Software gegenüber dem in den Anwendungsfällen spezifizierten Verhalten geprüft, um damit frühzeitig Fehler aufzudecken. Eine im Rahmen der Arbeit realisierte Validierungsumgebung unterstützt den Softwareentwickler dabei umfassend, angefangen bei der Spezifikation von prüfbaren Anwendungsfällen, bis hin zur automatisierten Prüfung des simulierten Verhaltens. Die Leistungsfähigkeit des Prüfverfahrens und der Validierungsumgebung werden abschließend am Beispiel der Entwicklung und Validierung einer komponentenbasierten Software für eine Kfz-Scheibenwischeranlage demonstriert.Item Open Access Direct volume visualization of geometrically unpleasant meshes(2003) Kraus, Martin; Ertl, Thomas (Prof. Dr.)Interactive volume visualization (i.e., the visualization of scalar data defined on volumetric meshes in real time) is not only difficult to achieve for large meshes but it is also complicated by particular geometric features of volumetric meshes, e.g., non-uniform cells, non-convex boundaries, or visibility cycles. This thesis addresses several of these geometric features and their unpleasant consequences with respect to direct volume visualization, which is one of the most successful techniques for interactive volume visualization. In order to overcome, or at least alleviate, these difficulties, several new algorithmic solutions are presented: pre-integrated cell projection and hardware-assisted ray casting for non-uniform meshes, edge collapses in non-convex meshes, cell sorting and cell projection for non-convex and cyclic meshes, as well as texture-based pre-integrated volume rendering, topology-guided downsampling, and adaptive volume textures for non-simplicial volumetric meshes (i.e., non-tetrahedral meshes). As this work cannot cover all geometrically unpleasant features of volumetric meshes, particular emphasis is put on a description of the development of the proposed algorithms. In fact, most of the presented techniques are (or may be interpreted as) generalizations, adaptations, or extensions of existing methods. The intention of explaining these origins is to motivate new solutions for those geometrically unpleasant features of meshes that were out of the scope of this work.Item Open Access Query processing concepts and techniques for set containment tests(2003) Rantzau, Ralf; Mitschang, Bernhard (Prof. Dr.-Ing. habil.)Relational division is an operator of the relational algebra that realizes universal quantifications in queries against a relational database. Expressing a universal quantification problem in SQL is cumbersome. If the division operator would have a counterpart in a query language, a more intuitive formulation of universal quantification problems would be possible. Although division is a derived operator - it can be expressed using other basic algebra operators - the performance of queries involving a division problem can be significantly increased if it is implemented as a separate operator in a query processor. In this work, we study relational division as well as operators related to it like set containment join. We present a classification of division algorithms and define algebraic laws to enable query optimization for queries involving division. A natural generalization of the division operator, called set containment division, is proposed and algorithms that realize it are discussed, including an algorithm that uses a new in-memory index data structure. Furthermore, we study strategies for parallelizing set containment division algorithms. The most popular data mining sub-task called frequent itemset discovery, where one tries to find the number of transactions that contain a given set of items, is an excellent example of a problem that requires efficient set containment tests. In this work, we focus on frequent itemset discovery algorithms that exploit the query processing capabilities of a relational database system. After reviewing the best algorithms based on SQL-92, we suggest a new approach, called Quiver, that can be executed with the help of set containment division. We report on performance results that cover experiments with frequent itemset discovery algorithms running on commercial database systems as well as experiments that highlight the most important properties of set containment test algorithms using a query processor prototype implemented in Java.Item Open Access Modellierung und Ablaufplanung adaptiver Multimedia-Dokumente(2003) Wirag, Stefan; Rothermel, Kurt (Prof. Dr. Dr.)Multimedia-Dokumente ermöglichen eine integrierte Präsentation diskreter und kontinuierlicher Medien. In einer verteilten Umgebung werden Multimedia-Dokumente typischerweise auf Servern gespeichert. Von dort können sie bei Bedarf abgerufen und präsentiert werden. Durch die enthaltenen kontinuierlichen Medien erfordert die Präsentation von Multimedia-Dokumenten viele Ressourcen, so daß schnell Ressourcenengpässe entstehen, wodurch es unmöglich wird ein Multimedia-Dokument wie spezifiziert zu präsentieren. Das Resultat ist eine reduzierte Präsentationsqualität und manchmal kann es sogar unmöglich werden ein Dokument zu präsentieren. Eine Lösung für dieses Problem bieten Multimedia-Dokumente, die sich an unterschiedliche Ressourcensituationen anpassen können. Adaptive Multimedia-Dokumente enthalten Präsentationsalternativen, die unterschiedliche Ressourcenanforderungen implizieren. Bei der Vorbereitung der Präsentation eines Multimedia-Dokuments wird dann eine geeignete Untermenge der Präsentationsalternativen unter Berücksichtigung der momentanen Ressourcensituation ausgewählt. In der Arbeit wird ein Modell für adaptive Multimedia-Dokumente vorgestellt und es werden Implikationen erörtert, die sich durch die Adaptivität in Bezug auf die Dokumenterstellung, die Konsistenzwahrung, die Ablaufplanung und die Architektur eines Dokumentensystems ergeben. Das entwickelte Dokumentenmodell integriert Abstraktionen zur Definition von alternativen Präsentationsmöglichkeiten sowie zur Steuerung der Auswahl von Präsentationsalternativen während der Präsentation. Der Schwerpunkt liegt hierbei auf der Modellierung adaptiver zeitlicher Aspekte. Da die Spezifikation von Präsentationsalternativen zu einer komplexeren Dokumentstruktur führt, wird ein graphisches Autorensystem erforderlich, das die Erstellung von adaptiven Multimedia-Dokumenten mittels visuellen Programmiertechniken ermöglicht. In der Arbeit wird ein Vorschlag für die Benutzerschnittstelle eines solchen Autorensystems erörtert. Dieses Konzept verwendet drei Ansichten, um die unterschiedlichen Aspekte eines adaptiven Multimedia-Dokuments zu visualisieren und zu erstellen. Eine komplexere Dokumentstruktur impliziert auch mehr Spezifikationsfehler. Es wurde daher ein automatischer Konsistenzprüfungsmechanismus entwickelt, der eine aufwendige und zeitintensive manuelle Fehlersuche vermeidet. Bevor ein Multimedia-Dokument präsentiert werden kann, muß das Präsentationssystem einen Ablaufplan erstellen, der beschreibt, wann welche Aktion durchgeführt werden muß, um eine Multimedia-Präsentation entsprechend dem Multimedia-Dokument zu erzeugen. Die Arbeit beschreibt einen adaptiven Ablaufplanungsalgorithmus, der die Ressourcensituation der Präsentationsumgebung bei der Erstellung von Ablaufplänen berücksichtigt. Der Algorithmus ermöglicht die Bestimmung der besten Kombination von Präsentationsalternativen, welche nicht mehr Ressourcen benötigt als verfügbar sind. Die vorgestellten Konzepte wurden prototypisch als Multimedia-Dokumentensystem implementiert, das über standardisierte Internet-Protokolle mit Dokument-Servern kommuniziert. Da die Nutzeranforderungen im Hinblick auf die Gestaltung von Multimedia-Dokumenten stetig wachsen, basiert das entwickelte Dokumentensystem auf einer Architektur, welche die Integration neuer Medientypen und Darstellungskonzepte für Medientypen unterstützt.Item Open Access An enhanced application model for scheduling in grid environments(2003) Ruffner, Christoph; Marrón, Pedro José; Rothermel, KurtApplication scheduling in Grid computing requires information about tasks in each application, as well as a description of the available resources that the scheduler needs, to find an efficient assignment of tasks to resources. In this context, information about applications is provided by the application model. Most current models are restricted to only a few features, but in some cases, such as simulations, which are an important example of Grid applications, more detailed information is available. In this paper, we propose an enhanced application model based on the concept of task refinements, which provide the scheduler with fine-grained information and allow it to determine more efficient schedules than traditional approaches. We backup and show the feasibility of our model by means of experimental evaluations.Item Open Access On recognition of group of human beings in images with navigation strategies : using efficient matching algorithms with parallelization(2003) Piriyakumar, Douglas Antony Louis; Levi, Paul (Prof. Dr.)Eventhough the aim of the study is to recognize the human beings in the images from monocular camera without usual constraints, initially the graph theory based methods for matching are analyzed with new neighbour isomorphism. The robust Hausdorff method of matching is extended to recognize the human beings with ample models and modified distance measures. As the strategy to fuse different algorithms to get better results despite occlusions is inherently parallel, the parallel implementations on Cray T3E produced correct results in appreciably shorter computation time. As industrial applications in robotics, three example situations, one with known environment, another with unknown environment and the third with going around were discussed taking primitive models with human beings as obstacles. Unless the problem of choosing a proper model with the good indexing is available, the recognition of human beings will continue to remain as one of the hard problems to be solved.Item Open Access Innovative Verfahren zur Erweiterung der Mess- und Prüftechnik von MMICs(2003) Berger, Niels Helge; Landstorfer, Friedrich M. (Prof. Dr.-Ing.)Im Mittelpunkt der vorliegenden Arbeit steht die Erweiterung der Mess- und Prüftechnik von MMICs hinsichtlich der Lokalisierung von Design- oder Schaltungsfehlern während der Prototypen-Phase. Besondere Aufmerksamkeit wird auf die Vermeidung von Störeinflüssen (auf das Testobjekt) durch die Messung selbst sowie auf eine Berücksichtigung der Schaltungsstruktur zur bestmöglichen Ortsauflösung in Hinblick auf die Fehler-Lokalisierung gelegt. Ein Hindernis für zeitnahe Entwicklungszyklen im Bereich der Mikrowellen- und Hochfrequenz-Komponenten ist das Fehlen innovativer Hilfsmittel zur umfassenden Analyse neuer Schaltungs-Komponenten auf potenzielle Fehlfunktionen. Bisherige Messtechniken sind entweder kontaktgebunden (an zuvor festgelegte Messpunkte) und damit sowohl wenig flexibel als auch unzuverlässig, da die gesuchten Schaltungsfehler von dem (durch die Messkontaktierung) verursachten Fehlverhalten nicht immer eindeutig zu unterscheiden sind oder erlauben es nur eine Fehlfunktion festzustellen, ohne diese lokalisieren zu können. Die vorgestellte Erweiterung der Messmöglichkeiten bei MMICs erstreckt sich auf eine Ortsauflösung, die im µm-Bereich liegt, auf die Verminderung bzw. Kontrollierbarkeit des Störeinflusses der Messung auf das Testobjekt sowie auf den "Informationsgehalt" der Messdaten, die mittels inverser Feldtransformation einen Rückschluss auf Betrag, Phase und Richtung des Signalflusses zulassen. Zentrale Idee dieses Ansatzes ist die Kombination aus einem nahfeldoptischen Mikrokop (zur Berücksichtigung feiner Oberflächenstrukturen) und elektromagnetischer Nahfeldmesstechnik relativ niedriger Auflösung mit dem Ziel einer hochauflösenden Nahfeldmessung. Die feldtheoretische Verarbeitung der Messdaten zur Bestimmung und "Bildschärfung" der Signalflussverteilung ermöglicht in einem zweiten Schritt eine Lokalisierung von Störstellen. Beginnend mit den Grundlagen im Bereich der elektromagnetischen Feldtheorie soll in Kapitel 2 der Weg, zur Bestimmung einer Signalflussverteilung auf einer Schaltung aus den Feldstärkeverteilungen im Nahfeld dicht über dieser Schaltung unter Berücksichtigung der Materialeigenschaften, aufgezeigt werden. Die Kenngrößen von Nahfeldsonden werden behandelt, um später die Qualität der realisierten Nahfeldsonden quantifizieren und bewerten zu können. Im Anschluss an diese feldtheoretischen Grundlagen erfolgt eine grundlegende Einführung in die Schaltungstechnik im Bereich der Mikrowellen- und Mikrostreifenleitungs-Technik, um die Alternativen beim Entwurf und bei der Realisierung von Anpassungsverstärkern für die Feldsonden aufzuzeigen. Ein Einblick in die Regelungstechnik zur Beschreibung des Verfahrens zur Nahfeld-optischen Berücksichtigung der Oberfächenstruktur schließt dieses Kapitel ab. Die "erweiterte Messtechnik", die im Mittelpunkt dieser Arbeit steht, wird anschließend in Kapitel 3 konkret an Hand des realiserten Prototyps in ihrem Aufbau, ihren Komponenten und deren Funktionen im Zusammenspiel ausführlich behandelt. Die numerischen Methoden fokusieren sich in Kapitel 4 zum Einen auf die analytisch nicht lösbare Rücktransformation von beliebigen Funktionen aus dem Fourier-Bessel-Oberbereich und zum Anderen auf die inverse Feldtransformation zur Bestimmung einer äquivalenten Signalflussverteilung aus gemessenen (und damit verrauschten) Feldstärkeverteilungs-Messdaten unter Berücksichtigung der Substrat-Parameter. Die Berechnungs- und Realisierungsmöglichkeiten sowie die Ergebnisse der Modellierung und des Aufbaus der Feldsonden bzw. deren Anpassungsverstärker werden in Kapitel 5 beschrieben. Die Entwurf-Kriterien und die Dimensionierung der Mikrowellen-Schaltungen werden ebenso behandelt, wie die Verfahren und Messgrößen zur quantitativen Charakterisierung der Feldsonden mittels Kalibration. Zur Berücksichtigung der Oberflächenstruktur der zu charakterisierenden Schaltungen dienen Verfahren aus dem Bereich der Regelungstechnik und der Nahfeld-Optik. Die Beschreibung eines hier genutzten physikalischen Effektes aus der Nahfeld-Optik steht im Mittelpunkt der Betrachtung von Kapitel 6, wie auch die Konzeption und digitale Realisierung eines Fuzzy-Regelkreises zur Abtastung des Höhenprofils mit Hilfe eines digitalen Signalprozessors. Die Ergebnisse von Messungen und deren Bewertung sowie die Perspektiven der vorgestellten Messtechnik werden anhand ausgewählter Anwendungen in Kapitel 7 zusammengefasst. Hierbei steht die Vorstellung der erreichbaren Auflösung, Genauigkeit, Dynamik sowie des Störeinflusses auf die untersuchte Schaltung ebenso im Mittelpunkt, wie die Untersuchung einer aktiven integrierten Schaltung. Erstere erfolgt durch den Vergleich zwischen Messung und Berechnung -- basierend auf der Untersuchung einer einfachen passiven Schaltung. Kapitel 8 fasst die Erkenntnisse und Erfahrungen zusammen und schließt diese Arbeit mit einem Ausblick auf mögliche künftige Entwicklungen ab.