Efficient belief propagation for early vision-英文文献.pdf

Efficient Belief Propagation for Early Vision Pedro F. Felzenszwalb and Daniel P. Huttenlocher Department of Computer Science, Cornell University pff,dph@cs.cornell.edu Abstract ers for solving stereo problems, and are too slow for prac- tical use when solving optical flow and image restoration Markov random field models pr ovide a robust and unified problems. Thus one is faced with choosing between these fr amework for early vision pr oblems such as stereo, opti- methods, which produce good results but are slow, and lo- calflow and image restoration. Inference algorithms based cal methods which produce substantially poorer results but on graph cuts and belief pr opagation yield accurate results, are fast. In this paper we present three new algorithmic but despite recent advances are often still too slowfor pr ac- techniques that substantially improve the running time of tical use. In this paper we pr esent new algorithmic tech- belief propagation (BP) for solving early vision problems. niques that substantially improve the running time of the Taken together these techniques speed up the standard al- belief pr opagation approach. One of our techniques re- gorithm by several orders of magnitude, making its running duces the complexity of the inference algorithm to be linear time competitive with local methods. In the case of stereo rather than quadratic in the number of possible labels for we obtain results with the same degree of accuracy as stan- each pixel, which is important for pr oblems such as opti- dard BP or graph cuts algorithms in about one second per