基于多特征融合与树形结构代价聚合的立体匹配算法

郁怀波, 胡越黎,3, 徐 杰

(1. 上海大学上海市电站自动化技术重点实验室, 上海200444; 2. 上海大学微电子研究与开发中心, 上海200444;3. 上海大学机电工程与自动化学院, 上海200444)

双目立体视觉是计算机视觉领域的热门话题之一. 立体匹配算法主要可以分为2 大类：全局算法和局部算法. 全局算法通常是通过定义一个全局能量函数并寻找最优解来得到视差图.全局算法包括动态规划[1]、置信区间传播[2]和图割算法[3]等. 虽然全局算法准确率较高, 但是算法运算量较大, 难以达到实时性要求; 局部算法则是通过像素点周围的局部信息来判断视差值, 速度较快且易于实现, 但是其匹配代价计算方式和代价聚合区域的选择是难点.

常用的匹配代价计算方式包括灰度的绝对差值之和(sum of absolute differences, SAD)、灰度的差值平方和(sum of squared differences,SSD)以及灰度值的归一化互相关(normalized crosscorrelation, NCC). 然而, 这些匹配代价计算方式对于噪声、相机增益、偏置都非常敏感,在弱纹理区域的匹配效果不佳[4]. 中值滤波、高斯拉普拉斯算子和图像梯度幅值[5]等图像预处理方式可以有效滤除噪声, 但是由此得到的视差图边缘部分不够清晰[4]. 互信息(mutual information, MI)[6]、Rank 变换和Census 变换等非参数方法对噪声具有较高的鲁棒性, 得到的视差图边缘部分也较清晰, 但是由于没有考虑到图像的颜色信息, 故在图像的重复结构区域往往会造成误匹配. 可见, 匹配代价计算方式的合理性直接关系到立体匹配算法的准确度.

为了在深度不连续区域得到精确的视差, 用于代价聚合的区域应该仅仅包含同一深度的像素点. 目前, 代价聚合方式主要分为2 大类[7]：①对每个像素点从预先定义的多个聚合窗口中选择最佳的窗口[8], 或者自适应调整每个像素点的聚合区域[9]; ②对于大小和形状固定的聚合窗口, 自适应调整窗口的权值[10]. 然而所有这些代价聚合方式都只考虑每个像素点周围的局部信息, 这必然会在弱纹理区域产生误匹配, 存在深度不连续区域匹配精度不高的问题.

为此, 针对立体匹配中弱纹理区域和深度不连续区域的匹配精度问题, 本工作提出了一种基于多特征融合的树形结构代价聚合立体匹配算法, 该算法总体分为4 个步骤：①融合图像梯度、图像颜色以及图像的Census 变换进行匹配代价计算; ②根据由原始图像颜色信息生成的最小生成树进行匹配代价聚合; ③使用多方向扫描线优化, 进一步提高在弱纹理区域的匹配准确率; ④使用左右一致性检测标记出误匹配点, 基于视差统计直方图对误匹配点进行修正.

1 基于多特征融合的匹配代价计算

Census 变换与像素灰度值的具体大小存在着弱相关性, 只涉及像素之间的相对大小之间的联系, 因而Census 变换对噪声具有强鲁棒性. 但是, 在图像的重复结构或相似结构区域,Census 变换的这种特性可能会导致误匹配. 与Census 变换相反, 基于颜色特征的SAD 在这些纹理复杂区域有着较好的表现效果. 再考虑到基于梯度的匹配代价可以最大限度地提取出原始图像的材质信息, 进一步提高在弱纹理区域内的匹配精度, 因此本工作提出了一种融合图像的梯度信息、颜色信息以及Census 变换的匹配代价计算方法.

1.1 基于梯度的匹配代价

图像的梯度包含丰富的结构信息. 由于图像的梯度不受图像绝对亮度的影响, 即使双目相机成像的亮度不同, 图像的梯度依然能较好地衡量2 幅图像的相似性, 故基于梯度的匹配代价被广泛应用在立体匹配算法中. 基于梯度的匹配代价计算方法为

式中, Cgrad(p, d)表示像素点p 在视差为d 时的基于梯度的匹配代价; ∇x和∇y分别为x 方向和y 方向的基于单色灰度值的梯度算子; IL(p)和IR(p, d)分别为左图像中的像素点p 和右图像中视差为d 所对应的像素点.

1.2 基于Census 变换的匹配代价

Census 变换是一种局部非参数变换, 即将变换窗口内的像素的强度值映射到一个比特串,从而捕捉到图像的结构信息, 并以该比特串代替变换窗口内的中心像素点. 具体定义为

式中, Np是以像素点p 为中心的变换窗口; ⊗为位拼接算子, 用来把单独的二进制位连接成比特串; Ip和Iq分别为像素点p 和q 的像素值. 对于在左图中像素点p 以及右图中视差为d对应的像素点q, 在分别得到Census 变换后的比特串Census(p)和Census(q)后, 基于Census变换的匹配代价即为2 串比特串之间的汉明距离. 用⊕来表示汉明距离算子, 则基于Census变化的匹配代价可表示为

1.3 基于颜色的匹配代价

基于颜色的匹配代价是立体匹配算法中最常用的匹配代价计算方法, 其具体操作如下: 令p 和q 分别为左图中像素点以及右图中视差为d 所对应的像素点, 则基于颜色的匹配代价定义R, G, B 这3 个通道颜色差值的平均值为

1.4 多特征匹配代价融合

将基于梯度、Census 变换和颜色的匹配代价进行融合, 形成最终的多特征匹配代价:

式中, CAD, Ccen和Cgrad分别为基于颜色、基于Census 变换和基于梯度的匹配代价, 由式(4), (3)和(1)定义; 截断函数T(C, t)定义为[4]

式(5)中的tAD, tcen和tgrad分别为基于颜色、基于Census 变换和基于梯度的匹配代价的截断阈值, 是用来确保当匹配代价融合时不过分偏向于某一种匹配代价. α, β, λ 为调整参数, 用来控制各个匹配代价在融合时的权值, α 和λ 分别用来调整基于颜色和梯度的匹配代价的权重, 通常λ 取为α 的4 倍, 这样使基于梯度的匹配代价能够补偿基于颜色的匹配代价在弱纹理区域内噪声鲁棒性较低的不足; 调整参数β 是用来调整基于Census 变化的匹配代价的权重的, 通常取大于α 和λ 的值, 使最终融合的匹配代价能够同时表达原始图像的颜色信息和基于Census 变换的结构信息.

2 基于树形结构的匹配代价聚合

传统的代价聚合通常是基于一个预先定义的、大小固定的窗口, 或根据颜色等信息自适应生成的代价聚合窗口, 但是基于窗口的代价聚合从根本上限制了每个像素点只能根据其周围的局部信息来对视差值进行判断, 因而在某些情况下根本无法找到一个最合适的聚合窗口. 与基于窗口的代价聚合不同, 文献[11]提出的基于树形结构的代价聚合对于每一个像素点, 都考虑到了原始图像上除该像素点以外所有的像素点. 本工作使用该树形结构对基于多特征融合的匹配代价进行聚合, 从而进一步提高匹配准确度.

2.1 树形结构的建立

将原始左图作为建立最小生成树的引导图像, 用G=(V, E)表示, 其中顶点V 为所有的图像像素点, 边E 为所有邻近像素点之间的边. 令s 和r 为一组邻近的像素点, 则这2 个顶点之间的边的权重定义为这2 个像素点的像素灰度差值:

在由原始左图生成的平面四连通无向图G 中, 去掉权重较大的边, 即生成了用来对匹配代价进行聚合的最小生成树.

2.2 基于树形结构的代价聚合

首先, 从叶节点往根节点方向进行代价聚合(见图1(a)). 图中, 每条边上的数字表示相邻2 个节点之间的距离. 从叶节点往根节点的代价聚合值

式中, P(vc)表示像素点vc的父节点, 函数S(p, q)表示像素点p 和q 的相似性. 令D(p, q)为最小生成树中p, q 这2 个像素点的距离, 那函数么S(p, q)定义为

式中, σ 是一个常数, 用来控制2 个像素点的相似性程度. 然后, 再从根节点往叶节点进行代价聚合, 从而得到每个像素点最终的代价聚合值(见图1(b)). 因此, 最小生成树上每一个像素点的代价聚合值为

图1 代价聚合过程Fig.1 Cost aggregation process

3 多方向扫描线优化

考虑到在实际场景中, 除物体边缘区域外视差变换都是连续的, 即相邻像素点之间的视差值应变化不大. 为此, 在全局能量函数中新增视差平滑约束项[12]

式中,C 为根据最小生成树聚合后并依据每个像素点代价聚合时的权值(即式(9)中的S(p,q))进行归一化后的匹配代价; p,d 分别为待匹配图像中的像素点及其视差值; p′,d′分别为像素点p领域中的像素点及其视差值; ε 为视差平滑约束项; G 为待匹配图像的梯度; λ 是一个调整参数, 用来调整视差平滑约束的强度. 对于该能量函数, 在原始图像的上下左右4 个方向上分别使用动态规划对该全局能量函数进行求解. 动态规划的递推表达式为[12]

经过多方向扫描线优化后的每个像素点的最终代价值用e 表示, 根据WTA(winner-takes-all)策略, 对于每个像素点p, 使得e(p, d)最小的d 即为该像素点的视差值.

4 视差修正

由上述步骤所得的初始视差图在弱纹理区域和深度不连续区域内包含很多误匹配点, 因此需要对误匹配点进行修正, 从而得到精确的视差图. 本工作对误匹配点进行视差修正的方法是使用左右一致性检测标记误匹配点, 并基于视差统计直方图对误匹配点进行修正.

4.1 左右一致性检测

左右一致性检测的原理是空间中一点在左图像和右图像中的视差值应相同. 分别以左右图像作为基准求得视差图DL和DR. 对左图中的像素点p, 根据DL找到其在右图中的对应点p −(DL(p), 0). 如果DL(p) = DR(p −(DL(p), 0)), 则表示该像素点通过左右一致性检测, 是稳定点; 否则该像素点为误匹配点.

4.2 误匹配点视差修正

误匹配点的特征是在其周围邻域内总是存在正确视差像素点, 即通过左右一致性检测的稳定点. 对于检测出的误匹配点p, 根据其周围邻域内的稳定点的视差值建立一个视差统计直方图Hp, 该直方图中的峰值所对应的视差d 即认为是该误匹配点p 的修正后的视差值:

5 算法总体流程

算法的总体流程如图2 所示. 在匹配代价计算部分, 首先分别计算基于梯度、基于Census变换和基于颜色的匹配代价, 并对这3 种匹配代价进行融合; 接着使用树形结构对融合后的匹配代价进行聚合; 然后使用多方向扫描线优化, 进一步提高算法匹配的准确度; 最后基于视差统计直方图, 将未通过左右一致性检测的误匹配点进行视差修正, 得到最终准确的视差图.

6 测试结果与分析

使用C++来验证本算法的有效性. 测试平台为CPU i7-6700HQ、内存8 GB 的电脑; 编译软件为VS 2013; 测试中所用的测试图像来自Middlebury 测试集. 测试结果表明, 立体匹配算法中参数的选取对算法效果有较大影响, 经过分析得到各参数的设置情况如下: 式(5)中匹配代价的截断阈值tgrad=40, tAD=10, tcen=100, 融合权值α=0.25, β=1, γ=0.1, Census 变换的窗口大小取11×11, 式(9)中的相似性调整参数σ 为0.05, 式(11)中的视差平滑约束强度调整参数λ 为0.1, 视差统计直方图统计的邻域大小为11×11.

同时, 为了更好地对本算法进行评测, 还选取了Middlebury 测试集中的NonLocal filter算法和SemiGlob 算法进行对比. NonLocal filter 算法是经典的基于树形结构代价聚合的非局部立体匹配算法, 在聚合的过程中只考虑颜色信息; SemiGlob 算法是一种半全局立体匹配算法, 在8 个方向上对全局能量函数进行求解, 能量函数中的视差平滑约束项是固定的常数.NonLocal filter, SemiGlob 和本算法的测试结果如图3 所示.

图2 算法整体流程Fig.2 Flow chart of the algorithm

图3 结果视差图对比Fig.3 Comparison of result disparity map

图3 中从左往右依次为Middlebury 测试集中的Tsukuba, Venus, Teddy 和Cones 测试图像. 在Tsukuba 测试图像中, 本算法与NonLocal filter 算法都能较好地保留台灯连接杆的边缘部分, 且在Teddy 测试图像中本算法的效果优于NonLocal filter 算法效果. 本算法在4 张测试图像的弱纹理区域以及深度不连续区域都能得到清晰、平滑的视差图.

为了对匹配算法的效果进行定量分析, 根据Middlebury 测试集提供的4 张测试图像所对应的标准视差图进行误匹配率计算. 表1 列出了3 种算法的误匹配率, 其中n-occ 表示非遮挡区域, all 表示所有区域, disc 表示深度不连续区域. 误匹配率越小则立体匹配算法准确度越高.由表1 中的数据可见, 本算法在Tsukuba, Venus 和Teddy 3 张测试集图像上的误匹配率均低于SemiGlob 算法, 且在Venus 和Teddy 2 张测试图像上的N-occ 非遮挡区域优于NonLocal filter 算法. 测试得到的平均误匹配率为6.38%, 低于SemiGlob 的7.50%, 略高于NonLocal filter 算法的5.48%.

表1 误匹配率对比Table1 Error ratio comparison %

为进一步验证本算法的实用性, 使用2 组实际场景进行测试, 其测试结果如图4 所示. 本算法得到的视差图较好地保留了原始图像的轮廓, 视差图整体较平滑, 效果较好.

图4 实际场景测试Fig.4 Actual scene test

由于拍摄的图像没有标准深度图, 故通过选取一些显著的特征点, 比较特征点处实际深度与匹配计算得到的深度, 来对算法提取深度信息的准确性进行定量评价(见表2). 对于每一个测试场景, 分别选取5 个测试点, 并根据测试点的实际深度与匹配深度计算得到平均测距误差率, 最终得到测试场景1 和2 的平均测距误差率分别为5.76%和5.55%, 基本达到双目视觉深度信息提取的要求, 证明了本算法的实用性.

表2 实际场景测试误差分析Table2 Error analysis of actual scene test

7 结束语

针对立体匹配中弱纹理区域和深度不连续区域的匹配精度不高的问题, 提出了一种基于多特征融合的树形结构代价聚合立体匹配算法. 首先在代价计算部分融合了图像的梯度、颜色和图像的Census 变换; 其次基于所有像素点, 在由原始图像构成的树形结构上进行代价聚合; 接着加入平滑约束在多方向上进行扫描线优化, 进一步提高算法在弱纹理区域的准确度;最后使用左右一致性检测误匹配点, 并根据视差统计直方图进行修正.

通过与Middlebury 测试集上另外2 种立体匹配算法Nonlocal filter 和SemiGlob 的对比表明, 本算法具有较好的立体匹配效果; 另外, 通过2 个实际场景的测试表明了本算法具有较高的实用性.