Prof. Takeshi Tokuyama (Tohoku University, Japan)

Geometric Optimization Problems in Image Segmentation

Consider an n x m pixel grid G. In a monochromatic (resp. color) digital picture, each pixel p has a real value (resp. Three dimensional vector) f(p) representing the brightness (resp. color). Thus, a digital picture is a function f on G. Therefore, an image processing problem can be considered as an optimization problem that computes a function Φ in F approximating f, where F is a family of well-behaved functions.

For example, the image segmentation problem is a problem to separate an image from background in the picture: Here, the output function Φ should be the characterizing function of the image region, that is, Φ(p)= a if p is a pixel in the image, and Φ(p) = b otherwise, where a and b are brightness (or color) representing the image and background, respectively.
We discuss the relation of the complexities of the problems and the geometric/combinatorial properties of the family F.

Zeit: Montag, 26. Oktober 2009, 17:30 Uhr
Ort: Hörsaal -101, Informatik-Hauptgebäude (Geb. 50.34), Am Fasanengarten 5, 76131 Karlsruhe