Stereo Matching Using Belief Propagation
|
Abstract—In this paper, we formulate the stereo matching problem as a Markov network and solve it using Bayesian belief propagation. The stereo Markov network consists of three coupled Markov random fields that model the following: a smooth field for depth/disparity, a line process for depth discontinuity, and a binary process for occlusion. After eliminating the line process and the binary process by introducing two robust functions, we apply the belief propagation algorithm to obtain the maximum a posteriori (MAP) estimation in the Markov network. Other low-level visual cues (e.g., image segmentation) can also be easily incorporated in our stereo model to obtain better stereo results. Experiments demonstrate that our methods are comparable to the state-of-the-art stereo algorithms for many test cases.
[1] 787 H. Baker and T. Binford, Depth from Edge and Intensity Based Stereo Proc. Int'l Joint Conf. Artificial Intelligence, 1981.
[2] P.N. Belhumeur, “A Bayesian Approach to Binocular Stereopsis,” Int'l J. Computer Vision, vol. 19, no. 3, pp. 237-260, 1996.
[3] S. Birchfield and C. Tomasi, “A Pixel Dissimilarity Measure that Is Insensitive to Image Sampling,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 4, pp. 401-406, Apr. 1998.
[4] M.J. Black and A. Rangarajan, “On the Unification of Line Processes, Outlier Rejection, and Robust Statistics with Applications in Early Vision,” Int'l J. Computer Vision, vol. 19, no. 1, pp. 57-91, 1996.
[5] A. Blake and A. Zisserman, Visual Reconstruction. MIT Press, 1987.
[6] A.F. Bobick and S.S. Intille, Large Occlusion Stereo Int'l J. Computer Vision, vol. 33, no. 3, pp. 1-20, 1999.
[7] R.C. Bolles, H.H. Baker, and M.J. Hannah, The Jisct Stereo Evaluation Proc. DARPA Image Understanding Workshop, 1993.
[8] Y. Boykov, O. Veksler, and R. Zabih, Fast Approximate Energy Minimization via Graph Cuts Proc. Int'l Conf. Computer Vision, 1999.
[9] D. Comaniciu and P. Meer, Robust Analysis of Feature Spaces: Color Image Segmentation Proc. 1997 IEEE Conf. Computer Vision and Pattern Recognition, pp. 750-755, 1997.
[10] I. Cox, S. Hingorani, and S. Rao, “A Maximum Likelihood Stereo Algorithm,” Computer Vision and Image Understanding, vol. 63, no. 3, pp. 542–567, 1996.
[11] W.T. Freeman, E.C. Pasztor, and O.T. Carmichael, “Learning Low-Level Vision,” Int'l J. Computer Vision, vol. 20, no. 1, pp. 25-47, 2000.
[12] D. Geiger and F. Girosi,“Parallel and deterministic algorithms from MRFs: Surface reconstruction,” IEEE Transactions on PAMI, vol. 13, no. 5, pp. 401-412, May 1991.
[13] D. Geiger, B. Ladendorf, and A. Yuille, “Occlusions and Binocular Stereo,” Int'l J. Computer Vision, vol. 14, pp. 211-226, 1995.
[14] S. Geman and D. Geman, Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, no. 6, pp. 721-741, 1984.
[15] W. Gilks, S. Richardson, and D. Spiegelhalter, Markov Chain Monte Carlo in Practice. Chapman and Hall, 1996.
[16] H. Hirschmueller, Improvements in Real-Time Correlation-Based Stereo Vision Proc. IEEE Workshop Stereo and Multi-Baseline Vision, 2001.
[17] B.K.P. Horn and M.J. Brooks, “The Variational Approach to Shape from Shading,” Computer Vision, Graphics, and Image Processing, vol. 33. no. 2, pp. 174-208, 1986.
[18] H. Ishikawa and D. Geiger, “Occlusions, Discontinuities, and Epipolar Lines in Stereo,” Proc. European Conf. Computer Vision, pp. 232-248, 1998.
[19] M.I. Jordan, ed., Learning in Graphical Models. NATO Science Series, Kluwer Academic, 1998.
[20] T. Kanade and M. Okutomi, “A Stereo Matching Algorithm with an Adaptive Window: Theory and Experiment,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, pp. 920-932, 1994.
[21] S. Kang, R. Szeliski, and J. Chai, Handling Occlusions in Dense Multi-View Stereo Proc. Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 103-110, 2001.
[22] V. Kolmogorov and R. Zabih, Computing Visual Correspondence with Occlusions via Graph Cuts Proc. Int'l Conf. Computer Vision, 2001.
[23] L. Rudin, S. Osher, and E. Fatemi, “Nonlinear Total Variation Based Removal Algorithm,” Physica D, vol. 60, pp. 259-268, 1992.
[24] A. Luo and H. Burkhardt, “An Intensity-Based Cooperative Bidirectional Stereo Matching with Simultaneous Detection of Discontinuities and Occlusions,” Int'l J. Computer Vision, vol. 15, pp. 171-188, 1995.
[25] D. Marr and T.A. Poggio, Cooperative Computation of Stereo Disparity Science, vol. 194, no. 4262, pp. 283-287, 1976.
[26] D. Mumford and J. Shah, Optimal Approximations by Piecewise Smooth Functions and Variational Problems Comm. Pure and Applied Math., 1988.
[27] J. Pearl, Probabilistic Reasoning in Intelligent Systems. San Mateo, Calif.: Morgan Kaufman, 1988.
[28] T.W. Ryan, R.T. Gray, and B.R. Hunt, Prediction of Correlation Errors in Stereo-Pair Images Optical Eng., vol. 19, no. 3, pp. 312-322, 1980.
[29] D. Scharstein and R. Szeliski, Stereo Matching with Nonlinear Diffusion Int'l J. Computer Vision, vol. 28, no. 2, pp. 155-174, 1998.
[30] D. Scharstein and R. Szeliski, “A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms,” IJCV, vol. 47, no. 1-3, pp. 7-42, Apr. 2002.
[31] J. Shade, S. Gortler, L.-W. He, and R. Szeliski, “Layered Depth Images,” Proc. SIGGRAPH '98, pp. 231-242, 1998.
[32] H. Tao, H. Sawhney, and R. Kumar, A Global Matching Framework for Stereo Computation Proc. Int'l Conf. Computer Vision, pp. 532-539, 2001.
[33] O. Veksler, Stereo Matching by Compact Windows via Minimum Ratio Cycle Proc. Int'l Conf. Computer Vision, 2001.
[34] J.S. Yedidia, W.T. Freeman, and Y. Weiss, Bethe Free Energy, Kikuchi Approximations, and Belief Propagation Algorithms Technical Report TR-2001-16, Mitsubishi Electric Reseach, 2001.
[35] R. Zabih and J. Woodfill, Non-Parametric Local Transforms for Computing Visual Correspondence Proc. European Conf. Computer Vision, 1994.
Index Terms:
Stereoscopic vision, belief propagation, Markov network, Bayesian inference.
Citation:
Jian Sun, Nan-Ning Zheng, Heung-Yeung Shum, "Stereo Matching Using Belief Propagation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 7, pp. 787-800, July 2003, doi:10.1109/TPAMI.2003.1206509
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb