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} $.