Markov random ?eld models provide a robust and uni?ed framework for early vision problems such as stereo and image restoration. Inference algorithms based on graph cuts and belief propagation have been found to yield accurate results, but are often too slow for practical use. I will describe some algorithmic techniques that substantially improve the running time of the belief propagation approach. One of the techniques uses min-convolutions to make the running time linear rather than quadratic in the number of possible labels for each pixel.
Another technique speeds up and reduces the memory usage of belief propagation on grid graphs. A third technique is a multi-grid method that makes it possible to obtain good results with a small number of message passing iterations. Taken together these techniques speed up the standard algorithm by several orders of magnitude. In practice we obtain results that are as accurate as those of other global methods while being nearly as fast as purely local methods.
Copyright. All Rights Reserved.