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

王國(guó)棟，王書志，馮全

（1.甘肅農(nóng)業(yè)大學(xué)工學(xué)院，甘肅 蘭州 730070；2.西北民族大學(xué)電氣工程學(xué)院，甘肅 蘭州 730030）

甜瓜在生產(chǎn)或收獲過程中容易受到人為和自然等因素的影響，會(huì)產(chǎn)生各種表面缺陷。提取這些缺陷對(duì)于甜瓜的品質(zhì)分級(jí)十分重要。常見的水果缺陷分割算法為閾值分割法，首先從背景中分割出水果，然后以水果為背景，再分割缺陷區(qū)域。而使用分水嶺分割算法可以一次完成缺陷分割，尤其是在缺陷面積比水果表面積小很多時(shí)，相比閾值分割算法如Otsu算法，分水嶺算法能有效地分割出缺陷區(qū)域。

分水嶺算法是一種有效的圖像分割算法，但是由于該算法對(duì)圖像的變化非常敏感，圖像中的噪聲和其他因素經(jīng)常會(huì)導(dǎo)致圖像的過度分割，從而降低檢測(cè)系統(tǒng)效率。分水嶺算法結(jié)合標(biāo)記、區(qū)域合并和預(yù)處理的方法[1]可以有效防止圖像的過度分割。盡管傳統(tǒng)分水嶺算法已經(jīng)很成熟，但由于基于軟件的算法時(shí)間開銷大，用時(shí)不確定，有時(shí)很難滿足水果在線檢測(cè)實(shí)時(shí)性的要求。

本文在現(xiàn)場(chǎng)可編程門陣列（FPGA）上實(shí)現(xiàn)了分水嶺算法，F(xiàn)PGA器件含有大量查找表和并行結(jié)構(gòu)單元，適合流水線算法設(shè)計(jì)，使甜瓜的在線檢測(cè)成為可能。

1 分水嶺算法

1.1 算法原理

分水嶺算法是一種基于數(shù)學(xué)形態(tài)學(xué)的圖像分割技術(shù)，其變換思想來源于地質(zhì)形態(tài)學(xué)。如果將圖像像素的灰度看作高度，圖像中極大灰度值和極小灰度值之間相連的區(qū)域就與地質(zhì)形態(tài)學(xué)的山峰和山谷盆地對(duì)應(yīng)，分水嶺就是盆地的邊緣。當(dāng)一幅圖像逐漸沉入一個(gè)湖中后，最先進(jìn)水的是圖像灰度最小的點(diǎn)；隨著圖像的下沉，水逐漸浸入整個(gè)山谷盆地。當(dāng)水位超過盆地的邊緣，湖水就會(huì)溢出。此時(shí)在水溢出處建立堤壩，直到整個(gè)圖像恰好沉入水中，所建的堤壩就是分開盆地的分水嶺。分水嶺分割方法應(yīng)用在圖像的梯度，理論上，集水盆地對(duì)應(yīng)灰度變化相對(duì)較小的區(qū)域，分水嶺則對(duì)應(yīng)灰度變化相對(duì)較大的區(qū)域。

分水嶺算法的特點(diǎn)在于能夠分割出目標(biāo)的完整外輪廓，其在圖像的識(shí)別和檢測(cè)中有著廣泛的應(yīng)用。

1.2 分水嶺算法的實(shí)現(xiàn)

1.2.1 預(yù)處理 在使用傳統(tǒng)分水嶺算法分割圖像的過程中，容易受到圖像本身噪聲以及量化誤差的影響，使本應(yīng)連續(xù)的區(qū)域分割成許多較小的區(qū)域。分水嶺算法中常需要計(jì)算圖像梯度，而梯度信息對(duì)噪聲非常敏感，因此可能會(huì)在物體的邊緣混進(jìn)許多虛假邊緣，即過度分割。為了避免這一現(xiàn)象，在實(shí)施分割算法之前，可以采取預(yù)處理濾波的方法來濾除圖像的噪聲。雖然在分水嶺算法中有很多有效的預(yù)處理方法[2-3]，但是這些方法比較復(fù)雜，不適合用FPGA實(shí)現(xiàn)。本文采用高斯低通濾波器對(duì)圖像進(jìn)行了預(yù)處理[4]，以消除噪聲，實(shí)現(xiàn)平滑。為便于FPGA硬件實(shí)現(xiàn)，高斯濾波器采用5×5模板取代卷積運(yùn)算。

1.2.2 分水嶺算法實(shí)現(xiàn) 采用標(biāo)記的方法與分水嶺算法相結(jié)合可以有效防止圖像的過度分割。Vincent等[5]提出的基于遞歸算法的方法以及由Meyer[6]提出的地形學(xué)距離的方法，是2種經(jīng)典區(qū)域標(biāo)記的方法，但這2種方法計(jì)算開銷太大，尤其考慮到硬件的實(shí)施時(shí)，F(xiàn)PGA器件提供了大量的并行運(yùn)算單元而且在順序執(zhí)行時(shí)效率較低，因此，本文采用Bieniek等[7]描述的基于本地連通部分和標(biāo)記的算法。Moga的并行分水嶺算法采用域分解并行模型（domain decomposition），即一副圖像以靜態(tài)映射方式分配給多個(gè)不同處理單元，每個(gè)子域上用串行算法計(jì)算子圖像，當(dāng)要用到鄰域的計(jì)算結(jié)果時(shí)可插入同步和通信點(diǎn)。Moga算法主要包括 3 個(gè)步驟：（1）最小值檢測(cè)；（2）“l(fā)ower detection”這種處理是為了確保每個(gè)像素有一個(gè)更低灰度值的鄰點(diǎn)（當(dāng)然在區(qū)域最小值點(diǎn)除外），目的在于去除平坦區(qū)（plateaus）；（3）泛洪處理（利用標(biāo)記爬山法或降水法）。

分水嶺算法的實(shí)施步驟：首先，提供基于物體和背景的標(biāo)記，由背景和物體的標(biāo)記初始化標(biāo)記數(shù)據(jù)庫(kù)，創(chuàng)建有向標(biāo)記圖。第一次掃描圖像時(shí)，比較圖像中每一個(gè)像素和其鄰域像素的像素值。如果掃描到灰度較暗鄰域像素，則將該鄰域的像素地址寫入標(biāo)記數(shù)據(jù)庫(kù)；如果鄰域有2個(gè)以上灰度較暗像素，可以選擇任意一個(gè)像素的地址。沒有灰度較暗的鄰域則意味著本像素屬于一個(gè)平坦區(qū)域。而此時(shí)還無法確定該平坦區(qū)是否含有極小值。掃描圖像時(shí)，如果一個(gè)像素的標(biāo)記不是背景或物體的標(biāo)記，在標(biāo)記數(shù)據(jù)庫(kù)插入新標(biāo)記。

下一步去除不含極小值的平坦區(qū)。掃描標(biāo)記數(shù)據(jù)庫(kù)，搜索每個(gè)標(biāo)記了LAB_P的像素的鄰域（LAB_P是平坦區(qū)的標(biāo)記），當(dāng)找到第1個(gè)標(biāo)記不同的鄰域時(shí)，將該鄰域地址輸入FIFO，并且終止該鄰域掃描。重復(fù)掃描其他標(biāo)記為L(zhǎng)AB_P的鄰域，當(dāng)所有標(biāo)記LAB_P的鄰域掃描完成之后，F(xiàn)IFO存儲(chǔ)了不含極小值平坦區(qū)的邊界上的像素地址，這些像素具有灰度較暗的鄰域。

接著在不含極小值的平坦區(qū)傳播灰度較暗的鄰域標(biāo)記。讀入FIFO，對(duì)每個(gè)來自FIFO的像素地址進(jìn)行標(biāo)記傳播。經(jīng)過這步，圖像只有含有極小值的平坦區(qū)。當(dāng)含有極小值的高平坦區(qū)標(biāo)記統(tǒng)一之后，創(chuàng)建有向圖，這可以通過對(duì)含有極小值的平坦區(qū)的標(biāo)記重新賦予地址來完成。本文在這一點(diǎn)上，參照文獻(xiàn)[7]的算法，在算法中，當(dāng)有向標(biāo)記圖創(chuàng)建后，按圖徑的傳播標(biāo)記進(jìn)行分割。在標(biāo)記的傳播過程中還采用壓縮路徑的方法，例如從點(diǎn)P出發(fā)到最低點(diǎn)M終止，途中經(jīng)過點(diǎn)Q，則意味著點(diǎn)Q也可以到達(dá)點(diǎn)M，對(duì)Q就不需要處理。壓縮路徑的方法明顯可以改善分水嶺算法的運(yùn)算速度。

最后，為了改善過度分割，可進(jìn)行區(qū)域合并。本文采用以下規(guī)則對(duì)分割較小的區(qū)域進(jìn)行合并。（1）當(dāng)分割區(qū)域小于特定值（基于像素個(gè)數(shù)的最小區(qū)域）、其灰度值接近于鄰域的分割時(shí)，將其鄰域和分割區(qū)域合并。（2）部分類似的平均亮度值融合，如果2個(gè)分割的平均灰度值完全不同，而且比閾值小，則將二者合并。

2 電路的系統(tǒng)結(jié)構(gòu)及硬件實(shí)現(xiàn)

2.1 電路的系統(tǒng)結(jié)構(gòu)

為了實(shí)現(xiàn)甜瓜圖像的實(shí)時(shí)預(yù)處理，本文采用ALPHA DATA公司的ADM-XRC-5T2-ADV6為系統(tǒng)的硬件加速器。這款開發(fā)板的主要計(jì)算單元為XILINXVIRTEX-5 FPGALX330T2器件，配備2組獨(dú)立的2M×18bits的DDR-IISSRAM和4組獨(dú)立的64M×32bits的DDR-II SDRAM，且經(jīng)VIRTEX4-LX25芯片與主PCI總線橋接。AMDXRC-5T2-ADV6加速板的框圖如圖1所示。

本文實(shí)現(xiàn)的分水嶺算法采用了2種結(jié)構(gòu)。第1種可以脫機(jī)離線工作，讀取靜態(tài)圖像數(shù)據(jù)并將其送到以VIRTEX-5為核心的專用硬件加速模塊；第2種結(jié)構(gòu)可實(shí)現(xiàn)在線處理，采用了ALPHA DATA的XRM-Cameralink接口卡，這種卡為上述FPGA開發(fā)板與符合工業(yè)標(biāo)準(zhǔn)“Cameralink”的數(shù)字?jǐn)z像機(jī)之間提供了連接。它的輸入部分通過26線的電纜連接攝像機(jī)，卡本身則可插入ADMXRC-5T2-ADV6開發(fā)板的前面板連接器中。該接口卡提供了視頻的幀捕獲功能，通過開發(fā)板可以很容易對(duì)其進(jìn)行控制。

2.2 分水嶺的硬件實(shí)現(xiàn)

ALPHADATA公司為ADM-XRC-5T2-ADV6提供軟件開發(fā)包（驅(qū)動(dòng)和API C++庫(kù)），支持復(fù)雜信號(hào)處理中軟件及硬件的應(yīng)用。用戶通過C++完成算法編寫后，可由開發(fā)包工具轉(zhuǎn)化為硬件語言，大大簡(jiǎn)化了FPGA的設(shè)計(jì)。本文在XILINX ISE語言環(huán)境下對(duì)硬件代碼進(jìn)行了綜合。

設(shè)計(jì)的分水嶺硬件模塊如圖2所示，它直接使用ADM-XRC-5T2-ADV6開發(fā)板的架構(gòu)完成功能實(shí)現(xiàn)。圖中控制寄存器接口（CTRL registers interface）允許軟件對(duì)設(shè)計(jì)單元進(jìn)行控制、定義圖像像素的尺寸以及狀態(tài)字。CKU單元產(chǎn)生時(shí)鐘信號(hào)，初始化整個(gè)單元以及外部寄存器模塊。CTRL單元是主要單元，可以順序啟動(dòng)5個(gè)計(jì)算單元：即標(biāo)記單元（LSU）：負(fù)責(zé)初始化和標(biāo)記選擇的平坦區(qū)以及鄰域像素比較、平坦區(qū)像素的標(biāo)記。消除單元（EPU）：負(fù)責(zé)消除不含極小值的高原，以及統(tǒng)一含有極小值的平坦區(qū)。標(biāo)記傳播單元（LPU）：負(fù)責(zé)標(biāo)記的傳播。區(qū)域合并單元（RMU）：標(biāo)記控制的區(qū)域合并。分割單元（EDU）：執(zhí)行最后的分割。

處理的數(shù)據(jù)存儲(chǔ)在DDR-II靜態(tài)存儲(chǔ)器模塊中。由于上述算法在寄存器模塊和內(nèi)部計(jì)算單元之間需要大量的數(shù)據(jù)交換，因此，數(shù)據(jù)吞吐量的最大化對(duì)運(yùn)算時(shí)間有著非常重要的影響。

3 試驗(yàn)結(jié)果與討論

在XILINX VIRTEX-5 FPGA LX330T2器件上實(shí)現(xiàn)了分水嶺算法，其算法大致需要半數(shù)資源，從而為其他的處理節(jié)省了資源。由于系統(tǒng)的分辨率限制在648×648像素。如果處理的圖像像素較大，則需要拓展EPU模塊中FIFO的長(zhǎng)度。對(duì)于一幅640×480分辨率的圖像，F(xiàn)IFO的平均利用率在5000 ～10000字之間。每幀甜瓜圖像包括分水嶺算法的整體處理時(shí)間為20～40ms，比用普通的軟件方法要快10倍以上。

試驗(yàn)表明，本文采用的FPGA硬件實(shí)現(xiàn)的分水嶺算法，具有較快的圖像處理速度，可以實(shí)現(xiàn)甜瓜圖像的實(shí)時(shí)分割，達(dá)到了預(yù)期的目的，而且這種方法還可以應(yīng)用到其他水果的缺陷分割中。

［1］刁智華，趙春江，郭新宇，等.分水嶺算法的改進(jìn)方法研究[J].計(jì)算機(jī)工程，2010，36（17）：4-6.

［2］潘婷婷，李朝鋒.基于區(qū)域生長(zhǎng)型分水嶺算法的衛(wèi)星圖像道路提取方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（19）：4987-4988.

［3］楊文明，陳國(guó)斌，沈曄湖，等.一種基于分水嶺變換的圖像分割方案[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2006，40（9）：1503-1510.

［4］丁怡心，廖勇毅.高斯模糊算法優(yōu)化及實(shí)現(xiàn)[J].現(xiàn)代計(jì)算機(jī)技術(shù)，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.