Institutt for informatikk

Instituttseminar 2008

Autumn 2008

December 18

Charl Botha, TU Delft

Title: Computer-assisted shoulder replacement

Abstract: Pre-operative planning systems aid clinicians by giving insight into patient-specific issues before surgery is performed. The ability to perform a virtual shoulder replacement procedure enables the surgeon to explore the probable and plausible outcomes. Pre-operative planning software assists the surgeon in this complex decision-making process.

In our prototype pre-operative planning system for shoulder replacement, we create patient-specific bone-determined range of motion (ROM) predictions based on collision detection using segmented pathological CT-data. The gleno-humeral ROM is visualised with motion envelopes, that indicate the maximum range of motion of the humerus in every direction. The prosthesis placement parameters can be adjusted interactively in our simulator, during which a novel visualisation technique depicts the differences between the current and previous range of motion. Recently we used a prototype intra-operative guidance module of our own design for performing a cadaver study, in order to validate the ROM simulation.


In this talk I will discuss our complete medical visualisation pipeline for shoulder replacement: acquisition, processing and segmentation, patient-specific motion modelling, visualisation, intra-operative guidance and evaluation. If time permits, I will also give a live demo of some aspects of the system. Monday, December 15

Douglas Rogers

Title: Paths on grids; or how a little discrete mathematics can take you a long way ...

Abstract: The discrete structures course is something of a flagship for the II teaching program around which all research groups can gather for the local recruitment of students. But why study instead of playing computer games? Amie Albrecht and Kevin White in an article in the March issue of the Australian Mathematical Society Gazette took an attractive applied problem about paths on grids and tied themselves up with their mathematics, obtaining an unmanageable formula. The aim of the talk is to show that that does not have to happen if we prepare the ground. As it happens, help was already to hand in the previous issue of the Gazette. Moreover, as also often happens, there are leads into fresh research on waiting patterns for a printer waiting to be explored ... The talk is a light hearted look at combinatorics suitable for this late in the semester.

December 11

Clemens Grabmayer (with Joerg Endrullis, Dimitri Hendriks)

Title: Data-Oblivious Stream Productivity

Abstract: We are concerned with demonstrating productivity of specifications of infinite streams of data, based on orthogonal rewrite rules. In general, this property is undecidable, but for restricted formats computable sufficient conditions can be obtained. The usual analysis, also adopted here, disregards the identity of data, thus leading to approaches that we call data-oblivious. We present a method that is provably optimal among all such data-oblivious approaches. This means that in order to improve on our algorithm one has to proceed in a data-aware fashion.

The paper is available at:

Our webpage with more information and our online productivity-tools:

December 4

Mary Sheeran, Chalmers University

Title: Finding good parallel prefix networks using search and functional programming

The prefix problem is to compute [x0, x0*x1, x0*x1*x2, .. x0*x1*..*xn] given inputs [x0, x1, .. xn] and an associative, but not necessarily commutative operator *. Prefix networks are important both as circuits and in parallel programming. They give a way to perform an apparently sequential computation quickly by exploiting parallelism. Prefix networks are, for example, used to compute the carries in fast adders, which are in turn used to build fast multipliers. Such adders are often the hot spots in microprocessors and we need new designs that consume less power. In parallel programming, the prefix function is closely associated with the parallelisation of loops. We need new ways to design these networks, both because this will lead to better arithmetic circuits and just because the algorithm is a fundamental one.

There are many standard prefix networks, usually named by the two authors who invented them (Ladner Fischer, Brent Kung, Kogge Stone). This talk presents my attempts at using dynamic programming (in Haskell) to find fast, low power, prefix networks. Initially, I minimise number of operators for a given depth, and with constrained fanout. The presented method gives networks that are in many cases better (that is have fewer operators or smaller fanout for a given depth) than those currently known.

Using depth as a measure of circuit speed, and number of operators as a measure of power consumption turns out to be a good first approximation. The accuracy of estimation of speed and power could then be improved by repeated calls, during the search, to the recently developed Wired system (Axelsson's wire-aware design system, embedded in Haskell). The use of Wired allows the production of real circuit layouts via a link to a commercial CAD tool. We have not produced any break-through results here yet, but it is now very easy to explore the design space.

I suspect that the search method could be used in other contexts, for instance in generating data parallel programs. (We are developing an embedded language for GPU programming that is closely related to the style of circuit description used here. We plan to experiment with searching for programs once the system is more stable.)

November 13

In Grupperom 2143: Serge Gaspers, UiB (Trial Lecture)

Title: Data streaming: Algorithms and Applications

(Store Auditorium (2144) is reserved for a school visit.)

November 6

Edi Gröller, TU Vienna

Title: Knowledge-Assisted Visualization

Abstract: Utilizing knowledge and information derived from the visualization process or from data analysis helps in generating more effective visualizations. The inclusion of knowledge and employing abstractions on various levels, generates expressive visualizations and allows user-centric interaction metaphors. The talk will discuss several examples of knowledge-assisted visualizations of volumetric data:

Importance-driven focus of attention is a concept for automatically focusing on interesting features within a volumetric data set. The user selects a focus, i.e., object of interest, from a set of pre-defined features. The system automatically determines the most expressive view on this feature. A characteristic viewpoint is estimated by an information-theoretic framework which is based on the mutual information measure. Viewpoints change smoothly by switching the focus from one feature to another one. This mechanism is controlled by changes in the importance distribution among features in the volume.

We will explain style transfer functions which allow to combine a multitude of different shading styles in a single rendering. In the case of multiple volumetric attributes and multiple visual styles the specification of a multi-dimensional transfer function becomes challenging and non-intuitive. We describe semantic layers as a methodology for the specification of a mapping from several volumetric attributes to multiple illustrative visual styles. Semantic layers enable an expert user to specify the mapping in the natural language of her/his domain.

LiveSync utilizes deformed viewing spheres for knowledge-based navigation in the medical domain. It is a concept to synchronize 2D slice views and volumetric views of medical data sets. Through simple and intuitive picking actions on a 2D slice, the users define the anatomical structures they are interested in. The 3D volumetric view is updated automatically with the goal that the users are provided with expressive result images. To achieve this live synchronization we use a minimal set of derived information, i.e., picked point, slice view zoom, patient orientation, viewpoint history, local object shape and visibility, without the need for segmented data sets or data-specific pre-computations.

Further information on the research projects discussed in the talk is available at http://www.cg.tuwien.ac.at/research/vis/

October 30

Dag Finne and Berit Helen Bjørnhaug, Bergen Teknologioverføring AS

Title: Research results, copyrights and patents – Rights and responsibilities for University employees

Slides and articles:

October 23

Alex Feigel – Soreq NRC, Israel

Title: Going beyond entropy in analysis of evolving information exchange: from communication to sex.

Abstract: Information, like energy or food, is a resource contributing to the evolutionary success of a population and its members. It is unclear, however, why are humans unique in developing such extensive abilities to exchange and process information. This work analyses, ab initio, the required essential evolutionary conditions for the emergence of information exchange and processing skills. Analytical tools based on evolutionary game theory and the notion of mutual information have been developed for this purpose. The novelty of the suggested approach is to consider information only through correlations of responses in the course of an evolutionary competition. The results of this work provide an explanation for the longstanding puzzles of the unique position of humans in the course of evolution and of the two-fold cost of sex paradox. The method is verified using field data from combat in male spiders, demonstrating that evolutionary stable animal behavior corresponds to a new type of game theoretical equilibrium. A surprising finding is that demographic fluctuations will accelerate the development of communication, which is corroborated by the evidence of demographic bottlenecks, distinguishing human from other species? (e.g. apes) evolution line.

September 25

Markus Schumacher, Virtual Forge GmbH

Title: The Missing Link: Compliance at the Code Level

Abstract: Mastering security in complex system landscapes is a big challenge. While roles & authorizations, encryption, Single-Sign-On, etc. are well-established practices, security issues at the code level are often neglected. Bad code can lead to vulnerabilities such as backdoors, elevation of privileges, and data manipulation. This in turn can lead to violations of regulations like SOX, PCI, or Data Protection laws. In this talk, examples of GRC issues at the code level are discussed. We also show how you should address such issues right form the beginning of a new software project.

September 18

Prof. Andy R. Conn, IBM

Title: Some recent work in derivative free optimization

Abstract: Derivative free methods are amongst the most commonly used optimization techniques in practise but it is absolutely essential that they balance the geomtry of sample points with efficiency. I will present a general framework for a trust region derivative free algorithm that, for the models, assumes only that they can be made to satisfy Taylor-like error bounds. The results have broader implications (for example to, second-order trust-region methods and the connection between geometry and a (scaled) basis matrix condition number) and are of both theoretical and practical interest.

(Joint work with Katya Scheinberg and Luis Vicente.)

September 17 (Extra session!)

Note day and place: Wednesday, Sept. 17th 14:15-15:00, in Lille Auditorium.

Hans van Ditmarsch, University of Otago, NZ

Title: Unconditionally secure protocols employing card deals

Abstract: We analyze and design security protocols for computationally unlimited agents using card deals. Consider three players, of which two (Alice and Bob) want to exchange a secret while the remaining player (Eve) can be considered eavesdropper. Alice, Bob, Eve hold a, b, and c cards, respectively: these parameters (a,b,c) characterize the card deal. Initially, players only know their own hand of cards. Typically, Alice and Bob wish to learn each others' actual hand of cards (in terms of interpreted systems: their local states), whereas this should be impossible for Eve. In the well-known Russian Cards problem (the case (3,3,1)) it is additionally required that Eve may not learn any of Alice's or Bob's cards. We will give a partial characterization for which (a,b,c) Alice and Bob can exchange their hands of cards, with the additional constraint that single card ownership may not be inferred either. Some such solutions allow Eve to guess a card with better than equal odds, even though she does not know that card to be held by Alice (or by Bob). We can counter these odds by a combinatorial constraint for announcements, or by adjusting the protocol producing the announcements. An open question was whether there are protocols of length essentially larger than two, i.e., after Alice's opening announcement and Bob's response, at least one further announcement by Alice is required to successfully conclude the communication of secrets. The answer to that is: yes, there are. I will show an example, and some general results for secure local state exchange in interpreted systems.

More info: http://www.cs.otago.ac.nz/staffpriv/hans/theoryAJC.pdf, slides

August 28

Timo Ropinski

Title: Generating Visual Representations from Volumetric Data

Abstract: Volumetric data sets as acquired by medical scanners contain a multitude of information. In order to allow the domain expert to visually extract relevant information, meaningful visual representations are necessary. Usually these visual representations are generated during an exploration process, in which the optical properties assigned to the intensities contained in a volume data set are changed interactively. In this talk I will describe concepts supporting the generation of meaningful visual representations from volumetric data. Therefore, I will first briefly review existing techniques used to assign optical properties to a volume data set, before introducing an alternative sketch-based approach, which eliminates some of the major drawbacks of existing techniques. To support the spatial comprehension of the generated visual representations, I will introduce how to compute light interactions between the structures interactively extracted from a volume data set. Specifically, it will be discussed how to compute these light interactions rapidly, since immediate visual feedback has the potential to support the interactive exploration process.

August 21

Helmut Doleisch (SimVis GmbH, SimVis.at)

Title: Interactive Visual Analysis in Meteorology with SimVis

Abstract: SimVis is an interactive visual analysis technology which has been researched and developed since 2001 at the VRVis Research Center in Vienna. The original goal was to develop an supportive technology for the exploration and analysis of very large and complex data sets resulting from computational fluid dynamics simulation (CFD).

After having presented the basic concepts of the SimVis framework, the presentation will concentrate on case studies and applications from meteorological data analysis. This will also demonstrate the general applicability of the SimVis approach for data from many different sources.

In the third part of the presentation the new developments of SimVis with regard to the ongoing commercialization will be discussed, especially focusing on future plans and possibilities of cooperative research work.

Note: This department seminar talk is part of ClimaVis08, which you're also welcome to attend.

ClimaVis08 will start at 1pm and end (approx.) at 17:30

Location: Store Auditorium.

Full program here.

We will not charge any registration fee, or so, but we ask all those who plan to participate to register via eMail to Helwig Hauser, so that planning is a bit eased for us.

Thank you for helping us with that.

Spring 2008

March 6 Joseph Young, Rice University, Houston, Texas
Title: Program Transformation for Mathematical Programming

Abstract: Mathematical programming refers to a collection of methods used to model and optimize a complicated process. These processes arise in many different settings such as minimizing the operating cost of an airline or describing the optimal layout of a microprocessor. The goal of solving these problems is to find an optimal set of parameters that characterize the original system.

Modeling a system requires several choices. Simplistic models may not give useful information while complicated models may be too difficult to solve. Thus, most analysts compose and experiment with several different formulations. Unfortunately, this requires the user to maintain several different models even when one model is simply a relaxation of another.

We present a collection of new techniques that can be used to automate the transformation of one problem to another. Rather than analyzing the intricacies of these methods, we focus on general strategies that lead us to computable solutions. During our discussion, we briefly touch on how different tools from formal language design can be used to implement these strategies.

March 27 Professor Mike Fellows, School of Electrical Engineering and Computer Science, The University of Newcastle, Australia
Title: Multivariate Algorithmics: A Subject that Every Computer Scientist Should Know About

Abstract: Parameterized complexity and algorithmics has emerged over the last fifteen years as a kind of ''alternative universe'' of algorithms and complexity research, pursued by an enthusiastic and expanding, but still relatively small band of researchers. What is this subject about? Where did it come from and where is it going? What does the subject offer to computer scientists in other areas of the very large enterprise of Computer Science? The first issue this year (Jan. 2008) of The Computer Journal is a collection of surveys of various aspects of parameterized complexity and algorithmics spurred on by the declaration of the Chief Editor, Fionn Murtagh, that, ''This is a subject that every computer scientist should know about!'' The talk will try to explain why, in the context of the development of the field. The main ideas, motivations and applications will be described, and an account given of the current state of the field and the emerging broader perspective of multivariate algorithmics. For more detail, see the Foreword to the special issue of The Computer Journal.

April 10 David Wheat, Senior Lecturer in System Dynamics University of Bergen, Norway
Title: System Dynamics Modeling: Illustrations from Economics & Epidemics

Abstract: The system dynamics modeling process can be summarized as a four-step process: (1) defining problematic behavior dynamically, (2) diagramming a causal structure that serves as a hypothesis for the problematic behavior, (3) formulating, simulating, and testing a model that replicates the problematic behavior, and (4) modifying the model's structure to simulate new policies for improving the problematic behavior. The presentation will illustrate the process, using examples from epidemics and economics.

May 29 Prof. Cornelis Roos from Delft University, The Netherlands
Title: Computing safe dike heights at minimal costs

Abstract: Safe dike heights are crucial for protecting life in the Netherlands and many other regions of the world. we discuss issues that arise when modeling the probability of floods, the expected damage and measures floods. Our aim is to minimize the sum of future investing costs and expected damage over a long period (of about 300 years). We present some MINLP optimization models and a dynamic programming model, as well as some computational results.

June 5 Peter Gottschling, TU Dresden
Title: Generic High-Performance Numerics

Abstract: Recently there has been efforts to integrate concepts into the C++ language. Concepts are a kind of interface declarations with (conditional equational) axioms. Concepts allow demands on template types to be made explicit, pushing the generic programming methodology forward. In our work we have specified the properties of algebraic structures, like semi-groups and fields, in terms of concepts. Thus we can develop generic linear algebra software providing algorithmic functionality on the entire set of data types fulfilling the requirements.

The Matrix Template Library 4 (MTL4) is developed in the spirit of such generalized mathematical behavior. It provides dense and sparse matrix and vector operations for all appropriate numeric types, e.g. quaternions, intervals, multi-precision. Matrices and vectors can be nested arbitrarily. For instance, the product of a matrix of raw vector times a matrix of vectors of vectors is performed automatically as scalar-matrix product of matrix-vector products of dot products. Despite the far broader applicability, the performance of MTL4 is in the range of assembly libraries hand-tuned for each single platform.

In this presentation, we will briefly illustrate the principles of generic programming, introduce the intriguing new opportunity to embed semantic properties into C++ sources, and show their utilization in MTL4.