Wednesday March 20 4:00PM in CS 1325
Olga Veksler
NEC Research Institute
Graph Algorithms for Stereo Correspondence

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
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 that can be matched reliably.  This approach
produces only semi-dense results, but they are more accurate than other approaches,
particularly for low-texture images.