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.