半全局立体匹配算法的改进研究

白 创，许百灵

(长沙理工大学物理与电子科学学院,湖南 长沙 410114)

0 引言

双目立体视觉是机器视觉研究的一个重点，被广泛应用于三维重建、目标检测以及虚拟现实[1]等领域。其中，立体匹配是双目立体视觉中最重要的一环，通过计算2幅不同视角下的图像间的像素视差，进而恢复出三维场景的深度信息。目前，立体匹配算法主要分为局部算法和全局算法2类。常见的局部算法有归一化互相关算法(normalized cross correlation，NCC)、基于灰度差绝对值算法(absolute difference，AD)和绝对误差和算法(sum of absolute differences，SAD)等。局部算法在支持窗口域中逐像素进行匹配，计算复杂度低，但匹配精度较弱。全局立体匹配则通过构造能量函数，转化成对能量函数求解最优解的问题来获取视差图，主要的全局算法有动态规划[2]、置信传播[3]等。全局算法匹配精度较局部要高，但耗时较长，实时性难以满足。2005年，Hirschmuller[4-5]提出了一种介于全局算法和局部算法之间的半全局立体匹配算法 (semi-global matching，SGM)，共分为4个部分：代价计算、代价聚合、视差选择和视差优化。在代价计算部分，SGM通常采用Census变换进行计算，但Census仅考虑图像的亮度信息，对光照和噪声鲁棒，在重复纹理容易有歧义。在代价聚合部分SGM通过寻找每个像素的最优视差使得整张图像的全局能量函数最小。SGM的能量函数包含2个参数：惩罚项P1和惩罚项P2。P1、P2分别用来适应视差变化小和视差变化大的情形。然而单纯地给每个像素赋予相同的参数，容易产生误匹配。近年来，有许多研究人员在SGM的基础上进行了改进。首先针对代价计算中Census变换的问题，一般的改进方式为将梯度信息、颜色信息和Census变换混合作为匹配代价，增强无纹理区域的鲁棒性[6-7]，但时间复杂度也会随之提高。另外针对代价聚合中参数赋值问题的优化有2个大方向：一是通过检测边缘，利用边缘特征来优化视差边缘精度，如Rothermel等[8]采用Canny算子检测边缘，并在边缘处减小参数P2，从而达到保持精度的效果，但采用Canny提取的边缘像素容易出现错误定位像素；二是将图像分割技术引入到匹配过程中，在各割块内进行能量函数优化，如宁晓斐[9]采用图像分割的方式，相比较于Canny算子，能更精确地得到边缘视差，在深度不连续区域精度得到提高。

综合考虑立体匹配算法研究现状，针对SGM算法的不足，本文采用立体像对的三通道亚像素差值(birchfield-tomasi metric，BT)算法和改进Census变换联合的代价计算方法，缓解重复纹理歧义，提高不连续区域匹配精度。并在代价聚合部分引入均值漂移图像分割，通过分割情况，自适应采用不同的惩罚参数P1、P2，提高边界纹理区域匹配精度。然后通过胜者为王策略进行视差选择，得到初始视差图。最后在视差优化部分提出分步中值滤波的概念，通过加入图像分割信息进行分段滤波，进一步细化视差，得到高精度视差图。

1 算法原理

本文算法由代价计算、代价聚合、视差选择和视差优化4部分组成，流程如图1所示。

图1 算法流程

1.1 代价计算

在对图像预处理结束后，需要依次遍历左图中每一个像素，在视差范围内计算其和右图中每个像素点的匹配代价值。Census[10]是目前应用比较广泛的代价，比较的是2幅图像的相对灰度关系，所以对亮度具有鲁棒性，并且基于窗口的方法对影像噪声也有一定的鲁棒性，但是在重复纹理区域有歧义，容易造成误匹配。而基于单像素亮度差的方法对差异性比较敏感，通常与Census结合使用[11]。但基于单像素亮度差的方法对于深度不连续区域误差较大，本文采用Birchfield等[12]提出的BT算法，这种方法是一种亚像素差值的方法，能在一定程度上缓解重复纹理歧义的前提下，在不连续区域也有较好的效果。

1.1.1 Census变换优化

传统Census变换的基本思想是通过将邻域窗口中的像素灰度值与中心像素灰度值进行比较，中心像素小的标记为1，反之标记为0，通过字符串接函数连接后得到0和1组成的字符串。表达式为：

(1)

(2)

u为窗口中心像素；v为窗口中心像素之外的其他像素；⊗ 为字符串接函数；I(u) 和I(v)为对应像素点的灰度值；T(u)为得到的字符串。

得到左右图像同位像素点的对应字符串后，利用汉明距离计算2个字符串的相似程度,得到的代价值为

Cα(u,d)=H(Tl(u),Tr(u,d))

(3)

α为Census变换；C为代价值；Cα(u,d)为当前像素u在视差值为d时的Census代价值；H为汉明距离计算公式；Tl(u)为左图中窗口中心像素u对应的字符串；Tr(u,d) 为像素u在视差为d时对应的右图中像素字符串。汉明代价的计算方式是将2个字符串进行异或运算，统计异或运算结果中不为1的个数，以大小为3×3的窗口为例，变换过程如图2所示。

图2 原始Census变换

传统的Census变换方法仅采用中心像素灰度值和邻域内像素灰度值进行比较，变换结果过于依赖中心像素点灰度值，一旦中心像素灰度值受到噪声干扰则容易得出错误编码，降低算法精度。针对这一问题，本文提出用邻域内像素值的中值替代中心像素的灰度值，在滤波窗口内进行一次中值滤波，将得到的中值作为窗口中心灰度值，与邻域窗口其他灰度值进行比较，得到最终的Census变换结果。2种Census变换对比如图3所示。图3a中，当中心像素灰度值受到噪声影响由84变成91时，采用原始Census变换的字符串由00100101变成了00100000，编码有了很大变化。图3b中，以中值代替中心像素灰度值得到的字符串结果仍保持不变，可见中值滤波的方法相较于传统Census引入了比较运算，降低了算法对窗口中心像素的依赖，虽然不能保证完全不受噪声影响，但能在一定程度上提高抗干扰能力。

图3 2种Census变换对比

1.1.2 BT算法优化

和基于单像素亮度差的算法一样，BT代价也是左右图像对应像素灰度值差值的绝对值，不同的是BT利用了亚像素的灰度信息。该算法计算采用的是一种类似线性差值的方法，如图4所示，线性插值可利用过2点的直线来近似表示原函数，在这里IL、IR代表左右图像灰度值，利用过2个像素点的直线来近似计算亚像素点的灰度值。

图4 BT算法

(4)

(5)

(6)

(7)

传统的BT算法利用的是灰度值，由于目前的立体图像对多为彩色影像，为充分利用图像信息，采用图像中RGB三通道颜色信息进行计算，在每一通道分别求出视差d的值后，利用β表示三通道BT算法，对于当前像素点xi得到BT匹配代价Cβ(xi,yi) ，即

(8)

1.1.3 联合匹配代价

联合匹配代价是将三通道BT算法和Census变换融合生成视差空间，但2个算法生成初始匹配代价的尺度不一致，不能简单地将二者进行加和。为此，采用归一化公式将二者的结果归一化到相同的范围区间，即

(9)

C(p,d)为像素点p在视差为d时的联合匹配代价；Cα(p,d)、Cβ(p,d)分别为像素点p在视差为d时的Census变换代价值和BT代价值， 采用函数ρ将2种匹配代价归一化至[0,1]的范围内，并通过参数λ调节2种方法对匹配成本的影响。

1.1.4 实验分析

选用Middlebury立体匹配测评网站中的泰迪图像进行对比实验，聚合部分采用原始的SGM聚合步骤，只改动代价计算部分，如图5所示。图5a为原始左图像，图5b为标准视差图，图5c是原始Census计算得到的视差图，图5d是改进后的视差图。从图5中可看出，相较于原始视差图，改进后的视差图在重复纹理区域、视差不连续区域的匹配精度都有了较大提高。

图5 改进代价计算

1.2 代价聚合

1.2.1 加入图像分割

由于匹配代价计算容易受到噪声、相似区域等因素影响，SGM将一个额外的平滑约束引入能量函数中。SGM定义能量函数E(d)为

(10)

C(p,d) 为像素点p在视差为d时通过代价计算步骤得到的初始匹配代价；后2项为约束项，表示对当前像素p的Np邻域内所有像素点q进行惩罚；P1、P2为惩罚因子，其中P1小于P2。当相邻视差变化量为1时，给定较小的惩罚因子P1，用来适应视差变化小的情形，如倾斜的平面。当相邻像素视差变化大于1个像素时，给定较大的P2用来适应视差变化大的情形，如前景背景交界处。但在现实复杂的场景中，导致视差突变的情况有很多，单一的固定惩罚无法适应各类场景。图像分割将某一区域内颜色相似的像素点划分到同一割块，同一割块内的视差变化较为平滑，割块边界往往视差不连续，本文在能量函数模型中引进图像分割，通过分割得到的信息对不同的像素点选择不同的惩罚参数。

Meanshift[13]图像分割又被称为均值漂移法，是一种利用概率分布的梯度寻找分布峰值的非参数迭代算法。对于当前像素点，以该像素点为中心划定邻域，求取该像素点邻域内的偏移均值，再以该偏移均值点为中心继续执行上述迭代过程，直到最终收敛。Meanshift处理之后的影像在色彩层面将变得平滑，然后通过漫水填充函数对每个割块上色，漫水填充能将与当前像素灰度值相近的连通域替换成指定颜色，通过不同的颜色就能够区分不同的割块，从而达到分割的目的。Meanshift计算原理简单，分割得到的图像边界与原影像几乎重合，故本文算法选择均值漂移算法进行图像分割。将分割后的信息与能量函数相结合，自适应选择惩罚参数，若像素不在同一分割区域，即当前像素为边缘像素，则对相邻像素的视差变化选取小的惩罚参数P11、P21允许其保持突变，若像素属于同一分割区域，即为非边缘像素，则通过设置大的惩罚参数P12、P22强制增加视差平滑。改进后的能量函数为

(11)

1.2.2 实验分析

对代价计算改进后的视差图接着进行代价聚合改进对比实验，如图6所示。图6a为采用原始代价聚合得到的视差图，图6b为加入图像分割后得到的视差图。

从图6中可以看出改进后的视差图在边缘地区有了较明显的变化，如白框框出来的部分，边界更加接近真实视差图，错误匹配像素减少，进一步提高了匹配精度。

图6 改进代价聚合

1.3 视差优化

在代价聚合之后，采用胜者为王策略，选出每个像素最小聚合值所对应的视差作为最终视差，得到视差图，然后进行优化处理，进一步提高视差精度。在视差优化这一步，采用了一系列方式，包括左右一致性检查、剔除小连通区域、视差填充和中值滤波。

中值滤波是为了尽可能在保留图像细节特征的条件下对噪声进行抑制，通过对滤波窗口中的像素进行排序，将中心点赋值为排序得到的中值从而对图像进行平滑。在这一步，本文提出一种分步中值滤波的方式，通过选用3×3的滤波窗口，将图像分割的信息引入进来，进行2步滤波。第1步根据之前分割得到的分割场景信息，在各个割块内部进行滤波;然后将第1步滤波得到的结果作为初始视差图再整体进行1次滤波，生成最终视差图。如图7所示，通过加入图像分割进行的分步中值滤波相比于单纯的整体滤波边缘更加平滑、流畅，可获得高精度的稠密视差图。

图7 改进中值滤波

2 整体实验结果与分析

为了验证本文算法的有效性，选取Middlebury立体匹配测评网站的4组标准图像锥面、泰迪、筑波和金星进行实验，视差的搜索范围分别为0～59、0～59、0～16、0～20。实验程序采用C++编写，平台为Windows 10下的Visual Studio 2019，OpenCV3.10。将本文算法与传统SGM算法进行实验对比，生成的结果如图8～图11所示。

图8为4组图像的原始左图像、图9为真实视差图、 图10为传统SGM算法视差图、图11为本文算法视差图。从图8～图11中可以看出，相比较传统算法，本文算法得到的视差图整体轮廓更清晰，如图中白色方框所框出来的区域，与真实视差图边界重合度更高。为了对算法进行定量评估，从非遮挡区域(Non)、所有区域(All)和深度不连续区域(Disc)3个区域来分别验证算法视差精度，评估结果如表1所示。

图8 原始左图像

图9 真实视差图

图10 传统SGM算法

图11 本文算法

表1 传统算法与本文算法误匹配率对比 %

由表1可以知道，本文算法对于3个区域都不同程度地降低了误匹配率，非遮挡区域平均降低了1.4%，全部区域降低了1.5%，深度不连续区域下降了3.5%，说明本文算法在原始SGM的基础上提高了整体匹配精度，验证了算法的有效性。

同时，为了进一步验证算法可行性，选取了一些其他的算法和本文算法进行比较，得到的结果如表2所示。

表2 不同算法与本文算法误匹配率对比 %

由表2可以知道，在6种算法中，对于场景比较复杂的锥面、泰迪图像，本文算法具有最小的误匹配率，对于简单图像对筑波和金星，本文算法的误匹配率也较低，尤其是金星的误匹配率在All区域只比第1名的LCVB-DEM算法低0.3个百分点，但金星、筑波2幅图像All区域误匹配率低的算法LCVB-DEM、RealTimBP和TreeDP，在锥面和泰迪上面的误匹配率要比本文算法却高得多，这说明本文算法在复杂场景匹配精度较高的同时,在简单纹理上也能保持较好的视差估计能力。从各类算法的平均误差来分析，本文算法的平均误差是6种算法中最低的，为6.5%，相较于其他算法匹配效果更接近原始图像，能较好地适用于各种不同场景。

3 结束语

针对单一Census匹配精度不高且边缘视差较差的问题，提出了一种新的改进方法。该算法融合三通道BT算法和改进Census变换提出一种新的代价计算方式，并在代价聚合和视差优化步骤中引入图像分割作为边缘约束，改进边缘视差。实验结果表明，本文算法相比于传统算法，有效地提高了视差图的精度，降低平均误匹配率，能较好地适用于各种复杂的场景。