基于最优斜面参数估计的局部立体匹配算法.docx

基于最优斜面参数估计的局部立体匹配算法*收稿日期：2013-2； 修订日期：基金项目：国家863高技术研究发展计划(2010AA7080302)作者简介：曹晓倩(1986-)，女，陕西彬县 ，博士生，主要研究方向为立体视觉。Emai:littlegrass0606导师简介：马彩文(1965-)，男，内蒙古赤峰 ，研究员，博士生导师，主要从事图像处理、目标跟踪方面的研究工作。Email:cwma曹晓倩1,2，马彩文11.中国科学院西安光学精密机械研究所,陕西 西安710119 2.中国科学院大学，北京100039摘 要：针对传统局部匹配算法在斜面场景匹配中所表现出的“阶梯效应”，本文提出了一种基于最优斜面参数估计的局部立体匹配算法。该算法首先为每一个像素随机地分配一组斜面参数，然后以新的斜面参数所定义的支撑域下当前像素的匹配代价是否减小为准则，迭代地进行斜面参数的“邻域传播单点优化”过程，并最终使得计算结果收敛到最优斜面，同时估计得到稠密的亚像素级视差。通过对典型斜面场景图像和Middlebury标准测试图像对的匹配实验表明，本文算法在将对普通场景的匹配效果保持在当前先进水平的同时，对斜面场景的匹配消除了“阶梯效应，且匹配率代表了局部匹配的先进水平。关键词：图像处理；立体匹配；斜面估计；阶梯效应中图分类号：TP391.41， 文献标识码： A 文章编号：Best slant-plane estimation based stereo matching algorithmCAO Xiao-qian1,2 MA Cai-wen11. Xi;an Institute ofoptics and precision mechenics , Chinese Academy of Sciences, Xian 710119, China;2. University of Chinese Academy of Sciences, Beijing 100039, ChinaAbstract： A novel stereo matching algorithm based on best slant-plane estimation is proposed in this paper in the purpose of eliminating “stair-casing” which shows up frequently in the slant scene matching process where the window-based matching algorithm is used. In this procedure, a slant parameter vector was randomly attributed to every pixel in the reference image firstly, then , those vectors are iteratively propagated between neighbor pixels followed by a recursively slant-plane parameter refinement process for each pixels in the principle of whether a lower cost could be got under the new slant-plane parameter vectors, until the parameter vectors are converged to the best slant-plane parameter vectors while a sub-pixel disparity is got for each pixel in the reference image. Experiment results indicate the effectiveness of the algorithm, the performance of the algorithm on the slant scene is ranked on top of those state-of art algorithm which is relatively close to the algorithm proposed here, while the performance on the normal scene is comparable with the state-of art algorithm.Key words： Image Processing Stereo matching slant plane evaluation stair-casing0 引 言立体视觉技术因其信息的丰富性以及在对抗环境中的隐蔽性在视觉导航，航天航空探测1,2等领域有很好的应用前景。而立体视觉的关键技术之一则是立体匹配，即寻找两幅或者多幅图像中对应于同一空间物点的像素，这一概念与普通图像处理中的图像配准3,4算法类似，只是立体匹配需要获取稠密的配准图谱。立体匹配算法根据其信息获方式的不同分为主动立体匹配5和被动立体匹配，被动立体匹配因其应用的便利性以及算法的多样性受到了广泛的关注。Daniel Scharstein6将可实现稠密匹配的立体匹配算法分为基于MRFs模型的全局匹配算法和基于窗口累积匹配代价的局部立体匹配算法。局部匹配算法因为其并行运算的特性有利于实时匹配而受到工程研究人员的青睐，然而，由于局部匹配算法窗口内视差恒定的基本假设在视差边缘和斜面场景中并不成立，从而出现了“前景肥大”现象和“阶梯效应”。飘移窗算法7、自适应窗口算法8、自适应权值算法9等鲁棒性较强的算法的出现实现了局部匹配算法在弱纹理区域和视差不连续区域匹配的双赢，在保证了匹配率的同时保护了视差边缘，解除了“前景肥大”。而对于“阶梯效应”，目前成熟的算法并不多：Q. Yang等10提出了通过抛物线插值取得亚像素级视差的方法；Y. Zhang11等提出了通过局部匹配算法估计场景模型然后在模型约束下进一步匹配的算法；近年来流行的基于图像分割12和斜面拟合的算法也试图解决这一问题；这些方法都在一定程度上改善了阶梯效应，但是算法本身都是以传统的局部匹配为基础，本质上并没有解除局部匹配算法基本假设的约束。为了从根本解决这一问题，代价匹配窗口必须是在代价立方体中与场景斜面参数一致的斜面区域，而且，在该支撑域下，当前像素的匹配代价最小，我们将这一斜面定义为最优斜面。现在的问题是，如何求解这一最优斜面。将最优斜面的定义逆向推理，直观上可以搜索使得当前像素匹配代价最小的斜面即为最优斜面，而无穷数量的可能的斜面参数使得这一理论只能成为算法的指导。Connelly Barnes13在进行图像配准时提出的搜索最优偏移量的方法为我们提供了思路，我们将这一思想应用到立体匹配领域，并根据立体匹配的具体环境，又引入了自适应三维斜面支撑域理论，来求解对应于每一个像素的最优斜面，同时，获取亚像素级视差。最后，我们采用图像处理的方式对获得的视差图进行高提升滤波，在去除匹配错误点（噪声）的同时，保留视差边缘，获取分段光滑的视差图谱。1 最优斜面估计所谓最优斜面，就是在代价立方体空间中与当前像素对应的场景斜面参数一致的斜面。在该斜面所确定的支撑域下计算当前像素的匹配代价，将会是所有可能的斜面支撑域下最小的。关于最优斜面的估计，我们基于Connelly Barnes13的思想，认为具有相同斜面参数的区域中包含的像素足够多，使得在为每一个像素随机地分配一组斜面参数之后，这一块区域中至少有一个像素的斜面参数是正确的，那么，通过迭代地进行斜面参数在邻域像素之间的传播，我们总能将这一正确的斜面参数传播给该区域中的每一个像素。当然，这一认定并不总是成立，所以，在每经过一次邻域传播之后，我们还会引入单点优化，以修正可能会出现的错误斜面参数。1.1 最优斜面假设参考图像中的每一个像素都位于某一个斜面上，该斜面用一组参数表示，这组参数是该斜面在代价立方体空间中斜面方程的视差表示形式的系数，其斜面方程的视差表示形式为： （1）根据最优斜面的定义，如果满足： （2）则其为当前像素的最优视差平面。其中，是所有可能的视差平面集合，是其中的任意斜面， （3） 是当前像素在斜面所定义斜面支撑域下的累积匹配代价，是在该斜面下，像素的匹配像素，其视差值可根据式（1）求得，是匹配相对的匹配代价求解函数，通常为绝对差（AD）或者平方差（SD），这两者的选择对匹配性能几乎没有影响。关于窗口的选择，我们会在下一章详细描述。1.2 最优斜面参数估计事实上，如果可能的斜面参数为有限个，我们的最优斜面参数的搜索问题与基于MRFs的全局匹配问题就会是同一类，所以其算法的求解思想也与全局匹配算法类似。首先，随机地为参考图像中的每一个像素分配一组斜面参数，然后，按照某种规则，对这组参数进行改变，迭代地进行这一过程，就会收敛到最优解。1.2.1 斜面参数的初始化斜面参数在初始化时要充分地随机才能保证“正确的”参数的出现，而斜面方程的视差模式下，视差轴的系数已为定值，所以，我们将斜面方程用代价立方体三维空间中的空间平面标准方程形式来表述： （4） 令（4）式与（1）式对应项系数相等，得到两组系数之间的转换关系： （5） 如此一来，充分随机地初始化和，就可以得到随机的视差模式斜面参数。理论上，令在 区间上随机取值，令（）为随机单位向量即可，可是考虑到实际情况，可正可负，而为正，且其出现在分母上，为了避免极小分母的出现，我们需要为确定一个最小阈值。在完成初始化之后，要根据式（5）将初始化参数转换为视差斜面的系数，以便于后续的斜面参数的传播。1.2.2斜面参数的邻域传播斜面参数可以在邻域之间进行传播是基于邻域像素位于同一斜面的基本假设的。所谓邻域传播，是指如果邻域像素所对应的斜面参数所定义的斜面支撑域能够减小当前像素的匹配代价，那么将该邻域像素的斜面参数传播给当前像素，用数学语言描述为：（6）为了保持局部匹配算法的并行运算特性，我们将邻域传播分为奇传播和偶传播两个过程，在奇传播过程中，当前像素仅在其右邻域像素和下领域像素之间传播斜面参数，而在偶传播过程中，当前像素在其左邻域像素和上邻域像素之间传播斜面参数。2.2.3 斜面参数的单点优化我们在本章的开始就对单点优化的必要性做了表述，这里给出单点优化的具体方法。由于单点优化也是一个随机优化的过程，所以，在这之前，我们需要将视差斜面系数变换为标准斜面系数，变换的公式可以从（5）式中得到。算法首先对视差平移量和法向量的增量取值范围进行设置，其中，表征单点优化过程的迭代次数，斜面系数增量的取值区间是指斜面法向量中各个元素的增量范围，具体的增量值为该取值区间内的随机值。新的斜面系数为当前斜面系数与这一随机数的和，当然，对于法向量而言，做增量变换之后还是要归一化为单位向量。斜面系数优化之后，如果在新的斜面系数下的匹配代价低于当前系数下的匹配代价，用新的斜系数替换当前斜面系数，至此，完成一次优化。逐渐缩小增量范围，直至小于指定阈值，使得斜面系数优化到指定精度。图1所示的流程图给出了这一过程的详细描述。图1 单点优化算法流程图Figure 1. Flow chart of the point optimization step2匹配代价的计算以及算法的收敛性上一章给出了最优斜面估计的主旨思想及本文算法的主要理论框架，本章主要给出在斜面支撑域下累积匹配代价计算过程中所涉及的特殊问题的处理，并对斜面参数估计算法的收敛性做出讨论性证明。2.1 匹配代价计算累积匹配代价是斜面参数传播和优化的准则，引导着斜面参数优化的方向，所以是本文算法的核心步骤。累积匹配代价的计算涉及匹配代价的计算和累积窗口的设计两个问题。关于匹配代价的计算函数我们前面已作出说明，我们的特殊情况是亚像素视差下以及超出了确定的视差区间0,dmax的情况先如何确定匹配代价。对于亚像素视差的情况，只要不超出0,dmax的范围，我们总能确定出匹配像素的位置，通过其两边的像素的线性插值来获取匹配像素的颜色信息，然后计算其匹配代价。而对于视差出界的情况，按照该视差之计算出的匹配像素通常会超出目标图像的范围，匹配像素不存在，使得匹配代价无法计算。此时，只能效仿在动态规划算法中对遮挡像素的处理方式，为这类视差超出范围的像素人为地设置一个匹配代价，我们成为截断误差。应为出现这种视差出界的情况只是一种临时状态，迭代过程需要将这样的斜面参数淘汰，所以，为了简单起见，直接将截断误差设置为无穷大。累积窗口的设计是局部匹配算法的永恒主题，斜面参数给出了三维支撑域的形状，而累积窗口的设计则要确定在支撑域的范围和密度(权值)。为了在提高弱纹理区域的匹配率的同时保留视差斜面的边缘，本文采用了颜色自适应的累积窗口，相关参数的选择参考文献9所给出的结果。2.2 算法的收敛性本文提出的斜面参数估计的算法本质上是一种置信度传播算法10，其收敛性由置信度传播算法的收敛性保证，最终收敛到近似最优值。下面给出本文算法在置信度传播模式下的表述。不失一般性，假设二维图像中各像素所对应的斜面参数（组）是在二维图像网格上的马尔可夫随机场（MRFs），则各像素的斜面参数的联合概率分布遵守Gibbs分布，同时，可以证明，在给定输入图像对条件下，其后验概率也满足Gibbs分布，即 (7)其中是联合斜面参数随机变量，是输入图像对，为匹配代价函数，即全局算法中所说的数据项，而是当相邻像素斜面参数的惩罚函数，即平滑项，按照贝叶斯理论，使得（7）式取得最大值的一组的配置方式就是最优的配置，所以求解最优斜面配置就转换为最大化后验概率（MAP）的问题。目前，有很多的全局匹配算法都在试图快速地解决这一问题，本文采用了与局部匹配算法最接近，同时也能够并行运算的置信度传播算法。只是根据实际情况，对算法做出了一些简化和变更。 首先，是对能量函数的简化，将（7）式中平滑项去掉，平滑作用通过将数据项中的单点匹配代价求和转化为窗口内的累积代价求和。然后，由于斜面参数状态空间的无限性，邻域像素向当前像素传递的信息仅由该邻域像素的斜面参数和该参数的置信度（用当前像素在该斜面参数下的累积匹配代价的倒数值表示）组成，然后，以最大化后验概率为准则，保留置信度最高的参数。该过程用数学语言描述如：1.为参考图像中的每一个像素随机分配一组斜面参数得到初始化的数据项信息，其中表示参数的置信度，是当前像素在斜面参数下， 所定义的窗口内的累积匹配代价。2.信息迭代更新，q是p的邻域。3.至此完成置信度传播的全过程。图1是本文算法应用与Middlebury标准测试图像时，所计算出的各个图像对的误匹配率与迭代次数的关系，该图表明：图2. 算法的收敛性Figure 2 convergence of the algorithm在刚开始迭代时，误匹配率下降较快，当迭代次数超过13次之后，误匹配率迭代次数曲线趋于平缓，在继续迭代，匹配的准确率几乎不再发生变化。图2所提供的数据是本文算法收敛性的实验证明。3视差图像的优化处理根据现有的参考文献，视差图像的优化处理主要解决图像的遮挡问题，通常的做法是分别以两个视角下的图像作为参考图像计算其对应的视差图，然后通过互对应性检测来检测出遮挡像素，再通过邻域插值对遮挡像素的视差值进行填充。这种处理方式虽然遮挡检测的效果较好，但是意味着算法的计算量（计算时间）增加一倍，这在实时性要求较高的场合是值得斟酌的一个因素。再者，本文算法计算出的是亚像素视差，参考图像对应的匹配像素不定，即使按照四舍五入的方式确定了匹配像素，那么两次的不定估计将会使得本应匹配的像素被误检为遮挡。本文中，我们基于视差图像是由平滑的分块曲面（斜面）组成的理论，不做遮挡检测，而是直接对所估计的斜面参数图像进行平滑，然后根据平滑后的斜面参数计算视差图谱，在此基础上，通过提升滤波加强视差图谱的边缘。这一过程本质上相当于对遮挡区域和匹配错误区域的一次与斜面参数一致的线性插值填充。4实验结果及分析本实验分为两个部分，第一部分是对典型斜面图像的实验，通过实验验证本文算法消除“阶梯效应”的能力。第二部分是对Middlebury标准图像对的实验，检验本文算法的匹配准确率。图2 给出了本文算法对典型斜面图像corridor和map的处理结果(a)-(d)依次为参考图像、标准视差图像、自适应权值算法结果和本文算法结果。 图2 典型斜面场景的立体匹配结果Fig.2 classical slant sconces disparity map (a) (b) (c) (d) 图3 middlebury 标准测试图像的视差图（本文算法（上）和自适应权值算法（下）Fig.3 disparity map of the standard test images form Middlebury（ours（up）and adaptive-weight(bottom)）自适应权值算法代表了当前局部匹配算法的最优水平，能够在提高弱纹理区域的匹配率的同时很好地保留视差边缘，但对与“阶梯效应”却依然无能为力，在图2(c) map与corridor的视差图像中能看到明显的视差变换线，而本文算法的结果图2(d)中视差变换非常平滑，几乎看不见视差变换的痕迹，表明本文算法可以有效地消除阶梯效应。实验的第二部分是利用本文算法求解Middlebury标准测试图像对视差图的结果，所得视差结果如图3(上)所示，(a)-(d)依次为Tuskuba，Venus，Cones 以及Teddy图像对的视差图，与实验的第一部分一样，图3(下)给出了自适应权值算法的处理结果， Venus和teddy图像对的处理结果进一步证明了本文算法的优越性。为了对本文算法匹配的准确率进行评估，将对标准测试图像的处理结果上传至Middlebury网站，通过标准的测试程序获取本文算法对标准图像对的匹配率，表2给出了本文算法与当前先进算法以及相关算法的性能（误匹配率）比较,误差阈值为一个像素，黑体部分表示本文算法的结果最优。表1 Middlebury标准测试图像的匹配性能比较（误差阈值为一个像素）Table 1 compare of different algorithm(erreo threshhode=1pixels)algorithmTuskubaVenusConesTeddyNoccalldiscNoccalldiscNoccalldiscNoccalldiscOur method2.132.379.350.250.432.643.048.239.642.477.857.97Adap-weight9 1.081.415.400.510.824.175.067.5011.82.718.027.73Sub-pixel102.132.329.920.250.422.765.5210.514.23.238.338.20Seg+BP111.101.745.530.981.925.474.839.9310.305.2612.009.97总结与展望本文提出的基于最优斜面估计的局部立体匹配算法有效地消除了斜面匹配中的阶梯效应，同时，获的了高准确率的亚像素级视差，且对标准图像的匹配率保持在先进水平。寻找加快本文算法的收敛速度，提高算法的计算效率的途径是我们下一步工作的重点。 参考文献1 SUN Chengming, YUAN Yan, HUANG Fengzhen et al. Modeling and simulation on infrared imaging characteristics of space target J. Infrared and Laser Engineering(in Chinese) 孙成明，袁艳，黄锋振,等.空间目标红外特性建模与仿真J.红外与激光工程, 2012, 41(3): 563-5682 HAN Yi, SUN Huayan, LI Yingchun, et al Simulation of space object laser radar cross sectionJ Infrared and Laser Engineering(in Chinese) . 韩意，孙华燕，李迎春，等.空间目标激光雷达散射截面仿真分析J.红外与激光工程，2010，39(5):819-8233 LI Xiaochang, ZHU Dan. Image registration method based on region selection and scale-invariant featureJ Infrared and Laser Engineering(in Chinese) 李小昌,朱丹.采用尺度不变特征和区域选择的图像配准方法J.红外与激光工程,2012,41(2):537-5424. WANG Hong1 JI Xiaoqiang DAI Ming et al. Improved speed up robust feathers matching algorithmJ.Infrared and Laser Engineering(in Chinese) 王洪,稽晓强,戴明,等.一种改进的快速鲁棒性特征匹配算法J.红外与激光工程，2012，41(3):811-8165 WEI Zhenzhong, FAN Yanrui, ZHANG Guangjun，Stereo matching method for raster binocular stereo vision sensor J. Infrared and Laser Engineering魏振忠,樊妍睿,张广军,光栅式双目立体视觉传感器的立体匹配方法J红外与激光工程, 2010, 39(4): 330-3346 SCHARSTEIN D, SZELISKI R. A taxonomy and evaluation of dense two- frame stereo correspondence algorithm J ,International Journal of Computer Vision, 2002, 47( 1 /2 /3): 7-42.7 BOBICK.A.F, INTILLE.S. S. Large occlusion stereo. J ,International Journal of Computer Vision,1999 ,33(3):1812008DE-MAEZTU.L,MATTOCCIA.S,VILLANUEVA.A. Linear stereo matchingC, IEEE International Conference on Computer Vision, 2011,1078-10759 DE-MAEZTU.L, VILLANUEVA.A. Near Real-Time Stereo Matching Using Geodesic DiffusionJ, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(2): 410-41610 YANG.Q, YANG.R, DAVIS.R, Spatial-depth super- resolution for range imagesC ,IEEE Conference on Computer Vision and Pattern Recognition, 2007,1-811 BLEUER.M,OTHER.C,KOHLI.P, Surface Stereo with Soft SegmentationJ ISPRS Journal,2005, 59(3):128150 12 ZHANG Y, GONG.M, YANG.Y. Local stereo matching with 3D adaptive cost aggregation for slanted surface modeling and sub-pixel accuracyC. 19th International Conference on Pattern Recognition ,2008,1-4 13C. Barnes, E. Shechtman, A. Finkelstein, and D. B. Goldman. PatchMatch: A randomizedCorres-pondence algorithm for structural image editing. ACM Transactions on Graphics (Proc. SIGGRAPH), 28(3), August 2009