Winter 2002/03

former semesters colloquium in Berlin

Time: Mondays, 14:15 - 15:45
Location: IFW B42
(unless stated otherwise)

Organizers: CGC faculty at ETH Zurich
Contact: Emo Welzl

November 25, 2002

Hans-Andrea Loeliger
ETH Zürich

Signal Processing with Factor Graphs

Naveen Garg
IIT Delhi / MPI Saarbrücken

Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems

Torben Hagerup
Johann Wolfgang Goethe-Universität Frankfurt am Main

Simpler Computation of Single-Source Shortest Paths in Linear Average Time

Gábor Szekely
ETH Zurich

Shape characterization in 2D and 3D by Voronoi skeletons

Factor graphs are graphical models with origins in coding theory. Closely related graphical models are Bayesian networks and Markov random fields; there are also close relations to basic notions in system theory. The sum-product algorithm (also called ``belief propagation''), which operates by message passing in the factor graph, subsumes many important algorithms in coding, signal processing, and artificial intelligence. We present these fundamentals and give several examples of ongoing research in signal processing.

Monday, December 02, 2002, 14:15 - 15:45, IFW B42

In this talk I will present a fully polynomial time approximation scheme (FPTAS) for the optimum fractional solution to the Steiner forest problem. This can easily be generalized to obtain an FPTAS for a hitting set problem on a collection of clutters. The algorithm is very simple to describe and has a running time better than those of existing algorithms. For clutters that do not satisfy the MFMC property (e.g., k-spanner, multicommodity flows, T-cuts, T-joins etc.), this is the only algorithm known (other than the generic algorithms for linear programming) for solving such hitting set problems.

Monday, December 09, 2002, 14:15 - 15:45, IFW B42

Meyer as well as Goldberg recently described algorithms that solve the single-source shortest-paths problem in linear average time on graphs with random edge lengths drawn from the uniform distribution on [0,1]. The talk will show how the same result can be obtained through a simple combination of standard data structures and with a trivial probabilistic analysis.

Monday, December 16, 2002, 14:15 - 15:45, IFW B42

Shape is perhaps the most characteristic feature of the objects in the world around us. Our visual system is very efficient in perceiving, analyzing and comparing shapes which provides major cues for the visual interpretation of our environment. Therefore it is to be expected that computerized image interpretation and vision systems will need efficient tools for dealing with the shape of objects.

The systematic scientific study of the shape of living objects goes back to the beginning of the last century. In his seminal work D'Arcy Thompson studied the laws and diversity of biological form and shape. While his work is basically descriptive and non-mathematical, D'Arcy Thompson already identified the decisive role of axial growth processes in forming the shape of living objects.

Half a century later Blum found an appropriate tool for the rigorous mathematical formulation of D'Arcy Thompson's ideas. He has shown that the concept of local symmetry captures axial growth efficiently and can be handled within the framework of a coherent mathematical theory of the symmetry axis transform. The skeletonization process, as proposed by Blum selects specific axes of axial symmetry out of the the enormous number of local symmetries present in even very simple objects leading to the reduction of the symmetry relations of an object to a small, manageable subset.

The symmetry axis transform is defined as a continuous transformation on a continuous plane. However, we need algorithms for its effective generation for the analysis of sensed image data, which are usually provided in digital form. This means we need procedures for discrete approximation of this essentially continuous operation. The concept of the Voronoi skeleton offers a promising way to skeletonize discretized images in a geometrically correct way. The approach is semi-continuous in that it represents objects by their sampled boundary and then calculates the Voronoi Diagram of the discrete boundary points.

The talk will summarize the most important results for the generation and simplification of 2D Voronoi skeletons. The basic topological properties of the skeleton will be investigated and the generation of an overall hierarchy of the skeletal axes will be presented. It will be shown, that while the skeletal concept readily generalizes to three dimensions, the more complex skeletal topology prevents to carry over the pruning methods to 3D and only heuristic procedures are known today for the simplification of the skeletons of volumetric objects. First results will be presented on complex anatomical organs, like the vascular system and the human brain.

Former semesters

Summer 2002 , Winter 2001/02 , Summer 2001 , Winter 2000/01 , Summer 2000 , Winter 1999/2000 , Summer 1999 , Winter 1998/99 , Summer 1998 , Winter 1997/98 , Summer 1997

Last modified on 2003-01-09 20:06:10 by Falk Tschirschnitz <tschirsc@inf.ethz.ch>

Copyright © 2000-2001