基于FPGA的Canny算法的硬件加速设计

0 引言

边缘检测是图像分析过程中非常基础和重要的研究领域，边缘提取的好坏将直接影响到后续处理的准确性和难易程度。用于边缘检测的方法有Roberts，Sobel，Laplace，Canny，PreWitt等众多算法。在这些算法当中，由于具有良好的边缘检测能力而使得Canny算法在数字图像处理中得到了广泛的应用。然而由于计算量的庞大，处理的时间又比较长，往往很难满足系统的要求。因为FPGA对数据的并行处理，能达到系统的实时性要求，且开发的周期短，采用电子设计的EDA技术使得开发、调试和验证更为直接和简单可行。
本文在FPGA基础上研究Canny算法的边缘检测，并对它进行了加速改进，且在数据处理过程中使用了流水线设计，更深入地挖掘了FPGA在数据处理速度中的优势。仿真实验证明了该方法的可行性，并且实现了良好的实时性。

1 Canny算子的边缘检测

边缘是指在其周围像素灰度有明显变化的那些像素的组合，它是具有幅值和方向的矢量，在图像中表现为灰度的突变。早在1986年Canny就提出了边缘检测应该满足的三个最优准则：

(1)重要的边缘不能丢失，没有虚假的边缘，并且误差检测率是最小的。
(2)实际边缘与检测到的边缘位置之间的变差最小。
(3)对单一边缘应具有惟一的响应。

Canny算子首先使用高斯滤波器来平滑图像，再计算图像梯度的强度和方向，接着对梯度图像进行非极大值抑制，最后采用双阈值方法从候选边缘点中检测和连接边缘。

1．1 Canny算子原理

Canny算子是把边缘检测问题转换为函数极大值的问题加以处理。提取边缘首先要进行高斯滤波，其目的是对原始图像进行平滑处理，以减弱或除去图像中的噪声。其高斯滤波的基本思想是将一个对称的二维高斯函数与原始的图像做卷积运算，再沿其梯度方向做微分，这样就形成了一个简单且有效的方向算子。
f(x，y)为原始图像，G(x，y)是二维高斯函数，则平滑滤波后的图像I(x，y)为：
I(x，y)=G(x，y)*_f(x，y) (1)
定义方向n为边缘方向的法向方向，则n可由下式得出：

式(3)说明了如何寻找局部最大值，在非极大值抑制之后，还要通过阈值化处理来寻找极大值。先设定一低阈值Th1，然后选取高阈值Th2≈2*Th1，将极大值抑制后的图像按Th1，Th2进行两次阈值化处理，得到图像T1和T2。由于图像T2是通过高阈值得到的，噪声和伪边缘很少，但也造成了一些真实边缘信息的丢失；而图像T1保留的边缘信息相对全面，但是存在一些虚假的边缘信息。所以以图像T2为基础，图像T1为补充可以获得相对全面的边缘图像。

1．2 算法的模板

本文算法中的高斯滤波器和梯度强度计算时都采用3×3的方形移动窗口，同时梯度强度计算选用Sobel算子。在对图像进行平滑处理时，需要使用高斯模板与原图像中的像素点值做矩阵的卷积运算。本文选取高斯模板的模板系数为0．062 5，且σ=1。模板如下所示：

式中：h为水平方向上的模板；v为垂直方向上的模板。h与图像做卷积得到水平方向上的梯度强度Ex；v与图像做卷积得到垂直方向上的梯度强度Ev。然后通过式(4)计算梯度强度Gr为：
Gr=|Ex|+|Ey| (4)
在FPGA中，卷积的运算是通过移位和加法来实现的。对于8位的图像来说，在移位和加法的运算中，由于存在正负号的运算，像素值的大小会被调整为11位，在最后做完绝对值的加法运算后要把11位缩回8位并得到最终的像素导数值。

2 加速功能设计

本文对图像的快速处理采用了流水线技术。所谓流水线技术是把规模较大、层次较多的组合逻辑电路分为几个级，在每一级插入寄存器组并暂存中间数据。对于每个步骤只依赖于前面步骤的运算结果的顺序处理来说，流水线技术能大大地提高系统的性能。在本文的算法中，可将处理过程分为以下几个任务：图像平滑、梯度计算、非极大值抑制和图像边缘判定检测。任务与任务之间都是顺序执行的，即就是说下一任务的执行需要上级任务的结果输出数据，因此总的时间花销为各个任务所需时间的总和。要使系统使用的处理时间最小，也就是使每个任务所花费的时间最短。

2．1 加速器设计实现

本文使用了一种能运用于高斯平滑滤波和梯度计算的加速器的数据路径结构。由于这两种计算过程均采用相同大小的方形移动窗口，故其加速设计具有极大的相似性。对此，这里选取3×3的Sobel模块来解释说明。

Sobel的加速数据结构如图1所示。它是一个具有以下功能的流水线：先从原始的图像中读取像素值存入图中右方的3组12寄存器中，数据流过中间的3×3的乘法器阵列，即像素值与模板值做乘法运算；然后向下流过加法器，在加法器中完成和运算，至此实现了像素值与模板的卷积运算，之后到达Ex和Ey寄存器，通过绝对值电路和加法器(实现式(4))到达寄存器，最终流入最下面的寄存器。图中负号表示取反，数值1和2表示右移的位数。
为使得加速器能够有序地按照确定的步骤进行，本文使用了有限状态机。如图2所示为加速器的简单状态转换图。在加速器的执行过程中，当检测到3组寄存器中的数据为空时，读信号使能re_en置1，自动读入新的3组数据；且在下方寄存器存储满时，写信号使能wr_en置1，数据被提取进行写操作。

在加速器的执行过程中，像素每4个为一组进行读写，这样在高速处理过程中大大缩减了对相同像素点的多次重复读取而浪费的时间；同时，在处理过程中不需要在处理每个像素点时都对其邻域的8个像素点更新，这样节省了大量的读取时间；并且由于FPGA的并行特性，像素的读、移位及写操作和乘法器的运算是同时进行的，使得处理速度有一定的提升。

2．2 加速器的地址产生

在系统的连续处理过程当中，加速器没有专门的等待时间用来对数据进行读取和存储，这两类运算都是并行进行的。因此加速器需要具有自动选通的读／写地址电路。对于一幅512×512图像来说，从偏移值0开始计数，一次加1，以便于从内存中读一组4个像素值，把偏移地址和基地址加起来形成前一行的像素地址，把它加上512／4就形成当前行的读地址，再加上1 024／4就形成了下一行的读地址。对于写地址来说，从偏移值512／4开始计数，一次加1形成每次的写地址。地址发生器的部分代码如下：


3 Canny算法加速设计

为了使得整个算法的计算速度得到提高，使算法既满足高速要求也不会耗费大量的硬件资源，本文对高斯滤波和梯度强度计算两个任务模块做了加速设计组合，流程图如图3所示。

高斯滤波器采用与Sobel加速器相似的设计原理，具有流水线的加速功能。图中RAM是FPGA中自带的Block RAM块，其大小配置为仅存储当前被处理图像的三行像素值，对于512×512的8位图像来说RAM应配置为512×3×8 b。因为高斯滤波的存储和Sobel加速器在读取的时候都是每4个像素点即32 b数据来进行，所以配置为32位宽的同时读写操作的双口RAM。

梯度运算之后，进行非极大值的抑制，在非极大值抑制之前需要计算梯度的方向。梯度方向的计算分为四个方向：水平、垂直、45°方向及135°方向，且每个方向上都包含两个45°的范围。通过Ex和Ey的比值及正负可以确定梯度方向落在上面规定的四个方向之一。判断四个方向的具体如下：

在FPGA中，直接做除法运算是很复杂的过程；为了减少资源的开销，把式(5)～式(8)中的除法变换成乘法，再做比较来判断梯度的方向。对于tan 22．5°和tan 67．5°做如下处理：

非极大值的抑制在系统中通过选择器和比较器来实现。根据输入的梯度值和梯度方向，用非极大值抑制条件(式(5)～(8))和高低阈值条件对输出的数据进行比较选择，强边缘点输出为255，弱边缘点输出为0。由于硬件流水线的特点，边界像素的计算结果是无效的，所以将边界上的行列都置为0。重复以上步骤，直到整幅图像扫描完成，最终得出边缘图像。

4 系统验证和结果分析

为了能清楚直观地验证加速的加速效果，本文在系统平台上对相同的图像分别用加速／未加速的系统做处理，记录相应时间并比较。

本文采用的验证系统平台以Altera公司CycloneⅡ系列中的EP2C20F484C8芯片为核心搭建而成，如图4所示。在验证系统设计中实现一个串口用来和PC机中的上位机通信，把处理完后的数据经过串口传输给上位机。数据在串口的传输过程中的延迟时间是固定的，故从上位机接收到第一个数据到最后一个数据的时间差即为一帧图像处理所花费的时间。

本文选取了不同大小的3幅图片做实验验证，系统时钟频率为100 MHz。其处理时间结果如表1所示，系统1为有加速功能的系统，系统2为未经加速的系统。

由表1可见，经过加速改进后的系统在处理时间上得到了很大的节约，随图像尺寸变大，总的节约时间显然是增加的；且经计算知：当尺寸变4倍(表1第2列256图与第3列512图)，节约时间大约增加3．9倍；640×480图比512×512图尺寸大1．17倍，节约时间是1．23倍，实际结果与理论计算相吻合。随着图像尺寸的增加，节约时间亦按比例增加，因此该加速功能在处理大容量高速的图像时具有更大的优势和广阔的应用前景。

图5为一幅在FPGA中经过加速器系统处理后使用Matlab呈现的边缘图像。该算法处理的图像结果基本得到所有的边缘信息，完全能满足应用需求。

5 结论

本文提出并实现了一种基于FPGA的加速Canny算法边缘检测系统。该系统充分发挥和利用FPGA的优良并行处理能力及流水线技术，从而实现功能加速。

在加速过程中通过状态机的控制作用能使模板的运算处理和数据的读／写操作得以同时进行，一定程度上节约了因大量的读／写数据操作而占用的时间。此系统充分利用了FPGA中的硬件资源，大大提高了系统算法的运算效率，且设计结构较为灵活。最终通过边缘检测实验，验证了设计的正确性。