Library

Description: We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.

Description: Nur wenn eine Kultur der Nachnutzung und des freien Teilens von Wissen entsteht, werden Wissenschaftler auch die eigenen Forschungsdaten für die Langzeitverfügbarkeit aufbereiten und freigeben. Zu diesem Zweck ist diese Handreichung als Einstieg in das Thema Forschungsdatenmanagement entstanden.

Description: We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.

Description: We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.

Description: The resource constrained assignment problem (RCAP) is to find a minimal cost cycle partition in a directed graph such that a resource constraint is fulfilled. The RCAP has its roots in an application that deals with the covering of a railway timetable by rolling stock vehicles. Here, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes several variants of vehicle routing problems. We contribute a local search algorithm for this problem that is derived from an exact algorithm which is similar to the Hungarian method for the standard assignment problem. Our algorithm can be summarized as a k-OPT heuristic, exchanging k arcs of an alternating cycle of the incumbent solution in each improvement step. The alternating cycles are found by dual arguments from linear programming. We present computational results for instances from our railway application at Deutsche Bahn Fernverkehr AG as well as for instances of the vehicle routing problem from the literature.

Description: The classical Unit Commitment Problem (UC) consists in determining the production of a set of thermal and hydro power generation units over a given time horizon, in order to meet a forecast energy demand and minimize a cost function. In the last years, in connection with the UC, increasingly attention has been given to active switching, namely the possibility of changing the topology of the transmission network by tripping some of the lines. Active switching has been indeed recognized as an important way to improve capacity and reliability of the network. Modifying the network topology is also very useful in modern electricity systems, where the penetration of on-programmable renewable energy sources is high and tends to be very concentrated in some zones of the network. As a consequence, the interest for automatic and optimized switching procedures is currently spreading. In this paper, we address the UC when complemented by active switching, thus leading to so-called Unit Commitment with Optimal Transmission Switching (UCOTS). We formulate the UCOTS as a mixed integer linear program, where we unify tight formulations recently proposed in literature for relevant subfamilies of constraints of the problem. Concerning the cost function, in our formulation we approximate the quadratic thermal cost objective function by a piecewise linear function based on perspective cuts and we propose a new simple and effective way to perturb it, with the aim of breaking symmetries induced by optimal transmission switching decision variables. Our original solution approach also exploits specialized branching priorities. Computational experiments on realistic UCOTS instances highlight that our new framework is able to find optimal and near-optimal solutions in reasonable amount of time by direct use of a state-of-the-art commercial MIP solver.

Description: Nach einem kurzen Abriss über die Bedeutung des Verkehrssektors als eine wichtige Schlüsseltechnologie im gesamten Verlauf der Menschheitsgeschichte skizzieren wir die Rolle der Mathematik für Verkehr und Transport. Wir spekulieren dann über zukünftige Entwicklungen, insbesondere im Bereich des öffentlichen Personenverkehrs, und begründen, dass die in diesem Bereich anstehenden Herausforderungen nur mit dem Einsatz mathematischer Methoden angemessen bewältigt werden können. Die demographischen Prozesse, die in verschiedenen Teilen der Welt unterschiedlich verlaufen, wie z.B. Überalterung in Europa oder dynamische Trends zu Megastädten in Entwicklungsländern, sich ändernde Lebens- und Produktionsverhältnisse, stark wachsender Bedarf nach Mobilität und enormes Anwachsen der Komplexität der Verkehrsplanung und -durchführung, machen einen verstärkten Zugriff auf mathematische Modellierung, Simulation und Optimierung notwendig. Diese Entwicklung stellt sowohl große Herausforderungen an die Mathematik, wo vielfach noch keine geeigneten Methoden vorhanden sind, als auch an die Praktiker im Bereich von Verkehr und Transport, die sich mit neuen Planungs- und Steuerungstechnologien befassen und diese effizient einsetzen müssen. Hier wird intensive Kooperation zwischen vielen beteiligten Akteuren gefragt sein.

Description: We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We show that the concept of metric inequalities to characterize capacities that support a multi-commodity flow can be generalized to deal with direct connections.

Description: In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult feasibility problem. The first phase consists of four distinct algorithms applying linear, and methods for complementarity constraints to compute possible settings for the discrete decisions. The second phase employs a precise continuous programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances that are significantly larger than networks that have appeared in the mathematical programming literature before.

Description: In den letzten Jahren ist die reproduktive Leistung von Milchkühen parallel zur steigenden Milchleistung drastisch gesunken. Um die zu Grunde liegenden biologischen Mechanismen besser zu verstehen, wurde in dieser Arbeit eine Modellerweiterung des vorhandenen Modells von Stötzel et al. (2011) um metabolische Einflussfaktoren angestrebt. Hierfür wurde zuerst aus veröffentlichten, experimentell gewonnen Erkenntnissen herausgearbeitet, wie die metabolischen Faktoren auf das periodische Zyklusverfahren der Milchkuh Einfluss nehmen. Daraus wurde ersichtlich, dass Glukose, Insulin und IGF-I die wichtigsten metabolischen Faktoren sind, aber lediglich IGF-I als dynamische Größe in das Modell eingeht. Zur Validierung des erweiterten Modells, wurden im Rahmen dieser Arbeit Szenarien aus der Literatur entwickelt, welche eine negative Energiebilanz oder den Effekt von Diätrestriktionen auf den Milchkuhzyklus simulieren sollten. Ferner wurden Messdaten für IGF, E2 und P4 von Kawashima et al. (2007) und Cerri et al. (2011) bereit gestellt. Das erweiterte Modell umfasst lediglich 8 Parameter mehr als das Ursprungsmodell, wobei gezeigt werden konnte, dass weder die Bedingung für die Lösbarkeit noch die Stabilität in den Anfangswerten eingebüßt wurde. Die Modellkurven konnten mittels des NLSCON erfolgreich an die bereitgestellten Messdaten für IGF, E2 und P4 angepasst werden. Anhand der Ergebnisse aus den Szenarien ließ sich zeigen, dass es teilweise gelingt über die metabolischen Einflussfaktoren eine negative Energiebilanz für unterernährte Kühe darzustellen. Die Rückführung in das periodische Zyklusverhalten verlief jedoch im Vergleich zu in vivo Beobachtungen zu schnell ab. Eine mögliche Erklärung hierfür ist ein zu geringer Einfluss von IGF-I auf das Modell. Darüber hinaus kam es trotz (stark) reduzierter LH-Konzentration zur Ovulation. Auf diesen Erkenntnissen aufbauend könnte in Zukunft die Follikelmodellierung modifiziert oder die Hillfunktion, die die Ovulation darstellt, überarbeitet werden.

Description: During the last few years there has been a drastic decline in the fertility of dairy cows. Therefore the goal of this work is to identify the underlying mechanisms for this problem by extending the model from Stötzel et al. (2011) to include the influence of metabolic factors. For this purpose the influence of the metabolic factors was determined based on published, experimentally obtained findings. The important metabolic factors were glucose, insulin and IGF-I, but only IGF-I was shown to be dynamic over the course of a cycle and therefore implemented into the model. To validate the chosen model extension we developed scenarios from the literature in order to simulate the impact of negative energy balance as well as the effect of diet restrictions on the bovine oestrous cycle. Furthermore we got measurement data from Kawashima et al. (2007) and Cerri et al. (2011) for IGF, E2 and P4. The new model has just 8 parameters more, while maintaining the same solvability and stability in the initial values. It was possible to fit the model with the use of NLSCON to the measurement data for IGF, E2 and P4. In addition the scenarios allowed us to show that the model is able to simulate a negative energy balance in parts. Merely the return into the cyclic behaviour was faster than observed in vivo. One possible explanation would be, that the influence of IGF-I on the model is not strong enough. The model showed a deficit while simulating the scenarios since a marked reduction of the LH concentration still led to ovulation. Thus future research could be done in this direction, where it would probably be necessary to modify the follicle function or the hill function responsible for ovulation.

Description: In this thesis, we study different modelling approaches for piecewise linear functions, in particular with respect to their occurrence in mathematical optimization problems. Reviewing the quality of the classical MIP models from the literature, we will see that all but the disaggregated convex combination method yield both sharp and locally ideal formulations. In the main part, we will present an alternative approach for modelling constraints involving piecewise linear functions, based on ideas of constraint programming and using a convex hull relaxation. For the purpose of developing a branch-and-bound procedure specifically adapted to our constraint formulation within SCIP, all required components such as propagation, branching and separation will be discussed. In particular, we will focus on adapting well-known MIP strategies for the selection of branching variables to our type of piecewise linear constraints.

Description: The discussion about sustainability and climate change as well as the energy cost perspective of network operators gives increasing attention to the energy efficiency of telecommunication networks. A promising way to improve the energy efficiency of such networks is the load-adaptive operation in which the network capacity is adjusted to the actual timevarying traffic transport needs. In this paper the concept of load-adaptive operation in the core network is explained, with the respective underlying optical network and the associated mathematical optimization. Within the DESI project a demonstrator has been realized with a commercially available WDM/OTN system. As results, concrete proven power and energy savings and the projected savings for a nationwide multilayer core network are reported.

Description: The applicability of accelerators is limited by the attainable speed-up for the offloaded computations and by the offloading overheads. While GPU programming models like CUDA and OpenCL only allow to optimise the application code and its speed-up, the available low-level APIs for the Intel Xeon Phi provide opportunity to address the overheads, too. This work presents an Heterogeneous Active Message (HAM) layer that minimises software overheads for offloading on Intel’s Xeon Phi. It provides the basis for an offload API with similar semantics as the Intel Language Extensions for Offload (LEO). In contrast to LEO, HAM works within the C++ language and needs no additional compiler support. We evaluated HAM on top of SCIF and MPI as communication backends. While the SCIF backend offers the best performance, the MPI backend allows for inter-node offloads which are not possible with other offload solutions. Benchmark results show that the cost for offloading a function call can be decreased by a factor up to 18 compared with LEO.

Description: Natural gas is one of the most important energy sources in Germany and Europe. In recent years, political regulations have led to a strict separation of gas trading and gas transport, thereby assigning a central role in energy politics to the transportation and distribution of gas. These newly imposed political requirements influenced the technical processes of gas transport in such a way that the complex task of planning and operating gas networks has become even more intricate. Mathematically, the combination of discrete decisions on the configuration of a gas transport network, the nonlinear equations describing the physics of gas, and the uncertainty in demand and supply yield large-scale and highly complex stochastic mixed-integer nonlinear optimization problems. The Matheon project "Optimization of Gas Transport" takes the key role of making available the necessary core technology to solve the mathematical optimization problems which model the topology planning and the operation of gas networks. An important aspect of the academic impact is the free availability of our framework. As a result of several years of research and development, it is now possible to download a complete state-of-the-art framework for mixed-integer linear and nonlinear programming in source code at http://scip.zib.de

Description: We investigate spectral deferred correction (SDC) methods for time stepping and their interplay with spatio-temporal adaptivity, applied to the solution of the cardiac electro-mechanical coupling model. This model consists of the Monodomain equations, a reaction-diffusion system modeling the cardiac bioelectrical activity, coupled with a quasi-static mechanical model describing the contraction and relaxation of the cardiac muscle. The numerical approximation of the cardiac electro-mechanical coupling is a challenging multiphysics problem, because it exhibits very different spatial and temporal scales. Therefore, spatio-temporal adaptivity is a promising approach to reduce the computational complexity. SDC methods are simple iterative methods for solving collocation systems. We exploit their flexibility for combining them in various ways with spatio-temporal adaptivity. The accuracy and computational complexity of the resulting methods are studied on some numerical examples.

Description: This section reviews the relation between the continuous dynamics of a molecular system in thermal equilibrium and the kinetics given by a Markov State Model (MSM). We will introduce the dynamical propagator, an error-less, alternative description of the continuous dynamics, and show how MSMs result from its discretization. This allows for an precise understanding of the approximation quality of MSMs in comparison to the continuous dynamics. The results on the approximation quality are key for the design of good MSMs. While this section is important for understanding the theory of discretization and related systematic errors, practitioners wishing only to learn how to construct MSMs may skip directly to the discussion of Markov model estimation.

Description: In this thesis we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations are combinatorial building blocks of primal solutions; they rule out the "capacity numerics" and make the problem purely combinatorial. The concept of configurations can also be adapted to other capacitated network design problems. The configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, multicover, and MIR inequalities. These theoretical findings can be confirmed in computations, however, the enormous number of configurations can blow up the formulation for large instances. We propose a mixed model that enriches the standard model by a judiciously chosen subset of configurations that provide a good compromise between model strength and size. Computational results for large-scale line planning problems are presented.

Description: Das Linienplanungsproblem ist ein wichtiges Teilproblem der Angebotsplanung im öffentlichen Nahverkehr. Dabei werden Routen und Betriebsfrequenzen von Linien in einem gegebenen Infrastrukturnetzwerk gesucht, sodass ein gegebener Beförderungsbedarf gedeckt wird und die Kosten minimal sind. Praktische Ansätze zum Lösen dieser Probleme beruhen auf ganzzahliger Programmierung. Ein Schwachpunkt klassischer Modelle ist, dass schon kleine Änderungen der Eingabeparameter eine Vergrößerung oder Verkleinerung der Menge der zulässigen fraktionalen Lösungen bewirken können, auch wenn die Menge der ganzzahligen Lösungen unverändert bleibt. Wir betrachten in dieser Arbeit einen neuen kombinatorischen Ansatz, welcher die Möglichkeiten den Bedarf auf einer Verbindung im Netzwerk mit Frequenzen zu überdecken mit Hilfe von diskreten "Konfigurationen" beschreibt und dieses Problem eliminiert. Um die Vorteile dieses Konfigurationsmodells aufzuzeigen, vergleichen wir es mit einem klassischen Ansatz, den wir Standardmodell nennen. Wir zeigen, dass das Konfigurationsmodell mehrere facettendefinierende Ungleichungen des Standardmodells impliziert: Setcover-, symmetrische Band-, Multicover- und MIR-Ungleichungen. Diese theoretischen Ergebnisse können wir mit Rechenergebnissen bestätigen. Um die Anzahl dieser Variablen auch für große Instanzen zu beschränken, schlagen wir ein weiteres Modell vor, welches nur eine Teilmenge der Konfigurationsvariablen enthält. Dieses stellt sich als ein sehr guter Kompromiss zwischen der Größe und der Stärke des Modells heraus. Da das Linienplanungsproblem eine Spezialisierung des Netzwerkdesignproblems ist, können unsere Methoden auch auf andere Problemklassen übertragen werden.

Description: Bibliotheken stehen heute mehr denn je vor der Frage, wie sie ihre Dienste attraktiv gestalten können. Da liegt es nahe, Nutzerinnen und Nutzer aktiv in den Designprozess einzubinden. Die Neuentwicklung des KOBV-Portals (http://portal.kobv.de), einer regionalen Suche über die Bestände der Bibliotheken in Berlin und Brandenburg, geht konsequent den Weg des Co-Designs. Nutzerinnen und Nutzer werden als Entwicklungspartner verstanden. Als Projektpartner wurde das Institut für Bibliotheks- und Informationswissenschaft (IBI) der Humboldt-Universität zu Berlin gewonnen.

Description: More than ever, libraries today are faced with the question of how to make their services more attractive. Thus, it only seems logical to actively integrate users into the design process. The re-implementation of the KOBV Portal (http://portal.kobv.de), a regional search in the holdings of libraries in Berlin and Brandenburg, consistently follows the path of co-design. Users are regarded as development partners. The Berlin School of Library and Information Science acts as a project partner.

Description: Kulturerbe- und Gedächtnisinstitutionen sammeln, bewahren, dokumentieren und vermitteln Zeugnisse und Objekte des kulturellen Erbes. Die Digitalisierung eröffnet für alle diese Handlungsfelder neue Möglichkeiten, aber gleichzeitig auch neue Herausforderungen. Diese berühren sowohl organisatorische und technische als auch rechtliche Aspekte. Gerade letztere sind oft mit schwer kalkulierbaren Risiken für die Kultureinrichtungen behaftet. Die vorliegende Handreichung, die von iRights im Auftrag der Servicestelle Digitalisierung des Landes Berlin (digiS) erstellt wurde, soll eine Einführung für die Mitarbeiter der Kulturinstitutionen in die Themen Urheber- und Leistungsschutzrechte sein. Sie soll für rechtliche Risiken sensibilisieren und Handlungsspielräume aufzeigen. Die ursprüngliche Version 1.0 wurde im Nachgang des Workshops der Autoren am ZIB noch einmal überarbeitet. Neu hinzugekommen sind zwei Abschnitte zu den Themen Archivkopie und elektronischer Leseplatz.

Description: Modern solving software for mixed-integer programming (MIP) incorporates numerous algorithmic components whose behavior is controlled by user parameter choices, and whose usefulness dramatically varies depending on the progress of the solving process. In this thesis, our aim is to construct a phase-based solver that dynamically reacts on phase transitions with an appropriate change of its component behavior. Therefore, we decompose the branch-and-bound solving process into three distinct phases: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP we construct a phase-based solver to make use of the phase concept in two steps: First, we identify promising components for every solving phase individually and show that their combination is beneficial on a test bed of practical MIP instances. We then present and evaluate three heuristic criteria to make use of the phase-based solver in practice, where it is infeasible to distinguish between the last two phases before the termination of the solving process.

Description: Rigorous optical simulations are an important tool in optimizing scattering properties of nano-photonic devices and are used, for example, in solar cell optimization. The finite element method (FEM) yields rigorous, time-harmonic, high accuracy solutions of the full 3D vectorial Maxwell's equations [1] and furthermore allows for great flexibility and accuracy in the geometrical modeling of these often complex shaped 3D nano-structures. A major drawback of frequency domain methods is the limitation of single frequency evaluations. For example the accurate computation of the short circuit current density of an amorphous silicon / micro-crystalline multi-junction thin film solar cell may require the solution of Maxwell's equations for over a hundred different wavelengths if an equidistant sampling strategy is employed. Also in optical metrology, wavelength scans are frequently used to reconstruct unknown geometrical and material properties of optical systems numerically from measured scatterometric data. In our contribution we present several adaptive numerical integration and sampling routines and study their efficiency in the context of the determination of generation rate profiles of solar cells. We show that these strategies lead to a reduction in the computational effort without loss of accuracy. We discuss the employment of tangential information in a Hermite interpolation scheme to achieve similar accuracy on coarser grids. We explore the usability of these strategies for scatterometry and solar cell simulations.

Description: In many experimentally realized applications, e.g. photonic crystals, solar cells and light-emitting diodes, nano-photonic systems are coupled to a thick substrate layer, which in certain cases has to be included as a part of the optical system. The finite element method (FEM) yields rigorous, high accuracy solutions of full 3D vectorial Maxwell's equations [1] and allows for great flexibility and accuracy in the geometrical modelling. Time-harmonic FEM solvers have been combined with Fourier methods in domain decomposition algorithms to compute coherent solutions of these coupled system. [2,3] The basic idea of a domain decomposition approach lies in a decomposition of the domain into smaller subdomains, separate calculations of the solutions and coupling of these solutions on adjacent subdomains. In experiments light sources are often not perfectly monochromatic and hence a comparision to simulation results might only be justified if the simulation results, which include interference patterns in the substrate, are spectrally averaged. In this contribution we present a scattering matrix domain decomposition algorithm for Maxwell's equations based on FEM. We study its convergence and advantages in the context of optical simulations of silicon thin film multi-junction solar cells. This allows for substrate light-trapping to be included in optical simulations and leads to a more realistic estimation of light path enhancement factors in thin-film devices near the band edge.

Description: The most popular molecular surface in molecular visualization is the solvent excluded surface (SES). It provides information about the accessibility of a biomolecule for a solvent molecule that is geometrically approximated by a sphere. During a period of almost four decades, the SES has served for many purposes – including visualization, analysis of molecular interactions and the study of cavities in molecular structures. However, if one is interested in the surface that is accessible to a molecule whose shape differs significantly from a sphere, a different concept is necessary. To address this problem, we generalize the definition of the SES by replacing the probe sphere with the full geometry of the ligand defined by the arrangement of its van der Waals spheres. We call the new surface ligand excluded surface (LES) and present an efficient, grid-based algorithm for its computation. Furthermore, we show that this algorithm can also be used to compute molecular cavities that could host the ligand molecule. We provide a detailed description of its implementation on CPU and GPU. Furthermore, we present a performance and convergence analysis and compare the LES for several molecules, using as ligands either water or small organic molecules.

Description: Several non-invasive methods are common practice in natural sciences today. Here we present how they can be applied and contribute to current topics in cephalopod (paleo-) biology. Different methods will be compared in terms of time necessary to acquire the data, amount of data, accuracy/resolution, minimum/maximum size of objects that can be studied, the degree of post-processing needed and availability. The main application of the methods is seen in morphometry and volumetry of cephalopod shells. In particular we present a method for precise buoyancy calculation. Therefore, cephalopod shells were scanned together with different reference bodies, an approach developed in medical sciences. It is necessary to know the volume of the reference bodies, which should have similar absorption properties like the object of interest. Exact volumes can be obtained from surface scanning. Depending on the dimensions of the study object different computed tomography techniques were applied.

Description: Connectomics is a branch of neuroscience that attempts to create a connectome, i.e., a complete map of the neuronal system and all connections between neuronal structures. This representation can be used to understand how functional brain states emerge from their underlying anatomical structures and how dysfunction and neuronal diseases arise. We review the current state-of-the-art of visualization and image processing techniques in the field of connectomics and describe a number of challenges. After a brief summary of the biological background and an overview of relevant imaging modalities, we review current techniques to extract connectivity information from image data at macro-, meso- and microscales. We also discuss data integration and neural network modeling, as well as the visualization, analysis and comparison of brain networks.

Description: Tracing microtubule centerlines in serial section electron tomography requires microtubules to be stitched across sections, that is lines from different sections need to be aligned, endpoints need to be matched at section boundaries to establish a correspondence between neighboring sections, and corresponding lines need to be connected across multiple sections. We present computational methods for these tasks: 1) An initial alignment is computed using a distance compatibility graph. 2) A fine alignment is then computed with a probabilistic variant of the iterative closest points algorithm, which we extended to handle the orientation of lines by introducing a periodic random variable to the probabilistic formulation. 3) Endpoint correspondence is established by formulating a matching problem in terms of a Markov random field and computing the best matching with belief propagation. Belief propagation is not generally guaranteed to converge to a minimum. We show how convergence can be achieved, nonetheless, with minimal manual input. In addition to stitching microtubule centerlines, the correspondence is also applied to transform and merge the electron tomograms. We applied the proposed methods to samples from the mitotic spindle in C. elegans, the meiotic spindle in X. laevis, and sub-pellicular microtubule arrays in T. brucei. The methods were able to stitch microtubules across section boundaries in good agreement with experts’ opinions for the spindle samples. Results, however, were not satisfactory for the microtubule arrays. For certain experiments, such as an analysis of the spindle, the proposed methods can replace manual expert tracing and thus enable the analysis of microtubules over long distances with reasonable manual effort.

Description: The analysis of data that captures volcanic eruptions and their atmospheric aftermath plays an important role for domain experts to gain a deeper understanding of the volcanic eruption and their consequences for atmosphere, climate and air traffic. Thereby, one major challenge is to extract and combine the essential information, which is spread over various, mostly sparse data sources. This requires a careful integration of each data set with its strength and limitations. The sparse, but more reliable measurement data is mainly used to calibrate the more dense simulation data. This work combines a collection of visualization approaches into an exploitative framework. The goal is to support the domain experts to build a complete picture of the situation. But it is also important to understand the individual data sources, the wealth of their information and the quality of the simulation results. All presented methods are designed for direct interaction with the data from different perspectives rather than the sole generation of some final images.

Description: Biological tissues achieve a wide range of properties and function, however with limited components. The organization of these constituent parts is a decisive factor in the impressive properties of biological materials, with tissues often exhibiting complex arrangements of hard and soft materials. The “tessellated” cartilage of the endoskeleton of sharks and rays, for example, is a natural composite of mineralized polygonal tiles (tesserae), collagen fiber bundles, and unmineralized cartilage, resulting in a material that is both flexible and strong, with optimal stiffness. The properties of the materials and the tiling geometry are vital to the growth and mechanics of the system, but had not been investigated due to the technical challenges involved. We use high-resolution materials characterization techniques (qBEI, µCT) to show that tesserae exhibit great variability in mineral density, supporting theories of accretive growth mechanisms. We present a developmental series of tesserae and outline the development of unique structural features that appear to function in load bearing and energy dissipation, with some structural features far exceeding cortical bone’s mineral content and tissue stiffness. To examine interactions among tesserae, we developed an advanced tiling-recognition-algorithm to semi-automatically detect and isolate individual tiles in microCT scans of tesseral mats. The method allows quantification of shape variation across a wide area, allowing localization of regions of high/low reinforcement or flexibility in the skeleton. The combination of our material characterization and visualization techniques allows the first quantitative 3d description of anatomy and material properties of tesserae and the organization of tesseral networks in elasmobranch mineralized cartilage, providing insight into form-function relationships of the repeating tiled pattern. We aim to combine detailed knowledge of intra-tesseral morphology and mineralization to model the relationships of tesseral shapes and skeletal surface curvature, to understand fundamental tiling laws important for complex, mechanically loaded 3d objects.

Description: Granular filters in hydraulically loaded earth structures constitute the ultimate barrier for the blockage of small particles moving through the structure regularly or along concentrated leaks. If filters are inefficient to block small particles several types of internal erosion may be initiated. A corresponding phenomenon appears during suffusion in a wide graded hydraulically loaded fill, when fine particles, embedded in the pore structure of a soil skeleton, are washed out. The cumulative constriction size distribution (CSD) is physically the key property that qualifies the soils retention capability as like a spatial acting sieve. Constrictions are defined as the narrowest sections of channels between larger volumes (pores) within the pore network of granular material and they are the main obstacles for a small particle to overcome when flowing along pathways. At least three different approaches are available to determine and compute the CSD, i.e. experimental, numerical and analytical methods. The purpose of this review is to present and discuss these methods pointing out their limits, advantages and significance related to internal erosion phenomena.

Description: This paper presents an algorithm called surfseek for selecting surfaces on the most visible features in direct volume rendering (DVR). The algorithm is based on a previously published technique (WYSIWYP) for picking 3D locations in DVR. The new algorithm projects a surface patch on the DVR image, consisting of multiple rays. For each ray the algorithm uses WYSIWYP or a variant of it to find the candidates for the most visible locations along the ray. Using these candidates the algorithm constructs a graph and computes a minimum cut on this graph. The minimum cut represents a very visible but relatively smooth surface. In the last step the selected surface is displayed. We provide examples for the results in real-world dataset as well as in artificially generated datasets.

Description: Kurzfassung. Durch die Alkalität des Betons wird Betonstahl dauerhaft vor Korrosion geschützt. Infolge von Chlorideintrag kann dieser Schutz nicht länger aufrechterhalten werden und führt zu Lochkorrosion. Die zerstörungsfreie Prüfung von Stahlbetonproben mit 3D-CT bietet die Möglichkeit, eine Probe mehrfach gezielt vorzuschädigen und den Korrosionsfortschritt zu untersuchen. Zur Quantifizierung des Schädigungsgrades müssen die bei dieser Untersuchung anfallenden großen Bilddaten mit Bildverarbeitungsmethoden ausgewertet werden. Ein wesentlicher Schritt dabei ist die Segmentierung der Bilddaten, bei der zwischen Korrosionsprodukt (Rost), Betonstahl (BSt), Beton, Rissen, Poren und Umgebung unterschieden werden muss. Diese Segmentierung bildet die Grundlage für statistische Untersuchungen des Schädigungsfortschritts. Hierbei sind die Änderung der BSt-Geometrie, die Zunahme von Korrosionsprodukten und deren Veränderung über die Zeit sowie ihrer räumlichen Verteilung in der Probe von Interesse. Aufgrund der Größe der CT-Bilddaten ist eine manuelle Segmentierung nicht durchführbar, so dass automatische Verfahren unabdingbar sind. Dabei ist insbesondere die Segmentierung der Korrosionsprodukte in den Bilddaten ein schwieriges Problem. Allein aufgrund der Grauwerte ist eine Zuordnung nahezu unmöglich, denn die Grauwerte von Beton und Korrosionsprodukt unterscheiden sich kaum. Eine formbasierte Suche ist nicht offensichtlich, da die Korrosionsprodukte in Beton diffuse Formen haben. Allerdings lässt sich Vorwissen über die Ausbreitung der Korrosionsprodukte nutzen. Sie bilden sich in räumlicher Nähe des BSt (in Bereichen vorheriger Volumenabnahme des BSt), entlang von Rissen sowie in Porenräumen, die direkt am BSt und in dessen Nahbereich liegen. Davon ausgehend wird vor der Korrosionsprodukterkennung zunächst eine BSt-Volumen-, Riss- und Porenerkennung durchgeführt. Dieser in der Arbeit näher beschriebene Schritt erlaubt es, halbautomatisch Startpunkte (Seed Points) für die Korrosionsprodukterkennung zu finden. Weiterhin werden verschiedene in der Bildverarbeitung bekannte Algorithmen auf ihre Eignung untersucht werden.

Description: Several non-invasive methods are common practice in natural sciences today. Here we present how they can be applied and contribute to current topics in cephalopod (paleo-) biology. Different methods will be compared in terms of time necessary to acquire the data, amount of data, accuracy/resolution, minimum/maximum size of objects that can be studied, the degree of post-processing needed and availability. The main application of the methods is seen in morphometry and volumetry of cephalopod shells. In particular we present a method for precise buoyancy calculation. Therefore, cephalopod shells were scanned together with different reference bodies, an approach developed in medical sciences. It is necessary to know the volume of the reference bodies, which should have similar absorption properties like the object of interest. Exact volumes can be obtained from surface scanning. Depending on the dimensions of the study object different computed tomography techniques were applied.

Description: Information about the temporal bone size and variations of anatomical structures are crucial for a safe positioning of the Vibrant Bonebridge B-FMT. A radiological based preoperative planning of the surgical procedure decreases the surgical time and minimizes the risk of complications. We developed a software tool, which allows a catch up of foreign DICOM data based CT temporal bone scans. The individual CT scan is transmitted into a 3D reconstructed pattern of the temporal bone. In this 3D reconstruction the individually favored position of the B- FMT should be found. The software allows a determination of a safe B-FMT position by identifying the individual relation of middle fossa, jugular bulb and external auditory canal. Skull thickness and screw length are contained parameters for the surgical planning. An easy to handle software tool allows a radiologically data based safe and fast surgical positioning of the B-FMT.

Description: It has been recently suggested that mechanical loads applied at frequencies close to the natural frequencies of bone could enhance bone apposition due to the resonance phenomenon. Other applications of bone modal analysis are also suggested. For the above-mentioned applications, it is important to understand how patient-specific bone shape and density distribution influence the natural frequencies of bones. We used finite element models to study the effects of bone shape and density distribution on the natural frequencies of the femur in free boundary conditions. A statistical shape and appearance model that describes shape and density distribution independently was created, based on a training set of 27 femora. The natural frequencies were then calculated for different shape modes varied around the mean shape while keeping the mean density distribution, for different appearance modes around the mean density distribution while keeping the mean bone shape, and for the 27 training femora. Single shape or appearance modes could cause up to 15% variations in the natural frequencies with certain modes having the greatest impact. For the actual femora, shape and density distribution changed the natural frequencies by up to 38%. First appearance mode that describes the general cortical bone thickness and trabecular bone density had one of the strongest impacts. The first appearance mode could therefore provide a sensitive measure of general bone health and disease progression. Since shape and density could cause large variations in the calculated natural frequencies, patient-specific FE models are needed for accurate estimation of bone natural frequencies.

Description: Die Positionierung des B-FMT der Vibrant Bonebridge kann aufgrund der anatomischen Verhältnisse des Mastoids und der Größe des Aktuators ohne eine vorherige Beurteilung der individuellen Computertomographie (CT) des Felsenbeins problematisch sein. Die Entwicklung eines einfach zu bedienenden Viewers, welcher eine Positionierung des B-FMT im Felsenbeinmodell ermöglicht und hier auf individuelle potenzielle anatomische Konflikte hinweist sowie Lösungsmöglichkeiten anbietet, kann ein hilfreiches Werkzeug zur präoperativen Positionierung sein. Ziel der Arbeit war die Definition von Anforderungen und die Anfertigung eines Prototyps eines Vibrant-Bonebridge-Viewers. Auf der Basis einer ZIBAmira-Software-Version und der Inklusion eines B-FMT-Modells unter Erstellung eines Felsenbeinmodells, welches die intuitive Beurteilung von Konflikten ermöglicht, erfolgte die Erstellung des Prototyps eines Vibrant-Bonebridge-Viewers.Ergebnisse. Die Segmentierungszeit der individuellen DICOM-Daten („digital imaging and communications in medicine“) beträgt etwa 5 min. Eine Positionierung im individuellen 3-D-Felsenbeinmodell ermöglicht die quantitative und qualitative Beurteilung von Konflikten (Sinus sigmoideus, mittlere Schädelgrube) und das Aufsuchen einer bevorzugten Position. Das Anheben des B-FMT mittels virtueller Unterlegscheiben kann simuliert werden. Der erstellte Vibrant-Bonebridge-Viewer ermöglicht verlässlich eine Simulation der B-FMT-Positionierung. Die klinische Anwendbarkeit muss evaluiert werden.

Description: Field lines in vector fields, e.g. stream lines, path lines, streak lines or time lines, play an important role in the analysis of vector fields. They improve the classification of flow features and its characteristics in particular. Because of the variety of structural information in field lines the effective processing, analysis and visualization play an important role. More effective techniques may contribute to an improved understanding of struc- tural phenomena in a wide range of applications of vector field visualization, such as gaseous flow (e.g. development of cars and aircrafts), design of machines (e.g. turbines), chemistry (e.g. simulation of molecules) and fluid flow in technical or medical applications (e.g. bloodvessel and ocean simulations). This master thesis focuses on the histogram-based visualization and analysis of vec- tor fields using field line projection plots, stream lines in particular. The goal of this work is to develop a hand full of selection criteria to answer specific applica- tion relevant questions about the characteristics and structures of their vector fields. Therefore we present a powerful analysis tool for vector fields or more precisely for their field lines.

Description: Hunterian ligation affecting hemodynamics in vessels was proposed to avoid rebleeding in a case of a fenestrated basilar artery aneurysm after incomplete coil occlusion. We studied the hemodynamics in vitro to predict the hemodynamic changes near the aneurysm remnant caused by Hunterian ligation. A transparent model was fabricated based on three-dimensional rotational angiography imaging. Arteries were segmented and reconstructed. Pulsatile flow in the artery segments near the partially occluded (coiled) aneurysm was investigated by means of particle image velocimetry. The hemodynamic situation was investigated before and after Hunterian ligation of either the left or the right vertebral artery (LVA/RVA). Since post-ligation flow rate in the basilar artery was unknown, reduced and retained flow rates were simulated for both ligation options. Flow in the RVA and in the corresponding fenestra vessel is characterized by a vortex at the vertebrobasilar junction, whereas the LVA exhibits undisturbed laminar flow. Both options (RVA or LVA ligation) cause a significant flow reduction near the aneurysm remnant with a retained flow rate. The impact of RVA ligation is, however, significantly higher. This in vitro case study shows that flow reduction near the aneurysm remnant can be achieved by Hunterian ligation and that this effect depends largely on the selection of the ligated vessel. Thus the ability of the proposed in vitro pipe-line to improve hemodynamic impact of the proposed therapy was successfully proved.

Description: The most popular molecular surface in molecular visualization is the solvent excluded surface (SES). It provides information about the accessibility of a biomolecule for a solvent molecule that is geometrically approximated by a sphere. During a period of almost four decades, the SES has served for many purposes – including visualization, analysis of molecular interactions and the study of cavities in molecular structures. However, if one is interested in the surface that is accessible to a molecule whose shape differs significantly from a sphere, a different concept is necessary. To address this problem, we generalize the definition of the SES by replacing the probe sphere with the full geometry of the ligand defined by the arrangement of its van der Waals spheres. We call the new surface ligand excluded surface (LES) and present an efficient, grid-based algorithm for its computation. Furthermore, we show that this algorithm can also be used to compute molecular cavities that could host the ligand molecule. We provide a detailed description of its implementation on CPU and GPU. Furthermore, we present a performance and convergence analysis and compare the LES for several molecules, using as ligands either water or small organic molecules.

Description: The authors report on the first experiences with the prototype of a surgical tool for cranial remodeling. The device enables the surgeon to transfer statistical information, represented in a model, into the disfigured bone. The model is derived from a currently evolving databank of normal head shapes. Ultimately, the databank will provide a set of standard models covering the statistical range of normal head shapes, thus providing the required template for any standard remodeling procedure as well as customized models for intended overcorrection. To date, this technique has been used in the surgical treatment of 14 infants (age range 6-12 months) with craniosynostosis. In all 14 cases, the designated esthetic result, embodied by the selected model, has been achieved, without morbidity or mortality. Frame-based reconstruction provides the required tools to precisely realize the surgical reproduction of the model shape. It enables the establishment of a self-referring system, feeding back postoperative growth patterns, recorded by 3D follow-up, into the model design.

Description: This paper presents an algorithm called surfseek for selecting surfaces on the most visible features in direct volume rendering (DVR). The algorithm is based on a previously published technique (WYSIWYP) for picking 3D locations in DVR. The new algorithm projects a surface patch on the DVR image, consisting of multiple rays. For each ray the algorithm uses WYSIWYP or a variant of it to find the candidates for the most visible locations along the ray. Using these candidates the algorithm constructs a graph and computes a minimum cut on this graph. The minimum cut represents a visible and typically rather smooth surface. In the last step the selected surface is displayed. We provide examples for results using artificially generated and real-world data sets.

Description: The goal of visualization is to effectively and accurately communicate data. Visualization research has often overlooked the errors and uncertainty which accompany the scientific process and describe key characteristics used to fully understand the data. The lack of these representations can be attributed, in part, to the inherent difficulty in defining, characterizing, and controlling this uncertainty, and in part, to the difficulty in including additional visual metaphors in a well designed, potent display. However, the exclusion of this information cripples the use of visualization as a decision making tool due to the fact that the display is no longer a true representation of the data. This systematic omission of uncertainty commands fundamental research within the visualization community to address, integrate, and expect uncertainty information. In this chapter, we outline sources and models of uncertainty, give an overview of the state-of-the-art, provide general guidelines, outline small exemplary applications, and finally, discuss open problems in uncertainty visualization.

Description: We propose a scheme for animating deformable objects based on spacetime optimization. The main feature is that it robustly and quickly (within a few seconds) generates interesting motion from a sparse set of spacetime constraints. Providing only partial (as opposed to full) keyframes for positions and velocities is sufficient. The computed motion satisfies the constraints and the remaining degrees of freedom are determined by physical principles using elasticity and the spacetime constraints paradigm. Our modeling of the spacetime optimization problem combines dimensional reduction, modal coordinates, wiggly splines, and rotation strain warping. Controlling the warped motion requires the derivative of the warp map. We derive a representation of the derivative that can be efficiently and robustly evaluated. Our solver is based on a theorem that characterizes the solutions of the optimization problem and allows us to restrict the optimization to very low-dimensional search spaces. This treatment of the optimization problem avoids a time discretization and the resulting method can robustly deal with sparse input and wiggly motion.

Description: Rays and sharks are cartilaginous fishes. Most of the cartilaginous skeleton is covered with calcified tiles to improve the stability of the skeleton. These tiles are called tesserae and enclose areas of uncalcified cartilage. Because of the special properties of the tesserae, biologists are interested to understand shape and structure of tessellated cartilage. This thesis presents a segmentation pipeline for the separation of tesserae on the cartilaginous skeleton of rays and sharks. The segmentation pipeline consists of an automatic initial segmentation step followed by manual error corrections by the user. The initial segmentation is based on the contour tree data structure that tracks the evolution of level sets in a dataset during iso-value changes. The presented segmentation concepts are not limited to the segmentation of tesserae but also viable for similar kinds of tiled structures. The input datasets are given as micro-CT scans. The contribution of this thesis is the development of a segmentation pipeline. The pipeline uses a newly developed fast version of the contour-tree-based segmentation algorithm that, after a preprocessing step, does not need to iterate over all voxels in the dataset. Visualizations and computations are done with the software system ZIBAmira. Used algorithms are either implemented as new ZIBAmira modules or they extend already existing ZIBAmira modules.

Description: This thesis concerns model reduction techniques for the efficient numerical treatment of physical systems governing the deformation behavior of geometrically complex shapes. We present new strategies for the construction of simplified, low-dimensional models that capture the main features of the original complex system and are suitable for use in interactive computer graphics applications. To demonstrate the effectiveness of the new techniques we propose frameworks for real-time simulation and interactive deformation-based modeling of elastic solids and shells and compare them to alternative approaches. In addition, we investigate differential operators that are derived from the physical models and hence can serve as alternatives to the Laplace-Beltrami operator for applications in modal shape analysis. Furthermore, this thesis addresses the compression of digital shapes. In particular, we present a lossless compression scheme that is adapted to the special characteristics of adaptively refined, hierarchical meshes.

Description: Sensory-evoked signal flow, at cellular and network levels, is primarily determined by the synaptic wiring of the underlying neuronal circuitry. Measurements of synaptic innervation, connection probabilities and sub-cellular organization of synaptic inputs are thus among the most active fields of research in contemporary neuroscience. Methods to measure these quantities range from electrophysiological recordings over reconstructions of dendrite-axon overlap at light-microscopic levels to dense circuit reconstructions of small volumes at electron-microscopic resolution. However, quantitative and complete measurements at subcellular resolution and mesoscopic scales to obtain all local and long-range synaptic in/outputs for any neuron within an entire brain region are beyond present methodological limits. Here, we present a novel concept, implemented within an interactive software environment called NeuroNet, which allows (i) integration of sparsely sampled (sub)cellular morphological data into an accurate anatomical reference frame of the brain region(s) of interest, (ii) up-scaling to generate an average dense model of the neuronal circuitry within the respective brain region(s) and (iii) statistical measurements of synaptic innervation between all neurons within the model. We illustrate our approach by generating a dense average model of the entire rat vibrissal cortex, providing the required anatomical data, and illustrate how to measure synaptic innervation statistically. Comparing our results with data from paired recordings in vitro and in vivo, as well as with reconstructions of synaptic contact sites at light- and electron-microscopic levels, we find that our in silico measurements are in line with previous results.