李鹏格　戴本祁

(华东理工大学信息科学与工程学院　上海 200237)



基于改进的种子点扩展自适应立体匹配算法

李鹏格戴本祁

(华东理工大学信息科学与工程学院上海 200237)

由于在图像中不同区域的纹理密集程度不同，因此使用固定窗口大小的算法无法兼顾纹理不同的区域，并且在视差不连续区域的匹配精度较低。针对该问题，提出一种自适应窗口和自适应权重相结合的算法，并且采用种子点扩展的方法。首先，通过交叉自适应窗口法，区分出连续点和孤立点，对于不同的分类点采用不同的处理方法。其次，针对每一个像素点，利用改进的自适应权重方法进行匹配。最后，提出一种新的种子点扩展的视差优化方法，对初始视差图进行精细化。实验结果表明，视差图中纹理密集区域和视差不连续区域的误匹配现象得到改善。该算法可以有效地处理图像中纹理分布不均的问题，提高了在视差不连续区域内匹配精度。

交叉自适应窗口自适应权重孤立点种子点

0　引　言

立体匹配是通过二维图像进行三维重构的一个重要环节。立体匹配的目的就是为要从一对左右图像得到一幅精准的视差图，但是由于左右视图中的遮挡问题、光照问题、基线偏移问题等使得在图像处理的过程中加大了提取视差的难度。根据立体匹配算法的处理范围不同可以分为全局算法和局部算法，全局算法在长期以来都有着在精度方面的优势。然而在运算速度方面却是不尽人意，因此不适于对时间要求比较苛刻的大多数工业环境中的实时处理系统。在局部算法方面，在研究学者们的不断努力下，该算法在精度上逐渐提高，并且目前一些局部算法的精度已经可以达到全局算法的水平。

局部立体匹配算法包括区域匹配和特征匹配算法[1]。区域匹配算法就是以各个像素点为中心构建或设定相应的一个支撑窗口，利用像素间的颜色约束和距离约束等约束条件，在一定的视差范围内进行匹配。主要有固定窗口法、滑动窗口法、多窗口法、自适应窗口法、自适应权重AW(Adaptive-Weight)法[2-4]、基于Rank变换的匹配算法[5,6]等。

目前，使用较多并且效果较好的是自适应权重法[2]及其改进算法，它是由Yoon等提出的。对每一个像素点分配一个固定窗口，计算窗口内的各个像素与中心像素间的颜色距离和空间距离，将二者的距离权重相结合，得到整个窗口内各个像素与中心像素的权重，然后结合像素初始距离计算匹配代价，利用WTA(Winner-Takes-All)方法得到密集视差图。然而，由于其利用固定窗的方法使得该方法存在一些固有的缺陷，如在稀疏纹理区域和视差不连续区域的匹配精度低。

为此，后来的研究者基于该方法提出了一些改进算法，如Tombari等[7]提出在分割区域的权重为1，其他区域的权重为AW算法中联合权重，这种方法使得在稀疏纹理区域的匹配精度得到有效的提高。Hosni等[8]利用通透性的原理，提出测地距离立体匹配的方法，将除去那些与中心像素不连续却拥有较高权值的像素的影响，在纹理稀疏区域更好地提高了匹配精度。但是由于Hosni等采用通透性原理，在高纹理的区域内像素的连续区域通常较小，导致其匹配区域减小而出现误匹配的现象。

为提高在纹理程度不同的区域的兼顾性，本文提出一种基于改进的交叉自适应增长的图像分割方法，并在各个分割区域内，利用各个像素与中心像素之间的空间距离和色度距离来确定其不同的相关权值。该算法有效地提高了整体图像的匹配精度，并且针对视差图中易出现误匹配的孤立像素点，提出一种改进的种子点扩展算法，即根据邻近视差有效种子点[9]扩展的方法，使视差精度进一步得到提高。

1　自适应匹配算法

在局部立体匹配算法中，为了得到精确的匹配结果，选择一个合适的窗口是很重要的。原则上来说，这个窗口应该包括所有具有相同视差的相邻的像素点，但是每个像素的视差值是不可预知的。由于在邻近区域内具有相似的色度的像素点一般都是在同一视差区域内，因此假设在一定阈值内的邻近像素点有相同的视差，即视差相似性假设。

本文算法流程如图1所示。图1中自适应匹配阶段，首先利用改进的自适应交叉分割算法，得到各个左右图中各个像素点的分割区域，并记录像素点为孤立点或者连续点；其次计算各个分割区域内的像素点对中心点的权重；最后得到联合匹配代价。

图1　本文匹配算法框图

1.1交叉自适应分割

(1)

式中pi=(xp-i,yp)，L是设定的臂长搜索范围。δ(p,pi)是像素p1和p2之间颜色相似度的测量函数如下[10]：

(2)

式中Ic是颜色通道c上的强度值，τ是设定的限定相似度程度的阈值，文献[10]中取20。由此可以得到点p的上下左右的臂长，即可得到点p的分割区域。

该分割算法中利用p点的垂直扩展臂，进行水平方向的扩展，可以得到p点的分割区域，但是这样只考虑了图像的水平方向的通透性，忽略了垂直方向的通透性，降低了匹配的精度。由于该算法利用图像的通透性，在低纹理区域可以得到较高的匹配精度，但是在高纹理区域，由于每个像素点的分割区域都较小，致使出现较高的误匹配现象，为此本文提出了解决该问题的方法。

对文献[8]中提出的交叉自适应分割方法进行补充和改进，不仅考虑到图像水平方向上的通透性，也利用图像垂直方向上的通透性。利用式(1)搜索到像素点p的上下左右臂长，再分别以p点上下臂和左右臂上的像素点作为基准点，分别进行左右和上下的扩展，两者结合一起可得到像素点p的支撑窗口W。如图2所示：其中(a)是以p点的垂直方向臂长上的像素点作为基准点，进行水平方向的扩展；(b)是以p点的水平方向臂长上的像素点作为基准点，进行垂直方向的扩展；(c)是联合(a)、(b)分割区域后的p点的支撑区域。这样扩展可以充分利用像素之间的相似性，得到更大的分割窗口，并且能包含所有与中心像素相似的像素点，实验证明也更加合理有效。

图2　支撑区域扩展图

1.2自适应权重算法

在一幅图像中，除了边缘点之外，每一个像素点与其周围的像素点都有一定的相似性，并且随着像素距离的边远，其相似度通常情况下也在逐渐变小。根据颜色约束和距离约束条件，Yoon和Kweon提出了自适应权重的算法。

在该算法中其像素距离fg(p,q)的计算是通过下面公式[2]得到的：

(3)

其中，Δgpq为任意像素点p、q点之间的欧氏距离，μg为联合权重中像素距离的权重。

由于其使用指数函数，其不足点在于，对于在低纹理区域的像素点，中心像素点与周围的邻近像素点具有较高的相似性。但是该函数下降速度快，只有在3×3邻域内的像素才具有较大的权重值，虽然有颜色权值作为补充，该算法在低纹理或无纹理区域匹配精度依然较低。

式(3)无法充分满足颜色相似的像素点要分配相同的权重的要求。本文利用下面公式[11]进行改进，可以满足在一定的范围内具有较高颜色相似性的像素点分配相同的权重的要求。

fg(p,q)=((1+exp(-a(Δipq+b)))-1-

(1+exp(-a(Δipq-b)))-1)×

((1+exp(-a(Δjpq+b)))-1-

(1+exp(-a(Δjpq-b)))-1)

(4)

式中，参数a可以设置像素距离的权值函数的下降速度，a越大下降速度越快；参数b可以改变函数的中心区域权值变化缓慢的区域块，b越大中心区域越大；Δipq、Δjpq分别表示像素点(p,q)的水平和垂直坐标距离。

1.3代价聚合

在代价聚合阶段，结合自适应分割算法和自适应权重算法计算匹配代价。在自适应分割时得到的分割区域内，利用自适应权重算法，可以排除那些与中心像素点不在同一纹理区域内的像素点，并且扩大在低纹理区域像素点的分割区域。因此，可以提高低纹理区域的匹配精度，其聚合匹配代价如下式：

(5)

其中fs(p,q)、fs(pd,qd)分别是左图和右图中p和pd点的支撑窗口；Spq为d在Rd范围内搜索时左右支撑窗口的联合窗口；Ns为联合窗口的大小，即窗口内的像素数目；w(p,q)、w(pd,qd)分别为p和pd对应的支撑窗口内的权重；e(q,qd)为p和pd的支撑窗口内对应像素点的初始匹配代价值。

在Rd={dmin,…,dmax}范围内，进行视差搜索，利用WTA算法[2]得到最优视差：

(6)

2　视差优化

2.1种子点选取

如本文算法图1所示，在得到初始视差图后，对视差图进行优化。首先，在初始视差图中选出准确度高的种子点[9]；然后，将孤立点，也就是由于支撑窗口小而可能引起误匹配的像素点，标记出来，在其支撑窗口内搜索到与其邻近的种子点，将种子点的视差值赋给该孤立点。

种子点的选取条件如下：

(1)DL(i,j)=DR(i,j-(DL(i,j)))

(2)C((i,j),DL(i,j))×γ

式中，DL(i,j)表示左视差图中(i,j)点的视差值，DR(i,j-(DL(i,j)))表示对应于(i,j)点的视差值在右图中的视差值，C((i,j)、DL(i,j))表示左视差图中(i,j)点视差值为DL(i,j)时的代价值。条件(1)要求种子点的视差值满足左右一致性(Left-Rightcheck,LRC)，条件(2)确保该点的可信度，设定的阈值γ可以改变种子点的可信度，本文中选取γ=1.1，γ越大，种子点的可信度越高，但是种子点数也会相应的减少。

2.2孤立点标记及优化

在自适应分割时，若得到像素点p(i,j)的支撑窗口内的像素点总数小于θ，或者其半边界小于θ/2，则标记P点为孤立点。根据产生孤立点的条件不同，可分为左边界孤立点、右边界孤立点和全孤立点。此时，对于每一个孤立点进行视差优化。

对于全孤立点，在其支撑区域内，所包含的所有种子点的视差值的均值即为P点的视差值；对于左边界孤立点，即该孤立点的左边靠近边界，根据视差相似性假设，即假设该点的视差与在其右边的像素点的视差相似，则在其支撑区域内，选取其右半部分的种子点的视差值的均值作为其视差值；同理，对右边界孤立点，选取其左半部分的种子点的视差值的均值作为其视差值。表示为：

(7)

其中，Np为p点的支撑区域，qA表示在p支撑区域内的种子点，d(p)表示p像素点的视差值，Sp表示p点的分割区域，Sp-left、Sp-right分别表示p点的分割区域内的左右半部分。

由于这些孤立点虽然其分割区域较小，但是其初始视差值不一定就不准确，因此，在视差优化阶段，从得到的孤立点图中除去那些本身是种子点的孤立点，只对非种子点的孤立点进行视差优化。然而由于部分遮挡点被误认为是种子点的情况会出现较大的误匹配率，因此，根据左右一致性检测，通过左右视差图得到遮挡点图，对其中遮挡点而非孤立点的像素点进行视差优化，直接取其11×11窗口内的种子点均值。

3　实验结果

实验测试中使用Middlebury数据库[12]中的标准图像进行测试，实验中各个参数的设置如表1所示。

表1　参数对照表

其中，θ阈值的选取是根据L值得大小，即窗口的大小。当L=19时，窗口的大小为39×39，其中包含的像素点数为1521个，当某个像素点的分割区域内像素点个数少于整个窗口的大约三分之一时，标记为孤立点。当阈值过小时，孤立点过少，无法有效地优化误匹配点的视差；反之，孤立点过多，使一些非误匹配点的视差被更改，反而降低了匹配率。

3.1种子点扩展实验结果

在图3中，下图的两列分别为Tsukuba图和Cones图，第一行为得到的种子点图，高亮度部分为种子点，黑色点为非种子点；第二行为待优化的孤立点图，通过2.2节部分的方法得到孤立点图，将其中视差值满足种子点要求的点去除，再将根据左右视差图得到的遮挡图部分考虑进去，可得到该孤立点图，高亮度区域表示孤立点；第三行为初始左视差图，第四行为种子点扩展后的左视差图。

从图3(a)、(b)中可以看出种子点一般出现在纹理稀疏并且视差连续的区域，而孤立点主要出现在纹理密集区域，包括视差不连续区域。

对比图3(a)、(b)，本文的孤立点选取方法可以提取出图像中的误匹配点；对比图3(c)、(d)，本文提出的种子点扩展方法可以有效地消除孤立点的误匹配现象。从图中用椭圆形标记出来的区域可以看出，在Tsukuba图中的台灯左侧的前景肿大现象得到优化，并且在头像的左上方的白色区域被消除；在Cones图像中效果明显，各个模型的左边黑块大幅减少。

图3　种子点扩展过程

3.2实验结果对比分析

根据表1参数对文献2以及本文的算法进行测试，结果如图4所示。其中各列的图依次为Tsukuba、Teddy、Cones和Venus。由图中结果可以看出，除去遮挡区域的少量误匹配现象，改进的算法在其他区域整体均有所提高。

在图4(b)中使用自适应权重的算法，在图4(c)图中利用自适应分割的方法。由于其在使用自适应分割时，最大臂长的设置与图4(b)中的固定窗口的相等，因此在视差不连续区域使得匹配窗口小于图4(b)中相应的匹配窗口，匹配结果提高不明显。但是在该过程中可以得到种子点和孤立点，再考虑到视差优化阶段的种子点扩展，可得到图4(d)，即本文算法，可以看出通过优化使得匹配效果得到较大提高。

对比图4(b)、(c)，在(b)的结果中Tsukuba图中的背景区域中出现被椭圆形标记的白块，以及在Teddy图中的用椭圆形标记的区域，也都在加上自适应分割窗口之后，得到有效的改善。对比图4(b)、(d)，在文献[2]的结果中，Venus图中有出现用椭圆形标记的白色区域，在Cones图中出现用椭圆形标记的黑色区域，都在改进算法中被消除。

图4　立体匹配原图及视差结果图

在Tsukuba图和Venus图中的标记区域出现在低纹理区域，在只考虑权重的情况下，由于附近视差的相似性，导致出现误差。但在考虑自适应分割和种子点扩展之后可以弥补这种误差。在Teddy图和Cones图中的标记区域出现在纹理不连续区域，在该区域利用孤立点的特性进行扩展，可以消除大量误匹配的像素点。

在实验结果图4中可以看出文献[2]的Venus中的背景边缘线模糊不清。但在本文的算法结果中边界明显，这是由于在边缘附近的像素点易出现误匹配现象，并且误匹配的视差值都是由于背景引起的，而本文提出的种子点扩展法，可以有效提高边缘附近像素点的匹配精度。然而在Teddy图的处理上出现了误匹配块现象，无法消除，主要是由于该区域纹理太过相近，而在进行图像分割时，是有最大窗口限制的分割，致使该区域出现误匹配。

图4的(c)、(d)实验得出的非遮挡区域错误率(nonocc)、总体错误率(all)和视差不连续区域错误率数据(disc)如表2所示。在文献[10]中只是利用自适应分割的水平方向扩展进行立体匹配，因此当图像中含有大量垂直边界的时候，无法保证匹配的准确性，而在本文算法中同时考虑到垂直方向上的扩展，可以使匹配率得到提高。不仅如此，本文还结合种子点扩展的方法，将像素点分类为孤立点和连续点，利用种子点对孤立点进行水平方向扩展，进行视差优化，使匹配率进一步得到提高。

表2　算法结果的误匹配率比较(error>1)

根据表2对误匹配率的分析，文献[10]的总平均误匹配率为7.60%，本文算法的总平均误匹配率为6.72%，减小了0.88%。实验结果也显示在Tsukuba、Venus和Teddy图中的误匹配率都有所改善，分别减少了0.35%、0.07%、0.65%，并且由于在Cones图中的孤立点大部分为左右边界点，因此Cones图的误匹配率提高最为明显，分别为1.68%、4.15%、1.48%。因此，本文算法可以降低立体匹配过程中的误匹配率，尤其在水平不连续区域内，可以大幅提高匹配率。

4　结　语

本文在交叉分割和自适应权重的立体匹配算法的基础上，提出一种改进的分割算法和自适应权重算法。通过实验表明，该方法有效地解决了自适应权重算法中在视差不连续区域匹配精度低的问题。虽然在计算效率上比较文献[2]有所降低，但是通过并行计算的方法依然可以大大提高计算速度。本文在视差优化阶段提出种子点扩展的算法，实验结果显示，在纹理密集区域匹配精度得到了显著的提高，弥补了文献[2]在该区域内匹配精度低的问题。

但是本文也存在一些有待提高的地方，如在Teddy图的实验数据中，all和disc区域的误匹配率优化较小，究其原因，是本文算法在进行孤立点的选取时只标记其左右的边界特性。而Teddy图里面又含有较大部分的上下边界点，如图中的烟囱部分，因此可以通过考虑其上下边界特性，使其匹配精度进一步提高。

[1]YangL,WangR,GeP,etal.Researchonarea-matchingalgorithmbasedonfeature-matchingconstraints[C]//2009FifthInternationalConferenceonNaturalComputation,Tianjin,August14-16,2009,Piscataway:IEEEPress,2009:208-213.

[2]YoonKJ,KweonIS.Adaptivesupport-weightapproachforcorrespondencesearch[J].IEEETransactionsOnPatternAnalysisandMachineIntelligence,2006,28(4):650-656.

[3]ChengF,ZhangH,YuanD,etal.Stereomatchingbyusingtheglobaledgeconstraint[J].Neurocomputing,2014,131(7):217-226.

[4]HuW,ZhangK,SunL,etal.Virtualsupportwindowforadaptive-weightstereomatching[C]//VisualCommunicationsandImageProcessing,2011IEEE,2011:1-4.

[5]IrijantiE,NayanMY,YusoffMZ.Localstereomatchingalgorithm:Usingsmall-colorcensusandsparseadaptivesupportweight[C]//NationalPostgraduateConference,KualaLumpur,September19-20,2011.Piscataway:IEEEPress,2011:1-5.

[6] 郭龙源,卢阿丽,杨静宇.非参量变换在彩色图像立体匹配中的应用研究[J].计算机科学,2008,35(11):217-219.

[7]TombariF,Mattoccia1S,StefanoLD.Segmentation-basedadaptivesupportforaccuratestereocorrespondence[C]//ProceedingsofAdvancesinImageandVideoTechnology,SecondPacificRimSymposium,Santiago,December17-19,2007.Berlin:Springer,2007:427-438.

[8]HosniA,BleyerM,GelautzM,etal.Localstereomatchingusinggeodesicsupportweights[C]//ImageProcessing,2009 16thIEEEInternationalConference,Cairo,November7-10,2009.Piscataway:IEEEPress,2009:2069-2072.

[9]SunX,MeiX,JiaoS,etal.Stereomatchingwithreliabledisparitypropagation[C]//3DImaging,Modeling,Processing,VisualizationandTransmission,2011InternationalConference,Hangzhou,May16-19,2011.Piscataway:IEEEPress,2011:132-139.

[10]ZhangK,LuJ,LafruitG.Cross-basedlocalstereomatchingusingorthogonalintegralimages[J].IEEETransactionsOnCircuitsandSystemsForVideoTechnology,2009,19(7):1073-1079.

[11] 王富治,黄大贵.改进的YOON自适应加权立体匹配算法[J].电子测量与仪器学报,2010,24(7):632-637.

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

ADAPTIVESTEREOMATCHINGALGORITHMBASEDONIMPROVEDSEEDPOINTSEXPANSION

LiPenggeDaiBenqi

(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

Sincetheimageindifferentregionshasdifferenttextureintensity,thereforethealgorithmusingasize-fixedwindowcan’ttakeintoaccounttheregionswithdifferenttextures,anditsmatchingprecisionislowindisparitydiscontinuitiesregions.Tosolvetheseproblems,inthispaperweproposeanewalgorithmwhichcombinesadaptivewindowandadaptiveweight,andusesthemeansofseedpointexpansion.First,wedistinguishtheconsecutivepointsandisolatedpointswithcross-adaptivewindowmethod,andusedifferentprocessingapproachesfordifferentclassificationpoints.Secondly,foreachpixelpointweusetheimprovedadaptiveweightmethodtomatchit.Finally,wepresentanewdisparityoptimisationapproachofseedpointsexpansiontorefinetherawdisparitymap.Experimentalresultsshowthatthephenomenonofmismatchingthetextureintensityregionanddisparitydiscontinuitiesregionindisparitymaphasbeenimproved.Thealgorithmcaneffectivelyprocesstheproblemofuneventexturedistributioninimage,andraisethematchingprecisionindisparitydiscontinuitiesregion.

Cross-adaptivewindowAdaptiveweightIsolatedpointSeedpoint

2014-09-06。李鹏格，硕士生，主研领域：立体匹配。戴本祁，副教授。

TP391

ADOI:10.3969/j.issn.1000-386x.2016.03.050