韩剑辉　吴振　李兰英

摘要：针对区域匹配算法在灰度变化比较大区域精度不高的问题，提出一种改进的匹配算法，利用sobel算子计算各像素点的梯度值，根据梯度幅度直方图获得自适应阈值，动态建立支持窗口，改进传统的Census变换，用窗口内所有像素均值代替中心像素进行Census变换，在左右图像中寻找最佳匹配点获得视差图，利用FPGA并行处理和硬件实现的优点，对大数据量实时地进行处理，提高运算效率，实验结果表明：改进的立体匹配算法和硬件结构能够获得精度较高的视差图，处理640×480的图像对只需32.4 ms，

关键词：立体匹配；Sobel算子；自适应阀值；Census变换；现场可编程门阵列

DOI：10.15938/j.jhust.2016.04.005

中图分类号：TP391

文献标志码：A

文章编号：1007-2683（2016）04-0025-05

0引言双目立体视觉是计算机视觉技术研究领域的热点问题，立体匹配是实现立体视觉的重要环节，匹配结果的精度则是制约立体视觉技术发展的瓶颈，立体匹配的算法大致可以分为全局匹配算法和局部匹配算法，其中区域匹配算法由于能够直接获取视差信息，算法复杂度也相对较低，因而广泛地应用在实时立体视觉系统的设计中，

区域匹配算法的性能很大程度上依赖匹配窗口的建立和相似性测度函数的选择，文根据分割区域动态选择窗口的形状和大小的方法得到了较好效果，但对于复杂纹理图像，无法做到较精确的色彩分割，Yoon和Kweon 利用像素间光度学和几何学关系调配窗口中像素的权值，本质上类似于分割的思想，但却回避了分割难题，此方法不依赖初始视差估计，同时在深度不连续和连续区域得到精确匹配，但其高时间计算复杂度问题有待解决，常用的相似性测度函数有像素灰度差的绝对值和（sumof absolute differences，SAD）、及像素灰度差的平方和（sum of squared differences，SSD）、以及非参数化方法的Rank变换和Census变换SSD、SDA算法容易受光照不均及遮挡问题的影响导致匹配误差增大，Rank变换的思想类似滤波器，通过待匹配点与特征窗内各点灰度差，定义灰度等级Zabih把等级变换算法推广到Census变换，通过编码像素间的等级信息保留其空间分布，用加权平均编码信息匹配图像，由于这种方法依据灰度排序方式，提高了算法的鲁棒性，但同时增加了窗口图像信息的维度，计算更加复杂。

虽然上述算法已经能够极大改善区域匹配的性能，但是对于存在灰度变化比较大区域的图像会出现视差图过渡平滑的现象，而且算法复杂度都比较高，难以满足立体视觉系统高速、实时的要求，本文结合边缘检测，利用Sobel梯度算子、梯度幅度直方图和Census变换改进基于传统Census变换的区域匹配算法，并且借助现场可编程门阵列（field pro—grammable gate arrays，FPGA）开发专用的硬件并行处理系统实现该算法，

1.算法描述

1.1梯度幅值计算

Sobel是一阶导数边缘检测算子，是一种有效的梯度计算方法，具体方法是通过3×3模板作为核与图像中的每个像素点做卷积和运算。

利用Sobel算子计算图像中一点的梯度幅值，需要以该像素点为中心建立一个3×3的窗口，然后将窗口内所有像素分别与两个核做卷积获得水平分量G_x和垂直分量G_y如式（1）～（4），

1.2自适应匹配窗口

匹配窗口尺寸的选取对于立体匹配至关重要，窗口太小，包括的图像信息过少，不足以表达出区域的特征，导致误匹配；窗口太大，则违背了匹配窗口内的像素的视差值是一致的假设，无法区分场景中物体和其背景，同时匹配速度也降低在实际匹配中，匹配窗口的大小需要随着图像像素灰度的变化而改变，以提高匹配的精度，

一般在像素灰度变化比较大的区域，对应的像素梯度值变化也比较剧烈，视差变化也不连续，匹配窗口大小应该设置得比较小；而对于梯度值较小的区域，往往是低纹理区域，此处匹配窗口应该设置得比较大，因此需要动态调节匹配窗口的大小，本文采用双阈值确定匹配窗口的大小：选定两个梯度幅值阈值，一个较高G_h另一个较低G_l；设定匹配窗口的尺寸标准分别为D₁、D₂、D₃（D₁>D₂>D₃）；当梯度幅值G（x，y）>G_l时，匹配窗口的大小为D₁×D₂；当梯度幅值G（x，y）3×D₃；其他情况时，匹配窗口大小为D₂×D₂

分析梯度直方图得出阈值的计算方法，自适应地动态生成阈值，克服人为设定阈值的不足，

根据梯度直方图可知，阈值的选择问题实际上即为在梯度幅值直方图中找出灰度变化平稳的区域的尖峰与第一个灰度变化较大区域的尖峰之间的平滑区域，阈值可以选取为此区域内任意一像素的梯度幅值，为了找到这段区域，对梯度幅值的相邻两点作差分，即

1.3改进的Census变换

Census变换属于非参数相似测度因子，基本思想是用一个矩形窗口遍历图像，把窗口内中心像素的灰度值作为参考值，将窗口内其余像素依次与参考值比较，灰度值小于参考值的像素点记为1，大于或等于参考值的像素点记为O，然后按位连接输出一串二进制代码。

式中：W（p）为以像素点P为中心的匹配窗口；I（p）为像素点P的灰度值，，（p）为W（p）内除像素点P以外任意一点的灰度值；表示按位连接，矩形窗口W（P）的尺寸是根据中心像素点的梯度幅值和梯度阈值比较之后确定的，函数E（X，y）定义为

但是传统的Census变换过于依赖中心像素，当图像受到干扰，中心像素发生畸变，就会增大误匹配的几率，本文用矩形窗口内所有像素值的平均值替代中心像素值，仍然按照式（8）、（9）进行变换，这样增强了Census变换的抗干扰能力，

将两幅图像的匹配窗口中的所有像素进行改进的Census变换得到两串01代码，利用Hamming距离公式计算两比特串之间的差异，Hamming距离越小则说明两点的匹配代价越小，两个像素点越相似匹配代价计算如下：式中：（x，y），）表示像素点的坐标值；w表示以点（x，y）为心中的邻域；I_r（x，y）表示在左图中像素点（x，y）的灰度值；I_r表示右图像素的灰度值；XOR表示异或运算；d表示视差，

2.算法描述

FPGA完成图像数据的存取、梯度计算、自适应阈值的计算和立体匹配，算法模块的RTL视图如图1所示，

2.1缓存窗口设计

使用QuartusⅡ软件中基于RAM的移位寄存器宏模块ahshift_taps来实现缓存窗口的设计，宏模块altshift_taps是一个可配置的、具有抽头（Taps）输出的移位寄存器，每个抽头在移位寄存器链的指定位置输出数据，例如，对于256×256的图像，ahshifltaps模块参数设置为8bit输入、8bit输出、3抽头，相邻的两个抽头相距256个寄存器，如图2所示，其中相邻两个抽头间的距离是根据图像大小来设定的，

在工程实际中，3×3的窗口是经常用到的，Shift—RAM中存储2行数据，同时输入数据组成3行阵列，接着输入row3_data数据，机构Shift_RAM移位存储后就可以得到3×3的窗口数据阵列，移位寄存器仿真波形如图3所示，

2.2Sobel梯度鼻子

Sobel梯度算子的硬件实现可以分为图像数据缓存模块和梯度结合模块，其中，图像数据缓存模块采用移位寄存器（shift register）实现，梯度结合模块采用可编程宏模块和Verilog HDL语言相结合的方法实现，

根据卷积运算公式，可以使用QuartusⅡ软件中的可编程加法器altmult_add模块以及可编程多路并行加法器parallel add模块来实现卷积运算，将运算得到的垂直方向和水平方向的梯度值求平方和G_x2+G_y2，利用QuaausⅡ中的宏模块ALTSQRT求解

2.3自适应阈值

自适应阈值的选择是基于梯度直方图进行的，因此首先需要对经过非极大值抑制后的图像进行直方图统计，自适应阈值的产生电路如图5所示，

这些寄存器用于存储不同梯度值像素点的个数，梯度值作为寄存器组的地址，在每幅图像开始时，对这些寄存器清零，梯度值输入后，通过地址选择器，相应地址的寄存器的内容被取出来送人累加器1，加l后再写入该寄存器，直到整幅图像的所有像素点统计完毕，在时钟保持有效期内，每个时钟到来累加器2的内容自加1，累加的结果作为寄存器组的地址，相应地址寄存器的内容以及下一个地址寄存器的内容分别送人寄存器1和寄存器2，对寄存器1和寄存器2的内容按式（6）进行差分，比较器比较差分的结果是否为0，若为0则发出停止累加信号，停止累加器2的累加，此时累加器2的值即为高阈值G_h，G_h右移一位（即除以2）得到低阈值G₁。

2.4立体匹配

为了提高系统的实时性，Census模块的设计采用了以资源换取时间的并行优化方法，例如，对于7×7的局部变换窗口，Census变换模块如图6所示，将移位寄存器组扩展为8行，每一列读入8个像素数据，在窗口水平移动中，每隔8个时钟周期对Census变换窗口的数据更新一次，当Census变换窗口移至每行末尾时，便获得了相邻两行像素的Census局部变换，从资源方面分析，并行后比较器的数量增加了1倍，但移位寄存器的数量只增加了1/7，优化结果却使Census局部变换的速度提高了近1倍，运算频率由1/7（像素/周期）提高到1/5（像素/周期），

3.实验结果与分析

为了验证本文算法的有效性，将实验结果上传到Middlebury网站平台进行评估，本文算法的支持窗口分别设置为D₁=7、D₂=5、D₃=3，为了分析匹配精度，选择Middlebury网站上一些相近的算法进行比较，匹配精度比较结果如表1所示，

通过比较，ADCensus算法能够达到很低的误点率，但算法较为复杂，本文算法与SSD+ASW、Cen—BUS+ASW算法相比误匹配率要低，对比而言本文提出的算法综合考虑了算法匹配精度与实时性，达到了较好的效果。

另外，在Pc和FPGA上实现本文算法，计算两者处理同一帧640×480像素图像所用时间，比较结果如表2所示，

选择Middlebury平台中的Teddy图像作为参考图像，比较SSD+ASW、Census+ASW和本文算法的匹配结果，

由图7（b）可以看出本文算法得到的视差图较Census+ASW和SSD+ASW算法更为清晰，能够比较准确地反应图像的深度信息，

4.结论

本文提出了一种基于Sobel梯度算子和改进的Census变换相结合的立体匹配算法，并借助FPGA硬件实现该算法，经过试验表明此算法的匹配效果好于传统Census变换的算法，所获得视差图比较稠密，而且有效提高了算法的实时性，但是，在遮挡情况下，视差边缘不准确，在后续的研究中将对这一方面进行完善。