一种异形自适应窗口局部立体匹配算法

刘 军,苗志勇,张煜祺,任建华

(兰州理工大学机电工程学院,兰州 730050)

随着“中国制造2025”计划的广泛实施,机器视觉中的双目测距[1]、三维重建[2-4]、无人自动驾驶、立体成像及虚拟现实[5]等诸多领域的发展,均需通过图像立体匹配技术高效准确地提供图像景深.而立体匹配算法作为图像立体匹配技术的核心,众多学者进行了很多研究工作.Scharstein等[6]与Affendi等[7]依据计算方法将立体匹配算法分为两大类:全局立体匹配算法和局部立体匹配算法.并且,依据实施阶段将立体匹配算法分为4 大步骤:匹配代价计算、匹配代价聚合、视差左右一致性检查与细化.全局立体匹配算法通过图像对像素的全局约束信息构造能量函数,并使之最小来获得稠密的视差图.而局部立体匹配算法是以待匹配像素为中心的局部窗口内的信息来准确描述待匹配像素,以便在对应图像中准确高效地确定对应点,从而获得视差值.局部立体匹配算法分为窗口形状选择法和自适应权重法.窗口形状选择法以待匹配像素为标准,期望把邻域内与待匹配像素“同等性质”(简称同质)的其他像素引入此窗口,形成可变窗口.“同等性质”的判断标准通常为像素间颜色相似度,大多数此类算法[8-9]只采用灰度值信息.

窗口形状选择法又分为可调节矩形窗口法和自适应形状窗口法.传统可调节矩形窗口法通过设置窗口半径获得固定矩形的待匹配窗口,若窗口半径选择太小,则会在图像低纹理区域内产生很大的匹配误差;若窗口半径选择太大,则容易在窗口中引入过多的“坏像素”,从而在深度不连续区域内产生较大的误差.曾凡志等[10]提出了一种自适应多窗口的立体匹配算法,采用8 个相同的窗口,根据图像的平滑情况从8 个方向选择适当的支撑区域,可有效减小单个窗口带来的匹配误差,但依然未解决窗口半径的选择问题.自适应形状窗口法则避免了上述算法选择窗口半径的难点,通过设置中心像素与非中心像素之间的相似性阈值和最大窗口半径,使窗口形状大小自适应变化.Boykov等[11]提出了一种任意形状窗口匹配算法,利用像素间灰度值差异判断是否为可用像素,虽解决了待匹配窗口形状问题,但确定窗口过程的时间复杂度较高,且获得的窗口可靠度较低.Men等[12]提出了像素扩展自适应窗口匹配算法,类似于十字交叉窗口匹配算法,以待匹配像素为原点沿一个方向搜索像素形成像素带,然后搜索像素带上与之垂直方向上的像素形成待匹配窗口.该算法虽使窗口内无“坏像素”,提高了窗口可靠度与立体匹配精度,但不足之处在于仍没有解决窗口无法贴合某些复杂图像边界的问题,还相应提高了算法时间复杂度.

基于以上窗口形状选择法存在的问题,本工作提出一种异形自适应窗口局部立体匹配技术.为使后期自适应窗口只选择当前特定区域像素,采用引导滤波算法[13-14]对待匹配图像进行预处理,平滑其非边缘区域信息,保持边缘信息;为解决传统自适应窗口形状过于单一的问题,采用结合了预处理图像CIELab 颜色空间信息和灰度值信息的双螺旋搜索路径法,来获得对复杂图像边界具有较好贴合性、较强描述性,以及可有效提高匹配精度的异形自适应匹配窗口.这种方法不仅可以有效遍历待匹配像素周围像素,生成比传统方法更加多变的、贴合复杂轮廓的窗口形状,如“X”或“S”形,还可以由顺、逆时针两条路径生成匹配窗口,提高窗口成形效率.另外,单一的匹配代价计算方式准确性较低,会直接影响视差值精度,为此使用传统的Census 变换和本工作提出的像素信息三维化处理技术进行匹配代价计算.像素信息三维化处理技术是通过将待匹配图像的像素值与像素坐标样条插值获得两个像素曲面,并投影求得体积差,从而获得窗口内其余像素信息和窗口间像素信息.这种匹配代价计算方法可以有效结合Census 变换对光照失真鲁棒性强的优点,同时又可以降低窗口内像素变化对窗口整体信息的影响,克服窗口中心像素对Census 变换干扰较强的缺点.最后对获得的匹配代价与异形自适应窗口代价聚合,对视差左右一致性进行检查与细化,获得误差较小的视差图,算法流程如图1 所示.图中,LRC(left right consistency)代表左右一致性,WTA(winner take all)代表赢者通吃,CT(Census transform)代表Census 变换.

图1 所提算法流程图Fig.1 Block diagram of proposed algorithm

1 问题描述

通过立体匹配技术获得的图像景深是双目立体视觉的基础,但是如图2 所示,由普通局部立体匹配算法得到的视差图对光照变化鲁棒性较差,图2(a)圆内的景深理论上是一致的,但在图2(b)圆内却存在明显误差;图2(a)矩形内的实物轮廓与图2(b)矩形内的视差轮廓也误差较大.所以,如何通过提高立体匹配视差值精度从而提高图像景深精度,一直是双目立体视觉领域研究的热点与难点.

图2 传统局部立体匹配算法生成的视差图Fig.2 Disparity map generated by traditional local stereo matching algorithm

图像景深与视差值的关系为

式中:l 为图像景深;f 为相机焦距;B 为双目间垂直于光轴的距离;d 为视差值.

图像立体匹配技术的核心是确定左(右)图像中任意一个像素,即如何高效准确地在右(左)图像中寻找到此像素(见图3).在解决此问题时对左、右图像给出以下约束条件:极线约束、唯一性约束、视差连续性约束、顺序一致性约束、相似性约束、平滑性约束、左右一致性约束、视差范围约束.需要达到的目标是,以左图像为参考生成的视差图与以右图像为参考生成的视差图,二者误差最小.基于以上约束与目标,故采用改进的局部立体匹配算法来提高匹配精度,具体为对图像进行引导滤波预处理增强其边缘信息;增加匹配代价计算信息和提高窗口对“同质”像素包含范围从而提高视差值精度.

图3 左右图像素匹配Fig.3 Left and right pixel matching

2 自适应窗口立体匹配算法

2.1 图像预处理

传统局部立体匹配算法大多直接采用不作预处理的原始图像,导致后期在窗口生成时不易感知边缘信息而误包含非当前区域像素.因此本工作根据Gestalt 原理在立体匹配之前强化图像轮廓信息以区分各物体,使后期视差图轮廓更接近原始图像.首先,在匹配代价计算之前采用引导滤波算法对图像进行预处理,在一定程度上削弱了原始图像平滑区域信息,相对增强了边缘区域信息.引导滤波算法具体原理如下:设输入图像为I(input),输出图像为O(output),引导图像为G(guide),当I=G 时引导滤波与双边滤波效果近似,但比双边滤波更容易实现与滤波半径无关的优化,同时降低时间复杂度.在引导滤波中将图像视为无法求出解析表达式的二维函数,该图像的任何像素满足局部线性模型,

式中:ω(k)为以I 中像素i 为中心、k 为半径、尺寸为(2k+1)2的矩形滤波窗口;ak,bk为窗口中的线性常参数.

为使拟合函数输出值Oi与实际输入值Gi差异最小,构造如下能量函数,并采用线性回归方法求解其线性常参数,

为降低能量函数模型的过拟合概率和减小参数的取值范围,需引入正则化参数ε,通过最小二乘法可得到能量函数最小值时的ak,bk值为

每个待计算像素被(2k+1)2个窗口所包含,因此会产生(2k+1)2个ak,bk值,具体求某像素的输出值时,需将所有该像素下的线性函数值平均,

2.2 生成异形自适应窗口

立体匹配的目的是确定左(右)图像中任意一个像素在右(左)图像中的位置,由于单个像素信息(三通道下的颜色与像素坐标)过于单一,所以很难利用仅有的信息去描述待匹配像素.传统自适应扩展窗口是寻找与待匹配像素“同质”的其他像素,从而可以更精确地再次描述该像素,由像素颜色和位置信息计算出的可变臂长确定窗口大小与形状,但其扩展只局限于横、纵两个方向,所以较难适应具有复杂边界的图像.因此,本工作提出了一种与传统方法不同的改进窗口选择方法,设置窗口的最大搜索半径,但不设置最小搜索半径,因此待匹配窗口半径可能为零(只有待匹配像素本身);但由于对初始左、右图像进行了引导滤波,所以会平滑图像中的绝对孤立像素,使得待匹配的窗口半径不会为零.采用螺旋搜索法遍历待匹配像素周围的所有像素,会形成比传统算法更加多变的窗口形状,更易贴合复杂图像的轮廓,提高对待匹配像素描述的准确性,从而提高匹配精度;设置顺、逆时针两条搜索路径生成匹配窗口,可以有效提高窗口形成效率,节约算法运行时间.异形自适应窗口生成过程如下.

(1) 考虑到人眼会对后期视差图作主观评估和Gestalt 原理,首先将RGB 颜色空间中的待匹配图像转换到与设备无关、基于人类生理特征的CIELab 颜色空间.

(2) 将RGB 颜色空间中的待匹配图像灰度化.

(3) 将灰度值与CIELab 颜色值叠加,使位于(x,y)处的像素具有4 层像素值,分别为(iL,ia,ib,i)(见图4);任选灰度图中坐标为i(x,y)的像素,以其为起点1 逆时针方向引入内层螺旋搜索线lN,同时为提高窗口ω 形成效率,以i(xr,yr)为起点2 顺时针方向引入外层螺旋搜索线lS(见图5).

图4 CIELab+i 颜色空间Fig.4 CIELab+i color space

图5 搜索路径Fig.5 Searching path

设待搜索窗口的最大半径为r,则i(xr,yr)定义如下:

(4) 确定螺旋搜索路径与起始点后,需对路径上的每个像素j(xp,yq)(p,q ∈ω)与起始像素i(x,y)进行如下比较,才能得到窗口ω,

式中:τ 为窗口像素截断阈值,

窗口搜索停止条件为两搜索路径交集不为空,或某环形像素带灰度值均为0,

环形像素带定义为以起始点1 为中心,集合Q 像素所构成的正方形(见图6),

图6 环形像素带Fig.6 Ring pixel strip

对图像上每个像素点重复上述过程,即可得到异形自适应窗口,

式中:L 为左图像;R 为右图像.

(5) 选择特定图像边界形成模拟窗口,如图7 所示.选取图7(a)圆内的银色货架边框中像素为待匹配像素,则与其“同质”的像素也应在此边框.当图像边界较为规则时,传统自适应匹配窗口与本工作所提算法窗口形状相同,皆为矩形窗口,如图7(b)所示.选取图7(c)圆内的褐色弧形把手中像素为待匹配像素,则与其“同质”的像素也应在此弧形把手(设置一定的窗口半径),本算法形成弧形窗口如图7(d)中黑色像素块.而传统基于十字的自适应窗口算法先沿红色箭头上下竖直搜索像素,直到大于阈值时停止,形成红色的竖直条状像素带;然后此像素带上的每个像素再分别沿黄色水平方向左右搜索像素,直到大于阈值时停止,形成黄色的水平条状像素带;最后所有条状像素带求并集就可以得到自适应窗口.图中基于十字的自适应窗口算法相比本算法,获得的窗口过早收敛在了图像的复杂边界处,窗口内的像素数更少,获得的信息量也更少,从而导致匹配精度降低.选取图7(e)圆内的白色交叉木框中像素为待匹配像素,则与其“同质”的像素也应在此交叉木框,本算法形成“X”形窗口如图7(f)中黑色像素块;而传统基于十字的自适应窗口算法形成的窗口如黄色边框所示.选取图7(g)圆内的字母“S”中像素为待匹配像素,则与其“同质”的像素也在此字母,本算法形成“S”形窗口如图7(h)中黑色像素块;而传统基于十字的自适应窗口算法形成的窗口如黄色矩形所示.传统自适应窗口算法在图7(d),(f),(h)中所形成的窗口形状均为近似“十”字状,难以有效描述图像边界,从而影响后期代价聚合.

图7 测试图像与异形窗口Fig.7 Test images and shaped windows

2.3 匹配代价计算

匹配代价就是左、右图像待匹配像素信息的相似程度,Hirschmuller等[15]在光照不均的情况下测试了各种匹配代价算法,得出Census 变换具有较好的鲁棒性和匹配精度.传统Census 变换将待匹配像素为中心窗口内非中心像素与中心像素的灰度值比较大小,并将这些信息储存在比特串中,最后计算Hamming 距离作为匹配代价值;但传统Census 变换受自身原理限制容易导致一些问题,如Hamming 距离只关注待匹配窗口内非中心像素与中心像素之间的大小关系,这会使中心像素间差异过大或窗口内非中心像素间差异过大的左右窗口误匹配,从而降低匹配精度.

针对上述问题,本工作提出像素信息三维化处理技术,将灰度值视为竖坐标,并与像素平面联合形成三维棱柱(见图8),在匹配代价计算时引入左右待匹配窗口内非中心像素间差异和窗口间中心像素差异信息,在一定程度上削弱了传统Census 变换信息单一带来的不确定性.具体是将待匹配像素的灰度值与像素坐标信息置于笛卡尔坐标系中,得到一个空间中的三维坐标点,然后将所有得到的坐标点光滑连接起来形成一个曲面;但由于待匹配窗口内的像素点个数有限,很难形成光滑曲面,所以需要在已知坐标点中插入一些点,从而得到更理想的曲面;基于已知窗口内定端点处的一阶导数值,且需分段依次插值多项式,又需提高插值函数光滑性,所以采用第一类边界条件下的三次样条插值函数[16],在待匹配窗口内的矩阵间进行横、纵向插值,使得窗口内数据更加密集.通过Matlab 的自带函数将所有三维坐标点光滑连接起来形成曲面,并将此曲面向xOy 平面投影求出体积;此体积是由窗口内所有像素信息参与构成,所以此方法引入了待匹配窗口内非中心像素间差异信息.由三次样条插值原理可知:插入像素处灰度值位于函数边界的两灰度值之间,且参与曲面形成及体积构成,故通过三次样条插值原理也可证明此方法引入了窗口内非中心像素间信息.最后,再求得左右待匹配窗口形成曲面间的差异,就可以获得窗口间中心像素差异信息,但直接求两曲面差异非常困难,所以比较两窗口在xOy 平面上的投影体积就可间接得到此差异.

图8 像素信息三维化Fig.8 3D pixel information

在左右匹配窗口形成时,引入阈值τ 使各窗口内非中心像素灰度值分布在i+ρ 与i−ρ 两平面之间,中心像素i 的灰度值大小决定上述两平面到像素平面的距离.因此,以i(x,y)和i(x −d,y)为中心像素的左右匹配窗口在像素平面投影的体积差反映了两窗口中心像素间差异.设i 为待匹配左窗口中心像素灰度值,坐标为(x,y),j 为待匹配左窗口非中心像素灰度值,ωi为以i 为中心的待匹配左窗口,待匹配右窗口中心像素坐标为(x −d,y),窗口为ωi+d,

式中:⊗为位的串联符号;Ccen(x,y,d)为在Census 变换下视差值为d 的匹配代价值;τc为在此计算方法下的截断值.

为引入窗口内非中心像素间信息,本算法在窗口内所有相邻像素间均插入θ 个亚像素(见图9),设待匹配窗口ωi半径为r,则尺寸为(2r+1)2,

图9 插入亚像素Fig.9 Inserting sub-pixel

函数T 为三次样条插值函数,经T (ωi)函数计算后的增强窗口尺寸为(2r(1+θ))2,(x,y)属于左图像L 或右图像R,得到增强窗口内的每个亚像素插值后,还需对其赋予新的像素坐标值,

其中×Θ定义为

图10 亚像素曲面Fig.10 Subpixel surface

式中:Cv(x,y,d)为在像素信息三维化方法下视差值为d 的匹配代价值;τv为在此计算方法下的截断值.

最终匹配代价为

2.4 匹配代价聚合与左右一致性检测

由式(16)和(17)可得左、右图像中所有待匹配窗口,通过寻求匹配代价差异最小的两个窗口就可得到视差值,此方法被称为赢者通吃(WTA):

WTA 原理简单且容易实现,但可能会引入错误的视差值.聚合后的最小匹配代价可能对应多个视差值,但WTA 只能选择其中一个作为待匹配点的视差值.因此,由WTA 获得的视差值具有不可靠性,对获得的视差图还需后期细化处理.具体处理过程如下:若左图像为参考图像时待匹配像素为i(x,y),则右图像中的待匹配像素为i(x −d,y);若右图像为参考图像时,左图像中i(x+d,y)的对应点为i(x,y);如果不满足双向对应关系,则为遮挡点或误匹配点,通过左右一致性(LRC)检测得到匹配异常点并重新赋值.不满足下式的点为遮挡点或误匹配点:

式中:dL,dR是左、右初始视差.

对检测到的遮挡点或误匹配点,扫描其水平方向的第一个左侧有效点,并将误匹配点的原始视差替换为二者中的视差较小值,然后获得视差图.此方法可以有效地提高分辨率、降低匹配误差,并细化视差图.最后再使用中值滤波器进行平滑操作去除噪声点,得到较高精度的视差图.

3 实验结果与分析

为测试所提出算法的有效性,基于Windows 系统的Matlab 2018a 软件进行实验,中央处理器(CPU)为Intel(R)Core(TM)i5-7300HQ,2.50 GHz,8 GB 内存,显卡(GPU)为NVIDIA GetForge GTX 1050 Ti.实验图像采用Middlebury 大学立体视觉数据库提供的第二版和第三版测试数据集.

(1) 为单独测试本工作提出的像素信息三维化匹配代价计算方法,选取以下3 种方法与所提出算法相比较:基于灰度值差的绝对值之和(sum of absolute differences,SAD)匹配代价计算方法、基于Census 变换(CT)的匹配代价计算方法、基于Census 变换和梯度(Census transform and gradient,CG)的匹配代价计算方法.算法参数设置如下:k=16,ε=0.01,r=7,τc=1,τv=0.275,τ=10θ=2,α=0.5;实验图像采用Middlebury 大学立体视觉第二版2001 年数据库中标准彩色图像对Tsukuba 和Venus,分辨率(pixel×pixel)为384×288 和434×383,视差(pixel)范围为[1,28]和[1,20];以及2003 年数据库彩色图像对Teddy 和Cones,分辨率为450×375 和450×375,视差范围为[1,55]和[1,55].

由实验结果(见表1)得出:本工作提出算法在非遮挡区域(Nonocc)的平均误匹配率为3.21%,在所有区域(All)的平均误匹配率为13.1%,均优于其他匹配代价计算方法,表明像素信息三维化匹配代价计算方法引入的左右待匹配窗口内非中心像素间差异和窗口间中心像素差异信息提高了匹配精度.

表1 不同匹配代价计算方法误匹配率Table 1 Percentage of mismatches for different matching cost calculations %

由图11 可知,Tsukuba(第一行)在本算法视差图背景中有两个较小的噪声点,图11(c),(d),(e)算法背景虽无明显噪声点但物体轮廓完整性较差,视差图有明显误差;Cones(第四行)采用图11(c),(d),(e)算法在左侧圆锥轮廓描述上均有缺陷;综合来看是由于结合了Census 变换,噪声抑制能力进一步增强,所提算法视差图平滑性较好,边界更为平整,轮廓更加清晰.

图11 不同立体匹配方法在图像对上的测试结果Fig.11 Test results of different stereo matching methods on image pairs

(2) 为全面有效地测评所提出算法,又选取Middlebury 大学立体视觉第三版2014 年数据库中标准彩色图像对AustraliaP,Livingroom,Hoops,Newkuba 作为测试图像对,分辨率为717×492,742×496,721×498,701×487,视差范围为[1,73],[1,113],[1,103],[1,143].

实验选取了视差阈值为2 时Middlebury 排名为43,48,50,61 的迭代差异细化(iterative disparity refinement,IDR)、局部平面扫描(local plane sweeps,LPS)、局部自适应代价(local adaptive cost,LAC)和局部自适应多重代价(local adaptive multi-cost,LAMC)的LAMC-DSM共4 组自适应窗口局部立体匹配算法,结合表2,3 与图12(a),(b)得出,本算法对植物、非洲鼓、呼啦圈和水壶等图像,均可获得与真实视差在轮廓与细节方面非常接近的视差图.在纹理丰富和深度不连续的区域匹配精度较高,说明结合了Census 变换的算法可以形成较为全面的、多重信息下的匹配代价计算方法,更能精确地描述待匹配像素间的差异,从而得到更为精确的匹配代价值.图12(a)和(d)中矩形框内的复杂边界植物茎叶和弧形椅子扶手与图12(b)和(c)中矩形框内的复杂边界圆形呼啦圈和斜线台灯杆比其他算法更加接近真实视差图;在图12(a)中非遮挡匹配率仅为3.83%,在其余图中也明显低于表2 中其他算法误差,说明异形自适应窗口更加多变的形状对图像轮廓贴合更为精确,在纹理丰富的区域更容易获得匹配精度较高的形状;且在图12(c)中光照不均的条件下表现依旧良好,非遮挡匹配率仅为5.12%,源于在匹配代价计算时结合了Census 变换,提高了算法对光照不均的鲁棒性.本算法平均误匹配率分别为14.74%与21.26%,相比表2 中前4 种算法平均值分别降低了3.32%与7.63%,由此可以得出异形自适应窗口算法在复杂边界图像中的匹配精度提升幅度较大.

表2 各算法在视差阈值为2 时的误差对比Table 2 Error comparison of each algorithm when the parallax threshold is 2 %

图12 各算法在Middlebury 图像对上的实验结果Fig.12 Experimental results of algorithms on Middlebury image pairs

实验选取了视差阈值为2 时Middlebury 排名前10 中的3 组算法,即卷积神经网络匹配代价与自顶向下分段回归(matching cost-convolutional neural networks+top down segmented regression,MC-CNN+TDSR),局部扩展(local expansion,LoaclExp),利用卷积神经网络更广泛寻找(look wide-convolutional neural networks,LW-CNN)(见表3).可以看出这3 组算法的误匹配率约为异形自适应窗口的60%,但是程序运行时间约为本算法的25 倍以上.这说明相对于排名靠前的优秀算法,异形自适应窗口算法在误匹配率上落后不大,但在效率上远远大于3 组算法.对于效率相近的算法,本工作提出的异形自适应窗口算法则在匹配精度上更占优势.

表3 各算法在表1和2图像中的匹配精度与运行时间对比Table 3 Comparison of the matching accuracy and runtime of each algorithm in the images of tables 1 and 2

4 结束语

本工作提出一种异形自适应窗口局部立体匹配算法,通过快速、可遍历窗口所有像素的双螺旋路径法得到形状多变的待匹配窗口,提高了复杂图像边界的贴合性和图像描述性;并采用结合了Census 变换的像素信息三维化匹配代价计算方法,引入了左右待匹配窗口内更为丰富的信息,在一定程度上削弱了传统Census 变换信息单一带来的不确定性,有效提高了对待匹配像素信息描述的准确性;由此在复杂边界与光照不均图像中获得较为精确的视差值,为双目立体视觉技术发展提供了有利的条件.

异形自适应窗口算法在图11 Tsukuba 视差图背景中有两个较小的噪声点,以及在图12(b),(d)中的局部出现了较大的匹配误差,这源于本算法在弱纹理区域获得的匹配窗口与传统自适应窗口类似,从而使窗口间像素信息差异过小,无法有效根据此差异获得可靠的匹配代价,所以匹配精度有所降低.具体还需在后续工作中进一步分析研究此问题,并对弱纹理区域匹配提出针对性的解决方法.