基于图像分割和可变窗的联合立体匹配

胡汉平，朱 明，吉淑娇，2，郭 滨

(1.中国科学院长春光学精密机械与物理研究所，长春130033;2.中国科学院研究生院，北京100039;3.长春理工大学，长春130022)

立体视觉是基于像素点视差，根据投影几何三角法原理得到场景中每一个空间点的三维空间信息，进而进行三维信息的整体恢复与重构。在立体视觉中，立体匹配技术是既是重点也是难点，立体匹配的主要任务是得到光滑稠密的视差图，立体匹配的结果直接影响到三维重构效果。

根据文献［1］提出的分类标准，立体匹配算法可分为局部匹配算法［2－6］和全局匹配算法［7－10］两大类。局部匹配算法是基于区域的，通常以参考图像中的某一像素点为中心构造一个邻域支撑窗口，确定相应的相似度计算函数后将该窗口在待匹配图像上进行遍历搜索，计算其与遍历过程中每个窗口的相似度，通常以相似度最大的窗口为最终匹配结果。

目前基于区域的局部立体匹配算法多数直接采用矩形窗口进行计算，这样虽提高了计算效率，但是得到的视差图精度较差，尤其在弱纹理和视差不连续的区域极易产生误匹配，导致最终匹配结果精度下降。全局立体匹配算法主要采用了全局优化函数估计视差，通过建立包含数据项和平滑项的全局能量函数，将视差的求取转化为最小化全局能量函数的求解。目前主要的全局匹配算法有图割法、置信传播算法和动态规划算法。和局部算法相比，全局算法能较好的处理遮挡区域和弱纹理区域，但由于全局能量函数的最优化求解较为费时，导致计算复杂度远高于局部匹配算法，得到高精度视差的同时运行时间也比较长，不适合实时平台应用。

针对目前匹配方法难于兼顾匹配精度和速度的不足，笔者提出一种基于图像分割和可变窗体的联合立体匹配算法，在匹配精度上较主流局部立体匹配算法有了较大的提高，同时使匹配速度得到较大提升，使算法在精度和速度上得到较好的平衡。

1 算法概述

笔者算法以图像分割和可变窗立体匹配为基础，先采用Mean－Shift［11］图像分割算法对彩色立体图像进行精细分割，假设同一色彩分割区域具有相同视差值，并以此构造基于分割的匹配代价。当对匹配图像过度分割时，图像的视差变化会伴随相应的色彩变化，利用此特性可提高视差在不连续区域和弱纹理区域的匹配精度。之后引入基于可变窗的匹配代价函数，它能增强不连续区域和弱纹理区域的匹配精度，最后采用赢家通吃(WTA)搜索策略确定最佳匹配点，一定程度上提高了算法的执行效率。

2 算法实现

2.1 匹配图像分割

图像分割主要是根据色彩信息把图像分割成若干区域组成的集合。采用Mean－Shift算法对图像进行分割，它是一种利用概率分布梯度寻找分布峰值的非参数估计方法，能将图像中像素逐个分类到相应的密度模式下，通过聚类得到一系列互不交叉的区域，在适当的算法参数下能实现图像的过分割，同时它还具有精度高和实时性好等优点。笔者算法中如果分割区域过大则该区域内的视差可能存在较大差异，不满足同一分割区域视差相同的假设，因此为使每个分割区域内视差平滑变化，对待匹配彩色图像使用过分割形成足够小的分割区域块，通过设定合适的算法参数，可得到一个较好的区域分割结果。

2.2 基于图像分割的匹配代价

通常假设p是参考图像Tl中任意一像素点，q是目标图像Tr中一像素点即p∈Tl，q∈Tr，在视差假设为s时其为一对匹配点即p=q－s。此时对于任一对匹配点(p，q)在视差为s时，其基于图像色彩分割的匹配代价可定义为

其中Yp是p在参考图像中的色彩分割区域，Dr为预先设定的固定截断阈值，由于成像时受外界因素影响可能会产生一些异常点，引入截断阈值后可降低异常点的影响，从而增强算法的鲁棒性。

c(p，q)为像素点p和q间的初始匹配代价，将其定义为

其中Rp，Gp，Bp分别代表像素点p的颜色分量; Rq，Gq，Bq分别表示q点的颜色分量。

2.3 基于可变窗的匹配代价

对于基于窗口的局部立体匹配算法，通常假设匹配窗口内的所有像素具有相同的视差值。但实际情况是一般简单固定大小的窗口根本无法满足该假设。文献［12］提出的可变窗口方法在不增加计算复杂度的同时提高了视差精度，较好的保持了局部算法的高效特性。对于匹配图像中任一对匹配点(p，q)，在视差为s时其对应的匹配误差定义为

此处使用像素点的RGB通道值计算匹配误差，它避免了将彩色图像转换为灰度图时对图像颜色细节造成的损失，有利于提高匹配精度。

其中|D|是窗口的大小，则此时窗口选择函数可定义为

式(5)中第1项是支撑窗口内像素的误差平均值，如果窗口内各个像素的视差值接近并且趋于平滑时，该项值将达到最小值;第2项为支撑窗口内的像素间的误差方差，若窗口内像素视差接近平滑时，误差方差此时也接近最小值，此项强化了对窗口内像素间视差平滑的约束性;第3项是让窗口选择评价函数时对大尺寸的窗口更具有倾向性，主要是因为一般情况下大窗口包含的图像信息比小窗口要丰富且不易造成误匹配，尤其是在均匀区域。可变窗体的选择范围为3×3到25× 25之间，k1=1.25，k2=5，k3=－3。

假设视差为s，选择具有最小W(D)的窗口作为可变窗口，则可变窗口的匹配代价为

其中Wp为p的可变窗体;Tr=30为截断阈值。

2.4 联合匹配代价生成

基于彩色图像分割和可变窗口内视差一致性的假设，结合上述两种匹配代价，提出一种联合立体匹配代价聚集函数:

其中n(Yp)是图像色彩分割区域Yp的大小，|Wp|是对应像素可变窗体的大小，α和β是预设权重系数取值分别为α=0.6，β=0.4。

3 实验结果

为验证算法有效性，在Intel core i5 3.0 GHz，4 Gbyts内存的Windows平台下用Opencv编程实现笔者算法，对Middlebury网站提供的4对合成彩色测试图像进行立体匹配。匹配时按照测试平台的要求，各算法都保持测试平台默认参数。在对彩色图像分割时，Mean－shift彩色分割算法的几何空间窗、特征空间窗的半径均设为3，且允许的最小区域为20像素。

图1是用Mean－Shift彩色分割算法的分割结果，通过控制参数，该算法能得到一个较好的分割结果。图2为笔者算法得到的视差结果图，从图2中可看出笔者所得视差图在满足视差平滑约束的同时较好的保留了图像的边缘细节信息，同时由于该算法采用空间距离函数作为匹配代价参考值，所以对于弱纹理和深度不连续区域都得到比较满意的匹配结果。图3为笔者算法得到的计算视差图与标准视差图之间的差异，黑色点表示在无遮挡区域匹配错误的像素点，灰色点表示在遮挡区域匹配错误的像素点，白色大片区域是匹配正确的像素点。图4是不同算法对Cones进行匹配后的效果对比。

图1 M ean-Shift彩色分割结果Fig.1 Color segmentation result by M ean-Shift

表1是根据 Middlebury网站 Middlebury Stereo Evaluation－Version 2提供的3个定量参数nonocc(非遮挡区域误匹配像素百分比)、all(全部区域误匹配像素百分比)、disc(深度不连续区域误匹配像素百分比)，将笔者算法与自适应权重算法(ASW)［13］、基于分割的自适应窗体算法(SASW)［14］进行对比，误差阈值限定为1个像素时，笔者算法的匹配精度要优于其余两个算法。同时为定量分析笔者算法的计算效率，在相同的实验条件下，使用Cones测试图对笔者算法和ASW、SASW进行对比，由于笔者算法计算过程中引入了积分图像节省了匹配代价计算时间，使得算法的计算效率得到较大改善，具体运行时间如表2所示。

图2 实验结果Fig.2 Experimental results

图3 误匹配点(视差值绝对误差＞1)Fig.3 Bad pixels(absolute disparity error＞1)

图4 不同算法Cones视差图Fig.4 The disparity maps of Cones using different algorithm

表1 笔者算法与其它算法性能对比(误差阈值为1个像素)Table 1 Performance com parison of differentmethods(error threshold is 1 pixel)

表2 计算Cones视差图的时间比较Table 2 Time comparison of computing Cones disparitymap

4 结论

笔者在深入研究图像分割和可变窗体立体匹配算法的基础上，提出一种基于图像分割和可变窗联合的立体匹配算法。利用在同一过分割区域视差平滑的假设，获取基于分割的匹配代价;然后结合分割结果，将传统的可变窗理论运用到彩色图像上获取可变窗体的匹配代价;最后配以不同权值合并两类匹配代价，通过WTA搜索策略确定最佳匹配。实验表明该算法相对其他同类局部算法能够更好的对弱纹理区域和深度不连续区域进行匹配，其整体匹配性能比目前较为成熟的自适应权重和基于分割的自适应窗体算法有所提高，算法的效率也得到较大提升。同时也看到了该算法对于大面积遮挡区域和强纹理区域的匹配效果仍然不是很理想，后续将继续深入研究遮挡区域的优化处理，同时继续简化匹配代价函数的计算过程，并着手对该算法进行并行加速，使其运行效率得到更大改善，进而能投入实时应用。

［1］Scharstein D，Szeliski R.A taxonomy and evaluation of dense two－frame stereo correspondence algorithms［J］. International Journal of Computer Vision，2002，47:7－42.

［2］Demaeztu L，Villanueva A，Cabeza R.Stereomatching u－sing gradient similarity and locally adaptive supportweight［J］.Pattern Recognition Letters，2011，32(13): 1643－1651.

［3］De－Maeztu L，Mattoccia S，Villanueva A，et al.Efficient aggregation via iterative block－based adapting support weight［C］//International Conference on 3D(IC3D 2011).Liege，Belgium，2011:7－8.

［4］Hirschmuller H.Innocent J，Garibaldi P.Real－time correlation－based stereo vision with reduced border errors［J］.Journal of Computer Vision，2002，47:1－3.

［5］伍春洪，付国亮.一种基于图像分割及邻域限制与放松的立体匹配方法［J］.计算机学报，2011，34(4): 755－760.

Wu Chun－hong，Fu Guo－liang.Based stereo matching method in image segmentation and neighborhood restrictions and relaxation［J］.Chinese Journal of Computers，2011，34(4):755－760.

［6］Mattoccia S.Accurate dense stereo by constraining local consistency on superpixels［C］//20th International Conference on Pattern Recognition(ICPR2010).Istanbul，Turkey，2010:23－26.

［7］Sun J，Zheng N N，Shum H Y.Stereomatching using belief propagation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(7):787－800.

［8］刘赫伟，汪增福.一种沿区域边界的动态规划立体匹配算法［J］.模式识别与人工智能，2010，23(1):38－44.

Liu He－wei，Wang Zeng－fu.An along the regional border dynamic programming stereo matching algorithm［J］.Pattern Recogntion and Drtificial Intelligence，2010，23(1):38－44.

［9］Wang Z，Zheng Z.A region based stereo matching algorithm using cooperative optimization［C］//CVPR 2008: 117－120.

［10］De－Maeztu L，Mattoccia S，Villanueva A，et al.Linear stereo ma tching［C］ //International Conference on Computer Vision(ICCV 2011).Barcelona，Spain，2011:6－13.

［11］Comaniciu D，meer P.Mean shift:A robust approach toward feature space analysis［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2002，24(5):603－619

［12］Velsler O.Fast variable window for stereo correspondence using integral images［C］//IEEE International Conference on Computer Vision and Pattern Recognition，USA.2003:556－561.

［13］Yoon K J，Kweon S.Adaptive support－weight approach for correspondence serarch［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28 (4):650－656.

［14］Tombari F，Mattoccia S，Distefano L.Segmentation－based adaptive support for accurate stereo correspondence［C］//IEEE Pacific－Rim Symposium on Image and Video Technology(PSIVT 2007).2007.