April 2002

BACK   

Graph algorithms have recently gained popularity in computer vision. They provide powerful combinatorial optimization tools for many vision problems. In the last four years I have been developing graph based algorithms for motion, segmentation, edge detection, image restoration, and stereo correspondence. In this talk I will focus on stereo, for three reasons. First, stereo shares a common structure with many other vision problems, and presents a similar set of challenges. Second, graph algorithms have achieved significant recent progress in solving stereo. Last, an objective evaluation of stereo algorithms on real images is now possible using the Middlebury stereo database of with dense ground truth.

Traditional approaches to stereo correspondence can be roughly divided in two groups: local and global. A central problem for the local methods is selecting an appropriate window shape. I will show how the minimum ratio cycle algorithm can optimize the search for window shapes. A central problem in the global approach is the optimization of the objective function. I will show how graph cut algorithms can efficiently compute provably good approximations to a certain class of objective functions.

The local approach is faster but works well only for high texture images. The global approach is slower but it can handle medium texture images. However, low texture images, which are common in office environments, cause problems even for the global approach. I will describe a new approach to stereo correspondence which using graph cuts extracts only the salient regions, that is regions which can be matched reliably. This approach produces only semi dense results, but they are more accurate than other approaches, particularly for low texture images.

BACK

Last Updated: April 17, 2002