基于图像分割的立体匹配算法研究
|
摘要
立体匹配是通过寻找同一空间场景在不同视点下投影图像的像素间的一一对应关系,最终得到该景物的视差图,是整个立体视觉系统中的核心部分。但是由于变形、遮挡、低纹理区域误匹配等情况的影响,立体匹配很难得到较高精度的视差图。因此立体匹配也是立体视觉最困难的环节。
本文对立体视觉技术进行了研究,着重研究了立体匹配算法。从提高视差精度角度出发,本文提出了一种基于Tao框架的改进立体匹配算法,主要针对初始匹配点的计算、模板参数的计算以及全局评价函数的选取进行了改进。算法通过彩色图像分割、初始匹配点的获取、区域分类、模板参数计算和模板参数优化等步骤实现。其中图像分割采用了目前广泛应用而且比较优秀的均值漂移算法;在Tao的算法中,初始匹配点的计算采用基于偏差绝对值和的固定较小窗口算法,在低纹理区域造成较多的误匹配,给后继的模板参数计算带来不利的影响,本文采用基于变窗口技术来获取较多的初始匹配点,并在计算过程中采用一致性校验和相似点滤除等措施去除误匹配点,以保证初始匹配点的可靠性;由于分割后存在一些初始匹配点较少的区域,这些区域计算出来的模板参数并不准确,本文先只计算匹配点数较多区域的模板参数,然后利用其相同或相近的模板参数近视初始匹配点较少的区域,通过模板参数优化求得不可靠区域的最终模板参数;模板参数优化阶段,本文采用了含有数据项、平滑项和遮挡项的评价函数,增加了遮挡约束。
本文还使用VC6.0开发工具在PC机上搭建了软件系统平台,对相关算法进行了实验。实验结果证实本文算法具有较高的匹配精度,边界清晰且定位较准确,低纹理区域的视差也得到了较好恢复。
Stereo matching is a correspondence between the relations by looking for the same space at different point of view of the pixel under the projection image and eventually get the disparity map of the scene. Stereo matching is the core issue in stereo vision. However, due to deformation, occlusion, texture-less regions the impact of false matches, etc., stereo matching is difficult to obtain high precision disparity map. Therefore, stereo matching is the most difficult part of stereo vision.
In this paper, stereo vision technology has been studied, focused on stereo matching algorithm. From the perspective of improving precision of disparity map, an improved stereo matching algorithm based on a framework of Tao has been proposed. Aimed at initial disparity acquirement, the calculation of the plane parameters and selection of the global evaluation function have been improved. And the whole algorithm includes several steps, such as color image segmentation, initial disparity acquirement, segments categories, the calculation of the plane parameters, the plane parameters optimization and so on. For image segmentation, a widely used and relatively good mean-shift algorithm has been adopted. In the initial disparity acquirement of Tao algorithm, deviation smaller window SAD algorithm has been adopted, resulting in texture-less regions more false matches and a subsequent negative impact of plane parameters. This paper based on variable window technique to obtain more initial match points, and the process used in the calculation of consistency checking and the similarity measures filtering to remove false matching points in order to ensure the reliability of the initial matching points. Because there are some regions with less matching points after the segmentation, these regions of the plane parameter are not calculated accurately, the paper calculate plane parameters of regions with more matching points, then use the same or similar plane parameters instead of the less initial matching points regions, and obtained by the plane parameter optimization the final template parameter of unreliable regions. In plane parameters optimization stage, containing data items, smooth items and occlusion items of the evaluation function has been adopted, with occlusion constraints.
This paper also uses VC6.0 development tools to build on the PC, the software system platform for the underlying algorithm in the experiment. The experiments results show our algorithm has a higher matching accuracy, the boundary clear and more accurate positioning and disparity map of texture-less regions has also been well restored.
本文对立体视觉技术进行了研究,着重研究了立体匹配算法。从提高视差精度角度出发,本文提出了一种基于Tao框架的改进立体匹配算法,主要针对初始匹配点的计算、模板参数的计算以及全局评价函数的选取进行了改进。算法通过彩色图像分割、初始匹配点的获取、区域分类、模板参数计算和模板参数优化等步骤实现。其中图像分割采用了目前广泛应用而且比较优秀的均值漂移算法;在Tao的算法中,初始匹配点的计算采用基于偏差绝对值和的固定较小窗口算法,在低纹理区域造成较多的误匹配,给后继的模板参数计算带来不利的影响,本文采用基于变窗口技术来获取较多的初始匹配点,并在计算过程中采用一致性校验和相似点滤除等措施去除误匹配点,以保证初始匹配点的可靠性;由于分割后存在一些初始匹配点较少的区域,这些区域计算出来的模板参数并不准确,本文先只计算匹配点数较多区域的模板参数,然后利用其相同或相近的模板参数近视初始匹配点较少的区域,通过模板参数优化求得不可靠区域的最终模板参数;模板参数优化阶段,本文采用了含有数据项、平滑项和遮挡项的评价函数,增加了遮挡约束。
本文还使用VC6.0开发工具在PC机上搭建了软件系统平台,对相关算法进行了实验。实验结果证实本文算法具有较高的匹配精度,边界清晰且定位较准确,低纹理区域的视差也得到了较好恢复。
Stereo matching is a correspondence between the relations by looking for the same space at different point of view of the pixel under the projection image and eventually get the disparity map of the scene. Stereo matching is the core issue in stereo vision. However, due to deformation, occlusion, texture-less regions the impact of false matches, etc., stereo matching is difficult to obtain high precision disparity map. Therefore, stereo matching is the most difficult part of stereo vision.
In this paper, stereo vision technology has been studied, focused on stereo matching algorithm. From the perspective of improving precision of disparity map, an improved stereo matching algorithm based on a framework of Tao has been proposed. Aimed at initial disparity acquirement, the calculation of the plane parameters and selection of the global evaluation function have been improved. And the whole algorithm includes several steps, such as color image segmentation, initial disparity acquirement, segments categories, the calculation of the plane parameters, the plane parameters optimization and so on. For image segmentation, a widely used and relatively good mean-shift algorithm has been adopted. In the initial disparity acquirement of Tao algorithm, deviation smaller window SAD algorithm has been adopted, resulting in texture-less regions more false matches and a subsequent negative impact of plane parameters. This paper based on variable window technique to obtain more initial match points, and the process used in the calculation of consistency checking and the similarity measures filtering to remove false matching points in order to ensure the reliability of the initial matching points. Because there are some regions with less matching points after the segmentation, these regions of the plane parameter are not calculated accurately, the paper calculate plane parameters of regions with more matching points, then use the same or similar plane parameters instead of the less initial matching points regions, and obtained by the plane parameter optimization the final template parameter of unreliable regions. In plane parameters optimization stage, containing data items, smooth items and occlusion items of the evaluation function has been adopted, with occlusion constraints.
This paper also uses VC6.0 development tools to build on the PC, the software system platform for the underlying algorithm in the experiment. The experiments results show our algorithm has a higher matching accuracy, the boundary clear and more accurate positioning and disparity map of texture-less regions has also been well restored.
引文
[1]章毓晋.图象工程(下册)图象理解与计算机视觉.北京:清华大学出版社,2000:1~6.
[2]王晓华.基于双目视觉的三维重建技术研究.[硕士学位论文].济南:山东大学,2004.
[3]姚国正,刘磊,汪云九译.计算机视觉.北京,科学出版社,1988:6~37.
[4] Marr D, Poggio T. A Computational Theory of Human Stereo Vision. in Proc Roy Soc, 1979: 301~328.
[5] Veksler O. Efficient Graph-based Energy Minimization Methods in Computer Vision. PhD thesis, Cornell University, 1999.
[6] Boykov Y, Veksler O, and Zabih R. Fast approximate energy minimization via graph cuts. IEEE Trans. PAMI, 2001, 23(11):1222~1239.
[7] Scharstein D, Szeliski R. A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms. IJCV, 2002, 47(1): 7~42.
[8] Sun J, Zheng N N, and Shum H Y. Stereo Matching Using Belief Propagation. IEEE Trans, PAMI, 2003, 25(7):787~800.
[9] Forstmann S, Kanou Y, Thuering S, et al. Real-Time Stereo by using Dynamic Programming. CVPR, 2004:29~29.
[10] Deng Y, Lin X. A fast line segment based dense stereo algorithm using tree dynamic programming. ECCV, 2006: 201~212.
[11] Z. Wang and Z. Zheng. A region based stereo matching algorithm using cooperative optimization. CVPR, 2008: 1~8.
[12] Tao H, Sawhney H S, Kumar R. A Global Matching Framework for Stereo Computation. Proceedings of the Eighth International Conference On Computer Vision, 2001. Vancouver, Canada,1: 532~539.
[13]李洪海.基于移动机器人的双目立体视觉技术研究.[硕士学位论文].南京:南京航空航天大学,2007.
[14]高文,陈熙霖.计算机视觉-算法与系统原理.北京:清华大学出版社,1998:59~60.
[15] Ruichek Y, Issa H, Postaire J G and Burie J C. Towards real-time obstacle detection using a hierarchical decomposition methodology for stereo matching with a genetic algorithm. 16th IEEE International Conference, Nov. 2004: 138~147.
[16]贾云德.机器视觉.北京:科学出版社,2000:160~164.
[17]吴立德.计算机视觉.上海:复旦大学出版社,1993:131~132.
[18] Hirschmuller H. Improvements in real-time correlation-based stereo vision[C]. proceedings of the IEEE Workshop on Stereo and Multi-Baseline Vision, F, 2001: 141~148.
[19] Veksler O. Fast variable window for stereo correspondence using integral images. proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, F, 2003[C]: 556~561.
[20] Konolige K. Small vision systems: hardware and implementation[C]. proceedings of the 8th International Robotics Research Symposium, F, 1998.
[21] Corke P, Dunn P. Real-time stereopsis using FPGAs[C]. proceedings of the IEEE Region 10 Annual Conference TENCON'97, Brisbane, Australia, F, 1997: 235~238.
[22] Rojas A,Calvo A,Munoz J.A dense disparity map of stereo images[J].Pattern Recognition Letters, 1997, 18(4): 385~393.
[23] Okutomim,Kanade T.A Multiple-Base-Line Stereo[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15(4): 353~363.
[24] Kisworo M,Venkatesh S,West G.Modeling Edges at Subpixel Accuracy Using the Local Energy Approach[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994, 16(4): 405~410.
[25] Yip R K K,How P. A multi-level dynamic programming method for stereo line matching[J]. Pattern Recognition Letters, 1998, 19(9): 839~855.
[26] Yip R K K.A multi-level dynamic programming method for line segment matching in axial motion stereo[J]. Pattern Recognition, 1998, 31(11): 1653~1668.
[27] Ming Sheng W,Jin Jang L.A bipartite matching approach to feature correspondence in stereo vision[J].Pattern Recognition Letters, 1995, 16(1): 23~31.
[28]赵杰,于舒春,蔡鹤皋.金字塔双层动态规划立体匹配算法.控制与决策,2007,22(1):69~73.
[29] Xu Z L, Ma L Z, Kimachi M, et al. Efficient contrast invariant stereo correspondence using dynamic programming with vertical constraint. The Visual Computer, 2007, 24(1): 45~55.
[30] Boykov Y,Veksler O,Zabih R.Fast approximate energy minimization via graph cuts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001, 23(11): 1222~1239.
[31] Kolmogorov V,Zabih R.Computing visual correspondence with occlusions using graph cuts[C]. proceedings of the 8th IEEE International Conference on Computer Vision, F, 2001: 508~515.
[32] Michel Sarkis, Klaus Diepold. Sparse Stereo Matching Using Belief Propagation.IEEE, 2008: 1780~1783.
[33] Pedro F,Daniel P. Efficient Belief Propagation for Early Vision. IEEE, 2004,24(1): 261~268.
[34] Schmid C, Zisserman A.The geometry and matching of lines and curves over multiple views[J].International Journal of Computer Vision, 2000, 40(3): 199-233.
[35]李德广,李科杰.一种快速立体视觉边缘匹配算法[J].计算机应用,2005,25(4):763~765.
[36]陈君,戚飞虎.一种新的基于特征点的立体匹配算法[J].中国图象图形学报,2005,10(11):1411~1414.
[37] Distefano L,Marchionni M,Mattoccia S.A fast area-based stereo matching algorithm[J]. Image and Vision Computing, 2004, 22(12): 983~1005.
[38] Kanade T,Okutomi M.A Stereo Matching Algorithm with an Adaptive Window-Theory and Experiment[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1994,16(9): 920~932.
[39] M.Z.Brown, D Burschka.Advances in computational stereo[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(8): 993~1008.
[40] Zhao J,Yu S C,Cai H G.Local-global stereo matching algorithm[J]. Aircraft Engimeering and Aerospace Technology:An International Journal, 2006, 78(4): 289~292.
[41]尹传历,向长波,宋建中等.一种基于自适应窗口和图切割的快速立体匹配算法[J].光学精密工程,2008,16(6):1117~1121.
[42] Yang Q,Wang L,Yang R,et al.Stereo matching with color-weighted correlation,hierarchical belief propagation and occlusion handling[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(3): 492~504.
[43]曹义.移动机器人运动导航中的立体视觉技术研究.[硕士学位论文].南京:南京航空航天大学,2009.
[44]郑志刚.高精度摄像机标定和鲁棒立体匹配.[博士学位论文].合肥:中国科学技术大学,2008.
[45] http://vision.middlebury.edu/stereo/.
[46] Canny J. A computational approach to edge detection. IEEE Tans.On Pattern Analysis and Machine Intelligence, 1986, 8(6): 679~698.
[47] Vincent L,Takeo K,Masatoshi O.Watersheds in digital spaces:an efficient algorithm based on Immersion simulations[J].IEEETrans, PMAI, 1991, 13(6): 538~598.
[48] Comanici D,Meer P.Mean Shift:A Robust Approach Toward Feature Space Analysis. IEEE Trans. Pattern Anal.Mach.Intell, 2002, 24(5): 603~619.
[49] Fukunaga K,Hostetler L D.The estimation of the gradient of adensity function, with applications in pattern recognition.IEEE Trans.Information Theory, 1975, 21: 32~40.
[50] Cheng Y.MeanShi,Mode Seeking,and Clustering.IEEE Trans.Pattern Anal.Mach.Intell, 1995, 17(8): 790~799.
[51] Birchfield S and Tomasi C. A pixel dissimilarity measure that is insensitive to image sampling. IEEE TPAMI, 1998, 20(4): 401~406.
[52] Koffka K. The Principle of Gestalt Psychology,New York:Harcourt Brace, 1935.
[53] Kuk Jin Y,Inso K. Locally adaptive support-weight approach for visual correspondence search. IEEE, 2005: 924~931.
[54]陶云刚.误差理论与数据分析.北京:航空工业出版社,1997:106~126.
[55] Bleyer, M, Gelautz, M. A layered stereo algorithm using image segmentation and global visibility constraints. Image Processing, 2004: 2997~3000.
[56]刘正东,徐涛,杨静宇.具有规则度约束的红外图像多层阈值分割方法.计算机工程,2005,31(14):13~15.
[2]王晓华.基于双目视觉的三维重建技术研究.[硕士学位论文].济南:山东大学,2004.
[3]姚国正,刘磊,汪云九译.计算机视觉.北京,科学出版社,1988:6~37.
[4] Marr D, Poggio T. A Computational Theory of Human Stereo Vision. in Proc Roy Soc, 1979: 301~328.
[5] Veksler O. Efficient Graph-based Energy Minimization Methods in Computer Vision. PhD thesis, Cornell University, 1999.
[6] Boykov Y, Veksler O, and Zabih R. Fast approximate energy minimization via graph cuts. IEEE Trans. PAMI, 2001, 23(11):1222~1239.
[7] Scharstein D, Szeliski R. A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms. IJCV, 2002, 47(1): 7~42.
[8] Sun J, Zheng N N, and Shum H Y. Stereo Matching Using Belief Propagation. IEEE Trans, PAMI, 2003, 25(7):787~800.
[9] Forstmann S, Kanou Y, Thuering S, et al. Real-Time Stereo by using Dynamic Programming. CVPR, 2004:29~29.
[10] Deng Y, Lin X. A fast line segment based dense stereo algorithm using tree dynamic programming. ECCV, 2006: 201~212.
[11] Z. Wang and Z. Zheng. A region based stereo matching algorithm using cooperative optimization. CVPR, 2008: 1~8.
[12] Tao H, Sawhney H S, Kumar R. A Global Matching Framework for Stereo Computation. Proceedings of the Eighth International Conference On Computer Vision, 2001. Vancouver, Canada,1: 532~539.
[13]李洪海.基于移动机器人的双目立体视觉技术研究.[硕士学位论文].南京:南京航空航天大学,2007.
[14]高文,陈熙霖.计算机视觉-算法与系统原理.北京:清华大学出版社,1998:59~60.
[15] Ruichek Y, Issa H, Postaire J G and Burie J C. Towards real-time obstacle detection using a hierarchical decomposition methodology for stereo matching with a genetic algorithm. 16th IEEE International Conference, Nov. 2004: 138~147.
[16]贾云德.机器视觉.北京:科学出版社,2000:160~164.
[17]吴立德.计算机视觉.上海:复旦大学出版社,1993:131~132.
[18] Hirschmuller H. Improvements in real-time correlation-based stereo vision[C]. proceedings of the IEEE Workshop on Stereo and Multi-Baseline Vision, F, 2001: 141~148.
[19] Veksler O. Fast variable window for stereo correspondence using integral images. proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, F, 2003[C]: 556~561.
[20] Konolige K. Small vision systems: hardware and implementation[C]. proceedings of the 8th International Robotics Research Symposium, F, 1998.
[21] Corke P, Dunn P. Real-time stereopsis using FPGAs[C]. proceedings of the IEEE Region 10 Annual Conference TENCON'97, Brisbane, Australia, F, 1997: 235~238.
[22] Rojas A,Calvo A,Munoz J.A dense disparity map of stereo images[J].Pattern Recognition Letters, 1997, 18(4): 385~393.
[23] Okutomim,Kanade T.A Multiple-Base-Line Stereo[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15(4): 353~363.
[24] Kisworo M,Venkatesh S,West G.Modeling Edges at Subpixel Accuracy Using the Local Energy Approach[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994, 16(4): 405~410.
[25] Yip R K K,How P. A multi-level dynamic programming method for stereo line matching[J]. Pattern Recognition Letters, 1998, 19(9): 839~855.
[26] Yip R K K.A multi-level dynamic programming method for line segment matching in axial motion stereo[J]. Pattern Recognition, 1998, 31(11): 1653~1668.
[27] Ming Sheng W,Jin Jang L.A bipartite matching approach to feature correspondence in stereo vision[J].Pattern Recognition Letters, 1995, 16(1): 23~31.
[28]赵杰,于舒春,蔡鹤皋.金字塔双层动态规划立体匹配算法.控制与决策,2007,22(1):69~73.
[29] Xu Z L, Ma L Z, Kimachi M, et al. Efficient contrast invariant stereo correspondence using dynamic programming with vertical constraint. The Visual Computer, 2007, 24(1): 45~55.
[30] Boykov Y,Veksler O,Zabih R.Fast approximate energy minimization via graph cuts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001, 23(11): 1222~1239.
[31] Kolmogorov V,Zabih R.Computing visual correspondence with occlusions using graph cuts[C]. proceedings of the 8th IEEE International Conference on Computer Vision, F, 2001: 508~515.
[32] Michel Sarkis, Klaus Diepold. Sparse Stereo Matching Using Belief Propagation.IEEE, 2008: 1780~1783.
[33] Pedro F,Daniel P. Efficient Belief Propagation for Early Vision. IEEE, 2004,24(1): 261~268.
[34] Schmid C, Zisserman A.The geometry and matching of lines and curves over multiple views[J].International Journal of Computer Vision, 2000, 40(3): 199-233.
[35]李德广,李科杰.一种快速立体视觉边缘匹配算法[J].计算机应用,2005,25(4):763~765.
[36]陈君,戚飞虎.一种新的基于特征点的立体匹配算法[J].中国图象图形学报,2005,10(11):1411~1414.
[37] Distefano L,Marchionni M,Mattoccia S.A fast area-based stereo matching algorithm[J]. Image and Vision Computing, 2004, 22(12): 983~1005.
[38] Kanade T,Okutomi M.A Stereo Matching Algorithm with an Adaptive Window-Theory and Experiment[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1994,16(9): 920~932.
[39] M.Z.Brown, D Burschka.Advances in computational stereo[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(8): 993~1008.
[40] Zhao J,Yu S C,Cai H G.Local-global stereo matching algorithm[J]. Aircraft Engimeering and Aerospace Technology:An International Journal, 2006, 78(4): 289~292.
[41]尹传历,向长波,宋建中等.一种基于自适应窗口和图切割的快速立体匹配算法[J].光学精密工程,2008,16(6):1117~1121.
[42] Yang Q,Wang L,Yang R,et al.Stereo matching with color-weighted correlation,hierarchical belief propagation and occlusion handling[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(3): 492~504.
[43]曹义.移动机器人运动导航中的立体视觉技术研究.[硕士学位论文].南京:南京航空航天大学,2009.
[44]郑志刚.高精度摄像机标定和鲁棒立体匹配.[博士学位论文].合肥:中国科学技术大学,2008.
[45] http://vision.middlebury.edu/stereo/.
[46] Canny J. A computational approach to edge detection. IEEE Tans.On Pattern Analysis and Machine Intelligence, 1986, 8(6): 679~698.
[47] Vincent L,Takeo K,Masatoshi O.Watersheds in digital spaces:an efficient algorithm based on Immersion simulations[J].IEEETrans, PMAI, 1991, 13(6): 538~598.
[48] Comanici D,Meer P.Mean Shift:A Robust Approach Toward Feature Space Analysis. IEEE Trans. Pattern Anal.Mach.Intell, 2002, 24(5): 603~619.
[49] Fukunaga K,Hostetler L D.The estimation of the gradient of adensity function, with applications in pattern recognition.IEEE Trans.Information Theory, 1975, 21: 32~40.
[50] Cheng Y.MeanShi,Mode Seeking,and Clustering.IEEE Trans.Pattern Anal.Mach.Intell, 1995, 17(8): 790~799.
[51] Birchfield S and Tomasi C. A pixel dissimilarity measure that is insensitive to image sampling. IEEE TPAMI, 1998, 20(4): 401~406.
[52] Koffka K. The Principle of Gestalt Psychology,New York:Harcourt Brace, 1935.
[53] Kuk Jin Y,Inso K. Locally adaptive support-weight approach for visual correspondence search. IEEE, 2005: 924~931.
[54]陶云刚.误差理论与数据分析.北京:航空工业出版社,1997:106~126.
[55] Bleyer, M, Gelautz, M. A layered stereo algorithm using image segmentation and global visibility constraints. Image Processing, 2004: 2997~3000.
[56]刘正东,徐涛,杨静宇.具有规则度约束的红外图像多层阈值分割方法.计算机工程,2005,31(14):13~15.