一种改进的基于BP的立体匹配算法

武翠芳，王永芳，刘 静，2，张兆杨，2，宋允东，2

(1.上海大学通信与信息工程学院，上海 200072;2.新型显示技术及应用集成教育部重点实验室，上海 200072)

0 引言

近年来，随着多媒体、Internet等技术的发展，普通二维观感的图像、视频越来越无法满足人们的观赏需求。接近真实场景的三维成像及环视的视觉体验已越来越被大众所期待。随之，立体视觉系统作为一种新兴的媒体系统，能够在很大程度上满足人们的视觉体验，而受到越来越多的研究者和商业机构的关注。视差信息是立体视觉系统的基础，而立体匹配技术是获取视差信息的主要手段。故而，双目立体匹配问题作为立体视觉的关键成为计算机视觉领域研究的热点。20世纪70年代末，MIT的Marr教授首次从信息处理的角度综合了图像处理、心理物理学、神经生物学及临床神经病学的研究成果，提出了第一个较为完善的视觉系统框架［1］。大大促进了立体视觉技术的发展，立体匹配问题一直扮演着至关重要的角色。

目前存在的立体匹配算法，由于立体匹配方法的不确定性，并没有一种统一的方式来解决立体匹配的问题。根据不同匹配基元及算法依据等有着不同的分类标准。目前广泛认可的一种分类即局部匹配算法和全局匹配算法两大类［2］。全局算法依赖图像的全局约束信息进行匹配，目前比较流行的全局算法如动态规划(DP)、graphcuts、BP(Belief Propagation)等。局部匹配算法利用对应点本身以及邻近区域约束信息来进行匹配。局部算法按照匹配基元不同，可分为3类:特征匹配、区域匹配和相位匹配。特征匹配算法［3－4］根据点、线、面、角点等作为匹配基元进行匹配，此算法在匹配运算速度上最为理想，而由于其匹配基元的稀疏性而无法得到稠密视差图，进而严重影响最终效果。但对于其稀疏视差的插值运算亦相当复杂，反而得不偿失;基于区域的局部立体匹配算法［5－7］，在算法并不复杂的前提下，能够获取稠密视差图而受到越来越多研究者的青睐。其不足之处在于对于遮挡及纹理单一区域易造成误匹配，这也是近年来针对区域匹配算法的重点改进之处;相位匹配算法［8－10］对带通滤波信号的相位信息进行处理而得到视差图。此算法对于图像的高频噪声有很好的抑制作用，同时对几何畸变和辐射畸变有很好的抑制作用，能获得亚像素级的稠密视差图。

全局匹配算法较比局部匹配算法在算法精确度和噪声敏感度上有很大优势，从最初的遗传算法、贪婪算法到动态规划算法，以及目前广泛采用的BP算法、graph－cuts算法等，全局算法得到了很大的发展。但全局算法复杂度非常高，消耗的运算成本太大，在很多应用环境中并不适用。局部匹配算法在精确度上没有全局算法更优秀，但运算速度上更胜一筹。本文算法结合全局匹配算法和局部匹配算法的优缺点，在图像分割基础上，对文献［11］的BP算法进行改进，利用BP对初始视差进行处理和优化，进而得到优于全局匹配算法精度的视差图。

1 改进BP算法

本算法框架如下图1。首先对输入的参考图像进行Mean－shift彩色分割，以左图像为参考图像进行匹配代价计算并获取初始视差;接着对初始视差进行交叉检测，并结合分割信息，将分割区域分为可靠和非可靠区域;然后利用本文的改进BP算法进行优化，为非可靠区域寻找最优视差值;最后得到最终视差图。

图1 算法流程图

1.1 获取初始视差

Comaniciu D［13］等人将 mean －shift方法首次应用于图像分割，并验证了其在特征空间的稳健性。mean－shift分割算法是一种利用概率分布地图寻找分布峰值的稳健型较高的非参数估计算法［13］，是一种比较有效的统计迭代算法，使得每个点能够“漂移”到密度函数的局部极大点。该算法在处理物体边界方面更为理想，且具有精度高和实时性好等优点［14］。

基于区域的匹配算法往往假设不同的颜色边缘与视差的跳跃是一致的(即假设区域内视差相等)，为使这一假设成立，实际操作中通常要采用“过分割”算法来得到尽量多的分割区域。在进行立体匹配时，首先用meanshift算法对图像进行过分割，得到分割图像后，计算初始匹配代价进而获取图像的初始视差。在进行匹配代价计算时，采用绝对误差和(Sum of Absolute Difference，SAD)并加入梯度约束，即:SAD+GRAD，如式(1)所示。

ω为梯度权重;N(x，y)为中心点(x，y)处支持窗口;Nx(x，y)为x方向窗口大小;Ny(x，y)为y方向窗口大小;I1(i+d，j)为参考图像当前点像素，I2(i+d，j)为目标图像当前点像素，(i，j)为当前点坐标，d为视差值。本算法中采用的是拉普拉斯梯度算子来计算梯度。

得到匹配代价后，利用胜者全取(Winner－Take－All，WTA)选择初始视差值。接着，对初始视差采用交叉检测算法进行可靠性检测，并对可靠点和非可靠点分别进行标记，为视差估计后续处理做准备。

1.2 基于区域的BP算法优化

BP算法采用消息传递机制实现能量的极小化，根据能量函数中每个因子的取值设定相应的消息(message)和置信度(belief)［15］。为每个分割区域选取最优视差值。这里对于初始视差值基于区域进行优化和重分配。同文献［11］一样，采用循环置信传播(Loopy Belief Propagation)优化算法。不同之处在于，文献［11］中算法是基于像素优化，而本文算法是基于mean－shift分割后的区域基础上的优化。

算法中的能量函数定义如式(2)

式中:Edata为数据项(匹配代价函数)，Esmooth为平滑项(平滑约束)。s为分割区域，fs表示为区域s分配最后标签(即视差)。考虑到BP算法是基于分割区域的。故式(2)中数据项Edata及平滑项Esmooth公式分别为

式中:SN表示所有相邻区域的集合;λdisc(si，sj)是相邻区域平滑惩罚项函数，是一个设定的经验值;CSEG表示分割区域内匹配代价累积和;C(x，y，d)表示像素点(x，y)视差为d时的匹配代价，表达式见式(1)。可见，与原算法不同，新算法将原算法中针对相邻像素间的置信度传播改进为相邻区域间的置信度传播。

对于信息(message)函数计算及迭代，公式为

式中:si，sj表示不同的分割区域;fsj表示区域sj视差值;S(si)/sj表示除去sj外，与si相邻的区域的集合。经T次迭代，得到每个区域的置信度如式(6)。最后，选取使得置信度函数最小的视差值f(s)，作为该区域s的最终视差值。

另本算法进一步改进:根据区域分割及交叉检测后视差图，将初始视差结果分为可靠区域与非可靠区域。原算法基于周围相邻区域间信息传递，而本文的算法中信息只在可靠区域与不可靠区域相互之间进行传递，略去可靠区域之间的信息计算和传递。

2 实验结果

本文选取Middlebury网站的标准测试序列，实验平台为VS2008。本算法与文献［11］算法进行对比。实验结果的评估标准:客观评价为误匹配像素百分比(Percentage of Bad Matching，PBM)(式(7))。

通常在遮挡区域(Occluded Region)和边缘区域(Discontinuity Region)视差匹配较易发生误匹配。在进行区域误差统计时，对于非遮挡区域，由于其在参考图像中不存在对应的匹配点，匹配中很难得到正确的视差，所以在视差匹配时利用非遮挡区域视差BO－(式8)来统计误匹配率;对于边缘区域则是视差的不连续区域，用Bd(式9)统计其误匹配率。

式中:dC(x，y)为算法得到视差估计值，dT(x，y)为真实视差值。PMB反映了算法估值所得视差值的误差大于设定阈值的像素占整幅图的所有像素的比例，PMB越大，表示误匹配点越多;反之，则匹配精确度越高。O－表示非遮挡区域，d表示边缘区域。这里选取δd=1.0。主观评价采用对比标准视差图法。

表1为文献［11］算法与改进算法客观评估结果对比。笔者给出了总体误匹配率以及各个区域误匹配率的详细统计数据。从表中可以看到本算法在非遮挡区域对teddy及cones两幅测试序列表现更好，对于tsukuba及venus两个序列误匹配率则略有提高，主要原因在于这两幅图像纹理特征:少纹理区域较多。如前所述，全局算法对于少纹理区域的处理要优于局部匹配算法。但本算法在对于边缘区域的处理上4幅测试序列均有提高，使得误匹配率最高可达到近13%的降低，其结果明显优于文献［11］算法。可见本算法对于边缘处理，以及纹理多样化的图像序列处理效果尤为突出。

表1 本文算法与文献［11］算法误匹配率比较

本文算法与文献［11］算法同在立体匹配测试网站Middlebury测试，本文算法对于4幅测试序列的平均误差率为10.7%，文献［11］算法则为16.2%。证明了本文算法的有效性。

表2为文献［11］算法与本文算法耗时结果对比。从表中可以看到，本文算法和文献［11］算法的计算消耗相当，有的序列计算消耗略有提高，但在匹配效果提高的基础上，还是可接受的。

表2 本文算法与文献［11］算法耗时比较

图2给出了文献［11］的算法和使用本文改进算法进行立体匹配得到的视差图对比。由匹配结果可以看到，本文算法在4幅测试序列中的整体匹配结果优于文献［11］算法，尤其是对于边缘区域的匹配有着明显优势。

3 小结

本文提出一种改进的基于区域的BP立体匹配算法，与文献［11］分层BP算法比较，本文改进BP算法在不分层的情况下，以几乎相对等的算法复杂度，使得立体匹配中获取的初始视差图更为精确，特别是在边缘区域。该算法进一步证明了局部算法可以有优于全局算法的匹配精度。从实验结果来看，本文改进算法在少纹理区域的处理上没有文献［11］的算法精确。接下来的工作是针对不同区域(少纹理、遮挡、边缘等区域)重点研究如何改善区域的误匹配问题，以期能够最终获得更为准确的视差图。

图2 本文算法与文献［11］算法视差图比较

［1］马尔著，姚国正，刘磊，等.计算机视觉［M］.北京:科学出版社，1998.

［2］于乃功，秦永钢，阮晓刚.立体匹配算法进展［J］.计算机测量与控制，2009(5):817－819.

［3］徐奕，周军，周源华.立体视觉匹配技术［J］.计算机工程与应用，2003，39(5):1－5.

［4］陈文鑫，陈伟东，朱仲杰，等.基于可变特征基元的视差估计新方法［J］.计算机工程与应用，2008，44(15):58－60.

［5］YOON K，KWEON I S.Adaptive support－ weight approach for correspondence search［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2006，28(4):650－656.

［6］KLAUS A，SORMANN M，KARNER K.Segment－based stereo matching using belief propagation and a self－adapting dissimilarity measure［C］//Proc.ICPR 2006:Vol.3.［S.l.］:IEEE Press，2006:15－18.

［7］郑志刚，汪增福.基于区域间协同优化的立体匹配算法［J］.自动化学报，2009，35(5):469－476.

［8］SANGER T D.Stereo disparity computation using Gabor filters［J］.Biological Cybemetics，1988，59:405－418.

［9］WENG J.Image matching using the windowed Fourier phase［J］.International Journal of Computer Vision，1993，11(3):211－236.

［10］荆元强.基于相位信息的立体图像匹配研究［D］.天津:天津工业大学，2008.

［11］FELZENSZWALB P F，HUTTENLOCHER D P.Efficient belief propagation for early vision［C］//Proc.CVPR 2004.［S.l.］:IEEE Press，2004:261－268.

［12］KOSCHAN A.What is new in computational stereo since 1989:a survey of current stereo papers［R］.Berlin:Univ.of Berlin，1993.

［13］COMANICIU D，MEER P.Mean shift:A robust approach toward feature space analysis［J］.IEEE Trans.Pattern Anal.Machine Intell.，2002，24(5):603 －619.

［14］袁惇.基于视差估计的立体视频对象分割［D］.北京:中国传媒大学，2007:17－26.

［15］王翀，赵力，齐增义，等.基于改进 BP算法的中间视合成方法［J］.信号处理，2010，26:347－353.