Fast Graph Algorithms for Bayesian Computer Vision

Ramin Zabih

Cornell University


Many problems in computer vision can be naturally described in a Bayesian framework. Unfortunately, the resulting optimization problems are highly intractable, because the search space has many thousands of dimensions. I will present some fast algorithms for solving these problems that rely on graph cuts. These algorithms produce answers with quality guarantees: the output is a local minimum even when very large moves are allowed. Experimental stereo results from real data with ground truth suggest that our results are over four times more accurate than previous methods.

This is joint work with Yuri Boykov and Olga Veksler.

Ramin Zabih did his undergraduate work at MIT, and received a PhD in Computer Science from Stanford in 1994. He is an Assistant Professor of Computer Science at Cornell University. His research area is computer vision, where he focuses on low-level problems and on applications. He is currently organizing a workshop on graph algorithms in computer vision, which is planned for ICCV in 1999. He can be contacted at

Edited by Leonidas Guibas