李龙勋，唐普英，唐湘成，刘 怡，黄自力

(1.电子科技大学，四川 成都 611731;2.西南技术物理研究所，四川 成都 610041)

责任编辑:时 雯

FPGA是在CPLD可编程器件的基础上进一步发展起来的新型高性能可编程逻辑器件。与ASIC相比，它具有设计开发周期短、制造成本低、开发工具先进以及可实时在线检验等优点，所以被广泛应用于产品的原型设计和生产之中［1］。传统上FPGA只能实现相对较小的逻辑电路，随着工艺技术的提高，FPGA的容量和性能也不断提高，如今FPGA已经被用于实现大的逻辑电路甚至整个系统。

在实现大的逻辑电路设计时，应对一些较为复杂或者重复性工作模块多的情况，为了达到资源的有效利用，FPGA资源就需要进行预评估。对设计进行一个有效的资源评估能够更好得利用FPGA芯片的资源。本文着重于FPGA上的算法的实现以及进行资源使用的预评估，以及多层次地评估算法在FPGA资源上的占用。

1 FPGA资源预评估的意义

FPGA可以在片内实现细粒度、高度并行运算结构，所以FPGA最大优势在于硬件实现已及通过并行处理实现的效率增益。相比DSP，FPGA最大的优势是能够在同一时间能处理大量不同的任务，因而在涉及到复杂计算时可把DSP的一些任务转移到FPGA中处理。

未来人们对通信的传输数据、图像处理等方面要求越来越高，传输速率要求能达到100 Mbit/s～1 Gbit/s，这就对无线技术、带宽、数据处理能力等提出更高要求。通过采用FPGA去做复杂的数据处理，可以实现更高的速率传输。

在FPGA应对复杂的数据处理时，因为要消耗大量的Register和LUT等逻辑资源来实现复杂运算，所以有必要在编写程序之前对算法资源进行预评估。提前的资源评估不仅可以更好地选择芯片的型号，还可以对算法程序有较详细的估计，在硬件选定的前提下能够有更好的优化算法。

2 对Harris算法的资源的评估

2.1 Harris角点检测原理

角点是图像的一个重要局部特征，它集中了图像上很多重要形状信息，且具有旋转不变性，几乎不受光照条件影响［2］，本文采用的是Harris角点检测算法。Harris算法是基于图像灰度的角点检测算法，若像素点所在位置的z方向梯度与y方向梯度的绝对值均比较大，则将该像素点判定为角点。

式中:w为高斯滤波进行去除噪声处理;Ix和Iy分别为需要计算的像素在水平方向和垂直方向的一阶灰度梯度［3］。

其中，式(1)、式(2)为计算相关函数，然后使用式(3)的角点函数计算出图像中的角点。最后根据角点检测原理可以得到算法计算步骤如图1所示。

图1 算法流程图

2.2 模板构造

Harris算法在FPGA实现中需要构造图像数据矩阵，假设采用5×5的模板如图2所示，即需要通过缓存4行4列的数据，然后在通过模板进行相应的计算。

图2 5×5的模板实现

其中r11，r12等为移位寄存器;FIFO是先进先出存储器，图像数据一次串行输入，利用行、场信号来控制读写信号，FIFO用来存储每一行的数据，使得 R11，R12，…，R55正好是5×5模板所对应的图像数据［4］。

2.3 资源的预评估

FPGA芯片主要由以下部分组成:可编程输入输出单元、基本可编程逻辑单元、数字时钟管理模块、嵌入式块RAM、丰富的布线资源、底层嵌入功能单元和内嵌专用硬核等［5］。

在算法未实现之前，在单一算法模块中，能够进行预评估的资源有RAM资源、逻辑资源(时序逻辑资源和组合逻辑资源)以及DSP模块使用情况。由上面的算法流程可以得知在计算过程中使用到的是FIFO资源、移位寄存器资源、加法器、减法器和乘法器。

如图3所示24位的 FIFO占用24个 LUT、6个M4KRAM资源和126的Register资源。一个16位的D触发器占用16个LUT资源。

图3 FIFO资源和D触发器资源

如图4所示，24位的加法器占用24LUT资源，24位减法器占用25LUT资源，12位乘法器占用2个DSP的9位模块资源，本算法中没有涉及到除法器所以没有使用到除法器。

图4 加法器、减法器和乘法器资源

2.3.1 RAM资源预评估

在Harris角点检测算法中，采用的是5×5的模板窗口进行检测，使用到FIFO资源。如图3、图4得知，FIFO占用了M4K的块RAM资源。从FPGA的资源介绍中知道，块RAM资源属于FPGA定制资源，受M4K数量限制。

1)在对Ix进行计算中，5×5模板需要利用4个FIFO进行存储，位宽和深度主要取决于图像像素(这里取FIFO位宽为24 bit、深度为1024)。计算Iy和Ix的为相同模板，所以和Ix计算占用同样资源。

2)在高斯滤波中，要针对Ix，Iy，Ixy三个值使用三个高斯滤波模块。高斯滤波也使用5×5的模板，在资源的占用上，使用了4个FIFO(位宽24 bit、深度1024)。具体预评估资源如表1所示。

表1 RAM资源预评估

2.3.2 逻辑资源预评估

1)在Harris算法程序中，计算Ix，Iy时使用到了5个D触发器进行移位，其中每个触发器的位宽为16 bit(位宽受像素影响)同样在计算高斯滤波时也使用5个D触发器，位宽16 bit，一共使用20个D触发器，位宽16 bit。在图3、图4可知，FIFO也会占用时序逻辑资源。具体预评估资源如表2所示。

表2 时序逻辑资源预评估

2)加减法器占用组合逻辑资源，受计算数据位宽的影响，每一位占用一个逻辑资源，由图3、图4中得知，FIFO也占用了LUT资源。具体预评估资源如表3所示。

表3 组合逻辑资源预评估

3)乘法器占用DSP elements资源，乘法器中位宽为36×36的占用8个DSP elements，18×18是占用2个DSP elements。在算法中乘法器中有3个24位的，有5个12位的，总共占用DSP elements 34个。如果是类似2×A的数字和数据相乘，而不是A×B的两个数据相乘，此时的乘法相当于加法，只占用组合逻辑资源而不占用DSP模块。

2.4 Harris算法在FPGA的实现

根据图2的算法流程，构造的图像数据矩阵，先计算出图像像素在水平方向和垂直方向的一阶灰度梯度Ix以及Iy。然后计算出m值再进行高斯滤波，最后根据M值计算R值求得角点。其中计算Ix，Iy值的时候注意Ix，Iy的非负性。下面为在FPGA中用Verilog语言计算Ix，Iy的值。

实现平台采用的是Stratix系列的EP2S60F672C4芯片，其中含有的等效逻辑单元为60440，RAM资源为2544，192 bit，DSP 模块有36 个，锁相环 PLL 有6 个，全局时钟有16个。表4为StratixII系列芯片的资源［6］。

表4 StratixII芯片的资源

3 实验结果

3.1 仿真结果和预评估比较

在Quartus 8.1软件中完成Harris算法的FPGA程序，在软件中仿真综合可以得到结果如图5、图6、图7所示。

如图所示，在对比由软件得到的RAM资源仿真结果和预评估的资源可以知道，ALUTs占用2666和预估计的4016相差1350，而Delicated logic registers占用2623和预估计的2262相差361，占用的RAM资源308353 bit和估计的393216 bit等相比相差84863 bit。理论预估计的要比实际占用的要多，其中ALUTS实际和估计差距较大原因在于FIFO在实际仿真中占用的ALUTS资源要比理论上要多。其他资源的预估计在仿真中得到相仿的结果。

3.2 实现图像

最后将程序在FPGA的硬件平台上实现，输入图像是CCD实时灰度图像，在阈值不大的情况下，得到图8的实时图像的Harris角点检测。其中图中的十字叉为检测到的角点。

图8 实时图像的Harris角点检测

4 小结

本文对Harris算法进行FPGA上的移植实现，及对其在FPGA上资源的占用进行了预评估。从最后的图像可以看出，在小阈值的情况下Harris算法在FPGA上实现了实时的角点检测。从仿真的结果可以看出，预评估的各项参数和实际仿真出来的相差不大，其中的误差取决于程序中流程编写中使用到的其他逻辑门，以及FIFO实际应用中占用的ALUT也比理论上的多。由此可以看出，只要知道算法的具体流程，在RAM资源和逻辑资源的预评估上是能有效提供参考价值的。

［1］俞吉波，孔雪.FPGA实际可用性评估与发展趋势分析［J］.计算机工程，2011，37(13):282-284.

［2］刘闯，龚声蓉.基于角点采样的多目标跟踪方法［J］.中国图象图形学报，2008，13(10):1873-1877.

［3］何丰，胡俊.一种改进的图像快速高精度角点检测算法［J］.电视技术，2011，35(15):57-60.

［4］王鹏，向厚振.基于FPGA的动态可重构边缘检测系统设计［J］.电视技术，2011，35(7):32-35.

［5］徐洋，黄智宇，李彦，等.基于Verilog HDL的FPGA设计与工程应用［M］.北京:人民邮电出版社，2009.

［6］Alter Product Catalog［EB/OL］.［2012-05-13］.http://www.altera.com.cn/literature/sg/product-catalog.pdf.