基于降采样聚类的双目图像测距算法研究

李先真，张大波

(辽宁大学 信息学院，辽宁 沈阳110036)

0 引言

据国家统计局分析，中国民用汽车保有量已经突破两亿，智能交通和辅助驾驶技术已经成为目前的研究热门，而测距是辅助驾驶技术的重要研究分支.现有的测距技术有很多，如：视觉测距、超声波测距、激光测距、红外线测距等.与其他测距技术相比，双目视觉测距具有实现简单、成本低廉、鲁棒性强、获取信息量大，抗干扰能力强等优点，因此成为近年来的热门研究方向.

双目视觉测距一般情况按如下步骤进行：摄像机标定、图像获取、图像预处理、立体匹配、获取视差图.其中立体匹配的准确度将直接影响视差图的精确程度，因此成为视觉测距算法中的核心研究课题.自20世纪70年代M IT的Marr提出了完整的双目视觉体系框架[1]起，立体匹配算法开始系统而高速的发展.目前的立体匹配算法主要分为两类：全局立体匹配算法和局部立体匹配算法.

全局立体匹配算法通过运用图像整体特征，建立全局能量函数，通过求能量函数的最小值来寻找最优视差值.全局立体匹配算法准确性较高，但是由于图像一般数据量较大所以全局算法效率较低.文献[2]提出了一种基于的动态规划立体匹配算法，减少了全局算法的复杂度并减轻了传统动态规划算法导致的视差图条纹现象；文献[3]提出了一种基于图像分割的立体匹配算法，可以获得较为平滑的视差图；文献[4]提出了一种基于置信度传播的立体匹配算法，降低了硬件实现的复杂度.文献[5]为了提高全局算法的效率将全局算法与局部算法融合，提出了一种基于半全局的立体匹配算法，取得了较好地效果.

局部立体匹配算法是通过局部特征对应或窗口对应的方法来计算匹配代价，通过代价聚合来求出最优视差值.由于局部立体匹配算法一般只考虑图像的局部信息，算法的效率较高，但是在弱纹理或者深度间断区域会出现误匹配现象.文献[6-7]通过窗口内像素点的颜色特征来计算匹配代价，对光照变化有较好地鲁棒性，但是在弱纹理区域效果不理想；文献[8-9]通过SIFT算法对图像的sift描述子进行匹配来计算最优视差值，可以较好地保存图像的几何特征.

立体匹配算法的速度和精确度的平衡是本文研究的重点，本文提出了一种基于降采样Census算法的局部立体匹配算法，通过缩小图像尺寸的方式在尽可能保留视差特征的基础上极大的提高算法运算速度.适合在对速度要求高，场景空间较大，对细节测量要求较低的情况下使用，如交通图像、无人机航拍图像等.获取视差图之后可以通过进一步对尺度缩小的图像进行处理以提高匹配的准确的，同时不会对效率产生过高的影响，

1 基本原理

双目视觉体系通过左右摄像机所拍摄图像中同名像素点(代表相同实际物体的像素点)之间的视差来计算深度.测量原理如图1所示：

图1 双目测距原理示意图

在理想情况下，两个摄像机主光轴平行，且成像平面于同一平面上.实际物体P与光心所在距离为Z，l为镜头平面即是摄像机成像坐标的XoY面，焦距为f，两光心之间距离为T，则根据相似性原理有[10]：

其中d＝x1+x2，即左右图像中同名像素点的视差.因此只要找到图像中的同名像素点，并求出起视差，即可计算出Z，即物体与摄像机之间距离的值.

因此，双目视觉测距核心就是立体匹配，立体匹配具体可分为四步：代价计算、代价聚合，视差优化、获取视差图.本文提出了一种基于降采样Census算法的局部立体匹配算法，并在代价聚合中采用WTA算法的同时使用Meanshift算法将视差聚类，以获得更加准确平滑的视差图.

图2 算法流程

1.1 降采样Census算法

通常局部立体匹配算法，受到窗口大小和局部噪声的影响，在弱纹理区域和噪声区域无匹配现象较为严重.常用的窗口对应代价计算算法有：灰度差绝对值之和SAD，灰度差平方之和SSAD、Census算法、归一化互相关等.

Census算法：传统Census算法是一种典型的通过窗口内颜色特征来计算匹配代价的算法，Census算法不关心具体灰度值，只考虑窗口内灰度值之间的关系，因此对光照变化不敏感.Census算法首先使用窗口遍历左右图像，对每个像素进行编码，形成Census串.如图3，A为当前像素点(常用窗口中心点)的灰度值，Ai为A的邻域窗口q内像素点的灰度值.其中

图3 Census算法实例

然后通过计算串之间的汉明距离来计算匹配代价，即：

distance＝⊕(Cenl⊖Cenr)

其中，⊖代表按位相减，⊕代表按位相加，Cenl和Cenr代表左右图像的Census串.

传统Census对光照变化不敏感，匹配较为准确.然而，由于Census算法需要对图像每一个像素点进行一次编码，而且为了保证匹配精度扫描窗口不宜过小，导致Census算法速度较慢.因此本文提出了一种基于降采样[11]的Census算法，可以较好提升算法的运算速度.

使用窗口q(w×w)遍历图像，遍历步长为w，按照Census算法的规则形成Census串.Census串矩阵计算方法如下

Cen(i，j)＝⊗ ⊗λ[A(ih，jk)，avg]

其中⊗代表按位连接，avg代表窗口内像素点灰度平均值，使用窗口内像素点灰度平均值来代替传统Census算法中窗口中心的点，以减弱噪声点的影响[13].

图4 左图为传统Census算法右图为降采样Census算法

根据Census算法的原理，编码过程与代价计算过程独立，同时编码对每一个像素点(像素区域块)独立，因此可以通过多线程和边缘计算的思想进一步提高算法运算速度.本文实验中是将两幅图像的编码过程并行进行，同时在施加极线约束之后，认为左右匹配点都在极线上，因此获得一行编码便可立即进行立体匹配.如此可以将运算速度继续提高.但不足之处在于由于匹配代价只在极线上计算，会导致横条纹现象.

1.2 代价聚合

在代价计算之后，需要确定最佳视差.在全局立体匹配方法中，视差选择能量函数取最小时的视差值，因此不需要进行代价聚合.局部立体匹配方法，通常只考虑局部特征，容易受到噪声和误匹配影响，单个像素点的视差实用性不高，需要通过代价聚合进一步优化视差.

本文使用贪心算法，来进行初步代价聚合.贪心算法选择匹配代价最小时的视差，同时增加了噪声容限以减少误匹配率.其优点是实现简单，计算速度快，但是缺点是局部算法固有的缺点导致精确度下降，对噪声点处理能力较弱[14].考虑到视差图像在同一物体内的连续性和不同物体之间存在较大灰度差，本文使用聚类算法对初步匹配代价进一步处理.

考虑到由于视差图灰度变化的不确定性，无法提前确定聚类中心，本文使用Meanshift算法来进行聚类[15].Meanshift算法是一个迭代的过程，其核心步骤是不断更新Meanshift向量：

其中G(x)是一个单位核函数，w(xi)≥0是一个赋给采样点xi的权重，本文中取其最简单的形式，即

算法步骤：

(1)开始迭代，给定初始聚类中心，n为迭代次数，初值为0，m为聚类中心序号，初值为1，容限误差为ε，令

(2)计算mh()，把mh()赋值给.

(3)如果‖mh()-‖≥ε，迭代次数加一，n＝n+1，返回(2).

(4)即为第m个聚类中心，图像中像素点灰度为f(x)，如果‖f()-f(x)‖＜δ，则将该点标记为m，并令f(x)＝f().

(5)如果图中还有未标记点，令m＝m+1，从图像中未标记的像素点中给定新的初始聚类中心，令n＝0，返回(2).

(6)结束迭代.

图5 左图为聚类聚类之前效果右图为聚类后效果

图5即为初始代价聚合结果，和聚类之后的结果.虽然Meanshift聚类算法较为复杂，但是由于降采样导致视差图尺寸极大缩小，聚类算法耗时被大大降低到可以接受的地步.

2 实验

本文实验使用使用用来自KITTI数据库的实际道路图像(375×1 250)进行实验.电脑处理器是i5-7 300 HQ，显卡是英伟达GTX1050Ti，实验平台是MATLAB.Census算法和SAD算法的消耗时间是通过MATLAB单线程操作运行时长获得的.本文算法的耗时是通过MATLAB单线程并行操作来模拟多线程所消耗的时间.以下表格是几种常见立体匹配算法效果的对比和时间复杂度分析.公认的立体匹配精确度指标是误匹配率，其计算公式如下：

其中dc(x，y)是通过匹配计算所得视差，dT(x，y)是真实视差值，δ是允许误差阈值，N是图像素总数，即计算误差点占全图点的比例.这里采用无效点(dc(x，y)＝0)和奇异点(在四个方向上dc+1(x，y)-dc(x，y)＞δ)和误匹配点(｜dc(x，y)-dT(x，y)｜＞δ)作为误差点来计算误匹配率.

表1 三种算法匹配精确度和时间复杂度对比

表中算法时间复杂度以比较操作为基准操作，其中M×N代表图像尺寸，d代表检索距离.

图6是使用用来自KITTI数据库的实际道路图像(375×1 250)进行实验.图6(a)是使用SAD立体匹配算法获得的视差图，图6(b)是使用Census算法获得的视差图，图6(c)是使用本文算法获得的视差图.图6(d)是原始图像.每种算法随机选取三幅图像作为代表展示实验效果.

图6 三种算法使用K ITTI数据库图像匹配效果及原图

表2 三种算法使用K ITTI数据库图像匹配效果

图7所示的是三种算法在不同尺度图像上的运行时间.横坐标为图像尺寸(单位：像素像素)，纵坐标为运行时间(单位：s).从图表中可以看出本文算法在时间效率上远远高于其他两种传统算法.

图7 三种算法时间随图像尺度变化图(单位：秒)

3 结论

综上所述，基于降采样的Census算法可以极大的提高传统算法的运算速度，并同时可以提高后续处理的速度，同时保证一定的的匹配准确率.但是由于图像尺寸缩小会导致细节的丢失，因此本算法适用于尺寸较大的空间测距，例如交通道路图像，而且由于视差图尺寸较小导致平滑处理对边缘影响较大，破坏了边缘的连续化.后续将对算法进一步优化，寻找更好保持细节和边缘的算法.