基于FPGA和分水嶺算法的甜瓜圖像分割

王國棟，王書志，馮全

（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.