1 引言

立体匹配是计算机视觉中的热门研究方向,广泛应用于机器人导航、虚拟现实、三维重建等领域^[1]。Scharstein等^[2]将立体匹配算法分为4个步骤:1)匹配代价计算;2)代价聚合;3)视差计算或优化;4)视差细化(视差后处理)。根据是否采用代价聚合步骤,可以将传统的立体匹配算法分为全局、半全局和局部立体匹配算法。全局立体匹配算法通常跳过匹配代价聚合步骤,直接进行视差的计算和优化,如图割法^[3]、置信度传播法^[4]等。全局立体匹配算法虽然精度高,但是计算效率低。半全局立体匹配算法中的动态规划算法^[5-6]是最为典型的方法,传统动态规划算法的结果会出现扫描线效应。局部立体匹配算法一般利用匹配点的局部信息计算匹配代价,采用代价聚合方法来改善匹配代价,然后利用WTA(Winner Take All)算法得到视差图,虽然精度低,但是计算效率高。

近几年,以深度学习为代表的机器学习被用于解决立体匹配问题,并且取得了非常好的效果。机器学习主要是将卷积神经网络(CNN)应用在立体匹配中。基于CNN解决立体匹配问题的方法也大致分为三类^[7]:1)利用CNN学习匹配代价,然后利用传统方法进行视差后处理,例如MC-CNN(Matching Cost-Convolutional Neural Network)及其改进网络^[8];2)从端到端训练CNN,直接从图像对估计视差,例如DispNets^[9]网络;3)利用多个网络得到视差图,例如CRL(Cascade Residual Learning)^[10]网络,由DisFullNet和DisResNet两个网络组成。基于CNN网络的方法取得了非常好的效果,但是也具有一定的局限性:首先遮挡区域的像素点不能用来训练,这意味着很难在这些区域获得可靠的视差估计^[7];其次,训练神经网络需要大量的数据,在某些特定场合,无法得到训练网络所需要的数据,这使得基于CNN的方法受到限制。

传统方法不需要训练数据,且已取得了较好的结果。Rhemann等^[11]将图像引导滤波器(GF)应用在立体匹配中,不仅能够减轻视差图边缘模糊现象,而且计算效率高。Yang^[12]将最小生成树(MST)引入匹配代价聚合,不仅速度快,而且精度高,但是在遮挡处容易误匹配。Zhang等^[13]提出跨尺度代价聚合模型,优化了GF、MST等算法的结果,但是对遮挡处的误匹配问题优化效果不佳。刘艳等^[14]提出结合局部二进制表示和超像素分割求精的方法,改善了弱纹理区域的阶梯效应,但是在平均误匹配率较高。龚文彪等^[15]利用mean shift分割算法,分割出不同深度区域的匹配点,根据匹配点所在的深度区域进行匹配代价重定义,在遮挡处的效果较好,但是在其他区域的误匹配率较高。为降低所有区域的误匹配率,本文提出基于图像分割的稠密立体匹配方法。

2 基于图像分割的立体匹配算法

所提算法的流程分为三个部分:1)匹配代价融合算法和SLIC(Simple Liner Iterative Cluster)^[16]算法;2)匹配代价聚合方法,包括基于视差图和超像素更新匹配代价和GF算法;3)视差后处理方法,包括左右一致性检验(LRC)、孔洞填充和十字交叉自适应窗口加权中值滤波。匹配代价聚合、视差后处理以及整个算法的流程图如图1所示。

图 1. 算法流程图。(a)匹配代价聚合;(b)视差后处理;(c)综合流程图

Fig. 1. Flow chart of algorithm. (a) Matching cost aggregation; (b) disparity post-processing; (c) integrated flow chart

下载图片 查看所有图片

2.1 匹配代价计算

匹配代价计算基于立体校正过的图像,即同一物体在左右两幅图像的同一行。匹配代价计算就是计算左右图像中各个点之间的相似性程度。分别计算图像中每点的灰度-梯度算法^[11]和零均值归一化互相关(ZNCC)算法的匹配代价。灰度-梯度算法的输入为RGB图像,而ZNCC算法的输入是由RGB图像转换成的灰度图像。

灰度-梯度算法的计算公式为

Cgray-gradient=(1-α)min[‖IL(x,y)-IR(x+d,y)‖,τ1]+αmin[‖∇xIL(x,y)-∇xIR(x+d,y)‖,τ2],(1)

式中:C_{gray-gradient}为灰度-梯度算法匹配代价;I_L为左图像;I_R(x+d,y)为右图像;x和y表示像素在图像中的坐标;d表示视差值; ∇xI_L和 ∇xI_R为图像水平方向的梯度图像;α为梯度图像匹配代价的权重;τ₁、τ₂为常量。

ZNCC算法的计算公式为

CZNCC=∑i,j∈Win[IL(x+i,y+j)-I¯L(x,y)]×[IR(x+i+d,y+j)-I¯R(x+d,y)]∑i,j∈Win[IL(x+i,y+j)-I¯L(x,y)]2×∑i,j∈Win[IR(x+i+d,y+j)-I¯R(x+d,y)]2,(2)

式中:C_ZNCC为ZNCC算法匹配代价;W_in是匹配窗口;i和j表示窗口中以中心元素为原点时,窗口内元素的坐标值,窗口大小为N×N; I¯L(x,y)和 I¯R(x+d,y)分别是左图像和右图像窗口W_in的平均值。

一般在物体边缘处容易发生遮挡,遮挡处容易发生误匹配。遮挡就是在相机的公共视场内,物体在左图中可以看到而在右图中看不到,或物体在左图中看不到而在右图中能看到。物体边缘处一般为图像边缘处。图像边缘和非边缘处具有不同的特征,因此在边缘和非边缘处对两种匹配代价计算方法分配不同的权值。由于灰度-梯度算法对灰度变化敏感,而物体边缘处一般灰度发生变化较大,因此在物体边缘处,给灰度-梯度算法分配的权值较大,给ZNCC算法分配的权值较小。反之,在非边缘区域,ZNCC算法对噪声具有较强的稳健性,因此给ZNCC算法分配的权值较大,给灰度-梯度算法分配的权值较小。

匹配代价计算公式为

C=(1-|CZNCC|)(2-β)+Cgray-gradient(2-γ)/2,edge(1-|CZNCC|)β+Cgray-gradientγ/2,others,(3)

式中:β和γ分别为ZNCC算法和灰度-梯度算法在非边缘区域的权值,都为常量。

图像的边缘可以利用SLIC超像素分割算法得到。SLIC算法将图像从RGB颜色空间转换到CIE-Lab颜色空间,每个像素的颜色(l,a,b)和坐标(x,y)组成一个5维向量V=[l,a,b,x,y],两个像素的相似性由对应向量V的欧式距离来测量。然后在图像上生成K个种子点,在每个种子点的周围空间搜索距离该种子最近的若干个像素,将它们与该种子归为同一类,直到所有像素点都归类完毕。然后计算K个超像素里所有像素点的平均向量值,再以K个平均向量值为中心去搜索其周围与其最相似的若干像素,所有像素归类完毕后重新得到K个超像素。更新聚类中心,再次迭代,如此反复直到收敛。种子点个数K可表示为

K=rowcolρ,(4)

式中:r_ow和c_ol表示图像的行和列;ρ为超像素内初始的像素个数,为常量。

对Tsukuba进行SLIC超像素分割,根据分割结果提取边缘,其结果如图2所示。

2.2 匹配代价聚合

匹配代价聚合分3个步骤:1)通过视差图更新匹配代价;2)利用超像素更新匹配代价;3)利用GF对匹配代价进行滤波。

图 2. SLIC算法结果。(a) Tsukuba图像;(b)超像素分割图;(c)边缘图像

Fig. 2. Result of SLIC algorithm. (a) Tsukuba image; (b) superpixel segmentation image; (c) edge image

下载图片 查看所有图片

首先利用视差图对匹配代价进行更新,视差图的更新公式为

Cnew(x,y,d)=|d-D(x,y)|,(5)

式中:C_new(x,y,d)为更新后的匹配代价;D(x,y)表示视差图;视差d∈[0,d_max],d_max为视差最大值。

利用超像素更新匹配代价,超像素内大多数像素拥有正确的视差值,用这些正确的视差更新超像素内像素的匹配代价。匹配代价更新公式为

Cnew=Cold×exp-nd,sns,(6)

式中:n_s表示第s块超像素中像素数目;n_d,s表示第s块超像素中视差值为d的像素数目;C_old为更新之前的匹配代价;C_new为更新之后的匹配代价。

为了解决边缘处的误匹配问题,使用GF对匹配代价进行滤波,GF滤波器定义为

gp=∑q∈wpWpq(I)fqWpq(I)=1|wk|2∑k:(p,q)∈wk[1+(Ip-μk)T(Σk+εE)-1(Iq-μk)],(7)

式中:I为RGB引导图像;f_q为待滤波图像,即匹配代价图像;g_q为滤波后的匹配代价图像;w_p为以像素p为中心的窗口;W_pq(I)为像素点p 和q 之间的权值;w_k为以像素k为中心的窗口,公式中窗口大小都为r×r;I_p和I_q为窗口w_k内像素的RGB颜色值,为三维向量;|w_k|为窗口内像素的数目;μ_k为窗口w_k的均值,为三维向量;Σ_k为3×3的协方差矩阵;ε为惩罚系数;E为3×3的单位矩阵。

2.3 视差后处理

完成匹配代价聚合后,使用WTA算法得到视差图。但是视差图上存在许多误匹配点,视差后处理在一定程度上可以消除这些误匹配点。视差后处理包括LRC算法,孔洞填充,十字交叉自适应窗口加权中值滤波和3×3的中值滤波。

LRC算法是检测误匹配点的重要且有效的方法,其主要思想是:当以左图像为参考图时,生成左视差图,反之生成右视差图。左视差图和右视差图中匹配点的视差值相同,视差值不同的点为误匹配点。LRC算法的计算公式为

|DL(x-d,y)-DR(x,y)|≤1,(8)

式中:D_L(x -d,y)表示左视差图;D_R(x,y)表示右视差图。

通过LRC算法标记出误匹配点,在孔洞填充阶段对误匹配点进行填充。孔洞填充可以看作是一个图像修复问题,经典的图像修复算法^[17-19]常利用偏微分方程、纹理合成、结构特征等方法修复图像,虽然能取得很好的结果,但是计算效率低,一般在孔洞填充阶段很少采用。传统的视差图孔洞填充算法是分别寻找误匹配点所在行的左侧和右侧距离误匹配点最近的有效匹配点,用这2个有效匹配点视差值中较小的视差值填充误匹配点,虽然效果一般,但是速度快。为了兼顾视差图修复过程的速度和精度,改进传统的视差图孔洞填充算法过程,不仅在误匹配点所在行寻找有效匹配点,还在误匹配点所在行的上一行和下一行寻找有效匹配点,此时一共有6个有效匹配点视差值,取6个视差值中的最小值填充误匹配点。但当选择同一个视差值作为大量无效点的填充值时,会在视差图上产生条纹效应,如图3(a)所示。

通过十字交叉自适应窗口加权中值滤波来减弱条纹效应,其效果图如图3(b)所示。首先确定加权中值滤波的支持域,其支持域示意图如图4所示。图4中p点为误匹配点,q是其邻域点。支持域的确定过程如下:首先在p点的竖直方向进行扩展,然后在扩展竖直方向的基础上,扩展水平方向,得到加权中值滤波的支持域。为了加快计算速度,只计算误匹配点的自适应窗口。用于判断q点是否在p点的支持域内^[20]的计算公式为

Dc(p,q)<θ1andDc(p,q+)<θ1q+=q(x,y+1),verticalq(x+1,y),horizonalDs(p,q)<L1Dc(p,q)<θ2ifL2<Ds(p,q)<L1,(9)

式中:D_c 表示点p与点q的RGB颜色差值;D_s表示两点之间的距离差值;L₁、L₂、θ₁、θ₂为常数。

图 3. 不同算法所得结果。(a)孔洞填充;(b)十字交叉自适应窗口加权中值滤波

Fig. 3. Results of different algorithms. (a) Hole filling; (b) cross adaptive window weighted median filtering

下载图片 查看所有图片

图 4. 支持域

Fig. 4. Support region

下载图片 查看所有图片

在支持域内进行加权中值滤波,权值通过RGB颜色值计算^[21]:

wpq=exp-(Ip-Iq)2σc2,(10)

式中:I_p和I_q分别为p点和q点的RGB颜色值;σ_c为常量。

求出权值后,再取中值。构造视差直方图:

h(x,d)=∑x'∈Ns(x)w(x,x')δ[V(xx')-d],(11)

式中:h(x,d)为p点的直方图;x为p点的坐标;x'为支持域内其他点的坐标;N_s(x)表示点x的支持域;V表示取点的视差值操作;δ(·)为狄拉克函数;w(x,x')表示权值。

将权值按照视差值从小到大的顺序相加,当权值之和大于等于总权值的一半时,此时对应的视差为加权中值滤波的结果,即

d*=minds.t∑jd=dmindh(x,jd)≥12∑jd=dmindmaxh(x,jd),(12)

式中:d^*为加权中值滤波的结果;d_min、d_max分别表示视差的最小值和最大值。

3 实验结果与分析

实验环境为:Windows7 64位系统,Intel(R) Core(TM)i7-6700CPU主频3.4 GHz,4核,8 GB内存。使用Middlebury^[22]平台提供的Tsukuba、Venus、Teddy和Cones 4组彩色图像进行测试。利用这4组图像确定算法参数,并与其他算法进行比较。除这4组图像外,再加上平台提供的27组图像,共利用31组图像对所提算法进行测试。

3.1 参数设置

所提算法参数设置如下:灰度-梯度算法和GF的参数采用文献[ 11]的参数α=0.9,τ₁=10,τ₂=2,r=9,ε=0.0001;十字交叉自适应窗口的参数采用文献[ 20]的参数L₁=62,L₂=32,θ₁=32,θ₂=16;加权中值滤波的参数采用文献[ 21]的参数σ_c=5;剩下的参数ZNCC窗口大小N,匹配代价融合系数β、γ,超像素分割系数ρ和迭代次数T通过实验确定。

首先,确定ZNCC窗口大小N的值,具体方法如下:1)计算ZNCC的匹配代价,GF滤波得到新的匹配代价;2)采用WTA算法得到视差图;3)计算AvgPBM。AvgPBM表示4组图像在非遮挡区域、所有区域和深度不连续区域(遮挡处)三个区域误匹配率的平均误匹配率。选择误匹配极限误差E_rror>1,即得到的视差图与标准视差图的像素差值大于1时认为是误匹配。N与AvgPBM的关系如图5(a)所示,当N=5时,AvgPBM值最小。

下一步确定β和γ的值,与确定N的方法相同。固定N=5、ρ=1000。β、γ取不同的值时与AvgPBM的关系如图5(b)所示。当β=0.9、γ=0.3时,AvgPBM值最小。

确定N、β、γ的值之后,选择迭代次数T=2,固定这几个值。按照第2节描述的算法得到视差图。超像素分割系数ρ与AvgPBM的关系如图5(c)所示。当ρ=2300时,AvgPBM值最小。

固定N=5、β=0.9、γ=0.3和ρ=2300,确定迭代次数T的值。迭代次数T与AvgPBM的关系如图5(d)所示。两次迭代后,AvgPBM大幅度减小,第三次迭代后AvgPBM减小幅度较小,所以迭代两次后停止迭代,即T=2。

通过实验,最终确定:N=5,β=0.9,γ=0.3,ρ=2300,T=2。

图 5. 不同参数对平均误差的影响。(a) N;(b) β和γ;(c) ρ;(d) T

Fig. 5. Influences of parameters on AvgPBM. (a) N; (b) β and γ; (c) ρ; (d) T

下载图片 查看所有图片

3.2 算法对比分析

确定参数之后,在Middlebury提供的Tsukuba、Venus、Teddy和 Cones 4组图像上进行测试,并将所提算法与MST^[13]、GF^[12]和GA-DP(Gradient Adaptive-Dynamic Programming)^[5]算法进行对比,如图6所示。从图6中可以看出所提算法在Tsukuba上的视差图效果一般,但是在其他三张视差图上效果较好。

图 6. 实验结果。(a)左图像;(b)真实视差图;(c)所提算法结果;(d) MST算法结果;(e) GF算法结果;(f) GA-DP算法结果

Fig. 6. Experimental results. (a) Left image; (b) ground-truth disparity; (c) result of proposed algorithm; (d) result of MST algorithm; (e) result of GF algorithm; (f) result of GA-DP algorithm

下载图片 查看所有图片

所提算法、MST、GF和GA-DP算法的误匹配率如表1所示。表1中“n-occ”表示非遮挡区域,“all” 表示所有区域,“disc”表示深度不连续区域(遮挡处),AvgDisc表示4组图像在遮挡区域的平均误匹配率。表1中,Gray表示采用所提算法,但是输入图像为灰度图像。从表1中可以看出,当灰度图像作为输入时,比RGB图像作为输入在AvgPBM上高1.47%,在AvgDisc上高2.85%。因此采用灰度图像作为输入时,效果比RGB图像作为输入要差。所提算法的AvgPBM比MST、GF和GA-DP算法的分别低0.49%、0.56%和1.11%。但是所提算法在Tsukuba上的n-occ和all区域的误匹配率较高,Tsukuba图像匹配错误的地方集中在无纹理和弱纹理区域,因此所提算法在无纹理和弱纹理区域容易出现误匹配。所提算法的AvgDisc比MST、GF和GA-DP算法的分别低0.72%、1.06%和1.44%。可见所提算法的AvgPBM和AvgDisc较低。

为全面地测试算法性能,对Middlebury提供的31组图像上进行测试,测试结果如表2所示。表2中数字下标表示各个算法匹配精度的排名,AvgErr表示算法在n-occ区域的平均误匹配率, AvgRank表示算法的平均排名。在表2中,灰度图像作为输入比直接输入RGB图像的AvgErr高1.32%,但是比MST算法低0.49%,因此得出所提算法可以用灰度图像作为输入的结论。所提算法在Midd1、Midd2、Monopoly、Plastic和Reindeer的误匹配率比较高,是因为这5幅图像中有大量无纹理和弱纹理区域。但是所提算法的AvgErr分别比GF、CS-MST和MST低0.83%、1.02%和1.81%。在4种算法中,所提算法的平均排名为1.87,排名高于其他三种算法。

4 结论

提出一种基于图像分割的稠密立体匹配算法。首先提出基于超像素边缘的匹配代价融合计算方法,为后面迭代提供良好的初始视差图。经过基于视差图和超像素的匹配代价更新、GF滤波和视差后处理循环迭代后,视差图的误匹配率有所降低。实验结果表明所提算法具有较低的平均误匹配率和较低的遮挡处误匹配率,但是在无纹理和弱纹理区域的匹配精度有待提高。

后续研究方向包括:1)继续研究匹配代价计算方法的融合;2)研究图像分割算法与立体匹配算法相结合的方法;3)对于无纹理区域,所提算法的错误率较高,后续工作着重解决无纹理区域的误匹配问题。