ColloquiaHiroshi Ishikawa - Friday, May 3 at 2:30 pm

[Margery Ishmael]

Friday, May 3, 2002
2:30 pm
Ryerson 251

HIROSHI ISHIKAWA
Courant Institute of Mathematical Sciences
New York University

"Graphs in Vision and Global Optimization"

Abstract:
Computer Vision is translation of representation. Given an image in
pixel representation, we try to make machines extract information
in quite different representations. The space of images in the pixel
representation is so vast that most of the space is occupied by
white noise. Typical natural image is very different from this; it is
more orderly than the white noise and the order comes from a highly
non-random higher-order statistics. A graph is a simple yet rich data
structure that abstracts the notion of neighborhood, which is the
simplest and most fundamental relationship between pixels in an image.
I will talk about two methods in low-level vision that utilize graph
algorithms. Each finds a global optimum in polynomial time.

The first maps a first-order Markov Random Field optimization problem
into a minimum cut problem. The theory of MRF does not explicitly
specify where to put the information on the relationship between
values at each sites. That information is implicitly given in the
statistics. Thus a model must be given before we can talk about what
to do with the information. The present method essentially gives
prescribed places for storing some of the most relevant statistical
information, which gives the graph algorithm the structured data to
work on. The exact condition of its applicability is shown to be the
convexity of the prior term in the MRF. Applications include stereo,
segmentation and image restoration.

The second method finds an optimal cycle in an image and in the
higher dimensional spaces that arise in vision problems. It uses a
minimum ratio cycle algorithm to find a cycle with minimum energy in
a graph. In the case of (2D) images, the energy can depend not only
on the cycle itself but also on the region surrounded by the cycle.
Because of this, the technique unifies the two competing views of
boundary and region segmentation. Here the edges in the graph are
used to represent line elements in the image, rather than the
neighborhood structure. It turns out that the graph being directed
instead of undirected is essential for finding nontrivial contours,
by looking for oriented cycles. It also allows us to treat the
directed edges as vectors and use Green's theorem.
http://www.cs.nyu.edu/phd_students/ishikawa/

Host: Yali Amit

*The talk will be followed by refreshments in Ryerson 255*
Persons who need assistance should call 773.834.8977


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margery Ishmael
Secretary to the Chairman, Department of Computer Science
The University of Chicago
tel. 773.834.8977  fax. 773.702.8487
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=