基于改进果蝇算法的工程图纸分割方法研究

于 灏，杨建鸣，王小刚,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 结束语

针对工程图纸构图简单与具有良好双峰特性等特点改进果蝇优化算法并使其适用于工程图纸的分割计算。首先依据遗传算法基因的编码、翻译与表达机理，把二进制数引入到果蝇算法，不但使果蝇的寻优空间与味道浓度决定值取值空间重合而且可以获得具有较好个体多样性的种群，简化了编程与计算难度，降低了运算时间，提高了计算精度。其次把最大熵阈值分割方法与果蝇优化算法相结合，使得果蝇优化算法处理图像分割问题成为了可能。实验结果表明，基于改进果蝇优化算法的最大熵图像分割算法对工程图纸进行分割是准确可行的，并且在运算时间与收敛性方面存在明显优势。但是果蝇算法在稳定性方面有待提高，果蝇算法的稳定性及果蝇算法与其他图像分割理论的结合还有待进一步的研究。