基于像素类别优化的PatchMatch立体匹配算法

高雅昆; 刘涛; 李海滨; 张文明

doi:doi:10.3788/AOS201939.0715006

光学学报, 2019, 39 (7): 0715006, 网络出版: 2019-07-16

基于像素类别优化的PatchMatch立体匹配算法下载： 1049次

Stereo Matching Algorithm Based on Pixel Category Optimized PatchMatch

论文大纲

高雅昆刘涛李海滨 ^*张文明

作者单位

燕山大学工业计算机控制工程河北省重点实验室, 河北秦皇岛 066004

机器视觉立体匹配算法 PatchMatch 像素分类视差优化 machine vision stereo matching algorithm PatchMatch pixel category disparity refinement

AI 词云图 AI一句话精读 AI短摘要

注：本部分内容由 AI 自动生成，请您知悉。

摘要

基于PatchMatch(同时估计像素点的视差和法向量的3D标签)的方案已经在立体匹配中取得高精度的亚像素视差,但该类方法无法有效解决图像无纹理区域的错误匹配。针对这一问题,对LocalExp(local expansion move)算法进行了改进,并提出一种融合多维信息的自适应像素类别优化的立体匹配算法。该方法设计了一种交叉窗口,在窗口内基于颜色与颜色的自相关信息构建相关权重,并利用约束函数剔除匹配代价中的离群值;在PatchMatch的标签初始化阶段增加约束机制,改进视差标签的建议生成机制,并利用基于局部扩张运动的优化方法求解标签值;利用基于像素类别的填充策略进行视差优化。实验结果表明所提算法能够在Middlebury数据集上取得较低的匹配误差。

Abstract

PatchMatch-based algorithms that simultaneously estimate the disparities and normal unit of a disparity plane have achieved highly accurate sub-pixel disparities in the stereo matching problem; however, this kind of methods can not effectively deal with error matching in the non-texture regions of image. To solve this problem, we improve the LocalExp(local expansion move)algorithm and present a new stereo matching algorithm integrating multidimensional information for adaptive pixel category optimization. First, a crossover window is designed,the color and color self-correlation information in the window are used to establish the weight, and the restrained function is utilized to eliminate the outliers in the matching cost. Second,the constraint mechanism is added to the label initialization procedure, the proposal generation mechanism is modified, and the local expansion movement algorithm is used to optimize the label values. Finally, the pixel category information-based filling strategy is used to refine the disparity. The experimental results show that the proposed method can obtain a low matching error on the Middlebury dataset.

1 引言

双目立体匹配技术作为三维重建研究领域的核心技术之一,已广泛应用于无人驾驶、机器人导航定位、增强/虚拟现实、物体识别与跟踪、地理信息系统(GIS)等领域^[1]。在正向平行表面的视差一致性假设下(窗口内视差相等),对于在斜面及曲面区域的视差计算,传统匹配算法会产生阶梯效应。针对这一问题,Bleyer等^[2]提出了基于3D标签的倾斜窗口假设(窗口内视差值存在渐变),利用PatchMatch(patch match)^[3]算法中图像修复的思想来解决立体匹配中视差问题,通过对像素点3D标签分别进行随机初始化、邻域传播、左右视图传播、随机搜索以及平面细化等来估计视差,并将该方法称为PMS(patch match stereo)。3D标签相对于单一视差值,增加了像素点的切平面法向量信息,更能表征像素点所在平面的空间信息。但采用PatchMatch算法进行立体匹配时存在以下问题:1)随机对每个像素点进行参数初始化,初始化过程并不能保证每个像素都有一个几何意义下可行的视差平面参数;2)平面细化过程使用Luus和Jaakola^[4]提出的优化方法来最小化代价函数,并不能保证找到代价的局部最小值;3)受代价函数或能量函数的限制,该方法不能有效解决弱或无纹理区域的错误匹配。

不同学者针对这些问题提出了不同的立体匹配解决方案。Besse等^[5]将PMS算法和粒子置信传播算法整合到统一的结构下,提出了一种基于置信传播BP(belief propagation)的加速全局立体匹配算法(PMBP)。该方法在BP框架下将粒子采样标签更新和PatchMatch算法的邻域传播相融合解决了连续性标签处理问题。同时,该方法在PMS算法的代价函数基础上,考虑邻域平面的平滑项约束构造能量函数,得到了比PMS算法更准确的视差,但BP作为优化算法会陷入局部极小值。Lu等^[6]提出的PMF(patch match filter)算法采用超像素作为匹配单元代替PMS算法中的固定尺寸窗口,在代价函数中引入由粗到精的尺度一致性约束关系以缓解无纹理区域中的错误匹配,并通过在PMS标签搜索策略中增加一种有效的超像素相似性计算方案来搜索候选标签。该方法比PMS算法的运行速度快,但在能量函数中无正则化约束视差平滑变化。Heise等^[7]提出的PM-huber算法将PatchMatch随机搜索环节同Huber算子约束的显式变分平滑方法相结合,构建能量函数的视差约束平滑项,并在PMS视差标签初始化时,根据经验限定标签取值范围,该方案相对于PMF能获得较好的精度。Li等^[8]提出的PMSC(PatchMatch-based superpixel cut)算法步骤为:1)利用超像素单元构建顶层匹配代价,以Žbontar等^[9]提出的卷积神经网络(CNN)方法计算得到的像素块相似度作为底层代价,并将两层代价进行组合以构建匹配能量函数,同时将基于曲率的二阶平滑项用于视差平滑;2)在视差优化过程中,在超像素间使用PatchMatch算法更新当前超像素区域标签,在超像素内利用GC(graph cut)^[10]优化每一像素点的最优标签值;3)融合超像素块标签和像素点标签以获得最终视差图。由于利用GC算法在节点间的优化可同步改善连接节点状态,因此该方案可有效地减少图像在弱/无纹理区域的误匹配。不同于PMSC算法,Li等^[11]提出的3DMST(3D minimum spanning tree)匹配方案的步骤为:1)采用分割树分割^[12]代替超像素分割,将图像分成多个最小生成树图结构;2)使用Yang^[13]提出的代价聚合方法计算每个MST上像素点的匹配代价值;3)基于PatchMatch算法优化每个MST标签状态,并求解像素点标签。该方案进一步降低了图像在无纹理区域的匹配错误率。Taniai等^[14]提出的局部扩展移动优化算法LocalExp与PMSC、3DMST算法的整体思想相似,但存在几点区别:1)构造由小到大的多尺寸规则窗口金字塔模型,在不同尺寸的窗口内计算匹配代价,进行标签传播;2)针对每一个窗口单元构造扩散区域用于PatchMatch的空间传播,构造滤波区域用于基于快速代价滤波的代价聚合方法中,求取粗略视差值;3)利用GC优化更新细化局部窗口内像素点的标签。目前该方法的结果在Middlebury网站上排名前列。

虽然上述匹配算法针对PatchMatch算法的局限性给出了不同的解决方法,但这些方法仍不能较好地解决图像中无纹理和弱纹理区域的误匹配问题。针对这一问题,本文基于LocalExp算法提出了一种新的基于像素分类的立体匹配解决方案。

2 基本原理

LocalExp算法的流程如下:1)随机初始化图像的3D标签图,为每个像素点p(p_x,p_y)随机分配单位表面法向量n_p(n_x,n_y,n_z)和随机视差z,用于像素点所在参数平面L_p(a_p,b_p,c_p)的初始化,其转换关系为a_p=-n_x/n_z,b_p=-n_y/n_z,c_p=-(n_xp_x+n_yp_y+n_zz)/n_z,其中p_x,p_y为像素点p的坐标分量,n_x,n_y,n_z为像素点p的3D单位法向量分量,a_p,b_p,c_p为点p所在视差参数平面系数;2)使用3种不同尺寸的窗口构建局部窗口,并将其作为优化单元,利用颜色和梯度信息计算各窗口中像素点在当前标签下的匹配代价;3)利用PatchMatch算法在不同窗口之间进行3D视差标签传播以搜寻最优标签;4)基于GC算法优化窗口内像素点的标签。

图1给出LocalExp算法和本文改进的算法内容,其中黑色字体为LocalExp算法的结构图,而黑色加粗字体为本文改进的环节,图中K_s、K_b为窗口分组数量。具体改进内容如下。

图 1. 算法内容细节对比

Fig. 1. Detail comparison of algorithm content

下载图片查看所有图片

1) 提出一种能够提取更多局部窗口用于计算像素点匹配代价和共享标签的交叉窗口模型,将颜色内相关性信息作为权重构建因素,在局部窗口内对匹配代价进行多维权重滤波运算,构建能量函数;同时,用Geman-McClure函数^[15]代替传统的截断函数处理异常值,以保证初始代价值的稳定与平滑。

2) 采用具有约束信息的视差标签初始化方法(IPMS),使初始化视差标签值更合理有效。

3) 根据像素分类信息改进LocalExp算法标签建议机制,即在迭代过程中通过多种机制生成候选标签集合用于迭代更新视差标签。

4) 在像素点视差值优化处理方面,设计了一种基于像素分类的视差优化方法,利用交叉线搜索同标签下可靠的视差标签对图像弱纹理和无纹理区域中的视差误匹配点进行错误填充;采用最近邻域填充方法对边缘、纹理区域以及遮挡区域中的错误点进行填充。

2.1 多维权重能量函数

利用在PairwiseMRF模型下定义的最小化能量函数来估计像素点的3D视差标签。能量函数表达式为

E (L) = \sum_{p \in Ω} ϕ_{p} (L_{p}) + λ \sum_{(p, q) \in N_{4}} φ_{pq} (L_{p}, L_{q}), (1)

式中:Ω为像素点集合;λ为平滑系数;N₄为四邻域关系;L为3D标签量集合;ϕ_p(L_p) 为像素点p的数据项;φ_pq(L_p,L_q)为像素点p、q间的平滑项,其中L_p为像素点p的3D标签值,L_q为像素点q的3D标签值,p为窗口中心像素点,q代表窗口中的其他像素点。ϕ_p(L_p)用于计算匹配像素间相似度的数据项,可表示为

ϕ_{p} (L_{p}) = \frac{1}{Z_{p}} \sum_{q \in W_{p}} ω_{pq} Γ (q, L_{p}), (2)

式中:Γ(q,L_p)为像素点q的标签值为L_p(a_p,b_p,c_p)时,以p为中心的窗口内的像素点q与待匹配图对应点q^*的匹配代价值;W_p为以点p为中心的滤波窗口;Z_p为权重归一化参数;ω_pq为权重,可表示为

ω_{pq} = \frac{1}{| W^{2} |} \cdot \sum_{(p, q) \in W_{k}} [I + (I_{p} - μ_{k})^{T} \cdot (Σ_{k} {+ e)}^{- 1} (I_{q} - μ_{k})] 。 (3)

其中μ_k、Σ_k、e分别为局部窗口W_k内的颜色均值、协方差和避免过拟合的矩阵^[16];W为窗口尺寸;I_p为p的颜色向量;I_q为q的颜色向量。

利用由颜色分量、图像水平和垂直梯度分量组合的相似度函数Γ(q,L_p)计算像素点间的匹配代价。多代价值融合的策略对一些变化区域的匹配精度有小幅度提升,并且能够在边缘处得到更加准确和平滑的视差图。

由颜色分量、图像水平和垂直梯度分量组合的相似度函数Γ(q,L_p)可表示为

Γ (q, L_{p}) = (1 - α) G_{col} (‖ I_{q} - I_{q^{*}} ‖_{1}, τ_{col}) + 0.5 α [G_{grad x} (‖ \nabla_{x} I_{q} - \nabla_{x} I_{q^{*}} ‖_{1}, τ_{grad x}) + G_{grad y} (‖ \nabla_{y} I_{q} - \nabla_{y} I_{q^{*}} ‖_{1}, τ_{grad y})], (4)

式中: $\nabla_{x}$ I表示灰度图像在梯度算子滤波处理后水平方向灰度梯度; $\nabla_{y}$ I为垂直方向灰度梯度;G_col为像素点颜色信息的约束函数;G_grad_x为水平方向梯度约束函数;G_grad_y为垂直方向梯度约束函数;τ_col、τ_grad_x、τ_grad_y分别表示匹配代价的不同分量的调节参数;α为比例因子。在(4)式中,可以通过预定义参数τ调整异常值控制范围,如图2所示,原始代价c经过变化后趋于稳定、平滑。LocalExp在匹配代价计算中用线性截断处理异常点代价值,而本文用

G (c, τ) = \frac{c^{2}}{c^{2} + τ^{2}} (5)

表示的约束函数替代线性截断函数,当代价值c超过某值时,函数的输出将平滑下降。

图 2. Geman-McClure函数不同参数对比曲线

Fig. 2. Comparison curves for different parameters of Geman-McClure function

下载图片查看所有图片

能量函数中用于约束视差变化的平滑项φ_pq(L_p,L_q)由Olsson等^[17]提出的二阶曲率正则化约束关系表示为

φ_{pq} (L_{p}, L_{q}) = \max (ω_{pq}^{*}, ε) \min [ψ (L_{p}, L_{q}), ε_{dis}], (6)

式中: $ω_{pq}^{*}$ 代表平滑项的权重;ψ(L_p,L_q)为视差惩罚函数;ε为下限值,能够减小权重受噪声的影响;ε_dis为最大视差跳变量。

相对于LocalExp,本文将颜色内相关性分量I_Cn和颜色分量作为平滑项的权重 $ω_{pq}^{*}$ 组合,组合后的权重关系反映了色彩内部的一些特征,更能表征出相邻像素颜色的一致性和差异性。I_Cn和 $ω_{pq}^{*}$ 可分别表示为

\begin{array}{l} I_{Cn} (p) = [{I^{r}}_{n} (p) - {I^{g}}_{n} (p), {I^{g}}_{n} (p) - {I^{b}}_{n} (p), {I^{b}}_{n} (p) - {I^{r}}_{n} (p)], (7) \\ ω_{pq}^{*} = \exp {- {β [‖ I_{n} (p) - I_{n} (q) ‖_{1} / γ_{n}] - (1 - β) [‖ I_{Cn} (p) - I_{Cn} (q) ‖_{1} / γ_{cn}]}}, (8) \end{array}

式中: ${I^{r}}_{n}$ (p)、 ${I^{g}}_{n}$ (p)、 ${I^{b}}_{n}$ (p)为像素点p的RGB(red-green-blue)强度值;(p,q)∈N₄,N₄为4邻域;β为组合因子;γ_n,γ_cn为颜色相似计算的参数。平滑项中的视差惩罚函数表达式为

ψ (L_{p}, L_{q}) = | d_{p} (L_{p}) - d_{p} (L_{q}) | - | d_{q} (L_{q}) - d_{q} (L_{p}) |, (9)

式中:d_q(L_p)=a_pq_x+b_pq_y+c_p为像素点q在L_p标签下的视差值。函数ψ(L_p,L_q)用于惩罚邻域像素点(p,q)∈N₄分别在标签L_p,L_q下视差的不连续性。由于平滑项函数满足GC算法中子模块能量优化条件,即

ψ (α^{1}, α^{1}) + ψ (β^{1}, γ^{1}) \leq ψ (α^{1}, β^{1}) + ψ (α^{1}, γ^{1}), (10)

式中:α¹,β¹,γ¹为3D视差平面参数,因此可根据GC算法最小化能量函数,获取标签值,(10)式的详细证明可参考文献[ 14]。

2.2 局部优化窗口模型

2.2.1 交叉窗口

在LocalExp中设定网格大小将图像分割成网格区域C_ij∈Ω,下标(i,j)∈Z²代表其网格单元坐标,Z为整数集。LocalExp中采用3种不同尺寸(5×5,10×10,25×25)的网格大小构建图像金字塔模型来平衡PM算法中的随机搜索和局部传播的互相影响。为了实现算法加速,对多匹配单元进行并行优化处理,规定了一种互不相交的局部区域窗口分组方法,图像的网格分组数K=6×(jmod 6)+(imod 6),如图3(a)所示为K=36分组后的图像细胞索引图。针对每个网格单元定义三个区域用于视差计算,图3(b)中标号12的白色网格单元为中心区域C_ij,相连的灰色单元为扩张区域R_ij=C_ij $\cup_{(}^{m}$ C_mn,其中m、n表示细胞单元C的横轴坐标。

图 3. 分组索引。(a)图像细胞索引分组;(b)局部扩张区域

Fig. 3. Grouping index. (a) Image cell index groups; (b) locally extended region

下载图片查看所有图片

受局部立体匹配中多窗口和自适应窗口思想的启发,提出一种交叉窗口模型以获取更多局部特性窗口。相对于LocalExp的窗口模型,本文模型中心窗口的滑动距离小于细胞单元尺寸大小,即保留相连细胞单元的部分区域作为新细胞的中心区域。新中心区域与原细胞区域存在局部信息交叉,故称交叉窗口。图4(a)中给出了同分组下的两种窗口模型(交叉窗口为半个细胞单元移动长度)单元标号结果。交叉窗口结构能够产生更多的窗口去捕捉局部信息,每一个像素能够被分配更多的标签求取代价,因此更有利于获取最优标签。图4(b)中M_ij= $\cup_{p}^{\in}$ W_p,表示为中心区域C_ij的滤波区域。图5给出两种窗口模型在5次实验后的平均错误率结果对比,相比于LocalExp,本文方法的平均匹配准确率明显提高。

图 4. 交叉窗口。(a)不同分组的扩展区域;(b)局部图像区域

Fig. 4. Cross windows. (a) Expansion regions for different groups; (b) local image region

下载图片查看所有图片

图 5. 交叉窗口与原窗口方案在测试图像上的错误匹配率

Fig. 5. Error matching rates of cross window and original method on test images

下载图片查看所有图片

2.2.2 窗口标签初始化

基于PatchMatch算法的匹配算法流程如下:1)初始化窗口内像素点标签;2)在每次迭代过程中,在窗口间对标签进行空间传播和随机搜索,通过判断窗口在当前标签下的能量函数增减性来改变窗口内像素的视差分布。算法迭代收敛速度取决于初始化过程的随机3D标签,随机数值越可靠,算法收敛速度越快。所以,初始化阶段是重要组成部分。本文替换LocalExp中视差标签初始化方式,采用Ahmed等^[18]提出的增加约束原则的PatchMatch推理方法IPMS,该方法建立窗口内的像素点所在视差平面法向量、视差范围以及窗口内视差分布关系,给出可靠的初始化标签以加速收敛速度。

IPMS中给出了两种初始化约束手段:

1) 左右视图下视差可见性约束原则。根据射影变换关系

n' = \frac{M^{- T} n}{‖ M^{- T} n ‖}, (11)

建立左视图I₀法向量n=(n_x,n_y,n_z)和右视图I₁法向量n'=(n'_x,n'_y,n'_z)的转换关系M,M= $(\begin{array}{l} 1 & 0 & - 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array})$ ,得到任意像素点p的n=(n_x,n_y,n_z)中变量的限制关系为n_z>0,n_x<n_z。

2) 在窗口内的视差约束。基于中心点p(x_p,y_p)的半径为r的窗口内q(x_q,y_q)的视差d_q满足

d_{q} = \frac{n_{x}}{n_{z}} (x_{p} - x_{q}) + \frac{n_{y}}{n_{z}} (y_{p} - y_{q}) + d_{p}, (12)

式中:d_p为像素点p的视差值。窗口内任意像素点q的视差范围为[d_min,d_max]及其与中心像素p的坐标差绝对值范围可分别表示为

\{\begin{array}{l} d_{q \in w_{p}} = {d_{m in}, d_{\max}} \\ | x_{q} - x_{p} | \leq r, | y_{q} - y_{p} | \leq r \end{array}, (13)

将(13)式代入(12)式中可得

- n_{z} (d_{p} - d_{\min}) \leq n_{x} (x_{p} - x_{q}) - n_{y} (y_{p} - y_{q}) \leq n_{z} (d_{\max} - d_{p}), (14)

式中:d_min为最小视差值;d_max为最大视差值。d^*为d_p与d_min和d_max差值中的最小值,满足

\begin{array}{l} d^{*} = \min (d_{p} - d_{\min}, d_{\max} - d_{p}), (15) \\ - n_{z} \cdot d^{*} \leq n_{x} \cdot r \pm n_{y} \cdot r \leq n_{z} \cdot d^{*} 。 (16) \end{array}

求解(12) ~(16)式可得

\begin{array}{l} - \frac{n_{z}}{r + d^{*}} d^{*} \leq n_{x} \leq \frac{n_{z}}{r} d^{*}, if p \in I_{0}, (17) \\ - \frac{n_{z}}{r} d^{*} \leq n_{x} \leq \frac{n_{z}}{r + d^{*}} d^{*}, if p \in I_{1}, (18) \end{array}

即获取左视图像素点n_x的上下边界。最后利用法向量在窗口内部的视差平面关系求解不等式[(16)式],得到左视图n_y的取值范围为

n_{y} \in \frac{s}{r} [- 1,1], where s = \{\begin{array}{l} \min [| n_{z} d^{*} + n_{x} r |, | (n_{z} + n_{x}) d^{*} + n_{x} r |], if p \in I_{0} \\ \min [| n_{z} d^{*} + n_{x} r |, | (n_{z} - n_{x}) d^{*} + n_{x} r |], if p \in I_{1} \end{array}, (19)

式中:I₀为参考图;I₁为待匹配图;s为约束因子。通过上述约束条件得到的单位法向量(n_x,n_y,n_z)取值范围可在初始化3D标签时控制异常3D标签的产生,只保留满足(17) ~(19)式以及n_z>0,n_x<n_z的标签值。该方案对单位法向量进行多次采样,直到满足约束条件,增加了正确估计像素点3D平面参数的概率。

2.3 基于像素类型的迭代优化

2.3.1 像素分类器

像素分类器由Meanshift分类器 ${^{[}}^{19}^{]}$ 、SNIC(simple non-iterative clustering)^[20]分类器、LRC(left right consistency)分类器以及纹理分类器4部分构成。其中Meanshift分类器利用颜色概率密度分布聚类颜色相似的像素点,有很好的全局特性,但颜色渐变小的区域分离效果不佳,如图6(b)方框中局部分割标签图所示,SNIC分类器对分割区域具有更好的局部特性,能够弥补Meanshift分割的单纯聚类方法缺点,如图6(c)中方框区域所示。纹理分类器可表示为

T (p) = \{\begin{array}{l} 0, & n \geq 0.75 \times N \times N \\ 1, & else \end{array}, (20)

式中:n为像素点个数;N为窗口半径。其原理是依据权重计算公式[(8)式]计算中心像素点与在半径为N的窗口内其他点的相似度大小,后累计相似度值满足大于0.8的像素点个数n,将大于设定阈值个数的像素点记作无纹理区域点,反之为弱纹理点。图6(d)给出输入图像的像素纹理性质分类结果,黑色代表有纹理点,白色代表无纹理点。LRC分类器可表示为

LRC (p) = \{\begin{array}{l} 1, & D_{0} (p) - D_{1} (p) < 1 \\ 0, & else \end{array}, (21)

式中:D₀为参考图视差图;D₁为待匹配图的视差图。(21)式用于分离视差图中的稳定点(1)和不稳定点(0)。以上几种像素点的分类方法所得结果可作为本文构建PatchMatch优化算法所需候选标签集生成和错误点视差优化的先验知识。

图 6. 多分类信息图。(a) Plastic;(b) Meanshift;(c) SNIC;(d)纹理结构图

Fig. 6. Multi-category graphs. (a) Plastic; (b) Meanshift; (c) SNIC; (d) texture structure graph

下载图片查看所有图片

2.3.2 基于像素分割类的标签生成机制

利用2.3.1节的Meanshift和SNIC像素分类先验知识和PatchMatch算法优化原理,改进了LocalExp算法的标签生成机制:

1) 传播机制。在局部窗口的中心区域的对角线上选取1~2个像素点的3D标签,加入更新候选标签集合。

2) 局部最优标签机制。利用局部随机一致性算法(LO-RANSAC)^[21]拟合局部最优视差平面参数,并将该参数加入到候选标签集合中。

3) 基于像素分类的标签机制。在像素分类集合S中构造同名像素点集合,并在其中随机选取一定数量的样本点用于LO-RANSAC拟合新标签,并加入候选标签集合中。

4) 视图传播机制。选取在其他视图下对应区域的有效视差标签加入到候选标签集合中。

5) 随机扰动细化机制。对当前窗口内选取的一个标签量增加归一化的扰动量,细化标签值,直至扰动量足够小,并将扰动标签加入候选标签集合中。

图7是采用上述标签生成机制后,基于PatchMatch和GC优化算法的求解视差的算法流程。针对每个图像细胞单元,首先构建候选标签集合S_et(α_ij),选取集合中最小化能量函数的标签L'_p作为更新像素点的标签值。最小化能量函数表达式为

L^{l + 1} = \underset{L'}{argmin} E [L'| L'_{p} \in S_{et} (α_{ij})], (22)

式中:l为迭代次数;L'为最小化能量函数的标签集合;E为能量函数。

图8对比了改进标签生成机制和原方法在一次迭代后的错误率,结果表明,相对于LocalExp,本文方法的错误率更低。

图 7. 改进的局部扩张运动算法

Fig. 7. Improved local expansion movement algorithm

下载图片查看所有图片

图 8. 对比改进标签生成机制和原方法在一次迭代后的错误率

Fig. 8. Comparison of error rates between improved generation mechanism and the original method in one iteration

下载图片查看所有图片

2.3.3 基于像素分割、纹理及一致性分类的视差优化

从图8对比实验结果可知,虽然误匹配率相对于原算法有所降低,但仍较高。为此,采用一种基于像素分类信息的填充方法进一步优化视差。首先通过LRC分类器分离不稳定点,其次,依据纹理分类器对有纹理和无纹理区域的不稳定点分别进行处理。

图9(a)表示位于纹理区域像素点的最近邻域填充方法。以图中标号5的不稳定更新为例,分别向左和向右找到第1个位于像素分类器中同分割区域的稳定点。为了避免前景膨胀,将稳定点中使错误点视差更小的标签值赋予该点。图像中无/弱纹理区域一般结构简单且对称,为了有效扩大搜集范围并获得更多的稳定视差点,如图9(b)所示,采用横竖方向的交叉线法提取一定数目的稳定点作为权重中值滤波像素点集合,用于优化错误点。该方法在当前错误像素点上下左右衍生一定范围以提取稳定点,在各方向选取平均化个数的稳定点以防止选取过多的不同区域点,通过累计稳定点个数自适应控制衍生搜索的臂长大小。最后采用权重中值选取标签用于更新无/弱纹理区域的不稳定点视差标签值。

图10是所提方法和LocalExp算法经过4次迭代视差优化的视差变化过程图。图10(a)为LocalExp运行结果图,其中方框1,2,3代表三个不同区域,图中的黑色点代表视差匹配错误点。在迭代过程中,方框1中部分点可在LocalExp算法迭代优化后得到正确的视差值,对于方框2,3中的像素点,由于能量函数陷入局部最小值且传统的视差优化手段对于陷入局部最小值的区域无法有效进行滤波处理,因此得到的视差标签图失效。图10(b)是所提方法的迭代过程图。从图中黑色点数目可知,在初始状态下和迭代过程中,错误区域误匹配率不断降低,最终获得较准确的视差图。

图 9. 填充方法。(a)纹理区域;(b)弱纹理分区域。红色为稳定点,黑色为不稳定点,白色为剔除点

Fig. 9. Filling methods. (a) Texture region; (b) texture-less region. Red regions represent stable points, black regions represent unstable points, and white regions represent culling points

下载图片查看所有图片

图 10. 迭代优化过程。(a) LocalExp;(b)提出的算法

Fig. 10. Iterative optimization process. (a) LocalExp; (b) proposed algorithm

下载图片查看所有图片

2.4 算法流程

图11是本文算法流程图,其中圆1代表算法初始化环节,即完成IPMS算法中的视差标签初始化和构建像素分类器用于算法迭代优化与视差优化;圆2为算法迭代优化环节,即对于每个局部窗口单元采用基于本文改进的标签生成机制的局部扩张运动算法来估计像素点视差;圆3代表满足迭代终止后的输出视差图,左下角为算法中数据流动图例说明。

图12给出本文算法优化流程说明。1)算法初始化:行1~5分别是2.2~2.3节中阐述的多层窗口模型尺寸大小、利用meanshift、SNIC和纹理分类器T(p)构建原始像素点分类集合S、迭代优化算法1中的propagation、optional和refinement更新次数以及其他的实验参数设定。2)算法迭代循环:行8~9表示从窗口尺寸集合G={10×10, 20×20, 35×35}从小到大选取窗口大小执行2.2.1节中阐述的交叉窗口模型和2.2.2节的IPMS算法初始化(该标签初始化算法只在首次迭代中执行,其余迭代过程中视差标签从上次迭代结果选取)。行11代表同组号窗口并行执行Algorithm 1-局部扩张运动算法迭代更新各自窗口内像素点的标签值,其中Δ={Δ'_d,Δ'_n}为视差和法向量的扰动量,用于细化视差标签^[14]。行14表示在一次迭代后,采用2.3.3节提出的方法进行错误点视差填充;行16处表示在一次窗口尺寸迭代完成后,缩小扰动范围Δ来改变视差标签细化精度。行17为迭代优化算法停止。行18执行后处理方法^[14],以进一步提高视差精度。

图 11. 本文算法流程图

Fig. 11. Flow chart of proposed algorithm

下载图片查看所有图片

图 12. 本文算法优化进程

Fig. 12. Optimization procedure of our algorithm

下载图片查看所有图片

3 实验结果及分析

实验环境为:Windows 7,64位系统,Intel(R) Core(TM)i5-3210M,CPU主频为2.50 GHz,4核,内存为8 GB。为了验证本文算法对无/弱纹理区域的适用性与准确性以及纹理丰富区域的通用性,实验数据采用Middlebury大学的立体视觉数据库中Midd2003 Datasets、Midd2006 Datasets。该数据集含有真实的视差数据,可用于衡量算法的误差精度,以及有效验证算法的正确性。本文实验参数为ε=0.01,ε_dis=0.8,N=5,γ_n=γ_cn=10,τ_col=0.2,τ_grad_x=τ_grad_y=0.7,λ=7,α=0.7,R=20,β=0.4。

图13中列出基于PatchMatch优化的匹配算法^[5,14,22-23]和本文提出的算法在Midd2006数据集中存在大片无纹理区域的4组测试图像Flowerpots、Bowling2、Midd1、Plastic的视差图可视化结果,其中红色点代表视差错误大于1 pixel的点。从图13可知,在采用没有结合CNN代价作为匹配代价的PatchMatch优化的全局匹配算法PMBP^[5]、LocalExp^[14]、SPM-BP^[22]和GCLSL^[23]得到的视差图中,出现了大量错误点。得益于可靠的初始化标签值和基于像素分类的迭代计算和视差优化,本文算法在任何一个测试图像上的实验效果都不存在较大区域的错误点。PMSC^[7]由于利用CNN作为匹配代价进行计算,获得了较好的实验效果,但其需要通过数据集驱动来训练深度网络结构并计算初始匹配代价值。相比之下,本文算法未采用CNN网格模型却取得与PMSC接近的视觉效果,在弱纹理区域的结果甚至更优。

图 13. 几种全局PatchMatch算法的视差图(匹配错误率大于1 pixel的点用红色显示)。(a) Image;(b) PMBP;(c) SPM-BP;(d) GCLSL;(e) PMSC;(f) LocalExp;(g) proposed

Fig. 13. Disparities of some global PatchMatch algorithms (points with error matching rate greater than 1 pixel are shown in red). (a) Image; (b) PMBP; (c) SPM-BP; (d) GCLSL; (e) PMSC; (f) LocalExp; (g) proposed

下载图片查看所有图片

表1中给出几种基于PatchMatch优化思想的全局匹配算法在Midd2006数据集典型图像中评价结果,其数值为图像中非遮挡区域的像素点视差错误值大于1 pixel的误匹配率结果。从表1中可知,本文算法取得了最低的平均误匹配率2.59%,相对LocalExp算法的平均误匹配率(11.66%),在所有测试的图像中,只有Rocks图像的误匹配率高于LocalExp。本文算法在纹理较为丰富的测试图像Cloth1、Cloth4中获得的最低错误匹配率分别为0.59%和0.89%,且在有无/弱纹理区域的Midd1、Plastic图像中,取得最低的误匹配率,在所有存在无纹理区域的图像中都取得较低的误匹配率。

表 1. 几种基于PatchMatch优化的匹配算法在Midd2006数据集中非遮挡区域的匹配结果(阈值为1 pixel,最好的实验结果用粗体显示)

Table 1. Matching results of some PatchMatch based stereo algorithms in Midd2006 datasets with nonocc regions (threshold is 1 pixel, and the best results are shown in bold)

Image	PMBP	SPMBP	GCLSL	PMSC	LocalExp	Proposed
Aloe	4.51	6.75	3.21	3.06	3.92	3.25
Baby1	4.10	3.27	2.21	1.98	2.74	1.34
Baby2	4.77	3.97	2.08	1.05	5.48	1.41
Baby3	4.77	3.92	3.07	3.12	6.56	2.73
Bowling1	14.10	12.10	4.14	2.06	5.37	2.46
Bowling2	4.64	5.27	2.19	1.45	6.44	1.99
Cloth1	1.68	1.17	0.71	0.60	0.78	0.59
Cloth4	3.10	2.20	1.75	1.87	0.99	0.98
Flowerpots	9.28	8.80	4.60	2.49	10.89	4.01
Lampshade1	13.50	8.67	12.60	1.50	5.96	2.14
Lampshade2	16.50	17.20	10.00	0.99	21.70	1.08
Midd1	37.40	37.40	34.90	12.80	30.80	6.07
Midd2	38.40	33.20	32.90	4.37	25.60	4.71
Monopoly	42.40	32.70	21.10	3.46	28.04	4.97
Plastic	44.80	35.20	43.90	4.40	40.10	3.34
Rocks1	4.15	2.60	2.19	1.80	1.60	2.34
Wood1	1.52	4.19	0.48	0.73	1.30	0.71
Average	14.68	12.85	10.70	2.80	11.66	2.59

查看所有表

表2是本文算法与LocalExp在测试图像Midd2003中的实验测试结果对比,Rate代表视差图在非遮挡区域(nonocc)、全部区域(all)以及视差不连续区域(disc)的误匹配率。本文算法相对于LocalExp算法在Teddy、Cones上取得更低的误匹配率,由原来的8.153%降低到本文的7.143%。在表2中的测试图像的视差图上框出视差细节对比区域,两种方法中获取视差效果更好的用虚线方框圈出,反之用实线方框圈出。对比方框内的细节可以发现,本文方法在图像Teddy和Cones的disc区域上获得更好的边缘精度,且在非遮挡区域获得更好的平滑视差效果。但对于第1行Tsukuba图像匹配效果较差,因为其局部场景结构性过于复杂、图中存在阴影覆盖的影响以及图像视差变化范围小,所以在三个区域的匹配错误率有小幅度上升。尽管本文算法在图像Tsukuba、Venus上的匹配精度降低,但整体上仍取得与LocalExp接近的平均错误率,LocalExp和本文算法的平均错误率分别为5.97%和6.01%。

表 2. 本文算法与LocalExp在 Midd2003数据集的错误率对比(阈值为0.5 pixel)

Table 2. Comparison of error rates between proposed method and LocalExp on Midd2003 datasets (threshold is 0.5 pixel)

查看所有表

4 结论

提出一种基于像素类别优化的全局匹配算法。与多种相近算法比较,本文算法在Midd2006图像数据集上取得了最低的平均错误匹配率,相对于LocalExp算法降低了9.07%,而且在存在大量无纹理区域图像Midd1、Plastic上取得了最低的误匹配率,实验验证以下结论:本文算法能够有效改善图像中弱纹理和无纹理区域的误匹配问题。但本文算法还存在一些不足:1)利用不同分类方法构建图像中像素点的类别信息,其作为一种人工设计的方法,对不同分割方法的准确性依赖较大;2)由于迭代过程中加入视差优化算法,运行比LocalExp耗时。在接下来的工作中,将研究以深度学习和传统方法相结合的方式获取可靠的全局像素信息,以提升匹配算法精确度并进一步缩短算法的运行时间。

参考文献

[1] 马瑞浩, 朱枫, 吴清潇, 等. 基于图像分割的稠密立体匹配算法[J]. 光学学报, 2019, 39(3): 0315001.

Ma R H, Zhu F, Wu Q X, et al. Dense stereo matching based on image segmentation[J]. Acta Optica Sinica, 2019, 39(3): 0315001.

[2] BleyerM, RhemannC, RotherC. PatchMatch stereo-stereo matching with slanted support windows[C]∥Procedings of the British Machine Vision Conference 2011, August 29-September 1, 2011, Dundee.Durham: BMVA Press, 2011: 14.

[3] Barnes C, Shechtman E, Finkelstein A, et al. PatchMatch: a randomized correspondence algorithm for structural image editing[J]. ACM Transactions on Graphics, 2009, 28(3): 24.

[4] Luus R. Jaakola T H I. Optimization by direct search and systematic reduction of the size of search region[J]. AIChE Journal, 1973, 19(4): 760-766.

[5] Besse F, Rother C, Fitzgibbon A, et al. PMBP: PatchMatch belief propagation for correspondence field estimation[J]. International Journal of Computer Vision, 2014, 110(1): 2-13.

[6] Lu JB, Yang HS, Min DB, et al. Patch match filter: efficient edge-aware filtering meets randomized search for fast correspondence field estimation[C]∥2013 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 23-28, 2013, Portland, OR, USA. New York: IEEE, 2013: 1854- 1861.

[7] HeiseP, KloseS, JensenB, et al. PM-huber: PatchMatch with huber regularization for stereo matching[C]∥2013 IEEE International Conference on Computer Vision (ICCV), December 1-8, 2013, Sydney, NSW, Australia. New York: IEEE, 2013: 2360- 2367.

[8] Li L C, Zhang S L, Yu X, et al. PMSC: PatchMatch-based superpixel cut for accurate stereo matching[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2018, 28(3): 679-692.

[9] Žbontar J. LeCun Y. Stereo matching by training a convolutional neural network to compare image patches[J]. Journal of Machine Learning Research, 2016, 17: 1-32.

[10] Boykov Y, Kolmogorov V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(9): 1124-1137.

[11] Li L C, Yu X, Zhang S L, et al. 3D cost aggregation with multiple minimum spanning trees for stereo matching[J]. Applied Optics, 2017, 56(12): 3411-3420.

[12] Felzenszwalb P F, Huttenlocher D P. Efficient graph-based image segmentation[J]. International Journal of Computer Vision, 2004, 59(2): 167-181.

[13] Yang QX. A non-local cost aggregation method for stereo matching[C]∥2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 16-21, 2012, Providence, RI, USA. New York: IEEE, 2012: 1402- 1409.

[14] Taniai T, Matsushita Y, Sato Y, et al. Continuous 3D label stereo matching using local expansion moves[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018, 40(11): 2725-2739.

[15] Chipot M, March R, Rosati M, et al. Analysis of a nonconvex problem related to signal selective smoothing[J]. Mathematical Models and Methods in Applied Sciences, 1997, 7(3): 313-328.

[16] He K M, Sun J, Tang X O. Guided image filtering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(6): 1397-1409.

[17] OlssonC, UlénJ, BoykovY. In defense of 3D-label stereo[C]∥2013 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 23-28, 2013, Portland, OR, USA. New York: IEEE, 2013: 1730- 1737.

[18] Ahmed S, Hansard M, Cavallaro A. Constrained optimization for plane-based stereo[J]. IEEE Transactions on Image Processing, 2018, 27(8): 3870-3882.

[19] Comaniciu D, Meer P. Mean shift: a robust approach toward feature space analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619.

[20] AchantaR, SüsstrunkS. Superpixels and polygons using simple non-iterative clustering[C]∥2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 21-26, 2017, Honolulu, HI, USA. New York: IEEE, 2017: 4895- 4904.

[21] ChumO, MatasJ, KittlerJ. Locally optimized RANSAC[M] ∥Michaelis B, Krell G. Lecture notes in computer science. Berlin, Heidelberg: Springer, 2003, 2781: 236- 243.

[22] LiY, Min DB, Brown MS, et al. SPM-BP: sped-up PatchMatch belief propagation for continuous MRFs[C]∥2015 IEEE International Conference on Computer Vision (ICCV), December 7-13, 2015, Santiago, Chile. New York: IEEE, 2015: 4006- 4014.

[23] TaniaiT, MatsushitaY, NaemuraT. Graph cut based continuous stereo matching using locally shared labels[C]∥2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 23-28, 2014, Columbus, OH, USA. New York: IEEE, 2014: 1613- 1620.

高雅昆, 刘涛, 李海滨, 张文明. 基于像素类别优化的PatchMatch立体匹配算法[J]. 光学学报, 2019, 39(7): 0715006. Yakun Gao, Tao Liu, Haibin Li, Wenming Zhang. Stereo Matching Algorithm Based on Pixel Category Optimized PatchMatch[J]. Acta Optica Sinica, 2019, 39(7): 0715006.

基于像素类别优化的PatchMatch立体匹配算法 下载： 1049次

1 引言

2 基本原理

图 1. 算法内容细节对比

Fig. 1. Detail comparison of algorithm content

2.1 多维权重能量函数

图 2. Geman-McClure函数不同参数对比曲线

Fig. 2. Comparison curves for different parameters of Geman-McClure function

2.2 局部优化窗口模型

图 3. 分组索引。(a)图像细胞索引分组;(b)局部扩张区域

Fig. 3. Grouping index. (a) Image cell index groups; (b) locally extended region

图 4. 交叉窗口。(a)不同分组的扩展区域;(b)局部图像区域

Fig. 4. Cross windows. (a) Expansion regions for different groups; (b) local image region

图 5. 交叉窗口与原窗口方案在测试图像上的错误匹配率

Fig. 5. Error matching rates of cross window and original method on test images

2.3 基于像素类型的迭代优化

图 6. 多分类信息图。(a) Plastic;(b) Meanshift;(c) SNIC;(d)纹理结构图

Fig. 6. Multi-category graphs. (a) Plastic; (b) Meanshift; (c) SNIC; (d) texture structure graph

图 7. 改进的局部扩张运动算法

Fig. 7. Improved local expansion movement algorithm

图 8. 对比改进标签生成机制和原方法在一次迭代后的错误率

Fig. 8. Comparison of error rates between improved generation mechanism and the original method in one iteration

图 9. 填充方法。(a)纹理区域;(b)弱纹理分区域。红色为稳定点,黑色为不稳定点,白色为剔除点

Fig. 9. Filling methods. (a) Texture region; (b) texture-less region. Red regions represent stable points, black regions represent unstable points, and white regions represent culling points

图 10. 迭代优化过程。(a) LocalExp;(b)提出的算法

Fig. 10. Iterative optimization process. (a) LocalExp; (b) proposed algorithm

2.4 算法流程

图 11. 本文算法流程图

Fig. 11. Flow chart of proposed algorithm

图 12. 本文算法优化进程

Fig. 12. Optimization procedure of our algorithm

3 实验结果及分析

图 13. 几种全局PatchMatch算法的视差图(匹配错误率大于1 pixel的点用红色显示)。(a) Image;(b) PMBP;(c) SPM-BP;(d) GCLSL;(e) PMSC;(f) LocalExp;(g) proposed

Fig. 13. Disparities of some global PatchMatch algorithms (points with error matching rate greater than 1 pixel are shown in red). (a) Image; (b) PMBP; (c) SPM-BP; (d) GCLSL; (e) PMSC; (f) LocalExp; (g) proposed

表 1. 几种基于PatchMatch优化的匹配算法在Midd2006数据集中非遮挡区域的匹配结果(阈值为1 pixel,最好的实验结果用粗体显示)

Table 1. Matching results of some PatchMatch based stereo algorithms in Midd2006 datasets with nonocc regions (threshold is 1 pixel, and the best results are shown in bold)

表 2. 本文算法与LocalExp在 Midd2003数据集的错误率对比(阈值为0.5 pixel)

Table 2. Comparison of error rates between proposed method and LocalExp on Midd2003 datasets (threshold is 0.5 pixel)

4 结论

Article Outline

相关论文

相关资讯

关于本站 Cookie 的使用提示

全站搜索

基于像素类别优化的PatchMatch立体匹配算法下载： 1049次