基于自适应权值的图割立体匹配算法
2018-03-27,
,
(昆明理工大学 机电工程学院, 昆明 650504)
0 引言
立体匹配是计算机视觉领域热门研究问题之一，特别是在提高匹配精度方面，一直是立体匹配的研究重点[1-3]。目前，立体匹配技术作为三维重建、增强现实和视觉导航等领域的关键技术，已经得到了国内外专家学者的广泛研究，其目的是通过确定两幅或多幅图像之间的对应点来得到视差数据，从而将二维的距离信息转化为空间上的深度信息[4]。
Daniel Scharstein 和Richard Szeliski[5]等人对当时常见的立体匹配算法进行了比较权威的研究、分类和总结，并为广大的研究者建立了立体匹配算法的统一评测网站Middlebury 进行立体匹配的匹配误差对比和分析，根据立体匹配算法采用的最优化理论方法的不同主要分为局部立体匹配和全局立体匹配两种。局部立体匹配算法采用局部优化方法进行视差估计，主要算法有SAD、SSD、NCC和ZNCC等，其能量函数一般只有数据项，没有平滑项，局部算法具有内存占用小，算法速度快以及能够满足实时性要求等优点，但是在遮挡、无纹理和重复纹理区域往往存在较高的误匹配，总体匹配精度不高。Kanade and Okutomi[6]是通过评估局部灰度和视差的变化来选取合适的窗口，但是该方法不仅过分依赖初始的视差估计而且计算开销大，匹配窗口的形状被限制为矩形，对于视差不连续区域匹配不够理想。Yoon[7]等人提出基于色彩和距离信息的自适应支持权重法，有效地提高了整体和视差不连续区域匹配精度，由于该算法是对彩色图像3个通道进行计算，随着匹配窗口的增加，计算复杂度较高。全局立体匹配算法采用全局优化方法进行视差估计，主要算法有置信传播、动态规划和图割等，建立包含数据项和平滑项的全局能量函数，通过最小化全局能量函数得到全局最优视差分布，由于全局匹配方法采用全局寻优，因此获得的视差图效果好，匹配精度较高。 Roy和Cox等人[8]提出基于图割理论的能量函数优化方法解决立体匹配问题，并在视差图效果和精度上取得了很大的突破。文献[9]基于图割理论对立体匹配的遮挡问题进行了研究，采用平滑约束和固定遮挡约束来处理图像对遮挡区域，但是算法复杂度较高，处理遮挡问题不够理想,总体匹配精度欠佳。
基于此，针对传统自适应权重存在计算复杂度高和图割匹配精度低的问题，本文提出一种改进的基于自适应权值的图割立体匹配算法。本文所提算法有3个贡献点，1)根据格式塔理论的相似性和相近性提出新的权重值计算方式作为能量函数的数据项。2)引入图像的梯度作为能量函数的平滑项，提升了视差图的效果。3)将新提出的自适应权值与图割算法相结合，提高了匹配精度。
1 创建能量函数及求解
利用图割算法求解立体匹配问题，主要分为3个步骤：首先建立全局匹配能量函数，然后根据能量函数的具体形式构建合适的网络图，最后运用最大流最小割求解能量函数的最小值。基于三维场景中同一景物在左右图像中具有相似的像素强度和视差图具有分段光滑的假设，可以构建出如公式(1)所示的能量函数。
E(d)=Edata(d)+λ·Esmooth(d)
(1)
这里的Edata(d)叫做数据项，在左右图像的匹配窗口内计算得出；Esmooth(d)叫做数据平滑项，是根据中心像素的梯度与邻域内像素的梯度信息求得。
1.1 数据项计算
在确定每个匹配窗口内的权重值时，根据格式塔理论下的相似性和相近性原则，分别利用图像的灰度相似性和空间上的相近性来构造权值计算方式，又由于这两个因素是相互独立的事件，在匹配窗口内每个像素权值的表达式可以写为：
w(p,q)=fg(Δgpq)·fs(Δspq)
(2)
这里的fg(Δgpq)和fs(Δspq)分别表示窗口内中心像素p与邻域像素q在灰度上的权重和空间上的权重。在此可以看出，fg(Δgpq)和fs(Δspq)函数的数学模型对于计算w(p,q)至关重要，也直接关系着立体匹配的匹配精度。
在本文算法中根据灰度相似性原则对函数fg(Δgpq)定义，随着像素p与q灰度差的绝对值Δgpq增大，fg(Δgpq)的函数值越小，又由于图像某些像素由于外部因素的干扰，使得Δgpq很大，这显然是不合乎常理的，这里我们采用了灰度值截断处理的方式。考虑到局部算法的实时性要求，这里采用计较简单的线性核来定义函数fg(Δgpq)，表达式为：
(3)
这里的Δgpq为匹配窗口内中心像素p与邻域像素q差的绝对值，t为灰度截断值，与图像的整体灰度分布有关，依据实验决定。
依据二维正态分布具有单值性和旋转对称性，在每一个匹配窗口内，单值性体现在邻域像素权值随着与中心点的距离增加而递减；旋转对称性体现在每一个方向上距离相同时权值也相同。空间上的相近性对函数fs(Δspq)可以定义为服从二维正态分布，表达式为：
(4)
这里的Δspq=x2+y2，x和y分别为中心像素p与邻域像素q在x、y方向上的坐标值之差。σ为标准差，其大小决定了fs(Δspq)在二维空间上权值分布的幅度。
匹配代价函数的数据项可以通过在左右图像的匹配窗口内的权值进行计算得到。在计算数据项时，为了避免左右匹配窗内权值差异情况，更准确地计算出匹配视差，需要联合参考图像和目标图像的匹配窗权值来计算。所以数据项可以写为：
(5)
(6)
1.2 平滑项项计算
在能量函数(1)中的数据平滑项Esmooth(d)，为了解决无纹理或者是弱纹理图像区域在匹配过程中较容易出现误匹配问题，可以依据视差图分段平滑的假设，根据中心像素的梯度与邻域内像素的梯度信息来确定平滑项的值，如果梯度值相近，则赋予Esmooth(d) 的值较大，增加平滑效果，反之亦然。Esmooth(d)可以写为：
(7)
这里的p和q分别表示中心像素点和邻域像素点，取q为p的四邻域内的像素点，即假设p为p(i,j)，则q取p(i,j-1) 、p(i-1,j)、p(i+1,j) 和p(i,j+1) 这4个点。N是p和q像素对的集合，dp和dq分别表示参考图像中中心像素点和四邻域像素点的视差值，V(dp,dq) 是像素p和q的视差平滑约束，可以写为：
V(dp,dq)=λ*T(dp≠dq)
(8)
(9)
这里的G表示参考图像的梯度，本文采用了sobel梯度模型。在确定具体的λ值时，本文采用了双阈值处理策略，如果匹配点p的梯度大于上限阈值或者小于下限阈值时，图像的该处被认为处于同一视差平面，需要给予较大的平滑约束；当匹配点p的梯度介于上限阈值和下限阈值之间时，则认为该处可能处于图像的视差不连续区域，则需要给予较小的平滑约束。
1.3 网络图的构建及模型求解
运用图个算法求解立体匹配相关问题时，当完成能量函数的构建后，还需要根据能量函数的具体形式去构建与此相对应的网络图。根据Greig提出的网格图创建法，网络图G=
构建基于图割的网络图一般步骤：首先需要创建一个三维的笛卡尔坐标系O-XYZ，将图像IL放置在坐标系的xoy平面上，图像的原点与xoy平面的原点重合，图像的x,y轴分别于xoy平面的x,y正半轴重合，在Z轴的正方向上，等距离放置l1,l2,…,ln向量，然后在l1(原点O)处放置q0，再li与li+1处放置qi，其中i=1,2,...,n-1， 在ln处放置qn，这样一个立方体网络就构建完成了。 在Z轴的每个区间[qi,qi+1] 都恰好包含一个li+1，这里的i=0,1,…,n-1；在整个立体网络中，(p,qi)=(px,py,qi)为网络图中的节点，N(p) 为像素p的邻域。然后再立方体网络的上下两个面分别放置源点s和汇点t，并在s到IL平面上的每个像素节点添加一条边，t到节点集合{(px,py,qn)|(px,py)∈IL}添加一条边，至此，就获得了一个无向图G
V={s,t}∪ {(p;qi)|p∈IL,i=0,1,2,...,n}
(10)
E={(s,(p;q0)),(t,(p;qn))|p∈IL}∪Es∪Ed
(11)
其中:Es为光滑边的集合，Ed为视差边的集合，具体表达式如下：
Es={(p;qi),(q;qi)|p∈IL,q∈N(p),i=0,1,...,n-1}
(12)
Ed={(p;qi),(p;qi+1)|p∈IL,i=0,1,...,n-1}
(13)
定义图G中各条边的容量：
1)连接源点和汇点边的容量：Ed和Es中的容量设置为+∞。
2)视差边的容量：对任意p∈IL,i=0,1,...,n-1 ，边ep,i+1=:((p;qi),(p,qi+1)) 的容量大小应等于数据项:
c(ep,i+1)=Edata
(14)
3)光滑边容量：p,q为一幅图像中的相邻像素。
c(p,q)=Esmooth
(15)
此时，完成网格图N=(G,s,t,c) 的组建，如图1所示。
图1 网络图构建
一个s-t切割C=S,T,把图G中的顶点分割成两个没有任何交集的集合S和T，最小割集就等于从集合S到集合T的所有边的容量之和，根据Ford-Fullkerson的网络流理论[10]，网络图中的最小割可以转化为求网络中的最大流来实现，然后再运用α扩展算法[8]进行图构造，算法通过对不同的α值进行迭代计算得到能量函数的最小值，直到收敛，从而找到能量函数大的局部最小，最终得到最优的视差分布图。
2 视差精化
(16)
误匹配点的视差通过在同一行上左右搜索最近的正确匹配点，把这两个点中视差值最小的作为误匹配点的视差值。经过左右一致性检查后，在一定程度上可以提高匹配精度，但同时也会产生水平条纹失真问题，为了解决这个问题和进一步提高视差精度，本文采用加权中值滤波对视差图做进一步后处理。具体的做法是以原始的左图像作为引导图像，以校正视差点p作一个校正窗口，利用图像的色彩相似性和距离的相近性分别计算窗口内每一点的像素权值，可以写为：
(17)
这里的Δcpq和Δspq分别为中心像素p和邻域像素q在RGB色彩空间上的差异性和几何空间的距离，λc和λs分别为所对应的权重系数。为每一像素点计算完权重后，再分析视差图中对应窗口内的视差分布，对p点邻域内所有点在视差图中进行加权直方图统计，统计后每个视差对应的权值为id，按照视差进行升序排列，最后在对加权直方图进行积分，在取得积分中值所对应的视差即为该点的最终视差。公式可以写为：
(18)
l为视差搜索时的最大视差。
3 实验结果及分析
本文的立体匹配算法流程主要包括创建新的能量函数、构建网络图、模型求解和视差精化四大步骤。实验平台为：实验平台为：Intel@ Core i5 CPU，主频 2.40 GHz，4 GB 内存。立体匹配系统的编程环境为旗舰版 Microsoft Visual Studio 2010。在匹配精度上，为了定量地检验本算法的有效性，实验中采用了来自美国 Middlebury 大学计算机视觉研究中心网站提供的四幅标准立体图像对Tsukuba、Venus、Teddy和Cones分别进行测评，通过将实验结果与网站提供的真实视差图进行对比分析可以得到量化的匹配误差，从而能够客观地去评价算法精度。实验时，四组标准图像对的视差搜索范围依次0～15, 0～19, 0～59, 0～59，立体匹配算法参数的选择对实验结果影响很大，若无特殊说明，实验中的相关参数设置如表1所示。
表1 参数设置
图2 不同方法对Tsukuba图像的匹配结果
图2以Tsukuba图像为例，采用不同的匹配方法分别对图像进行立体匹配，直观反映了本文所提算法较以往算法具有更好的匹配效果。图2中的(c) 图结果是采用了传统的图割方法进行立体匹配的结果，可以看到图中用红色方框标记的地方代表了传统的图割优化方法得到的视差图存在明显的误匹配，而本文算法在这些地方的视差几乎与标准视差图一致，不存在误匹配现象；图2中的(d) 图是采用AdaptAggrDP[13]方法进行立体匹配的结果，与传统的动态规划方法一样，依然存在明显的条纹现象，本文算法利用图像梯度信息估计能量函数的平滑项，通过图割的优化方法就避免了这种条纹现象，也使视差图呈现分段平滑效果。图2中的(e) 图是采用TwoStep[14]方法进行立体匹配的视差图结果，通过比较图中方框标记部分可以得出，TwoStep方法在桌子边缘处并没有得到准确的视差信息，出现了明显的匹配错误，图2中的(f)图是采用SymBP+occ[12]方法进行立体匹配的结果，可以看到，通过BP算法和遮挡处理后的视差图在边界区域依然表现得不尽人意，而本文算法得到的视差图背景与前景边界清晰，定位准确，明显优于TwoStep和SymBP+occ方法所得结果。图2中的(h) 图是本文视差图与标准视差图在对应位置上大于一个像素的误匹配像素图像，白色代表正确匹配，黑色代表误匹配，通过计算正确匹配点与所有匹配点的比值，实验结果表明所提算法正确匹配率高达98.48%，与SymBP+occ和GC方法相比，视差图的总体精度分别提高了0.23% 和2.6%。
图3是以Teddy图像为例，为了验证本文所提算法在低纹理和无纹理区域的匹配效果，不同匹配算法和本文算法在此区域的匹配细节对比图。图3中的(a) 图采用AdaptAggrDP方法在图中低纹理和无纹理区域(红色标记区域，圆圈为低纹理区域，方框为无纹理区域)都没有得到准确的视差，在这些区域的匹配结果极差，图3中的(b) 图采用了MultiResGC[15]方法得到的视差结果，在传统的图割算法基础上引入了多个标签进行细化，以增加深度标签的数量，视差结果优于AdaptAggrDP方法，能够解决大部分低纹理和无纹理区域的匹配错误，同时也能够在一定程度上还原图像的真实边界，但是边界不够准确，边界缺失和无纹理区域存在误匹配的现象依然存在，图3中的(c) 图采用文中所提算法，利用改进的自适应权值和图像梯度信息重新构造新的能量函数进行匹配计算，同时运用图割的优化方法来求解全局能量函数的最小值和加权中值滤波进行视差精化，从而可以有效地提高低纹理和无纹理区域的匹配精度，通过与真实的视差图对比，图中的标记区域都已经得到了准确的视差值，从而验证了本文所提算法在一定程度上是可以提高图像在低纹理和无纹理区域的正确匹配率。
图3 细节对比图
为了更好地测评本文所提算法，图4是采用了另外两种算法和本文算法分别对标准的四幅测试图像对进行测试的对比结果。第一列为标准图像对的左视图参考原图，从上到下依次为Tsukuba、Venus和Teddy、Cones图像；第二列为各参考图对应的标准视差图；第三列为AdaptAggrDP[13]算法匹配结果；第四列为MultiResGC[15]算法匹配结果；第五列为本文所提算
法的匹配结果。由图4分析可知，文中所提算法在四幅图像中的匹配总体上优于AdaptAggrDP和MultiResGC两种立体匹配算法。具体来讲，在Tsukuba和Teddy的视差图中，AdaptAggrDP 呈现出前景溢出和明显条纹现象，Teddy视差图甚是突出，MultiResGC方法出现边界不够清晰，反观本文结果，视差图呈现分段平滑，边缘清晰可辨；在Venus的视差图中，AdaptAggrDP和MultiResGC 方法由于误匹配产生了黑色区块，文中算法由于没有这些误匹配存在进而提高了匹配精度。
图4 不同方法对四幅标准图像的综合对比
依据 Middlebury 提供的3个定量算法评价指标分别对比本文算法和其他几种经典算法，表2给出了nonocc (非遮挡区域匹配误差百分比)、disc (视差不连续区域匹配误差百分比)和all(所有区域的匹配错误百分比)的量化评价结果。从图2图4和表2综合分析可以得出：本文算法与其他算法TwoStep、PM-GCP和AdaptAggrDP等相比，遮挡区域和视差不连续区域匹配精度均高于这3种算法，从误差数据分析来看，Tsukuba视差图中所有区域的匹配精度分别提高了2.16%， 0.67% 和1.98%， 视差不连续区域的匹配精度分别提高了7.63%，4.43%和2.6%；与传统的GC算法进行对比，本文算法在重复纹理、稀疏纹理区域具有很好的匹配效果，四幅测试图像GC算法的平均误匹配率为11.42%，本文算法的平均误匹配率为5.86%，平均精度提高了5.56%。特别是在Teddy图中，由于弱纹理区域(如蓝色背景板)、重复纹理区域(如砖墙部分)以及遮挡区域相对较多，所以匹配难度也相对较大，出现误匹配的几率也大，本文算法与文献[10]所提SymBP+occ算法相比，SymBP+occ算法在Teddy 图中的平均误匹配率为11.39%，而本文算法的平均误匹配率为10.21%，平均匹配精度提高了1.18%。
表2 实验结果数据对比
4 结论
本文提出了一种基于自适应权值的图割立体匹配算法：首先利用灰度相似性和空间相近性对能量函数的数据项进行重新定义计算，引入图像梯度作为平滑项的度量，以此创建新的能量函数；然后运用图割理论和α扩展算法进行模型求解，最后视差精化得到最终视差图。本文所提出算法的优点在于通过重新定义数据项和平滑项的计算方法，与传统的图割和大多数算法相比，在图像的低纹理和无纹理区域均能获得较好的匹配效果，边缘细节更清晰，总体匹配精度更高。但是对于大范围视差匹配还是不尽人意，原因是没有对遮挡区域和边界大范围遮挡做进一步研究，在今后的学习中将对算法进行进一步研究和改进，提高算法的鲁棒性。
[1]Ishikawa H，Geier D．Occlusion，discontinuities and epipolar lines in stereo[A]//Proceedings of the 5th European Conference on Computer Vision[C]．Freiburg，Germany：Springer Press，1998：242-256．
[2]Sun J．Shum H Y．Stereo matching using belief propagation[A].Proceedings of the 7th European Conference On Computer Vision[C]．Copenhagen，Denmark：Springer Press，2002：510-524．
[3]Scharstein D，Szeliski R．A taxonomy and evaluation of dense tw0-frame stereo correspondence algorithms[J]． International Journal on Computer Vision，2002，47(1)：7-42．
[4]Bai M, Zhuang Y, Wang W. Progress in binocular stereo matching algorithms[J]. Control & Decision, 2008, 23(7):721-729.
[5]Scharstein D, Szeliski R. A Taxonomy and Evaluation of Dense Two-frame Stereo correspondence Algorithms[J]. International Journal of Computer Vision ,2002,47(1):7-42.
[6]Kanade T , Okutomi M. A stereo matching algorithm with an adaptive window : theory and experiments [ J ] . IEEE Transactions on Pattern Analysis and Machine Intelligence , 1994 , 16 ( 9) : 920 -932.
[7]Yoon K J , Kweon I S. Locally adaptive support-weight approach for visual correspondence search [J ] . IEEE Transactions on Pattern Analysis and Machine Intelligence , 2006 , 28(4) :650-656.
[8]Boykov Y，Veksler O，Zabih R．Fast approximate energy minimization via graph cuts[J]．IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23(11)： 1222-1239．
[9]Kolmogorov V，Zabih R．Computing visual correspondence with occlusions using graph cuts[A]. Proceedings of the 8th International Conference on Computer Vision，2001[C]． 2001．2：508-515．
[10]Ford L R. Fulkerson flows in networks[J]. 1962.
[11]Huang X, Yuan C, Zhang J. Graph Cuts Stereo Matching Based on Patch-Match and Ground Control Points Constraint[A].Pacific Rim Conference on Multimedia[C]. Springer International Publishing, 2015: 14-23.
[12]Sun J, Li Y, Kang S B, et al. Symmetric Stereo Matching for Occlusion Handling[A]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition[C]. 2005:399-406.
[13]Wang L, Yang R, Gong M, et al. Real-time stereo using approximated joint bilateral filtering and dynamic programming[J]. Journal of real-time image processing, 2014, 9(3): 447-461.
[14]Wang L, Liu Z, Zhang Z. Feature Based Stereo Matching Using Two-Step Expansion[J]. Mathematical Problems in Engineering, 2014,(2014-12-18).
[15]Papadakis N, Caselles V. Multi-label depth estimation for graph cuts stereo problems[J]. Journal of Mathematical Imaging and Vision, 2010, 38(1): 70-82.
