第32卷第1期2010年1月机器人ROBOTVol.32,No.1Jan.,2010:1002-0446(2010-01-0104-05一种基于图割的改进立体匹配算法张令涛1,2,3,曲道奎1,2,徐方1,2(1.中国科学院沈阳自动化研究所,辽宁沈阳110016;2.沈阳新松机器人自动化股份有限公司,辽宁沈阳110168;3.中国科学院研究生院,北京100049摘要:针对基于图割法的立体匹配算法耗时太长的问题,提出了一种基于简化网格图的立体匹配算法.算法通过区域匹配算法得到每个像素的初始视差值,然后只保留完整网格图的部分可能的视差值,去除其余大部分的节点和边缘,建立简化的网格图.该方法大大缩减了网格图的容量,缩短匹配所用时间,并且能够选用更大的视差范围.实验证明,该算法能够得到比较理想的视差图,而且大大缩短立体匹配所用时间.关键词:立体匹配;图割;简化网格图;最小割/最大流:TP302.1文献标识码:AAnImprovedStereoMatchingAlgorithmBasedonGraphCutsZHANGLingtao1,2,3,QUDaokui1,2,XUFang1,2(1.ShenyangInstituteofAutomation,ChineseAcademyofSciences,Shenyang110016,China;2.ShenyangSIASUNRobotAutomationCO.LTD,Shenyang110168,China;3.GraduateSchooloftheChineseAcademyofSciences,Beijing100049,ChinaAbstract:Fortheproblemthatstereomatchingmethodsbasedongraphcutsaretimeconsuming,thispaperputsforwardanimprovedstereomatchingalgorithmbasedonreducedgraphs.First,theinitialdisparityforeachpixelcanbecalculatedbyusinglocalmatchingmethod.Then,wekeeponlysomepotentialdisparityvaluesinthecompletegraph,andthereducedgraphwillcontainareducednumberofverticesandedges.Thereforethegraphcapacityandexecutiontimearedecreased,andawiderdisparityrangeisobtained.Atlast,itisprovedbyexperimentsthatthisalgorithmcanachievearelativelyidealdisparitymapandsavemuchtimeinstereomatching.Keywords:stereomatching;graphcut;reducedgraph;min-cut/max-flow1引言(Introduction机器人视觉技术最困难的问题之一就是找出每对图像点之间的对应关系,即解决立体匹配问题.关于立体匹配算法,国内外学者已经做了大量的工作,但是寻找更为稳定的算法仍然是大家共同追求的目标.立体匹配算法大致可分为两类[1]:一类为基于区域的算法,这种算法很容易恢复出高纹理区域的视差,但在低纹理区域会造成大量的误匹配,从而导致边界模糊,同时对遮挡的区域也很难进行处理,优点是速度快,占用内存少;另一类为基于全局的算法,该算法一般用相容性约束和平滑性约束来构成一个评价函数,再通过各种最优算法求得评价函数的最小值.由于基于全局的匹配算法是全局寻优,所以匹配准确性较高,尤其是采用图割思想的算法在精度上取得了很好的效果.图割算法由Roy和Cox首次提出,用来解决立体匹配问题,它在1维动态规划方法的基础上建立了2维的一般形式.实验结果表明,基于图割的方法比传统的基于正则相关(normalizedcorrelation的方法误差小,并且性能优于模拟退火法.文[2-3]用马尔可夫随机场(Markovrandomfield表示立体匹配公式,获得了准确度更高的视差图,尤其在物体边缘等不连续区域,得到了更为准确的视差;文[4-6]通过改进图割法中的能量函数,较好地解决了立体匹配中的遮挡问题.然而,基于图割的算法存在的最大问题是计算量过大,不适用于对实时性要求比较高的场合.图割方法计算量过大是因为所建立的网格图包含大量的节点和边缘,每个像素的视差计算过程需要遍历该像素所有可能的像素差,这占用了大量的时间而且效率很低.本文提出了一种改进的基于图割的立体匹配算法,利用局部匹配算法得出的像素差作为基金项目:国家863计划重点资助项目(2007AA041701.通讯作者:张令涛,zhangingao@yahoo收稿/录用/修回:2009-01-14/2009-06-22/2009-11-17第32卷第1期张令涛等:一种基于图割的改进立体匹配算法105先验值,去除大量不相关节点和边缘,减小计算量,缩减匹配所用的时间.2基于图割的匹配算法(Stereomatchingbasedongraphcuts基于标号的图像匹配算法把图像的视差看成标号,建立标号的能量函数,把匹配问题转化为能量函数最小化问题.最小化该能量函数的方法主要有两种,一种是模拟退火...