Library

Description: We prove a mathematical programming characterisation of approximate partial D-optimality under general linear constraints. We use this characterisation with a branch-and-bound method to compute a list of all exact D-optimal designs for estimating a pair of treatment contrasts in the presence of a nuisance time trend up to the size of 24 consecutive trials.

Description: One quarter of Europe’s energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology extension problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. In this article we offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speed-up for the necessary computations.

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 derive a feasibility condition for path capacities supporting such direct connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows. The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers.

Description: Markov State Modelling as a concept for a coarse grained description of the essential kinetics of a molecular system in equilibrium has gained a lot of atten- tion recently. The last 10 years have seen an ever increasing publication activity on how to construct Markov State Models (MSMs) for very different molecular systems ranging from peptides to proteins, from RNA to DNA, and via molecu- lar sensors to molecular aggregation. Simultaneously the accompanying theory behind MSM building and approximation quality has been developed well be- yond the concepts and ideas used in practical applications. This article reviews the main theoretical results, provides links to crucial new developments, outlines the full power of MSM building today, and discusses the essential limitations still to overcome.

Description: We present a comprehensive theory for analysis and understanding of transition events between an initial set A and a target set B for general ergodic finite-state space Markov chains or jump processes, including random walks on networks as they occur, e.g., in Markov State Modelling in molecular dynamics. The theory allows us to decompose the probability flow generated by transition events between the sets A and B into the productive part that directly flows from A to B through reaction pathways and the unproductive part that runs in loops and is supported on cycles of the underlying network. It applies to random walks on directed networks and nonreversible Markov processes and can be seen as an extension of Transition Path Theory. Information on reaction pathways and unproductive cycles results from the stochastic cycle decomposition of the underlying network which also allows to compute their corresponding weight, thus characterizing completely which structure is used how often in transition events. The new theory is illustrated by an application to a Markov State Model resulting from weakly damped Langevin dynamics where the unproductive cycles are associated with periodic orbits of the underlying Hamiltonian dynamics.

Description: Model-based optimal design of experiments (M-bODE) is a crucial step in model parametrization since it encloses a framework that maximizes the amount of information extracted from a battery of lab experiments. We address the design of M-bODE for dynamic models considering a continuous representation of the design. We use Semidefinite Programming (SDP) to derive robust minmax formulations for nonlinear models, and extend the formulations to other criteria. The approaches are demonstrated for a CSTR where a two-step reaction occurs.

Description: This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 % on affected instances while not degrading the performance on the remaining problems.

Description: Background. The chemical master equation is the fundamental equation of stochastic chemical kinetics. This differential-difference equation describes temporal evolution of the probability density function for states of a chemical system. A state of the system, usually encoded as a vector, represents the number of entities or copy numbers of interacting species, which are changing according to a list of possible reactions. It is often the case, especially when the state vector is high-dimensional, that the number of possible states the system may occupy is too large to be handled computationally. One way to get around this problem is to consider only those states that are associated with probabilities that are greater than a certain threshold level. Results. We introduce an algorithm that significantly reduces computational resources and is especially powerful when dealing with multi-modal distributions. The algorithm is built according to two key principles. Firstly, when performing time integration, the algorithm keeps track of the subset of states with significant probabilities (essential support). Secondly, the probability distribution that solves the equation is parametrised with a small number of coefficients using collocation on Gaussian radial basis functions. The system of basis functions is chosen in such a way that the solution is approximated only on the essential support instead of the whole state space. Discussion. In order to demonstrate the effectiveness of the method, we consider four application examples: a) the self-regulating gene model, b) the 2-dimensional bistable toggle switch, c) a generalisation of the bistable switch to a 3-dimensional tristable problem, and d) a 3-dimensional cell differentiation model that, depending on parameter values, may operate in bistable or tristable modes. In all multidimensional examples the manifold containing the system states with significant probabilities undergoes drastic transformations over time. This fact makes the examples especially challenging for numerical methods. Conclusions. The proposed method is a new numerical approach permitting to approximately solve a wide range of problems that have been hard to tackle until now. A full representation of multi-dimensional distributions is recovered. The method is especially attractive when dealing with models that yield solutions of a complex structure, for instance, featuring multi-stability. Electronic version: http://www.biomedcentral.com/1752-0509/9/67

Description: In this article we present a new idea for approximating exit rates for diffusion processes living in a craggy landscape. We are especially interested in the exit rates of a process living in a metastable regions. Due to the fact that Monte Carlo simulations perform quite poor and are very computational expensive in this setting we create several similar situations with a smoothed potential. For this we introduce a new parameter $\lambda \in [0,1]$ ($\lambda = 1$ very smoothed potential, $\lambda=0$ original potential) into the potential which controls the influence the smoothing. We then sample the exit rate for different parameters $\lambda$ the exit rate from a given region. Due to the fact that $\lambda$ is connected to the exit rate we can use this dependency to approximate the real exit rate. The method can be seen as something between hyperdynamics and temperature accelerated MC.

Description: The task of periodic timetabling is to schedule the trips in a public transport system by determining arrival and departure times at every station such that travel and transfer times are minimized. To date, the optimization literature generally assumes that passengers do not respond to changes in the timetable, i.e., the passenger routes are fixed. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We show that different routing models have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. to different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems.

Description: Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: 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 demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice.

Description: We investigate the 3-architecture Connected Facility Location Problem arising in the design of urban telecommunication access networks integrating wired and wireless technologies. We propose an original optimization model for the problem that includes additional variables and constraints to take into account wireless signal coverage represented through signal-to-interference ratios. Since the problem can prove very challenging even for modern state-of-the art optimization solvers, we propose to solve it by an original primal heuristic that combines a probabilistic fixing procedure, guided by peculiar Linear Programming relaxations, with an exact MIP heuristic, based on a very large neighborhood search. Computational experiments on a set of realistic instances show that our heuristic can find solutions associated with much lower optimality gaps than a state-of-the-art solver.

Description: Markov State Modelling as a concept for a coarse grained description of the essential kinetics of a molecular system in equilibrium has gained a lot of atten- tion recently. The last 10 years have seen an ever increasing publication activity on how to construct Markov State Models (MSMs) for very different molecular systems ranging from peptides to proteins, from RNA to DNA, and via molecu- lar sensors to molecular aggregation. Simultaneously the accompanying theory behind MSM building and approximation quality has been developed well be- yond the concepts and ideas used in practical applications. This article reviews the main theoretical results, provides links to crucial new developments, outlines the full power of MSM building today, and discusses the essential limitations still to overcome.

Description: A commercial aircraft cannot freely use the available airspace but instead has to stick to a three-dimensional network of segments similar to a car in a road network. In this network it faces several variable and interdependent costs in the form of travel time, fuel consumption and overflight charges. These are also highly dependent on other factors such as weather conditions, aircraft performance, take-off time and weight as well as the changing availability of elements in the graph. This is further complicated by the distinction of separate flight phases that challenge the standard notion of a graph with predetermined nodes and arcs. Therefore when trying to find either a distance, fuel, time or cost minimal trajectory for a specific aircraft between an origin and a destination airport, one faces a very complex shortest path problem in the airway network graph that even for strong implifications is often NP-hard. This thesis will focus on exploring the costs that occur in this graph and that are associated with the aircraft performance. Here we will rely on actual performance and weather data supplied by Lufthansa Systems AG in Frankfurt and analyze whether they meet the requirements necessary for common algorithms such as the First-in, First-out property. Since it is vital for any shortest path algorithm to have a fast and accurate way of determining the costs in the graph, we will face two problems regarding the calculation of aircraft performance during cruise as well as the calculation of the so-called air distance. So far these problems have been approached by the industry with rudimentary approximative methods. We will reformulate them as initial value problems and try to find good approximations using both general Runge-Kutta methods as well as a novel approach which relies on finding piecewise linear approximations of some primitive integrals in pre-processing. Computations will show that these approaches deliver fast and accurate results.

Description: We propose a new Robust Optimization method for the energy offering problem of a price-taker generating company that wants to build offering curves for its generation units, in order to maximize its profit while taking into account the uncertainty of market price. Our investigations have been motivated by a critique to another Robust Optimization method, which entails the solution of a sequence of robust optimization problems imposing full protection and defined over a sequence of nested subintervals of market prices: this method presents a number of issues that may severely limit its application and computational efficiency in practice and that may expose a company to the risk of presenting offering curves resulting into suboptimal or even infeasible accepted offers. To tackle all such issues, our method provides for solving one single robust counterpart, considering an intermediate level of protection between null and full protection, and to make energy offers at zero price, practically eliminating the risk of non-acceptance. Computational results on instances provided by our industrial partners show that our new method is able to grant a great improvement in profit.

Description: In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.

Description: Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.

Description: This thesis investigates the shortest path problem with pair constraints or the pair constraint problem (PCP) for short. We consider two types of pair constraints, namely forbidden pairs and binding pairs consisting of two distinct vertices each. A path respects a forbidden pair if it uses at most one of the two vertices and it respects a binding pair (x,y) if it uses also y, if x is used. Within this thesis, we bring together and compare several formulations and variants of the pair constraint problem and their complexities. We also collect existing recursive algorithms and present their running times. Most of the presented contributions only consider forbidden pairs. We introduce a new recursive algorithm also handling binding pairs and prove its theoretical complexity of O(n^4). We implemented the algorithm and tested it on real-world instances provided by Lufthansa Systems AG. Therefore we needed to develop a heuristic translating the real-world data into an instance of the shortest path problem with pair constraints. This heuristic is presented as well as all computational results. In Chapter 4, we start investigating the associated polytope of an integer program formulation of the shortest path problem with pair constraints. For the case of one forbidden or binding pair, we find a complete linear description of the associated polytope. We prove that the number of facets grows exponentially in |V| even in these simple cases. However, separation is still possible in polynomial time. The complete linear description can be extended to the case of contiguously disjoint pairs.

Description: The resource constrained assignment problem (RCAP) is to find a minimal cost partition of the nodes of a directed graph into cycles such that a resource constraint is fulfilled. The RCAP has its roots in rolling stock rotation optimization where a railway timetable has to be covered by rotations, i.e., cycles. In that context, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes variants of the vehicle routing problem (VRP). The paper contributes an exact branch and bound algorithm for the RCAP and, primarily, a straightforward algorithmic concept that we call regional search (RS). As a symbiosis of a local and a global search algorithm, the result of an RS is a local optimum for a combinatorial optimization problem. In addition, the local optimum must be globally optimal as well if an instance of a problem relaxation is computed. In order to present the idea for a standardized setup we introduce an RS for binary programs. But the proper contribution of the paper is an RS that turns the Hungarian method into a powerful heuristic for the resource constrained assignment problem by utilizing the exact branch and bound. We present computational results for RCAP instances from an industrial cooperation with Deutsche Bahn Fernverkehr AG as well as for VRP instances from the literature. The results show that our RS provides a solution quality of 1.4 % average gap w.r.t. the best known solutions of a large test set. In addition, our branch and bound algorithm can solve many RCAP instances to proven optimality, e.g., almost all asymmetric traveling salesman and capacitated vehicle routing problems that we consider.

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 von 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 bisherige Version 1.1 aus dem letzten Jahr wurde nun überarbeitet.

Description: Spawned by practical applications, numerous variations of the classical Steiner tree problem in graphs have been studied during the last decades. Despite the strong relationship between the different variants, solution approaches employed so far have been prevalently problem-specific. In contrast, we pursue a general-purpose strategy resulting in a solver able to solve both the classical Steiner tree problem and ten of its variants without modification. These variants include well-known problems such as the prize-collecting Steiner tree problem, the maximum-weight connected subgraph problem or the rectilinear minimum Steiner tree problem. Bolstered by a variety of new methods, most notably reduction techniques, our solver is not only of unprecedented versatility, but furthermore competitive or even superior to specialized state-of-the-art programs for several Steiner problem variants.

Description: Der KOBV-Jahresbericht informiert rückblickend im 2-Jahres-Rhythmus über die bibliothekarisch-fachlichen Entwicklungen im Verbund und die Projekte des Kooperativen Bibliotheksverbunds Berlin-Brandenburg (KOBV).

Description: For the solution of optimal control problems governed by nonlinear parabolic PDEs, methods working on the reduced objective functional are often employed to avoid a full spatio-temporal discretization of the problem. The evaluation of the reduced gradient requires one solve of the state equation forward in time, and one backward solve of the ad-joint equation. The state enters into the adjoint equation, requiring the storage of a full 4D data set. If Newton-CG methods are used, two additional trajectories have to be stored. To get numerical results which are accurate enough, in many case very fine discretizations in time and space are necessary, which leads to a significant amount of data to be stored and transmitted to mass storage. Lossy compression methods were developed to overcome the storage problem by reducing the accuracy of the stored trajectories. The inexact data induces errors in the reduced gradient and reduced Hessian. In this paper, we analyze the influence of such a lossy trajectory compression method on Newton-CG methods for optimal control of parabolic PDEs and design an adaptive strategy for choosing appropriate quantization tolerances.

Description: We present a novel heuristic to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point of a nonlinear relaxation. Based on the information from the KKT point we alter some of the binary variables in a locally promising way exploiting our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP.

Description: The problem of decomposing networks into modules (or clusters) has gained much attention in recent years, as it can account for a coarsegrained description of complex systems, often revealing functional subunits of these systems. A variety of module detection algorithms have been proposed, mostly oriented towards finding hard partitionings of undirected networks. Despite the increasing number of fuzzy clustering methods for directed networks, many of these approaches tend to neglect important directional information. In this paper, we present a novel random walk based approach for finding fuzzy partitions of directed, weighted networks, where edge directions play a crucial role in defining how well nodes in a module are interconnected. We will show that cycle decomposition of a random walk process connects the notion of network modules and information transport in a network, leading to a new, symmetric measure of node communication. Finally, we will use this measure to introduce a communication graph, for which we will show that although being undirected it inherits all necessary information about modular structures from the original network.

Description: The S-Bahn Challenge in Berlin is a challenge in which one has to travel the entire S-Bahn network of Berlin in the shortest possible time. We explain how the problem can be modeled and solved mathematically. Furthermore, we report on our record attempt on January 10, 2015.

Description: Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway cus- tomers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain devel- oping mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice, with a few notable exceptions. In this paper we address three success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will dis- cuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that math- ematical optimization can support the planning of rolling stock resources. Thus, mathematical models and optimization can lead to a greater effi- ciency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.

Description: We propose a composite step method, designed for equality constrained optimization with partial differential equations. Focus is laid on the construction of a globalization scheme, which is based on cubic regularization of the objective and an affine covariant damped Newton method for feasibility. We show finite termination of the inner loop and fast local convergence of the algorithm. We discuss preconditioning strategies for the iterative solution of the arising linear systems with projected conjugate gradient. Numerical results are shown for optimal control problems subject to a nonlinear heat equation and subject to nonlinear elastic equations arising from an implant design problem in craniofacial surgery.

Description: We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.

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. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of arcs to be controlled. 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 (SSE) is more relevant for this problem and we give a mixed integer programming (MIP) formulation for this problem. We show that the computation of such an equilibrium is NP-hard. More generally, we prove that it is NP-hard to compute a SSE in a polymatrix game, even if the game is pairwise zero-sum. Then, we give some bounds on the price of spite, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we report computational experiments on instances constructed from real data, for an application to the enforcement of a truck toll in Germany. These numerical results show the efficiency of the proposed methods, as well as the quality of the bounds derived in this article.

Description: In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.

Description: Cardiovascular diseases are one of the major problems in medicine today and the number of patients increases worldwide. To find the most efficient treatment, prior knowledge about function and dysfunction of the cardiovas- cular system is required and methods need to be developed that identify the disease in an early stage. Mathematical modeling is a powerful tool for prediction and investigation of cardiovascular diseases. It has been shown that the Windkessel model, being based on an analogy between electrical circuits and fluid flow, is a simple but effective method to model the human cardiovascular system. In this paper, we have applied parametric local sensitivity analysis (LSA) to a linear elastic model of the arm arteries, to find and rank sensitive param- eters that may be helpful in clinical diagnosis. A computational model for end-to-side anastomosis (superior ulnar collateral anastomosis with posterior ulnar recurrent, SUC-PUR) is carried out to study the effects of some clinically relevant haemodynamic parameters like blood flow resistance and terminal re- sistance on pressure and flow at different locations of the arm artery. In this context, we also discuss the spatio-temporal dependency of local sensitivities. The sensitivities with respect to cardiovascular parameters reveal the flow resistance and diameter of the vessels as most sensitive parameters. These parameters play a key role in diagnosis of severe stenosis and aneurysms. In contrast, wall thickness and elastic modulus are found to be less sensitive.

Description: The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong branching until variables are considered reliable. The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains. We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a specialized version of a two-sample Student’s t -test for filtering branching candidates with a high probability to be better than the best history candidate. Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented.

Description: The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong-branching until variables are considered reliable. The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains. We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong-branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a two-sample Student-t test for filtering branching candidates with a high probability to be better than the best history candidate. Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented.

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 derive a feasibility condition for path capacities supporting such direct connection flows similar to the well-known feasibility condition for arc capacities in ordinary multi-commodity flows. The condition can be expressed in terms of a class of metric inequalities for routings on direct connections. We illustrate the concept on the example of the line planning problem in public transport and present an application to large-scale real-world problems.

Description: Wireless body area networks are wireless sensor networks whose adoption has recently emerged and spread in important healthcare applications, such as the remote monitoring of health conditions of patients. A major issue associated with the deployment of such networks is represented by energy consumption: in general, the batteries of the sensors cannot be easily replaced and recharged, so containing the usage of energy by a rational design of the network and of the routing is crucial. Another issue is represented by traffic uncertainty: body sensors may produce data at a variable rate that is not exactly known in advance, for example because the generation of data is event-driven. Neglecting traffic uncertainty may lead to wrong design and routing decisions, which may compromise the functionality of the network and have very bad effects on the health of the patients. In order to address these issues, in this work we propose the first robust optimization model for jointly optimizing the topology and the routing in body area networks under traffic uncertainty. Since the problem may result challenging even for a state-of-the-art optimization solver, we propose an original optimization algorithm that exploits suitable linear relaxations to guide a randomized fixing of the variables, supported by an exact large variable neighborhood search. Experiments on realistic instances indicate that our algorithm performs better than a state-of-the-art solver, fast producing solutions associated with improved optimality gaps.

Description: A chiral structure is not super-imposable with its mirror image. Most commonly found in organic molecules, chirality can also occur in other systems, such as electromagnetic fields, where circularly polarized light is the most widespread example. Chiral electromagnetic fields can be a useful tool for biosensing applications. In particular, it has been shown that chiral plasmonic nanostructures have the ability to produce strongly enhanced chiral near-fields. Recently, our group has developed chiral plasmonic nanopyramids, which have the ability to focus chiral near-fields at their tip. This could enable chiral sensing at the single-molecule level. Chiral near-fields can be characterized in terms of the “optical chirality density”. This time-even and parity-odd pseudoscalar was first derived by Lipkin and was found to follow a conservation law analogous to the energy conservation of electromagnetic fields. More recently, Tang and Cohen identified the physical meaning of the “optical chirality density” as the degree of asymmetry in the excitation rate of a chiral molecule. However, how this near-field interpretation of the optical chirality could translate into the far-field is not well understood. Here, we formulate a far-field interpretation by investigating the conservation law for optical chirality in matter, and performing time-averaging in analogy to Poynting’s Theorem. In parallel to extinction energy, we define the “global chirality” as the sum of chirality dissipation within a material and the chirality flux leaving the system. With finite-element simulations, we place a dipole source at locations of enhanced local chirality and investigate the global chirality and ellipticity of emitted light in the far-field. Interestingly, we find that lossy materials with a complex dielectric function have the ability to generate global chirality when excited by achiral light. In particular, chiral plasmonic nanostructures are found to act as effective global chirality generators. The global interpretation of optical chirality provides a useful tool for biosensing applications with chiral plasmonic nanostructures, where the detection is routinely performed in the far-field.

Description: Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.

Description: In this paper, we present a systematic transition scheme for a large class of ordinary differential equations (ODEs) into Boolean networks. Our transition scheme can be applied to any system of ODEs whose right hand sides can be written as sums and products of monotone functions. It performs an Euler-like step which uses the signs of the right hand sides to obtain the Boolean update functions for every variable of the corresponding discrete model. The discrete model can, on one hand, be considered as another representation of the biological system or, alternatively, it can be used to further the analysis of the original ODE model. Since the generic transformation method does not guarantee any property conservation, a subsequent validation step is required. Depending on the purpose of the model this step can be based on experimental data or ODE simulations and characteristics. Analysis of the resulting Boolean model, both on its own and in comparison with the ODE model, then allows to investigate system properties not accessible in a purely continuous setting. The method is exemplarily applied to a previously published model of the bovine estrous cycle, which leads to new insights regarding the regulation among the components, and also indicates strongly that the system is tailored to generate stable oscillations.

Description: We present two algorithms to solve a 3-objective optimization problem arising in telecommunications access network planning, the k-Architecture Connected Facility Location Problem. The methods can also be used to solve any 3-objective integer linear programming model and can be extended to the multiobjective case. We give some exemplary computations using small and medium-sized instances for our problem.

Description: Rigorous optical simulations of 3-dimensional nano-photonic structures are an important tool in the analysis and optimization of scattering properties of nano-photonic devices or parameter reconstruction. To construct geometrically accurate models of complex structured nano-photonic devices the finite element method (FEM) is ideally suited due to its flexibility in the geometrical modeling and superior convergence properties. Reduced order models such as the reduced basis method (RBM) allow to construct self-adaptive, error-controlled, very low dimensional approximations for input-output relationships which can be evaluated orders of magnitude faster than the full model. This is advantageous in applications requiring the solution of Maxwell's equations for multiple parameters or a single parameter but in real time. We present a reduced basis method for 3D Maxwell's equations based on the finite element method which allows variations of geometric as well as material and frequency parameters. We demonstrate accuracy and efficiency of the method for a light scattering problem exhibiting a resonance in the electric field.

Description: Patient-specific parameters such as the orientation of the acetabulum or pelvic tilt are useful for custom planning for total hip arthroplasty (THA) and for evaluating the outcome of surgical interventions. The gold standard in obtaining pelvic parameters is from three-dimensional (3D) computed tomography (CT) imaging. However, this adds time and cost, exposes the patient to a substantial radiation dose, and does not allow for imaging under load (e.g. while the patient is standing). If pelvic parameters could be reliably derived from the standard anteroposterior (AP) radiograph, preoperative planning would be more widespread, and research analyses could be applied to retrospective data, after a postoperative issue is discovered. The goal of this work is to enable robust measurement of two surgical parameters of interest: the tilt of the anterior pelvic plane (APP) and the orientation of the natural acetabulum. We present a computer-aided reconstruction method to determine the APP and natural acetabular orientation from a single, preoperative X-ray. It can easily be extended to obtain other important preoperative and postoperative parameters solely based on a single AP radiograph.

Description: We propose a new framework for spacetime optimization that can generate artistic motion with a long planning horizon for complex virtual characters. The scheme can be used for generating general types of motion and neither requires motion capture data nor an initial motion that satisfies the constraints. Our modeling of the spacetime optimization combines linearized dynamics and a novel warping scheme for articulated characters. We show that the optimal motions can be described using a combination of vibration modes, wiggly splines, and our warping scheme. This enables us to restrict the optimization to low-dimensional spaces of explicitly parametrized motions. Thereby the computation of an optimal motion is reduced to a low-dimensional non-linear least squares problem, which can be solved with standard solvers. We show examples of motions created by specifying only a few constraints for positions and velocities.

Description: Clouds and precipitation systems are fundamental features in the global climate cycle and are one focus aspect of recent high resolution, cloud resolving simulations and measurement modalities. Highly resolved data sources allow for more precise methodologies to extract and track cloud features on different scales and enable novel evaluation tasks such as life-cycle tracking, feature-based statistics, and feature-based comparison of simulation and measurements. However, their complex dynamics and highly variable shape morphology makes extraction and tracking of clouds a challenging task with respect to stable and reliable algorithms. In this work we will present our efforts on establishing an community-wide inter-comparison study to provide an overview of state-of-the-art algorithms for cloud extraction and tracking. We propose a set of 2D and 3D benchmark data sets (from simulations and measurements) that are used as a common basis for comparison. In addition we describe a joint feature-based evaluation framework and provide an in depth analysis and comparison of those algorithms. The goal is to systematically compare and assess numerical extraction and tracking techniques for cloud features in meteorological data and provide a comprehensive overview of suitable application scenarios, describe current strengths and limitations, and derive statements about their variability for feature-based analysis tasks.

Description: Einführung: Die Tiefenwirkung dreidimensionaler Räume in einem zweidimensionalen Bild einzufangen, ist ein Faszinosum nahezu aller Kulturen der Menschheitsgeschichte. Der vorliegende Aufsatz folgt den Spuren dieses Faszinosums, vergleichend in der Malerei und der mathematisierten Computergrafik. Die Entdeckung der Zentralperspektive in der italienischen Renaissance zeigt bereits den engen Zusammenhang von Malerei und Mathematik. Auf der Suche nach Maltechniken, mit denen Raumtiefe bildnerisch dargestellt werden kann, beginnen wir in Kap. 2 mit einem chronologischen Gang durch verschiedene Epochen der europäischen Malerei. Hieraus abgeleitete Prinzipien, soweit sie im Rechner realisierbar scheinen, stellen wir in Kap. 3 am Beispiel moderner Methoden der mathematischen Visualisierung vor.

Description: Facial appearance in our societies is often associated with notions of attractiveness, juvenileness, beauty, success, and so forth. Hence, the role of facial plastic surgery is highly interrelated to a patient's desire to feature many of these positively connoted attributes, which of course, are subject of different cultural perceptions or social trends. To judge about somebody's facial appearance, appropriate quantitative measures as well as methods to obtain and compare individual facial features are required. This special issue on facial profile is intended to provide an overview on how facial characteristics are surgically managed in an interdisciplinary way based on experience, instrumentation, and modern technology to obtain an aesthetic facial appearance with harmonious facial proportions. The facial profile will be discussed within the context of facial aesthetics. Latest concepts for capturing facial morphology in high speed and impressive detail are presented for quantitative analysis of even subtle changes, aging effects, or facial expressions. In addition, the perception of facial profiles is evaluated based on eye tracking technology.

Description: This article reflects the research of the last two decades in computational planning for cranio-maxillofacial surgery. Model-guided and computer-assisted surgery planning has tremendously developed due to ever increasing computational capabilities. Simulators for education, planning, and training of surgery are often compared with flight simulators, where maneuvers are also trained to reduce a possible risk of failure. Meanwhile, digital patient models can be derived from medical image data with astonishing accuracy and thus can serve for model surgery to derive a surgical template model that represents the envisaged result. Computerized surgical planning approaches, however, are often still explorative, meaning that a surgeon tries to find a therapeutic concept based on his or her expertise using computational tools that are mimicking real procedures. Future perspectives of an improved computerized planning may be that surgical objectives will be generated algorithmically by employing mathematical modeling, simulation, and optimization techniques. Planning systems thus act as intelligent decision support systems. However, surgeons can still use the existing tools to vary the proposed approach, but they mainly focus on how to transfer objectives into reality. Such a development may result in a paradigm shift for future surgery planning.

Description: Pelvic tilt determines functional orientation of the acetabulum. In this study, we investigated the interaction of pelvic tilt and functional acetabular anteversion (AA) in supine position.

Description: Diese Bachelorarbeit beschäftigt sich mit der Entwicklung eines allgemeinen Verfahrens, welches die Dicke der mineralisierten Schicht von Haikieferelementen automatisch bestimmt. Dabei soll das Verfahren die Dicke näherungsweise im zweidimensionalen (2D) Raum sowie im dreidimensionalen (3D) Raum anhand von Computertomografie-Scans berechnen (im Folgenden als zweidimensionaler bzw. dreidimensionaler Fall bezeichnet). Es werden drei mögliche Verfahren eingeführt und im Anschluss auf ihre Verwendbarkeit analysiert. Für die Implementierung zur Dickenbestimmung wird der Kern der Rayburst Sampling Methode verwendet und im Weiteren für den 2D-Raum durch kleinere Optimierungen verbessert. Die Überprüfung der Genauigkeit des für den zweidimensionalen Fall entwickelten Programms erfolgt manuell. Für einen Vergleich im 3D-Raum wird ein zweites Verfahren programmiert, das auf der Berechnung der Isoflächen basiert. Diese Arbeit ist in den Bereich der angewandten Mathematik mit dem Schwerpunkt Informatik einzuordnen. Das entwickelte Programm wird im Anschluss Anwendung im Bereich der Biologie am Max-Planck-Institut für Grenzflächen- und Kolloidforschung Potsdam-Golm finden.

Description: The organization of the mitotic spindle, a structure that separates the chromosomes during cell division, is an active research topic in molecular cell biology. It is composed of microtubules, elongated tubular macromolecules with a diameter of 25 nm. The only volumetric imaging technique that is available to a wide community and provides the required resolution to capture details about microtubules is electron tomography. However, the automatic detection of microtubules in electron tomograms is a difficult task due to the low contrast of the data. Furthermore, thick samples have to be cut into 300 nm thin sections before electron tomography can be applied. Software for automatically segmentation and stitching of the microtubules are not available and therefore these tasks have to be performed manually. Unfortunately, manual segmentation is time consuming for large samples and manual stitching of the tomograms is often infeasible due to the lack of prominent features for registration. Conclusions drawn from electron tomographic data is currently mostly based on either small samples containing few microtubules or single sections of complex structures. Consequently, simple properties, such as the length of microtubules in the spindle or their number, are still unknown for most model organisms. In this thesis, we present methods for 1) an automatic segmentation of microtubule centerlines in electron tomograms, and 2) an automatic stitching of the lines extracted from serial sections. For the centerline segmentation, we use 3D template matching and exploit knowledge about shape of microtubules and microscopy artifacts to design the templates. For the registration of the lines, we present a way to model the orientation of lines as a mixture of Fisher-Mises distributions where we estimate transformation parameters with the expectation maximization algorithm. The final line matching problem is formulated in terms of a probabilistic graphical model. To find the correct correspondences of line ends, we use belief propagation. We handle the poor convergence properties of this algorithm by detecting ambiguous and conflicting assignments of lines automatically. An expert can then influence the final output of the algorithm by solving conflicts manually. A detailed error analysis on true biological data and assessment of the reliability of the results is the prerequisite for analyzing the resulting line representations of the microtubules. To this end, the developed workflow for segmenting and stitching of microtubule centerlines is evaluated on plasticembedded samples of C. elegans early embryos and of spindles from X. laevis egg extracts. Our results suggest that the output of the presented algorithms together with little manual correction is of sufficient quality to allow a detailed analysis of dense microtubule networks. Finally, we exemplarily show results for the centrosome of a C. elegans mitotic spindle.

Description: Eine grundlegende Eigenschaft von naturwissenschaftlichen Daten ist, dass der wahre Wert einer Größe nicht beliebig genau bestimmbar ist. Es ist lediglich möglich, ihn durch Intervalle einzugrenzen oder die Unsicherheit durch eine Wahrscheinlichkeitsverteilung zu charakterisieren. Dies gilt für alle reellwertigen Daten, sowohl für Mess-, als auch für Simulationsergebnisse. Beispiele sind Messungen von grundlegenden physikalischen Größen wie Geschwindigkeit oder auch langfristige Temperaturvorhersagen, die durch Klimamodelle berechnet werden. Die Unsicherheit von Ergebnissen ist eine wichtige Information, die in Natur- und Ingenieurwissenschaften häufig durch Konfidenzintervalle in 1D-Plots und Tabellen angezeigt wird. Im Gegensatz dazu ist es bisher bei der Visualisierung von 2D- und 3D-Daten mithilfe von Standardmethoden meist unmöglich, die Datenunsicherheit zu repräsentieren. Diese Arbeit stellt wahrscheinlichkeitstheoretisch fundierte Methoden vor, die die Analyse und Visualisierung von Skalar-, Vektor- und Tensorfeldern mit Unsicherheiten ermöglichen. Der Fokus liegt dabei auf der Extraktion von raumzeitlichen geometrischen und topologischen Merkmalen aus den Feldern (z.B. Isokonturen und kritische Punkte). Wir nutzen parametrische und nichtparametrische Zufallsfelder, um Variabilität und räumliche Korrelation mathematisch zu modellieren. Die Wahrscheinlichkeitsverteilungen werden aus Ensemble-Datensätzen geschätzt, die mehrere Simulationsergebnisse (z.B. basierend auf variierenden Simulationsparametern) zusammenfassen. Wir untersuchen die Konditionszahlen von Merkmalsextraktionsmethoden, um die Sensitivität, d.h. die Verstärkung oder Abschwächung der Unsicherheit der Ergebnisse relativ zu Unsicherheiten in den Eingangsdaten abzuschätzen. Wir stellen einen allgemeiner Ansatz für die probabilistische Merkmalsextraktion vor, der die Basis für die Berechnung räumlicher Wahrscheinlichkeitsverteilungen von verschiedenen Merkmalen in Skalar-, Vektor- und Tensorfeldern bildet. In diesem Framework werden Wahrscheinlichkeiten für die Existenz von Merkmalen aus lokalen Randverteilungen und formalen Merkmalsdefinitionen berechnet. Numerisch können die Wahrscheinlichkeiten durch Monte-Carlo­-Integration bestimmt werden. Um den hohen Rechenaufwand dieses Ansatzes zu vermeiden, schlagen wir schnelle Berechnungsmethoden vor, wobei Merkmalswahrscheinlichkeiten näherungsweise mit Hilfe von Surrogatfunktionen bzw. Lookup-Tabellen geschätzt werden. Die vorgeschlagenen Methoden werden anhand von Daten aus Klima- und Biofluidmechaniksimulationen sowie aus der medizinischen Bildgebung qualitativ und quantitativ evaluiert.

Description: The cartilaginous endoskeletons of sharks and rays are covered by tiles of mineralized cartilage called tesserae that enclose areas of unmineralized cartilage. These tesselated layers are vital to the growth as well as the material properties of the skeleton, providing both flexibility and strength. An understanding of the principles behind the tiling of the mineralized layer requires a quantitative analysis of shark and ray skeletal tessellation. However, since a single skeletal element comprises several thousand tesserae, manual segmentation is infeasible. We developed an automated segmentation pipeline that, working from micro-CT data, allows quantification of all tesserae in a skeletal element in less than an hour. Our segmentation algorithm relies on aspects we have learned of general tesseral morphology. In micro-CT scans, tesserae usually appear as round or star-shaped plate-like tiles, wider than deep and connected by mineralized intertesseral joints. Based on these observations, we exploit the distance map of the mineralized layer to separate individual tiles using a hierarchical watershed algorithm. Utilizing a two-dimensional distance map that measures the distance in the plane of the mineralized layer only greatly improves the segmentation. We developed post-processing techniques to quickly correct segmentation errors in regions where tesseral shape differs from the assumed shape. Evaluation of our results is done qualitatively by visual comparison with raw datasets, and quantitatively by comparison to manual segmentations. Furthermore, we generate two-dimensional abstractions of the tiling network based on the neighborhood, allowing representation of complex, biological forms as simpler geometries. We apply our newly developed techniques to the analysis of the left and right hyomandibulae of four ages of stingray enabling the first quantitative analyses of the tesseral tiling structure, while clarifying how these patterns develop across ontogeny.

Description: In civil engineering, the corrosion of steel reinforcements in structural elements of concrete bares a risk of stability-reduction, mainly caused by the exposure to chlorides. 3D computed tomography (CT) reveals the inner structure of concrete and allows one to investigate the corrosion with non-destructive testing methods. To carry out such investigations, specimens with a large artificial crack and an embedded steel rebar have been manufactured. 3D CT images of those specimens were acquired in the original state. Subsequently three cycles of electrochemical pre-damaging together with CT imaging were applied. These time series have been evaluated by means of image processing algorithms to segment and quantify the corrosion products. Visualization of the results supports the understanding of how corrosion propagates into cracks and pores. Furthermore, pitting of structural elements can be seen without dismantling. In this work, several image processing and visualization techniques are presented that have turned out to be particularly effective for the visualization and segmentation of corrosion products. Their combination to a workflow for corrosion analysis is the main contribution of this work.

Description: Structural properties of molecules are of primary concern in many fields. This report provides a comprehensive overview on techniques that have been developed in the fields of molecular graphics and visualization with a focus on applications in structural biology. The field heavily relies on computerized geometric and visual representations of three-dimensional, complex, large, and time-varying molecular structures. The report presents a taxonomy that demonstrates which areas of molecular visualization have already been extensively investigated and where the field is currently heading. It discusses visualizations for molecular structures, strategies for efficient display regarding image quality and frame rate, covers different aspects of level of detail, and reviews visualizations illustrating the dynamic aspects of molecular simulation data. The survey concludes with an outlook on promising and important research topics to foster further success in the development of tools that help to reveal molecular secrets.

Description: In this work, we developed an automatic algorithm to analyze cell migration in chemotaxis assays, based on phase-contrast time-lapse microscopy. While manual approaches are still widely used in recent publications, our algorithm is able to track hundreds of single cells per frame. The extracted paths are analysed with traditional geometrical approaches as well as diffusion-driven Markov state models (MSM). Based on these models, a detailed view on spatial and temporal effects is possible. Using our new approach on experimental data, we are able to distinguish between directed migration (e.g. towards a VEGF gradient) and random migration without favored direction. A calculation of the committor probabilities reveals that cells of the whole image area are more likely to migrate directly towards the VEGF than away from it during the first four hours. However, in absence of a chemoattractant, cells migrate more likely to their nearest image border. These conclusions are supported by the spatial mean directions. In a next step, the cell-cell interaction during migration and the migration of cell clusters will be analyzed. Furthermore, we want to observe phenotypical changes during migration based on fluorescence microscopy and machine learning. The algorithm is part of a collaborative platform which brings the experimental expertise of scientists from life sciences and the analytical knowledge of computer scientists together. This platform is built using web-based technologies with a responsive real-time user interface. All data, including raw and metadata as well as the accompanying results, will be stored in a secure and scalable compute cluster. The compute cluster provides sufficient space and computational power for modern image-based experiments and their analyses. Specific versions of data and results can be tagged to keep immutable records for archival.

Description: Enhancements in tomographic imaging techniques facilitate non-destructive methods for visualizing fossil structures. However, to penetrate dense materials such as sediments or pyrites, image acquisition is typically performed with high beam energy and very sensitive image intensifiers, leading to artifacts and noise in the acquired data. The analysis of delicate fossil structures requires the images to be captured in maximum resolution, resulting in large data sets of several giga bytes (GB) in size. Since the structural information of interest is often almost in the same spatial range as artifacts and noise, image processing and segmentation algorithms have to cope with a very low signal-to-noise ratio (SNR). Within this report we present a study on the performance of a collection of denoising algorithms applied to a very noisy fossil dataset. The study shows that a non-local means (NLM) filter, in case it is properly configured, is able to remove a considerable amount of noise while preserving most of the structural information of interest. Based on the results of this study, we developed a software tool within ZIBAmira that denoises large tomographic datasets using an adaptive, GPU-accelerated NLM filter. With the help of our implementation a user can interactively configure the filter's parameters and thus its effectiveness with respect to the data of interest, while the filtering response is instantly visualized for a preselected region of interest (ROI). Our implementation efficiently denoises even large fossil datasets in a reasonable amount of time.

Description: Socially interactive robot needs the same behaviors and capabilities of human to be accepted as a member in human society. The environment, in which this robot should operate, is the human daily life. The interaction capabilities of current robots are still limited due to complex inter-human interaction system. Humans usually use different types of verbal and nonverbal cues in their communication. Facial expression and head movement are good examples of nonverbal cues used in feedback. This paper presents a biological inspired system for Human-Robot Interaction (HRI). This system is based on the interactive model of inter-human communication proposed by Schramm. In this model, the robot and its interaction partner can be send and receive information at the same time. For example, if the robot is talking, it also perceive the feedback of the human via his/her nonverbal cues. In this work, we are focusing on recognizing the facial expression of human. The proposed facial expression recognition technique is based on machine learning. Multi SVMs have been used to recognize the six basic emotions in addition to the neutral expression. This technique uses only the depth information, acquired by Kinect, of human face.

Description: Cardiac Phase-resolved Blood Oxygen-Level-Dependent (CP- BOLD) MRI is a new contrast agent- and stress-free imaging technique for the assessment of myocardial ischemia at rest. The precise registration among the cardiac phases in this cine type acquisition is essential for automating the analysis of images of this technique, since it can potentially lead to better specificity of ischemia detection. However, inconsistency in myocardial intensity patterns and the changes in myocardial shape due to the heart’s motion lead to low registration performance for state- of-the-art methods. This low accuracy can be explained by the lack of distinguishable features in CP-BOLD and inappropriate metric defini- tions in current intensity-based registration frameworks. In this paper, the sparse representations, which are defined by a discriminative dictionary learning approach for source and target images, are used to improve myocardial registration. This method combines appearance with Gabor and HOG features in a dictionary learning framework to sparsely represent features in a low dimensional space. The sum of squared differences of these distinctive sparse representations are used to define a similarity term in the registration framework. The proposed descriptor is validated on a challenging dataset of CP-BOLD MR and standard CINE MR acquired in baseline and ischemic condition across 10 canines.

Description: Though unsupervised segmentation was a de-facto standard for cardiac MRI segmentation early on, recently cardiac MRI segmentation literature has favored fully supervised techniques such as Dictionary Learning and Atlas-based techniques. But, the benefits of unsupervised techniques e.g., no need for large amount of training data and better potential of handling variability in anatomy and image contrast, is more evident with emerging cardiac MR modalities. For example, CP-BOLD is a new MRI technique that has been shown to detect ischemia without any contrast at stress but also at rest conditions. Although CP-BOLD looks similar to standard CINE, changes in myocardial intensity patterns and shape across cardiac phases, due to the heart’s motion, BOLD effect and artifacts affect the underlying mechanisms of fully supervised segmentation techniques resulting in a significant drop in segmentation accuracy. In this paper, we present a fully unsupervised technique for segmenting myocardium from the background in both standard CINE MR and CP-BOLD MR. We combine appearance with motion information (obtained via Optical Flow) in a dictionary learning framework to sparsely represent important features in a low dimensional space and separate myocardium from background accordingly. Our fully automated method learns background-only models and one class classifier provides myocardial segmentation. The advantages of the proposed technique are demonstrated on a dataset containing CP-BOLD MR and standard CINE MR image sequences acquired in baseline and ischemic condition across 10 canine subjects, where our method outperforms state-of-the-art supervised segmentation techniques in CP-BOLD MR and performs at-par for standard CINE MR.

Description: Cardiac Phase-resolved Blood Oxygen-Level-Dependent (CP- BOLD) MR is capable of diagnosing an ongoing ischemia by detecting changes in myocardial intensity patterns at rest without any contrast and stress agents. Visualizing and detecting these changes require significant post-processing, including myocardial segmentation for isolating the myocardium. But, changes in myocardial intensity pattern and myocardial shape due to the heart’s motion challenge automated standard CINE MR myocardial segmentation techniques resulting in a significant drop of segmentation accuracy. We hypothesize that the main reason behind this phenomenon is the lack of discernible features. In this paper, a multi scale discriminative dictionary learning approach is proposed for supervised learning and sparse representation of the myocardium, to improve the myocardial feature selection. The technique is validated on a challenging dataset of CP-BOLD MR and standard CINE MR acquired in baseline and ischemic condition across 10 canine subjects. The proposed method significantly outperforms standard cardiac segmentation techniques, including segmentation via registration, level sets and supervised methods for myocardial segmentation.

Description: Precise voxel trajectory estimation in 4D CT images is a prerequisite for reliable dose accumulation during 4D treatment planning. 4D CT image data is, however, often affected by motion artifacts and applying standard pairwise registration to such data sets bears the risk of aligning anatomical structures to artifacts – with physiologically unrealistic trajectories being the consequence. In this work, the potential of a novel non-linear hybrid intensity- and feature-based groupwise registration method for robust motion field estimation in artifact-affected 4D CT image data is investigated. The overall registration performance is evaluated on the DIR-lab datasets; Its robustness if applied to artifact-affected data sets is analyzed using clinically acquired data sets with and without artifacts. The proposed registration approach achieves an accuracy comparable to the state-of-the-art (subvoxel accuracy), but smoother voxel trajectories compared to pairwise registration. Even more important: it maintained accuracy and trajectory smoothness in the presence of image artifacts – in contrast to standard pairwise registration, which yields higher landmark-based registration errors and a loss of trajectory smoothness when applied to artifact-affected data sets.

Description: Two new species of cheilostome Bryozoa are described from continental-slope habitats off Mauritania, including canyon and coldwater-coral (mound) habitats. Internal structures of both species were visualised and quantified using micro-computed tomographic (micro-CT) methods. Cellaria bafouri n. sp. is characterised by the arrangement of zooids in alternating longitudinal rows, a smooth cryptocyst, and the presence of an ooecial plate with denticles. Smittina imragueni n. sp. exhibits many similarities with Smittina cervicornis (Pallas, 1766), but differs especially in the shape and orientation of the suboral avicularium. Observations on Smittina imragueni and material labelled as Smittina cervicornis suggest that the latter represents a species group, members of which have not yet been discriminated, possibly because of high intracolony variation and marked astogenetic changes in surface morphology. Both new species are known only from the habitats where they were collected, probably reflecting the paucity of bryozoan sampling from this geographic area and depth range. Both species are able to tolerate low oxygen concentration, which is assumed to be compensated by the high nutrient supply off Mauritania. The application of micro-CT for the semiautomatic quantification of zooidal skeletal characters was successfully tested. We were able to automatically distinguish individual zooidal cavities and acquire corresponding morphological datasets. Comparing the obtained results with conventional SEM measurements allowed ascertaining the reliability of this new method. The employment of micro-CT allows the observation and quantification of previously un- seen characters that can be used in describing and differentiating species that were previously indistinguishable. Further- more, this method might help elucidate processes of colony growth and the function of individual zooids during this process.

Description: We consider the spectral proper orthogonal decomposition (SPOD) for experimental data of a turbulent swirling jet. This newly introduced method combines the advantages of spectral methods, such as Fourier decomposition or dynamic mode decomposition, with the energy-ranked proper orthogonal decomposition (POD). This poster visualizes how the modal energy spectrum transitions from the spectral purity of Fourier space to the sparsity of POD space. The transition is achieved by changing a single parameter – the width of the SPOD filter. Each dot in the 3D space corresponds to an SPOD mode pair, where the size and color indicates its spectral coherence. What we notice is that neither the Fourier nor the POD spectrum achieves a clear separation of the dynamic phenomena. Scanning through the graph from the front plane (Fourier) to the back plane (POD), we observe how three highly coherent SPOD modes emerge from the dispersed Fourier spectrum and later branch out into numerous POD modes. The spatial properties of these three individual SPOD modes are displayed in the back of the graph using line integral convolution colored by vorticity. The first two modes correspond to single-helical global instabilities that are well known for these flows. Their coexistence, however, has not been observed until now. The third mode is of double- helical shape and has not been observed so far. For this considered data set and many others, the SPOD is superior in identification of coherent structures in turbulent flows. Hopefully, it gives access to new fluid dynamic phenomena and enriches the available methods.