王国栋，王书志，冯全

（1.甘肃农业大学工学院，甘肃 兰州 730070；2.西北民族大学电气工程学院，甘肃 兰州 730030）

甜瓜在生产或收获过程中容易受到人为和自然等因素的影响，会产生各种表面缺陷。提取这些缺陷对于甜瓜的品质分级十分重要。常见的水果缺陷分割算法为阈值分割法，首先从背景中分割出水果，然后以水果为背景，再分割缺陷区域。而使用分水岭分割算法可以一次完成缺陷分割，尤其是在缺陷面积比水果表面积小很多时，相比阈值分割算法如Otsu算法，分水岭算法能有效地分割出缺陷区域。

分水岭算法是一种有效的图像分割算法，但是由于该算法对图像的变化非常敏感，图像中的噪声和其他因素经常会导致图像的过度分割，从而降低检测系统效率。分水岭算法结合标记、区域合并和预处理的方法[1]可以有效防止图像的过度分割。尽管传统分水岭算法已经很成熟，但由于基于软件的算法时间开销大，用时不确定，有时很难满足水果在线检测实时性的要求。

本文在现场可编程门阵列（FPGA）上实现了分水岭算法，FPGA器件含有大量查找表和并行结构单元，适合流水线算法设计，使甜瓜的在线检测成为可能。

1 分水岭算法

1.1 算法原理

分水岭算法是一种基于数学形态学的图像分割技术，其变换思想来源于地质形态学。如果将图像像素的灰度看作高度，图像中极大灰度值和极小灰度值之间相连的区域就与地质形态学的山峰和山谷盆地对应，分水岭就是盆地的边缘。当一幅图像逐渐沉入一个湖中后，最先进水的是图像灰度最小的点；随着图像的下沉，水逐渐浸入整个山谷盆地。当水位超过盆地的边缘，湖水就会溢出。此时在水溢出处建立堤坝，直到整个图像恰好沉入水中，所建的堤坝就是分开盆地的分水岭。分水岭分割方法应用在图像的梯度，理论上，集水盆地对应灰度变化相对较小的区域，分水岭则对应灰度变化相对较大的区域。

分水岭算法的特点在于能够分割出目标的完整外轮廓，其在图像的识别和检测中有着广泛的应用。

1.2 分水岭算法的实现

1.2.1 预处理 在使用传统分水岭算法分割图像的过程中，容易受到图像本身噪声以及量化误差的影响，使本应连续的区域分割成许多较小的区域。分水岭算法中常需要计算图像梯度，而梯度信息对噪声非常敏感，因此可能会在物体的边缘混进许多虚假边缘，即过度分割。为了避免这一现象，在实施分割算法之前，可以采取预处理滤波的方法来滤除图像的噪声。虽然在分水岭算法中有很多有效的预处理方法[2-3]，但是这些方法比较复杂，不适合用FPGA实现。本文采用高斯低通滤波器对图像进行了预处理[4]，以消除噪声，实现平滑。为便于FPGA硬件实现，高斯滤波器采用5×5模板取代卷积运算。

1.2.2 分水岭算法实现 采用标记的方法与分水岭算法相结合可以有效防止图像的过度分割。Vincent等[5]提出的基于递归算法的方法以及由Meyer[6]提出的地形学距离的方法，是2种经典区域标记的方法，但这2种方法计算开销太大，尤其考虑到硬件的实施时，FPGA器件提供了大量的并行运算单元而且在顺序执行时效率较低，因此，本文采用Bieniek等[7]描述的基于本地连通部分和标记的算法。Moga的并行分水岭算法采用域分解并行模型（domain decomposition），即一副图像以静态映射方式分配给多个不同处理单元，每个子域上用串行算法计算子图像，当要用到邻域的计算结果时可插入同步和通信点。Moga算法主要包括 3 个步骤：（1）最小值检测；（2）“lower detection”这种处理是为了确保每个像素有一个更低灰度值的邻点（当然在区域最小值点除外），目的在于去除平坦区（plateaus）；（3）泛洪处理（利用标记爬山法或降水法）。

分水岭算法的实施步骤：首先，提供基于物体和背景的标记，由背景和物体的标记初始化标记数据库，创建有向标记图。第一次扫描图像时，比较图像中每一个像素和其邻域像素的像素值。如果扫描到灰度较暗邻域像素，则将该邻域的像素地址写入标记数据库；如果邻域有2个以上灰度较暗像素，可以选择任意一个像素的地址。没有灰度较暗的邻域则意味着本像素属于一个平坦区域。而此时还无法确定该平坦区是否含有极小值。扫描图像时，如果一个像素的标记不是背景或物体的标记，在标记数据库插入新标记。

下一步去除不含极小值的平坦区。扫描标记数据库，搜索每个标记了LAB_P的像素的邻域（LAB_P是平坦区的标记），当找到第1个标记不同的邻域时，将该邻域地址输入FIFO，并且终止该邻域扫描。重复扫描其他标记为LAB_P的邻域，当所有标记LAB_P的邻域扫描完成之后，FIFO存储了不含极小值平坦区的边界上的像素地址，这些像素具有灰度较暗的邻域。

接着在不含极小值的平坦区传播灰度较暗的邻域标记。读入FIFO，对每个来自FIFO的像素地址进行标记传播。经过这步，图像只有含有极小值的平坦区。当含有极小值的高平坦区标记统一之后，创建有向图，这可以通过对含有极小值的平坦区的标记重新赋予地址来完成。本文在这一点上，参照文献[7]的算法，在算法中，当有向标记图创建后，按图径的传播标记进行分割。在标记的传播过程中还采用压缩路径的方法，例如从点P出发到最低点M终止，途中经过点Q，则意味着点Q也可以到达点M，对Q就不需要处理。压缩路径的方法明显可以改善分水岭算法的运算速度。

最后，为了改善过度分割，可进行区域合并。本文采用以下规则对分割较小的区域进行合并。（1）当分割区域小于特定值（基于像素个数的最小区域）、其灰度值接近于邻域的分割时，将其邻域和分割区域合并。（2）部分类似的平均亮度值融合，如果2个分割的平均灰度值完全不同，而且比阈值小，则将二者合并。

2 电路的系统结构及硬件实现

2.1 电路的系统结构

为了实现甜瓜图像的实时预处理，本文采用ALPHA DATA公司的ADM-XRC-5T2-ADV6为系统的硬件加速器。这款开发板的主要计算单元为XILINXVIRTEX-5 FPGALX330T2器件，配备2组独立的2M×18bits的DDR-IISSRAM和4组独立的64M×32bits的DDR-II SDRAM，且经VIRTEX4-LX25芯片与主PCI总线桥接。AMDXRC-5T2-ADV6加速板的框图如图1所示。

本文实现的分水岭算法采用了2种结构。第1种可以脱机离线工作，读取静态图像数据并将其送到以VIRTEX-5为核心的专用硬件加速模块；第2种结构可实现在线处理，采用了ALPHA DATA的XRM-Cameralink接口卡，这种卡为上述FPGA开发板与符合工业标准“Cameralink”的数字摄像机之间提供了连接。它的输入部分通过26线的电缆连接摄像机，卡本身则可插入ADMXRC-5T2-ADV6开发板的前面板连接器中。该接口卡提供了视频的帧捕获功能，通过开发板可以很容易对其进行控制。

2.2 分水岭的硬件实现

ALPHADATA公司为ADM-XRC-5T2-ADV6提供软件开发包（驱动和API C++库），支持复杂信号处理中软件及硬件的应用。用户通过C++完成算法编写后，可由开发包工具转化为硬件语言，大大简化了FPGA的设计。本文在XILINX ISE语言环境下对硬件代码进行了综合。

设计的分水岭硬件模块如图2所示，它直接使用ADM-XRC-5T2-ADV6开发板的架构完成功能实现。图中控制寄存器接口（CTRL registers interface）允许软件对设计单元进行控制、定义图像像素的尺寸以及状态字。CKU单元产生时钟信号，初始化整个单元以及外部寄存器模块。CTRL单元是主要单元，可以顺序启动5个计算单元：即标记单元（LSU）：负责初始化和标记选择的平坦区以及邻域像素比较、平坦区像素的标记。消除单元（EPU）：负责消除不含极小值的高原，以及统一含有极小值的平坦区。标记传播单元（LPU）：负责标记的传播。区域合并单元（RMU）：标记控制的区域合并。分割单元（EDU）：执行最后的分割。

处理的数据存储在DDR-II静态存储器模块中。由于上述算法在寄存器模块和内部计算单元之间需要大量的数据交换，因此，数据吞吐量的最大化对运算时间有着非常重要的影响。

3 试验结果与讨论

在XILINX VIRTEX-5 FPGA LX330T2器件上实现了分水岭算法，其算法大致需要半数资源，从而为其他的处理节省了资源。由于系统的分辨率限制在648×648像素。如果处理的图像像素较大，则需要拓展EPU模块中FIFO的长度。对于一幅640×480分辨率的图像，FIFO的平均利用率在5000 ～10000字之间。每帧甜瓜图像包括分水岭算法的整体处理时间为20～40ms，比用普通的软件方法要快10倍以上。

试验表明，本文采用的FPGA硬件实现的分水岭算法，具有较快的图像处理速度，可以实现甜瓜图像的实时分割，达到了预期的目的，而且这种方法还可以应用到其他水果的缺陷分割中。

［1］刁智华，赵春江，郭新宇，等.分水岭算法的改进方法研究[J].计算机工程，2010，36（17）：4-6.

［2］潘婷婷，李朝锋.基于区域生长型分水岭算法的卫星图像道路提取方法[J].计算机工程与设计，2008，29（19）：4987-4988.

［3］杨文明，陈国斌，沈晔湖，等.一种基于分水岭变换的图像分割方案[J].浙江大学学报：工学版，2006，40（9）：1503-1510.

［4］丁怡心，廖勇毅.高斯模糊算法优化及实现[J].现代计算机技术，2010（8）：76-78.

［5］Vincent L，Soille P.Watersheds in digital space and efficient algorithm based on immersion simulations[J].IEEE Transactions on PAMI，1991，13（6）：583-598.

［6］Meyer F.Topographic distance and watershed lines[J].Signal Processing，1994，38：113-125.

［7］Bieniek A.An efficient watershed algorithm based on connected components[J].Pattern Recognition，2000，33：907-916.