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

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

0 引 言

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

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

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

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

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

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

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

圖1 果蠅覓食示意圖

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

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

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

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

xi=xaxis+randomvalue

(1)

yi=yaxis+randomvalue

(2)

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

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

(3)

Si=1/Di

(4)

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

smelli=function(Si)

(5)

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

[bestsmell,bestindex]=max(smelli)

(6)

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

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

假設(shè)圖像灰度的分布范圍是{0,1,…,L-1},若灰度值小于t的像素區(qū)域構(gòu)成目標(biāo)區(qū)域，大于t的構(gòu)成背景區(qū)域，那么各個(gè)灰度級(jí)在本區(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算法的最大熵分割算法

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

目前常用的灰度圖像為256級(jí)灰度，即灰度值最大為255，最小為0。以灰度的取值空間作為圖像閾值分割的閾值取值空間，采用八位二進(jìn)制數(shù)編碼這一空間，00000000對(duì)應(yīng)灰度為0，11111111對(duì)應(yīng)灰度為255。這樣做的好處是可以把灰度值作為味道濃度判定值，味道濃度的取值空間與灰度值的取值空間重合，可以通過(guò)簡(jiǎn)單的限定二進(jìn)制數(shù)的位數(shù)來(lái)約束灰度值與味道濃度判定值的取值范圍。若迭代步進(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)圖簡(jiǎn)單且良好的雙峰特性，不存在細(xì)微的紋理，所以采用一維最大熵的值作為適應(yīng)度函數(shù)即可快速準(zhǔn)確地分割工程圖紙。改進(jìn)后果蠅算法的流程如圖2所示。

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

2 實(shí)驗(yàn)測(cè)試分析

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

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

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

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

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

2.2 分割效果分析

誤分率(misclassification error，ME)是常用的圖片分割效果評(píng)價(jià)標(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é)果分析見(jiàn)表2。

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

2.3 收斂性能分析

以收斂性作為遺傳算法與基于改進(jìn)FOA的工程圖紙分割算法比較分析的標(biāo)準(zhǔn)，由經(jīng)驗(yàn)可知，收斂性好的算法尋優(yōu)能力較佳。在比較實(shí)驗(yàn)中迭代的最大次數(shù)設(shè)定為50，每一次實(shí)驗(yàn)獨(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é)束語(yǔ)

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