Library

Description: The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP.

Description: Ensuring the long-term availability of research data forms an integral part of data management services. Where OAIS compliant digital preservation has been established in recent years, in almost all cases the services aim at the preservation of file-based objects. In the Digital Humanities, research data is often represented in highly structured aggregations, such as Scholarly Digital Editions. Naturally, scholars would like their editions to remain functionally complete as long as possible. Besides standard components like webservers, the presentation typically relies on project specific code interacting with client software like webbrowsers. Especially the latter being subject to rapid change over time invariably makes such environments awkward to maintain once funding has ended. Pragmatic approaches have to be found in order to balance the curation effort and the maintainability of access to research data over time. A sketch of four potential service levels aiming at the long-term availability of research data in the humanities is outlined: (1) Continuous Maintenance, (2) Application Conservation, (3) Application Data Preservation, and (4) Bitstream Preservation. The first being too costly and the last hardly satisfactory in general, we suggest that the implementation of services by an infrastructure provider should concentrate on service levels 2 and 3. We explain their strengths and limitations considering the example of two Scholarly Digital Editions.

Description: Context. The change of the rotation period and the orientation of the rotation axis of comet 67P/Churyumov-Gerasimenko (67P/C-G) is deducible from images taken by the scientific imaging instruments on-board the Rosetta mission with high precision. Non gravitational forces are a natural explanation for these data. Aims. We describe observed changes for the orientation of the rotation axis and the rotation period of 67P/C-G. For these changes we give an explanation based on a sublimation model with a best-fit for the surface active fraction (model P). Torque effects of periodically changing gas emissions on the surface are considered. Methods. We solve the equation of state for the angular momentum in the inertial and the body- fixed frames and provide an analytic theory of the rotation changes in terms of Fourier coefficients, generally applicable to periodically forced rigid body dynamics. Results. The torque induced changes of the rotation state constrain the physical properties of the surface, the sublimation rate and the local active fraction of the surface. Conclusions. We determine a distribution of the local surface active fraction in agreement with the rotation properties, period and orientation, of 67P/C-G. The torque movement confirms that the sublimation increases faster than the insolation towards perihelion. The derived relatively uniform activity pattern is discussed in terms of related surface features.

Description: Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floating-point QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and Mészáros benchmark library.

Description: Probabilistic integration of a continuous dynamical system is a way of systematically introducing model error, at scales no larger than errors inroduced by standard numerical discretisation, in order to enable thorough exploration of possible responses of the system to inputs. It is thus a potentially useful approach in a number of applications such as forward uncertainty quantification, inverse problems, and data assimilation. We extend the convergence analysis of probabilistic integrators for deterministic ordinary differential equations, as proposed by Conrad et al.\ (\textit{Stat.\ Comput.}, 2016), to establish mean-square convergence in the uniform norm on discrete- or continuous-time solutions under relaxed regularity assumptions on the driving vector fields and their induced flows. Specifically, we show that randomised high-order integrators for globally Lipschitz flows and randomised Euler integrators for dissipative vector fields with polynomially-bounded local Lipschitz constants all have the same mean-square convergence rate as their deterministic counterparts, provided that the variance of the integration noise is not of higher order than the corresponding deterministic integrator.

Description: Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver. The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced.

Description: One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over a strict, non-rectangular subset of the box. In order to exploit this in practice, we propose to compute valid linear inequalities for the projection of the feasible region onto the x-y-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for x, y, and xy over the available projections. Our computational evaluation using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly.

Description: We present HAM (Heterogeneous Active Messages), a C++-only active messaging solution for heterogeneous distributed systems.Combined with a communication protocol, HAM can be used as a generic Remote Procedure Call (RPC) mechanism. It has been used in HAM-Offload to implement a low-overhead offloading framework for inter- and intra-node offloading between different architectures including accelerators like the Intel Xeon Phi x100 series and the NEC SX-Aurora TSUBASA Vector Engine. HAM uses template meta-programming to implicitly generate active message types and their corresponding handler functions. Heterogeneity is enabled by providing an efficient address translation mechanism between the individual handler code addresses of processes running different binaries on different architectures, as well a hooks to inject serialisation and deserialisation code on a per-type basis. Implementing such a solution in modern C++ sheds some light on the shortcomings and grey areas of the C++ standard when it comes to distributed and heterogeneous environments.

Description: The simulation of open molecular systems requires explicit or implicit reservoirs of energy and particles. Whereas full atomistic resolution is desired in the region of interest, there is some freedom in the implementation of the reservoirs. Here, a combined, explicit reservoir is constructed by interfacing the atomistic region with regions of point-like, non-interacting particles (tracers) embedded in a thermodynamic mean field. The tracer molecules acquire atomistic resolution upon entering the atomistic region and equilibrate with this environment, while atomistic molecules become tracers governed by an effective mean-field potential after crossing the atomistic boundary. The approach is extensively tested on thermodynamic, structural, and dynamic properties of liquid water. Conceptual and numerical advantages of the procedure as well as new perspectives are highlighted and discussed.

Description: Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity and an associated length, together with nonempty supply-intervals for the sources and nonempty demand-intervals for the sinks. The goal of the Maximum Minimum Cost Flow Problem (MMCF) is to find fixed supply and demand values within these intervals, such that the optimal objective value of the induced Minimum Cost Flow Problem (MCF) is maximized. In this paper, we show that MMCF is APX-hard and remains NP-hard in the uncapacitated case.

Description: SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively parallel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best-known solutions to instances from the benchmark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been considerably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.

Description: Branch-and-bound (B&B) is an algorithmic framework for solving NP-hard combinatorial optimization problems. Although several well-designed software frameworks for parallel B&B have been developed over the last two decades, there is very few literature about successfully solving previously intractable combinatorial optimization problem instances to optimality by using such frameworks.The main reason for this limited impact of parallel solvers is that the algorithmic improvements for specific problem types are significantly greater than performance gains obtained by parallelization in general. Therefore, in order to solve hard problem instances for the first time, one needs to accelerate state-of-the-art algorithm implementations. In this paper, we present a computational study for solving Steiner tree problems and mixed integer semidefinite programs in parallel. These state-of-the-art algorithm implementations are based on SCIP and were parallelized via the ug[SCIP-*,*]-libraries---by adding less than 200 lines of glue code. Despite the ease of their parallelization, these solvers have the potential to solve previously intractable instances. In this paper, we demonstrate the convenience of such a parallelization and present results for previously unsolvable instances from the well-known PUC benchmark set, widely regarded as the most difficult Steiner tree test set in the literature.

Description: Nutrition plays a crucial role in regulating reproductive hormones and follicular development in cattle. This is visible particularly during the time of negative energy balance at the onset of milk production after calving. Here, elongated periods of anovulation have been observed, resulting from alterations in luteiniz- ing hormone concentrations, likely caused by lower glucose and insulin concen- trations in the blood. The mechanisms that result in a reduced fertility are not completely understood, although a close relationship to the glucose-insulin metabolism is widely supported. Following this idea, a mathematical model of the hormonal network combining reproductive hormones and hormones that are coupled to the glucose compartments within the body of the cow was developed. The model is built on ordinary differential equations and relies on previously introduced models on the bovine estrous cycle and the glucose-insulin dynam- ics. Necessary modifications and coupling mechanisms are thoroughly discussed. Depending on the composition and the amount of food, in particular the glu- cose content in the dry matter, the model quantifies reproductive hormones and follicular development over time. Simulation results for different nutritional regimes in lactating and non-lactating dairy cows are examined and compared with experimental studies. Regarding its applicability, this work is an early attempt towards developing in silico feeding strategies and may eventually help refining and reducing animal experiments.

Description: We consider the problem of partitioning a weighted graph into k connected components of similar weight. In particular, we consider the two classical objectives to maximize the lightest part or to minimize the heaviest part. For a partitioning of the vertex set and for both objectives, we give the first known approximation results on general graphs. Specifically, we give a $\Delta$-approximation where $\Delta$ is the maximum degree of an arbitrary spanning tree of the given graph. Concerning the edge partition case, we even obtain a 2-approximation for the min-max and the max-min problem, by using the claw-freeness of line graphs.

Description: The recent article "A Bayesian conjugate gradient method" by Cockayne, Oates, Ipsen, and Girolami proposes an approximately Bayesian iterative procedure for the solution of a system of linear equations, based on the conjugate gradient method, that gives a sequence of Gaussian/normal estimates for the exact solution. The purpose of the probabilistic enrichment is that the covariance structure is intended to provide a posterior measure of uncertainty or confidence in the solution mean. This note gives some comments on the article, poses some questions, and suggests directions for further research.

Description: The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances.

Description: Solvers for partial differential equations (PDE) are one of the cornerstones of computational science. For large problems, they involve huge amounts of data that needs to be stored and transmitted on all levels of the memory hierarchy. Often, bandwidth is the limiting factor due to relatively small arithmetic intensity, and increasingly so due to the growing disparity between computing power and bandwidth. Consequently, data compression techniques have been investigated and tailored towards the specific requirements of PDE solvers during the last decades. This paper surveys data compression challenges and corresponding solution approaches for PDE problems, covering all levels of the memory hierarchy from mass storage up to main memory. Exemplarily, we illustrate concepts at particular methods, and give references to alternatives.

Description: Linear energy system models are often a crucial component of system design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers|already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an interior-point solver that exploits common structures of linear energy system models to efficiently run in parallel on distributed memory systems. The solver is designed for linear programs with doubly bordered block-diagonal constraint matrix and makes use of a Schur complement based decomposition. Special effort has been put into handling large numbers of linking constraints and variables as commonly observed in energy system models. In order to handle this strong linkage, a distributed preconditioning of the Schur complement is used. In addition, the solver features a number of more generic techniques such as parallel matrix scaling and structure-preserving presolving. The implementation is based on the existing parallel interior-point solver PIPS-IPM. We evaluate the computational performance on energy system models with up to 700 million non-zero entries in the constraint matrix, and with more than 200 million columns and 250 million rows. This article mainly concentrates on the energy system model ELMOD, which is a linear optimization model representing the European electricity markets by the use of a nodal pricing market clearing. It has been widely applied in the literature on energy system analyses during the recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models.

Description: In this dissertation, we study matchings and flows in hypergraphs using combinatorial methods. These two problems are among the best studied in the field of combinatorial optimization. As hypergraphs are a very general concept, not many results on graphs can be generalized to arbitrary hypergraphs. Therefore, we consider special classes of hypergraphs, which admit more structure, to transfer results from graph theory to hypergraph theory. In Chapter 2, we investigate the perfect matching problem on different classes of hypergraphs generalizing bipartite graphs. First, we give a polynomial time approximation algorithm for the maximum weight matching problem on so-called partitioned hypergraphs, whose approximation factor is best possible up to a constant. Afterwards, we look at the theorems of König and Hall and their relation. Our main result is a condition for the existence of perfect matchings in normal hypergraphs that generalizes Hall’s condition for bipartite graphs. In Chapter 3, we consider perfect f-matchings, f-factors, and (g,f)-matchings. We prove conditions for the existence of (g,f)-matchings in unimodular hypergraphs, perfect f-matchings in uniform Mengerian hypergraphs, and f-factors in uniform balanced hypergraphs. In addition, we give an overview about the complexity of the (g,f)-matching problem on different classes of hypergraphs generalizing bipartite graphs. In Chapter 4, we study the structure of hypergraphs that admit a perfect matching. We show that these hypergraphs can be decomposed along special cuts. For graphs it is known that the resulting decomposition is unique, which does not hold for hypergraphs in general. However, we prove the uniqueness of this decomposition (up to parallel hyperedges) for uniform hypergraphs. In Chapter 5, we investigate flows on directed hypergraphs, where we focus on graph-based directed hypergraphs, which means that every hyperarc is the union of a set of pairwise disjoint ordinary arcs. We define a residual network, which can be used to decide whether a given flow is optimal or not. Our main result in this chapter is an algorithm that computes a minimum cost flow on a graph-based directed hypergraph. This algorithm is a generalization of the network simplex algorithm.

Description: Diese Arbeit untersucht Matchings und Flüsse in Hypergraphen mit Hilfe kombinatorischer Methoden. In Graphen gehören diese Probleme zu den grundlegendsten der kombinatorischen Optimierung. Viele Resultate lassen sich nicht von Graphen auf Hypergraphen verallgemeinern, da Hypergraphen ein sehr abstraktes Konzept bilden. Daher schauen wir uns bestimmte Klassen von Hypergraphen an, die mehr Struktur besitzen, und nutzen diese aus um Resultate aus der Graphentheorie zu übertragen. In Kapitel 2 betrachten wir das perfekte Matchingproblem auf Klassen von „bipartiten“ Hypergraphen, wobei es verschiedene Möglichkeiten gibt den Begriff „bipartit“ auf Hypergraphen zu definieren. Für sogenannte partitionierte Hypergraphen geben wir einen polynomiellen Approximationsalgorithmus an, dessen Gütegarantie bis auf eine Konstante bestmöglich ist. Danach betrachten wir die Sätze von Konig und Hall und untersuchen deren Zusammenhang. Unser Hauptresultat ist eine Bedingung für die Existenz von perfekten Matchings auf normalen Hypergraphen, die Halls Bedingung für bipartite Graphen verallgemeinert. Als Verallgemeinerung von perfekten Matchings betrachten wir in Kapitel 3 perfekte f-Matchings, f-Faktoren und (g, f)-Matchings. Wir beweisen Bedingungen für die Existenz von (g, f)-Matchings auf unimodularen Hypergraphen, perfekten f-Matchings auf uniformen Mengerschen Hypergraphen und f-Faktoren auf uniformen balancierten Hypergraphen. Außerdem geben wir eine Übersicht über die Komplexität des (g, f)-Matchingproblems auf verschiedenen Klassen von Hypergraphen an, die bipartite Graphen verallgemeinern. In Kapitel 4 untersuchen wir die Struktur von Hypergraphen, die ein perfektes Matching besitzen. Wir zeigen, dass diese Hypergraphen entlang spezieller Schnitte zerlegt werden können. Für Graphen weiß man, dass die so erhaltene Zerlegung eindeutig ist, was im Allgemeinen für Hypergraphen nicht zutrifft. Wenn man jedoch uniforme Hypergraphen betrachtet, dann liefert jede Zerlegung die gleichen unzerlegbaren Hypergraphen bis auf parallele Hyperkanten. Kapitel 5 beschäftigt sich mit Flüssen in gerichteten Hypergraphen, wobei wir Hypergraphen betrachten, die auf gerichteten Graphen basieren. Das bedeutet, dass eine Hyperkante die Vereinigung einer Menge von disjunkten Kanten ist. Wir definieren ein Residualnetzwerk, mit dessen Hilfe man entscheiden kann, ob ein gegebener Fluss optimal ist. Unser Hauptresultat in diesem Kapitel ist ein Algorithmus, um einen Fluss minimaler Kosten zu finden, der den Netzwerksimplex verallgemeinert.

Description: Our project aimed at building an in silico model based on our recently developed in vitro osteoarthritis (OA) model seeking for refinement of the model to enhance validity and translatability towards the more sophisticated simulation of OA. In detail, the previously 3D in vitro model is based on 3D chondrogenic constructs generated solely from human bone marrow derived mesenchymal stromal cells (hMSCs). Besides studying the normal state of the model over 3 weeks, the in vitro model was treated with interleukin-1β (IL-1β) and tumor necrosis factor alpha (TNFα) to mimic an OA-like environment.

Description: In many physical situations involving diverse length scales, waves or rays representing them travel through media characterized by spatially smooth, random, modest refractive index variations. "Primary" diffraction (by individual sub-wavelength features) is absent. Eventually the weak refraction leads to imperfect focal "cusps". Much later, a statistical regime characterized by momentum diffusion is manifested. An important intermediate regime is often overlooked, one that is diffusive only in an ensemble sense. Each realization of the ensemble possesses dramatic ray limit structure that guides the waves (in the same sense that ray optics is used to design lens systems). This structure is a universal phenomenon called branched flow. Many important phenomena develop in this intermediate regime. Here we give examples and some of the physics of this emerging field.

Description: We find previously unknown families of sets which ensure Frankl's conjecture holds for all families that contain them using an algorithmic framework. The conjecture states that for any nonempty finite union-closed (UC) family there exists an element of the ground set in at least half the sets of the considered UC family. Poonen's Theorem characterizes the existence of weights which determine whether a given UC family implies the conjecture for all UC families which contain it. We design a cutting-plane method that computes the explicit weights which satisfy the existence conditions of Poonen's Theorem. This method enables us to answer several open questions regarding structural properties of UC families, including the construction of a counterexample to a conjecture of Morris from 2006.

Description: We present a mechanistic pharmacokinetic-pharmacodynamic model to simulate the effect of dexamethasone on the glucose metabolism in dairy cows. The coupling of the pharmacokinetic model to the pharmacodynamic model is based on mechanisms underlying homeostasis regulation by dexamethasone. In particular, the coupling takes into account the predominant role of dexamethasone in stimulating glucagon secretion, glycogenolysis and lipolysis and in impairing the sensitivity of cells to insulin. Simulating the effect of a single dose of dexamethasone on the physiological behaviour of the system shows that the adopted mechanisms are able to induce a temporary hyperglycemia and hyperinsulinemia, which captures the observed data in non-lactating cows. In lactating cows, the model simulations show that a single dose of dexamethasone reduces the lipolytic effect, owing to the reduction of glucose uptake by the mammary gland.

Description: The kinetics of bimolecular reactions in solution depends, among other factors, on intermolecular forces such as steric repulsion or electrostatic interaction. Microscopically, a pair of molecules first has to meet by diffusion before the reaction can take place. In this work, we establish an extension of Doi’s volume reaction model to molecules interacting via pair potentials, which is a key ingredient for interacting-particle-based reaction–diffusion (iPRD) simulations. As a central result, we relate model parameters and macroscopic reaction rate constants in this situation. We solve the corresponding reaction–diffusion equation in the steady state and derive semi- analytical expressions for the reaction rate constant and the local concentration profiles. Our results apply to the full spectrum from well-mixed to diffusion-limited kinetics. For limiting cases, we give explicit formulas, and we provide a computationally inexpensive numerical scheme for the general case, including the intermediate, diffusion-influenced regime. The obtained rate constants decompose uniquely into encounter and formation rates, and we discuss the effect of the potential on both subprocesses, exemplified for a soft harmonic repulsion and a Lennard-Jones potential. The analysis is complemented by extensive stochastic iPRD simulations, and we find excellent agreement with the theoretical predictions.

Description: Mussel glue‐proteins undergo structural transitions at material interfaces to optimize adhesive surface contacts. Those intriguing structure responses are mimicked by a mussel‐glue mimetic peptide (HSY*SGWSPY*RSG (Y* = l‐Dopa)) that was previously selected by phage‐display to adhere to Al2O3 after enzymatic activation. Molecular level insights into the full‐length adhesion domain at Al2O3 surfaces are provided by a divergent‐convergent analysis, combining nuclear Overhauser enhancement based 2D NOESY and saturation transfer difference NMR analysis of submotifs along with molecular dynamics simulations of the full‐length peptide. The peptide is divided into two submotifs, each containing one Dopa “anchor” (Motif‐1 and 2). The analysis proves Motif‐1 to constitute a dynamic Al2O3 binder and adopting an “M”‐structure with multiple surface contacts. Motif‐2 binds stronger by two surface contacts, forming a compact “C”‐structure. Taking these datasets as constraints enables to predict the structure and propose a binding process model of the full‐length peptide adhering to Al2O3.

Description: Osteoarthritis (OA) is the most common cause of disability in ageing societies, with no effective therapies available to date. Two preclinical models are widely used to validate novel OA interventions (MCL-MM and DMM). Our aim is to discern disease dynamics in these models to provide a clear timeline in which various pathological changes occur. OA was surgically induced in mice by destabilisation of the medial meniscus. Analysis of OA progression revealed that the intensity and duration of chondrocyte loss and cartilage lesion formation were significantly different in MCL-MM vs DMM. Firstly, apoptosis was seen prior to week two and was narrowly restricted to the weight bearing area. Four weeks post injury the magnitude of apoptosis led to a 40–60% reduction of chondrocytes in the non-calcified zone. Secondly, the progression of cell loss preceded the structural changes of the cartilage spatio-temporally. Lastly, while proteoglycan loss was similar in both models, collagen type II degradation only occurred more prominently in MCL-MM. Dynamics of chondrocyte loss and lesion formation in preclinical models has important implications for validating new therapeutic strategies. Our work could be helpful in assessing the feasibility and expected response of the DMM- and the MCL-MM models to chondrocyte mediated therapies.

Description: Mathematische Algorithmen können durch Vorhersage von Unsicherheiten optimierte OP-Pläne berechnen, sodass mehrere Zielkriterien wie Überstunden, Wartezeit und Ausfälle im OP minimiert werden.

Description: We examine an effect of side walls on the linear stability of an interface of tangential-velocity discontinuity in shallow-water flow. The flow is pure horizontal in the plane xy, and the fluid is bounded in a finite width 2d in the y− direction. In region 0 〈 y 〈 d, the fluid is moving with uniform velocity U but is at rest for −d 〈 y 〈 0. Without side walls, the flow is unstable for a velocity difference U〈√8c U 〈 √8 c, with c being the velocity of gravity waves. In this work, we show that if the velocity difference U is smaller than 2c, the interface is always destabilized, also known as the flow is unstable. The unstable region of an infinite width model is shrunken by the effects of side walls in the case of narrow width, while there is no range for the Froude number for stabilization in the case of large width. These results play an important role in predicting the wave propagations and have a wide application in the fields of industry. As a result of the interaction of waves and the mean flow boundary, the flow is unstable, which is caused by a decrease in the kinetic energy of disturbance.

Description: Mathematical publications are an important resource for the devel- opment of machine-based methods for mathematical knowledge man- agement. This article describes the publication-based approach to improve the information and the access to two important classes of mathematical research, mathematical software and mathematical algo- rithms. The publication-based approach is based on analyzing links and the structure of mathematical publications. It has been used to build the swMATH service which provides comprehensive information about mathematical software and algorithms.

Description: We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases.

Description: Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with transfer of resources during a finite length planning horizon of multiple periods. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of line type designs and question the choice of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.

Description: We present a method for the automated segmentation of knee bones and cartilage from magnetic resonance imaging that combines a priori knowledge of anatomical shape with Convolutional Neural Networks (CNNs). The proposed approach incorporates 3D Statistical Shape Models (SSMs) as well as 2D and 3D CNNs to achieve a robust and accurate segmentation of even highly pathological knee structures. The shape models and neural networks employed are trained using data of the Osteoarthritis Initiative (OAI) and the MICCAI grand challenge "Segmentation of Knee Images 2010" (SKI10), respectively. We evaluate our method on 40 validation and 50 submission datasets of the SKI10 challenge. For the first time, an accuracy equivalent to the inter-observer variability of human readers has been achieved in this challenge. Moreover, the quality of the proposed method is thoroughly assessed using various measures for data from the OAI, i.e. 507 manual segmentations of bone and cartilage, and 88 additional manual segmentations of cartilage. Our method yields sub-voxel accuracy for both OAI datasets. We made the 507 manual segmentations as well as our experimental setup publicly available to further aid research in the field of medical image segmentation. In conclusion, combining statistical anatomical knowledge via SSMs with the localized classification via CNNs results in a state-of-the-art segmentation method for knee bones and cartilage from MRI data.

Description: Simulations and measurements of blood and air flow inside the human circulatory and respiratory system play an increasingly important role in personalized medicine for prevention, diagnosis, and treatment of diseases. This survey focuses on three main application areas. (1) Computational Fluid Dynamics (CFD) simulations of blood flow in cerebral aneurysms assist in predicting the outcome of this pathologic process and of therapeutic interventions. (2) CFD simulations of nasal airflow allow for investigating the effects of obstructions and deformities and provide therapy decision support. (3) 4D Phase-Contrast (4D PC) Magnetic Resonance Imaging (MRI) of aortic hemodynamics supports the diagnosis of various vascular and valve pathologies as well as their treatment. An investigation of the complex and often dynamic simulation and measurement data requires the coupling of sophisticated visualization, interaction, and data analysis techniques. In this paper, we survey the large body of work that has been conducted within this realm. We extend previous surveys by incorporating nasal airflow, addressing the joint investigation of blood flow and vessel wall properties, and providing a more fine-granular taxonomy of the existing techniques. From the survey, we extract major research trends and identify open problems and future challenges. The survey is intended for researchers interested in medical flow but also more general, in the combined visualization of physiology and anatomy, the extraction of features from flow field data and feature-based visualization, the visual comparison of different simulation results, and the interactive visual analysis of the flow field and derived characteristics.

Description: Volumetry of the cartilage of the knee, as needed for the assessment of knee osteoarthritis (KOA), is typically performed in a tedious and subjective process. We present an automated segmentation-based method for the quantification of cartilage volume by employing 3D Convolutional Neural Networks (CNNs). CNNs were trained in a supervised manner using magnetic resonance imaging data as well as cartilage volumetry readings given by clinical experts for 1378 subjects. It was shown that 3D CNNs can be employed for cartilage volumetry with an accuracy similar to expert volumetry readings. In future, accurate automated cartilage volumetry might support both, diagnosis of KOA as well as assessment of KOA progression via longitudinal analysis.

Description: Advanced osteoarthritis is a leading cause of knee replacement and loss of functionality. Early detection of risk factors plays an important role in the application of preventive measures. One of the risk factors is the leg alignment which influences the speed of knee cartilage degradation. The ’gold standard’ measurement of leg alignment is done by determining the Hip Knee Ankle (HKA) angle from full lower limb radiographs. Convolutional Neural Networks (CNNs) have gained popularity recently in computer vision. In this thesis we developed methods using CNNs to determine HKA angles from full lower limb radiographs. We trained the CNNs using data from the Osteoarthritis Initiative (OAI). We evaluated our method’s performance by evaluating its agreement to experts measurement and its reliability. Our best performing method shows excellent agreement and reliability levels.

Description: Background: Although several studies have provided insights into the role of long non-coding RNAs (lncRNAs), the majority of them have unknown function. Recent evidence has shown the importance of both lncRNAs and chromatin interactions in transcriptional regulation. Although network-based methods, mainly exploiting gene-lncRNA co-expression, have been applied to characterize lncRNA of unknown function by means of ’guilt-by-association’, no strategy exists so far which identifies mRNA-lncRNA functional modules based on the 3D chromatin interaction graph. Results: To better understand the function of chromatin interactions in the context of lncRNA-mediated gene regulation, we have developed a multi-step graph analysis approach to examine the RNA polymerase II ChIA-PET chromatin interaction network in the K562 human cell line. We have annotated the network with gene and lncRNA coordinates, and chromatin states from the ENCODE project. We used centrality measures, as well as an adaptation of our previously developed Markov State Models (MSM) clustering method, to gain a better understanding of lncRNAs in transcriptional regulation. The novelty of our approach resides in the detection of fuzzy regulatory modules based on network properties and their optimization based on co-expression analysis between genes and gene-lncRNA pairs. This results in our method returning more bona fide regulatory modules than other state-of-the art approaches for clustering on graphs. Conclusions: Interestingly, we find that lncRNA network hubs tend to be significantly enriched in evolutionary conserved lncRNAs and enhancer-like functions. We validated regulatory functions for well known lncRNAs, such as MALAT1 and the enhancer-like lncRNA FALEC. In addition, by investigating the modular structure of bigger components we mine putative regulatory functions for uncharacterized lncRNAs.

Description: Statistical Shape Models (SSMs) allow for a compact representation of shape and shape variation and they are a proven means for model-based 3D anatomy reconstruction from medical image data. In orthopaedics and biomechanics, SSMs are increasingly employed to individualize measurement data or to create individualized anatomical models. The human spine is a versatile and complex articulated structure and thus is an interesting candidate to be modeled using an advanced type of SSMs. For modeling and analysis of articulated structures, so called articulated SSMs (aSSMs) have been developed. However, a missing feature of aSSMs is the consideration of collisions in the course of individual fitting and articulation. The aim of this thesis is to develop an aSSM of two adjacent vertebrae that handles collisions between components correctly. The model will incorporate the two major aspects of variability: Shape of a single vertebra and the relative positioning of neighboring vertebrae. That way it becomes possible to adjust shape and articulation in view of a physically and geometrically plausible individualization. To be able to apply collision-aware aSSMs in simulation and optimisation in future work, the approach is based on a parallelized collision detection method employing Graphics Processing Units (GPUs).

Description: In this paper, we present a software-assisted workflow for the alignment and matching of filamentous structures across a stack of 3D serial image sections. This is achieved by a combination of automatic methods, visual validation, and interactive correction. After an initial alignment, the user can continuously improve the result by interactively correcting landmarks or matches of filaments. This is supported by a quality assessment that visualizes regions that have been already inspected and, thus, allows a trade-off between quality and manual labor. The software tool was developed in collaboration with biologists who investigate microtubule-based spindles during cell division. To quantitatively understand the structural organization of such spindles, a 3D reconstruction of the numerous microtubules is essential. Each spindle is cut into a series of semi-thick physical sections, of which electron tomograms are acquired. The sections then need to be stitched, i.e. non-rigidly aligned; and the microtubules need to be traced in each section and connected across section boundaries. Experiments led to the conclusion that automatic methods for stitching alone provide only an incomplete solution to practical analysis needs. Automatic methods may fail due to large physical distortions, a low signal-to-noise ratio of the images, or other unexpected experimental difficulties. In such situations, semi-automatic validation and correction is required to rescue as much information as possible to derive biologically meaningful results despite of some errors related to data collection. Since the correct stitching is visually not obvious due to the number of microtubules (up to 30k) and their dense spatial arrangement, these are difficult tasks. Furthermore, a naive inspection of each microtubule is too time consuming. In addition, interactive visualization is hampered by the size of the image data (up to 100 GB). Based on the requirements of our collaborators, we present a practical solution for the semi-automatic stitching of serial section image stacks with filamentous structures.

Description: Quantification of magnetic resonance (MR)-based relaxation parameters of tendons and ligaments is challenging due to their very short transverse relaxation times, requiring application of ultra-short echo-time (UTE) imaging sequences. We quantify both T1 and T2⁎ in the quadriceps and patellar tendons of healthy volunteers at a field strength of 3 T and visualize the results based on 3D segmentation by using bivariate histogram analysis. We applied a 3D ultra-short echo-time imaging sequence with either variable repetition times (VTR) or variable flip angles (VFA) for T1 quantification in combination with multi-echo acquisition for extracting T2⁎. The values of both relaxation parameters were subsequently binned for bivariate histogram analysis and corresponding cluster identification, which were subsequently visualized. Based on manually-drawn regions of interest in the tendons on the relaxation parameter maps, T1 and T2⁎ boundaries were selected in the bivariate histogram to segment the quadriceps and patellar tendons and visualize the relaxation times by 3D volumetric rendering. Segmentation of bone marrow, fat, muscle and tendons was successfully performed based on the bivariate histogram analysis. Based on the segmentation results mean T2⁎ relaxation times, over the entire tendon volumes averaged over all subjects, were 1.8 ms ± 0.1 ms and 1.4 ms ± 0.2 ms for the patellar and quadriceps tendons, respectively. The mean T1 value of the patellar tendon, averaged over all subjects, was 527 ms ± 42 ms and 476 ms ± 40 ms for the VFA and VTR acquisitions, respectively. The quadriceps tendon had higher mean T1 values of 662 ms ± 97 ms (VFA method) and 637 ms ± 40 ms (VTR method) compared to the patellar tendon. 3D volumetric visualization of the relaxation times revealed that T1 values are not constant over the volume of both tendons, but vary locally. This work provided additional data to build upon the scarce literature available on relaxation times in the quadriceps and patellar tendons. We were able to segment both tendons and to visualize the relaxation parameter distributions over the entire tendon volumes.

Description: We describe a novel nonlinear statistical shape model basedon differential coordinates viewed as elements of GL+(3). We adopt an as-invariant-as possible framework comprising a bi-invariant Lie group mean and a tangent principal component analysis based on a unique GL+(3)-left-invariant, O(3)-right-invariant metric. Contrary to earlier work that equips the coordinates with a specifically constructed group structure, our method employs the inherent geometric structure of the group-valued data and therefore features an improved statistical power in identifying shape differences. We demonstrate this in experiments on two anatomical datasets including comparison to the standard Euclidean as well as recent state-of-the-art nonlinear approaches to statistical shape modeling.

Description: In our chapter we are describing how to reconstruct three-dimensional anatomy from medical image data and how to build Statistical 3D Shape Models out of many such reconstructions yielding a new kind of anatomy that not only allows quantitative analysis of anatomical variation but also a visual exploration and educational visualization. Future digital anatomy atlases will not only show a static (average) anatomy but also its normal or pathological variation in three or even four dimensions, hence, illustrating growth and/or disease progression. Statistical Shape Models (SSMs) are geometric models that describe a collection of semantically similar objects in a very compact way. SSMs represent an average shape of many three-dimensional objects as well as their variation in shape. The creation of SSMs requires a correspondence mapping, which can be achieved e.g. by parameterization with a respective sampling. If a corresponding parameterization over all shapes can be established, variation between individual shape characteristics can be mathematically investigated. We will explain what Statistical Shape Models are and how they are constructed. Extensions of Statistical Shape Models will be motivated for articulated coupled structures. In addition to shape also the appearance of objects will be integrated into the concept. Appearance is a visual feature independent of shape that depends on observers or imaging techniques. Typical appearances are for instance the color and intensity of a visual surface of an object under particular lighting conditions, or measurements of material properties with computed tomography (CT) or magnetic resonance imaging (MRI). A combination of (articulated) statistical shape models with statistical models of appearance lead to articulated Statistical Shape and Appearance Models (a-SSAMs).After giving various examples of SSMs for human organs, skeletal structures, faces, and bodies, we will shortly describe clinical applications where such models have been successfully employed. Statistical Shape Models are the foundation for the analysis of anatomical cohort data, where characteristic shapes are correlated to demographic or epidemiologic data. SSMs consisting of several thousands of objects offer, in combination with statistical methods ormachine learning techniques, the possibility to identify characteristic clusters, thus being the foundation for advanced diagnostic disease scoring.

Description: Volumetry of cartilage of the knee is needed for knee osteoarthritis (KOA) assessment. It is typically performed manually in a tedious and subjective process. We developed a method for an automated, segmentation-based quantification of cartilage volume by employing 3D Convolutional Neural Networks (CNNs). CNNs were trained in a supervised manner using magnetic resonance imaging data and cartilage volumetry readings performed by clinical experts for 1378 subjects provided by the Osteoarthritis Initiative. It was shown that 3D CNNs are able to achieve volume measures comparable to the magnitude of variation between expert readings and the real in vivo situation. In the future, accurate automated cartilage volumetry might support both, diagnosis of KOA as well as longitudinal analysis of KOA progression.

Description: The fiber surface generalizes the popular isosurface to multi-fields, so that pre-images can be visualized as surfaces. As with the isosurface, however, the fiber surface suffers from visual occlusion. We propose to avoid such occlusion by restricting the components to only the relevant ones with a new component-wise flexing algorithm. The approach, flexible fiber surface, generalizes the manipulation idea found in the flexible isosurface for the fiber surface. The flexible isosurface in the original form, however, relies on the contour tree. For the fiber surface, this corresponds to the Reeb space, which is challenging for both the computation and user interaction. We thus take a Reeb-free approach, in which one does not compute the Reeb space. Under this constraint, we generalize a few selected interactions in the flexible isosurface and discuss the implication of the restriction.

Description: Functional surgery on the nasal framework requires referential criteria to objectively assess nasal breathing for indication and follow-up. Thismotivated us to generate amean geometry of the nasal cavity based on a statistical shape model. In this study, the authors could demonstrate that the introduced nasal cavity’s mean geometry features characteristics of the inner shape and airflow, which are commonly observed in symptom-free subjects. Therefore, the mean geometry might serve as a reference-like model when one considers qualitative aspects. However, to facilitate quantitative considerations and statistical inference, further research is necessary. Additionally, the authorswere able to obtain details about the importance of the isthmus nasi and the inferior turbinate for the intranasal airstream.

Description: Successful functional surgery on the nasal framework requires reliable and comprehensive diagnosis. In this regard, the authors introduce a new methodology: Digital Analysis of Nasal Airflow (diANA). It is based on computational fluid dynamics, a statistical shape model of the healthy nasal cavity and rhinologic expertise. diANA necessitates an anonymized tomographic dataset of the paranasal sinuses including the complete nasal cavity and, when available, clinical information. The principle of diANA is to compare the morphology and the respective airflow of an individual nose with those of a reference. This enablesmorphometric aberrations and consecutive flow field anomalies to localize and quantify within a patient’s nasal cavity. Finally, an elaborated expert opinion with instructive visualizations is provided. Using diANA might support surgeons in decision-making, avoiding unnecessary surgery, gaining more precision, and target-orientation for indicated operations.

Description: We present a method for the automated segmentation of knee bones and cartilage from magnetic resonance imaging (MRI) that combines a priori knowledge of anatomical shape with Convolutional Neural Networks (CNNs).The proposed approach incorporates 3D Statistical Shape Models (SSMs) as well as 2D and 3D CNNs to achieve a robust and accurate segmentation of even highly pathological knee structures.The shape models and neural networks employed are trained using data from the Osteoarthritis Initiative (OAI) and the MICCAI grand challenge "Segmentation of Knee Images 2010" (SKI10), respectively. We evaluate our method on 40 validation and 50 submission datasets from the SKI10 challenge.For the first time, an accuracy equivalent to the inter-observer variability of human readers is achieved in this challenge.Moreover, the quality of the proposed method is thoroughly assessed using various measures for data from the OAI, i.e. 507 manual segmentations of bone and cartilage, and 88 additional manual segmentations of cartilage. Our method yields sub-voxel accuracy for both OAI datasets. We make the 507 manual segmentations as well as our experimental setup publicly available to further aid research in the field of medical image segmentation.In conclusion, combining localized classification via CNNs with statistical anatomical knowledge via SSMs results in a state-of-the-art segmentation method for knee bones and cartilage from MRI data.

Description: Quantitative photoacoustic tomography aims to recover maps of the local concentrations of tissue chromophores from multispectral images. While model-based inversion schemes are promising approaches, major challenges to their practical implementation include the unknown fluence distribution and the scale of the inverse problem. This paper describes an inversion scheme based on a radiance Monte Carlo model and an adjoint-assisted gradient optimization that incorporates fluence-dependent step sizes and adaptive moment estimation. The inversion is shown to recover absolute chromophore concentrations, blood oxygen saturation and the Grüneisen parameter from in silico 3D phantom images for different radiance approximations. The scattering coefficient was assumed to be homogeneous and known a priori.

Description: We present a novel approach for nonlinear statistical shape modeling that is invariant under Euclidean motion and thus alignment-free. By analyzing metric distortion and curvature of shapes as elements of Lie groups in a consistent Riemannian setting, we construct a framework that reliably handles large deformations. Due to the explicit character of Lie group operations, our non-Euclidean method is very efficient allowing for fast and numerically robust processing. This facilitates Riemannian analysis of large shape populations accessible through longitudinal and multi-site imaging studies providing increased statistical power. We evaluate the performance of our model w.r.t. shape-based classification of pathological malformations of the human knee and show that it outperforms the standard Euclidean as well as a recent nonlinear approach especially in presence of sparse training data. To provide insight into the model’s ability of capturing natural biological shape variability, we carry out an analysis of specificity and generalization ability.

Description: This work introduces methods for analyzing the three imaging modalities delivered by Talbot-Lau grating interferometry X-ray computed tomography (TLGI-XCT). The first problem we address is providing a quick way to show a fusion of all three modal- ities. For this purpose the tri-modal transfer function widget is introduced. The widget controls a mixing function that uses the output of the transfer functions of all three modalities, allowing the user to create one customized fused image. A second problem prevalent in processing TLGI-XCT data is a lack of tools for analyzing the segmentation process of such multimodal data. We address this by providing methods for computing three types of uncertainty: From probabilistic segmentation algorithms, from the voxel neighborhoods as well as from a collection of results. We furthermore introduce a linked views interface to explore this data. The techniques are evaluated on a TLGI-XCT scan of a carbon-fiber reinforced dataset with impact damage. We show that the transfer function widget accelerates and facilitates the exploration of this dataset, while the uncertainty analysis methods give insights into how to tweak and improve segmentation algorithms for more suitable results.

Description: In dentistry, software-based medical image analysis and visualization provide effcient and accurate diagnostic and therapy planning capabilities. We present an approach for the automatic recognition of tooth types and positions in digital volume tomography (DVT). By using deep learning techniques in combination with dimension reduction through non-planar reformatting of the jaw anatomy, DVT data can be effciently processed and teeth reliably recognized and classified, even in the presence of imaging artefacts, missing or dislocated teeth. We evaluated our approach, which is based on 2D Convolutional Neural Networks (CNNs), on 118 manually annotated cases of clinical DVT datasets. Our proposed method correctly classifies teeth with an accuracy of 94% within a limit of 2mm distancr to ground truth landmarks.

Description: In many applications, geodesic hierarchical models are adequate for the study of temporal observations. We employ such a model derived for manifold-valued data to Kendall's shape space. In particular, instead of the Sasaki metric, we adapt a functional-based metric, which increases the computational efficiency and does not require the implementation of the curvature tensor. We propose the corresponding variational time discretization of geodesics and apply the approach for the estimation of group trends and statistical testing of 3D shapes derived from an open access longitudinal imaging study on osteoarthritis.

Description: Quantitative photoacoustic tomography aims recover the spatial distribution of absolute chromophore concentrations and their ratios from deep tissue, high-resolution images. In this study, a model-based inversion scheme based on a Monte-Carlo light transport model is experimentally validated on 3-D multispectral images of a tissue phantom acquired using an all-optical scanner with a planar detection geometry. A calibrated absorber allowed scaling of the measured data during the inversion, while an acoustic correction method was employed to compensate the effects of limited view detection. Chromophore- and fluence-dependent step sizes and Adam optimization were implemented to achieve rapid convergence. High resolution 3-D maps of absolute concentrations and their ratios were recovered with high accuracy. Potential applications of this method include quantitative functional and molecular photoacoustic tomography of deep tissue in preclinical and clinical studies.

Description: Background Geometric parameters have been proposed for prediction of cerebral aneurysm rupture risk. Predicting the rupture risk for incidentally detected unruptured aneurysms could help clinicians in their treatment decision. However, assessment of geometric parameters depends on several factors, including the spatial resolution of the imaging modality used and the chosen reconstruction procedure. The aim of this study was to investigate the uncertainty of a variety of previously proposed geometric parameters for rupture risk assessment, caused by variability of reconstruction procedures. Materials 26 research groups provided segmentations and surface reconstructions of five cerebral aneurysms as part of the Multiple Aneurysms AnaTomy CHallenge (MATCH) 2018. 40 dimensional and non-dimensional geometric parameters, describing aneurysm size, neck size, and irregularity of aneurysm shape, were computed. The medians as well as the absolute and relative uncertainties of the parameters were calculated. Additionally, linear regression analysis was performed on the absolute uncertainties and the median parameter values. Results A large variability of relative uncertainties in the range between 3.9 and 179.8% was found. Linear regression analysis indicates that some parameters capture similar geometric aspects. The lowest uncertainties 〈 6% were found for the non-dimensional parameters isoperimetric ratio, convexity ratio, and ellipticity index. Uncertainty of 2D and 3D size parameters was significantly higher than uncertainty of 1D parameters. The most extreme uncertainties 〉 80% were found for some curvature parameters. Conclusions Uncertainty analysis is essential on the road to clinical translation and use of rupture risk prediction models. Uncertainty quantification of geometric rupture risk parameters provided by this study may help support development of future rupture risk prediction models.

Description: Surgical tool detection is attracting increasing attention from the medical image analysis community. The goal generally is not to precisely locate tools in images, but rather to indicate which tools are being used by the surgeon at each instant. The main motivation for annotating tool usage is to design efficient solutions for surgical workflow analysis, with potential applications in report generation, surgical training and even real-time decision support. Most existing tool annotation algorithms focus on laparoscopic surgeries. However, with 19 million interventions per year, the most common surgical procedure in the world is cataract surgery. The CATARACTS challenge was organized in 2017 to evaluate tool annotation algorithms in the specific context of cataract surgery. It relies on more than nine hours of videos, from 50 cataract surgeries, in which the presence of 21 surgical tools was manually annotated by two experts. With 14 participating teams, this challenge can be considered a success. As might be expected, the submitted solutions are based on deep learning. This paper thoroughly evaluates these solutions: in particular, the quality of their annotations are compared to that of human interpretations. Next, lessons learnt from the differential analysis of these solutions are discussed. We expect that they will guide the design of efficient surgery monitoring tools in the near future.

Description: In many applications, it is often necessary to sample the mean value of certain quantity with respect to a probability measure $\mu$ on the level set of a smooth function ξ:R^d→R^k, 1≤k〈d. A specially interesting case is the so-called conditional probability measure, which is useful in the study of free energy calculation and model reduction of diffusion processes. By Birkhoff's ergodic theorem, one approach to estimate the mean value is to compute the time average along an infinitely long trajectory of an ergodic diffusion process on the level set whose invariant measure is $\mu$. Motivated by the previous work of Ciccotti, Lelièvre, and Vanden-Eijnden, as well as the work of Lelièvre, Rousset, and Stoltz, in this paper we construct a family of ergodic diffusion processes on the level set of ξ whose invariant measures coincide with the given one. For the conditional measure, in particular, we show that the corresponding SDEs of the constructed ergodic processes have relatively simple forms, and, moreover, we propose a consistent numerical scheme which samples the conditional measure asymptotically. The numerical scheme doesn't require computing the second derivatives of ξ and the error estimates of its long time sampling efficiency are obtained.

Description: Effective dynamics using conditional expectation was proposed in [F. Legoll and T. Lelièvre, Nonlinearity, 2010] to approximate the essential dynamics of high-dimensional diffusion processes along a given reaction coordinate. The approximation error of the effective dynamics when it is used to approximate the behavior of the original dynamics has been considered in recent years. As a continuation of the previous work [F. Legoll, T. Lelièvre, and S. Olla, Stoch. Process. Appl, 2017], in this paper we obtain pathwise estimates for effective dynamics when the reaction coordinate function is either nonlinear or vector-valued.

Description: The fiber surface generalizes the popular isosurface to multi-fields, so that pre-images can be visualized as surfaces. As with the isosurface, however, the fiber surface suffers from visual occlusion. We propose to avoid such occlusion by restricting the components to only the relevant ones with a new component-wise flexing algorithm. The approach, flexible fiber surface, generalizes the manipulation idea found in the flexible isosurface for the fiber surface. The flexible isosurface in the original form, however, relies on the contour tree. For the fiber surface, this corresponds to the Reeb space, which is challenging for both the computation and user interaction. We thus take a Reeb-free approach, in which one does not compute the Reeb space. Under this constraint, we generalize a few selected interactions in the flexible isosurface and discuss the implication of the restriction.

Description: To assess the influence of the alkali-silica reaction (ASR) on pavement concrete 3D-CT imaging has been applied to concrete samples. Prior to imaging these samples have been drilled out of a concrete beam pre-damaged by fatigue loading. The resulting high resolution 3D-CT images consist of several gigabytes of voxels. Current desktop computers can visualize such big datasets without problems but a visual inspection or manual segmentation of features such as cracks by experts can only be carried out on a few slices. A quantitative analysis of cracks requires a segmentation of the whole specimen which could only be done by an automatic feature detection. This arises the question of the reliability of an automatic crack detection algorithm, its certainty and limitations. Does the algorithm find all cracks? Does it find too many cracks? Can parameters of that algorithm, once identified as good, be applied to other samples as well? Can ensemble computing with many crack parameters overcome the difficulties with parameter finding? By means of a crack detection algorithm based on shape recognition (template matching) these questions will be discussed. Since the author has no access to reliable ground truth data of cracks the assessment of the certainty of the automatic crack is restricted to visual inspection by experts. Therefore, an artificial dataset based on a combination of manually segmented cracks processed together with simple image processing algorithms is used to quantify the accuracy of the crack detection algorithm. Part of the evaluation of cracks in concrete samples is the knowledge of the surrounding material. The surrounding material can be used to assess the detected cracks, e.g. micro-cracks within the aggregate-matrix interface may be starting points for cracks on a macro scale. Furthermore, the knowledge of the surrounding material can help to find better parameter sets for the crack detection itself because crack characteristics may vary depending on their surrounding material. Therefore, in addition to a crack detection a complete segmentation of the sample into the components of concrete, such as aggregates, cement matrix and pores is needed. Since such a segmentation task cannot be done manually due to the amount of data, an approach utilizing convolutional neuronal networks stemming from a medical application has been applied. The learning phase requires a ground truth i.e. a segmentation of the components. This has to be created manually in a time-consuming task. However, this segmentation can be used for a quantitative evaluation of the automatic segmentation afterwards. Even though that work has been performed as a short term subtask of a bigger project funded by the German Research Foundation (DFG) this paper discusses problems which may arise in similar projects, too.

Description: Quantitative photoacoustic tomography aims to recover maps of the local concentrations of tissue chromophores from multispectral images. While model-based inversion schemes are promising approaches, major challenges to their practical implementation include the unknown fluence distribution and the scale of the inverse problem. This paper describes an inversion scheme based on a radiance Monte Carlo model and an adjoint-assisted gradient optimization that incorporates fluence-dependent step sizes and adaptive moment estimation. The inversion is shown to recover absolute chromophore concentrations, blood oxygen saturation and the Grüneisen parameter from in silico 3D phantom images for different radiance approximations. The scattering coefficient was assumed to be homogeneous and known a priori.

Description: Statistical Shape Models (SSMs) are a proven means for model-based 3D anatomy reconstruction from medical image data. In orthopaedics and biomechanics, SSMs are increasingly employed to individualize measurement data or to create individualized anatomical models to which implants can be adapted to or functional tests can be performed on. For modeling and analysis of articulated structures, so called articulated SSMs (aSSMs) have been developed. However, a missing feature of aSSMs is the consideration of collisions in the course of individual fitting and articulation. The aim of our work was to develop aSSMs that handle collisions between components correctly. That way it becomes possible to adjust shape and articulation in view of a physically and geometrically plausible individualization. To be able to apply collision-aware aSSMs in simulation and optimisation, our approach is based on an e� cient collision detection method employing Graphics Processing Units (GPUs).

Description: Various 3D imaging techniques are routinely used to examine biological materials, the results of which are usually a stack of grayscale images. In order to quantify structural aspects of the biological materials, however, they must first be extracted from the dataset in a process called segmentation. If the individual structures to be extracted are in contact or very close to each other, distance-based segmentation methods utilizing the Euclidean distance transform are commonly employed. Major disadvantages of the Euclidean distance transform, however, are its susceptibility to noise (very common in biological data), which often leads to incorrect segmentations (i.e. poor separation of objects of interest), and its limitation of being only effective for roundish objects. In the present work, we propose an alternative distance transform method, the random-walk distance transform, and demonstrate its effectiveness in high-throughput segmentation of three microCT datasets of biological tilings (i.e. structures composed of a large number of similar repeating units). In contrast to the Euclidean distance transform, this random-walk approach represents the global, rather than the local, geometric character of the objects to be segmented and, thus, is less susceptible to noise. In addition, it is directly applicable to structures with anisotropic shape characteristics. Using three case studies—stingray tessellated cartilage, starfish dermal endoskeleton, and the prismatic layer of bivalve mollusc shell—we provide a typical workflow for the segmentation of tiled structures, describe core image processing concepts that are underused in biological research, and show that for each study system, large amounts of biologically-relevant data can be rapidly segmented, visualized and analyzed.

Description: We present visual analysis methods for the evaluation of tomographic fiber reconstruction algorithms by means of analysis, visual debugging and comparison of reconstructed fibers in materials science. The methods are integrated in a tool (FIAKER) that supports the entire workflow. It enables the analysis of various fiber reconstruction algorithms, of differently parameterized fiber reconstruction algorithms and of individual steps in iterative fiber reconstruction algorithms. Insight into the performance of fiber reconstruction algorithms is obtained by a list‐based ranking interface. A 3D view offers interactive visualization techniques to gain deeper insight, e.g., into the aggregated quality of the examined fiber reconstruction algorithms and parameterizations. The tool was designed in close collaboration with researchers who work with fiber‐reinforced polymers on a daily basis and develop algorithms for tomographic reconstruction and characterization of such materials. We evaluate the tool using synthetic datasets as well as tomograms of real materials. Five case studies certify the usefulness of the tool, showing that it significantly accelerates the analysis and provides valuable insights that make it possible to improve the fiber reconstruction algorithms. The main contribution of the paper is the well‐considered combination of methods and their seamless integration into a visual tool that supports the entire workflow. Further findings result from the analysis of (dis‐)similarity measures for fibers as well as from the discussion of design decisions. It is also shown that the generality of the analytical methods allows a wider range of applications, such as the application in pore space analysis.

Description: We present a novel approach for nonlinear statistical shape modeling that is invariant under Euclidean motion and thus alignment-free. By analyzing metric distortion and curvature of shapes as elements of Lie groups in a consistent Riemannian setting, we construct a framework that reliably handles large deformations. Due to the explicit character of Lie group operations, our non-Euclidean method is very efficient allowing for fast and numerically robust processing. This facilitates Riemannian analysis of large shape populations accessible through longitudinal and multi-site imaging studies providing increased statistical power. We evaluate the performance of our model w.r.t. shape-based classification of pathological malformations of the human knee and show that it outperforms the standard Euclidean as well as a recent nonlinear approach especially in presence of sparse training data. To provide insight into the model's ability of capturing natural biological shape variability, we carry out an analysis of specificity and generalization ability.

Description: We describe a novel nonlinear statistical shape model basedon differential coordinates viewed as elements of GL+(3). We adopt an as-invariant-as possible framework comprising a bi-invariant Lie group mean and a tangent principal component analysis based on a unique GL+(3)-left-invariant, O(3)-right-invariant metric. Contrary to earlier work that equips the coordinates with a specifically constructed group structure, our method employs the inherent geometric structure of the group-valued data and therefore features an improved statistical power in identifying shape differences. We demonstrate this in experiments on two anatomical datasets including comparison to the standard Euclidean as well as recent state-of-the-art nonlinear approaches to statistical shape modeling.

Description: In individuals of similar body mass representing closely related species with different lifestyles, muscle architectural properties can be assumed to reflect adaptation to differing, lifestyle-related functional demands. We here employ a fiber recognition algorithm on contrast-enhanced micro-computed tomography (μCT) scans of one specimen each of an arboreal (Sciurus vulgaris) and a fossorial (Spermophilus citellus) sciuromorph rodent. The automated approach accounts for potential heterogeneity of architectural properties within a muscle by analyzing all fascicles that compose a muscle. Muscle architectural properties (volume, fascicle length, and orientation, and force-generating capacity) were quantified in 14 hindlimb (hip, knee, and ankle) extensor muscles and compared between specimens. We expected the arboreal squirrel to exhibit greater force-generating capacity and a greater capacity for length change allowing more powerful hindlimb extension. Generally and mostly matching our expectations, the S. vulgaris specimen had absolutely and relatively larger extensor muscles than the S. citellus specimen which were thus metabolically more expensive and demonstrate the relatively larger investment into powerful hindlimb extension necessary in the arboreal context. We conclude that detailed quantitative data on hindlimb muscle internal structure as was gathered here for a very limited sample further lends support to the notion that muscle architecture reflects adaptation to differential functional demands in closely related species with different locomotor behaviors and lifestyles.

Description: In many applications, geodesic hierarchical models are adequate for the study of temporal observations. We employ such a model derived for manifold-valued data to Kendall's shape space. In particular, instead of the Sasaki metric, we adapt a functional-based metric, which increases the computational efficiency and does not require the implementation of the curvature tensor. We propose the corresponding variational time discretization of geodesics and apply the approach for the estimation of group trends and statistical testing of 3D shapes derived from an open access longitudinal imaging study on osteoarthritis.

Description: In dentistry, software-based medical image analysis and visualization provide efficient and accurate diagnostic and therapy planning capabilities. We present an approach for the automatic recognition of tooth types and positions in digital volume tomography (DVT). By using deep learning techniques in combination with dimensionality reduction through non-planar reformatting of the jaw anatomy, DVT data can be efficiently processed and teeth reliably recognized and classified, even in the presence of imaging artefacts, missing or dislocated teeth. We evaluated our approach, which is based on 2D Convolutional Neural Networks (CNNs), on 118 manually annotated cases of clinical DVT datasets. Our proposed method correctly classifies teeth with an accuracy of 94% within a limit of 2mm distance to ground truth labels.

Description: Various 3D imaging techniques are routinely used to examine biological materials, the results of which are usually a stack of grayscale images. In order to quantify structural aspects of the biological materials, however, they must first be extracted from the dataset in a process called segmentation. If the individual structures to be extracted are in contact or very close to each other, distance-based segmentation methods utilizing the Euclidean distance transform are commonly employed. Major disadvantages of the Euclidean distance transform, however, are its susceptibility to noise (very common in biological data), which often leads to incorrect segmentations (i.e. poor separation of objects of interest), and its limitation of being only effective for roundish objects. In the present work, we propose an alternative distance transform method, the random-walk distance transform, and demonstrate its effectiveness in high-throughput segmentation of three microCT datasets of biological tilings (i.e. structures composed of a large number of similar repeating units). In contrast to the Euclidean distance transform, this random-walk approach represents the global, rather than the local, geometric character of the objects to be segmented and, thus, is less susceptible to noise. In addition, it is directly applicable to structures with anisotropic shape characteristics. Using three case studies—stingray tessellated cartilage, starfish dermal endoskeleton, and the prismatic layer of bivalve mollusc shell—we provide a typical workflow for the segmentation of tiled structures, describe core image processing concepts that are underused in biological research, and show that for each study system, large amounts of biologically-relevant data can be rapidly segmented, visualized and analyzed.

Description: In our chapter we are describing how to reconstruct three-dimensional anatomy from medical image data and how to build Statistical 3D Shape Models out of many such reconstructions yielding a new kind of anatomy that not only allows quantitative analysis of anatomical variation but also a visual exploration and educational visualization. Future digital anatomy atlases will not only show a static (average) anatomy but also its normal or pathological variation in three or even four dimensions, hence, illustrating growth and/or disease progression. Statistical Shape Models (SSMs) are geometric models that describe a collection of semantically similar objects in a very compact way. SSMs represent an average shape of many three-dimensional objects as well as their variation in shape. The creation of SSMs requires a correspondence mapping, which can be achieved e.g. by parameterization with a respective sampling. If a corresponding parameterization over all shapes can be established, variation between individual shape characteristics can be mathematically investigated. We will explain what Statistical Shape Models are and how they are constructed. Extensions of Statistical Shape Models will be motivated for articulated coupled structures. In addition to shape also the appearance of objects will be integrated into the concept. Appearance is a visual feature independent of shape that depends on observers or imaging techniques. Typical appearances are for instance the color and intensity of a visual surface of an object under particular lighting conditions, or measurements of material properties with computed tomography (CT) or magnetic resonance imaging (MRI). A combination of (articulated) statistical shape models with statistical models of appearance lead to articulated Statistical Shape and Appearance Models (a-SSAMs).After giving various examples of SSMs for human organs, skeletal structures, faces, and bodies, we will shortly describe clinical applications where such models have been successfully employed. Statistical Shape Models are the foundation for the analysis of anatomical cohort data, where characteristic shapes are correlated to demographic or epidemiologic data. SSMs consisting of several thousands of objects offer, in combination with statistical methods ormachine learning techniques, the possibility to identify characteristic clusters, thus being the foundation for advanced diagnostic disease scoring.

Description: We consider the problem of routing a data packet through the visibility graph of a polygonal domain P with n vertices and h holes. We may preprocess P to obtain a "label" and a "routing table" for each vertex of P. Then, we must be able to route a data packet between any two vertices p and q of P, where each step must use only the label of the target node q and the routing table of the current node. For any fixed epsilon 〉 0, we present a routing scheme that always achieves a routing path whose length exceeds the shortest path by a factor of at most 1 + epsilon. The labels have O(log n) bits, and the routing tables are of size O(((epsilon^-1)+h)log n). The preprocessing time is O((n^2)log n). It can be improved to O(n^2) for simple polygons.

Description: The historical importance of ancient manuscripts is unique since they provide information about the heritage of ancient cultures. Often texts are hidden in rolled or folded documents. Due to recent impro- vements in sensitivity and resolution, spectacular disclosures of rolled hidden texts were possible by X-ray tomography. However, revealing text on folded manuscripts is even more challenging. Manual unfolding is often too risky in view of the fragile condition of fragments, as it can lead to the total loss of the document. X-ray tomography allows for virtual unfolding and enables non-destructive access to hid- den texts. We have recently demonstrated the procedure and tested unfolding algorithms on a mockup sample. Here, we present results on unfolding ancient papyrus packages from the papyrus collection of the Musée du Louvre, among them objects folded along approximately orthogonal folding lines. In one of the packages, the first identification of a word was achieved, the Coptic word for “Lord”.

Description: The historical importance of ancient manuscripts is unique since they provide information about the heritage of ancient cultures. Often texts are hidden in rolled or folded documents. Due to recent impro- vements in sensitivity and resolution, spectacular disclosures of rolled hidden texts were possible by X-ray tomography. However, revealing text on folded manuscripts is even more challenging. Manual unfolding is often too risky in view of the fragile condition of fragments, as it can lead to the total loss of the document. X-ray tomography allows for virtual unfolding and enables non-destructive access to hid- den texts. We have recently demonstrated the procedure and tested unfolding algorithms on a mockup sample. Here, we present results on unfolding ancient papyrus packages from the papyrus collection of the Musée du Louvre, among them objects folded along approximately orthogonal folding lines. In one of the packages, the first identification of a word was achieved, the Coptic word for “Lord”.