基于ELAS立体匹配算法的研究与改进

张道德， 伍 渊， 吴良溢， 胡新宇

(1 湖北工业大学机械工程学院， 湖北 武汉 430068；2 武汉市轻工装备工程技术研究中心， 湖北 武汉 430068)

基于ELAS立体匹配算法的研究与改进

张道德1,2， 伍 渊1,2， 吴良溢1，2， 胡新宇1，2

(1 湖北工业大学机械工程学院， 湖北 武汉 430068；2 武汉市轻工装备工程技术研究中心， 湖北 武汉 430068)

在双目机器人视觉伺服控制中，双目立体匹配算法的实时性和准确性，对机器人的精确定位及控制至关重要。在研究现有的一些先进性立体匹配算法的基础上，引入一种基于视差平面的局部立体匹配算法ELAS(算法，将该算法与先进的立体匹配算法对比发现，其克服了现有算法需要给定最大视差值范围才能获得较好视差图的缺点，综合处理时间和处理效果，表现最好。介绍ELAS算法原理,并分析其存在的问题，针对ELAS算法处理效果不佳的问题，根据视差连续原理，研究改进的ELAS算法，并使用引导滤波器处理视差图。实验证明，改进的ELAS算法显著提高了原算法的效果，而处理时间增加不多，在不考虑实时性的情况下，结合上述滤波器后，处理效果能够接近真实视差图。

立体匹配; ELAS; 滤波; 实时性

在基于双目视觉的视觉伺服中，视觉图像采集和处理的实时性至关重要[1]。视觉图像处理算法的识别效果，影响着机器人或机器手动作的准确性[2]，而立体匹配求解视差是最为关键的一步。根据视差值和像素位置计算场景中目标的三维坐标信息，进而，控制机器人或机械手达到目标位置，构成了视觉伺服的基本过程。立体匹配是由左右图像获得图像中场景的视差值，生成视差图的过程。现有立体匹配算法可以划分为全局方法和局部方法两类[3]。全局方法通过能量函数最小化来获得匹配结果，精度较高但效率较低，运行时间过长，不能满足实时性应用。局部方法利用窗口内的邻域信息来进行单像素匹配，视差计算依赖于待匹配点周围的相邻像素值。其优点是计算复杂度低、运行速度快，但对遮挡或纹理一致等局部歧义区域非常敏感，误匹配率较高。立体匹配的步骤分为：匹配代价计算、匹配代价聚合、视差获取、视差细化。算法的优劣主要体现在前两个步骤，其中匹配代价的计算采用的相似度函数一般采用差的绝对值AD(absolute intensity differences)和差的平方SD(squared intensity differences)等。在匹配代价聚合阶段，局部的立体匹配算法一般在聚合函数后加入与窗口有关的平滑项，而全局的立体匹配算法则加入全局约束项。

著名的opencv开源库在当前发布的立体匹配算法中，选取了3种较为先进的算法，分别为BM(Block Matching)、SGBM(Semi-GloBal Matching)和GC(Graph Cut)。BM算法是一种局部立体匹配算法，它使用了块匹配的思想，即使用包围像素的局部窗口，对比两个局部窗口的相似性，来获得正确的视差。该思想被广泛应用于其他的一些立体匹配算法中。SGBM也是一种局部立体匹配算法，由Heiko Hirschm等人[4]于2008年提出，它加入动态规划的思想，不同于一般只局限于极线上的视差搜索，而是通过多方向的路径搜索找到最佳的视差值，因而被称为Semi-GloBal。GC算法则是一种全局立体匹配算法，由Martull,S和Martorell,M.P等人[5]于2012年在ICPR会议中提出，基于图割，利用最小分割最大流技术，加入全局能量约束项，能获得较好的视差图。Geiger等人在2010年ACCV会议提出了一种算法——ELAS(Efficient LArge-scale Stereo)，ELAS算法是一种基于视差平面的快速立体匹配算法，不需要进行密集重建，仅进行视差估计即可，大大减少了匹配时间，在单核cpu(i5)上能达到每秒计算100万个像素点视差的速度[6]，是一种先进的局部立体匹配算法，该算法的time/Mp(时间/百万像素)值第二小，可以应用于对实时性要求较高的视觉伺服领域。

1 常用立体匹配算法与ELAS的比较

本文所有实验采用的cpu为CORE i7 4710 M。以下实验使用Middlebury测试网站上著名的Tsukuba(384×288)、Teddy(450×375)和Cone(450×375)测试图，实验的误匹配率是通过与真实视差对比得出。ELAS算法的参数选择为:γ=5，β=0.02，σ=1(参见下文公式) 。其余的参数如，视差范围和SAD窗口大小等与其他3种算法(BM算法，SGBM算法，GC算法)相同，由于其他3种算法中所使用的最大视差值会影响视差搜索范围和相似区域的数量，因此它的取值对这些算法的速度和效果均有很大影响，而ELAS却不需要设置该值就可获得具有参数唯一性的视差图，故其值由ELAS计算出来后再设置给其他三种算法(表1，图1)。

表1 立体匹配算法比较

图 1 立体匹配算法效果对比

实验结果表明，BM算法速度最快，完全可以应用于实时性较高的场合，但误匹配率(阈值为一个像素差，即bad1.0)却过高。从数据来看，GC算法时间最长，只有在处理背景较暗，且和前景色差较大的Tsukuba，才有较好的表现效果，这是因为GC利用图割产生的颜色块的关系，当相邻的色块较多时，视差判别会不准确，但根据算法的结果图与标准视差图对比发现，GC算法的结果表现出了最多的细节和清晰的轮廓，场景中的物品表现得最完整。ELAS算法与opencv优化过的SGBM算法相当，两种算法在时间和效果方面均有较好表现，在处理小尺寸的Tsukuba图时，时间都在0.1s左右，均能达到10 帧/s的实时处理最低要求，但ELAS算法速度要稍快一些。综合来看，ELAS算法在效果和时间上的表现最好，但误匹配率依然较高。

2 ELAS算法过程、原理及分析

ELAS算法用于已矫正过图像。算法包括4个步骤：1)选取合适支持点，并获取支持点的所有备选视差；2)以这些支持点为顶点进行Delaunay三角剖分，得到具有唯一性的三角形网格；3)假定投影的线性模型，认为每一个三角形代表一个视差平面，通过顶点的坐标值计算视差平面的方程；4)使用这些视差平面方程估计每一个像素点的视差值，将该视差值对应的相似度函数值与以3个支持点(三角形顶点，也是视差平面的顶点)包含的所有备选视差(可以认为这些视差为该视差平面所有可能选取的视差，即可称为视差平面的备选视差)对应的相似度函数值比较，函数值最小的视差即为该像素点视差。算法的关键是寻找支持点和备选视差以及计算相似度函数值。

2.1 寻找支持点获取备选视差

(1)

(2)

2.2 视差估计点处的优化函数模型

图 2 视差计算模型

在视差的估计点处，采用图2所示模型，输入参照点、支持点和参数γ、σ就可以计算出视差，然后由视差和参照点及参数β得到对应点。由此得到优化函数为

E(d)=β×E(k)-

(3)

其中：μ(S,o(l))为参照点的高斯分布均值，一般取0；为了更好地用于程序计算，将其转化为

E′(d)=E(k)+

(4)

而其中一般视差的相似度函数计算式为

(5)

也就是说对某一个像素点，其相似度值函数值有两种：1)视差平面估计出的视差值附近的视差，使用式(4)计算其相似度值函数值；2)其他的视差值，使用式(5)计算其相似度值函数值。最后再采用WTK(胜者为王)算法得到最终视差，即选取相似度函数最小的那个视差作为该像素点的最终视差。

2.3ELAS算法分析

令

图 3 平滑函数曲线

3 改进ELAS算法原理

视差的连续性原理有两种表述。其一，在同一幅图像中，相邻灰度值相同的地方视差连续，即场景中同一个物体或背景的视差是连续的，不会出现视差突变。视差突变表明出现了新的前景或背景。其二，在遮挡区域内，同一幅图像中相邻灰度值突变的像素点视差值不会连续。这其实是对第一种表述的反向理解，之所以设定在遮挡区域内，是因为在遮挡区域内部一般是前景遮挡背景，或背景遮挡前景的情况，这时，出现新的前景或背景(即遮挡区域内出现视差值大于0的区域)，必然有灰度突变。

根据上述表述一，考虑左摄像机图像中某个像素点，如果它的左侧相邻像素的灰度值与它的灰度值相等，即没有边缘，表明它们的视差连续。在上述选取视差的过程(二选一，即最终视差是选择对应视差平面的备选视差还是估计视差)中，选择与左侧视差值接近的那个视差，即可选择较准确的视差。不过要先设置一个阈值表明视差是连续的，当视差变化值小于阈值时，才使用上述的改进方法。设这个阈值为Threshold_d，该点处的备选视差设为dout，对应的相似度函数值为E_valout，该点处的估计视差设为dinner，对应的相似度函数值为E_valinner，与该点灰度值相等的左侧相邻像素点的视差值为dleft，该点最终视差设为d。

(6)

其中：

(7)

(8)

在计算出所有像素点的最终视差，获取初始视差图后，根据表述二，为了减少在遮挡区域逻辑错误的视差，以便后续的处理过程能去除掉这些错误区域，考虑在遮挡区域里可能存在逻辑错误的区域中找出灰度突变点。其中经过算法的处理遮挡区域的视差已被设置为负值，基本步骤如下。1)找出被遮挡区域包围的可能存在逻辑错误的区域，标记这些区域内的像素，前提是该过程标记的区域内其视差值是连续。2)从左到右扫描这些像素，从起始像素点处，即其相邻左侧的像素点的视差值为负值，判断其灰度是否突变，如果不是突变点就将其视差置为负值；如果是突变点，就标记突变mark=-1.3)向右移动，如果其相邻左侧像素点为标记突变点，或者如果其相邻左侧像素点不是标记突变点，且该点视差值不为负值这两种情况下，就判断当前像素点的灰度是否突变。如果不是突变点就保持当前视差，如果是突变点就将其视差置为负值并标记突变；如果其相邻左侧像素点不是标记突变点，且该点视差值为负值，就判断当前像素点的灰度是否突变，如果不是突变点就其视差置为负值并标记突变，如果是突变点就保持当前视差。4)重复3过程直到扫描完一行，移动到下一行重复2和3步骤，直到扫描完所有标记区域。

以上处理过程的关键是标记出可能出现逻辑错误的区域和寻找灰度突变点。为了标记出这些区域，可以找出所有连通域，其间在原有的连通域分割基础上加入视差的因素，当其内视差连续时才会被选为一个独立的连通域，由于连通域被灰度值为负值或灰度突变的点包围，这符合可能出现逻辑错误的区域的特征，同时为了剔除大范围的背景和前景，可以通过限定连通域的大小找出这些区域，设该限定阈值为Threshold_s。寻找灰度突变点比较简单，只要求当前灰度和其左侧相邻像素点的灰度差的绝对值是否大于限定阈值，设该阈值为Threshold_g。由于噪点的灰度值与周围像素点的灰度值相差很大，因此使用该方法寻找的灰度突变点容易受到噪点的影响，会导致一些错误。为了剔除噪点需要增加一步处理，但为了同时不影响真正的灰度突变点，在处理区域不能使用简单的中值滤波。Sobel的特征也能很好地描述这些真正的灰度突变点，而且原算法中也计算过(寻找支持点的过程中)，不用额外增加计算负担，因此采用如下处理方式：对处理的某一个像素点，计算其3×3窗口内灰度均值mean1，再剔除该像素点的灰度值求均值mean2，如果|mean2-mean1|×8>Threshold_g，再判断该像素点的sobel水平响应值或垂直响应值的绝对值的1/4是否大于阈值，设为Threshold_f.如果大于阈值，表明该点不是噪点；如果小于阈值，表明该点是噪点，需要使用mean2替代该点灰度值。

4 改进ELAS算法与原算法对比

使用Middlebury 2014 datasets作为测试数据集，将原算法和改进算法生成的视差图，上传至Middlebury网站上，得到测试结果。改进算法中Threshold_d=5，Threshold_s=500，Threshold_g=10，Threshold_f=10。

实验结果表明，这些测试图误匹配率均得以降低，其中，在Adirondack测试图上，改进算法降低的误匹配率达到38.7%，时间增加26 ms；在Playtable上也降低了38.4%，时间增加25 ms；在PlaytableP测试图上降低的误匹配率最低为15.63%，时间增加16 ms。可以看出，改进算法大大降低了误匹配率，而由于原算法中已标记了逻辑错误可能出现的区域，且计算出了sobel响应值，故不需要额外大量的计算来增加运行时间，只需判断和赋值即可，而且由于这些区域内的像素点较少，故增加的时间不多，平均在20 ms左右。表2所述实验中，原算法和改进算法的Mp/time均超过100万像素/s，因此，改进算法也具有实时性的应用价值。

表2 原算法和改进算法bad2.0下的all

5 视差图场景物体轮廓细化

改进算法减少了误匹配率，但前景的轮廓并不是很明显，使用表2中误匹配率较高的PianoL测试图来说明(图4)。

图 4 PianoL测试图

由图4可见，在算法中没有体现出来的台灯，在改进算法中能清晰看到。但是在某些对轮廓要求较

高的场合，需要与真实视差类似的视差图，改进算法提供的视差图并不能较好地识别物体的轮廓或其他特征。由于原图中的灰度分布特征能较好的描述轮廓特征，因此，考虑使用原图为引导图像的引导滤波，根据文献[10]对得到的视差图采用引导滤波，该滤波器采用线性化的思想，引导图和滤波图具有线性对应关系，其理论公式如下：

(9)

bk=Pk-ak×μk

(10)

(11)

式中：I为引导图像，P为滤波图像,wk和ω是窗口，μk是窗口内均值，σ是窗口内方差，ε为正则化项，q为滤波器输出。选取左相机图像为引导图像。w=9，ε=500。使用box-filter(盒滤波)技术使其复杂度为O(1)，加速处理过程，减少运行时间。

可见，通过滤波，新的视差图反应出场景中物体的很多细节，并和真实的场景很接近(图5)。

图 5 PianoL原算法滤波后效果

图6为以Teddy测试图对比的原算法与改进算法滤波前后的效果。实验证明，使用引导滤波能有效改善原视差图中的轮廓细节。但滤波处理Teddy(450×375)的时间为0.53s，处理PianoL(707×480)的时间为1.04s，平均35万像素/s左右。处理时间过长，达不到实时处理的要求。

图 6 原算法与改进算法滤波前后的对比效果

6 在实时场合的应用

在一般的实时应用中，若算法过慢，不能达到实时的要求，且算法时间与处理的图像尺寸有关，可以将获得的图像进行缩小或裁剪后进行处理以满足实时性要求。

表3 不同尺寸运行时间比较 s

实验表明，缩小图像尺寸能够减少算法时间，ELAS算法在不同尺寸图像上的运行时间的比值正比于尺寸比值。滤波时间也随着尺寸的缩小而减少，1/16图像大小的PianoL图像，即PianoL(176×120)，总的处理时间为0.096s，已能达到实时处理的要求，其最终视差图如图7所示。

图改进算法滤波后效果

7 结束语

基于视差连续原理的改进算法，对原算法的匹配效果有较大提升，且运行时间也增加不多，基本可以满足实时性的要求。在轮廓要求较高的实时性应用场合，也可以通过缩小图像尺寸并使用引导滤波来改善视差图。

另外，改进算法只使用相邻灰度信息，表2中某些测试图中的误匹配率依然较高，在后续的研究中应考虑更加有效的信息，以进一步减少误匹配率，深入探究如何更加合理和准确地选取视差，设计更加有效的相似度函数和平滑函数或后续处理。

[1] 魏朋玉.双目视觉立体匹配方法研究[D].重庆：重庆大学，2009.

[2] 赵星星.实时双目立体匹配算法研究与实现[D].沈阳：东北大学，2010.

[3]ScharsteinD,SzeliskiR.Ataxonomyandevaluationofdensetwo-framestereocorrespondencealgorithms[J].InternationalJournalofComputerVision, 2002, 47(1):7-42.

[4]HirschmullerH.Stereoprocessingbysemiglobalmatchingandmutualinformation[J].IEEETransactionsonPatternAnalysis&MachineIntelligence,2007,30(2):328-341.

[5]MartullS,PerisM,FukuiK.Realisticcgstereoimagedatasetwithgroundtruthdisparitymaps[J].TechnicalReportofIeicePrmu, 2011, 111:117-118.

[6]GeigerA,RoserM,UrtasunR.Efficientlarge-scalestereomatching[C]//asianconferenceoncomputervision[A].Springer-Verlag, 2010:25-38.

[7]BobickAF,IntilleSS.LargeOcclusionStereo[J].InternationalJournalofComputerVision, 1999, 33(3):181-200.

[8]HuX,MordohaiP.Evaluationofstereoconfidenceindoorsandoutdoors[C]//computervisionandpatternrecognition[A].IEEE, 2010:1466-1473.

[9]RaR.Findingthelargestunambiguouscomponentofstereomatching[C]//europeanconferenceoncomputervision[A].Springer-Verlag, 2002:900-914..

[10]HeK,SunJ,TangX.Guidedimagefiltering[C]//europeanconferenceoncomputervision[A].Springer-Verlag, 2010:1-14.

[责任编校： 张 众]

Research on Improvement of Stereo Matching Algorithm Based on ELAS

ZHANG Daode1，2, WU Yuan1，2, WU Liangyi1,2, HU Xinyu1,2

(1SchoolofMechanicalEngin.,HubeiUniv.ofTech.,Wuhan,430068; 2Engin.RearchCenterofWuhanLightIndustyEquipment,Wuhan430068,China)

Binocular stereo matching algorithm is real-time and accurate in the binocular vision servo control system,which is very important for the accurate positioning and control of the robot. Based on the study of some advanced stereo matching algorithms,this paper introduces an algorithm of local stereo matching based on parallax plane-ELAS (Efficient LArge-scale Stereo) algorithm,introduces the principle of ELAS algorithm,Which overcomes the shortcomings of these existing algorithms in which the best disparity map cannot be obtained until the maximum disparity value range is given. The best performance is obtained by considering the combination of the processing time and processing effect.Aiming at the problem that the ELAS algorithm does not work well, the improved ELAS algorithm is studied based on the principle of disparity continuity. The disparity map is processed using the guided filter. Experiments show that the improved ELAS algorithm improves the performance of the original algorithm significantly. Without considering the real-time performance, combined with the above-mentioned filters, the processing effect can be close to the real disparity map, which is of great significance in 3D reconstruction and visual servoing.

Stereo matching; ELAS; filtering; real time

2017-01-13

湖北省自然科学基金项目(2014CFA528)

张道德(1973-)， 男， 湖北黄冈人，工学博士，湖北工业大学教授，研究方向为智能控制系统和机器视觉图像处理

伍 渊(1990-)，男，湖北洪湖人，湖北工业大学硕士研究生，研究方向为机器视觉图像处理

1003-4684(2017)02-0001-06

TP242.62

A