Rhetorische Stilmittel, werden seit jeher in Texten verwendet, um Bilder zu erzeugen, Leser zu fesseln und wichtige Punkte hervorzuheben. Unter diesen Stilmitteln ist die Vossianische Antonomasie besonders für den Einsatz von Eigennamen als rhetorische Elemente beliebt. Genauer definiert beinhaltet die Vossianische Antonomasie, dass einem Eigennamen eine bestimmte Menge von Eigenschaften oder Attributen zugeordnet wird, indem ein anderer Eigenname, der für die entsprechenden Eigenschaften allgemein bekannt ist, genannt wird. Modifizierende Phrasen, die typischerweise in Kombination mit dem letztgenannten Eigennamen auftreten, helfen, diese Attribute zu kontextualisieren. Trotz ihrer Allgegenwärtigkeit in modernen Medien ist die Forschung zu ihrer Identifizierung, Verwendung und Interpretation selten. Dies motiviert das Thema dieser Arbeit: die automatische Erkennung, Extraktion und Analyse der Vossianischen Antonomasie. Wir präsentieren mehrere Methoden zur automatisierten Erkennung des Phänomens und entwickeln einen annotierten Datensatz. Die Methoden basieren zumeist auf neuronalen Netzen. Zusätzlich stellen wir verschiedene Ansätze zur Extraktion jedes Teils des Stilmittels in einem Satz vor. Darüber hinaus führen wir sprachübergreifende Extraktionsmodelle ein und verfeinern Erkennungsmethoden für eine verbesserte Leistung bei bisher unbekannten syntaktischen Variationen des Phänomens, indem wir uns ausschließlich auf den Schlüsseleigennamen des Stilmittels konzentrieren. Außerdem befassen wir uns mit einer anderen, aber ergänzenden Aufgabe, nämlich der Extraktion des zu beschreibenden Eigennamens in einem ganzen Textabsatz. Für ein tieferes Verständnis der Vossianischen Antonomasie präsentieren wir eine explorative Analyse des entwickelten Datensatzes. Wir führen zwei interaktive Visualisierungen ein, die die einzelnen Teile des Phänomens und ihr Zusammenspiel hervorheben, um weitere Einblicke zu gewinnen. / Stylistic devices, also known as figures of speech or rhetorical devices, have always been used in text to create imagery, engage readers, and emphasize key points. Among these devices, Vossian Antonomasia, which is closely related to metaphor and metonymy, is particularly popular for employing named entities as rhetorical elements. Defined more precisely, Vossian Antonomasia involves attributing a particular set of properties or attributes to an entity by naming another named entity that is generally well-known for the respective properties. Modifying phrases, which typically appear in combination with the latter entity, help contextualize these attributes. Despite its ubiquity in modern media, the research on its identification, usage, and interpretation is rare. This motivates the topic of this thesis: The automated detection, extraction and analysis of Vossian Antonomasia. We present several methods for the automated detection of the phenomenon and create an annotated dataset. Mostly, the methods are based on neural networks. Additionally, we introduce several approaches for extracting each chunk of the device in a sentence by modeling the problem as a sequence tagging task. Moreover, we introduce cross-lingual extraction models and refine detection methods for an improved performance on unseen syntactic variations of the phenomenon by focusing solely on the key entity of the device. Furthermore, we tackle a distinct but complementary task, namely, the extraction of the entity being described in an entire text paragraph. For a deeper understanding of Vossian Antonomasia, we present an exploratory analysis of the developed dataset. We introduce two interactive visualizations that highlight the chunks of the phenomenon and their interplay to gain more insights.

Im Bereich von Exascale Computing und HPC sind Fehler nicht gelegentlich. Sondern treten sie regelmäßig während der Laufzeit von Anwendungen auf. Die Bewältigung dieser Herausforderungen ist wichtig, um die Zuverlässigkeit der Supercomputing-Anwendung zu verbessern. Checkpoint/Restart ist eine Technik, die in HPC verwendet wird, um die Ausfallsicherheit bei Ausfällen zu verbessern. Dabei wird der Status einer Anwendung regelmäßig auf der Festplatte gespeichert, sodass die Anwendung bei einem Ausfall vom letzten Checkpoint aus neu gestartet werden kann. Checkpointing kann jedoch zeitaufwändig sein insbesondere hinsichtlich I/O. Daher ist die Optimierung des C/R-Prozesses wichtig, um seine Auswirkungen auf die Anwendungsleistung zu reduzieren und die Job-Resilienz zu verbessern. Der erste Teil dieser Arbeit erforscht und entwickelt innovative Techniken im Bereich des C/R-Managements im HPC-Kontext. Dazu gehört die Entwicklung eines neuartigen C/R-Ansatzes, die Entwicklung eines Modells für mehrstufiges C/R, und die Optimierung der gemeinsamen Nutzung von Burst-Puffer für C/R in Supercomputern. C/R-Prozeduren erzeugen umfangreiche I/O-Operationen. Daher ist eine Optimierung der I/O-Prozesse zwingend erforderlich. Um den C/R-Prozess zu optimieren, ist es auch wichtig, das I/O-Verhalten einer Anwendung zu verstehen, einschließlich der Menge an Daten, die geschrieben werden müssen, wie oft Checkpoints genommen werden sollten und wo die Checkpoints gespeichert werden sollen. Daher untersuchen und stellen wir im zweiten Teil Innovationen von Ansätzen für I/O-Modellierung und -Management. Dazu gehört die Entwicklung eines Plugins für GCC, das das optimale Speichergerät für die I/O von Anwendungen basierend auf ihrem durch Pragma-Vorstellungen definierten Verhalten auswählt, und die Entwicklung eines Modells zur Schätzung der I/O-Kosten Anwendungen unter Linux unter Berücksichtigung von Seitenverwaltung und Prozessdrosselung. / In the context of exascale computing and HPC, failures are not occasional but rather inherent, occurring during the runtime of applications. Addressing these challenges is essential to enhance the resilience and reliability of supercomputing operations. Checkpoint/Restart (C/R) is a technique used in HPC to improve job resilience in the case of failures. This involves periodically saving the state of an application to disk, so that if the application fails, it can be restarted from the last checkpoint. However, checkpointing can be time-consuming and significantly impact application performance, particularly regarding its I/O operations. Therefore, optimizing C/R is crucial for reducing its impact on application performance and improving job resilience. The first part of this work develops novel techniques in C/R management within the context of HPC. This includes developing a novel C/R approach by combining XOR and partner C/R mechanisms, developing a model for multilevel C/R in large computational resources, and optimising the shared usage of burst buffers for C/R in supercomputers. C/R procedures generate substantial I/O operations, emerging as a bottleneck for HPC applications. Hence, the need for optimization in I/O processes becomes imperative to overcome this bottleneck. To optimize the C/R process, it is also important to understand the I/O behavior of an application, including how much data needs to be written, how frequently checkpoints should be taken, and where to store the checkpoints to minimize I/O bottlenecks. Hence, in the second part, we investigate and introduce innovative techniques and approaches for I/O modeling and management. This includes developing a plugin for GNU C Compiler (GCC) that selects the optimal storage device for the I/O of applications based on their behavior that is defined by Pragma notions, and developing a model to estimate I/O cost of applications under Linux considering page management and process throttling.

Systeme der Computer Vision spielen in der Automatisierung vieler Prozesse eine wichtige Rolle. Die wichtigste Aufgabe solcher Systeme ist die Automatisierung des visuellen Erkennungsprozesses und die Extraktion der relevanten Information aus Bildern oder Bildsequenzen. Eine wichtige Komponente dieser Systeme ist die Bildsegmentierung, denn sie bestimmt zu einem großen Teil die Qualitaet des Gesamtsystems. Fuer die Segmentierung von Bildern und Bildsequenzen werden neue Algorithmen vorgeschlagen. Das Konzept der Multiresolution wird als eigenstaendig dargestellt, es existiert unabhaengig von der Wavelet-Transformation. Die Wavelet-Transformation wird zur Verarbeitung von Bildern und Bildsequenzen zu einer 2D- bzw. 3D-Wavelet- Transformation erweitert. Fuer die Segmentierung von Bildern wird der Algorithmus Resolution Mosaic Expectation Maximization (RM-EM) vorgeschlagen. Das Ergebnis der Vorverarbeitung sind unterschiedlich aufgeloesten Teilbilder, das Aufloesungsmosaik. Durch dieses Mosaik lassen sich raeumliche Korrelationen zwischen den Pixeln ausnutzen. Die Verwendung unterschiedlicher Aufloesungen beschleunigt die Verarbeitung und verbessert die Ergebnisse. Fuer die Extraktion von bewegten Objekten aus Bildsequenzen werden neue Algorithmen vorgeschlagen, die auf der 3D-Wavelet-Transformation und auf der Analyse mit 3D-Wavelet-Packets beruhen. Die neuen Algorithmen haben den Vorteil, dass sie sowohl die raeumlichen als auch die zeitlichen Bewegungsinformationen beruecksichtigen. Wegen der geringen Berechnungskomplexitaet der Wavelet-Transformation ist fuer den ersten Segmentierungsschritt Hardware auf der Basis von FPGA entworfen worden. Aktuelle Anwendungen werden genutzt, um die Algorithmen zu evaluieren: die Segmentierung von Magnetresonanzbildern des menschlichen Gehirns und die Detektion von bewegten Objekten in Bildsequenzen von Verkehrsszenen. Die neuen Algorithmen sind robust und fuehren zu besseren Segmentierungsergebnissen. / More and more computer vision systems take part in the automation of various applications. The main task of such systems is to automate the process of visual recognition and to extract relevant information from the images or image sequences acquired or produced by such applications. One essential and critical component in almost every computer vision system is image segmentation. The quality of the segmentation determines to a great extent the quality of the final results of the vision system. New algorithms for image and video segmentation based on the multiresolution analysis and the wavelet transform are proposed. The concept of multiresolution is explained as existing independently of the wavelet transform. The wavelet transform is extended to two and three dimensions to allow image and video processing. For still image segmentation the Resolution Mosaic Expectation Maximization (RM-EM) algorithm is proposed. The resolution mosaic enables the algorithm to employ the spatial correlation between the pixels. The level of the local resolution depends on the information content of the individual parts of the image. The use of various resolutions speeds up the processing and improves the results. New algorithms based on the 3D wavelet transform and the 3D wavelet packet analysis are proposed for extracting moving objects from image sequences. The new algorithms have the advantage of considering the relevant spatial as well as temporal information of the movement. Because of the low computational complexity of the wavelet transform an FPGA hardware for the primary segmentation step was designed. Actual applications are used to investigate and evaluate all algorithms: the segmentation of magnetic resonance images of the human brain and the detection of moving objects in image sequences of traffic scenes. The new algorithms show robustness against noise and changing ambient conditions and gave better segmentation results.

Die Informations- und Kommunikationstechnologien haben die Arbeitswelt grundlegend verändert. Durch den Einsatz komplexer, hochautomatisierter Systeme werden an die kognitive Leistungsfähigkeit und Belastbarkeit von Arbeitnehmern hohe Anforderungen gestellt. Über die Ermittlung der psychischen Beanspruchung des Menschen an Arbeitsplätzen mit hohen kognitiven Anforderungen wird es möglich, eine Über- oder Unterbeanspruchung zu vermeiden. Gegenstand der Dissertation ist deshalb die Entwicklung, Implementierung und der Test eines neuen Systems zur kontinuierlichen Bewertung psychischer Beanspruchung an informationsintensiven Arbeitsplätzen auf Basis des Elektroenzephalogramms. Im theoretischen Teil der Arbeit werden die Konzepte zur Definition der psychischen Beanspruchung und Modelle zur Beschreibung der menschlichen Informationsverarbeitung zusammengestellt. Die Auswertung einer Reihe von Experimenten ist die Basis für die Konzeption und den Test des neuen Systems zur Indexierung der psychischen Beanspruchung. Die Aufgabenbatterie, die Stichprobenbeschreibung, der Versuchsaufbau und -ablauf sind Bestandteil des experimentellen Teils der Arbeit. Während der Aufgabenlösung wird von den Probanden das Elektroenzephalogramm mit 25 Kanälen abgeleitet. Es folgt eine Artefakteliminierung, für die ein neues automatisch und in Echtzeit arbeitendes Verfahren entwickelt wurde. Die Klassifikation und damit die Indexierung von Segmenten des Elektroenzephalogramms in die Klassen niedriger, mittlerer oder hoher Beanspruchung erfolgt auf Basis einer ebenfalls neu entwickelten Methode, deren Grundlage Dual Frequency Head Maps sind. Damit ist ein vollständiges System entstanden, das die einzelnen Verfahrensschritte integriert und die Aufgabenstellung der Arbeit erfüllt: Es kann an informationsintensiven Arbeitsplätzen eingesetzt werden, um kontinuierlich die Bewertung der psychischen Beanspruchung auf Basis des Elektroenzephalogramms vorzunehmen. / Advanced information and communication technology has fundamentally changed the working environment. Complex and highly automated systems impose high demands on employees with respect to cognitive capacity and the ability to cope with workload. The registration of mental workload of employees on-site at workplaces with high cognitive demands enables preventing over- or underload. The subject of this dissertation is therefore the development, implementation and testing of a novel system for continuous assessment of mental workload at information intensive workplaces on the basis of the electroencephalogram. In the theoretical section of the thesis concepts for defining mental workload are given; furthermore, models for describing human information processing are introduced and the relevant terminology such as strain, workload, and performance is clarified. Evaluation of an array of experiments with cognitive tasks forms the basis for the conceptual design and testing of the novel system for indexing mental workload. Descriptions of these tasks, the sample, the experimental set-up and procedure are included in the experimental section. The electroencephalogram with 25 channels was recorded from the subjects while performing the tasks. Subsequently, an artifact elimination was carried out, for which a new, automated, and real-time capable procedure has been developed. Segments from the electroencephalogram are classified and thusly indexed into classes of low, medium, and high workload on the basis of a likewise newly developed method, whose central element are Dual Frequency Head Maps. Hence, a complete system emerges that integrates the single processing steps and satisfies the scope of this thesis: It can be applied on-site at information intensive workplaces for continuous assessment of mental workload on the basis of the electroencephalogram.

Diese Dissertation soll einen Beitrag zur Weiterentwicklung der luftgestützten Verkehrslageerfassung leisten. Als Plattform dafür dient ein flugzeuggetragenes Kamerasystem, welches mit einem Inertialsystem gekoppelt ist. Vorgestellt werden hauptsächlich bildverarbeitende Algorithmen, welche an die Bildaufnahme anschließend bis hin zur Ermittlung der verkehrstechnischen Kenngrößen zum Einsatz kommen. Nach kurzer Skizzierung der verwendeten Hardware wird die Kalibrierung der Kameraeinbauwinkel durch Testflüge erläutert und auf ihre Genauigkeit hin untersucht. Es wird gezeigt, dass die Orientierungsdaten nicht die vom Hersteller angegebene Genauigkeit erreichen, was jedoch für die Verkehrslageerfassung nur von geringer Bedeutung ist. Anschließend an die Bildaufbereitung, welche die Orthobildgenerierung sowie die Eingrenzung der verkehrsaktiven Flächen beinhaltet, wird zur Ermittlung der Fahrzeugdichte ein zweistufiger Fahrzeugerkennungsalgorithmus entwickelt, welcher zunächst auf Kantenfilterbasis möglichst schnell Hypothesen erstellt. Diese werden in einer zweiten Phase durch eine Support Vector Machine überprüft, wobei ein Großteil der Fehlhypothesen verworfen wird. Die Erkennung erreicht bei guten Voraussetzungen Vollständigkeiten bis zu 90 Prozent bei sehr geringem Anteil von Fehldetektionen. Anschließend wird ein auf Singulärwertzerlegung basierender Tracking-Algorithmus verwendet, um Fahrzeughypothesen in benachbarten Bildern zu assoziieren und die mittleren Geschwindigkeiten zu ermitteln. Die erhaltenen Geschwindigkeiten unterscheiden sich um weniger als zehn km/h von den manuell erhobenen. Abschließend wird eine alternative Orientierungsmethode vorgestellt, welche auf Basis von GPS-Positionen und Bildinformationen automatisch die Fluglage ermittelt. Dies geschieht durch die Extraktion und das Matching von Straßensegmenten sowie zusätzliche Passpunktverfolgung. Die Ergebnisse weisen Genauigkeiten von etwa 0,1 bis 0,2 Grad auf. / This dissertation should make a contribution to the further development of airborne traffic detection. The used hardware is an airborne camera system combined with an inertial measurement unit for orientation determination. Mainly computer vision algorithms are presented, which are applied afterwards the image acquisition up to the determination of the most important traffic data. After a short presentation of the used hardware the calibration of the camera''s alignment angles during test flights is explained and its accuracy is analyzed. It is shown that the orientation data doesn''t reach the specified accuracy, which is fortunately less important for traffic detection. After the image preparation, which contains the ortho image generation as well as the clipping of traffic areas, a two-stage vehicle detection algorithm is implemented, which at first rapidly creates hypotheses based on edge filters. In the second stage those hypotheses are verified by a Support Vector Machine which rejects most of the False Posititves. At good conditions the detection reaches completeness rates of up to 90 percent with a low contingent of FP detections. Subsequently a tracking algorithm based on singular value decomposition is applied to associate vehicle hypotheses in adjacent images and determine the average speed. The achieved velocities differ less than ten kph from the manually obtained data. Concluding an orientation method is presented, that automatically determines the airplane''s attitude based on GPS and image information. This is realized by extraction and matching of street segments and additional tracking of ground control points. The results have accuracies of around 0.1 to 0.2 degrees.

Durch ein zunehmendes Verkehrsaufkommen wächst die Notwendigkeit den Verkehr in irgendeiner Form "intelligent" zu organisieren. In diesem Kontext sind die sogenannten Intelligent Transportation Systems (ITS) in den Fokus der Forschung gerückt. Diese Systeme zielen in der Regel auf die dynamische Optimierung der Routenwahlen von Verkehrsteilnehmern ab und sollen dadurch die Effizienz des Verkehrs verbessern. Grundsätzlich kann die Vorstellung einer optimalen Routenwahl in eine von zwei Kategorien eingeteilt werden: das Nash Gleichgewicht und die systemoptimale Routenwahl. Während Nash Gleichgewichte vergleichsweise einfach erzielt werden können-beispielsweise dadurch, dass jeder Fahrer seine Route egoistisch optimiert-ist das Erreichen des Systemoptimums ungleich schwerer. Dieses setzt nämlich voraus, dass alle Fahrer miteinander kooperieren und gemeinsam eine Lösung finden, von der die Gesamtheit als solche profitiert. In dieser Dissertation diskutieren wir das Design eines dezentralisierten ITS, welches in der Lage ist, eine systemoptimale Routenzuweisung im Straßennetzwerk zu approximieren, so dass die Fahrzeuge den price of anarchy nicht mehr in voller Höhe bezahlen müssen. Der besondere Fokus liegt hierbei auf der Anwendbarkeit des Ansatzes in realistischen Umgebungen, in denen eine Vielzahl von Schwierigkeiten zu erwarten ist. Dies beinhaltet beispielsweise eine unvollständige oder inkorrekte Sicht auf die aktuelle Verkehrssituation, das Fehlen von Wissen über Fahrzeuge, die erst in der Zukunft das Straßennetz betreten sowie ein nicht perfekter oder ressourcenlimitierter Kommunikationskanal. / The increasing amount of road traffic necessitates approaches that somehow "intelligently" organize traffic. In this context, the study of intelligent transportation systems (ITS) has been performed for some time. The goals of such systems include, e.g., is the dynamic optimization of route choices in a road network and hence the improvement of traffic conditions. There are two main methodologies how an optimization can be performed: the optimization towards a Nash equilibrium or towards a system optimum. While Nash equilibria can be easily reached, e.g., when every driver selfishly optimizes his own route, reaching the system optimum is a challenging task and requires all drivers to cooperate in an altruistic manner in favor of the system from a global perspective. In this work, we discuss the design of a decentralized ITS that is capable of approximating system optimal route choices in the network avoiding that the drivers have to pay the full price of anarchy. The focus, in this context, lies on the applicability to real life situations where a number of difficulties has to be expected, e.g., an incomplete or incorrect view on the current traffic situation, the lack of future knowledge and an imperfect or limited communication channel. Facing these challenging questions, we develop solutions to a number of research questions, that arise from the aforementioned difficulties. Before we can do so, we focus on the fundamental concepts of traffic optimization with an emphasis both on the theoretical concepts as well as their applicability in real world environments.

Diese Arbeit befasst sich mit Worst-Case-Algorithmen für das Erfüllbarkeitsproblem boolescher Ausdrücke in konjunktiver Normalform. Im Wesentlichen betrachten wir Laufzeitschranken drei verschiedener Algorithmen, zwei für 3-SAT und einen für Unique-k-SAT. Wir entwickeln einen randomisierten Algorithmus, der eine Lösung eines erfüllbaren 3-KNF-Ausdrucks G mit n Variablen mit einer erwarteten Laufzeit von O(1.32793^n) findet. Der Algorithmus basiert auf der Analyse sogenannter Strings, welche Sequenzen von Klauseln der Länge drei sind. Dabei dürfen einerseits nicht aufeinanderfolgende Klauseln keine Variablen und andererseits aufeinanderfolgende Klauseln ein oder zwei Variablen gemeinsam haben. Gibt es wenige Strings, so treffen wir wahrscheinlich bereits während der String-Suche auf eine Lösung von G. 1999 entwarf Schöning einen Algorithmus mit einer Schranke von O(1.3334^n) für 3-SAT. Viele Strings erlauben es, die Laufzeit dieses Algorithmusses zu verbessern. Weiterhin werden wir den PPSZ-Algorithmus für Unique-k-SAT derandomisieren. Der 1998 von Paturi, Pudlak, Saks und Zane vorgestellte PPSZ-Algorithmus hat die besondere Eigenschaft, dass die Lösung eines eindeutig erfüllbaren 3-KNF-Ausdrucks in höchstens O(1.3071^n) erwarteter Laufzeit gefunden wird. Die derandomisierte Variante des Algorithmusses für Unique-k-SAT hat im Wesentlichen die gleiche Laufzeitschranke. Wir erreichen damit die momentan beste deterministische Worst-Case-Schranke für Unique-k-SAT. Zur Derandomisierung wenden wir die "Methode der kleinen Zufallsräume" an. Schließlich verbessern wir die Schranke für den Algorithmus von Iwama und Tamaki. 2003 kombinierten Iwama und Tamaki den PPSZ-Algorithmus mit Schönigs Algorithmus und konnten eine Schranke von O(1.3238^n) bewiesen. Um seinen Beitrag zum kombinierten Algorithmus zu steigern, justieren wir die Schranke des PPSZ-Algorithmusses. Damit erhalten wir die momentan beste randomisierte Worst-Case-Schranke für das 3-SAT-Problem von O(1.32216^n). / This work deals with worst-case algorithms for the satisfiability problem regarding boolean formulas in conjunctive normal form. The main part of this work consists of the analysis of the running time of three different algorithms, two for 3-SAT and one for Unique-k-SAT. We establish a randomized algorithm that finds a satisfying assignment for a satisfiable 3-CNF formula G on n variables in O(1.32793^n) expected running time. The algorithm is based on the analysis of so-called strings, which are sequences of clauses of size three, whereby non-succeeding clauses do not share a variable, and succeeding clauses share one or two variables. If there are not many strings, it is likely that we already encounter a solution of G while searching for strings. In 1999, Schöning proved a bound of O(1.3334^n) for 3-SAT. If there are many strings, we use them to improve the running time of Schöning''s algorithm. Furthermore, we derandomize the PPSZ algorithm for Unique-k-SAT. The PPSZ algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the feature that the solution of a uniquely satisfiable 3-CNF formula can be found in expected running time at most O(1.3071^n). In general, we will obtain a derandomized version of the algorithm for Unique-k-SAT that has essentially the same bound as the randomized version. This settles the currently best known deterministic worst-case bound for the Unique-k-SAT problem. We apply the `Method of Small Sample Spaces'' in order to derandomize the algorithm. Finally, we improve the bound for the algorithm of Iwama and Tamaki to get the currently best known randomized worst-case bound for the 3-SAT problem of O(1.32216^n). In 2003 Iwama and Tamaki combined Schöning''s and the PPSZ algorithm to yield an O(1.3238^n) bound. We tweak the bound for the PPSZ algorithm to get a slightly better contribution to the combined algorithm.

In dieser Arbeit geht es um die schrittweise Verfeinerung verteilter Algorithmen. Dabei wird ein einfacher Algorithmus, der einige gewünschte Eigenschaften hat, Schritt für Schritt zu einem komplexen Algorithmus verfeinert, der konkrete Implementationsanforderungen erfüllt, so daß in jedem Schritt die gewünschten Eigenschaften erhalten bleiben. Wir stellen einen neuen eigenschaftserhaltenden Verfeinerungsbegriff vor, der auf der kausalen Ordnung der Aktionen eines Algorithmus basiert. Diesen Begriff definieren wir als Transitionsverfeinerung für elementare Petrinetze und diskutieren Beweiskriterien. Danach definieren und diskutieren wir die simultane Verfeinerung mehrerer Transitionen. Zur Modellierung komplexer verteilter Algorithmen sind elementare Petrinetze oft nicht adäquat. Wir benutzen deshalb algebraische Petrinetze. Wir definieren Transitionsverfeinerung für algebraische Petrinetze und stellen einen Zusammenhang zur simultanen Verfeinerung von Transitionen in elementaren Petrinetzen her. Transitionsverfeinerung ist besonders für Verfeinerungsschritte geeignet, in denen synchrone Kommunikation zwischen Agenten durch asynchronen Nachrichtenaustausch ersetzt wird. Wir zeigen dies am Beispiel eines komplexen verteilten Algorithmus, zur Berechnung des minimalen spannenden Baumes in einem gewichteten Graphen. Wir zeigen die Korrektheit dieses Algorithmus in mehreren Schritten, von denen einige Schritte Transitionsverfeinerungen sind. In anderen Schritten sind klassische Verfeinerungsbegriffe ausreichend. Wir übertragen deshalb auch einen klassischen Verfeinerungsbegriff in unser formales Modell. / The topic of this PhD thesis is the stepwise refinement of distributed algorithms. Stepwise refinement starts with a simple algorithm with certain desired properties. This algorithm is refined step by step such that the desired properties are preserved in each refinement step. The result is a complex distributed algorithm which satisfies concrete implementation requirements and which still has the desired properties. We propose a new property preserving notion of refinement which is based on the causal ordering of actions of an algorithm. We call this notion transition refinement and we define it first for elementary Petri nets. Furthermore, we discuss proof criteria. Then, we define and discuss the simultaneous refinement of several transitions. For modelling complex distributed algorithms, we use algebraic Petri nets instead of elementary Petri nets. We define transition refinement for algebraic Petri nets, and we show its relationship to simultaneous transition refinement in elementary Petri nets. Transition refinement is particularly suitable for refinement steps in which synchronous communication between agents is replaced by asynchronous message passing. We show this by means of a complex distributed algorithm for determining the minimal spanning tree of a weighted graph. We prove the correctness of this algorithm in several steps. Some of these steps are transition refinements. For other steps, well-known notions of refinement are sufficient. Therefore, we also carry over a well-known notion of refinement into our formal model.

In den letzten Jahren kommen immer mehr nicht perspektivische Kamerasysteme beim maschinellen Sehen zur Anwendung, die vor allem ein deutlich erweitertes Blickfeld bieten. Das klassische perspektivische Abbildungsmodell lässt sich hier häufig nicht mehr erfolgreich anwenden. In dieser Arbeit wird ein generisches Abbildungsmodell vorgestellt, welches übliche Kamerasysteme akkurat modellieren kann. Solche Kamerasysteme schließen insbesondere klassische perspektivische Systeme, aber auch Fischaugen- und Spiegellinsen-Kamerasysteme ein. Die Nutzung eines einheitlichen Abbildungsmodells ermöglicht schließlich eine einfache Verwendung und Kalibrierung von heterogenen Stereokamerasystemen, also einer Kombination von unterschiedlichen Kameratypen, die vorteilhafte Eigenschaften gegenüber klassischen Stereosystemen bieten. Nicht zuletzt trägt die in dieser Arbeit vorgestellte einheitliche Modellierung und Kalibrierung von Mono- und Stereokamerasystemen dazu bei, Fehler durch falschen Umgang oder falsche Wahl von Methoden der Modellierung oder Kalibrierung zu vermeiden und den Kamerakalibrierprozess insgesamt zu vereinfachen. In dieser Arbeit wurden verschiedene Ansätze der Modellierung untersucht und evaluiert. Es wurde eine generische Modellierung vorgeschlagen, die die untersuchten spezifischen Abbildungsmodelle vollständig ersetzen kann. Für die Kalibrierung nicht linearer Abbildungsmodelle wurde eine einheitliche Methode zur Startwertbestimmung vorgeschlagen und evaluiert. Die Genauigkeit der Kalibrierung mittels einheitlicher Methoden wurde anhand diverser realer Kamerasysteme untersucht und bewertet. Es konnte gezeigt werden, dass die dabei auftretenden Fehler deutlich im Subpixelbereich liegen. Durch Erweiterung des klassischen Konzepts der Epipolargeometrie um die generische Abbildungsmodellierung konnten schließlich heterogene Stereokamerasysteme kalibriert und genaue Stereomodelle abgeleitet werden. / The application of perspective camera systems in photogrammetry and computer vision is state of the art. In recent years non-perspective and especially omnidirectional camera systems have increasingly been used in close-range photogrammetry tasks. In general, the perspective camera model, i.e. pinhole model, cannot be applied when using non-perspective camera systems. However, several camera models for different omnidirectional camera systems are proposed in literature. Using different types of cameras in a heterogeneous camera system may lead to an advantageous combination. The advantages of different camera systems, e.g. field of view and resolution, result in a new enhanced camera system. If these different kinds of cameras can be modeled, using a unified camera model, the total calibration process can be simplified. Sometimes it is not possible to give the specific camera model in advance. In these cases a generic approach is helpful too. Furthermore, a simple stereo reconstruction becomes possible when using a fisheye and a perspective camera for example. In this work camera models for perspective, wide-angle and omnidirectional camera systems were evaluated. A generic camera model were introduced that fully substitutes specific camera models. The crucial initialization of the model''s parameters is conducted using a new generic method that is independent of the particular camera system. The accuracy of this generic camera calibration approach is validated by the calibration of a dozen of real camera systems up to subpixel accuracy. Finally, it has been shown that a unified method of modeling, parameter approximation and calibration of interior and exterior orientation can be applied to a generic stereo system to derive precise 3D object data.

Für einen Algorithmus zum Lösen eines Graphenproblems wird üblicherweise angenommen, dieser sei mit wahlfreiem Zugriff (random access) auf den Eingabegraphen G ausgestattet, als auch mit einem Arbeitsspeicher, der G vollständig aufzunehmen vermag. Diese Annahmen erweisen sich als fragwürdig, wenn Graphen betrachtet werden, deren Größe jene konventioneller Arbeitsspeicher übersteigt. Solche Graphen können nur auf externen Speichern wie Festplatten oder Magnetbändern vorrätig gehalten werden, auf denen wahlfreier Zugriff sehr zeitaufwändig ist. Um riesige Graphen zu bearbeiten, die auf externen Speichern liegen, hat Muthukrishnan 2003 das Modell eines Semi-Streaming Algorithmus vorgeschlagen. Dieses Modell beschränkt die Größe des Arbeitsspeichers und verbietet den wahlfreien Zugriff auf den Eingabegraphen G. Im Gegenteil wird angenommen, die Eingabe sei ein Datenstrom bestehend aus Kanten von G in beliebiger Reihenfolge. In der vorliegenden Dissertation entwickeln wir Algorithmen im Semi-Streaming Modell für verschiedene Graphenprobleme. Für das Testen des Zusammenhangs und der Bipartität eines Graphen, als auch für die Berechnung eines minimal spannenden Baumes stellen wir Algorithmen vor, die asymptotisch optimale Laufzeiten erreichen. Es ist bekannt, dass kein Semi-Streaming Algorithmus existieren kann, der ein größtes gewichtetes Matching in einem Graphen findet. Für dieses Problem geben wir den besten bekannten Approximationsalgorithmus an. Schließlich zeigen wir, dass sowohl ein minimaler als auch ein maximaler Schnitt in einem Graphen nicht von einem Semi-Streaming Algorithmus berechnet werden kann. Für beide Probleme stellen wir randomisierte Approximationsalgorithmen im Semi-Streaming Modell vor. / An algorithm solving a graph problem is usually expected to have fast random access to the input graph G and a working memory that is able to store G completely. These powerful assumptions are put in question by massive graphs that exceed common working memories and that can only be stored on disks or even tapes. Here, random access is very time-consuming. To tackle massive graphs stored on external memories, Muthukrishnan proposed the semi-streaming model in 2003. It permits a working memory of restricted size and forbids random access to the input graph. In contrast, the input is assumed to be a stream of edges in arbitrary order. In this thesis we develop algorithms in the semi-streaming model approaching different graph problems. For the problems of testing graph connectivity and bipartiteness and for the computation of a minimum spanning tree, we show how to obtain running times that are asymptotically optimal. For the problem of finding a maximum weighted matching, which is known to be intractable in the semi-streaming model, we present the best known approximation algorithm. Finally, we show the minimum and the maximum cut problem in a graph both to be intractable in the semi-streaming model and give semi-streaming algorithms that approximate respective solutions in a randomized fashion.