双目立体相机中实时匹配算法的FPGA实现

单 洁，唐 垚，姜 晖

(西安邮电大学通信与信息工程学院，陕西西安710121)

1 引言

随着机器视觉的发展，立体视觉系统得到越来越广泛的应用［1－2］。双目立体相机采用两台相机，模拟人眼成像原理，先通过寻找两个相机中图像对应点的光学，得到各个点处的视差，再根据视差信息和相机的投影模型恢复出原始景物的深度信息。所以，在通过立体相机计算场景信息的深度过程中，图像获取、相机标定、图像匹配和三维重建成为了关键技术。

根据匹配基元的不同，图像匹配可分为区域匹配［1－2］、特征匹配［1］和相位匹配［2－4］。其中，区域匹配以区域相似度为匹配基元，基本原理是在基准图上选取一个模板窗口，在配准图上选取同样大小的一组窗口，再将这些窗口与基准图中的模板窗口进行相似度比较，找出与模板窗口最相似的窗口，那么该窗口的中心点就是模板窗口中心点的匹配点，两点的横坐标差即为视差［1］。

区域匹配直接利用图像的灰度信息，实质是利用局部窗口之间灰度信息的相关程度，并能取得致密的视差场。区域匹配适用于具有明显纹理特征的图像，可以直接获得稠密的深度图，但区域匹配选取一定大小窗口内的灰度分布特性作为匹配基元，决定了该算法具有以下局限性［5］:(1)计算量大;(2)对左右两幅图像中光照不均匀较敏感，在这种情况下容易造成匹配困难;(3)匹配窗大小难选择。窗口选择过大，在高度间断处会出现误匹配，选择过小，区域内的灰度分布特性未得以充分展现;(4)对于视差不连续处的情况，如物体边缘附近的区域，适应性较差。文献［6］、［7］提出了在FPGA上基于SAD匹配准则的算法实现。基于FPGA实现图像匹配算法，能够充分发挥FPGA的特点，利用流水线和并行计算技术，提高运算效率和系统的吞吐率，解决了计算量大的问题，达到实时处理的要求。针对区域匹配对因亮度变化、噪声等因素引起的幅度失真非常敏感的问题，先后有文献提出了对幅度失真不敏感的匹配代价，其中主要有归一化互相关(NCC)、互信息和 Rank、Census 非参数变换［8］等。Hirschmulle通过大量实验发现:基于Census变换的匹配代价对图像中的噪声和亮度不一致性有很高的鲁棒性，能获得更优的视差结果［9］。文献［7］采用基于Census变换的匹配算法实现了图像匹配的实时处理。此外，传统的固定窗口存在变换窗口大小的选择问题，若窗口太小，则匹配代价区分度过低，在低纹理区域容易出现误匹配;若窗口过大，又会在深度不连续区域出现误匹配。文献［10］提出了基于Census变换与自适应窗口的局部匹配算法，对幅度失真具有良好的鲁棒性。但是，经过研究表明，Census变换由于丢弃了图像色彩信息而仅保留了像素间大小关系，容易造成误匹配［11］，文献［12］提出了多相关窗口的匹配方法。

本课题主要应用双目立体相机进行障碍物检测，不仅要求对数据的正确性，还要求算法需要较低的复杂度，同时还要具有较好的鲁棒性，处理好噪声、目标区域低纹理、遮挡和图像边界不连续等问题，实现最佳的立体匹配效果。为了解决区域匹配的局限性，对立体匹配算法的进展进行了研究，利用Census度量算法的特点，结合文中具体立体相机的硬件结构，提出了一种基于FPGA的并行实时Census变换立体匹配算法。基于FPGA的算法实现结合了多窗口匹配的方法，通过左右一致性约束，实现了基于FPGA的立体图像匹配硬件结构，不仅保证了匹配精度，而且对幅度失真具有较好的鲁棒性，为下一步的三维重建及深度测量打下了良好的基础。

2 算法描述

2.1 Census变换

非参数变换［8］，如 Rank 或 Census，是首先对图像进行非参数化变换，提取包含局部纹理信息的描述符。Census变换通过计算点在窗口中的灰度顺序。变换以像素为中心选择一个窗口，将窗口中心像素以外的像素变换为一个比特串。如果窗口中一个像素的灰度值比中心像素大，则相应位置为1，反之，即为0。Census变换公式如式(1)(2)所示:

式中，I(m，n)为变换窗口N对应的中心像素灰度值;I(x，y)为窗口内其余像素的灰度值，函数通过对这些像素值的比较，将结果串连(Ⓧ)成比一个特向量code(m，n)，它表征了中心像素(m，n)与周围像素的灰度值的比较关系。然后再利用Hamming距计算Census变换后比特串之间的差异程度，Hamming距越小，说明两点的匹配度越高。

经过Census变换后，中心像素的灰度值被替换为一个0和1的比特串，该比特串仅与变换窗口中心像素和其他各个像素灰度大小有关，因此，Census变换对于幅度失真有着很好的抑制能力。

2.2 多相关窗口匹配

由于匹配窗口位于深度不连续的区域时会引入匹配误差，本文中相关窗口的选取采用了文献［10］提出的多相关窗口的匹配方法。当匹配窗口位于深度不连续的区域时，可以通过只采用深度连续区域的相关窗口来减小误差。如图2中(b)所示。

图1 多窗口匹配示意图

图2中(c)所示为9窗口匹配方式，其中当中心窗口位于深度不连续的区域时，左右两幅图像的相关过程会存在歧义性。在这种情况下，假设中心窗口的代价值为C0，在周围8个窗口中选取的代价值最小的4个窗口，设其代价值分别为分别为C1i1、C1i2、C 1i3和C1i4，那么最终的代价值C的计算入式(3)所示。

这种方法还可以扩展为25窗口处理的模式，如图2(d)所示。可以看出，多匹配窗口可以通过通过小窗口与大窗口结合的方法以适应局部环境。采用周围小窗口可以避免在图像深度不连续的区域引入匹配误差;另一方面，选用较大尺寸的相关窗口可以减少在弱纹理区域的错误匹配。

3 硬件实现

3.1硬件整体结构

根据任务需求，双目立体相机中采用了一片FPGA进行左右两路视频数据的同步采集，预处理，在片上经过立体图像匹配算法后，通过电路中预留的USB2.0接口，将得到的视差图传输给PC机。整个相机的硬件系统包括视频接口模块，USB2.0数据传输模块和视频处理模块。整个硬件结构原理图如图2所示。

图2 基于FPGA的硬件结构原理图

在立体图像匹配时，要对两组图像做Census变换和相似度比较，在这几个步骤中，采用流水线计算方式并对左右两路图像采用并行技术同时计算，大大提高了系统的运算速度。

3.2 多窗口相关匹配法在FPGA中的实现

对于硬件实现来说，Census变换和多窗口代价值计算是基于窗口的操作，在计算之前先要缓存与窗口高度相同的图像行数。本文实现结构中采用了3×3子窗口和9个子窗口进行代价值计算的方式。首先，需要读入并缓存3行数据，然后对中间的1行数据进行Census变换，变换完毕后将Census值缓存到另一个具有3行数据大小的缓存器中，为下一步的相关匹配窗口代价计算做准备。

进行数据缓存时，假设计算的是第2行数据，在计算完当前y列的数据进行第(y+1)列数据的计算时，就可以对第1行第y列数据进行更新。同样，当计算第3行数据时，就可以对第2行数据进行同步更新。这样，Census变换的计算与图像像素采集形成了流水线结构，将以与图像输出同样的速度进行运算，达到实时性。并且在这种情况下，对于宽度为1024的8bit灰度图像来说，需要耗费的片上存储资源为1K×3=3Kbyte。

在下一个相关匹配的计算单元中，因为采用3×3的子窗口，也要首先缓存3行Census值，再进行窗口代价的计算。在这一步中，需要计算不同视差情况下，匹配子窗口中中心窗口的代价值和周围8个子窗口的代价值，并且找出其中代价值最小的4个，与中心窗口代价值进行累加。

通过以上的判决和累加后，找到代价值最优的情况，就完成了多窗口的相关匹配，也就是得到了视差值。在本文中，立体视觉试验系统将视差输出给上位机，由上位机根据此视差值和相机的标定结果，计算出实际场景中物体的景深。图3所示为FPGA中匹配算法的结构流程图。

图3 匹配算法结构流程图

4 结果分析

通过流水线技术，采用循环数据更新结构，不仅使得计算可以实时进行，还可以充分利用缓存空间，大大降低了缓存的使用量。对于一幅尺寸为N×N个像素的图像，假设相关窗口尺寸n×n，搜索视差的范围是d，直接进行块匹配计算时的复杂度为 O(N2n2d)，采用本文中的方法完成一幅灰度图像的匹配所需的计算复杂度为 O(N2d)，与窗口尺寸无关。

在Stratix II FPGA EP2S30实验板上实现了的文中提出的硬件结构，如图4所示。

图4 立体图像处理实验板

左右两路输入图像通过视频采集接口传输到实验板，经过预处理后送入FPGA进行立体视觉算法的处理。匹配的视差图像结果再通过USB2.0送给上位机，与Matlab变换的结果进行比较，实验验证了设计的正确性。图5中，图5(c)、图5(d)所示为通过硬件仿真，分别将图5(a)、图5(b)两帧图像送入实验板，经过FPGA变换后的结果。

通过与Matlab运算结果相比较，变换后的结果完全一致，验证了硬件运算的正确性。FPGA硬件结构的描述全部采用VHDL语言，可以较方便的在不同FPGA平台上进行移植。综合和分析采用了QuartusII软件，采用Modelsim进行功能仿真和时序仿真。实现1024×1024@30f/s灰度视频图像实时匹配功能，经过综合，在 Stratix II FPGA EP2S30FPGA平台中布局布线后的结果如表1所示。

图5 FPGA实现Census变换结果

表1 FPGA综合结果

5 结论

本文提出了在双目立体相机中基于FPGA实现立体图像匹配算法的一种设计。采用了改进的基于Census变换的方法，结合多窗口相关匹配和左右一致性原理，实现立体图像匹配的实时运算。设计中结合FPGA结构的特点，充分利用流水线结构和并行执行的思想，减少运算量和存储器的使用，降低了资源的使用量，提高运算速度。实验结果证明，该匹配算法结构具有较高的吞吐率和变换速度，可以工作在97.3MHz的频率下，能够实现1024×1024灰度图像30f/s的图像实时匹配。

［1］ Zhou Xing，Gao Zhi－ jun.Application and Future Development of Stereo Vision Technology［J］.Journal of Graphics，2010，04:50 －55.周星，高志军.立体视觉技术的应用与发展［J］.工程图学学报，2010，04:50 －55.

［2］ You Suya.State of the art and Future the development of stereo vision［J］.Journal of Image and Graphics，1997，01:17－22.游素亚.立体视觉研究的现状与进展［J］.中国图象图形学报，1997，01:17 －22.

［3］ Xu Yanjun，Du Limin，Hou Ziqiang.A Scale － Adaptive Phase － Based Stereo Maching Method［J］.Acta Electronica Sinica，1997，07:38 －41.徐彦君，杜利民，侯自强.基于相位的尺度自适应立体匹配方法［J］，电子学报，1997，07:38 －41.

［4］ Zitova B，Flusser J.Image registration methods:a survey［J］.Image and Vision Computing，2003，21(11):977－1000.

［5］ Bai Ming，Zhuang Yan，Wang Wei.Progress in binocular stereo matching algorithms［J］.Control and Decision，2008，23(7):721 －729.(in Chinese)白明，庄严，王伟.双目立体匹配算法的研究与进展［J］.控制与决策，2008，23(7):721 －729.

［6］ Ambrosch K，Humenberger M，Kubinger W，et al.Hardware implementation of an SAD based stereo vision algorithm［C］.Proceedings of the Conference on Computer Vision and Pattern Recognition Workshops，Minneapolis，Jun.17，2007:1 －6.

［7］ Chen L，Jia Yunde.A parallel reconfigurable architecture for real－time stereo vision［C］.Proceedings of the International Conference on Embedded Software and Systems，Hangzhou，May 25，2009:32 －39.

［8］ Zabih R，Woodfill J.Non － parametric local transforms for computing visual correspondence［C］//European Conference on Computer Vision，Stockholm，1994:151 －158.

［9］ Jin S，Cho J，Phan X，et al.FPGA design and implementation of a Real－ Time stereo vision system［J］.IEEE Transaction on Circuits and Systems for Video Technology，2010，20(1):15 －26.

［10］ Zhou L，Xu G L，Li K Y.Stereo matching algorithm based on Census transform and modified adaptive windows［J］.ACTA，2012，33:886 －892.(in Chinese)周龙，徐贵力，李开宇，等.基于Census变换和改进自适应窗口的立体匹配算法［J］.航空学报，2012，33:886－892.

［11］ Xiong G M，Li X.Color rank and census transforms using perceptual color contrast［C］//the 11th International，Conference on Control，Automation，Robotics and Vision，Singapore，2010:1225 －1230.

［12］ Hirschmüller H，Innocent P R，Garibaldi J.Real－ timecorrelation－based stereo vision with reduced border errors［J］.International Journal of Computer Vision，2004，47(1－3):229－246.