Speaker: Takeshi Tokuyama

Title: Geometric optimization in grid topology and related combinatorics

Abstract:

Consider an $n \times m$ pixel grid $G$. In a monochromatic (resp. 
color) digital picture, each pixel $p$ has is 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 $\phi \in {\cal F} $ 
approximating $f$, where ${\cal F}$ is a family of {\em 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 $\phi$ 
should be the characterizing function of the image region, that is, 
$\phi(p)= a$ if $p$ is a pixel in the image, and $\phi(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 ${\cal F} $.