基于改進果蠅算法的工程圖紙分割方法研究

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

(1.內蒙古科技大學 機械工程學院，內蒙古 包頭 014010；2包頭鋼鐵鋼聯股份有限公司焦化廠，內蒙古 包頭 014010)

0 引 言

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

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

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

1 基于改進FOA算法的最大熵分割算法

1.1 果蠅優化算法

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

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

圖1 果蠅覓食示意圖

這一算法的突出之處是把種群的搜索能力與種群中個體間的信息交換進行有機結合，通過個體之間的信息共享來逐步更新群體中的最優解，然后整個族群以此為中心重新搜索并交換信息，當迭代次數達到預先設定的代數后，或是解的誤差在預定的區間之內時終止迭代，最終達到尋找全局最優解的目的。

經過歸納總結，果蠅算法尋優過程需要經過如下步驟[14]。

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

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

xi=xaxis+randomvalue

(1)

yi=yaxis+randomvalue

(2)

其中，randomvalue為迭代步進值。

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

(3)

Si=1/Di

(4)

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

smelli=function(Si)

(5)

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

[bestsmell,bestindex]=max(smelli)

(6)

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

smellbest=bestsmell

(7)

xaxis=X(bestindex)

(8)

yaxis=Y(bestindex)

(9)

(7)重復步驟2～6進行迭代尋優，直到最大代數maxgen尋優終止并返回最優結果。

1.2 最大熵閾值分割

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

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

目標區域的熵為：

(10)

背景區域的熵為：

(11)

熵函數的定義為：

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

(Hr-Ht)/(1-pt)

(12)

1.3 基于改進FOA算法的最大熵分割算法

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

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

xi=xaxis+r×(-1)r

(13)

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

圖2 改進果蠅算法流程

2 實驗測試分析

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

2.1 工程圖紙分割結果

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

表1 算法的CPU運算時間

三種算法在分割工程圖紙的結果相差不大，都可以準確地對工程圖紙進行分割，但是三種算法計算耗時是不同的。

2.2 分割效果分析

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

(14)

其中,Bo為背景區域的標準二值掩碼;Fo為目標區域的標準二值掩碼;Bt為分割后背景區域的二值掩碼;Ft為分割后目標區域的二值掩碼。

如果分割效果越好，則越少的背景圖像素被分割到目標區域，即ME值越小。算法的結果分析見表2。

表2 算法的結果分析

2.3 收斂性能分析

以收斂性作為遺傳算法與基于改進FOA的工程圖紙分割算法比較分析的標準，由經驗可知，收斂性好的算法尋優能力較佳。在比較實驗中迭代的最大次數設定為50，每一次實驗獨立運行，次數為30。得到果蠅的軌跡如圖3所示。

圖3 果蠅軌跡

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

圖4 收斂性能

3 結束語

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