于灝 王小剛 楊建鳴

摘 ?要： 針對工程圖紙分割運(yùn)算時間長、效率低的問題，提出一種基于蝙蝠算法（BA）的最大熵工程圖紙分割算法。通過引入二進(jìn)制編碼機(jī)制模擬遺傳學(xué)中基因的編碼、翻譯與表達(dá)，優(yōu)化BA算法中蝙蝠位置的初始化，使其易于約束位置的初始空間與產(chǎn)生多樣性良好的種群。實驗結(jié)果證明：基于BA算法的分割效果與窮舉法相同，優(yōu)于基于果蠅算法（FOA）的分割方法;運(yùn)算時間遠(yuǎn)小于窮舉法，約是基于FOA算法的50%;收斂性與魯棒性明顯優(yōu)于基于FOA的分割算法。

關(guān)鍵詞： 工程圖紙; 圖像識別; 圖像分割; 閾值法; 蝙蝠算法; 最大熵

中圖分類號： TN911.73?34; TP391.4 ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）13?0069?04

Research on engineering drawing segmentation method

YU Hao1， WANG Xiaogang1， 2， YANG Jianming1

（1. School of Mechanical Engineering， Inner Mongolia University of Science and Technology， Baotou 014010， China;

2. Coal Coke Chemical Branch of Baogang united Steel， Baotou 014010， China）

Abstract： A maximum entropy engineering drawing segmentation method based on bat algorithm （BA） is proposed to shorten the computing time and improve the efficiency of engineering drawing segmentation algorithm. By means of introducing the binary encoding mechanism， the encoding， translation and expression of gene in genetics are simulated， the initialization of bat position is optimized in BA algorithm to make it easier to locate in constrain positional initial space and generate the population with better diversification. The experimental results show that the segmentation effect of the method based on BA algorithm is superior to that of the method based on fruit fly optimization algorithm （FOA）， and is just the same as that of exhaustion method; but its operation time is only 50% of FOA algorithm， and is much shorter than that of exhaustion method; the convergence and robustness of the proposed method is obviously superior to that of the segmentation method based on FOA.

Keywords： engineering drawing; image identification; image segmentation; threshold method; bat algorithm; maximum entropy

0 ?引 ?言

工程圖紙分割是計算機(jī)識別圖紙信息、理解與三維重建的基礎(chǔ)所在，雖然已經(jīng)取得了相當(dāng)成果，但是尚有不足之處[1]。工程圖紙的智能識別與重建不但是CAD領(lǐng)域的重要課題還是制造業(yè)信息化的關(guān)鍵技術(shù)[2]。圖像分割是計算機(jī)提取圖像信息的關(guān)鍵一步，工程圖紙的分割是圖像分割的具體應(yīng)用。

隨著科學(xué)技術(shù)的發(fā)展，大量的優(yōu)化算法產(chǎn)生并被應(yīng)用到數(shù)字圖像處理中。文獻(xiàn)[3]利用混沌理論與蛙跳算法改進(jìn)布谷鳥算法，應(yīng)用于火焰圖像的分割，取得較佳效果。文獻(xiàn)[4]提出一種改進(jìn)布谷鳥算法并與模糊C均值聚類算法結(jié)合，算法不僅取得了較好的分割效果，效率也有所提高。文獻(xiàn)[5]提出基于隨機(jī)森林算法的分割方法，正確識別率高達(dá)95%，處理時間為1.6 s左右。文獻(xiàn)[6]引進(jìn)云模型改進(jìn)人工魚群算法，解決了傳統(tǒng)算法收斂慢與易陷入局部最優(yōu)的問題。文獻(xiàn)[7]提出基于改進(jìn)小生境遺傳算法的圖像分割算法，算法具有較強(qiáng)的全局搜索能力，魯棒性較強(qiáng)。

上述文獻(xiàn)說明把優(yōu)化算法應(yīng)用于圖像分割領(lǐng)域的優(yōu)勢所在，但目前很少有專門針對工程圖紙分割的研究，把智能算法用于工程圖紙的分割幾乎沒有。工程圖紙相比于其他圖像具有構(gòu)圖簡單、背景均勻且直方圖有明顯雙峰性的特點，依據(jù)工程圖的特點提出專門用于工程圖紙分割的方法是可行的。

1 ?BA算法與最大熵法

1.1 ?蝙蝠優(yōu)化算法

蝙蝠通過回聲定位來捕捉獵物和躲避障礙物。飛行時不斷發(fā)出聲音脈沖與接收這些脈沖的回音，脈沖的頻率可以是變化的也可以是恒定的。

蝙蝠在搜尋獵物時所發(fā)出脈沖的頻度隨著與獵物距離的減小而增加，微型蝙蝠在遠(yuǎn)離獵物處所發(fā)出的脈沖個數(shù)約10～20次，在靠近獵物處脈沖頻度可迅速高達(dá)200次，其處理信息的時間一般小于500 [μs]。

理想化蝙蝠利用超聲回聲定位捕食的原理，提出一種啟發(fā)式算法即蝙蝠算法（Bat Algorithm，BA），其具體規(guī)則如下[8?10]：

1） 蝙蝠都是依靠回聲定位來躲避障礙物與逼近獵物的，忽略其視覺與嗅覺的作用。

2） 假設(shè)蝙蝠在位置[xi]處隨機(jī)飛行且其飛行速度是[vi]，搜索獵物的頻率為[fi]，聲音的響度為[Ai]，而且其搜索頻率會隨其與獵物之間的距離按一定的規(guī)律進(jìn)行變化。

3） 假設(shè)蝙蝠所發(fā)出脈沖的響度隨距離的增大而減小，響度的最大值為[Amax]，最小值為[Amin]。

為了簡便算法，易于編程，BA算法做出如下簡化：規(guī)定頻率的范圍是[fmin，fmax，]波長的范圍是[λmin，λmax]。設(shè)定搜索空間維度為[D]，[t+1]時刻蝙蝠[i]的位置與速度可由如下公式求得：

1.2 ?最大熵法

最大熵法是Shannon熵理論在圖像分割中的具體應(yīng)用，當(dāng)直方圖的熵取最大值時，分割結(jié)果最佳。實驗證明Otsu在分割白圖時會過分割，丟失幾乎全部的圖紙信息，處理藍(lán)圖時會造成欠分割的現(xiàn)象，過多背景像素?fù)诫s于目標(biāo)之中，工程圖紙信息難以讀取，但是其對復(fù)雜自然圖像有較好的處理效果。最大熵法處理工程圖紙結(jié)果優(yōu)于Otsu法，對大多數(shù)工程圖紙可以進(jìn)行正確分割，所以采用最大熵作為BA算法的適應(yīng)度。

2 ?基于BA的最大熵分割方法

模擬生物遺傳中基因編碼、翻譯與表達(dá)的機(jī)理，參照遺傳算法引進(jìn)二進(jìn)制編碼機(jī)制，由于所處理工程圖紙灰度化后的圖像是8 bit圖像，所以在初始化蝙蝠位置時采用8位二進(jìn)制編碼，編碼00000000對應(yīng)0灰度即黑色，編碼11111111對應(yīng)255灰度即白色。

采用二進(jìn)制編碼初始化蝙蝠位置可以有效約束初始解的取值空間，獲得良好多樣性的種群。以圖像在某一閾值的熵值作為算法的適應(yīng)度值，適應(yīng)度值最大時即取得最大熵值。

基于BA最大熵算法的程序如下：

1） 初始化種群規(guī)模與迭代終止條件，確定算法的適應(yīng)度函數(shù)。

2） 初始化蝙蝠種群的位置與速度，計算初始頻率，選定頻度與響度的初值;尋找并記錄最佳個體適應(yīng)度值與位置。

3） 依據(jù)式（1）～式（3），計算并更新蝙蝠的速度與位置。

4） 產(chǎn)生隨機(jī)數(shù)rand1，如果隨機(jī)數(shù)大于此時的頻度，則依據(jù)式（4）擾動產(chǎn)生新的解。

5） 計算所有個體適應(yīng)度值。

6） 產(chǎn)生隨機(jī)數(shù)rand2，如果隨機(jī)數(shù)小于此時的響度，并且此時的適應(yīng)度值大于上一次產(chǎn)生的最優(yōu)適應(yīng)度值，則接受這一新的解，并依據(jù)式（5）與式（6）更新響度與頻度。

7） 更新全局最優(yōu)解，判斷終止條件。是，則輸出結(jié)果;否，則轉(zhuǎn)到步驟3）。

3 ?實驗結(jié)果分析

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

3.1 ?實驗閾值

實驗采用窮舉最大熵法、基于FOA（Fruit Fly Optimization Algorithm，果蠅算法）最大熵法與本文基于BA的最大熵法進(jìn)行比較，圖1是實驗圖像的熵與灰度的關(guān)系圖。實驗分別用3種算法進(jìn)行20次獨立實驗，F(xiàn)OA與BA的種群規(guī)模都是10，最大迭代次數(shù)都是60。

圖1 ?實驗圖紙的熵

基于BA的最大熵分割方法在分割效果上與窮舉法相同，兩種方法結(jié)果優(yōu)于基于FOA的工程圖紙分割算法。20次實驗所得到的閾值如圖2所示，可以看出在閾值上BA的精度與穩(wěn)定性優(yōu)于FOA。

3.2 ?運(yùn)算時間

運(yùn)算時間是衡量一個算法好壞的重要標(biāo)準(zhǔn)，由實驗結(jié)果可知，基于FOA的最大熵分割方法與基于BA的最大熵分割方法所用時間都遠(yuǎn)小于窮舉法;BA與FOA相比，BA用時約是FOA用時的50%，如圖3所示。

圖2 ?閾值比較

圖3 ?時間比較

3.3 ?收斂性

收斂性是評判算法優(yōu)劣的重要指標(biāo)，實驗中初始位置隨機(jī)產(chǎn)生，以收斂到最優(yōu)值的最小代數(shù)與最小代數(shù)的標(biāo)準(zhǔn)差作為衡量標(biāo)準(zhǔn)。雖然初始位置是隨機(jī)產(chǎn)生（初始位置影響收斂代數(shù)，初始位置越接近最優(yōu)值所需代數(shù)越少），但是BA收斂代數(shù)基本都集中在10～20之間，F(xiàn)OA的收斂代數(shù)則是在1～60之間。當(dāng)實驗中當(dāng)取值遠(yuǎn)離最優(yōu)解時FOA收斂性較慢，圖4是初始值為47時，BA與FOA的收斂性能圖。

圖4 ?收斂性能

4 ?結(jié) ?語

本文針對工程圖紙分割時間長，提出一種基于BA的最大熵工程圖紙分割算法。算法參考遺傳學(xué)中基因的編碼、翻譯與表達(dá)機(jī)理，引進(jìn)二進(jìn)制數(shù)編碼方式初始化BA中蝙蝠的位置，通過改變編碼位數(shù)有效控制初始解的取值空間，生成多樣性種群。比較分析選擇最大熵理論作為BA的適應(yīng)度函數(shù)，可獲得比Otsu法更好的分割效果。實驗比較了基于BA分割方法、基于FOA和窮舉法，實驗結(jié)果顯示，BA可精確分割工程圖紙，所用時間是基于FOA的50%，且遠(yuǎn)小于窮舉法，收斂性與魯棒性均優(yōu)于基于FOA的分割方法。

參考文獻(xiàn)

[1] 杜益福.基于圖割理論的圖像分割和三維重建方法研究[D].秦皇島：燕山大學(xué)，2013.

DU Yifu. Study on image segmentation and three?dimensional reconstruction based on graph?cutting theory [D]. Qinhuangdao： Yanshan University， 2013.

[2] 文雅玫.基于帶剖視工程圖的三維重建算法研究[D].北京：清華大學(xué)，2012.

WEM Yamei. Study on three?dimensional reconstruction algorithm based on cross?sectional drawing [D]. Beijing： Tsinghua University， 2012.

[3] 張曉琳，張沖，楊濤.基于改進(jìn)布谷鳥算法的火焰圖像閾值分割算法[J].微電子學(xué)與計算機(jī)，2017，34（1）：66?70.

ZHANG Xiaolin， ZHANG Chong， YANG Tao. Threshold segmentation algorithm for flame image based on improved cuckoo algorithm [J]. Microelectronics and computer， 2017， 34（1）： 66?70.

[4] 朱春，林國，郭劍.基于改進(jìn)布谷鳥優(yōu)化的模糊聚類圖像分割[J].計算機(jī)科學(xué)，2017，44（6）：278?282.

ZHU Chun， LIN Guo， GUO Jian. Fuzzy clustering image segmentation based on improved cuckoo optimization [J]. Computer science， 2017， 44（6）： 278?282.

[5] 張經(jīng)緯，貢亮，黃亦翔，等.基于隨機(jī)森林算法的黃瓜種子腔圖像分割方法[J].農(nóng)機(jī)化研究，2017，39（10）：163?168.

ZHANG Jingwei， GONG Liang， HUANG Yixiang， et al. Segmentation of cucumber seed cavity based on random forest algorithm [J]. Journal of agricultural mechanization research， 2017， 39（10）： 163?168.

[6] 崔麗群，黃殿平，宋曉.基于云模型魚群算法的多閾值圖像分割研究[J].計算機(jī)工程與應(yīng)用，2017，53（6）：204?208.

CUI Liqun， HUANG Dianping， SONG Xiao. Multi?threshold image segmentation based on cloud model fish?swarm algorithm [J]. Computer engineering and applications， 2017， 53（6）： 204?208.

[7] 李陽，歸偉夏.一種基于改進(jìn)小生境遺傳算法的圖像分割方法[J].計算機(jī)應(yīng)用與軟件，2017，34（4）：202?206.

LI Yang， GUI Weixia. An image segmentation method based on improved niche genetic algorithm [J]. Journal of computer applications and software， 2017， 34（4）： 202?206.

[8] YANG X. A new metaheuristic bat?inspired algorithm [M/OL]. Anon. Nature inspired cooperative strategies for optimization. Berlin： Springer， 2010： 65?74.

[9] 李煜，馬良.新型全局優(yōu)化蝙蝠算法[J].計算機(jī)科學(xué)，2013，40（9）：225?229.

LI Yu， MA Liang. New global optimization bats algorithm [J]. Computer science， 2013， 40（9）： 225?229.

[10] 薛菲.基于蝙蝠算法的啟發(fā)式智能優(yōu)化研究與應(yīng)用[D].北京：北京工業(yè)大學(xué)，2016.

XUE Fei. Study and application of heuristic intelligent optimization based on bats algorithm [D]. Beijing： Beijing University of Technology， 2016.