• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 141
  • 48
  • Tagged with
  • 189
  • 189
  • 141
  • 111
  • 111
  • 71
  • 49
  • 49
  • 47
  • 26
  • 20
  • 19
  • 18
  • 18
  • 17
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
31

Multiresolution image segmentation

Salem, Mohammed Abdel-Megeed Mohammed 27 November 2008 (has links)
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.
32

Kontinuierliche Bewertung psychischer Beanspruchung an informationsintensiven Arbeitsplätzen auf Basis des Elektroenzephalogramms

Radüntz, Thea 21 January 2016 (has links)
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.
33

Entwicklung und Validierung eines Gesamtsystems zur Verkehrserfassung basierend auf Luftbildsequenzen

Kozempel, Karsten 22 March 2012 (has links)
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.
34

A distributed evolutionary approach to cooperative vehicular traffic optimization

Cagara, Daniel 10 January 2017 (has links)
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.
35

Algorithms for the satisfiability problem

Rolf, Daniel 22 November 2006 (has links)
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.
36

Halbordnungsbasierte Verfeinerung zur Verifikation verteilter Algorithmen

Peuker, Sibylle 03 July 2001 (has links)
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.
37

Ein generisches Abbildungsmodell für Stereokamerasysteme

Luber, Andreas 19 January 2015 (has links)
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.
38

Algorithms for streaming graphs

Zelke, Mariano 06 May 2009 (has links)
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.
39

Extraction and integration of Web query interfaces

Kabisch, Thomas 20 October 2011 (has links)
Diese Arbeit fokussiert auf die Integration von Web Anfrageschnittstellen (Web Formularen). Wir identifizieren mehrere Schritte für den Integrationsprozess: Im ersten Schritt werden unbekannte Anfrageschnittstellen auf ihre Anwendungsdomäne hin analysiert. Im zweiten Schritt werden die Anfrageschnittstellen in ein maschinenlesbares Format transformiert (Extraktion). Im dritten Schritt werden Paare semantisch gleicher Elemente zwischen den verschiedenen zu integrierenden Anfragesschnittstellen identifiziert (Matching). Diese Schritte bilden die Grundlage, um Systeme, die eine integrierte Sicht auf die verschiedenen Datenquellen bieten, aufsetzen zu können. Diese Arbeit beschreibt neuartige Lösungen für alle drei der genannten Schritte. Der erste zentrale Beitrag ist ein Exktraktionsalgorithmus, der eine kleine Zahl von Designregeln dazu benutzt, um Schemabäume abzuleiten. Gegenüber früheren Lösungen, welche in der Regel lediglich eine flache Schemarepräsentation anbieten, ist der Schemabaum semantisch reichhaltiger, da er zusätzlich zu den Elementen auch Strukturinformationen abbildet. Der Extraktionsalgorithmus erreicht eine verbesserte Qualität der Element-Extraktion verglichen mit Vergängermethoden. Der zweite Beitrag der Arbeit ist die Entwicklung einer neuen Matching-Methode. Hierbei ermöglicht die Repräsentation der Schnittstellen als Schemabäume eine Verbesserung vorheriger Methoden, indem auch strukturelle Aspekte in den Matching-Algorithmus einfließen. Zusätzlich wird eine globale Optimierung durchgeführt, welche auf der Theorie der bipartiten Graphen aufbaut. Als dritten Beitrag entwickelt die Arbeit einen Algorithms für eine Klassifikation von Schnittstellen nach Anwendungsdomänen auf Basis der Schemabäume und den abgeleiteten Matches. Zusätzlich wird das System VisQI vorgestellt, welches die entwickelten Algorithmen implementiert und eine komfortable graphische Oberfläche für die Unterstützung des Integrationsprozesses bietet. / This thesis focuses on the integration of Web query interfaces. We model the integration process in several steps: First, unknown interfaces have to be classified with respect to their application domain (classification); only then a domain-wise treatment is possible. Second, interfaces must be transformed into a machine readable format (extraction) to allow their automated analysis. Third, as a pre-requisite to integration across databases, pairs of semantically similar elements among multiple interfaces need to be identified (matching). Only if all these tasks have been solved, systems that provide an integrated view to several data sources can be set up. This thesis presents new algorithms for each of these steps. We developed a novel extraction algorithm that exploits a small set of commonsense design rules to derive a hierarchical schema for query interfaces. In contrast to prior solutions that use mainly flat schema representations, the hierarchical schema better represents the structure of the interfaces, leading to better accuracy of the integration step. Next, we describe a multi-step matching method for query interfaces which builds on the hierarchical schema representation. It uses methods from the theory of bipartite graphs to globally optimize the matching result. As a third contribution, we present a new method for the domain classification problem of unknown interfaces that, for the first time, combines lexical and structural properties of schemas. All our new methods have been evaluated on real-life datasets and perform superior to previous works in their respective fields. Additionally, we present the system VisQI that implements all introduced algorithmic steps and provides a comfortable graphical user interface to support the integration process.
40

Description of languages based on object-oriented meta-modelling

Scheidgen, Markus 19 May 2009 (has links)
In dieser Dissertation, schaue ich auf objekt-orientierte Metamodellierung und wie sie verwendet werden kann, um Computersprachen zu beschreiben. Dabei, fokussiere ich mich nicht nur auf die Beschreibung von Sprachen, sondern auch auf die Verwendung von Sprachbeschreibungen zur automatischen Erzeugung von Sprachwerkzeugen aus Sprachbeschreibungen. Ich nutze die Idee von Metasprachen und Metawerkzeugen. Metasprachen werden verwendet um bestimmte Sprachaspekte, wie Notationen und Semantiken, zu beschreiben, und Metawerkzeuge werden verwendet um Sprachwerkzeuge wie Editoren und Interpreter aus entsprechenden Beschreibungen zu erzeugen. Diese Kombination von Beschreibung und automatischer Entwicklung von Werkzeugen ist als Domänenspezifische Modellierung (DSM) bekannt. Ich verwende DSM basierend auf objekt-orientierter Metamodellierung zur Beschreibung der wichtigen Aspekte ausführbarer Computersprachen. Ich untersuche existierende Metasprachen und Metawerkzeuge für die Beschreibung von Sprachvorkommen, ihrer konkreten Repräsentation und Semantik. Weiter, entwickle ich eine neue Plattform zur Beschreibung von Sprachen basierend auf dem CMOF-Modell der OMG MOF 2.x Empfehlungen. Ich entwickle eine Metasprache und Metawerkzeug für textuelle Notationen. Schlussendlich, entwickle ich eine graphische Metasprache und Metawerkzeug zur Beschreibung von operationaler Semantik von Computersprachen. Um die Anwendbarkeit der vorgestellten Techniken zu prüfen, nehme ich SDL, die Specification and Description Language, als einen Archetypen für textuell notierte Sprachen mit ausführbaren Instanzen. Für diesen Archetyp zeige ich, dass die präsentierten Metasprachen und Metawerkzeuge es erlauben solche Computersprachen zu beschreiben und automatisch Werkzeuge für diese Sprachen zu erzeugen. / In this thesis, I look into object-oriented meta-modelling and how it can be used to describe computer languages. Thereby, I do not only focus on describing languages, but also on utilising the language descriptions to automatically create language tools from language descriptions. I use the notion of meta-languages and meta-tools. Meta-languages are used to describe certain language aspects, such as notation or semantics, and meta-tools are used to create language tools, such as editors or interpreters, from corresponding descriptions. This combination of describing and automated development of tools is known as domain specific modelling (DSM). I use DSM based on object-oriented meta-modelling to describe all important aspects of executable computer languages. I look into existing meta-languages and meta-tools for describing language utterances, their concrete representation, and semantics. Furthermore, I develop a new platform to define languages based on the CMOF-model of the OMG MOF 2.x recommendations. I develop a meta-language and meta-tool for textual language notations. Finally, I develop a new graphical meta-language and meta-tool for describing the operational semantics of computer languages. To prove the applicability of the presented techniques, I take SDL, the Specification and Description Language, as an archetype for textually notated languages with executable instances. For this archetype, I show that the presented meta-languages and meta-tools allow to describe such computer languages and allow to automatically create tools for those languages.

Page generated in 0.4443 seconds