基于SAD的立体匹配算法研究

于春和，张 静

(沈阳航空航天大学 电子信息工程学院，沈阳 110136)

立体匹配是二维图像对三维场景结构信息获取的主要技术手段，一直是人们的研究热点之一[1]。立体匹配作为计算机双目立体视觉中最关键的一个步骤，其后面进行的三维重建的精度与匹配结果准确与否息息相关。所谓立体匹配就是从不同视点获得的两幅图像中找到匹配的对应点，再由匹配代价函数来估算匹配点的视差值。

20世纪80年代的研究人员提出层次处理立体匹配的概念，通过立体匹配约束条件来提高立体匹配的精确度。随着科技的发展，双目立体视觉技术渐渐走向成熟，不少研究人员把立体匹配技术与人们的实际应用相结合，比如深度的计算，场景的三维重建，虚拟现实等。双目立体匹配技术虽已经过几十年的研究且已经取得了一定的研究成果，立体匹配的准确率还是会受到图像无纹理区、物体之间的相互遮挡、镜头畸变、光照变化及相机特性等各方面因素的影响，这些因素都被综合到了图像的灰度值中。因此，想要精准地对存在这么多不利因素的图像来进行无歧义的匹配是一个困难的过程[2]。为了使立体匹配的有效性得到提高有三个问题需要解决，即匹配特征的选择要正确，找出特征间的匹配属性并且建立能够准确的匹配所选特征的稳定算法[3]。目前，围绕以上所提到的三个方面展开研究的匹配方法有许多种，最具代表性的有区域相关法[4]、动态规划法[5]、和基于图论的最小切割方法[6]。但是还有好多立体匹配所涉及的问题没有得到妥善解决，尤其需要进一步深入研究在复杂场景中如何去提高匹配算法的准确率。

局部立体匹配算法以及全局立体匹配算法是现阶段应用最广泛的两类匹配算法[7]。在局部算法中，灰度差累积(Sum of absolute differences，SAD)算法是常用的匹配算法，该算法匹配速度快、计算效率高，得到的视差图更适合密集型的三维重构。

1 极线校正

极线校正实质上就是图像进行匹配过程之前对图像预处理的一部分。为进一步提高匹配效率，在匹配时往往采用在同一极线上搜索两幅图中最相似点对的方法，在同一水平线上进行匹配可以达到降低搜索范围的目的。但从实际角度出发，无论如何摆放两台摄像机都不可能使光轴做到完全平行。为满足上述情况就需要两台摄像机的成像平面必须共面且完全行对准。校正后的图片使立体匹配的结果更加精准，所以要在立体匹配之前对双目图像进行校正[8]。

极线校正过程如图1所示，极线校正将双目立体视觉的几何结构校正为平视双目标准几何结构。该校正过程可分两步完成。第一步，将左右两个成像平面拉到同一平面上；第二步，左右成像平面通过绕光轴旋转使两摄像机主点连线与像素坐标的连线平行[9]，两个极点被映射到无穷远，校正后的左右成像平面水平对齐且在同一个平面上。平面上的成像点距离保持不变，类似于刚体变换。根据已经标定的两摄像机内部参数矩阵Kl和Kr以及左右两个摄像机之间的旋转矩阵R和平移向量T，那么可以将摄像机的基本矩阵F用如下公式表示为

(1)

其中，S为平移矢量的反对称矩阵，表示为

(2)

图1 极线校正过程

左右极点经过极线校正被映射到无穷远处，校正后的图像对极线方程为

(3)

其中，pl和pr分别表示空间中的一点P在左右摄像机成像平面上的成像点的坐标。

2 基于SAD算法的立体匹配

2.1 立体匹配约束准则

通过二维图像来获取空间物体的三维信息，立体匹配的本身就存在一些不确定性，为了使得到的匹配结果能够相对准确，需要借助各种约束条件来缩小匹配的搜索程序任务量，同时提高匹配的精确度。约束准则常用的有以下几种。

(1)极线约束

极线约束就是指同一空间中的实物点在左、右两幅成像平面上的映射。三维场景中的一点P投影到两个不同摄像机成像平面，投影点分别为Pl、Pr。定义左、右摄像机的光心分别为Ol、Or。由P、Ol和Or三点构成的极平面与摄像机成像平面的交线为极线。由此可以确定与左图映射点Pl对应的右图映射点Pr一定在右极线上，二维搜索降为一维搜索，这样降低了匹配的复杂程度[10]。

(2)图像一致性约束

由于左右两摄像机的位置和成像条件不同，景物被拍摄过程中所得图像中的对应点可能存在一定的差异。但若两幅图像中的点是来自同一空间实物点的影像，则图像区域的灰度变化情况以及几何结构都是相同的，由此可以确定对应的匹配点。

(3)唯一性约束

由成像原理可知，空间中的任意一点在成像平面上只有唯一的点对应。唯一性约束对匹配过程起到简化的作用。即在匹配图像上的任意一个匹配基元在待匹配图像上有且仅有一个匹配基元与其相对应[11]，这样每个匹配基元至多得到一个视差值。

(4)连续性约束

三维空间的某一被拍摄物体在拍摄时其自身的信息经过透视映射到了成像平面上，且成像过程不会影响每个特征点的位置关系，也就是说物体表面上相邻的两点在成像平面上的投影点也是相邻的关系。例如：P和Q是相邻两点且分别在成像平面上对应的匹配点为P′、Q′。已知P和P′是对应匹配的关系，则作为相邻点Q的匹配点Q′与P′一定也是相邻的关系。

约束条件可在一定程度上限定对应点的搜索范围，减少匹配中的歧义性。

2.2 SAD算法原理

在双目立体视觉的众多匹配算法当中，灰度差累积(Sum of absolute differences，SAD)算法是基于灰度的模板匹配算法。具有运算速度快、实时性好等优点，可以较好地满足多数双目立体视觉系统的需求[12]。该算法的中心思想是把左右图像中匹配点对应灰度值的差取绝对值再进行累积求和，计算得到的结果可对左右两个图像块的相似度进行评估。

针对双目立体视觉系统同时采集的图像对，经过极线校正处理后是水平的，即图像对的外极线平行。同一空间点在左右成像平面上得到的两个像点其y轴坐标一致。局部立体匹配算法需要建立窗口来完成匹配，用窗口中的多个像素灰度值来表征中心点，逐一选取像素点邻域内的一个子窗口与参考窗口进行比较，用相似性测度函数的计算值来评价两个窗口的相似度[13]。当某个子窗口与参考窗口最相似时，即认为这个窗口的中心点与待匹配点是对应点对。对每一个像素点进行处理，即可完成两幅图像的匹配。匹配窗口的构建如图2所示。其中，Wl、Wr分别表示所构建尺寸大小为M×N的匹配窗口和待匹配窗口，两窗口的中心点坐标分别为(x0,y0)、(x0-d,y0)。Pl、Pr分别表示左摄像机拍摄的参考图像以及右摄像机拍摄的待匹配图像。SAD窗口匹配算法在匹配窗口Wl与待匹配窗口Wr中分别统计对应位置窗口内的像素灰度值差的绝对值，在不超出所给定的视差范围内对所有待匹配点构建的匹配窗口进行遍历。

图2 匹配窗口示意图

如图3所示，通过滑动窗口来完成立体匹配。取dmax为可承受的最大视差值，则搜索范围为[0,dmax]，也就是只需在横坐标为[x,x+dmax]的范围内进行搜索。对目标图进行匹配的过程为在视差范围沿着极线依次选取点作为M×N匹配窗口的中心点，在视差范围内对所有待匹配点构建的匹配窗口进行搜索，筛选出邻域灰度信息最相似的点作为最佳匹配点。SAD是其中的一种相似性测度函数，表达式为

(4)

其中d为该点的视差值，W表示支持窗口.使CSAD结果最小的待匹配窗口视差值d就是投影点(x0,y0)的最佳视差值。

图3 模板遍历过程

匹配计算必须有合理的相似性测度指标。满足匹配的准确性和计算效率的要求。相似性测度在不同的算法中具体形式有所不同，但多数立体匹配算法可将相似性测度归纳为一种求解匹配代价函数形式[14]。常用的匹配代价函数还有MAD、SSD、NCC等。

平均绝对差算法MAD具有匹配精度大的优点，但是运算量大、对噪声比较敏感。其计算原理如下

(5)

误差平方和算法SSD与SAD算法步骤大体一致，差别在于SSD将所得的像素差平方运算之后再进行累加。表达式为

(6)

归一化积相关算法NCC定义了归一化相关系数，计算公式为

(7)

归一化相关系数R(i,j)的值域范围为[-1,1],也就是说相关系数越接近于1，两幅图像中对应区域块越匹配。以上提到的三种匹配算法在匹配过程中与本文所研究的SAD匹配算法思路比较类似，主要区别在于判别函数。其中，NCC算法公式相对复杂，而且计算量比较大。

3 匹配过程

立体匹配分为匹配代价计算、匹配代价累积、计算视差、视差精化四个步骤。

匹配代价通常是通过对左右两幅图像对应像素的灰度值差计算来决定的，一般通过构建目标函数或能量函数，能使目标函数最小化的即为最佳匹配结果。在匹配代价计算得到的三维视差空间图像内搜索到的匹配代价最小视差值就是理想视差。

匹配代价积累就是采用窗口卷积对每一幅代价图进行聚合以达到局部滤波的目的。上一步的代价计算得到了全部像素对应的视差值，但是这些视差值都是孤立存在的，有大量噪声被引入。

常用WTA(Winner-take-all)算法对基于区域的立体匹配进行视差值的计算[15]。根据左右两幅视图的差异可分为特征点和非特征点，对视图中的特征点进行WTA计算，视图中的非特征点只进行简单的验证，不仅运算量减少了，还能得到致密的视差图。

所谓视差精化就是对所得的视差结果进行优化的过程。常用的处理方法有遮挡处理、左右一致性检测、中值滤波等。经过此类方法优化后基本都能使最后的视差结果提升约1%。

匹配实现流程如图4所示。首先从输入的图像中获取数据信息，对左侧图像进行扫描并选定一个锚点。接下来构造一个固定矩形匹配窗口并设置它的大小，进行匹配代价聚合，即求出所有像素点灰度差绝对值之和。最后在右侧图像上进行视差筛选，选出相似性最高的匹配点，即找到左视图锚点的最佳匹配像素块。

4 实验结果与仿真

通过相机标定得到左右相机的内外参数信息，将此参数结果写入MATLAB校正程序的参数矩阵中来对采集的图像对进行校正，校正后的结果图如图5，图6所示。

基于区域的匹配算法所得视差图效果与匹配窗口尺寸密切相关。随着窗口尺寸的调整，匹配效果发生了很大的变化。尺寸过大会有更大的几率包含深度不同的目标，但在深度不连续区域的表现下降；尺寸过小的窗口会因为不能包含足够的信息以抵抗随机噪声的干扰而产生较多的错误匹配点。

为了评价本文匹配算法的准确性，基于VS2010开发环境，采用OPENCV3.3.0编写程序实现传统SAD 算法对校正后的图像对进行立体匹配，并对不同的窗口大小进行试验，得到元素值为视差值的图像，即视差图[16]。显示结果如图7所示。

图5 采集的图像对

通过以上的对比实验可直观观察到，SAD算法进行的立体匹配得到的视差图效果随着窗口尺寸的调整，发生了很大变化。当窗口尺寸小于3时边缘区域很大的程度被模糊了。窗口尺寸为4～6时，视差图效果较好。窗口尺寸大于8时，产生了很多的错误匹配点。

图6 校正后的图像对

图7 不同匹配窗口下的视差图

经过实验测试，当窗口尺寸设置为4×4时，得到的视差图效果最佳。图中存在的瑕疵之处是在纹理不丰富的区域发生一定的错误匹配，故本文算法还需要进一步的研究和优化。

5 结论

立体匹配的速度和所得结果的精度受多种因素影响。现阶段，还尚未有能够完整处理立体匹配的整个流程的算法[17]。本文所述的SAD(Sum of absolute differences)算法主要针对立体匹配中图像块匹配这一步骤，对局部有明显特征的特征点匹配更准确。用SAD算法进行的立体匹配，得到的视差图具有较好深度感，为下一步的三维重建打下了坚实的基础。