基于广度优先视差优化的双目立体匹配

吴志伟

（四川大学计算机学院，成都 610065）

基于广度优先视差优化的双目立体匹配

吴志伟

（四川大学计算机学院，成都 610065）

双目立体匹配属于三维重建的重要环节，匹配所获得的视差图很大程度上影响着模型的重建质量。在原有局部特征的双目立体匹配算法的基础上，提出一种基于广度优先搜索的视差优化后处理方法；在左右一致性检测之后添加视差优化过程，结合局部特征的双目立体匹配算法，计算出的视差准确率有进一步的提升。使用通用计算进行并行优化，提高实时三维重建的精度。

双目立体匹配；视差优化；广度优先搜索

0 引言

三维重建属于计算机视觉中的热门话题。基于双目立体匹配的三维重建近年来被国内外研究人员广泛研究。双目立体匹配算法利用仿生学原理，依据双目生物立体视觉成像原理，对左右双目图像对进行扫描线搜索匹配得到视差图，从而还原真实三维场景。

双目立体匹配算法主要分为两大类：局部特征匹配和全局优化匹配。前者具有强纹理区域精确度高、可并行优化等优点，常见为自适应支持权值方法（AW）[1]。但是该算法使用局部特征进行扫描线搜索，在弱纹理区域，使用Winner-Takes-All策略将很难找到真实匹配点对。后者使用动态规划（DP）、图割（GC）、置信度传播（BP）等全局优化方法[2～3]，将视差图的计算转化为以代价函数作优化目标的最优化问题，保证了图像上临近点之间的约束关系，同时在弱纹理区域能够得到较准确视差。但是全局优化过程会消耗大量的计算时间，在现今的计算机硬件条件下还很难实现实时处理。

立体匹配算法可以分别计算出左右图视差，再对两视差图进行左右一致性检测，找到视差非一致性的区域进行填补[1]。通常通过搜索非一致点左右临近的可信视差中较小值作为该点的视差，并没有进一步考虑输入图像中的色块特性加以优化。

针对以上提到的问题，本文提出一种基于广度优先搜索的视差优化算法对自适应支持权值算法的视差图进行后处理。结合局部算法的可并行特性，实现实时高精度三维重建。

1 自适应支持权值双目立体匹配

自适应支持权值[1]的双目立体匹配是局部立体匹配常用方法之一。该方法首先使用SAD算子获得初始代价，再对局部窗口的初始代价进行聚合。代价的聚合其实就是对窗口内代价进行加权平均。其中，同时使用色彩和结构的距离来确定窗口中每一个点的权重，确保自适应的代价聚合。本文使用三次聚合迭代进一步提高算法精度。对于聚合后的新代价，使用Winner-Takes-All策略进行匹配，即可求得视差图。图1为Middlebury双目数据集[4]中的Teddy像对左右视差图。

2 左右一致性检测

如图1所示，立体匹配得到的左右视差图中，存在许多噪声点，可以通过左右图像素位置关系找到视差不一致区域，进行修补。

图1 左右视差图

图2 左右一致性检测结果

在左视差图LD中进行遍历，对每一个遍历点P，通过该点视差LD[P]可得到右图中该点对应位置Q，在右视差图RD中对应位置得到视差RD[Q]，比较LD[P]与RD[Q]绝对值差是否在一个可接受的范围内。当LD [P]与RD[Q]差距较大（本文取绝对差大于1）时，记录当前点为一个左右不一致点，本文定义为A类不一致点。

视差的值与景深成反比，对于现实场景的三维重建问题，视差值通常在一个可预测的范围，这就使得视差结果不能太小。视差图中，视差凡是小于最小值（本文取为3个像素）的点，被标记为B类不一致点。由于双目图像边缘存在遮挡，视差图的边缘部分只能使用启发式的方式进行填补，与边缘相连的A类不一致点也将调整为B类不一致点。这时需要使用广度优先搜索算法[5]对不一致区域进行连通检测，具体步骤如下：

①初始化已访问数组，全部置为未被访问状态，令计数变量i为0；

②初始化一个待访问队列，从左视差图边缘的每一个像素点出发，当前遍历点如果未被访问，且为不一致点，则插入到队列中；

③如果队列已经为空则进行步骤5，否则从队列中弹出队首元素像素点K，标记为已访问，将其记录到B类不一致点集合Seti（N为Set集合个数，且0≤i≤N-1）中，获得其四个方向的邻居像素点N[4]；

④对四个邻居点中的每一个N[j]进行边缘检测，如果N[j]在原图中不属于颜色梯度较大的点，且为不一致点，则将之插入到队列中，对四个点都处理完毕后进行③；

⑤计数变量i增加1并回到②，直到边缘像素全部遍历完，结束算法。

A类、B类不一致点统称为不一致点，如图2黑色（像素值为0）区域所示。

3 视差填补

对不一致点进行视差填补操作。A类不一致点，一般出现在视差可信区域，由于一些噪声或者局部弱纹理区域造成的，直接选择距离当前点最近的左右两个一致点的视差进行填充。

B类不一致点通常是弱纹理区域造成的，针对这样的点，使用上文提到的方法在一些图像边缘区域信息量不足的情况下将无法进行合理的填补。本文通过广度优先搜索找到所有的B类点集Seti（0≤i≤N-1），对与点集直接相邻的一致点的视差进行K-means聚类[6]。再找出视差出现个数最多的前K个类（本文K取1），使用这K个类中所有点进行平面拟合，得到一个平面方程，将B类点集中的坐标代入方程即为该坐标点处的视差。

4 实验结果与分析

编程对Middlebury的Stereo双目图像数据集[4]进行对比实验，平均误差相对于原自适应支持权值算法（AW）有了一定的提升，实验结果的视差图如图3和图4所示。

图3 AW算法

图4 本文算法

图3为原自适应支持权值算法，图4为本文算法。可以看出本文算法改善了很多受弱纹理影响的视差缺陷，并且解决了原有算法对于Teddy双目像对玩具小熊轮廓不分明等问题；在Middlebury上的排名[4]也有所增加。使用CUDA[7]进行GPU通计算减少本算法运行时间到毫秒级别，进而实现了实时三维重建。

参考文献：

[1] K.-J.Yoon and I.-S.Kweon.Adaptive Support-Weight Approach for Correspondence Search[J].PAMI，,2006，28(4):650～656

[2] D.Scharstein and R.Szeliski.A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms[C].IJCV 2002

[3] Q.Yang,L.Wang,R.Yang,S.Wang,M.Liao,D.Nistér.Real-time Global Stereo Matching Using Hierarchical Belief Propagation[C]. BMVC，2006

[4] Middlebury Stereo Vision Page.http://vision.middlebury.edu/stereo/

[5] Thomas H.Cormen and Charles E.Leiserson.算法导论[M].潘金贵,顾铁成.北京:机械工业出版社出版，2006：324

[6] J.B.MacQueen.Some Methods for classification and Analysis of Multivariate Observations,Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability[J].Berkeley,University of California Press,1:281～297

[7] CUDA Parallel Computing Platform.http://www.nvidia.com/object/cuda_home_new.html

Binocular Stereo Matching Based on Breadth-First Disparity Optimization

WU Zhi-wei
(College of Computer Science,Sichuan University,Chengdu 610065)

Binocular stereo matching is the most important part of 3D reconstruction.The quality of the reconstruction is greatly influenced by the disparity map.Based on the raw local methods,proposes a breadth-first optimization algorithm for the post processing of disparity.Adds parallax optimization process after the consistency checking,combined with the binocular stereo matching algorithm of local characteristics.With the local stereo matching,the result shows the increased accuracy.

Binocular Stereo Matching;Disparity Optimization;Breadth First Search

1007-1423（2015）02-0055-03

10.3969/j.issn.1007-1423.2015.02.014

吴志伟（1990-），男，四川眉山人，硕士，研究方向为计算机视觉与图像处理

2014-11-13

2014-12-16

四川省科技创新苗子工程（No.2014-033、No.2014-034）