门宇博，马 宁，，张国印，李 香，门朝光，孙鹏飞

(1.哈尔滨工程大学计算机科学与技术学院，150001哈尔滨;2.哈尔滨师范大学计算机科学与信息工程学院，150001哈尔滨)

立体匹配作为计算机视觉领域中的热点研究内容，在机器人自主导航、物体识别与跟踪、工业控制与检测、地理信息系统、生物医学成像及虚拟现实等领域有着广泛的应用［1-3］.Scharstein 等［4］把立体匹配过程概括为匹配代价计算、匹配代价集成、初始视差计算和视差优化.根据匹配基元的不同，立体匹配算法可以分为基于区域的匹配算法［5］，基于特征的匹配算法［6］和基于相位信息的匹配算法［7］.在基于区域的算法中，Zabih 等［8］提出的传统Census算法，利用像素间的大小关系作为相似性测度，解决了因相机在拍摄过程中受到光照等外部条件影响而产生的参考图像与目标图像之间的灰度差异所造成的匹配效果降低的问题.但传统Census的相似性测度由变换窗口的中心像素的灰度值决定，不能完整的描述矩形变换窗口内的信息，匹配精度不高，并且在中心点像素发生畸变的情况下会出现误匹配.

本文提出一种基于非参数变换和改进动态规划的立体匹配算法，考虑到相邻像素间的视差约束，利用改进的Census算法计算匹配代价，增加区域内像素点与邻域像素均值的比较，将区域内全部像素均值代替了中心点像素，有效地解决了中心点像素的畸变问题，在代价集成中利用全局的改进动态规划方法，大幅提高算法精度.此算法具有较高的匹配精度与鲁棒性，在视差优化中处理图像的非纹理区、深度不连续处和遮挡处，最终获得稠密视差图，得到较好的匹配效果.

1 初始视差图计算

1.1 稀疏Census非参数变换的初始匹配代价计算

Census变换的思想是以待匹配像素点为中心取一个矩形区域，把待匹配像素点灰度值与其邻域的像素灰度值进行对比生成匹配模板，对该模板进行非参数变换获得比特串作为匹配基元，最后利用Hamming距离完成立体匹配［9］.但是由于Census变换匹配法是一种局部算法，没有考虑相邻像素间的视差约束，视差结果的平滑约束受到影响，所以本文提出的基于稀疏Census非参数变换法作为初始代价的计算方法.并且传统的Census变换的相似性测度只依赖于变换窗口的中心像素的灰度值，不能完整的描述矩形变换窗口内的信息，本文算法将邻域像素灰度的平均值作为另一个约束条件，用矩形窗口内所有像素点灰度均值代替中心点的灰度值，并且每隔一行以及一列选择一个像素点与两个均值做比对，获得两位二进制码构成的比特串作为新的匹配基元.改进后的Census变换可以更完整地描述所选取支持区域的像素信息，清晰地区分出两个矩阵窗口图像的不同，同时提高了算法的执行效率，解决了由于中心点因噪声问题发生畸变所带来的误匹配.

稀疏Census非参数变换的原理如图1所示，图1(a)为稀疏Census非参数变换的模板，其中阴影部分为参加变换的像素，图1(b)为传统Census非参数变换的模板.对图像Ⅰ中的像素(u，v)进行稀疏Census非参数变换，首先以像素(u，v)为中心选取一个矩形变换窗口W，其窗口尺寸为n×m，计算窗口内全部像素点的均值，计算公式为

式中:Ⅰ(i，j)为像素(i，j)的灰度值;n':=⎿n/2」，m':=⎿m/2」.以此均值代替中心像素.计算窗口内邻域像素的均值为

将矩形变换窗口内每隔一行以及一列的邻域像素灰度值Ⅰ(u+i，v+j)与窗口内邻域像素点的均值和窗口内全部像素点灰度均值进行比较，可获得一组bit字符串.稀疏Census变换表示为

式中运算符⊗为位连接运算，辅助函数ξ定义为

基于稀疏Census非参数变换的初始代价计算采用Hamming距离的方法，Hamming距离表示两个比特串之间在相同位置上不同比特数的数目总和，相同的位数越多，Hamming距离越短，匹配代价越小，两个像素点越相似.初始代价计算为C(u，v，d)=Hamming(Tr(u，v)，Tt(u+d，v)).式中Tr(u，v)、Tt(u，v)分别为参考图像和目标图像的像素(u，v)对应的稀疏Census变换bit字符串.至此基于稀疏Census变换的初始代价计算完毕，将C(u，v，d)保存在视差空间图 DSI中，作为下一步动态规划算法的输入数据.

图1 稀疏Census非参数变换示意

1.2 行列双向约束动态规划的匹配代价集成

由于空间场景的复杂性以及局部算法的局限性，立体匹配需要借助全局优化技术获得满足平滑约束的视差图.动态规划算法是一种对扫描线进行约束的全局优化算法.该类算法匹配准确率较高，可以获得较高精度的稠密视差图［10］.但是传统的动态规划立体匹配算法缺乏对扫描线列方向上的视差连续性的融合，每一条扫描线被单独处理，缺少了对扫描线之间的约束限制，使得生成的视差图上带有明显的“条纹效应”.本文采用基于行列双向约束的动态规划方法，在已求得的初始匹配代价的基础上，分别在扫描线行方向上和扫描线列方向上进行全局优化以获得平滑的视差图.首先构造全局能量代价函数为

式中:Edata(u，v，d)为对应像素点(u，v)与(u+d，v)之间的初始匹配代价，即已求得的C(u，v，d);Esmooth-h(u，v，d)为扫描线行方向上的平滑约束项，用来约束扫描线行方向上相邻像素点之间的不连续性;Esmooth-v(u，v，d)为扫描线列方向上的平滑约束项，用来约束扫描线列方向上相邻像素点之间的不连续性;Eocclude(u，v，d)为遮挡惩罚项，用来对遮挡像素点进行惩罚.

依据该能量函数分别在扫描线行方向上和扫描线列方向上进行全局优化.由于在扫描线行方向上暂不考虑列方向平滑性约束，行方向能量函数Eh(u，v，d)可简化为由数据项Edata(u，v，d)，扫描线行方向上的平滑约束项Esmooth-h(u，v，d)以及遮挡惩罚项Eocclude(u，v，d)组成.

利用动态规划算法对行方向上每一条扫描线内对应像素点之间的匹配代价值进行求解:

根据扫描线行方向上得到的线内能量函数，对列方向进行动态规划优化.列方向能量函数Ev(u，v，d)即为全局能量代价函数，可由数据项Edata(u，v，d)，扫描线列方向上的视差平滑约束项Esmooth-v(u，v，d)和扫描线行方向上的优化结果Eh(u，v，d)组成.

利用动态规划算法对全局能量代价函数进行全局优化为

将获得的匹配代价和初始视差结果存储于缓存中，作为后续步骤的输入数据.

2 视差图优化

2.1 图像可信性与纹理性检测

虽然利用行列双向约束的动态规划算法可以增加匹配的可信度，但是由于大面积的弱纹理区域所导致的误匹配仍然存在.针对非可信与非纹理的图像区域，本文提出用于判别图像的纹理性和可信性的方法.

像素(u，v)的可信性利用最优与次优匹配代价获得

式中:Δ(u，v)为像素(u，v)最优与次优匹配之差;maxcost为最优匹配代价值.

像素(u，v)的纹理性通过尺寸为n×m的矩形方差滤波函数来判断为

非可信像素与非纹理像素通过两个阈值τ1和τ2来判断，只有满足下式的像素才可以直接赋值为初始视差值.而不满足下式的像素点则利用视差面拟合计算相应的视差，来代替该像素点的初始视差为

2.2 图像分割与视差平面拟合

对非可信像素与非纹理像素利用分割与平面拟合的方法获取最终视差.拟合的像素包括非可信与非纹理两类，利用mean-shift算法［11］对参考图像进行区域分割.mean-shift算法利用概率分布的梯度寻找分布峰值的稳定性高的非参数估计方法，将图像聚类得到一系列互不交叉的区域.

对于每个图像分块，可使用平面方程描述其视差值.将分块内的视差d(x，y)视作关于像素位置(x，y)的函数为

式中:x、y分别为像素(x，y)的坐标;d为该像素对应视差值;(a，b，c)为视差平面的参数，可以用最小二乘法求解平面参数.

式中:矩阵A的第i行元素为［xi，yi，1］;B向量的第i个元素为d(xi，yi).式(2)可以展开为

式中m为分割区域中的像素点个数.本文利用奇异值分解(SVD)求解该表达式.

式中(ATA)-为ATA的Moore-Penrose逆矩阵，可由SVD求得.

3 算法流程

综上所述，本文算法流程如图2所示.

关键步骤归纳如下:

1)采用稀疏Census变换算法对参考图像和目标图像进行局部匹配处理，获取初始匹配代价;

2)利用行列双向约束的动态规划算法对初始匹配代价进行全局优化获取初始视差，其中惩罚系数普遍采用λdisc=20，λocc=15来进行试验;

3)对参考图像逐像素点进行可信性和纹理性检测，确定非可信像素与非纹理像素位置.对于非可信像素的检测，由于图像平面的质量很大程度上取决于用于拟合的数据，所以选取τ1=200这种高可信度的阈值.对于非纹理像素的检测，为了综合提高算法可行性与准确度，在不失准确性与运算速度的同时能够检测出弱纹理区，选取τ2=20;

4)按照纹理性对参考图像进行二值化分割，同时利用mean-shift算法对参考图像进行灰度区域分割;

5)利用奇异值分解计算分割面参数，将非可信像素与非纹理像素的视差值用视差平面拟合的结果替换;

6)将计算结果合并为最终的稠密视差图.

图2 算法流程

4 实验分析

为了验证本文算法的有效性与正确性，本文利用VC++编程实现了所提算法.实验对象采用Middlebury大学立体视觉数据库中提供的4组标准立体图像［4］:包括 Tsukuba、Teddy、Venus 和Cones图像，尺寸分别为384像素 ×288像素、434像素×383像素、450像素 ×375像素和450像素×375像素，图像均已进行了极线校正，视差只存在于同扫描线方向，视差搜索范围的最大值分别是16、20、60和60像素，通过对上述图像分别进行测试验证本文算法的匹配效果.图3给出了本文算法的实验结果.

同时为了更好地评测本文算法的立体匹配结果，本文实现了另外两种文中涉及到的算法，一种算法是经典的动态规划立体匹配算法(DP算法)［4］，另一种算法是 Humenberger 等［12］提出的改进Census非参数变换立体匹配算法，该方法是目前非参数变换类型的算法中效果较好的一种 (简称RTCensus算法).

图3 本文算法的立体匹配实验结果

图4给出了3种算法的实验结果图.可以看出，DP算法生成的视差图平滑性较好，物体边缘较清晰，但视差结果中存在着明显的条纹状效应，导致了错误视差向相邻像素传递;RTCensus算法生成的视差图在纹理丰富区域效果较好，但在物体边界处(遮挡或不连续区域)，产生边界模糊现象，在弱纹理区域同样存在错误匹配;本文算法得到的视差结果优于DP算法和RTCensus算法的实验结果，由于同时考虑了行列双方向上的视差不连续性，明显消除了条纹状效应，且利用分割与平面拟合技术，在弱纹理区域、遮挡区域和视差不连续区域得到的匹配效果更加理想.另外，本文算法的初始代价计算利用了Census变换，使得算法具有一定的抑制噪声能力.

图4 基于标准立体图像的3种算法比较实验结果

表1给出了3种参加比对实验的算法在错误匹配率方面的量化实验结果.表1为Nonocc(非遮挡)区域的错误匹配率;All(包括遮挡区域在内的整体)区域的错误匹配率;Disc(视差不连续)区域的错误匹配率.由表1给出的量化结果显示，本文提出的算法在非遮挡区域、整体区域和视差不连续区域的错误匹配率都明显低于DP算法和 RTCensus算法，取得了较高的匹配精度.

表1 本文算法与DP算法、RTCensus算法的量化实验结果比较

根据上述实验结果可知，本文算法有效解决了立体影像的匹配问题，算法匹配正确率较高，尤其在弱纹理区域、遮挡区域和视差不连续区域具有良好的稳定性.

5 结语

本文提出一种基于非参数变换和改进动态规划的立体匹配算法，采用稀疏Census变换计算初始局部匹配代价，构造基于行列双向的全局能量函数，并利用改进动态规划算法求解初始视差，对非纹理与非可信区域的像素，通过视差平面拟合代替初始视差结果.算法最大限度地利用了图像纹理信息以及扫描线相邻像素点间的平滑信息，有效克服了弱纹理区域、遮挡区域和视差不连续区域对视差结果的影响.实验结果表明，该算法在匹配效果和匹配精度方面均优于传统的动态规划立体匹配算法和鲁棒性较好的基于Census非参数变换立体匹配算法，降低了错误匹配率，可以获得匹配准确率较高的稠密视差图，得到较好的匹配效果.

［1］BROWN M Z，BURSCHKA D，HAGER G D.Advances in computational stereo［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence， 2003，25(8):993-1008.

［2］HUMENBERGER M，ENGELKE T，KUBINGER W.A census-based stereo vision algorithm using modified semi-global matching and plane fitting to improve matching quality［C］//Proceeding of the 2010 IEEE Computer Society Conference on Computer Vision and PatternRecognition Workshops(CVPRW).San Francisco，CA:IEEE，2010:77-84.

［3］ KUMAR S，KUMAR S，SUKAVANAM N，et al.Human visualsystem and segment-based disparity estimation ［J］. AEU-International Journal of Electronics and Communications，2013，67(5):372-381.

［4］SCHARSTEIN D，SZELISKI R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms［J］.International Journal of Computer Vision，2002，47(1/3):7-42.

［5］ RHEMANN C，HOSNI A，BLEYER M，et al.Fast cost-volume filtering forvisualcorrespondence and beyond［C］//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition(CVPR).Washington， DC:IEEE ComputerSociety， 2011:3017-3024.

［6］ NIERADKA G，BUTKIEWICZ B S.Features stereo matching based on Fuzzy logic［C］//Proceedings of the Joint 2009 InternationalFuzzy SystemsAssociation World Congress and 2009 European Society of Fuzzy Logic and Technology Conference.Lisbon，Portudal，2009:1188-1193.

［7］ULUSOY I，HANCOCK E R.A statistical approach to sparse multi-scale phase-based stereo［J］. Pattern Recognition，2007，40(9):2504-2520.

［8］ ZABIH R， WOODFILL J. Non-parametricLocal Transforms for Computing Visual Correspondence［M］.Springer，Berlin-Heidelberg:Computer Vision—ECCV'94，1994:151-158.

［9］FIFE W S，ARCHIBALD J K.Improved census transforms for resource-optimized stereo vision ［J］. IEEE Transactions on Circuits and Systems for Video Technology，2013，23(1):60-73.

［10］TORR P H S，CRIMINISI A.Dense stereo using pivoted dynamic programming［J］.Image and Vision Computing，2004，22(10):795-806.

［11］COMANICIU D，MEER P.Mean shift:a robust approach toward feature space analysis［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(5):603-619.

［12］HUMENBERGER M，ZINNER C，WEBER M，et al.A fast stereo matching algorithm suitable for embedded real-time systems［J］.Computer Vision and Image Understanding，2010，114(11):1180-1202.