一种基于自适应权重SAD与Census融合的匹配算法

邹进贵，万 荧，孟丽媛

(1. 武汉大学测绘学院，湖北 武汉 430079； 2. 精密工程与工业测量国家测绘地理信息局重点实验室，湖北 武汉 430079)

双目立体视觉的目的是从二维图像中提取三维信息，从而恢复三维场景，它在三维测量、虚拟现实、机器人导航等领域中有着广泛应用[1]。立体匹配是立体视觉技术中的关键，其任务是计算图像对中同名像素点间的视差，得到视差图[2]。

立体匹配算法可以分为全局算法和局部算法。全局算法匹配精度高，但计算复杂且计算量大；局部算法易于实现且效率较高，但易造成误匹配[3]。在局部算法中，差的绝对值之和(sum of absolute differences，SAD)算法是常用的算法，该算法匹配速度快，但对曝光程度和光照条件较为敏感；Census算法是一种非参数变换的算法，该算法可以克服曝光和光照不同对匹配的影响，但其过度依赖中心像素灰度值的大小，也没有利用临近像素灰度值之间的连续性约束，整体精度不高[4-5]。

本文研究SAD算法与Census算法，将改进后的SAD算法与Census算法融合，提出一种基于SAD算法和Census算法的自适应权重的立体匹配算法，该算法可以提高匹配精度，且对光照变化和曝光不同引起的图像亮度差异，也可保持较好的稳健性。

1 SAD算法与Census算法

1.1 SAD算法原理

局部立体匹配算法处理的是水平双目立体视觉系统摄取的图像对，图像对的外极线平行，即同一物方点在左右图像上成像，两个像点的行坐标一致。这类算法需要建立窗口来辅助匹配，其原理如图1所示。

图1 局部立体匹配原理

以图(b)为参考图，在图(a)上寻找匹配点。首先以图(b)中的某一待匹配点作为中心点，创建一个参考窗口，然后在图(a)像中同一位置创建一个相同的子窗口，用窗口中的多个像素灰度值来表征中心点。在图(a)像中的搜索范围内，逐一建立子窗口与参考窗口进行比较，用相似性测度函数的计算值来评价两个窗口的相似度，当某个子窗口与图(b)的参考窗口最相似时，即认为这个窗口的中心点与图(b)中的待匹配点是匹配点对。对每一个像素点进行处理，即可完成两幅图像的匹配。若以图(a)为参考图，在图(b)上寻找匹配点，匹配原理一致。

SAD是其中的一种相似性测度函数，其计算公式如下

(1)

式中，IL(x,y)、IR(x,y)为左右图像中(x,y)位置的像素灰度值。用i、j遍历窗口中每个元素，每进行一次计算后，d的数值加1，完成范围内的逐一搜寻。两个子窗口计算所得SAD值最小时，其对应的点就是匹配点，此时的d即为视差值[6]。

1.2 Census算法原理

Census算法也需要建立子窗口，其首要工作是对窗口中的元素进行Census变换。Census变换是一种局部非参数变换，计算窗口的灰度值大小序列，将中心像素以外的像素用一个比特串表示。如果窗口中某个像素的灰度值比中心像素的灰度值大，则在比特串相应位置标记为1，反之标记为0。Census变换公式如下

(2)

式中，I(p)为窗口中心像素的灰度值；I(p′)为中心点以外的像素灰度。左右两个窗口进行Census变换后，计算汉明距离表征相似度，即将这两点的Census编码逐位进行异或运算，结果为1的个数就是汉明距，汉明距越小，两点相似度越高。依次寻找图像中每一点的匹配点，完成匹配[5]。

2 自适应权重SAD-Census算法

2.1 自适应权重的SAD算法

传统的SAD算法中，求得每个窗口对应位置的像素灰度差的绝对值后，直接累加获得SAD值，即窗口中的每个位置求出的灰度差绝对值都是等权的。但在实际情况中，距离中心点越远的像素，与中心点的相关性越小，因此本文将邻域像素点到中心像素点的几何距离作为权重因子来求取SAD值，然后再进行匹配。在比较多种函数形式之后，发现正态分布比较合适，故权重W取正态分布形式，如下

W=e-kf2

(3)

式中，f为邻域像素点到中心点的几何距离；k为与窗口大小有关的系数。经试验分析，得到k的表达式如下

(4)

式中，a为窗口大小。权重W既与距离有关，也与窗口大小有关。以9×9大小的窗口为例，其权重W的特性曲线如图2所示。

图2 9×9的窗口权重曲线

图2中以0为中心点，横坐标代表邻域像素与中心点的距离(以像素为单位)，纵坐标代表权重值。可以看出越靠近中心点，权重W数值越大，即该点的参考价值越大。

2.2 自适应权重的SAD算法与Census算法的融合

Census具有灰度不变的特性，即编码与像素灰度值具体数值关联不强，只与像素之间的大小关系有关，保证了它对曝光或光照不同的两幅图像的匹配有一定的稳健性。但这种算法整体误匹配较多，要解决这个问题，就需要加入更多信息来辅助计算，因此考虑将一部分图像像元的灰度信息加入Census匹配中。SAD算法是基于图像像元灰度值的匹配算法，而自适应权重的SAD算法理论上比传统SAD算法匹配效果更好。因此，针对两者可以相互补充的特点，将Census算法与自适应权重的SAD算法进行融合：在分别求取改进后的SAD值与汉明距后，将两者加权求和，得到新的相似度数值C，C的求取方式如下

(5)

式中，CCensus表示汉明距；CSAD表示SAD值；a表示窗口大小。窗口大小对CSAD和CCensus值影响很大，将窗口大小引入公式，目的是保持两者的权重关系。取指数的目的是归一化，CCensus与CSAD的取值范围可能会相差很大，这样便有必要将两者都归化到[0,1]区间，使计算出来的C值更可靠。

2.3 自适应权重SAD-Census算法流程

自适应权重SAD-Census算法流程如图3所示，可基本概述如下：

(1) 输入图像对，以左图像为参考图像、右图像为目标图像，运用算法依次寻找匹配点对，匹配点对在左右图像上的横坐标差值即为以像素为单位的视差值，逐一匹配得到稠密的视差图。

(2) 以右图像为参考图像、左图像为目标图像，运用算法依次寻找匹配点对，得到另一幅稠密的视差图。

(3) 对两幅视差图进行左右一致性检验，对遮挡点进行补充(由于两张图像拍摄的视角不同，被遮挡的部分也不尽相同，因此两幅视差图存在不一致的地方，有必要对这些地方进行一致性校验并赋值[7-8])。

(4) 进行中值滤波，得到优化后的视差图。

图3 自适应权重SAD-Census算法流程

3 试验结果与算法评价

为了评价本文匹配算法的准确性，基于VS 2013开发环境，采用C++语言实现了传统SAD算法、传统Census算法与自适应权重SAD-Census算法，分别对无亮度差异的图像组和存在亮度差异的图像组进行匹配处理，并分析比较匹配结果。

3.1 基于无亮度差异的图像对试验

首先利用Middlebury平台提供的3组无幅度失真图像Tsukuba、Teddy和Cones进行试验，原始图像和理想视差图如图4所示。

图4中，第一、二、三行分别是Tsukuba、Teddy和Cones图像，(a)、(b)、(c)列分别是原始图像组中的左图、右图和理想视差图。

图4 原始图像组和理想视差图的匹配结果

对3组试验样本分别采用传统SAD算法、传统Census算法和自适应权重SAD-Census算法进行匹配，视差结果如图5所示。

图5 基于无亮度差异的图像对的匹配试验

图5中，(a)、(b)、(c)列分别是采用传统SAD算法(窗口大小为9×9)、传统Census算法(窗口大小为23×23)和自适应权重SAD-Census算法(窗口大小为19×19)对3组样本进行匹配得到的结果，其中采用的窗口均是各自算法中最优窗口(窗口大小的确定：在各自算法内，依次用多个大小的窗口进行匹配，匹配结果最佳时，其对应的窗口即为此算法的最优窗口)。

将3种算法获取的最佳视差图与理想视差图作差，差值超出阈值的标记为误匹配，采用误匹配率量化匹配质量，误匹配率越小，匹配效果越好。试验样本的误匹配率结果见表1。

表1 无亮度差异的图像匹配结果的误匹配率 (%)

几种算法运算时间的比较见表2(以SAD算法Tsukuba图像匹配用时作为衡量标准)。

表2 无亮度差异的图像匹配所需时间比较

从匹配质量上看，相对于传统SAD算法和传统Census算法，自适应权重SAD-Census算法匹配的效果更优质。从运行效率上看，传统SAD算法效率较高，自适应权重的SAD-Census算法与传统Census算法效率相近。

3.2 基于亮度不一致的图像对的试验

通过只改变目标图像的亮度构建了3组新的试验样本(对Tsukuba、Teddy和Cones 3组原始图像中的右图提高整体亮度，左图不改变，调整之后的左右图像形成新的试验样本)，对这3组新样本进行试验，视差结果如图6所示。

图6 基于亮度不一致的图像的匹配试验

图6中，(a)、(b)、(c)列分别是采用传统SAD算法、传统Census算法和自适应权重SAD-Census算法对3组样本进行匹配得到的结果(各算法均采用最优窗口)。直观来看，对于存在亮度差异的图像对，传统的SAD算法误匹配严重，得到的匹配结果几乎不能分辨出目标物，传统Census算法和自适应权重SAD-Census算法相比较而言呈现的结果较好。3种算法匹配结果的误匹配率见表3。

表3 基于亮度不一致的图像匹配结果的误匹配率 (%)

从误匹配率结果来看，当待匹配的左右图像亮度存在差异时，3种算法中的传统SAD算法效果最差，几乎不能达到匹配目的，传统Census算法与自适应权重SAD-Census算法结果较稳定。

3.3 实拍图像试验

为了验证算法的实用性，在实际场景中拍摄左右图像，采用3种算法进行处理。其中，在拍摄左右视角的图像时，采用不同的测光点，使左右图像的亮度不一致。匹配结果如图7所示。

图7 基于真实场景的图像匹配试验

图7中，(a)、(b)、(c)、(d)分别是原始图像的右图和分别采用传统SAD算法、传统Census算法、自适应权重SAD-Census算法匹配得到的视差图。对比结果可以发现，自适应权重SAD-Census算法得到的视差图效果优质，且呈现的深度信息与实际情况保持一致，表明自适应权重SAD-Census算法在实际情况中可以适应，对亮度有差异的图像也有较好的稳定性；瑕疵之处是在纹理不丰富的区域存在一些误匹配。

综合以上3个试验的结果，可以得到如下结论：传统SAD算法效率高，但对于存在亮度差异的左右图像，其匹配效果很差；传统Census算法对于存在亮度差异的左右图像，其稳健性较好，但整体匹配精度不足；本文提出的自适应权重的SAD-Census算法，匹配精度优于传统SAD算法与传统Census算法，在面对存在亮度差异的左右图像时，也可以保持较好的稳健性，在实际场景中，该算法也可以较好地实现其功能。

4 结 语

本文将改进的SAD算法与传统Census算法融合，提出了自适应权重的SAD-Census算法。经过对比试验可以发现，本文提出的自适应权重SAD-Census算法，在精度上要优于传统SAD算法和传统Census算法，且能有效地减弱由光照或曝光不同所引起的图像亮度不一致对匹配结果的影响，但对于图像中的弱纹理区域的匹配，本文算法仍需要进一步优化。