Laplacian图像边缘检测器的FPGA实现研究

1 引言
    边缘可定义为图像中灰度发生急剧变化的区域边界，它是图像最基本的特征，是图像分析识别前必不可少的环节，是一种重要的图像预处理技术。边缘检测主要就是(图像的)灰度变化的度量、检测和定位，它是图像分析和模式识别的主要特征提取手段，在计算机视觉、图像分析等应用中起着重要的作用，是图像分析与处理中研究的热点问题。
    数字信号和图像处理算法的实现有多种途径，传统上多采用高级语言编程实现，便于使用的还有基于专用单片机来实现(一般称为可编程DSP单片机)以及在VLSI上实现某种算法的专用集成电路芯片(ASIC)等。近年来，随着EDA技术的迅速发展，国内外逐渐比较流行的是在FPGA中实现复杂算法的运算处理。
    在图形处理领域，图像处理的速度一直是一个很难突破的设计瓶颈。这里通过研究图像边缘检测器的FPGA实现，来探讨提高图像处理速度的有关途径。

2 Laplacian边缘检测的数学模型
    常见的边缘检测算子有：Roberts，Laplacian，Kirseh，So—bel，Prewitt等。各种检测算子各有其优缺点，其中Laplacian算子是一种典型的边缘检测方法，它是一个3×3模板，对实现硬件的要求不高，用于检测屋顶型边缘的效果也不错。研究其硬件实现具有一定的典型性，可推广到对其他算子的硬件实现。
    拉普拉斯算子是根据图像f(x，y)在x，y方向上的二阶偏导数定义的一种边缘检测算子，其定义：

   
    因为图像边缘的灰度变化较大，所以图像的一阶偏导数在边缘处有局部最大值或最小值，这样二阶偏导数在边缘处会通过零点。用拉普拉斯算子检测边缘就是估算拉普拉斯算子的输出，找出其零点位置。拉普拉斯算子定义为：

   
    如果把它用加权矩阵来表示则可表示成图1左侧所示的卷积模板。由于数字图像中离散信号的特点，在连续情况下能获得的精确零点这时可能无法全部检测出来，故拉普拉斯算子输出为零的点并不能表示出完整的目标边缘。为此，在设计中定义边缘为满足以下两个条件的像素点的集合：①拉普拉斯算子的输出为正；②在其8邻点存在拉普拉斯算子的输出为负的点。

3 图像边缘检测的实现流程
    图像边缘检测有一个共同点：可转化为用一个模板(2×2．3×3，4×4，5×5等)对图像进行卷积。因此图像边缘检测的核心就是如何处理模板的卷积运算。Laplacian算子就是一个3×3的卷积模板。
    3x3卷积运算阁定义如(3)式所示，其中Cm，n为被卷积后的像素值，Pm，n为图像的实际像素值，其中Cm，n为被卷积后的像素值，Pm，n为图像的实际像素值。由(3)式可知，完成一次3x3卷积操作需要9次乘法和8次加法操作。

   
    由图1可知，图像边缘检测的主要实现流程为：①模板在图像中以光栅扫描方式移动；②将模板系数与模板下对应像素相乘；③将所有乘积相加；④将和(模板输出响应)赋给图像中对应模板中心位置的像素完成一次卷积。不断重复上述步骤直至整幅图像被处理完。

4 分布式算法的运算原理
    分布式算法早在1973年就被Croisier提出，直到FPGA出现，才被广泛地应用在FPGA中计算乘积和。除了用于卷积运算，还用于相关DFT和RNS反演映射的运算。介绍DA算法的运算原理。一个线性时不变网络的输出用下式表示：

   
    假设系数c[n]是已知常数，x[n]是变量，在有符号DA系统中假设变量x[n]的表达式如下：

   
    式中xb[n]表示x[n]的第b位，而x[n]也就是x的第n次采样。于是，内积y可以表示为：

   
    重新分别求和(即分布式算法的由来)，其结果为：

   
    从(7)式发现，分布式算法是一种以实现乘加运算为目的运算方法。与传统算法的不同在于执行部分积运算的先后顺序不同。分布式算法在实现乘加功能时，是将各输入数据的每一对应位产生的部分积预先相加形成相应的部分积．然后再对各个部分积累加形成最终结果，而传统算法是等到所有乘积已经产生后再相加完成乘加运算。与传统串行算法相比，分布式算法可极大地减少硬件电路的规模，提高电路的执行速度。该算法实际上是一个“速度最优的高阶分布式算法”

5 Laplacian边缘检测器的FPGA设计
5．1 系统的总体设计
    Laplacian边缘检测器DETECTOR总体设计如图2所示。系统工作原理为：帧存储器按照一定的规则(是按行)输出数据，经过FIFO输入缓冲，进入两个32位的移位寄存器。由SIPO(串进并出)模块得到所需的9个并行数据，送卷积处理器(Convolver)得到处理后的数据，最后卷积器输出一个像素值。根据边缘判断规则，即可判断出该点是否为边缘点。

5．2 卷积运算模块的设计
    Laplacian模板是一个3x3阶的数，每个像素值为8位，因此，它和另外的3x3模板进行卷积，其输出表达式为：

   

   
    对于该卷积运算的实现，采用前述的“速度最优的高阶分布式算法”，其硬件实现的原理框图如图3所示。它是完全流水线式字并行结构，能够达到最大的运算速度。其中的8个ROM是用于实现9个R图位的数相乘，每个ROM都实现一个9位的查找表的功能。5．3卷积运算数据“流水线”输入模块的设计图像的像素是由CCD(或CMOS)摄像机经A／D转换，再经量化而得到，并放入帧存储器。在图像中，整幅图像像素以帧为单位进行存储。每一帧数据的存储方式如图4所示。卷积运算扫描像素的获取如图5所示，该数据输入方式，使用了两个32位的移位寄存器存放像素值，避免了卷积运算中对存储器数据的高度重复读取，使用9个寄存器实现了数据由串行到并行的转换，实现了完全“流水线”的输入方式。

5．4 系统的仿真结果
    根据前述的总体设计方案，使用VHDL设计进行各个模块和系统总体程序，选择的FPGA为ALTERA／FLEX／EPF10K20TC144—3，使用的开发工具是MAX+plus II 10．0。图6是边缘检测器的时序仿真图(钟频率10 MHz)，由波形仿真结果分析可知，系统达到了设计功能要求，该系统经过初始的两行行延迟和串并转化后(为72个时钟周期)，以后每个时钟周期就可“流水式”输出一个处理结果，若系统时钟周期TCLK，对于像素为N个点的数字图像，系统的处理时间TN=70xTCLK+N×TCLK。处理一幅1 024x1 024的图像的时间，当系统时钟为10MHz时，仅需0．1 s，而系统时钟为10 MHz时，仅需0．Ol s。

6 结语
    在Laplacian图像边缘检测器的设计中，采用了速度最优的高阶分布式算法(DA)完成模板的卷积运算，使用两个32位的移位寄存器存放像素值，避免了卷积运算中对存储器数据的高度重复读取，使用9个寄存器实现数据由串行到并行的转换，实现了完全“流水线”的数据输入方式，从而在资源．速度上达到了较好的优化，具有良好的实时处理性能。若系统工作时钟为100 MHz，则处理一幅1 024x1 024的图像的时间仅需0．01 s左右。“流水线”的数据输入方式和分布式卷积运算的设计思想，对于数字图像和数字信号处理的FPGA硬件实现，具有广泛的推广应用价值。