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.

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.

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.

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.

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

Copyright © 2000-2001