Fast Belief Propagation for Early Vision


May 24, 2004


Daniel Huttenlocher


Cornell University


Markov random field (MRF) models provide a robust and unified framework for early vision problems such as stereo, optical flow and image restoration. Inference algorithms based on graph cuts and belief propagation yield accurate results, but despite recent advances are often still too slow for practical use. We present three new algorithmic techniques that substantially improve both the running time and the memory utilization of loopy belief propagation for early vision problems. Taken together these techniques speed up the standard algorithm several by orders of magnitude. For example, for stereo images in the Middlebury benchmark we improve the running time from several minutes to about a second. In practice we obtain results that achieve the accuracy of global methods such as MRF’s while being comparable in speed to local methods such as correlation.

This is joint work with Pedro Felzenszwalb.


Daniel Huttenlocher

Dan Huttenlocher is the John P. and Rilla Neafsey Professor of Computing, Information Science and Business at Cornell University, where he holds a joint appointment in the Computer Science Department and the Johnson Graduate School of Management. His research interests are in computer vision, geometric algorithms, interactive document systems, financial trading technology, and IT strategy. Huttenlocher has 24 U.S. patents, has published more than 75 technical papers, and has been recognized on several occasions for his teaching and research, including being named an NSF Presidential Young Investigator in 1990, the New York State Professor of the Year in 1993, and a Stephen H. Weiss Fellow in 1996. At Cornell, Huttenlocher chaired the Provost’s task force that led to the creation of the new Faculty of Computing and Information Science. In addition to his academic work, Huttenlocher has served as CTO of Intelligent Markets and was on the senior management team at Xerox PARC.