图1 视差空间图像
Fig.1 Disparity space image
耿冬冬,罗娜
(华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海200237)
摘要：双目立体视觉匹配通过两幅具有一定视差的图像获得精确、稠密的视差图。为了解决动态规划立体匹配算法橫条纹瑕疵以及精度低的问题,提出了一种基于多邻域非线性扩散的立体匹配算法。该算法采用AD测度函数构建视差空间,根据行列像素之间的约束关系,基于非线性扩散的代价聚合方法,通过图像边缘的动态优化寻求全局能量函数最优值得到稠密视差图。在Middlebury测试集上的实验结果表明,该算法的平均误匹配率为5.60%,相比IIDP动态规划全局匹配算法,精度提高了39.9%,有效地解决了横向条纹问题,改善了边缘模糊情况,且提升了算法的稳定性。与其他全局匹配算法相比,本文算法误匹配率降低了38.2%,在图像参数的11个指标中有9项指标排名第1。
关键词：动态规划; 立体匹配; 非线性扩散; 视差; 代价叠加
作为计算机视觉领域的一个重要研究方向,立体视觉可以重构场景的三维几何信息,已被广泛应用于移动机器人的自主导航系统、航空及遥感测量、工业自动化工件检测等领域。为从平面图像中恢复深度信息,立体匹配技术通过三角测量原理,建立合适的匹配约束和匹配准则以寻找同一场景在不同观察点下投影图像中像素间的一一对应关系,并由此得到相应的视差图像,算法的性能直接影响到图像深度的分析以及后期三维重建场景的准确性和效果。因此,立体匹配算法一直是计算机视觉领域的一个中心研究问题,对立体匹配算法的研究具有重要的意义。
针对实际问题中匹配的不确定性,研究者们提出了不同的立体匹配算法[1-2]。根据匹配约束条件和搜索策略的不同,算法可以分为局部支持邻域准则的局部立体匹配算法[3-4]以及采用全局策略的全局立体匹配算法[5-6]。局部匹配方法的优点是计算复杂度低、运算速度快,因此被较多实时立体视觉系统所采用。但由于是基于局部寻优,对弱纹理、遮挡等局部歧义区域较敏感,相对全局算法来说,易造成误匹配,因此视差图的误匹配率比较高。全局匹配算法通过引入平滑函数项,将对应的匹配问题转化为寻找能量函数的全局最优解问题,再通过各种全局最优算法求得能量函数的最小值。全局匹配算法主要包括最大流/最小割的图割算法(Graph Cut,GC)[7-8]、动态规划算法(Dynamic Programming,DP)、模拟退火算法(Simulated Annealing,SA)[9]以及置信度传播算法(Belief Propagation,BP)[10-12]等。全局匹配算法的误匹配率低,准确率较高,能够获得较精准的稠密视差图,但是计算量大,计算时间较长。
作为目前立体匹配中广泛应用的动态规划立体匹配算法[13],在计算出初始匹配代价的基础上,用动态规划算法进行全局优化,视差图的质量得到了明显的提高,但是该算法的缺点是缺少对扫面线之间的约束限制,因此生成的视差图上带有明显的条纹状瑕疵。针对这一问题,Birchfield等[14]提出在垂直方向上,将可信度高区域内的视差向可信度低的区域扩张,改善了视差效果。Leung等[15]提出了快速的IDP方法,加强了图像的扫面线之间的视差连续性,但是算法本身需要迭代多次,且视差图质量依赖于设置的初始值。Scharstein等[16]使用独立灰度动态规划算法(IIDP)降低边缘处的遮挡代价,取得了较好的效果,但横向条纹问题仍然存在。
为解决视差图的条纹瑕疵问题以及降低误匹配率,本文在动态规划算法的基础上,提出了一种基于多邻域非线性扩散的动态规划全局立体匹配算法。该算法不仅有效地解决了水平方向上的条纹瑕疵问题,而且在图像边缘处改善了边缘模糊问题,提升了算法的精度和准确性。
1.1视差匹配约束关系
图像的成像是物体从三维投影到二维空间的过程,大量信息丢失,同时伴随着空间噪声、相机切向和径向畸变的存在,使得视差匹配问题本身存在固有的不确定性。一般情况下,源图(Resource)中的像素点,在匹配图(Matching)中会存在多个候选匹配点,因而导致了匹配歧义。为了使匹配更有效,需要引入一系列的约束来降低像素点之间的误匹配,从而提高匹配质量和效率。本文算法遵循下列约束条件:
(1) 顺序一致性约束。在源图中具有一定顺序的像素点,在目标图中也具有相应的顺序。即Rm<Rn且Tm<Tn,0≤m≤n<W,其中Rm、Rn是源图中的像素点坐标,Tm和Tn是目标图中对应的匹配点坐标,W是图像的宽度。
(2) 视差范围约束。限定立体匹配搜索的视差空间是有限的,即d∈[0,dmax],其中d是匹配点的视差值。
(3) 遮挡约束。当图像中存在遮挡区域时,左遮挡与右遮挡不能同时出现。
1.2全局能量代价函数的构造
基于能量代价函数的全局优化算法的本质是将立体匹配问题转化为求取视差的最优解问题。首先要构造一个建立在视差空间的全局能量代价函数,然后利用全局优化算法来求取使代价函数取得最小值时的视差值d。
立体匹配的全局能量代价函数包括匹配像素间的数据项Edata(d)、衡量图像对中匹配像素点之间的相似性、像素间的视差平滑惩罚项Esmooth(d),约束相邻像素间的不连续性。
E(d)=Edata(d)+λEsmooth(d)
(1)
式(1)的解空间为D(d1,d2,…,dn),其中n为行内像素的个数,di为第i个像素的视差值。通过最小化该函数得出匹配的视差图Edata(d)如下:
Edata(d)=∑(DSI(x,y,d))
(2)
其中,DSI是视差的叠加代价。
Esmooth(d)=∑ρ(d(x,y)-d(x+1,y))+
ρ(d(x,y)-d(x,y+1))
(3)
其中,ρ是视差的单调递增函数,使得视差处处平滑。
现有的全局优化动态规划匹配算法的一个问题是在计算每个像素点的匹配代价后直接构建包含有平滑约束的全局能量函数,并未考虑匹配代价叠加,从而导致动态规划立体匹配中的横条纹瑕疵问题。另一个问题是在图像的边缘处,深度是不连续的,在边缘再平滑将会造成边界的模糊。边界模糊的很大原因是由于在此处的视差代价计算过大,不符合真实情况。对此,本文在原有的视差空间基础上重新设计视差空间,根据降低平滑代价的思想优化原有Esmooth,定义全新的平滑优化项解决边缘模糊问题。
2.1概述
在立体匹配算法框架的基础上,本文算法结构主要分为3个部分。首先是使用相似性测度函数建立待匹配图像对的视差空间;其次通过非线性扩散方法对得到的视差空间进行匹配代价聚合;最后用优化边缘的动态规划算法来建立全局匹配代价函数。
2.2视差空间图像的建立
虽然立体匹配算法有多种,但是求解步骤通常包括原始匹配代价计算、匹配代价聚集、视差最优化计算以及视差求精4个步骤。通过相似性测度函数计算原始匹配代价,对图像进行不同视差下的灰度相似性测度,得到原始的视差空间图像(DSI),如图1所示。
图1 视差空间图像
Fig.1 Disparity space image
DSI是三维空间中不同视差d下所对应的x-y切面,该空间中的每个坐标值(x,y,d)表示像素点(x,y)在视差为d时的匹配代价值C(x,y,d),该值可用式(4)表示:
C(x,y,d)=f(IL(x,y),IR(x,y))
(4)
其中函数f(…)表示相似性测度函数。
2.3基于多邻域非线性扩散的匹配代价聚合
由于包括IIDP方法在内的动态规划算法并没有考虑到行与行之间的像素约束关系,因此往往会出现比较明显的横向条纹,即动态规划立体匹配中的横条纹瑕疵问题。本文引入非线性扩散方法解决立体匹配中的条纹问题。
在图像处理领域中,非线性扩散可以用于图像的平滑处理,可以进行图像邻域的交互,从而扩大局部数据的影响。扩散过程中,灰度值在图像中传播,当所有像素的灰度值相等时达到平衡。本文在Perona等[17]提出的将非线性扩散与图像内容相联系的PM模型的基础上,对区域内和区域间采取不同的滤波策略,从而得出DSI的扩散规则如下:
DSI(x,y,d)=(1-4β)DSI(x,y,d)+
(5)
其中:DSI(x′,y′,d)是像素点(x,y)的多邻域,即与点(x,y)直接相连的上、下、左、右以及对角线上的像素点;β表示控制扩散速度的参数;N8定义如下:
N8={(-1,-1),(0,-1),(1,-1),(1,0),
(1,1),(0,1),(-1,1),(-1,0)}
(6)
将非线性扩散匹配代价聚合方法加入视差计算框架中,构建新的待优化问题模型。多邻域非线性扩散代价聚合可以考虑到行间像素点的约束信息,因此减少横向条纹,提高匹配质量。
2.4动态规划寻径求解优化的全局能量函数
因原有的平滑优化项会导致边缘模糊的问题,在原有的视差函数ρ的基础上与某个单调递减函数乘积,利用在此区域降低平滑代价的思想优化,全新的Esmooth如下:
Esmooth(d)=∑ρ(d(x,y)-d(x+1,y))×
ρ′(|(I(x,y)-I(x+1,y))|)+
ρ(d(x,y)-d(x,y+1))×
ρ′(|(I(x,y)-I(x,y+1))|)
(7)
其中ρ′是和灰度值关联的单调递减函数,在图像的边缘处,灰度值的变化较大,因此可以降低灰度值相差较大处的平滑代价,优化边缘。
动态规划解决匹配问题的思想是,在源图与目标图中对应的扫描线上寻找最小匹配代价路径。设m、l、r分别代表上一阶段的3种匹配状态:匹配、左图可见(左遮挡)、右图可见(右遮挡)。同理,设M、L、R分别表示目前状态。在加入限定的约束条件后,排除双遮挡(即左右均遮挡)的情形,那么匹配状态转换只有7种形式,如图2所示。通过以上假设,可将问题转化为动态规划的范畴[18]。
图2 动态规划立体匹配算法的状态变换形式
Fig.2 Style of state transition of dynamic programming stereo matching algorithm
图3所示为动态规划路径的实例,在当前的匹配状态中,左右扫描线上的a、b、c、f、g、k6个像素点实现了正确匹配,d和e像素点发生了左遮挡,即在右扫描线上是不可见的,而h和i像素点在左扫描线上不可见,即右遮挡点。
图3 动态规划路径寻找
Fig.3 Routine of dynamic programming
用动态规划在源图与目标图之间对应扫描线上寻找最优路径的过程,就是求解某一视差分配的路径或者最优轨迹(即最优视差分布)使得能量代价函数E(d)取值最小,即P(d)=arg min(E(d))。此时寻优路径搜索出的路径包括了遮挡点和匹配的像素点的信息。在算法中,用检测到的遮挡点的像素左最邻近的点的视差填充遮挡点,提高了匹配精度。填充的部分程序如下:
for (x=start;x!=end;x+=1)
{
intd= disp[x] ;
if (disp[x] ==occLabel)
disp[x]=oldd ;
else
oldd=d;
}
目前,立体匹配算法的主要评价标准是美国Middlebury College的Scharsitein提出的立体匹配评价标准和评价平台[19],本文采用该平台提供的标准立体图像测试集Tsukuda图像、Sawtooth图像、Venus图像和Map图像检验本文算法的效果,并依此进行分析。
对于匹配所产生视差图的评价主要通过定量衡量标准的误匹配率(Percentage of Bad Matching,PBM)体现,定义PBM为
B=
(|dc(x,y)-dT(x,y)|>δd)
(8)
其中:δd为视差容差,一般取值为1.0;N为图像的像素点总数。该指标反映了算法得到的视差值dc(x,y)与真实视差值dT(x,y)的误差大于δd的像素个数在整幅图像中的比例。
与此同时,采用另外3个重要指标来量化最后的视差结果以便更全面地反映匹配结果,分别为
无纹理区域误匹配率)、BD(视差不连续区域误匹配率
非遮挡区域误匹配率)。
测试集图像的源图像、真实的视差图、IIDP动态规划全局匹配算法得到的视差图以及本文方法得到的视差图对比结果如图4所示。
图4(a)～4(d)中,对于Tsukuba图像,本文算法相比原有IIDP全局算法的误匹配率降低了28%,在无纹理区域和非遮挡区域的误匹配率分别降低了40%和31.8%,横向条纹得到了明显的改善,且修复了边缘模糊的问题。在图4(e)～4(f)中,对于Sawtooth图像,改进后的全局算法相比原算法的误匹配率下降了34%,而在无纹理区域和非遮挡区域的误匹配率分别降低了48.8%和50%。在第3幅测试图像Venus中,改进的全局算法相比原有算法的误匹配率降低了51.6%,在无纹理区域和非遮挡区域的无匹配率分别降低了58.5%和60.7%。同时,在图4(d)和图4(i)两幅深度图中,有较为清晰的黑色或者灰色的纹理,代表此处是遮挡部分,可见本文算法能够有效地识别遮挡区域。因而本文方法对带有遮挡的图像依然具有稳定的匹配效果,相比于传统动态规划算法,提高了匹配的鲁棒性。在Map图像中,改进的全局算法相比原有的全局算法的误匹配率降低了75.5%,在无遮挡区域和连续区域的误匹配率分别降低了88.3%和62.7%。本文算法所获得的视差图都大幅度地提高了匹配的精度,且明显改善了动态规划全局算法中的“橫条纹瑕疵”问题,提高了匹配的准确性,证明了算法的可行性和正确性。在匹配算法耗时方面,测试所用计算机的配置为Intel Core i3,4 G内存,算法运行时间如表1所示。可以看出,本文的改进算法在提高匹配精度的同时,也保证了算法的执行时间。
图4 对标准图像Tsukuda、Sawtooth、Venus和Map的实验结果对比
Fig.4 Comparsion of experiment results for standard images of Tsukuda、Sawtooth、Venus and Map
表1 算法运行时间
Table1 Time consumption of different methods
相似性测度函数中常用的有灰度差的平方(SD)、灰度差的绝对值(AD)等。本文用这两种测度函数测评Middlebury提供的标准立体匹配数据集图像,对比数据如表2所示。
从表2可以看出,在所有评价结果中,AD方法的结果完全优于SD方法,因此,本文算法在原始匹
配代价计算选用AD方法,即
C(x,y,d)=|IL(x,y)-IR(x-d,y)|
(9)
为了更好地评测本文算法的立体匹配效果,将其与其他几种著名的算法进行对比,对比结果如表3所示。从表3可以看出,本文的全局算法对所有图像的平均误匹配率为5.60%,相比于IIDP全局算法的9.32%,误匹配率降低了39.9%。
表3中还对比了Scanline 全局[16]、Di快速匹配[20]等全局立体匹配算法以及RTCensus[21]算法。综合各个指标,本文算法不仅平均误匹配率在所有算法中最低,且在图像参数的11个指标中有9项指标排名第1,本文算法的表现均优于其他全局算法和局部算法,体现出了更好的准确精度和匹配质量。
表2 SD、AD测度函数表现
Table2 Performance of SD、AD test functions based on test images (%)
表3 本文方法与IIDP全局算法的参数对比
Table3 Comparison results for IIDP and the proposed algorithm (%)
在深入研究现有算法的基础上,本文提出了一种基于多邻域的非线性扩散动态规划立体匹配算法,增加了多邻域非线性扩散进行代价叠加计算,提高了算法整体的准确性,明显改善了传统动态算法的“橫条纹瑕疵”问题,降低了误匹配率。在视差优化阶段,在图像的边缘处降低平滑代价,从而改善了边缘模糊的问题。本文算法与传统动态优化算法相比,具有更准确、效率更高、边缘清晰的特点。针对不同测试图像的实验结果表明,本文算法的平均误匹配率为5.60%,算法的效果和精度远远高于改进前的IIDP全局优化算法,且匹配的稳定性得到加强。与其他全局算法的对比结果表明,本文算法具有更好的精度和准确度。
参考文献：
[1] TIPPETTS B,LEE D J,LILLYWHITE K,etal.Review of stereo vision algorithms and their suitability for resource-limited systems[J].Journal of Real-Time Image Processing,2016,11(1):5-25.
[2] BROWN M Z,BURSCHKA D,HAGER G D.Advances in computational stereo [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2003,25(8):993-1008.
[3] DUMONT M,GOORTS P,MAESEN S,etal.Real-time local stereo matching using edge sensitive adaptive windows[C]//International Conference on Signal Processing and Multimedia Applications.Switzerland:Springer,2015:117-126.
[4] HOSNI A,BLEYER M,GELAUTZ M.Secrets of adaptive support weight techniques for local stereo matching [J].Computer Vision & Image Understanding,2013,117(6):620-632.
[5] PAN S C.Stereo matching algorithm based on belief propagation system[J].Applied Mechanics & Materials,2015,713/715:1931-1934.
[6] KOLMOGOROV V,MONASSE P,TAN P.Kolmogorov and Zabih's graph cuts stereo matching algorithm[J].Image Processing on Line,2014(4):220-251.
[7] TANIAI T,MATSUSHITA Y,NAEMURA T.Graph cut based continuous stereo matching using locally shared labels[C]//IEEE Conference on Computer Vision and Pattern Recognition.USA:IEEE Computer Society,2014:1613-1620.
[8] KIM J H,KWON J W,YUN H K.Multi-baseline based texture adaptive belief propagation stereo matching technique for dense depth-map acquisition[C]//International Conference on Electronics,Information and Communications.USA:IEEE,2014:1-2.
[9] HERRERA P J,PAJARES G,GUIJARRO M,etal.Combining support vector machines and simulated annealing for stereovision matching with fish eye lenses in forest environments [J].Expert Systems with Applications,2011,38(7):8622-8631.
[10] WANG X,LIU Y.Accurate and fast convergent initial-value belief propagation for stereo matching[J].Plos One,2015,10(9):e0137530.
[11] KLAUS A,SORMANN M,KARNER K.Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure[C]//International Conference on Pattern Recognition.USA:IEEE Computer Society,2006:15-18.
[12] YANG Y,WANG X,LIANG Q.Belief propagation stereo matching algorithm based on ground control points and spatiotemporal consistency[C]//International Congress on Image and Signal Processing.USA:IEEE,2015:79-80.
[13] OHTA Y,KANADE T.Stereo by intra- and inter-scanline search using dynamic programming [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1985,7(2):139-154.
[14] BIRCHFIELD S,TOMASI C.Depth discontinuities by pixel-to-pixel stereo[J].International Journal of Computer Vision,1999,35(3):269-293.
[15] LEUNG C,APPLETON B,SUN C.Fast stereo matching by iterated dynamic programming and quadtree subregioning[C]//British Machine Vision Conference.UK:[s.n.],2004:97-106.
[16] SCHARSTEIN D,SZELISKI R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[C]//Stereo and Multi-Baseline Vision.USA:IEEE,2001:131-140.
[17] PERONA P,MALIK J.Scale-space and edge detection using anisotropic diffusion [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1990,12(7):629-639.
[18] WANG P,CHEN C,WEI F F.A Stereo Matching Algorithm Based on Outline-Assisted Dynamic Programming[M].Berlin Heidelberg:Springer,2014:297-306.
[19] WEI P Y.Research on stereo matching algorithms of binocular vision [D].Chongqing:Chongqing University,2009.
[20] 狄红卫,柴颖,李逵.一种快速双目视觉立体匹配算法[J].光学学报,2009,29(8):2180-2184.
[21] HUMENBERGER M,ZINNER C,WEBER M,etal.A fast stereo matching algorithm suitable for embedded real-time systems[J].Computer Vision & Image Understanding,2010,114(11):1180-1202.
ADynamicProgrammingGlobalStereoMatchingAlgorithmBasedonMultipleNeighbors’NonlinearDiffusion
GENGDong-dong,LUONa
(KeyLaboratoryofAdvancedControlandOptimizationforChemicalProcesses,MinistryofEducation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)
Abstract:Binocular stereo matching can obtain the accuracy and dense disparity map by comparing two images.However,the utilization of dynamic programming algorithms may result in some shortcomings,such as stripe-like and low accuracy.Aiming these problems,this paper proposes a new stereo matching algorithm based on multiple neighbors’ nonlinear diffusion.Firstly,absolute difference test method is used to build disparity space image in raw costs computation period.And then,according to the constraint relation between rows and columns,multiple neighbors’ nonlinear diffusion of costs aggregation is proposed to improve the global costs function.Finally,dense disparity maps during the global optimization process are obtained by the edges-optimized DP optimization.The experiment results via Middlebury test images show that the proposed algorithm attains the average PBM5.60% and raises the accuracy39.9% than IIDP.Moreover,the problem of stripe-like is well solved and the edge-blurring is also improved.Compared with other global matching methods,the proposed algorithm reduces PBM by38.2% and has9of11indexes to rank the first.
Key words:dynamic programming; stereo matching;nonlinear diffusion;disparity;costs aggregation
中图分类号：TP391
文献标志码：A
文章编号：1006-3080(2017)05-0677-07
DOI:10.14135/j.cnki.1006-3080.2017.05.012
收稿日期：2016-11-16
基金项目：国家自然科学基金(61403140);上海市自然科学基金(13ZR1411500)
作者简介：耿冬冬(1991-),男,硕士生,主要研究方向为图像处理、双目视觉。E-mail:wintergeng@foxmail.com
通信联系人：罗 娜,E-mail:naluo@ecust.edu.cn