Eldorado Collection:
http://hdl.handle.net/2003/70
2024-03-29T11:19:35ZEfficient, collision-free multi-robot navigation in an environment abstraction framework
http://hdl.handle.net/2003/42310
Title: Efficient, collision-free multi-robot navigation in an environment abstraction framework
Authors: Böckenkamp, Adrian
Abstract: Industrial automation deploys a continuously increasing amount of mobile robots in favor of classical linear conveyor systems for material flow handling in manufacturing and intralogistics. This increases flexibility by handling a larger variety of goods, improves scalability by adapting the fleet size to varying system loads, and enhances fault tolerance by avoiding single points of failure. However, it also raises the need for efficient, collision-free multi-robot navigation. This core problem is first precisely modeled in a form that differs from existing approaches specifically in terms of application relevance and structured algorithmic treatability. Collision-free trajectories for the mobile robots between given start and goal locations are sought so that the number of goals reached per time is as high as possible. Based on this, a decoupled solution called the Collaborative Local Planning Framework (CLPF), is designed and implemented, which, in contrast to existing solutions, aims at avoiding deadlocks with the greatest possible concurrency. Moreover, this solution includes the handling of dynamic inputs consisting of both moving and non-moving robots. For testing, performance analysis, and optimization, due to the complexity of multi-robot systems, the use of simulation is common. However, this also creates a gap between real and simulated robots. These issues can be reduced by using several different simulators---albeit with the disadvantage of further increasing complexity. For this purpose, the Robot Experimentation Framework (REF) is introduced to write robotic experiments with a unified interface that can be run on multiple simulators and also on real hardware. It facilitates the creation of experiments for performance assessment, (parameter) optimization and runtime analysis. The framework has proven its effectiveness throughout this thesis. Lastly, experimental proof of the viability of the solution is provided based on a case study of a complete (simulated) assembly system of decentralized autonomous agents for the production of highly individualized automobiles. This integrates all developed concepts into a holistic application of industrial automation. Detailed evaluations of more than 800 000 solved scenarios with more than 5 700 000 processed goals have experimentally proven the robustness and reliability of the developed concepts. Robots have never crashed into each other in any of the conducted experiments, empirically proving the claimed safety guarantees. A fault-tolerance analysis of the decentralized assembly system has experimentally proven its resilience to failures at workstations and, thus, specifically revealed an advantage over linear conveyor systems.2023-01-01T00:00:00ZConstructing L∞ Voronoi diagrams in 2D and 3D
http://hdl.handle.net/2003/42291
Title: Constructing L∞ Voronoi diagrams in 2D and 3D
Authors: Bukenberger, D. R.; Buchin, K.; Botsch, M.
Abstract: Voronoi diagrams and their computation are well known in the Euclidean L2 space. They are easy to sample and render in generalized Lp spaces but nontrivial to construct geometrically. Especially the limit of this norm with p → ∞ lends itself to many quad- and hex-meshing related applications as the level-set in this space is a hypercube. Many application scenarios circumvent the actual computation of L∞ diagrams altogether as known concepts for these diagrams are limited to 2D, uniformly weighted and axis-aligned sites. Our novel algorithm allows for the construction of generalized L∞ Voronoi diagrams. Although parts of the developed concept theoretically extend to higher dimensions it is herein presented and evaluated for the 2D and 3D case. It further supports individually oriented sites and allows for generating weighted diagrams with anisotropic weight vectors for individual sites. The algorithm is designed around individual sites, and initializes their cells with a simple meshed representation of a site's level-set. Hyperplanes between adjacent cells cut the initialization geometry into convex polyhedra. Non-cell geometry is filtered out based on the L∞ Voronoi criterion, leaving only the non-convex cell geometry. Eventually we conclude with discussions on the algorithms complexity, numerical precision and analyze the applicability of our generalized L∞ diagrams for the construction of Centroidal Voronoi Tessellations (CVT) using Lloyd's algorithm.2022-10-06T00:00:00ZBahnplanung mittels impliziter Methoden für spanende und beschichtende Fertigungsverfahren
http://hdl.handle.net/2003/41343
Title: Bahnplanung mittels impliziter Methoden für spanende und beschichtende Fertigungsverfahren
Authors: Gaspar, Marcel
Abstract: Das Thema der Dissertation ist die Entwicklung einer auf Level-Sets basierenden Bahnplanungsmethodik. Zu diesem Zweck werden unterschiedliche Ansätze zur impliziten Definition, Repräsentation und Manipulation von für die Planung von Werkzeugbahnen relevanten Flächen und Kurven vorgestellt. Die entwickelten Methoden dienen zur Planung von Werkzeugbahnen in zwei unterschiedlichen Anwendungsszenarien, der spanenden Fertigung dentaler Werkstücke wie Zahnkronen, Brücken oder Inlays mittels einer 5-achsigen Tischfräsmaschine, und zur thermischen Beschichtung von Oberflächen mittels einer am Roboterarm geführten Spritzpistole. Die Verwendung impliziter Methoden führt einerseits zu bedeutsamen Vorteilen gegenüber expliziten Methoden, andererseits jedoch auch zu neuen Herausforderungen, welche in der Dissertation thematisiert werden. Hervorgehoben sei hier der Ansatz zur impliziten Repräsentation von Kammlinien als Projektion des Medialachsenrandes auf eine explizite Oberfläche, sowie die damit verbundene Identifikation von für die Bahnplanung kritischen Bereichen auf der Zieloberfläche. Ebenso werden die den Werkzeugbahnen zugrunde liegenden Kurven auf Oberflächen und im Raum implizit definiert, sowie Ansätze zur Überführung explizit bzw. implizit definierter Kontaktpunktkurven auf Oberflächen in explizit bzw. implizit definierte Werkzeugpositionskurven im Raum vorgestellt. Die Überführung von Kontaktpunktkurven auf Oberflächen in Werkzeugpositionskurven im Raum wird weitergehend vertieft, indem die Bestimmung einer Positionskurve als Lösung eines Optimierungsproblems aufgefasst wird, welche zwischen einer aus prozesstechnischer, geometrischer und dynamischer Perspektive günstigen Positionierung des Werkzeugs abzuwägen vermag. Abschließend wird eine neuartige und auf ausschließlich impliziten Repräsentationen beruhende Methodik zur Simulation des Materialabtrags bei der spanenden Fertigung vorgestellt.2022-01-01T00:00:00ZAgent-based simulation of pedestrian dynamics for exposure time estimation in epidemic risk assessment
http://hdl.handle.net/2003/41231
Title: Agent-based simulation of pedestrian dynamics for exposure time estimation in epidemic risk assessment
Authors: Harweg, Thomas; Bachmann, Daniel; Weichert, Frank
Abstract: Purpose
With the coronavirus disease 2019 (COVID-19) pandemic spreading across the world, protective measures for containing the virus are essential, especially as long as no vaccine or effective treatment is available. One important measure is the so-called physical distancing or social distancing.
Methods
In this paper, we propose an agent-based numerical simulation of pedestrian dynamics in order to assess the behavior of pedestrians in public places in the context of contact transmission of infectious diseases like COVID-19, and to gather insights about exposure times and the overall effectiveness of distancing measures.
Results
To abide by the minimum distance of 1.5 m stipulated by the German government at an infection rate of 2%, our simulation results suggest that a density of one person per 16m2 or below is sufficient.
Conclusions
The results of this study give insight into how physical distancing as a protective measure can be carried out more efficiently to help reduce the spread of COVID-19.2021-04-01T00:00:00ZLayered character models for fast physics-based simulation
http://hdl.handle.net/2003/41075
Title: Layered character models for fast physics-based simulation
Authors: Komaritzan, Martin
Abstract: This thesis presents two different layered character models that are ready to be used
in physics-based simulations, in particular they enable convincing character animations
in real-time. We start by introducing a two-layered model consisting of rigid bones and
an elastic soft tissue layer that is efficiently constructed from a surface mesh of the
character and its underlying skeleton. Building on this model, we introduce Fast Projective
Skinning, a novel approach for physics-based character skinning. While maintaining
real-time performance it overcomes the well-known artifacts of commonly used geometric
skinning approaches. It further enables dynamic effects and resolves local and global self-collisions.
In particular, our method neither requires skinning weights, which are often
expensive to compute or tedious to hand-tune, nor a complex volumetric tessellation,
which fails for many real-world input meshes due to self-intersections. By developing a
custom-tailored GPU implementation and a high-quality upsampling method, our ap-
proach is the first skinning method capable of detecting and handling arbitrary global
collisions in real-time.
In the second part of the thesis, we extend the idea of a simplified two-layered volumetric
model by developing an anatomically plausible three-layered representation of
human virtual characters. Starting with an anatomy model of the male and female body,
we show how to generate a layered body template for both sexes. It is composed of three
surfaces for bones, muscles and skin enclosing the volumetric skeleton, muscles and fat
tissues. Utilizing the simple structure of these templates, we show how to fit them to
the surface scan of a person in just a few seconds. Our approach includes a data-driven
method for estimating the amount of muscle mass and fat mass from a surface scan,
which provides more accurate fits to the variety of human body shapes compared to
previous approaches. Additionally, we demonstrate how to efficiently embed fine-scale
anatomical details, such as high resolution skeleton and muscle models, into the layered
fit of a person. Our second model can be used for physical simulation, statistical analysis
and anatomical visualization in computer animation or in medical applications, which
we demonstrate on several examples.2022-01-01T00:00:00ZOn the power of message passing for learning on graph-structured data
http://hdl.handle.net/2003/41059
Title: On the power of message passing for learning on graph-structured data
Authors: Fey, Matthias
Abstract: This thesis proposes novel approaches for machine learning on irregularly structured input data such as graphs, point clouds and manifolds. Specifically, we are breaking up with the regularity restriction of conventional deep learning techniques, and propose solutions in designing, implementing and scaling up deep end-to-end representation learning on graph-structured data, known as Graph Neural Networks (GNNs).
GNNs capture local graph structure and feature information by following a neural message passing scheme, in which node representations are recursively updated in a trainable and purely local fashion. In this thesis, we demonstrate the generality of message passing through a unified framework suitable for a wide range of operators and learning tasks. Specifically, we analyze the limitations and inherent weaknesses of GNNs and propose efficient solutions to overcome them, both theoretically and in practice, e.g., by conditioning messages via continuous B-spline kernels, by utilizing hierarchical message passing, or by leveraging positional encodings. In addition, we ensure that our proposed methods scale naturally to large input domains. In particular, we propose novel methods to fully eliminate the exponentially increasing dependency of nodes over layers inherent to message passing GNNs. Lastly, we introduce PyTorch Geometric, a deep learning library for implementing and working with graph-based neural network building blocks, built upon PyTorch.2022-01-01T00:00:00ZThe Diamond Laplace for polygonal and polyhedral meshes
http://hdl.handle.net/2003/40774
Title: The Diamond Laplace for polygonal and polyhedral meshes
Authors: Bunge, Astrid; Botsch, Mario; Alexa, Marc
Abstract: We introduce a construction for discrete gradient operators that can be directly applied to arbitrary polygonal surface as well as polyhedral volume meshes. The main idea is to associate the gradient of functions defined at vertices of the mesh with diamonds: the region spanned by a dual edge together with its corresponding primal element — an edge for surface meshes and a face for volumetric meshes. We call the operator resulting from taking the divergence of the gradient Diamond Laplacian. Additional vertices used for the construction are represented as affine combinations of the original vertices, so that the Laplacian operator maps from values at vertices to values at vertices, as is common in geometry processing applications. The construction is local, exactly the same for all types of meshes, and results in a symmetric negative definite operator with linear precision. We show that the accuracy of the Diamond Laplacian is similar or better compared to other discretizations. The greater versatility and generally good behavior come at the expense of an increase in the number of non-zero coefficients that depends on the degree of the mesh elements.2021-08-23T00:00:00ZDifferentiable algorithms with data-driven parameterization in 3D vision
http://hdl.handle.net/2003/40738
Title: Differentiable algorithms with data-driven parameterization in 3D vision
Authors: Lenssen, Jan Eric
Abstract: This thesis is concerned with designing and analyzing efficient differentiable data flow for representations in the field of 3D vision and applying it to different 3D vision tasks. To this end, the topic is looked upon from the perspective of differentiable algorithms, a more general variant of Deep Learning, utilizing the recently emerged tools in the field of differentiable programming. Contributions are made in the subfields of Graph Neural Networks (GNNs), differentiable matrix decompositions and implicit neural functions, which serve as important building blocks for differentiable algorithms in 3D vision. The contributions include SplineCNN, a neural network consisting of operators for continuous convolution on irregularly structured data, Local Spatial Graph Transformers, a GNN to infer local surface orientations on point clouds, and a parallel GPU solver for Eigendecomposition on a large number of symmetric matrices. For all methods, efficient forward and backward GPU implementations are provided.
Consequently, two differentiable algorithms are introduced, composed of building blocks from these concept areas. The first algorithm, Differentiable Iterative Surface Normal Estimation, is an iterative algorithm for surface normal estimation on unstructured point clouds. The second algorithm, Group Equivariant Capsule Networks, is a version of capsule networks grounded in group theory for unsupervised pose estimation and, in general, for inferring disentangled representations from 2D and 3D data.
The thesis concludes that a favorable trade-off in the metrics of efficiency, quality and interpretability can be found by combining prior geometric knowledge about algorithms and data types with the representational power of Deep Learning.2022-01-01T00:00:00ZWeb-based scientific exploration and analysis of 3D scanned cuneiform datasets for collaborative research
http://hdl.handle.net/2003/38487
Title: Web-based scientific exploration and analysis of 3D scanned cuneiform datasets for collaborative research
Authors: Fisseler, Denis; Müller, Gerfrid G. W.; Weichert, Frank
Abstract: The three-dimensional cuneiform script is one of the oldest known writing systems and a central object of research in Ancient Near Eastern Studies and Hittitology. An important step towards the understanding of the cuneiform script is the provision of opportunities and tools for joint analysis. This paper presents an approach that contributes to this challenge: a collaborative compatible web-based scientific exploration and analysis of 3D scanned cuneiform fragments. The WebGL -based concept incorporates methods for compressed web-based content delivery of large 3D datasets and high quality visualization. To maximize accessibility and to promote acceptance of 3D techniques in the field of Hittitology, the introduced concept is integrated into the Hethitologie-Portal Mainz, an established leading online research resource in the field of Hittitology, which until now exclusively included 2D content. The paper shows that increasing the availability of 3D scanned archaeological data through a web-based interface can provide significant scientific value while at the same time finding a trade-off between copyright induced restrictions and scientific usability.2017-12-12T00:00:00ZThe PAMONO-sensor enables quantification of individual microvesicles and estimation of nanoparticle size distribution
http://hdl.handle.net/2003/38485
Title: The PAMONO-sensor enables quantification of individual microvesicles and estimation of nanoparticle size distribution
Authors: Shpacovitch, Viktoria; Sidorenko, Irina; Lenssen, Jan Eric; Temchura, Vladimir; Weichert, Frank; Müller, Heinrich; Überla, Klaus; Zybin, Alexander; Schramm, Alexander; Hergenröder, Roland
Abstract: In our recent work, the plasmon assisted microscopy of nano-objects (PAMONO) was
successfully employed for the detection and quantification of individual viruses and virus-like
particles in aquatic samples (Shpacovitch et al., 2015). Further, we adapted the PAMONO-sensor for
the specific detection of individual microvesicles (MVs), which have gained growing interest as
potential biomarkers of various physiological and pathological processes. Using MVs derived from
human neuroblastoma cell line cells, we demonstrated the ability of the PAMONO-sensor to
specifically detect individual MVs. Moreover, we proved the trait of the PAMONO-sensor to perform
a swift comparison of relative MV concentrations in two or more samples without a prior sensor
calibration. The detection software developed by the authors utilizes novel machine learning
techniques for the processing of the sensor image data. Using this software, we demonstrated that
nanoparticle size information is evident in the sensor signals and can be extracted from them. These
experiments were performed with polystyrene nanoparticles of different sizes. We also suggested a
theoretical model explaining the nature of observed signals. Taken together, our findings can serve
as a basis for the development of diagnostic tools built on the principles of the PAMONO-sensor.2017-09-27T00:00:00ZMulti-objective optimisation based planning of power-line grid expansions
http://hdl.handle.net/2003/38400
Title: Multi-objective optimisation based planning of power-line grid expansions
Authors: Bachmann, Daniel; Bökler, Fritz; Kopec, Jakob; Popp, Kira; Schwarze, Björn; Weichert, Frank
Abstract: German nuclear power phase out in 2022 leads to significant reconstruction of the energy transmission system. Thus, efficient identification of practical transmission routes with minimum impact on ecological and economical interests is of growing importance. Due to the sensitivity of Germany’s public to grid expansion (especially in case of overhead lines), the participation and planning process needs to provide a high degree of openness and accountability. Therefore, a new methodological approach for the computer-assisted finding of optimal power-line routes considering planning, ecological and economic decision criteria is presented. The approach is implemented in a tool-chain for the determination of transmission line routes (and sets of transmission line route alternatives) based on multi-criteria optimisation. Additionally, a decision support system, based on common Geographic Information Systems (GIS), consisting of interactive visualisation and exploration of the solution space is proposed.2018-06-29T00:00:00ZReview of three-dimensional human-computer interaction with focus on the leap motion controller
http://hdl.handle.net/2003/38399
Title: Review of three-dimensional human-computer interaction with focus on the leap motion controller
Authors: Bachmann, Daniel; Weichert, Frank; Rinkenauer, Gerhard
Abstract: Modern hardware and software development has led to an evolution of user interfaces from command-line to natural user interfaces for virtual immersive environments. Gestures imitating real-world interaction tasks increasingly replace classical two-dimensional interfaces based on Windows/Icons/Menus/Pointers (WIMP) or touch metaphors. Thus, the purpose of this paper is to survey the state-of-the-art Human-Computer Interaction (HCI) techniques with a focus on the special field of three-dimensional interaction. This includes an overview of currently available interaction devices, their applications of usage and underlying methods for gesture design and recognition. Focus is on interfaces based on the Leap Motion Controller (LMC) and corresponding methods of gesture design and recognition. Further, a review of evaluation methods for the proposed natural user interfaces is given.2018-07-07T00:00:00ZExtraction, localization, and fusion of collective vehicle data
http://hdl.handle.net/2003/38149
Title: Extraction, localization, and fusion of collective vehicle data
Authors: Skibinski, Sebastian
Abstract: Maps representing the detailed features of the road network are becoming more and more important for self-driving vehicles and next generation driver assistance systems. The mapping of the road network, by specially equipped vehicles of the well-known map providers, leads to usually quarterly map updates, which might result in problems encountered by self-driving vehicles in the case that the road information is outdated. Furthermore, the provided maps could lack details, such as precise landmark geometries or data known to exhibit a fast temporal decay rate, which might be, nevertheless, highly relevant, such as friction data.
As an alternative, extensive amounts of information about the road network can be acquired by common vehicles, which are, nowadays, commonly equipped with manifold types of sensors. Subsequently, this type of gathered data is referred to as CVD (Collective Vehicle Data). The process of map creation requires, at first, the extraction of relevant sensor data at the vehicle-side and its accurate localization. Unfortunately, sensor data is typically affected by measurement uncertainties and errors. A minimization of both can be achieved by means of an appropriate sensor data fusion.
This work aims for a holistic view of a three-staged pipeline, consisting of the extraction, localization, and fusion of CVD, intended for the derivation of large-scale, high-precision, real-time maps from collective sensor measurements acquired by a common vehicle fleet. The vehicle fleet is assumed to be solely equipped with commercially viable sensors. Concerning the processing at the back-end-side, general approaches that are applicable in a straightforward manner to new types of sensor data are strictly favored. For this purpose, a novel distinction of CVD into areal, point-shaped landmark, and complex landmark data is introduced. This way, the similarities between different types of environmental attributes are exploited in an overall highly beneficial manner; and the proposed algorithms can be adapted to new types of data that appertain to these categories by appropriately adjusting their parameterizations. To achieve the above mentioned goals, both novel approaches, where the research lacks established ways, and relevant extensions/adaptations of existing ones are suggested to fulfill the very specific, automotive requirements.
All in all, the thesis condenses a broad and manifold research concerning the deduction of large-scale and high-precision map data grounded on preprocessed sensor measurements that have been acquired by common vehicles, the so-called CVD. The focus is put on the utilization of commercially viable sensors. Additionally, besides its broad perspective, this thesis also emphasizes highly relevant details, such as the efficient, adaptive temporal weighting of sensor data at the back-end-side and the template-based hierarchical data storage. A complete pipeline, consisting of the extraction, localization, and fusion of CVD, is presented and evaluated, as each component is known to have a direct impact on the quality of the deduced map data. Approaches to the fusion of areal and point-shaped/complex landmark data are either invented from scratch or significantly enhanced according to the state of the art, always bearing in mind the highly specific needs of the automotive context.2019-01-01T00:00:00ZContributions to computer-aided analysis of cuneiform tablet fragments
http://hdl.handle.net/2003/37929
Title: Contributions to computer-aided analysis of cuneiform tablet fragments
Authors: Fisseler, Denis Bernd
Abstract: This thesis presents methods for computer-aided three-dimensional analysis of digitized
cuneiform tablets, an ancient type of writing documents. Since cuneiform script is predominantly
conserved in the form of fractured clay tablet fragments, identifying matching fragments
is a central task of manuscript reconstruction. This goal can benefit from the increasing
3D digitization of cuneiform fragments, which offers access to highly accurate cuneiform
representations.
The main contribution of the thesis is a novel model-based method for the extraction of
individual cuneiform wedges and associated wedge geometries from 3D scans, which can serve
as a base for a statistical analysis of script features. This new automated approach enables
access to large amounts of accurate quantitative cuneiform script features, which were not
accessible by previously available 2D methods and can be employed for script similarity-based
identification of candidates for fragment joining. A central aspect and challenging task is the
robustness of the presented extraction method against scanning issues and mesh errors. This
is achieved by employing a watershed-based wedge area extraction operating on a surface
distance field with a subsequent constructive multi-stage model fitting. The extracted wedge
models are refined by a wedge type classification followed by an effective wedge validation to
handle false detections on fracture faces and damaged surfaces. An evaluation with respect to
extraction rates, robustness, and performance shows the suitability of the developed methods
that goes beyond an application purely for cuneiform fragment joining.
To address some compromises made during the wedge extraction regarding the representation
of complex features, a fast supplementary approach for extracting skeletal surface features
is presented. These features provide an alternative readable cuneiform representation and
are created using a thinning approach on an approximated distance field. The quality of the
resulting skeletons is optimized by employing a complex junction resolution, branch pruning
and branch simplification methods, where both pruning and simplification can be used to
adjust the resulting representation to different use cases. Aside from manual feature analysis,
possible application scenarios also include providing a representation that can be handled by
GraphCNNs for retrieval related tasks on cuneiform structures.
The cuneiform segmentation methods are complemented by a set of visualization concepts for a
cuneiform segmentation framework. This includes a hierarchical concept for data handling and
persistent storage of the generated segmentation data. Beyond, methods for fast rendering of
large meshes, visualization methods to achieve good depth perception, detail enhancement, and
semi-realistic surface shading are integrated. In order to not only address application scenarios
like fragment joining and collation related tasks, the framework provides a sophisticated,
highly interactive, and flexible segmentation data visualization that additionally offers fast
geometry selection methods. A good accessibility of the generated data is guaranteed though
an XML-based file format for storing segmentation data and through providing flexible data
export methods. Although the framework is primarily intended for real-time segmentation,
most segmentation methods can also be scheduled to process large numbers of fragments
without user interaction.
All presented methods are evaluated with respect to performance aspects and their suitability
for a set of philological use cases. The developed methods can be used flexibly in the scope of
many aspects of the investigated application cases. This does not only apply to the automated
feature extraction, but also to manual analysis aspects, which were discovered only by the
new availability of the methods. The usability of the framework is underlined by the fact that
it is actively being used by philologists from the Hethitologie-Portal Mainz, an established
online resource in Hittitology.2019-01-01T00:00:00ZOptimierung thermischer Verhältnisse bei der Bahnplanung für das thermische Spritzen mit Industrierobotern
http://hdl.handle.net/2003/36053
Title: Optimierung thermischer Verhältnisse bei der Bahnplanung für das thermische Spritzen mit Industrierobotern
Authors: Hegels, Daniel
Abstract: Diese Arbeit befasst sich mit der Erzeugung und Optimierung von neuartigen Bahnen für Industrieroboter beim thermischen Spritzen auf komplexen Freiformoberflächen unter besonderer Berücksichtigung der thermischen Verhältnisse in dem Werkstück. Thermisches Spritzen ist ein Produktionsprozess, bei dem eine Werkstückoberfläche mit geschmolzenem Material beschichtet wird, so dass die Oberfläche die gewünschten Oberflächeneigenschaften aufweist. Ein Alleinstellungsmerkmal des präsentierten Systems ist der modulare Aufbau, der vor allem eine in diesem Bereich unübliche Trennung zwischen der Initialbahnplanung und der Bahnoptimierung vorsieht. Die Basis des Gesamtsystems bilden verschiedene Simulationskomponenten, wie die Beschichtungssimulation, die thermische Simulation und die Robotersimulation.
Die Initialbahnplanung erzeugt flächenüberdeckende Bahnen auf einem Werkstück unter Berücksichtigung verschiedener Qualitätsmerkmale. Dazu werden die Bahnen über flexible Bahnstrukturen repräsentiert, darunter neuartige Strukturen, wie die Rand-zu-Rand Bahnen und die Punkt-zu-Punkt Bahnen. Die Qualität der Bahnen wird über verschiedene Zielfunktionen bewertet, die neben der Schichtqualität vor allem die thermischen Varianzen berücksichtigen, welche bisher nur selten in Betracht gezogen wurden, obwohl sie großen Einfluss auf die endgültige Schichtqualität haben. Weitere praxisrelevante Zielkriterien, wie die Roboterachsbeschleunigungen und der Overspray, welcher das Material beschreibt, das nicht auf der funktionalen Fläche abgelagert wird, werden ebenfalls beachtet. Das Problem der Initialbahnplanung wird als mehrkriterielles Optimierungsproblem formuliert und mit Hilfe eines Evolutionären Algorithmus optimiert. Verschiedene Varianten für die Operatoren des Evolutionären Algorithmus werden verwendet und gegeneinander evaluiert. Hieraus wird die Kombination von Operatoren bestimmt, mit der der Algorithmus mit hoher Konvergenzgeschwindigkeit strukturell gute Bahnen für den anschließenden Bahnoptimierungsprozess erzeugt.
Die Bahnoptimierung wird für die Verbesserung vorhandener Bahnen bezüglich der Beschichtungsfehler und der Ausführbarkeit mit Robotern verwendet. Ein neuartiges Konzept zur kombinierten Anwendung des in der Arbeit entwickelten, analytischen Auftragsmodells mit einer externen Blackbox Simulation wird verwendet, um die Bahnen mit Hilfe des Verfahrens der nichtlinearen konjugierten Gradienten zu optimieren. Die Fehler werden hierbei über die externe Simulation und die Gradienten über das analytische Auftragsmodell bestimmt. Die Verwendung der Bahnoptimierung beschränkt sich nicht nur auf die Optimierung der Bahnen, die von der Initialbahnplanung erstellt worden sind, sondern kann ebenfalls genutzt werden, um bereits erstellte Bahnen an andere Spritzprozesse oder ähnliche Werkstückgeometrien anzupassen. Hierdurch lässt sich der erhebliche Aufwand zur Generierung neuer Bahnen stark reduzieren.
Zum Abschluss der Arbeit wird ein Verfahren vorgestellt, das die bisher unberücksichtigte Roboterdynamik in das System miteinbezieht. Dazu wird eine Dynamikkorrektur präsentiert, die die Bahnen mit Hilfe einer Roboterherstellersoftware in den dynamisch zulässigen Bereich projiziert. Diese Projektion wird in einer weiteren Optimierungsschleife alternierend mit der Bahnoptimierung genutzt, um eine dynamisch zulässige Bahn zu erzeugen, die sehr gute Ergebnisse bezüglich der Qualitätsmaße liefert.2017-01-01T00:00:00ZExploration of cyber-physical systems for GPGPU computer vision-based detection of biological viruses
http://hdl.handle.net/2003/35929
Title: Exploration of cyber-physical systems for GPGPU computer vision-based detection of biological viruses
Authors: Libuschewski, Pascal
Abstract: This work presents a method for a computer vision-based detection of biological viruses in PAMONO sensor images and, related to this, methods to explore cyber-physical systems such as those consisting of the PAMONO sensor, the detection software, and processing hardware. The focus is especially on an exploration of Graphics Processing Units (GPU) hardware for “General-Purpose computing on Graphics Processing Units” (GPGPU) software and the targeted systems are high performance servers, desktop systems, mobile systems, and hand-held systems.
The first problem that is addressed and solved in this work is to automatically detect biological viruses in PAMONO sensor images. PAMONO is short for “Plasmon Assisted Microscopy Of Nano-sized Objects”. The images from the PAMONO sensor are very challenging to process. The signal magnitude and spatial extension from attaching viruses is small, and it is not visible to the human eye on raw sensor images. Compared to the signal, the noise magnitude in the images is large, resulting in a small Signal-to-Noise Ratio (SNR).
With the VirusDetectionCL method for a computer vision-based detection of viruses, presented in this work, an automatic detection and counting of individual viruses in PAMONO sensor images has been made possible. A data set of 4000 images can be evaluated in less than three minutes, whereas a manual evaluation by an expert can take up to two days. As the most important result, sensor signals with a median SNR of two can be handled. This enables the detection of particles down to 100 nm.
The VirusDetectionCL method has been realized as a GPGPU software. The PAMONO sensor, the detection software, and the processing hardware form a so called cyber-physical system. For different PAMONO scenarios, e.g., using the PAMONO sensor in laboratories, hospitals, airports, and in mobile scenarios, one or more cyber-physical systems need to be explored. Depending on the particular use case, the demands toward the cyber-physical system differ.
This leads to the second problem for which a solution is presented in this work: how can existing software with several degrees of freedom be automatically mapped to a selection of hardware architectures with several hardware configurations to fulfill the demands to the system? Answering this question is a difficult task. Especially, when several possibly conflicting objectives, e.g., quality of the results, energy consumption, and execution time have to be optimized.
An extensive exploration of different software and hardware configurations is expensive and time-consuming. Sometimes it is not even possible, e.g., if the desired architecture is not yet available on the market or the design space is too big to be explored manually in reasonable time. A Pareto optimal selection of software parameters, hardware architectures, and hardware configurations has to be found.
To achieve this, three parameter and design space exploration methods have been developed. These are named SOG-PSE, SOG-DSE, and MOGEA-DSE. MOGEA-DSE is the most advanced method of these three. It enables a multi-objective, energy-aware, measurement-based or simulation-based exploration of cyber-physical systems. This can be done in a hardware/software codesign manner. In addition, offloading of tasks to a server and approximate computing can be taken into account. With the simulation-based exploration, systems that do not exist can be explored. This is useful if a system should be equipped, e.g., with the next generation of GPUs. Such an exploration can reveal bottlenecks of the existing software before new GPUs are bought.
With MOGEA-DSE the overall goal—to develop a method to automatically explore suitable cyber-physical systems for different PAMONO scenarios—could be achieved. As a result, a rapid, reliable detection and counting of viruses in PAMONO sensor data using high-performance, desktop, laptop, down to hand-held systems has been made possible.
The fact that this could be achieved even for a small, hand-held device is the most important result of MOGEA-DSE. With the automatic parameter and design space exploration 84% energy could be saved on the hand-held device compared to a baseline measurement. At the same time, a speedup of four and an F-1 quality score of 0.995 could be obtained. The speedup enables live processing of the sensor data on the embedded system with a very high detection quality.
With this result, viruses can be detected and counted on a mobile, hand-held device in less than three minutes and with real-time visualization of results. This opens up completely new possibilities for biological virus detection that were not possible before.2017-01-01T00:00:00ZApproximation anatomischer Strukturen und biomedizinischer Prozesse zur rechnergestützten Untersuchung der Hämodynamik in Aneurysmen
http://hdl.handle.net/2003/35324
Title: Approximation anatomischer Strukturen und biomedizinischer Prozesse zur rechnergestützten Untersuchung der Hämodynamik in Aneurysmen
Authors: Walczak, Lars
Abstract: Arterien des Menschen können Aneurysmen aufweisen, deren Ruptur zu lebensbedrohenden inneren Blutungen wie Schlaganfällen führen kann. Ein Therapieansatz ist das Einsetzen von sogenannten Stents. Eine Ruptur oder der Einfluss eines Stents kann mit dem momentanen Stand der Technik nicht exakt vorhergesagt werden. Für eine optimale Behandlung von Patienten wäre dies allerdings eine wichtige Zusatzinformation für den behandelnden Arzt. Zur Bestimmung dieser Zusatzinformation sollen zukünftig Simulationen der Hämodynamik in pathologischen Arterien eingesetzt werden. In dieser Arbeit werden Strömungsgeschwindigkeiten in Arterien ohne beziehungsweise mit Einbringung von Einbauten wie Stents berechnet und die entstehenden Wandscherspannungen im Hinblick auf eine Rupturvorhersage untersucht. Weiterhin wird der Massentransfer zwischen Arterie und Aneurysma charakterisiert und eine Analyse des Thrombosierungsverhaltens unter Strömungseinfluss vorgenommen. Bei letztgenanntem Thema werden insbesondere der Verschluss von Aneurysmen durch Thromben, die Ortseindämmung der Thrombenbildung und das Verhalten von wandanhaftenden Thromben auch in Bezug auf eine Ablösung untersucht. Um hierfür geeignete Simulationen durchführen zu können, wird eine Analyse der biomedizinischen Grundlagen durchgeführt. Für die Untersuchung der komplexen Dynamik sind aus methodischer Sicht zwei grundlegende Aspekte zu bearbeiten: die geometrische und die funktionelle Approximation. Die funktionelle Approximation biomedizinischer Prozesse umfasst die Untersuchung der Blutströmung, des Transports von passiven Stoffen und der Thrombosierung. Hierfür werden entsprechende Modelle identifiziert, in entsprechende Lattice-Boltzmann-Verfahren umgewandelt, simuliert und untersucht. Durch die Erarbeitung geeigneter Konzepte für eine Umsetzung der hier beschriebenen Simulationen auf einzelnen oder mehreren, miteinander kommunizierenden Grafikprozessoren kann eine effiziente Simulation der gekoppelten Multi-Physik-Probleme mit Lattice-Boltzmann-Verfahren erreicht werden. Insgesamt stellt diese Vorgehensweise ein Novum dar und unterstreicht die Praktikabilität der Methode. Die geometrische Approximation anatomischer Strukturen wird in dieser Arbeit mit Level-Set-Darstellungen gelöst. Mit ihnen können vielfältige Problemstellungen im Umfeld der Simulation bearbeitet werden, dies umfasst beispielsweise die Konstruktion einer Simulationsdomäne aus unterschiedlichen Tomographiedaten und die Einbringung von Einbauten wie Stents in das Untersuchungsgebiet. Durch die Kombination mit der Lattice-Boltzmann-Methode können Vorteile gegenüber dem Stand der Technik erreicht werden, etwa bei der effizienten Berechnung der Wandscherspannungen. Eine Validierung der Strömungs- und Transportsimulationen wird mit hochaufgelöster Magnetresonanztomographie vorgenommen. Dazu wird ein Modell des Aufnahmevorgangs unter Einfluss von Radiofrequenz-Magnetfeldern und Gradienten erstellt und der Magnetisierungstransport sowie die Relaxation simuliert. Die bestimmten Abweichungen zwischen Simulation und Messung sind insgesamt gering. Für die Messexperimente werden erstmals 3D-Druckverfahren für die Konstruktion von physischen Modellen eingesetzt und deren Güte untersucht. Durch die Ergebnisse dieser Arbeit steht eine effiziente und umfassende Verarbeitungspipeline für Blutströmungs-, Transport- und Thrombosierungsprozesse für weitere Untersuchungen bereit. Sie kann ebenfalls leicht um neue Modelle erweitert werden. Die Simulation der Magnetresonanztomographie für Flussbildgebung ermöglicht ebenfalls zukünftige Anwendungen im Bereich der Sequenzentwicklung.2016-01-01T00:00:00ZA parameter-optimizing model-based approach to the analysis of low-SNR image sequences for biological virus detection
http://hdl.handle.net/2003/35229
Title: A parameter-optimizing model-based approach to the analysis of low-SNR image sequences for biological virus detection
Authors: Siedhoff, Dominic
Abstract: This thesis presents the multi-objective parameter optimization of a novel image analysis process. The focus of application is automatic detection of nano-objects, for example biological viruses, in real-time. Nano-objects are detected by analyzing time series of images recorded with the PAMONO biosensor, after parameters have been optimized on synthetic data created by a signal model for PAMONO. PAMONO, which is short for Plasmon-Assisted Microscopy of Nano-Sized Objects, is a biosensor yielding indirect proofs for objects on the nanometer-scale by measuring the Surface Plasmon Resonance (SPR) effects they cause on the micrometer scale. It is an optical microscopy technique enabling the detection of biological viruses and other nano-objects within a portable device. The PAMONO biosensor produces time series of 2-D images on the order of 4000 half-megapixel images per experiment. A particular challenge for automatic analysis of this data emerges from its low Signal-to-Noise Ratio (SNR). Manual analysis takes approximately two days per experiment and analyzing person. With the automatic analysis process developed in this thesis, occurrences of nano-objects in PAMONO data can be counted and displayed in real-time while measurements are being taken. Analysis is divided into a GPU-based detector aiming at high sensitivity, complemented with a machine learning-based classifier aiming at high precision. The analysis process is embedded into a multi-objective optimization approach that automatically adapts algorithm choice and parameters to changes in physical sensor parameters. Such changes occur, for example, during sensor prototype development. In order to automatically evaluate the objectives undergoing optimization, a signal model for the PAMONO sensor is proposed, which serves to synthesize ground truth-annotated data. The parameters of the analysis process are optimized on this synthetic data, and the classifier is learned from it. Hence, the signal model must accurately mimic the data recorded by the sensor, which is achieved by incorporating real sensor data into synthesis. Both, optimized parameters and the learned classifier, achieve high quality results on the real sensor data to be analyzed: Nano-objects with diameters down to 100nm are detected reliably in PAMONO data. Note that the median SNR over all nano-objects to be detected was below two in the examined experiments with 100nm objects. While the presented analysis process can be used for real-time virus detection in PAMONO data, the optimization approach can serve in accelerating the advancement of the sensor prototype towards a final setup of its physical parameters: In this scenario, frequent changes in physical sensor parameters make the automatic adaptation of algorithmic process parameters a desirable goal. No expertise concerning the underlying algorithms is required in these use cases, enabling ready applicability in a lab scenario.2016-01-01T00:00:00ZEffiziente, GPU-basierte Simulation thermischer Spritzprozesse
http://hdl.handle.net/2003/34285
Title: Effiziente, GPU-basierte Simulation thermischer Spritzprozesse
Authors: Wiederkehr, Thomas
Abstract: Im Rahmen dieser Arbeit wird eine GPU-basierte Beschichtungssimulation für robotergestützte thermische Spritzprozesse vorgestellt, welche die effiziente Berechnung der Schichtdickenverteilung auf komplexen dreidimensionalen Bauteiloberflächen ermöglicht. Zu diesem Zweck wurde ein Footprint-basiertes Beschichtungsmodell entworfen, welches die Modellierung unterschiedlicher Spritzcharakteristiken und -prozesse auf Basis experimentell ermittelter Schichtprofile erlaubt.
Der erste Teil dieser Arbeit befasst sich daher ausführlich mit der experimentellen Erzeugung, der Digitalisierung und der Nachbearbeitung von Footprintprofilen, deren exakte Erfassung maßgeblich für die Genauigkeit der Beschichtungssimulation ist. Dabei wird zunächst die grundlegende experimentelle und algorithmische Vorgehensweise dargestellt. Im Folgenden werden verschiedene potentielle Probleme in der Herstellung und Vermessung der benötigten Schichtprofile identifiziert und technische sowie algorithmische Lösungen vorgestellt. Zur genauen und wiederholbaren Einmessung der Spritzpistole auf das zu beschichtende Bauteil wird die Konstruktion einer unmittelbar auf der Spritzpistole montierbaren Lasereinmessvorrichtung beschrieben, welche die Kompensation von translatorischen und rotatorischen Abweichungen ermöglicht und ein Referenzkoordinatensystem für die bisher geometrisch schwer erfassbare Spritzrichtung im Lichtbogenspritzprozess definiert. Zur Digitalisierung der sehr dünnen Schichtprofile werden sechs taktile und optische 3D-Scansysteme unterschiedlicher Bau- und Funktionsweise untersucht und miteinander sowie mit lichtmikroskopischen Vermessungsmethoden verglichen. Zur digitalen Nachbearbeitung der Scandaten werden zwei Methoden zur Kompensation thermisch bedingter Verformungen des Substrats vorgestellt und verglichen, durch die eine Verbesserung der Profilgenauigkeit erreicht werden kann. Ferner wird der Einfluss des zur Probenpräparation eingesetzten Sandstrahlprozesses auf die Messungen mit taktilen Systemen untersucht und als nicht zu vernachlässigender Faktor für die Messgenauigkeit identifiziert. Um darüber hinaus auch die vergleichsweise hohe Genauigkeit zweidimensionaler lichtmikroskopischer Messungen in metallographischen Querschliffen für eine Kalibrierung des dreidimensionalen Beschichtungsmodells nutzen zu können, wird ein modellbasiertes Optimierungsverfahren vorgestellt. Dieses Verfahren erlaubt die geometrische Optimierung der dreidimensionalen Footprintform auf Basis mehrerer Querschnitte von Schichtprofilen, die mittels linearer Verfahrbahnen erzeugt werden. Abschließend werden in diesem ersten Teil der Arbeit Methoden zur Darstellung von Footprintprofilen durch die Überlagerung bivariater Gaußfunktionen untersucht. Im Gegensatz zu bisherigen aus der wissenschaftlichen Literatur bekannten Ansätzen wird dabei die Anzahl der Gaußfunktionen nicht auf die Anzahl der Partikelinjektoren beschränkt. Auf diese Weise können die Vorteile funktionaler Repräsentationen, gute Filtereigenschaften und eine kontinuierliche Repräsentation der Massenstromdichte im Randbereich, mit der Fähigkeit einer numerischen Repräsentation, nahezu beliebige Spritzcharakteristiken abbilden zu können, kombiniert werden.
Der zweite Teil dieser Arbeit befasst sich mit dem Entwurf des dreidimensionalen Footprint-basierten Beschichtungsmodells und des GPU-beschleunigten Simulationssystems. Das Beschichtungsmodell wird darin in drei logische Teile gegliedert. Der erste Teil beschreibt eine grundlegende, den Prozess definierende Massenstromdichteverteilung auf Basis der ermittelten Footprintprofile. Der zweite Teil des Modells definiert eine geometrische Übertragungsfunktion, welche die Umrechnung zwischen Footprintexperiment und allgemeinen im Rahmen der Simulation auftretenden Eingriffssituationen erlaubt. In diesem Kontext werden Übertragungsfunktionen für kegelförmige und zylindrische Strahlformen hergeleitet, veranschaulicht und mit einer vereinfachten Formulierung verglichen. Der dritte Teil des Modells bildet den variablen Haftwirkungsgrad ab, zu dessen Bestimmung eine automatisierte, simulationsgestützte Verfahrensweise vorgestellt wird.
Das Simulationskonzept zeichnet sich insbesondere durch die Abbildung geometrischer Gegebenheiten des Schichtablagerungsprozesses auf den kamerabasierten Bildgenerierungsprozess der OpenGL-Renderingpipeline aus. Dies ermöglicht die Ausnutzung der Rechenleistung moderner Grafikkarten zur Schichtberechnung. Eine hohe Simulationsgeschwindigkeit, welche insbesondere für die Verwendung der Beschichtungssimulation in automatisierten Bahnplanungs- und Bahnoptimierungssystemen notwendig ist, wird durch die Implementierung weiter Teile der Simulation in Form von GLSL-Shaderprogrammen erzielt. Die interaktive Visualisierung der Schichtdickenverteilung und weiterer oberflächen- und bahnbezogener Zielgrößen sowie die vorgestellten Verfahren zur automatisierten Parameterkalibrierung und zur Sensitivitätsanalyse erlauben eine detaillierte Beurteilung und Planung eines Beschichtungsprozesses. In der ausführlichen Evaluation wird die Beschichtungssimulation anhand einfacher Experimente verifiziert und anhand der Beschichtung komplexer Tiefziehwerkzeuge validiert. Im Kontext der Beschichtung von Tiefziehwerkzeugen werden darüber hinaus die Ergebnisse einer Sensitivitätsanalyse präsentiert und der Einsatz der Simulation wird im Rahmen eines automatisierten Bahnoptimierungsverfahrens demonstriert. Ein Vergleich mit einer Implementierung auf Basis der GPU-Bibliothek Optix Prime von Nvidia bestätigt ferner die hervorragenden Laufzeiteigenschaften des in dieser Dissertation konzipierten Simulationssystems.2015-01-01T00:00:00ZGeometric and algorithmic aspects of automatic path planning with relation to spray deposition processes
http://hdl.handle.net/2003/34177
Title: Geometric and algorithmic aspects of automatic path planning with relation to spray deposition processes
Authors: Kout, Alexander2015-01-01T00:00:00ZEvolutionäre Segmentierung dreidimensionaler Formen unter Verwendung von Satelliten-Seeds
http://hdl.handle.net/2003/33939
Title: Evolutionäre Segmentierung dreidimensionaler Formen unter Verwendung von Satelliten-Seeds
Authors: Engel, Kai2015-01-01T00:00:00ZBeiträge zur Analyse, Modellierung und Kalibrierung von Kameras und 3D-Tiefensensoren
http://hdl.handle.net/2003/33118
Title: Beiträge zur Analyse, Modellierung und Kalibrierung von Kameras und 3D-Tiefensensoren
Authors: Fiedler, David Norbert
Abstract: Zahlreiche Anwendungen des Visual Computing basieren auf visuellen Daten, die durch entsprechende Sensoren erfasst werden. Dabei spielt eine möglichst genaue Kenntnis über das Abbildungsverhalten der Sensoren eine wesentliche Rolle. Diese Dissertation befasst sich mit der Analyse, der Modellierung und der Kalibrierung von Kameras und 3D-Tiefensensoren, mit den Zielen der Steigerung der Realitätsnähe der erfassten Daten und der Abschätzung der Abweichung der erfassten Daten von der Realität.
Der erste Teil dieser Dissertation widmet sich einem neuen Verfahren zur Linsenverzerrungskorrektur.
Zunächst wird ein parameterabhängiges Korrekturmodell für die Korrektur der Linsenverzerrung gewählt und anschließend eine Zielfunktion definiert, anhand der die Entzerrungsparameter optimiert werden. Dabei sind sowohl das Korrekturmodell als auch die Zielfunktion unabhängig vom Lochkameramodell und somit von den extrinsischen und intrinsischen Parametern. Die vorgeschlagene Zielfunktion basiert auf der Annahme, dass gerade Linien in der Szene auf gerade Linien im Kamerabild projiziert werden, und dass eine Verletzung dieser Eigenschaft auf eine vorhandene Linsenverzerrung zurückzuführen ist. Zur Erfassung der Linienstrukturen werden einfache schachbrettartige Kalibrierobjekte eingesetzt. Der aus dem Kontext der Objektverfolgung (Tracking) bekannte Condensation-Algorithmus wird derart angepasst, dass er als stochastischer partikelfilterbasierter Optimierer zur Berechnung der optimalen Entzerrungsparameter dient. Nach einer umfassenden Untersuchung der Kontrollparameter des Condensation-Algorithmus wird die Korrekturleistung des vorgeschlagenen Verfahrens mit existierenden Verfahren verglichen, wobei insbesondere bei starker Linsenverzerrung und zunehmendem Rauschen mit dem neuen Ansatz deutlich bessere Ergebnisse erzielt werden können. Um einen direkten Vergleich der Optimierer unter Verwendung des vorgeschlagenen Verfahrens zu ermöglichen, wird der stochastische partikelfilterbasierte Optimierer gegen den deterministischen Levenberg-Marquard-Algorithmus ausgetauscht. Mit Ausnahme eines untersuchten Spezialfalls ist das vorgeschlagene stochastische Verfahren überlegen.
Der zweite Teil der Dissertation liefert Beiträge im Bereich der 3D-Tiefensensoren, die anhand des Kinect-Tiefensensors erarbeitet werden, jedoch auch auf andere Tiefensensoren übertragbar sind. Zunächst wird auf die Messfehlerbeschaffenheit in den Tiefenbildern der Kinect eingegangen, die sowohl von Sensorort (Position im Tiefenbild) als auch von der Messdistanz abhängig ist. Es werden zwei auf planaren Oberflächen basierende Korrekturansätze (Delta-Plane und MDP) vorgestellt, die auf einem heuristischen Korrekturmodell basieren und durch eine tabellarische Beschreibung effizient eingesetzt werden können. Die Korrekturleistung wird anhand unterschiedlicher Testszenarien sowohl quantitativ als auch qualitativ beurteilt und demonstriert. Einen weiteren Beitrag stellt ein homographiebasiertes Verfahren zur Online-Referenzmessdatengewinnung dar, welches mit einfachen Kalibrierobjekten sowie der bereits in der Kinect integrierten Hardware vollständig durchführbar ist. Dieses Verfahren ermöglicht eine kostengünstige und interaktive Aufdeckung und Beurteilung von Messfehlern während des laufenden Betriebs. Ein weiterer Teil der Dissertation widmet sich der Aufdeckung unterschiedlicher umweltbedingter Auswirkungen auf den Tiefensensor sowie auf die internen Kameras der Kinect, wobei insbesondere der Temperatur ein wesentlicher Einfluss nachgewiesen wird. Als Konsequenz aus den Beobachtungen und Experimenten wird eine Reihe von praktischen Regeln abgeleitet, die zur Fehlervermeidung bzw. Fehlerreduktion während des Kalibrier- und Messvorgangs der Kinect beitragen. Zuletzt wird ein experimenteller Nachweis der Robustheit des MDP basierten Korrekturverfahrens gegenüber Umwelteinflüssen erbracht.2014-05-13T00:00:00ZKlassifikation morphologischer und pathologischer Strukturen in koronaren Gefäßen auf Basis intravaskulärer Ultraschallaufnahmen zur klinischen Anwendung in einem IVB-System
http://hdl.handle.net/2003/27016
Title: Klassifikation morphologischer und pathologischer Strukturen in koronaren Gefäßen auf Basis intravaskulärer Ultraschallaufnahmen zur klinischen Anwendung in einem IVB-System
Authors: Weichert, Frank
Abstract: Erkrankungen des Herz-Kreislaufsystems sind in Deutschland für fast 50% der Todesfälle verantwortlich. Insbesondere die Arteriosklerose (vulgo: „Arterienverkalkung“) ist dabei ein dominierendes Krankheitsbild. So ist es auch nicht verwunderlich, dass die Arteriosklerose seit den Anfängen der wissenschaftlichen Medizin ein Feld für umfangreiche Untersuchungen gewesen ist. Speziell durch den technischen Fortschritt bildgebender Verfahren war es möglich neuartige Diagnose- und Therapiemethoden zu entwickeln. Dabei hat sich gerade der intravaskuläre Ultraschall zu einem Goldstandard in der Diagnose arteriosklerotischer Erkrankungen und, in Kombination mit der intravaskulären Brachytherapie, zu einer Erfolg versprechenden Basistechnik für therapeutische Maßnahmen entwickelt. Grundvoraussetzung fast jeder bildbasierten Intervention ist aber die Separierung der Bilddaten in anatomisch und pathologisch differenzierte, saliente Regionen. In Anbetracht zunehmender, umfangreicherer Datenmengen kann eine derartige Aufarbeitung nur rechnergestützt durch Problem adaptierte Klassifikationsalgorithmen gewährleistet werden.
Daher war es das Ziel dieser Arbeit, neue Methoden zur Merkmalsextraktion und Algorithmen zur Klassifikation morphologischer und pathologischer Strukturen in koronaren Gefäßen bereitzustellen. Aus der initialen Fragestellung wurde zudem zeitnah deutlich, dass das Forschungsvorhaben Anknüpfungspunkte zu weiteren hochgradig relevanten inter- und intradisziplinären Forschungsthemen, beispielsweise der Histologie, Systembiologie oder Chemietechnik, aufweist. Aber auch vonseiten der Anwendungsszenarien wurden teilweise völlig neue, innovative Wege beschritten. Exemplarisch sei ein E-Learning-Ansatz zur „Übersetzung“ digitaler Bilddaten in haptisch erfahrbare Reliefs für blinde und sehbehinderte Schülerinnen und Schüler genannt. In Anbetracht dieser partiell divergierenden Sichtweisen war auch die generalisierte, von der expliziten Fragestellung abstrahierte Umsetzung eine Ausrichtung der Arbeit.
Dieser Intention folgend wurden drei wesentliche methodische und konzeptionelle Entwicklungen innerhalb der Arbeit realisiert: ein Expertensystem zur Approximation arterieller Kompartimente mittels unscharfer elliptischer Templates, ein neuartiger, effizienter Ansatz zur signaltheoretischen Extraktion textureller Merkmale und die Etablierung maschinelle Lernverfahren unter Integration von a priori Wissen. Über eine konsequente Integration statistischer Gütemaße konnte zudem eine ausgeprägte Rückkopplung zwischen Klassifikations- und Bewertungsansätzen gewährleistet werden. Gemeinsam ist allen Ansätzen das Ansinnen, trotz hoch anwendungsbezogener Umsetzungen, die fortwährende Portabilität zu beachten. In einer übergeordneten Abstraktion kann die Intention der Arbeit somit auch in der „generalisierten Nutzung signaltheoretischer Merkmale zur Klassifikation heterogener, durch texturelle Ausprägungen zu differenzierende Kompartimente mittels maschineller Lernverfahren“ verstanden werden.2010-03-31T10:13:57ZAlgorithmische Analyse von rohrförmigen Flächen für das Reverse Engineering
http://hdl.handle.net/2003/25780
Title: Algorithmische Analyse von rohrförmigen Flächen für das Reverse Engineering
Authors: Wortmann, Christian
Abstract: This dissertation presents a method for planning the manufacturing of pipes from straight cylinders. On the one hand, this allows for feasibility studies by simulation and analysis of the strain on the cylinder during the manufacturing process. This is done before a pipe is created. On the other hand, planning may be used as input for manufacturing machines used by the industry. A possible approach is to start with the result, i.e. the desired pipe, to get the initial situation, i.e. the cylinder. This is done by reverse engineering the manufacturing operations. Here the following problems can be determined: - Integration of pipes, i.e. the approximation of the pipe by a tube. A tube is a deformed and bent cylinder. - Approximation of spatial curves by circular splines i.e. a G1 continuous curve which is a consecutive combination of arcs and lines. This dissertation starts with a mathematical definition of pipes and the needed theoretical basis, for example the definition of part-pipes. Based on this, the pipe-tube-approximation problem is formulated as a multicriterial optimization problem which is orientated at the elastic contours of the image processing. Two solutions are presented for the optimization problem. The first one uses dynamic programming, the second one is an adaptive segmentation which is a well known approximation method of curves by polygons. The advantage of the adaptive segmentation is the low run-time. The disadvantage is that a success is not guaranteed, in contrast to dynamic programming. Some methods for basic geometrical operations are presented, which are required to achieve an efficient implementation. Both optimization methods are analyzed. On the one hand, theoretical conditions are presented to guarantee the success of adaptive segmentation. On the other hand, analysis is based on experimental evaluation. It will be shown that both methods yield good results for pipes used in the industry. However, neither provide fully automatic solutions for the practical domain of application. Suggestions are made to handle this complex problem. The definition of a "U-spline-curve" is presented to describe the curve approximation. The aim of a U-spline-curve is to contain as few segments as possible. Therefore, two heuristics are presented. The first one uses adaptive segmentation which is based on the curvature of the curve. The second one is based on a well known algorithm which creates an arc-spline-curve with a minimal number of segments. It will be shown that both methods yield equal results when applied to pipes used in the industry.2008-08-25T13:47:58ZRemote vision based multi gesture interaction in natural indoor environments
http://hdl.handle.net/2003/24211
Title: Remote vision based multi gesture interaction in natural indoor environments
Authors: Brockmann, Christian
Abstract: Der Einsatz von Computersehen als Sensor für die Interaktion mit technischen Systemen hat in den letzten Jahren starkes Interesse gefunden. In vielen der bekannt gewordenen Fallstudien und Anwendungen werden Posen oder Bewegungen einer interagierenden Person durch einen Rechner, der mit Kameras ausgestattet ist, beobachtet, und die Reaktionen des Rechners dem Benutzer angezeigt, der sein Verhalten dann so ändert, dass ein gewünschtes Interaktionsziel erreicht wird.
Diese Arbeit greift zwei wesentliche Schwierigkeiten der computersehensbasierten oder perzeptuellen Mensch-Maschine-Interaktion auf: das Unterscheiden von Gesten von willkürlichen Körperhaltungen oder Bewegungen sowie der Umgang mit natürlichen Umgebungen. Ferner wird die Frage der Abtrennung der computersehensbasierten Schnittstelle von der Anwendung angegangen, analog zu heutigen anwendungsunabhängigen graphischen Benutzungsschnittstellen. Wesentliche Beiträge sind
- eine so genannte "Interaktionsraumarchitektur", die die computersehensbasierte Schnittstelle von der Anwendung durch eine Folge von Interaktionsräumen entkoppelt, die aufeinander abgebildet werden,
- eine so genannte "Interaktionsraumarchitektur", die die computersehensbasierte Schnittstelle von der Anwendung durch eine Folge von Interaktionsräumen entkoppelt, die aufeinander abgebildet werden,
- ein Konzept der "Mehrtyp-Gesteninteraktion", die verschiedene Gesten mit örtlichen und zeitlichen Randbedingungen kombiniert, um so die Zuverlässigkeit der Gestenerkennung zu erhöhen,
- zwei Konzepte zur optischen Kalibrierung des Interaktionsraumes, die den Aufwand der Integration von Kameras in die Interaktionsumgebung reduzieren,
- eine Lösung des Problems der Kombination von Zeigegesten mit statischen Handgesten durch die Verwendung von statischen Kameras für globale Ansichten und rechnergesteuerten aktiven Kameras für lokal angepasste Ansichten,
- eine Kombination von mehreren Methoden, um das Problem von unzuverlässigen Ergebnissen der Bildsegmentierung zu mindern, die durch wechselnde Beleuchtung, die für natürliche Umgebungen typisch ist, hervorgerufen werden: Fehlererkennung und Konturkorrektur auf Grundlage von Bildfolgen und mehreren Ansichten, situationsabhängige Signalverarbeitung sowie automatische Parameteranpassung.
Die Tragfähigkeit der Konzepte wird anhand eines Systems zur computersehensbasierten Interaktion mit einer Rückprojektionswand nachgewiesen, das implementiert und evaluiert wurde.; Computer vision as a sensor of interaction with technical systems has found increasing interest in the past few years. In many of the proposed case studies and applications, the user's current pose or motion is observed by cameras attached to a computer, and the computer's reaction is displayed to the user who changes the pose accordingly in order to reach a desired goal of interaction.
The focus of this thesis is on two major difficulties of computer vision-based, or perceptual, human-computer interaction: distinguishing gestures from arbitrary postures or motions, and coping with troubles caused by natural environments. Furthermore, we address the question of decoupling the computer vision-based interface from the application in order to achieve independency between both, analogously to today's application-independent graphical user interfaces. The main contributions are
- a so-called “interaction space architecture” which decouples the computer vision interface from the application by using a sequence of interaction spaces mapped on each other,
- a concept of “multi-type gesture interaction” which combines several gestures with spatial and temporal constraints in order to increase the reliability of gesture recognition,
two concepts of optical calibration of the interaction space which reduce the efforts of integrating the cameras as sensors in the environment of interaction,
a solution to the problem of combining pointing gestures with static hand gestures, by using static cameras for global views and computer-controlled active cameras for locally adapted views,
a combination of several methods for coping with unreliable results of image segmentation caused by varying illumination typical for natural environments: error detection and contour correction from image sequences and multiple views, situation-dependent signal processing, and automatic parameter control.
The concepts are proved based on a system for computer vision-based interaction with a backprojection wall, which has been implemented and evaluated.2007-03-27T05:56:28ZDiscrete displacement fields
http://hdl.handle.net/2003/2572
Title: Discrete displacement fields
Authors: Ayasse, Jörg
Abstract: Die Form von Produkten und Gebrauchsgütern wird zunehmend komplexer. Der Einsatz von Computern hilft dabei, diese Komplexität zu beherrschen und die Entwicklungszeit für neue Produkte zu reduzieren. Zwei wichtige Fertigungsprozesse sind Fräsen und Schleifen. Beide Prozesse haben gemeinsam, dass ein Werkzeug (Fräser, Schleifscheibe) entlang der Oberfläche eines Werkstücks geführt wird und Material vom Werkstück abträgt. Ein zentrales Problem der Produktionsplanung, bekannt als Bahnplanungsproblem, ist es, automatisch eine geeignete Werkzeugbahn zu finden, um das Werkstück aus seiner initialen Form in die gewünschte Form zu überführen. Ein weiterer Fertigungsprozess ist Umformen, z.B. von Blechen. Ein Problem beim Umformen besteht darin, geeignete Oberflächen und Formen zu finden, welche bei der Deformation keine Schäden verursachen. In dieser Arbeit werden sogenannte diskrete Verschiebungsfelder (Discrete Displacement Fields, DDFs) zur Darstellung der Werkstückoberfläche in der Simulation von Fertigungsprozessen verwendet. Ein DDF besteht aus einer Trägerfläche S, auf welcher ein Vektorfeld V definiert ist. Der zu einem Punkt von S gehörende Vektor gibt eine Verschiebung dieses Punktes an, die Menge aller verschobenen Punkte definiert eine neue Fläche F . Die Vektoren können als Strecken interpretiert werden, deren Vereinigung eine Kruste auf der Fläche S definiert. Von dieser Kruste kann Material abgetragen werden, indem die Verschiebungsvektoren gekürzt werden. Eine weitere Interpretationsmöglichkeit von DDFs ist es, die Fläche F als Deformation der Fläche S aufzufassen. Damit können Simulationen von spanenden und umformenden Prozesse in natürlicher Weise durch eine einheitliche geometrische Repräsentationsform, die DDF, unterstützt werden. Als zentrales Werkzeug für die Simulation von spanenden Prozessen wird ein DDF-Tiefenpuffer-Algorithmus vorgestellt. Es wird gezeigt, wie dieser Algorithmus im Rahmen eines allgemeinen Verfahrens für die Bahnplanung für das Schleifen eingesetzt werden kann, das in der Arbeit skizziert wird. Weitere Ergebnisse betreffen die Konvertierung von Dreiecksnetzen in die DDF-Darstellung und das Problem des Auffindens von Krusten, die die Eigenschaft der eindeutigen Projizierbarkeit haben. Letzteres ist für die überschneidungsfreie Deformation von Flächen wichtig, die in einem Verfahren zur Formenplanung für das Umformen verwendet wird.; The shapes of mechanical parts become more and more complex, and the introduction of computers helps to cope with the complexity and reduces the development time for new products. Two important technologies of production are milling and grinding. Both processes have in common that a tool (milling cutter, grinding disc/belt) is moved along the surface of a workpiece, removing material from the workpiece. A central task of production planning, known as path planning problem, is to find automatically a suitable motion path for the tool to transform the initial workpiece into the desired shape. Another technology of production is deformation of e.g. metal plates. A problem arising with deformation is to find shapes and moulds which do not cause damages during the process of deformation. We propose to use so-called discrete displacement fields (DDFs) as the basis of representation of geometric shapes in simulations of production processes. A DDF consists of a supporting surface S on which a vector field V is given. The vector assigned to every point on S defines a displacement of the point in space and the union of all displaced points define a new surface F. If the displacement vectors are seen as line segments, their union defines a solid fringe on S, and material can be removed from this fringe by cutting displacement vectors. A further interpretation of DDFs is to understand the surface F as deformation of S. Thus simulations of milling/grinding as well as of deformation can be supported canonically by a common geometric representation, the DDF. We introduce the DDF depth-buffer algorithm as the central tool for efficient simulation of material removal from DDF surfaces. We show how the DDF depth-buffer algorithm can be used in a general approach to path planning for grinding which we present. Further results concern conversion of triangular meshes into a DDF representation, and the problem of finding fringes having the so-called unique-projection property. The latter is important for intersection-free deformation of surfaces used in an approach to mould planning for deformation.2003-08-28T00:00:00ZA model-based approach to intraoperative guidance of flexible endoscopy
http://hdl.handle.net/2003/2571
Title: A model-based approach to intraoperative guidance of flexible endoscopy
Authors: Kukuk, Markus
Abstract: Endoscopy is a medical procedure, where a physician uses an optical instrument called an "endoscope" to obtain a magnified view of the inner surface of hollow organs and to access the tissue through surgical tools. An endoscope is a flexible tube, which is inserted into the body through either natural body openings or small incisions. Flexible endoscopy often results in a better outcome for the patient as opposed to open surgery. However, this technique also presents increased challenges to the physician and therefore often necessitates intraoperative guidance.
This dissertation presents a new approach to the intraoperative guidance of flexible endoscopy. It proposes to calculate a patient specific "protocol" prior to the intervention to achieve a sensorless guidance during the procedure. This protocol prescribes in detail how to handle the endoscope and tools in order to successfully perform an endoscopic procedure. During the intervention, the physician executes the protocol, by setting endoscope and tools to the prescribed configuration.
The calculation of the protocol is based on three components: (1) A 3D model of the target anatomy derived from a CT/MRI scan of the patient, (2) a deformable model representing the endoscope and (3) a virtual endoscopy system. These components are combined to simulate an endoscopic procedures and to estimate a set of endoscope parameters. This general approach is validated for an endoscopic procedure called "Transbronchial Needle Aspiration" (TBNA), which involves the "blind" placement of a needle into a target. Based on a set of candidate shapes for the real endoscope obtained from the endoscope model, an "optimal" needle placement strategy is presented that maximizes the probability of success for TBNAs.2003-05-02T00:00:00ZA Framework for Segmentation and Contour Approximation in Computer-Vision Systems
http://hdl.handle.net/2003/2570
Title: A Framework for Segmentation and Contour Approximation in Computer-Vision Systems
Authors: Leubner, Christian
Abstract: In dieser Arbeit wird ein System zur Segmentierung und Konturapproximation in Computer-Vision Systemen vorgestellt. Das Ziel des Systems ist die Erkennung und räumliche Abtrennung von Personen und Objekten in Videobildern von einem bekannten Hintergrund. Hierfür wird ein hierarchisches mehrstufiges Segmentierungssystem mit internen Rückkopplungsmechanismen eingeführt, das aus einer unteren, einer mittleren und einer oberen Verarbeitungsebene besteht. Auf der unteren Verarbeitungsebene wird eine pixelweise Segmentierung durchgeführt und detailliertes Wissen über den Hintergrund in Fuzzy-Wissensbasen abgelegt. Die mittlere Verarbeitungsebene unterteilt das Bild in rechteckige Bereiche und wendet ein fuzzy-regelbasiertes Mustererkennungssystem auf diesen Bereichen an. Schließlich werden auf der oberen Verarbeitungsebene anwendungsabhängige Kenntnisse über die zu findenden Objekte einbezogen, um mögliche Fehlklassifikationen zu eliminieren. Interne Rückkopplungsmechanismen ermöglichen ein ständiges Weiterlernen des Hintergrundes, eine Adaption der Parameter im laufenden Betrieb und eine ständige Verbesserung der Segmentierungsergebnisse. Desweiteren wird ein neuer Algorithmus zur Konturapproximation vorgestellt. Der Algorithmus ist für den Einsatz in Echtzeitsystem geeignet, benötigt nur wenige Parameter und basiert auf rein geometrischen Berechnungen. Besonderer Wert wurde in dieser Arbeit auf den Umgang mit wechselhaften und sich ändernden Beleuchtungsverhältnissen gelegt, die häufig zu ernsthaften Problem bei Segmentierungsalgorithmen führen. Die hohe Leistungsfähigkeit des Algorithmus wird durch massive Hauptspeichernutzung erreicht. Die gute Gesamtleistung des vorgestellten Systems wird anhand verschiedener Anwendungen demonstriert.; In this thesis, a framework for segmentation and contour approximation in computer-vision systems is presented. The goal of the system is the recognition and spatial isolation of persons and objects in video images in front of a known background. For this purpose, a hierarchical multi-level segmentation system with internal feedback mechanisms is introduced, which consists of a low-level, a mid-level, and a high-level processing stage. The low-level processing stage performs a pixelwise segmentation and acquires detailed knowledge about the background in fuzzy knowledge bases. The mid-level processing stage subdivides the image area in rectangular boxes and applies a fuzzy rule-based pattern recognition system to these box areas. Finally, the high-level processing stage incorporates application-dependent knowledge about the objects that have to be found in order to eliminate possible misclassifications. Internal feedback mechanisms allow for continuous learning of the background, online adaption of parameters, and a continuous improvement of the segmentation results. Moreover, a new algorithm for contour approximation is introduced. The algorithm is suitable for real-time applications, requires only few parameters, and is based on mere geometric calculations. A special emphasis of this work has been laid on the anticipation of varying and changing illumination, which often leads to severe problems for segmentation algorithms. The good capabilities of the algorithm are achieved by extensively exploiting main memory. The good overall performance of the introduced system is demonstrated on the basis of different applications.2002-12-16T00:00:00ZReconstruction of surfaces from unorganized three-dimensional point clouds
http://hdl.handle.net/2003/2569
Title: Reconstruction of surfaces from unorganized three-dimensional point clouds
Authors: Mencl, Robert
Abstract: In dieser Arbeit wird ein neuer Algorithmus zur Rekonstruktion von Flächen aus dreidimensionalen Punktwolken präsentiert. Seine besonderen Eigenschaften sind die Rekonstruktion von offenen Flächen mit Rändern, Datensätzen mit variabler Punktdichte und die Behandlung von scharfen Kanten, d.h. Stellen mit unendlicher Krümmung. Es werden formale Argumente angegeben, die erklären, warum der Algorithmus korrekt arbeitet. Sie bestehen aus einer Definition von 'Rekonstruktion' und dem Beweis der Existenz von Punktmengen für die der Algorithmus erfolgreich ist. Diese mathematische Analyse konzentriert sich dabei auf kompakte Flächen mit beschränkter Krümmung und ohne Ränder. Weitere Beiträge sind die Anwendung des Flächenrekonstruktionsverfahrens für die interaktive Modellierung von Flächen und eine Prozedur für die Glättung von verrauschten Punktwolken. Zusätzlich kann der Algorithmus leicht für die lokal beschränkte Rekonstruktion eingesetzt werden, wenn nur ein Teil des Datensatzes zur Rekonstruktion herangezogen werden soll.; In this thesis a new algorithm for the reconstruction of surfaces from three-dimensional point clouds is presented. Its particular features are the reconstruction of open surfaces with boundaries, data sets with variable density, and the treatment of sharp edges, that is, locations of infinite curvature. We give formal arguments which explain why the algorithm works well. They consist of a definition of 'reconstruction', and the demonstration of existence of sampling sets for which the algorithm is successful. This mathematical analysis focuses on compact surfaces of limited curvature without boundary. Further contributions are the application of the surface reconstruction algorithm for interactive shape design and a smoothing procedure for noise elimination in point clouds. Additionally, the algorithm can be easily applied for locally-restricted reconstruction if only a subset of the data set has to be considered for reconstruction.2001-12-05T00:00:00ZVerfahren zur verbesserten Approximation von Lichtverteilungen in der fotorealistischen Bildsynthese
http://hdl.handle.net/2003/2568
Title: Verfahren zur verbesserten Approximation von Lichtverteilungen in der fotorealistischen Bildsynthese
Authors: Pietrek, Georg
Abstract: Gegenstand der fotorealistischen Bildsynthese ist die Erzeugung realistisch wirkender Rasterbilder aus dreidimensionalen Szenen durch die Berechnung von Lichtverteilungen. Grundlage der Berechnung ist die Bildsynthesegleichung von Kajiya, als deren Lösung sich die gesuchte Lichtverteilung ergibt. Die Bildsynthesegleichung ist im allgemeinen nicht analytisch lösbar. Zur näherungsweisen Lösung sind im wesentlichen zwei Vorgehensweisen bekannt: Monte Carlo-Abtastverfahren und Finite-Elemente-Verfahren.In dieser Arbeit wird eine Verbesserung von Monte Carlo-Strahlverfolgung entwickelt, die bei gegebener Stichprobenanzahl Bilder signifikant besserer Qualität als bisher bekannte Verfahren liefert. Dies wird durch den Einsatz adaptiver hierarchischer Dichtefunktionen erreicht. Aus den Abtastungen der Strahlverfolgung werden als Nebenprodukt Approximationen des Integranden bestimmt, aus denen verbesserte Dichtefunktionen gewonnen werden, die zu einer Effizienzsteigerung des Monte Carlo-Integrationsverfahrens führen.Für die Berechnung von Bildern für den Fall der uniformen diffusen Reflexion (Radiosity-Berechnung) nach dem klassischen Finite-Elemente-Ansatz mit konstanten Basisfunktionen werden eine Reihe von Interpolationsverfahren für die resultierende Radiosity-Funktion zur Verbesserung der visuellen Bilddarstellung angegeben. Diese basieren insbesondere auf Verfahren für die Streudateninterpolation. Durch empirische Analyse wird eine Bewertung der untersuchten Verfahren durchgeführt.Für die Implementierung und Analyse der Verfahren wurde eine Software-Architektur entwickelt. Designziele waren die Entwicklung einer flexibel änderbaren und erweiterbaren Testumgebung sowie die Ermöglichung der vergleichbaren empirischen Effizienzanalyse verschiedener Lösungsverfahren, indem soweit wie möglich dieselbe Implementierungsbasis genutzt wird und nur in wirklich unterschiedlichen Teilen unterschiedliche Algorithmen und deren Implementierung zum Einsatz kommen.2001-07-25T00:00:00ZGeometrische Algorithmen in der Flächenrückführung
http://hdl.handle.net/2003/2567
Title: Geometrische Algorithmen in der Flächenrückführung
Authors: Weller, Frank
Abstract: Gegenstand der Flächenrückführung ist, aus einer gegebenen Menge von Abtastpunkten einer Fläche eine Näherung zu rekonstruieren, die die Fläche möglichst gut repräsentiert. Ein weit verbreiteter Ansatz ist, die rekonstruierte Fläche durch ein Netz aus Polygonen, meist Dreiecken, zu beschreiben. Die Schwierigkeit besteht darin, unter den kombinatorisch vielen Möglichkeiten eine "gute" Rekonstruktion zu erhalten, insbesondere für den Fall, dass die ursprünglich gegebene Fläche nicht bekannt ist. Im Zusammenhang mit Verfahren zur Flächenrückführung treten vielfältige geometrische Teilprobleme auf, die für sich gesehen interessant sind. In dieser Arbeit werden für eine Reihe solcher Probleme effiziente Algorithmen entwickelt. Zu nennen sind Korrektheitsbetrachtungen für den gebräuchlichen Oriented-Walk-Algorithmus, Triangulierung innerhalb frei wählbarer, nicht konvexer Gebiete in der Ebene, Berechnung konvexer Hüllen von Polygonen auf Sphären mit linearem Zeitaufwand, Stabilität von Delaunay-Facetten mit Anwendung auf die Rekonstruktion geschlossener Flächen sowie effiziente Aufzählung polygonaler Hüllen.2001-01-17T00:00:00ZNew contributions to spatial partitioning and parallel global illumination algorithms
http://hdl.handle.net/2003/2566
Title: New contributions to spatial partitioning and parallel global illumination algorithms
Authors: Garmann, Robert
Abstract: Diese Dissertation ist an der Schnittstelle zweier Disziplinen der Informatik angesiedelt: Computergrafik (Globale Beleuchtung) und Paralleles Rechnen (Dynamisches Partitionieren). Einerseits wird der Hierarchische Radiosity Algorithmus (HRA) - ein berühmter und effizienter Algorithmus zur globalen Beleuchtungssimulation - bzgl. seiner Parallelisierungsfähigkeit untersucht. Andererseits wird ein Werkzeug aus der Gattung der orthogonalen rekursiven Zweiteilungsverfahren zur dynamischen Partitionierung räumlich abgebildeter Aufgaben entwickelt sowie theoretisch und experimentell analysiert. Der HRA ist eine spezielle Instanz von Algorithmen, die als eine Ansammlung von räumlich abgebildeten Aufgaben formuliert werden können. Als Beweis der Praktikabilität unseres Werkzeugs wenden wir das Werkzeug auf den HRA an und beobachten ein gut skalierbares Verhalten und nützliche Werte bzgl. der Steigerung der Berechnungsgeschwindigkeit.; This thesis resides around the interface of two disciplines in computer science: computer graphics (global illumination) and parallel computing (dynamic partitioning). On the one hand the hierarchical radiosity algorithm (HRA) - a famous and efficient global illumination algorithm - is examined with respect to its capability of being parallelized. On the other hand a dynamic orthogonal recursive bisection tool for the dynamic partitioning of spatially mapped tasks is developped and analyzed theoretically and experimentally. The HRA is a special instance of algorithms that can be formulated as a collection of spatially mapped tasks. As a proof of practicability of our tool we apply the tool to the HRA and observe a well scalable behaviour and useful speedup values.2000-09-27T00:00:00ZEffiziente Lösungsverfahren für Sichtbarkeitsprobleme in der realitätsnahen Bildsynthese
http://hdl.handle.net/2003/2565
Title: Effiziente Lösungsverfahren für Sichtbarkeitsprobleme in der realitätsnahen Bildsynthese
Authors: Hinkenjann, André
Abstract: Eine prinzipielle Schwierigkeit bei der Bildsynthese ist die Sichtbarkeitsbestimmung. Sie nimmt einen grossen Anteil des Rechenaufwands praktisch aller heutigen Verfahren ein. In dieser Dissertation werden Sichtbarkeitsprobleme in anderen Ausprägungen als der üblichen Sichtbarkeit von einem Punkt aus betrachtet, nämlich wie sie etwa beim hierarchischen Radiosity-Verfahren auftreten. Als Hauptproblem wird die Berechnung der Sichtbarkeitsmenge zweier Elemente behandelt. Dieses besteht darin, eine gegebene Szene von Elementen so in eine Datenstruktur vorzuverarbeiten, dass die Sichtbarkeit zwischen zwei disjunkten Elementen a und b (desselben Typs und disjunkt vom Rest der Szene) effizient bestimmt werden kann.
Dieses Problem wird zunächst im Hinblick auf eine worst-case-effiziente, exakte Lösung betrachtet. Auf der Grundlage von Datenstrukturen zur Halbraumanfrage wird eine Lösung präsentiert, die eine Anfrage asymptotisch schneller als durch systematisches Testen, d.h. in sublinearer Zeit in der Szenengrösse, beantwortet und dabei mit nahezu linearem Speicherplatzbedarf auskommt.
Begründet durch die bekannte Beobachtung, dass sich Sichtbarkeitsprobleme trotz ihres unangenehmen Verhaltens im schlechtesten Fall heuristisch gut lösen lassen, konzentriert sich die Arbeit dann auf diesen Aspekt. Als ein Lösungsvorschlag werden zunächst hierarchische Verdeckungsbäume eingeführt. Sie erlauben einen Trade-off zwischen Speicherbedarf und Rechenzeit sowie Exaktheit der Lösung.
Als ganz anderer Zugang wird dann eine Lösung durch Abtastung entwickelt, die sich auch auf andere Anfrageprobleme übertragen lässt. In einem Vorverarbeitungsschritt werden Abtastanfragen zusammen mit ihren Antworten in einer Antwortdatenbank gespeichert. Aus diesen Abtastanfragen werden zur Laufzeit für beliebige Anfragen Antworten (re)konstruiert. Es werden worst-case-Schranken für Laufzeit und Speicherbedarf der Datenstruktur für die Abtastanfragen in Abhängigkeit von einem vorgegebenen Fehler hergeleitet. Dabei werden die zwangsläufig auftretenden Fragen der Stichprobenanfragen und der Komprimierung der Stichprobenantworten behandelt.2000-05-19T00:00:00ZRadiosity on evolving networks
http://hdl.handle.net/2003/2564
Title: Radiosity on evolving networks
Authors: Bohn, Christian-Arved2000-03-29T00:00:00Z