于灏 王小刚 杨建鸣

摘  要： 针对工程图纸分割运算时间长、效率低的问题，提出一种基于蝙蝠算法（BA）的最大熵工程图纸分割算法。通过引入二进制编码机制模拟遗传学中基因的编码、翻译与表达，优化BA算法中蝙蝠位置的初始化，使其易于约束位置的初始空间与产生多样性良好的种群。实验结果证明：基于BA算法的分割效果与穷举法相同，优于基于果蝇算法（FOA）的分割方法;运算时间远小于穷举法，约是基于FOA算法的50%;收敛性与鲁棒性明显优于基于FOA的分割算法。

关键词： 工程图纸; 图像识别; 图像分割; 阈值法; 蝙蝠算法; 最大熵

中图分类号： TN911.73?34; TP391.4                文献标识码： 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  引  言

工程圖纸分割是计算机识别图纸信息、理解与三维重建的基础所在，虽然已经取得了相当成果，但是尚有不足之处[1]。工程图纸的智能识别与重建不但是CAD领域的重要课题还是制造业信息化的关键技术[2]。图像分割是计算机提取图像信息的关键一步，工程图纸的分割是图像分割的具体应用。

随着科学技术的发展，大量的优化算法产生并被应用到数字图像处理中。文献[3]利用混沌理论与蛙跳算法改进布谷鸟算法，应用于火焰图像的分割，取得较佳效果。文献[4]提出一种改进布谷鸟算法并与模糊C均值聚类算法结合，算法不仅取得了较好的分割效果，效率也有所提高。文献[5]提出基于随机森林算法的分割方法，正确识别率高达95%，处理时间为1.6 s左右。文献[6]引进云模型改进人工鱼群算法，解决了传统算法收敛慢与易陷入局部最优的问题。文献[7]提出基于改进小生境遗传算法的图像分割算法，算法具有较强的全局搜索能力，鲁棒性较强。

上述文献说明把优化算法应用于图像分割领域的优势所在，但目前很少有专门针对工程图纸分割的研究，把智能算法用于工程图纸的分割几乎没有。工程图纸相比于其他图像具有构图简单、背景均匀且直方图有明显双峰性的特点，依据工程图的特点提出专门用于工程图纸分割的方法是可行的。

1  BA算法与最大熵法

1.1  蝙蝠优化算法

蝙蝠通过回声定位来捕捉猎物和躲避障碍物。飞行时不断发出声音脉冲与接收这些脉冲的回音，脉冲的频率可以是变化的也可以是恒定的。

蝙蝠在搜寻猎物时所发出脉冲的频度随着与猎物距离的减小而增加，微型蝙蝠在远离猎物处所发出的脉冲个数约10～20次，在靠近猎物处脉冲频度可迅速高达200次，其处理信息的时间一般小于500 [μs]。

理想化蝙蝠利用超声回声定位捕食的原理，提出一种启发式算法即蝙蝠算法（Bat Algorithm，BA），其具体规则如下[8?10]：

1） 蝙蝠都是依靠回声定位来躲避障碍物与逼近猎物的，忽略其视觉与嗅觉的作用。

2） 假设蝙蝠在位置[xi]处随机飞行且其飞行速度是[vi]，搜索猎物的频率为[fi]，声音的响度为[Ai]，而且其搜索频率会随其与猎物之间的距离按一定的规律进行变化。

3） 假设蝙蝠所发出脉冲的响度随距离的增大而减小，响度的最大值为[Amax]，最小值为[Amin]。

为了简便算法，易于编程，BA算法做出如下简化：规定频率的范围是[fmin，fmax，]波长的范围是[λmin，λmax]。设定搜索空间维度为[D]，[t+1]时刻蝙蝠[i]的位置与速度可由如下公式求得：

1.2  最大熵法

最大熵法是Shannon熵理论在图像分割中的具体应用，当直方图的熵取最大值时，分割结果最佳。实验证明Otsu在分割白图时会过分割，丢失几乎全部的图纸信息，处理蓝图时会造成欠分割的现象，过多背景像素掺杂于目标之中，工程图纸信息难以读取，但是其对复杂自然图像有较好的处理效果。最大熵法处理工程图纸结果优于Otsu法，对大多数工程图纸可以进行正确分割，所以采用最大熵作为BA算法的适应度。

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

模拟生物遗传中基因编码、翻译与表达的机理，参照遗传算法引进二进制编码机制，由于所处理工程图纸灰度化后的图像是8 bit图像，所以在初始化蝙蝠位置时采用8位二进制编码，编码00000000对应0灰度即黑色，编码11111111对应255灰度即白色。

采用二进制编码初始化蝙蝠位置可以有效约束初始解的取值空间，获得良好多样性的种群。以图像在某一阈值的熵值作为算法的适应度值，适应度值最大时即取得最大熵值。

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

1） 初始化种群规模与迭代终止条件，确定算法的适应度函数。

2） 初始化蝙蝠种群的位置与速度，计算初始频率，选定频度与响度的初值;寻找并记录最佳个体适应度值与位置。

3） 依据式（1）～式（3），计算并更新蝙蝠的速度与位置。

4） 产生随机数rand1，如果随机数大于此时的频度，则依据式（4）扰动产生新的解。

5） 计算所有个体适应度值。

6） 产生随机数rand2，如果随机数小于此时的响度，并且此时的适应度值大于上一次产生的最优适应度值，则接受这一新的解，并依据式（5）与式（6）更新响度与频度。

7） 更新全局最优解，判断终止条件。是，则输出结果;否，则转到步骤3）。

3  实验结果分析

基于BA的工程图纸分割算法进行实验测试，实验环境如下：操作系统Windows 8专业版，处理器Pentium[?]Dual?Core CPU E5300 @ 2.60 GHz 2.60 GHz，安装内存6 GB，在Matlab平台中编程实现。

3.1  实验阈值

实验采用穷举最大熵法、基于FOA（Fruit Fly Optimization Algorithm，果蝇算法）最大熵法与本文基于BA的最大熵法进行比较，图1是实验图像的熵与灰度的关系图。实验分别用3种算法进行20次独立实验，FOA与BA的种群规模都是10，最大迭代次数都是60。

图1  实验图纸的熵

基于BA的最大熵分割方法在分割效果上与穷举法相同，两种方法结果优于基于FOA的工程图纸分割算法。20次实验所得到的阈值如图2所示，可以看出在阈值上BA的精度与稳定性优于FOA。

3.2  运算时间

运算时间是衡量一个算法好坏的重要标准，由实验结果可知，基于FOA的最大熵分割方法与基于BA的最大熵分割方法所用时间都远小于穷举法;BA与FOA相比，BA用时约是FOA用时的50%，如图3所示。

图2  阈值比较

圖3  时间比较

3.3  收敛性

收敛性是评判算法优劣的重要指标，实验中初始位置随机产生，以收敛到最优值的最小代数与最小代数的标准差作为衡量标准。虽然初始位置是随机产生（初始位置影响收敛代数，初始位置越接近最优值所需代数越少），但是BA收敛代数基本都集中在10～20之间，FOA的收敛代数则是在1～60之间。当实验中当取值远离最优解时FOA收敛性较慢，图4是初始值为47时，BA与FOA的收敛性能图。

图4  收敛性能

4  结  语

本文针对工程图纸分割时间长，提出一种基于BA的最大熵工程图纸分割算法。算法参考遗传学中基因的编码、翻译与表达机理，引进二进制数编码方式初始化BA中蝙蝠的位置，通过改变编码位数有效控制初始解的取值空间，生成多样性种群。比较分析选择最大熵理论作为BA的适应度函数，可获得比Otsu法更好的分割效果。实验比较了基于BA分割方法、基于FOA和穷举法，实验结果显示，BA可精确分割工程图纸，所用时间是基于FOA的50%，且远小于穷举法，收敛性与鲁棒性均优于基于FOA的分割方法。

参考文献

[1] 杜益福.基于图割理论的图像分割和三维重建方法研究[D].秦皇岛：燕山大学，2013.

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

[2] 文雅玫.基于带剖视工程图的三维重建算法研究[D].北京：清华大学，2012.

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

[3] 张晓琳，张冲，杨涛.基于改进布谷鸟算法的火焰图像阈值分割算法[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].计算机科学，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].农机化研究，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].计算机工程与应用，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].计算机应用与软件，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] 李煜，马良.新型全局优化蝙蝠算法[J].计算机科学，2013，40（9）：225?229.

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

[10] 薛菲.基于蝙蝠算法的启发式智能优化研究与应用[D].北京：北京工业大学，2016.

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