基于改進(jìn)果蠅算法的工程圖紙分割方法研究

于 灝，楊建鳴，王小剛,2

(1.內(nèi)蒙古科技大學(xué) 機(jī)械工程學(xué)院，內(nèi)蒙古 包頭 014010；2包頭鋼鐵鋼聯(lián)股份有限公司焦化廠，內(nèi)蒙古 包頭 014010)

0 引 言

隨著CAD/CAM的發(fā)展，傳統(tǒng)工程圖紙幾乎被時代所淘汰[1-3]，工程圖紙分割是圖紙以電子形式存儲與傳輸、智能識別與三維重建的必由之路。為了取得最佳分割效果，近年來越來越多的優(yōu)化算法應(yīng)用于圖像的分割與矢量化并取得了豐碩成果。張曉琳等[4]把布谷鳥算法應(yīng)用到火焰圖像的分割中，并對布谷鳥算法作了改良，取得了良好效果，大大提高了火焰圖像分割的效率；湯凌等[5]提出了一種二維最大熵法與人工免疫算法相結(jié)合的圖像分割算法，應(yīng)用在高分辨的遙感圖像上，其分割用時是傳統(tǒng)計算方法的1.8%；庹謙等[6]提出了一種遺傳算法與最大熵相結(jié)合的圖像分割算法，算法耗時縮減5%，具有較好的魯棒性與收斂性；陳愷等[7]提出了基于螢火蟲算法的二維熵多閾值快速圖像分割算法，該算法可有效解決復(fù)雜圖像的多閾值分割問題，其速度是窮舉法的幾倍或是幾千倍；李薇等[8]為了克服二維交叉熵計算復(fù)雜、計算時間長等缺點(diǎn)，引入了BBO算法，實現(xiàn)了對復(fù)雜圖像多閾值的快速準(zhǔn)確分割。

文獻(xiàn)證明了把群智能算法應(yīng)用于圖像分割技術(shù)的可行性與必要性，群智能算法的應(yīng)用不但可以提高圖像分割的準(zhǔn)確率，還可以降低計算時間與誤分率(misclassification，ME)。但是，目前的研究主要集中于特定領(lǐng)域的特定圖像，例如合成孔徑雷達(dá)(SAR)圖像與火焰圖像，或是用于處理復(fù)雜的自然圖像，幾乎沒有算法是針對工程圖紙分割的。工程圖紙具有其特定屬性，所以把現(xiàn)有算法直接拿來應(yīng)用是不合適的，不但可能結(jié)果不夠精確而且復(fù)雜的算法還會浪費(fèi)大量時間。果蠅優(yōu)化算法[9](fruit fly optimization algorithm，F(xiàn)OA)是近年來提出的模擬果蠅覓食的優(yōu)秀群智能算法，具有易于理解、編寫簡單、計算量小與全局尋優(yōu)能力強(qiáng)等特點(diǎn)[10]。

果蠅算法由于提出時間較短還存在諸多不足，文中參考遺傳算法中基因初始化與翻譯表達(dá)的機(jī)理對果蠅算法進(jìn)行改進(jìn)，引進(jìn)二進(jìn)制數(shù)把果蠅算法簡化到一維空間，結(jié)合大熵理論使其適用于圖像分割中閾值的優(yōu)化。

1 基于改進(jìn)FOA算法的最大熵分割算法

1.1 果蠅優(yōu)化算法

果蠅廣泛分布于溫帶與熱帶地區(qū)，以腐爛水果與酵母菌等為食，具有發(fā)達(dá)的感覺系統(tǒng)，尤其是視覺與嗅覺，其覓食行為也是主要在視覺與嗅覺的引導(dǎo)下完成的。果蠅依靠嗅覺感應(yīng)空氣中各種物質(zhì)所散發(fā)的氣味，最遠(yuǎn)可以嗅到在40千米處的味源，先依靠嗅覺判斷食物方向并以此為依據(jù)逼近食物，到達(dá)視力范圍后依據(jù)視力精確找到食物。果蠅以群體存在，在覓食過程中群體間共享氣味信息，比對后飛向氣味濃處進(jìn)而接近食物，在到達(dá)一定范圍后則依靠視覺精確導(dǎo)航飛向食物開始進(jìn)食[11]。

臺灣學(xué)者潘文超博士于2011年提出了果蠅優(yōu)化算法[12]，該算法具有進(jìn)化方程簡單、調(diào)整參數(shù)少等優(yōu)點(diǎn)，得到了廣泛的關(guān)注與應(yīng)用[13]。果蠅算法是一種模擬自然界中果蠅覓食行為的仿生群優(yōu)化算法，具有良好的全局尋優(yōu)能力。果蠅覓食的過程如圖1所示。

圖1 果蠅覓食示意圖

這一算法的突出之處是把種群的搜索能力與種群中個體間的信息交換進(jìn)行有機(jī)結(jié)合，通過個體之間的信息共享來逐步更新群體中的最優(yōu)解，然后整個族群以此為中心重新搜索并交換信息，當(dāng)?shù)螖?shù)達(dá)到預(yù)先設(shè)定的代數(shù)后，或是解的誤差在預(yù)定的區(qū)間之內(nèi)時終止迭代，最終達(dá)到尋找全局最優(yōu)解的目的。

經(jīng)過歸納總結(jié)，果蠅算法尋優(yōu)過程需要經(jīng)過如下步驟[14]。

(1)初始化相關(guān)參數(shù)。參數(shù)包括種群的規(guī)模(sizepop)、迭代次數(shù)(maxgen)與果蠅群所在的位置(X_axis，Y_axis)，位置隨機(jī)選取。

(2)設(shè)定果蠅尋優(yōu)的步長與方向，換言之就是以種群位置為參數(shù)分別確定種群中個體相對于種群位置所在的距離與方向，其公式為:

xi=xaxis+randomvalue

(1)

yi=yaxis+randomvalue

(2)

其中，randomvalue為迭代步進(jìn)值。

(3)由于在尋優(yōu)結(jié)束之前不知道代表最優(yōu)解的坐標(biāo)，所以只能依靠群體位置與原點(diǎn)之間的距離D來計算味道濃度判定值S，其大小等于距離D的倒數(shù)。

(3)

Si=1/Di

(4)

(4)依據(jù)具體尋優(yōu)問題設(shè)定果蠅優(yōu)化算法的味道濃度判定函數(shù)smell function，即遺傳算法中所提到的適應(yīng)度fitness function，把味道濃度判定值S帶入即可求得果蠅群中個體的味道濃度smell。

smelli=function(Si)

(5)

(5)比較得出整個族群中味道濃度最佳(最大或最小，以最大為例)的果蠅。

[bestsmell,bestindex]=max(smelli)

(6)

(6)果蠅依靠其強(qiáng)大的視覺飛向此位置，反映到算法上既是把種群的坐標(biāo)用此位置坐標(biāo)替換并記錄存儲，以便于以后的計算。

smellbest=bestsmell

(7)

xaxis=X(bestindex)

(8)

yaxis=Y(bestindex)

(9)

(7)重復(fù)步驟2～6進(jìn)行迭代尋優(yōu)，直到最大代數(shù)maxgen尋優(yōu)終止并返回最優(yōu)結(jié)果。

1.2 最大熵閾值分割

工程圖紙主要以藍(lán)圖或是白圖的形式保存，圖紙經(jīng)過掃描后得到光柵圖并灰度化，與自然圖像或是遙感圖像相比其構(gòu)圖較為簡單，并有良好的雙峰特性。最大熵法既是在圖像分割領(lǐng)域應(yīng)用Shannon熵的概念來分析工程圖紙灰度直方圖，熵取最大值時圖像中目標(biāo)區(qū)域與背景區(qū)域所分布的信息量取得極大值，以此為依據(jù)尋找閾值的最佳值分割圖像。

假設(shè)圖像灰度的分布范圍是{0,1,…,L-1},若灰度值小于t的像素區(qū)域構(gòu)成目標(biāo)區(qū)域，大于t的構(gòu)成背景區(qū)域，那么各個灰度級在本區(qū)域的分布概率分別為：pi/pt,i=1,2,…;pi/(1-pt),i=t+1,t+2,…,L-1。

目標(biāo)區(qū)域的熵為：

(10)

背景區(qū)域的熵為：

(11)

熵函數(shù)的定義為：

H(t)=Ho(t)+Hb(t)=lnpt(1-pt)+Ht/P+

(Hr-Ht)/(1-pt)

(12)

1.3 基于改進(jìn)FOA算法的最大熵分割算法

在遺傳算法中，遺傳算法是從一個代表問題解集的種群開始的，而這一種群由一定數(shù)目的染色體構(gòu)成，染色體是基因的載體，基因翻譯后會表達(dá)出不同的表現(xiàn)型，依據(jù)表現(xiàn)型的不同可以對個體進(jìn)行選擇。由于基因編碼的復(fù)雜性，在實際計算中常常使用二進(jìn)制編碼。借用這一機(jī)制，把二進(jìn)制編碼這一方式引入到果蠅算法中，并把其尋優(yōu)空間由二維降到一維。

目前常用的灰度圖像為256級灰度，即灰度值最大為255，最小為0。以灰度的取值空間作為圖像閾值分割的閾值取值空間，采用八位二進(jìn)制數(shù)編碼這一空間，00000000對應(yīng)灰度為0，11111111對應(yīng)灰度為255。這樣做的好處是可以把灰度值作為味道濃度判定值，味道濃度的取值空間與灰度值的取值空間重合，可以通過簡單的限定二進(jìn)制數(shù)的位數(shù)來約束灰度值與味道濃度判定值的取值范圍。若迭代步進(jìn)值(randomvalue)的值為r，則果蠅位置可由式11求得。若r為兩位二進(jìn)制數(shù)，則r可能的取值有00、01、10、11，則群體中果蠅的位置在種群位置的兩側(cè)且概率相同，距離中心處的距離可能為0、1、2、3。

xi=xaxis+r×(-1)r

(13)

由于工程圖具有構(gòu)圖簡單且良好的雙峰特性，不存在細(xì)微的紋理，所以采用一維最大熵的值作為適應(yīng)度函數(shù)即可快速準(zhǔn)確地分割工程圖紙。改進(jìn)后果蠅算法的流程如圖2所示。

圖2 改進(jìn)果蠅算法流程

2 實驗測試分析

對基于改進(jìn)果蠅算法的工程圖紙分割算法進(jìn)行實驗測試，實驗環(huán)境如下:操作系統(tǒng)為Windows 8.1專業(yè)版，處理器為Pentium(R)Dual-Core CPU E5300 @ 2.60 GHz，安裝內(nèi)存6 GB，在MATLAB平臺中編程實現(xiàn)。

2.1 工程圖紙分割結(jié)果

利用工程圖紙的一部分進(jìn)行實驗，并分別對窮舉搜索法、遺傳算法與基于改進(jìn)FOA的工程圖紙分割算法進(jìn)行比較，如表1所示。

表1 算法的CPU運(yùn)算時間

三種算法在分割工程圖紙的結(jié)果相差不大，都可以準(zhǔn)確地對工程圖紙進(jìn)行分割，但是三種算法計算耗時是不同的。

2.2 分割效果分析

誤分率(misclassification error，ME)是常用的圖片分割效果評價標(biāo)準(zhǔn)，反映的是被誤分到目標(biāo)區(qū)域中的背景像素的比值，用下式求得：

(14)

其中,Bo為背景區(qū)域的標(biāo)準(zhǔn)二值掩碼;Fo為目標(biāo)區(qū)域的標(biāo)準(zhǔn)二值掩碼;Bt為分割后背景區(qū)域的二值掩碼;Ft為分割后目標(biāo)區(qū)域的二值掩碼。

如果分割效果越好，則越少的背景圖像素被分割到目標(biāo)區(qū)域，即ME值越小。算法的結(jié)果分析見表2。

表2 算法的結(jié)果分析

2.3 收斂性能分析

以收斂性作為遺傳算法與基于改進(jìn)FOA的工程圖紙分割算法比較分析的標(biāo)準(zhǔn)，由經(jīng)驗可知，收斂性好的算法尋優(yōu)能力較佳。在比較實驗中迭代的最大次數(shù)設(shè)定為50，每一次實驗獨(dú)立運(yùn)行，次數(shù)為30。得到果蠅的軌跡如圖3所示。

圖3 果蠅軌跡

遺傳算法的收斂性能與基于改進(jìn)FOA的工程圖紙分割算法的收斂性能如圖4所示。由圖4可以看出，改進(jìn)FOA的工程圖紙分割算法在第10代左右基本尋到最優(yōu)值，遺傳算法則需要30代左右，因此改進(jìn)FOA的工程圖紙分割算法的收斂性高于遺傳算法，而且合理設(shè)定參數(shù)還可以進(jìn)一步提高改進(jìn)FOA的工程圖紙分割算法的運(yùn)算效率。

圖4 收斂性能

3 結(jié)束語

針對工程圖紙構(gòu)圖簡單與具有良好雙峰特性等特點(diǎn)改進(jìn)果蠅優(yōu)化算法并使其適用于工程圖紙的分割計算。首先依據(jù)遺傳算法基因的編碼、翻譯與表達(dá)機(jī)理，把二進(jìn)制數(shù)引入到果蠅算法，不但使果蠅的尋優(yōu)空間與味道濃度決定值取值空間重合而且可以獲得具有較好個體多樣性的種群，簡化了編程與計算難度，降低了運(yùn)算時間，提高了計算精度。其次把最大熵閾值分割方法與果蠅優(yōu)化算法相結(jié)合，使得果蠅優(yōu)化算法處理圖像分割問題成為了可能。實驗結(jié)果表明，基于改進(jìn)果蠅優(yōu)化算法的最大熵圖像分割算法對工程圖紙進(jìn)行分割是準(zhǔn)確可行的，并且在運(yùn)算時間與收斂性方面存在明顯優(yōu)勢。但是果蠅算法在穩(wěn)定性方面有待提高，果蠅算法的穩(wěn)定性及果蠅算法與其他圖像分割理論的結(jié)合還有待進(jìn)一步的研究。