摘要
本文针对计算机立体视觉中的立体匹配中存在的问题,对双目立体校正、基于马尔可夫随机场的置信传播算法的优化及其高性能实现和立体匹配用于静态场景目标提取进行了研究。
本文主要工作和创新点如下:
1)针对传统立体校正需要对摄像机进行标定以获取摄像机参数的问题,提出了一种无需摄像机参数的简便的立体校正方法。该方法先对待校正图像对进行特征点匹配,得到两幅图像间的空间坐标相对关系,然后利用极线几何约束将两幅图像的对应点校正到同一水平线上,完成对立体图像对的校正。实验表明,这种校正方法能有效的校正未知摄像机参数的图像对。
2)针对全局立体匹配中基于马尔可夫随机场的置信传播算法中计算时间随消息迭代次数线性增长的问题,提出了一种基于自适应机制的分层置信传播方法。该方法利用分层置信传播算法中大部分消息快速收敛的性质,引入消息收敛的条件判断,在迭代上限相同情况下,减少了算法的迭代次数,缩减了整体迭代的时间。实验表明,与传统HBP相比,该方法有效的缩减了计算时间,而且计算时间对整体迭代上限不敏感。
3)针对分层置信传播算法难以快速实现的问题,提出了一种利用GPU对其进行高性能的并行计算的方法。该方法结合CUDA编程的特点,分析了分层置信传播算法的特点,对其进行像素级的并行化处理,使计算的吞吐率有效增加。实验表明,在相同的匹配水平下,该方法具有比较高的加速比。
4)针对目前现有的立体视频目标提取方法主要依赖于运动场,提出了一种基于精确视差的静态目标分割方法。该方法首先通过基于图像分割与平面拟合的自适应全局立体匹配算法得到得到包含场景深度信息的精确视差图。然后由视差图的特性,先对其进行前后景分离,然后对前景进行遍历,得到其类间方差最大的灰度分割方法,完成对目标的提取。实验表明,该方法分割结果准确,目标提取效果好。
To solve those problems on stereo vision in computer vision, we have studied on stereo rectification, the optimization and parallelization of belief propagation based on MRF and the static object segmentation based on disparity map.
The main work and innovation of this dissertation are as follows:
1) A method of stereo rectification with uncalibrated cameras is proposed.In this method,we at first detect and match the interest points to achieve the spatial relationship between the two images, and then finish the rectification by finding the projections in which the epipolar lines run parallel with the x-axis according to the epipolar geometry. Experimental results show that this method can rectify the stereo pairs accurately and meet the requirement of stereo matching.
2) A self-adaptive algorithm with convergence detection to reduce the computational complexity of HBP is proposed. Convergence detection is introduced to stop the iterations of messages which are already converged to optimal values. Thus the overall computational time is reduced. Experimental results show the self-adaptive algorithm reduces computational time effectively, and the computational time is insensitive with iteration up bound. The convergence detection methodology can also be applied to other HBP related applications.
3) An efficient CUDA-based graphic processing unit is introduced into implementation of the belief propagation algorithm. After analysis for the belief propagation algorithm, we achieve the parallelization on pixel-level by CUDA.Experimental results show that this method can be used to speed up stereo image processing without much loss of accuracy.
4) An object segmentation algorithm based on accurate disparity map is presented. The accurate disparity map is available by a stereo match algorithm including initial matching cost estimation, mismatched pixels checking, plane estimation and self-adaptive hierarchical belief-propagation. Then, self-adaptive threshold segmentation is performed on the result that is achieved from the first step. Experimental results show that the proposed algorithm is an effective object extraction method suitable for stereoscopic static scenes and image sequences with unitary global motion.
引文
[1]章毓晋.图像理解与计算机视觉[J].北京:清华大学出版社, 2000,
[2] D.Marr. Vision [J]. WHFreeman and Company, 1982, [M] San Francisco(
[3] L.Roberts. Machine Perception of three-dimensional solids [J]. Optical and Electroptical Information Processing, 1965, 159-97.
[4] R. Hartley A Z. Multiple View Geometry in Computer Vision (2nd edition) [J]. Cambridge University Press, 2003,
[5] S.T.Barnard M a F. Computational Stereo [J]. ACM Comput Surv, 1982, 14(4)(553-72.
[6]孙龙祥等.深度图像分析[J].北京:电子工业出版社, 1996,
[7] Scharstein D, Szeliski R. High-accuracy stereo depth maps using structured light; proceedings of the Computer Vision and Pattern Recognition, 2003 Proceedings 2003 IEEE Computer Society Conference on, F 18-20 June 2003, 2003 [C].
[8] Scharstein D, Szeliski R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms [J]. Int J Comput Vision, 2002, 47(1-3): 7-42.
[9] Dhond U R, Aggarwal J K. Structure from stereo-a review [J]. Systems, Man and Cybernetics, IEEE Transactions on, 1989, 19(6): 1489-510.
[10] Koschan A. What is New in Computational Stereo Since 1989:A Survey of Current Stereo Papers [J]. Technical Report 1989, 93—22(
[11] Brown M Z, Burschka D, Hager G D. Advances in computational stereo [J]. Ieee T Pattern Anal, 2003, 25(8): 993-1008.
[12] Klaus A, Sormann M, Karner K. Segment-Based Stereo Matching Using Belief Propagation and a Self-Adapting Dissimilarity Measure; proceedings of the Pattern Recognition, 2006 ICPR 2006 18th International Conference on, F, 2006 [C].
[13] Yang Q X, Wang L, Yang R G, et al. Stereo Matching with Color-Weighted Correlation, Hierarchical Belief Propagation, and Occlusion Handling [J]. Ieee T Pattern Anal, 2009, 31(3): 492-504.
[14] Zeng-Fu W, Zhi-Gang Z. A region based stereo matching algorithm using cooperative optimization; proceedings of the Computer Vision and PatternRecognition, 2008 CVPR 2008 IEEE Conference on, F, 2008 [C].
[15] Jian S, Yin L, Kang S B, et al. Symmetric stereo matching for occlusion handling; proceedings of the Computer Vision and Pattern Recognition, 2005 CVPR 2005 IEEE Computer Society Conference on, F 20-25 June 2005, 2005 [C].
[16] Sun J, Zheng N N, Shum H Y. Stereo matching using belief propagation [J]. Ieee T Pattern Anal, 2003, 25(7): 787-800.
[17]文贡坚周.基于视差点的大遮挡检测和立体匹配方法[J].软件学报, 2005, 16(15)(708-17.
[18]周修芝文,王润生.自适应窗口快速立体匹配[J].计算机学报, 2006, 29(3)(473-9.
[19] Huang X F. Cooperative optimization for energy minimization in computer vision: A case study of stereo matching [J]. Pattern Recognition, 2004, 3175(302-9.
[20]徐奕,周军.立体视觉匹配技术[J].计算机工程与应用, 2003, 15(1-6.
[21] Guofeng Z, Xueying Q, Wei H, et al. Robust Metric Reconstruction from Challenging Video Sequences; proceedings of the Computer Vision and Pattern Recognition, 2007 CVPR '07 IEEE Conference on, F 17-22 June 2007, 2007 [C].
[22] Zhang G F, Hua W, Qin X Y, et al. Stereoscopic video synthesis from a monocular video [J]. Ieee T Vis Comput Gr, 2007, 13(4): 686-96.
[23] Zhang G F, Qin X Y, An X B, et al. As-consistent-As-possible compositing of virtual objects and video sequences [J]. Comput Animat Virt W, 2006, 17(3-4): 305-14.
[24] Lhuillier M, Quan L. Match propagation for image-based modeling and rendering [J]. Ieee T Pattern Anal, 2002, 24(8): 1140-6.
[25]李鸣翔贾.基于自适应聚合的立体视觉合作算法[J].软件学报, 2008, 19(7)(1674-82.
[26] Li H, Chen G. Segment-based stereo matching using graph cuts; proceedings of the Computer Vision and Pattern Recognition, 2004 CVPR 2004 Proceedings of the 2004 IEEE Computer Society Conference on, F, 2004 [C].
[27]陈旺张茂军,熊志辉.基于区域边界约束和图割优化的稠密匹配算法[J].软件学报, 2008, 16(6)(960-9.
[28] Felzenszwalb P F, Huttenlocher D P. Efficient belief propagation for early vision [J]. Int J Comput Vision, 2006, 70(1): 41-54.
[29] Jia L X a J. Stereo Matching: An Outlier Confidence Approach [J]. In European Conference on Computer Vision - Eccv 2006, Pt 2, Proceedings, 2006,
[30] Shah J. A nonlinear diffusion model for discontinuous disparity and half-occlusions in stereo; proceedings of the Computer Vision and Pattern Recognition, 1993 Proceedings CVPR '93, 1993 IEEE Computer Society Conference on, F 15-17 Jun 1993, 1993 [C].
[31] Comaniciu D, Meer P. Mean shift: A robust approach toward feature space analysis [J]. Ieee T Pattern Anal, 2002, 24(5): 603-19.
[32] Qingxiong Y, Liang W, Ruigang Y, et al. Stereo Matching with Color-Weighted Correlation, Hierarchical Belief Propagation, and Occlusion Handling [J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2009, 31(3): 492-504.
[33] Taguchi Y, Wilburn B, Zitnick C L. Stereo reconstruction with mixed pixels using adaptive over-segmentation; proceedings of the Computer Vision and Pattern Recognition, 2008 CVPR 2008 IEEE Conference on, F 23-28 June 2008, 2008 [C].
[34] Gelautz. M B a M. Graph-based surface reconstruction from stereo pairs using image segmentation [J]. Proceedings of the SPIE - The International Society for Optical Engineering, 2005, 5665(288-99.
[35] Dongbo M, Kwanghoon S. Cost Aggregation and Occlusion Handling With WLS in Stereo Matching [J]. Image Processing, IEEE Transactions on, 2008, 17(8): 1431-42.
[36] Hosni A, Bleyer M, Gelautz M, et al. Local stereo matching using geodesic support weights; proceedings of the Image Processing (ICIP), 2009 16th IEEE International Conference on, F 7-10 Nov. 2009, 2009 [C].
[37] Kuk-Jin Y, In-So K. Locally adaptive support-weight approach for visual correspondence search; proceedings of the Computer Vision and Pattern Recognition, 2005 CVPR 2005 IEEE Computer Society Conference on, F, 2005 [C].
[38] Yoon K J, Kweon I S. Adaptive support-weight approach for correspondence search [J]. Ieee T Pattern Anal, 2006, 28(4): 650-6.
[39] W.Zucker G L a S. Differential Geometric Consistency Extends Stereo to Curved Surfaces [J]. European Conference on Computer Vision, 2006, 44-57.
[40] Zucker G L a S W. Stereo for Slanted Surfaces: First Order Disparities and Normal Consistency [J]. Energy Minimization Methods in Computer Vision and Pattern Recognition, 2005, 617-32.
[41] Jong Dae Oh S M a C-C J K. Stereo matching via disparity estimation and surface modeling [J]. Computer Vision and Pattern Recognition, 2007, 1-8.
[42] Di Stefano L, Marchionni M, Mattoccia S. A fast area-based stereo matching algorithm [J]. Image Vision Comput, 2004, 22(12): 983-1005.
[43] Kanade T, Okutomi M. A Stereo Matching Algorithm with an Adaptive Window - Theory and Experiment [J]. Ieee T Pattern Anal, 1994, 16(9): 920-32.
[44] Hannah M J: STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE, 1974.
[45] Anandan P. A computational framework and an algorithm for the measurement of visual motion [J]. Int J Comput Vision, 1989, 2(3): 283-310.
[46] Matthies L, Kanade T, Szeliski R. Kalman filter-based algorithms for estimating depth from image sequences [J]. Int J Comput Vision, 1989, 3(3): 209-38.
[47] Thirion J P. Image matching as a diffusion process: an analogy with Maxwell's demons [J]. Medical image analysis, 1998, 2(3): 243-60.
[48] Kanade T, Kano H, Kimura S, et al. Development of a video-rate stereo machine, F, 1995 [C]. Published by the IEEE Computer Society.
[49] Brett S. Digital video processing [M]. Google Patents. 2000.
[50] Black M J, Anandan P. A framework for the robust estimation of optical flow, F, 1993 [C]. IEEE.
[51] Black M J, Rangarajan A. On the unification of line processes, outlier rejection, and robust statistics with applications in early vision [J]. Int J Comput Vision, 1996, 19(1): 57-91.
[52] Scharstein D, Szeliski R. Stereo matching with nonlinear diffusion [J]. Int J Comput Vision, 1998, 28(2): 155-74.
[53] Birchfield S, Tomasi C. Depth discontinuities by pixel-to-pixel stereo; proceedings of the Computer Vision, 1998 Sixth International Conference on,F 4-7 Jan 1998, 1998 [C].
[54] Yoon K J, Kweon I S. Stereo matching with the distinctive similarity measure [J]. 2007,
[55] Poggio D M a T. Cooperative computation of stereo disparity [J]. Science, 1976, 194(283-7.
[56] Scharstein D. Matching images by comparing their gradient fields, F, 1994 [C]. IEEE.
[57] Seitz P. Using local orientational information as image primitive for robust object recognition, F, 1989 [C].
[58] Cox I J, Roy S, Hingorani S L. Dynamic histogram warping of image pairs for constant image brightness, F, 1995 [C]. Published by the IEEE Computer Society.
[59] Gu Q, Zhou J. A novel similarity measure under Riemannian metric for stereo matching, F, 2008 [C]. IEEE.
[60] Okutomi M, Kanade T. A multiple-baseline stereo [J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1993, 15(4): 353-63.
[61] Kang S B, Webb J A, Zitnick C L, et al. A multibaseline stereo system with active illumination and real-time image acquisition, F, 1995 [C]. Published by the IEEE Computer Society.
[62] Arnold R D: STANFORD UNIV CA DEPT OF COMPUTER SCIENCE, 1983.
[63] Bobick A F, Intille S S. Large occlusion stereo [J]. Int J Comput Vision, 1999, 33(3): 181-200.
[64] Kang S B, Szeliski R, Chai J. Handling occlusions in dense multi-view stereo [J]. 2001,
[65] Okutomi M, Kanade T. A locally adaptive window for signal matching [J]. Int J Comput Vision, 1992, 7(2): 143-62.
[66] Veksler O. Stereo correspondence with compact windows via minimum ratio cycle [J]. Ieee T Pattern Anal, 2002, 1654-60.
[67] Boykov Y, Veksler O, Zabih R. A variable window approach to early vision [J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1998, 20(12): 1283-94.
[68] Grimson W E L, Laboratory M I O T a I. Computational experiments with a feature based stereo algorithm [M]. Citeseer, 1984.
[69] Pollard S B, Mayhew J E, Frisby J P. PMF: A stereo correspondence algorithm using a disparity gradient limit [J]. Perception, 1985,
[70] Prazdny K. Detection of binocular disparities [J]. Biol Cybern, 1985, 52(2): 93-9.
[71] Yoon K J, Kweon I S. Locally adaptive support-weight approach for visual correspondence search [J]. 2005,
[72] Tombari F, Mattoccia S, Di Stefano L. Segmentation-based adaptive support for accurate stereo correspondence [J]. Advances in Image and Video Technology, 2007, 427-38.
[73] Szeliski R, Hinton G. Solving random-dot stereograms using the heat equation, F, 1985 [C].
[74] Barnard S T. Stochastic stereo matching over scale [J]. Int J Comput Vision, 1989, 3(1): 17-32.
[75] Geiger D, Girosi F. Parallel and deterministic algorithms from MRFs: Surface reconstruction [J]. Ieee T Pattern Anal, 1991, 401-12.
[76] Marroquin J, Mitter S, Poggio T. Probabilistic solution of ill-posed problems in computational vision [J]. Journal of the American Statistical Association, 1987, 82(397): 76-89.
[77] Roy S, Cox I J. A maximum-flow formulation of the n-camera stereo correspondence problem, F, 1998 [C]. IEEE.
[78] Veksler O. EFFICIENT GRAPH-BASED ENERGY MINIMIZATION [D]; Cornell University, 1999.
[79] Kolmogorov V, Zabih R. Computing visual correspondence with occlusions using graph cuts [J]. 2001,
[80] Ishikawa H, Geiger D. Occlusions, discontinuities, and epipolar lines in stereo [J]. Computer Vision?aECCV'98, 1998, 232.
[81] Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts [J]. Ieee T Pattern Anal, 2001, 1222-39.
[82] Boykov Y, Kolmogorov V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision [J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2004, 26(9): 1124-37.
[83] Boykov Y, Veksler O, Zabih R. Markov random fields with efficient approximations, F, 1998 [C]. IEEE.
[84] Birchfield S, Tomasi C. Multiway cut for stereo and motion with slanted surfaces, F, 1999 [C]. Published by the IEEE Computer Society.
[85] Belhumeur P N. A Bayesian approach to binocular steropsis [J]. Int J Comput Vision, 1996, 19(3): 237-60.
[86] Belhumeur P N, Mumford D. A Bayesian treatment of the stereo correspondence problem using half-occluded regions, F, 1992 [C]. IEEE.
[87] Cox I J, Hingorani S L, Rao S B, et al. A maximum likelihood stereo algorithm [J]. Comput Vis Image Und, 1996, 63(3): 542-67.
[88] Li G, Zucker S W. Surface geometric constraints for stereo in belief propagation [J]. 2006,
[89] Geiger D, Ladendorf B, Yuille A. Occlusions and binocular stereo [J]. Int J Comput Vision, 1995, 14(3): 211-26.
[90] Ohta Y, Kanade T. Stereo by intra-and inter-scanline search using dynamic programming [M]. Carnegie-Mellon University, Dept. of Computer Science, 1983.
[91] Marroquin J. Design of cooperative networks [J]. 1983,
[92] Marr D, Poggio T. Cooperative computation of stereo disparity [J]. Science, 1976, 194(4262): 283.
[93] Horn B K P, Schunck B G. Determining optical flow [J]. Artificial intelligence, 1981, 17(1-3): 185-203.
[94] Lucas B D, Kanade T. An iterative image registration technique with an application to stereo vision, F, 1981 [C]. Citeseer.
[95] Tian Q, Huhns M N. Algorithms for subpixel registration [J]. Computer Vision, Graphics, and Image Processing, 1986, 35(2): 220-33.
[96] Cochran S D, Medioni G. 3-D surface description from binocular stereo [J]. Ieee T Pattern Anal, 1992, 981-94.
[97] Fua P. A parallel stereo algorithm that produces dense depth maps and preserves image features [J]. Mach Vision Appl, 1993, 6(1): 35-49.
[98] Intille S S, Bobick A F. Incorporating intensity edges in the recovery of occlusion regions; proceedings of the Pattern Recognition, 1994 Vol 1 - Conference A: Computer Vision & Image Processing, Proceedings of the 12th IAPR International Conference on, F 9-13 Oct 1994, 1994 [C].
[99] S. Geman D G. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, Readings in uncertain reasoning [J]. MorganKaufmann Publishers Inc, San Francisco, CA, 1990, 452-72.
[100] Greig D, Porteous B, Seheult A H. Exact maximum a posteriori estimation for binary images [J]. Journal of the Royal Statistical Society Series B (Methodological), 1989, 51(2): 271-9.
[101] Kolmogorov V, Zabih R. What energy functions can be minimized via graph cuts? [J]. Computer Vision?aECCV 2002, 2002, 185-208.
[102] Tao H, Sawhney H S, Kumar R. A global matching framework for stereo computation [J]. 2001,
[103] Http://Vision.Middlebury.Edu.
[104] Kanhere N K, Birchfield S T. A Taxonomy and Analysis of Camera Calibration Methods for Traffic Monitoring Applications [J]. Intelligent Transportation Systems, IEEE Transactions on, 2010, 11(2): 441-52.
[105] Bay H, Ess A, Tuytelaars T, et al. Speeded-Up Robust Features (SURF) [J]. Comput Vis Image Und, 2008, 110(3): 346-59.
[106] Bay H, Tuytelaars T, Van Gool L. SURF: Speeded up robust features [J]. Computer Vision - Eccv 2006 , Pt 1, Proceedings, 2006, 3951(404-17.
[107] Lilienthal C V A. SIFT, SURF and seasons: Long-term outdoor localization using local features [J]. Proc. European Conference on Mobile Robots,Freiburg,Germany,ECMR, 2007, 253-8.
[108] Lowe D G. Distinctive image features from scale-invariant keypoints [J]. Int J Comput Vision, 2004, 60(2): 91-110.
[109] Hartley R I. Theory and practice of projective rectification [J]. Int J Comput Vision, 1999, 35(2): 115-27.
[110] http://www.vision.ee.ethz.ch/~bleibe/data/datasets.html [J].
[111] http://www.stereomaker.net/sample/index.html [J].
[112] Pearl J. Probabilistic reasoning in intelligent systems: networks of plausible inference [M]. Morgan Kaufmann, 1988.
[113] Weiss Y, Freeman W T. On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs [J]. Information Theory, IEEE Transactions on, 2001, 47(2): 736-44.
[114] Ihler A, Fisher J, Willsky A. Loopy belief propagation: Convergence and effects of message errors [J]. Journal of Machine Learning Research, 2006, 6(1): 905.
[115]郁理,郭立,袁红星.基于分级置信度传播的立体匹配新方法[J].中国Kaufmann Publishers Inc, San Francisco, CA, 1990, 452-72.
[100] Greig D, Porteous B, Seheult A H. Exact maximum a posteriori estimation for binary images [J]. Journal of the Royal Statistical Society Series B (Methodological), 1989, 51(2): 271-9.
[101] Kolmogorov V, Zabih R. What energy functions can be minimized via graph cuts? [J]. Computer Vision?aECCV 2002, 2002, 185-208.
[102] Tao H, Sawhney H S, Kumar R. A global matching framework for stereo computation [J]. 2001,
[103] Http://Vision.Middlebury.Edu.
[104] Kanhere N K, Birchfield S T. A Taxonomy and Analysis of Camera Calibration Methods for Traffic Monitoring Applications [J]. Intelligent Transportation Systems, IEEE Transactions on, 2010, 11(2): 441-52.
[105] Bay H, Ess A, Tuytelaars T, et al. Speeded-Up Robust Features (SURF) [J]. Comput Vis Image Und, 2008, 110(3): 346-59.
[106] Bay H, Tuytelaars T, Van Gool L. SURF: Speeded up robust features [J]. Computer Vision - Eccv 2006 , Pt 1, Proceedings, 2006, 3951(404-17.
[107] Lilienthal C V A. SIFT, SURF and seasons: Long-term outdoor localization using local features [J]. Proc. European Conference on Mobile Robots,Freiburg,Germany,ECMR, 2007, 253-8.
[108] Lowe D G. Distinctive image features from scale-invariant keypoints [J]. Int J Comput Vision, 2004, 60(2): 91-110.
[109] Hartley R I. Theory and practice of projective rectification [J]. Int J Comput Vision, 1999, 35(2): 115-27.
[110] http://www.vision.ee.ethz.ch/~bleibe/data/datasets.html [J].
[111] http://www.stereomaker.net/sample/index.html [J].
[112] Pearl J. Probabilistic reasoning in intelligent systems: networks of plausible inference [M]. Morgan Kaufmann, 1988.
[113] Weiss Y, Freeman W T. On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs [J]. Information Theory, IEEE Transactions on, 2001, 47(2): 736-44.
[114] Ihler A, Fisher J, Willsky A. Loopy belief propagation: Convergence and effects of message errors [J]. Journal of Machine Learning Research, 2006, 6(1): 905.
[115]郁理,郭立,袁红星.基于分级置信度传播的立体匹配新方法[J].中国