May 2002

BACK   

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.

BACK

Last Updated: April 29, 2002