基于强相似点检测快速双目立体匹配算法

马龙，孙铭泽，黄超，裴昕，周航，张鸿燕

中国民航大学中欧航空工程师学院，天津300300

基于强相似点检测快速双目立体匹配算法

马龙，孙铭泽，黄超，裴昕，周航，张鸿燕

中国民航大学中欧航空工程师学院，天津300300

1 引言

近年来实时准确地获取移动机器人工作空间的三维信息成为机器人视觉导航、障碍物检测与环境地图构建中的一个研究热点，其匹配速度对于视觉导航，特别是在障碍物检测技术的实际应用中起着重要的作用[1]。

立体匹配作为计算机视觉的一个重要方向，是通过多视点图像还原出物体深度信息的主要手段[2]。目前，根据匹配不同的基元，立体匹配主要分为特征点匹配与区域特征匹配[3]。两者各具优势与不足。其中Andrej Satnik等人[4]通过将不同特征描述方法进行比对，并优化了立体匹配方法，但基于特征点的立体匹配方法仍然难以得到稠密的视差图[5]。而根据文献[6]，基于基元的立体匹配方法根据最优化理论方法的不同，分为全局与局部立体匹配方法。全局匹配方法是指通过构造全局能量函数，并通过该函数得到全局最优解的方法得到最优视差，其包括图割（graph cuts）[7]、信念传播（belief propagation）[8]等。虽然全局方法能够得到精度很好的结果，但受限于复杂的建模过程，需要大量计算时间，即使较快的情况下也需要几十秒的计算时间。从文献[9]可以看出，虽然近年来全局方法得到进一步发展，但其速度仍然难以满足实时性要求。局部匹配方法[10]通过采用固定形状和大小的支撑窗口计算匹配代价，再将其聚合得到视差，根据不同的匹配代价函数，其包括灰度匹配灰度绝对值和（Sum of Absolute Differences）[11]、灰度平方差和（Sum of squared Differences）[12]、自适应权重（Adapt Weight）[10]与归一化互相关（Normalized Cross Correlation）[13]等局部方法。虽然相比于全局方法在精度上有所牺牲，但是在速度上却有较大提高。由于SAD代价函数计算简单，近年来在机器人导航、障碍物检测等实时立体匹配的领域内得到了广泛应用[14]。

基于以上问题，本文提出了一种基于强相似点的快速双目立体匹配算法。首先对采集图像进行对极化处理；其次，将图像进行灰度转化，并选取与待匹配点相似高的点作为强相似点，在强相似点的集合内计算最优视差；最后将得到整个视差图进行视差修正与滤波，保证视差的精度，得到最终视差。利用标准数据集与实际室内场景进行了实验验证，验证了本文算法的有效性。

2 双目视觉系统

如图1所示，双目立体视觉成像的模型一般为两个并排放置的摄像头。其中Ol与Or分别为左右相机光心，两个光心之间距离为T,P为真实空间中一点，它成像在左右两相机的坐标分别为Pl(xl,yl)和Pr(xr,yr)。

图1 双目视觉模型

若两相机严格水平并排放置，则目标的深度与在两图像上的视差成反比，视差定义为d=xl-xr。根据三角相似原理，深度为：

然而实际情况下两相机很难做到严格平行放置，所以需要在进行立体匹配前对图像进行极线校正，进行极线校正之后的图像不但易于计算目标深度，还减少了立体匹配的计算量，提高了系统速度。图片校正后结果如图2。

图2 极线校正结果

从图2中可以看出，经过极线校正后，左图像上任一点在右图像上的匹配点一定在同一条水平线上。除此之外，校正会将相机畸变的影响进行消除，从而造成了如左图上方的黑区出现。

3 算法原理

3.1 强相似点定义

在许多研究中，关于基于特征点的视差求解一直难以得出稠密视差，而基于局部窗口的求解方式需要在整个搜索空间上进行计算，导致计算量较大[10]。强相似点指的是与待匹配点相似度强的点，并且在该待匹配点对应的视差搜索空间内。为了进一步加快速度，本文直接通过待匹配点与其对应视差搜索范围内的点的灰度值差的绝对值作为相似度评价函数。当两点灰度值小于阈值时，即定义为强相似点。如式（2）所示，其中fL(x,y)与fR(x,y)分别表示点(x,y)在左右图的灰度值，δ表示设定阈值。

若在该点对应的匹配区域内不存在强相似点，则以每次增加定量增大阈值δ，直至出现强相似点或者到达迭代上限。其中最大迭代次数为5次，定量增量为初始阈值的20%。随着增量幅度的增大，强相似点与原点的相似度越低，会导致匹配效果下降，但与此同时由于能够提取到更多的强相似点因而能够减少立体匹配中相似度函数的计算量，减少运算时间。若到达最大迭代次数依然没能出现强相似点，则将所有在匹配区域内的点都作为该点的强相似点，也就是正常计算所得待匹配的点。与传统的特征点不同，强相似点的计算更加简单，而且计算区域也明显小于特征点提取。因此与特征点提取相比，其计算量更小，且计算速度更快。

虽然在不同场景情况下光照强度不同，但是由于双目相机间距较小，左右相机采集图像差异较小，导致不同场景下对选取相同阈值的匹配效果影响有限。同时阈值的选取更多是考虑到匹配的效果与速度，并通过实验结果与分析，阈值取10的情况能够在不同场景下均具有较好的适应性。

3.2 基于强相似点的快速匹配

本文通过局部匹配窗口的方式进行视差求解，相比较于全局匹配局部匹配具有速度快的优势，同时能生成特征点匹配方式不具备的稠密视差图。如图3所示，区域匹配通常为以左图像中待匹配点p为中心，选择一个区域，以此区域中的灰度信息来表征该匹配点的性征，同时在右图像中以任意一个对应的待匹配的点q为中心选取同样大小的区域，对两个区域的相似测度进行计算，此时若相似测度函数能够取得极值，两个区域就被称为相互匹配。

图3 局部匹配窗口

虽然SAD减少计算量的同时会对匹配的质量造成影响，但是其在速度上的提高要远远优于SSD与ASW。因此为了简化计算量，增加算法速度，从而满足整个算法在实时性上的性能，本文选取了Sum of Absolute Differences（SAD）匹配代价作为相似测度函数，其计算公式如下所示：

其中IL(X,Y)为左图像在(X,Y)位置上的灰度值，同理IR(X,Y)为右图像该点的灰度值。本文算法仅对待匹配点的强相似点的区域进行相似测度计算，并取其中数值最小的点进行计算得出视差。由于大部分的待匹配点的强相似点的数量要远小于视差搜索范围，因此减少了相似测度函数的计算区域，而立体匹配中大部分的时间是用来进行区域匹配的相似度函数计算，因此本方法能够有效地减少视差的计算时间。

3.3 视差修正与滤波

在得到基于强相似点的立体匹配结果之后，算法又通过遮挡点检测与平滑滤波进一步修正视差结果，使得在速度得到提高的同时，保证了匹配的精度。

遮挡点检测就是以右图像参考点为基准，在左图像中搜索匹配点，则其在左图像上得到的匹配点应该与右图像参考点一致。设d(i,j)和d′(i,j)分别为从右向左和从左向右匹配计算得到的视差，对于计算出的匹配点应当满足：

不满足则不是匹配点，即为遮挡点。在经过左右遮挡点检测得到遮挡点位置之后，需要对遮挡点进行过滤。对于遮挡点p，分别找到p点左方向与右方向的第一个非遮挡点，即为pl与pr。即点p的视差值为：

在进行遮挡点检测与处理之后，算法还对图像进行平滑滤波，去除遮挡过滤可能产生的水平条纹。滤波前后图像如图4、图5所示。在图中可以看到，图片右区域的横线减少，同时屋顶区域也得到了改善。最后通过与数据集标准视差图对比，得出平滑滤波会将误差再降低1%左右。

图4 平滑滤波前视差图

图5 平滑滤波后视差图

4 实验结果与分析

4.1 Middlebury数据集结果及分析

为了验证本文算法的性能，在实验中使用来自Middlebury大学立体视觉网站的图像集和实验室室内实际环境的立体图像进行测试和对比分析。实验所用计算机配置：实验环境为Inter®CoreTMi7-4500U CPU 1.80 GHz，Windows 7 64位操作系统，算法程序在Visual Studio 2013环境设计完成。

其中标准数据集实验中分别采用SAD匹配算法、Sum of Squared Differences（SSD）匹配算法、ASW匹配算法和本文算法进行实验比较验证。其中Adapt Size Weight（ASW）算法精度较高，用于进行准确度的对比。而本文算法中阈值δ设定为10，SAD窗口选择为7。方便起见本文图像只给出Teddy数据集中右图像实验图像结果。Teddy数据集实验结果如图6所示。其中图6（a）～6（d）分别表示原始SAD、SSD、ASW与本文方法的匹配代价计算结果，而图6（e）与6（f）则表示标准视差与原始图像用来比较匹配结果的好坏。

从图6（a）和图6（d）可看出，本文算法相对于SAD区域算法，计算得到视差精度较高，较好地解决了遮挡区域的视差问题，不但精确地再现了布偶、玩具房子与画布的轮廓，还对轮廓边缘区域得到了比较可信的结果。但是由图6（c）和图6（d）可知，本文算法仍然存在一些匹配效果欠佳的区域，主要原因是在屋顶区域的纹理信息不够丰富，而在物体边缘处本文算法依然要由优于ASW算法。对于不同数据集精度比较如表1所示。

表1 本文算法与其他算法误差率比较%

表1中分别表示了不同数据集下每种算法计算出视差图的误差率（百分比）。从表1和图6不难看出，与SAD、SSD相比，本文匹配效果得到改善，与ASW算法相比精度接近在某些情况下，甚至性能优于ASW算法。

图6 Teddy数据集实验结果

而在表2中可以看出，SAD虽然精度较低，但是具有明显的速度优势，与速度较快的SSD方法相比，SAD精度相差2%左右，速度却提高2倍，而与精度较高的ASW方法相比，虽然精度相差5%，但是在速度上SAD提高超过100倍。本文算法与传统SAD算法相比，速度提高约为三倍，因此能够满足在对速度要求高的实时匹配场景下的应用。

表2 本文算法与其他算法运算时间比较s

4.2 室内环境实验结果及分析

本文还在是室内环境下进行实测。在实验过程中，通过自主设计的双目视觉平台作为实验平台。该双目摄像头的设计与应用目标为安装在室内无人机上，向无人机平台提供视觉数据，进而计算获取深度等信息。

图7 室内实验结果

首先采集一组图像进行极线校正，再将校正后图像通过本文算法进行立体匹配，其中阈值为大小为10，最高迭代次数为5，最后得出视差结果。实验中首先将本文方法与常在实时双目系统使用的优化SAD进行比对。虽然与本文方法都选取相同的SAD匹配代价函数进行匹配代价计算，但对比算法为了满足实时性的要求而牺牲了匹配的质量，本文则通过强匹配点进行匹配精度的增强，并通过遮挡点的检测与处理进一步优化了匹配的质量。因此从图7（c）与图7（d）的对比中可以看出，本文算法相比较于优化SAD算法，本文获得的视差图更加完整，而且细节的还原也更高。同时如图7（e）～图7（j）所示，本文还将系统在室内环境下不同场景进行了实验，其中不同场景具有不同光照强度与光照分布情况，实验结果表明本文方法能够在室内环境下满足立体匹配质量与环境适应性上的要求。

同时由于双目视觉平台采集图像的分辨率为640×480，比标准数据集的分辨率更低，也因此具有更快的计算速度，但是由于实物图具有对图像的校正，去畸变等处理，导致整体时间略有增加，依然可控制在0.9 s左右，能够满足旋翼飞行器的实时性要求。

5 结束语

本文提出了一种基于强相似点的快速匹配算法。在不损坏精确度的情况下，大大增加了匹配的速度，提高了匹配效率。加速与遮挡点处理，保证了系统的检测的速度与准确性。实验表明，所述算法相比于速度较快的SAD算法，能够提高近三倍匹配速度，同时精度提高3%。又通过实验验证了本文算法的实际价值，为立体匹配算法在视觉导航、障碍物检测等方面的应用奠定了良好基础。

[1] 王军华，李丁，刘盛鹏.基于改进RANSAC的消防机器人双目障碍检测[J].计算机工程与应用，2017，53（2）：236-240.

[2] Watanabe Y，Calise A，Johnson E.Vision-based obstacle avoidance for UAVs[C]//AIAA Guidance，Navigation and Control Conference and Exhibit.South Carolina：American Institute of Aeronautics and Astronautics Press，2007：20-23.

[3] Hirschmuller H.Stereo processing by semiglobal matching and mutual information[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2008，30（2）：328-341.

[4] Satnik A，Hudec R，Kamencay P，et al.A comparison of key-point descriptors for the stereo matching algorithm[C]//Radioelektronika，2016：292-295.

[5] 贺利乐，路二伟，李赵兴，等.基于ORB算子的快速立体匹配算法[J].计算机工程与应用，2017，53（1）：190-194.

[6] Hong G S，Kim B G.A local stereo matching algorithm based on weighted guided image filtering for improving the generation of depth range images[J].Displays，2017，49：80-87.

[7] Rother C，Kolmogorov V，Blake A.GrabCut：Interactive foreground extraction using iterated graph cuts[J].ACM Transactions on Graphics，2004，23（3）：309-314.

[8] Sun J，Shum H Y，Zheng N N.Stereo matching using belief propagation[C]//European Conference on Computer Vision.Berlin Heidelberg：Springer，2002：510-524.

[9] Cao G，Peng H.Graph cut stereo matching based on region consistency[J].Journal of Northwestern Polytechnical University，2017，35（1）：160-163.

[10] Huang D.Improved Yoon stereo matching algorithm based on adaptive weight[J].Journal of Electronic Measurement&Instrument，2010，24（7）：632-637.

[11] Tabssum T，Charles P，Patil A V.Evaluation of disparity map computed using local stereo parametric and nonparametric methods[C]//International Conference on Automatic Control and Dynamic Optimization Techniques，2017：104-109.

[12] Song Y.A computational optimization method of the SSD and NCC algorithms of the stereo matching[J].Computer Engineering&Applications，2006，42（2）：42-44.

[13] Chen D，Ardabilian M，Wang X，et al.An improved nonlocalcostaggregationmethodforstereomatching based on color and boundary cue[C]//IEEE International Conference on Multimedia and Expo，2013：1-6.

[14] Zhu S，Gao R，Li Z.Stereo matching algorithm with guided filter and modified dynamic programming[J].Multimedia Tools&Applications，2017，76：1-18.

MA Long,SUN Mingze,HUANG Chao,et al.Fast binocular stereo matching algorithm based on strong similarity detection.Computer Engineering andApplications,2018,54（6）：193-197.

MALong,SUN Mingze,HUANG Chao,PEI Xin,ZHOU Hang,ZHANG Hongyan

Sino-European Institute ofAviation Engineering,CivilAviation University of China,Tianjin 300300,China

Stereo matching is an important branch of binocular vision,which can reduce the three-dimensional information through the depth map,but because of its huge amount of computation,real-time is difficult to be guaranteed.In this paper,a fast stereo matching algorithm based on strong similarity is proposed.Firstly,the binocular image is processed by the pole,so that the matching region is fixed on the same horizontal line,and the matching region is reduced.Secondly,the image is gray,and the points in the search range which are close to the gray value of the matching points are defined as strong similarities.The matching cost of the strong similarity points is calculated and the optimal parallax is obtained.Point for normal parallax calculation,the final parallax correction and filtering,get the final parallax.The results show that the proposed method can improve the accuracy of SAD by 70%without compromising the accuracy rate,which provides a good foundation for the practical application of stereo matching algorithm.In the visual navigation,obstacle detection also has a good application prospects.

binocular vision;epipolar rectification;stereo matching;strong similarities;matching cost

立体匹配是双目视觉的一个重要分支领域，能够通过深度图还原出三维信息，但由于其计算量庞大，实时性难以得到保障。为此，提出了一种基于强相似点的快速立体匹配算法。首先，将双目图像通过对极处理，使匹配区域固定在同一水平线上，减少匹配区域；其次，对图像进行灰度转化，并将搜索范围内与待匹配点灰度值接近的点定义为强相似点，对强相似点所在块进行匹配代价计算，并得出该点最优视差，对不存在强相似点的待匹配点进行正常视差计算；最后将进行视差修正与滤波，得到最终视差图。经Middlebury算法测试平台的提供数据进行验证，结果表明在不损失精确率的前提下，该方法相对于SAD速度提高70%左右，为立体匹配算法的实际应用奠定了良好基础，在视觉导航、障碍物检测方面也有着良好的应用前景。

双目视觉；极线校正；立体匹配；强相似点；相似代价

2017-08-25

2017-10-13

1002-8331（2018）06-0193-05

A

TP242.6；TP301.6

10.3778/j.issn.1002-8331.1708-0313

国家自然科学基金委员会与中国民用航空局联合资助（No.U1633101）；中央高校基本科研业务费中国民航大学专项（No.3122015Z003）。

马龙（1983—），男，博士，讲师，主要从事精密测量，光学无损检测和导航信息融合等方面的研究，E-mail：malong9904@aliyun.com；孙铭泽（1993—），男，硕士研究生，主要从事双目视觉与导航方面的研究。