动态权重的蝙蝠算法在图像分割中的应用研究

陈 瑶，陈 思

1.西京学院 理学院，西安 710123

2.西北工业大学 理学院，西安 710072

1 引言

随着人工智能技术（Artificial Intelligence）、计算机科学技术（Computer Science）等研究领域的深入发展，广大学者开始将数字图像处理带向更深、更高的研究水平，开始通过计算机系统对图像进行理解，尝试用计算机模仿人类视觉系统用以理解图像信息，这就是计算机视觉技术。图像分割（Image Segmentation）作为计算机视觉中的关键技术之一，是对已有的原始图像进行预处理的过程，经过预处理为后续图像的进一步精确解析做基础，因此图像分割具有承上启下的重要意义。具体来说，图像分割就是将原始图像分割成若干个不同的区域，尽管目前已提出众多边缘提取、区域分割的算法，然而还没有找到一种可以普遍适用的有效算法，因此图像分割仍然是目前研究的热点问题之一。

传统的图像分割方法主要包括：阈值分割法、聚类分割法、边缘检测法以及区域提取法。在这些方法中，阈值分割法是最常用的方法，和其他方法相比，它具有算法操作简单、计算复杂度低，分割性能稳定的优点。目前，学者们已经提出了大量关于阈值分割的综合性研究方法[1-3]。针对阈值选取问题，许多学者从原始图像的直方图中提取了一些统计属性用于阈值选择，例如最大似然方法[4]、类间方差法[5]和熵[6]。这些阈值方法大致分为两类，第一类是使用直方图的轮廓特征并找到阈值的方法。例如：Rosenfeld等人使用直方图中凹面的凸包来确定阈值选择[7]；Lim和Lee提出了一种新方法，该方法使用模糊C均值技术通过计算平滑直方图的导数来检测谷值作为阈值[8]；Yin等人使用了一种通过直方图特征进行阈值选择的方法[9]。第二类是使用某个目标函数来获得最佳阈值的方法。具有代表性的有：Otsu最大化了对象和背景部分的方差分析，进而进行阈值选择[5]；Pun提出了一种使目标和背景部分的熵最大化以找到最佳值的方法[10]。在众多的阈值分割技术中，基于熵的方法始终被广大学者认为是阈值选择算法的有效手段。

随着计算智能的发展[11]，研究者们先后提出了各种新型的自然启发式算法[12-15]，这类算法被广泛应用于各种复杂的优化问题中（例如线性规划、动态规划、整数规划等），并被证明是有效的。这类自然启发式算法主要是模拟某些自然现象或过程而形成的，是一类迭代算法，启发式算法和传统的搜索算法相比具有很多优势，它的搜索策略是结构化和随机化的方式，因此具有很强的全局性、通用性和并行性。同时，启发式算法对复杂优化问题的数学描述并不要求所解决的问题是满足可微、凸性等条件，它是将种群视为一组解作为迭代的初始值，将所求解的问题参数进行编码并将其映射为可操作的数据结构，进而对问题进行有效求解。由于很多数字图像处理问题都可以转化为一类优化问题，而启发式算法作为一类可以高效求解优化问题的方法被成功应用于各类图像处理问题中[16-18]。其中，图像分割问题实质上就是一个在复杂的参数空间里寻找最优的分割参数的寻优问题。对该类复杂寻优问题，由于对求解准确度和速度的要求已经不是传统优化算法（例如单纯形法和基于梯度的各类迭代算法）所能解决的，因此各种群智能优化算法用以解决图像分割问题受到广大学者的青睐，例如 GA[19]、ACO[20]、PSO[21]、CSO[22]。Sood 等人针对欠分割和过分割的问题利用GA找到最优阈值，完成分割皮肤损伤图像，但这类算法的分割图像速度较慢[23]；Taherdangkoo等人利用蚁群算法对医学磁力共振图像中的相似点进行寻找，以找到最优阈值完成图像分割，但在分割精度上还需要进一步改善[24]；Mohsenl等人利用粒子群算法进行图像分割，虽分割速度较快，但分割的准确度还有待提高[25]；王光彪等人把CSO应用到图像分类中，将组合优化求解转化为猫群的位置进行搜寻[26]；张效杰等人针对Otsu算法应用到多阈值图像分割时运算量过大的问题，将BFO算法运用到多阈值图像分割中[27]。

除此以外，近年来深度神经网络方法在图像分割中也取得了令人满意的结果。该方法比起传统处理算法有较大的优点，但也存在着一些缺点，例如在图像分割这类图像预处理阶段，基于神经网络的方法大部分是非自适应性的，这些算法往往是针对某类特定的图像模型，一旦原始图像模型发生变换时（如最简单的缩放和角度变换），神经网络的权值也都需要重新训练。同时，基于像素的神经网络图像分割方法需要处理的数据量太大，不适合于实时性的数据处理；基于特征的神经网络图像分割方法无法保证抽取的特征就是有效的图像特征，并且该类方法的前提假设是所处理的图像没有受到污染，具有一定限制性。因此，使用新型的群智能算法进行图像分割处理一方面为图像分割处理提供了一类相对操作简单的新思路，另一方面也扩大了该类算法的应用领域。

本文选用的BA算法属于新型群智能优化算法中的一种，是由英国学者Yang在2010年基于蝙蝠回声定位行为提出的一种新型群智能启发式算法[28]。同其他智能算法一样，BA算法易于实现、可适用范围广，尤其在求解高维优化问题时表现突出，日益成为学者研究的焦点。Yang等使用BA算法进行多目标优化的工程设计[29]；Gandomi等使用BA算法求解工程全局优化问题[30]；Mishra等使用BA算法对数据进行分类[31]；孙奇等重新定义了蝙蝠的编码方式并利用GRASP启发式算法生成蝙蝠算法初始种群来改进算法，然后应用于求解车辆路径问题[32]；尹建津等提出了一种改进的连续蝙蝠算法用于解决柔性流水车间调度问题[33]。然而，很少有文献使用BA算法来求解图像分割问题，因此具有研究意义。在图像分割问题中，一幅灰度级为256，大小为300×300的灰度图像，就有90 000个像素，很多情况下算法的计算复杂度很高，使用BA算法求解图像分割问题的优点在于它不仅具备类似PSO、ACO、BFO等群智能算法能保留历史最优解以利于种群进化，具有本质的并行性，可对复杂的非线性多维数据空间进行快速有效的计算；同时，它采用实数编码直接在问题域上求解，无需进制转换，易于实现，没有类似GA算法中较为复杂的交叉、变异等操作，更容易编程实现；此外，BA算法的参数设置相对于其他群智能算法较少，且有一定的约束范围，这些机制保证了BA算法的相对稳定性。美中不足的是BA算法在图像分割领域的文献研究不多，不能系统直观地对比不同分割方法（如阈值法、聚类法等）在BA算法中的效果，一定程度上降低了算法的可比性。

本文将改进的BA算法成功应用于最小交叉熵多阈值分割问题中。由于基本的BA算法存在容易陷入局部最优无法跳出，在靠近最优解时的收敛速度下降的问题，为了增加算法多样性更好地开发算法的探索能力从而解决不足，提出了改进的BA算法。使用随着迭代次数的变化而变化的动态权重机制来更新算法模式。为了验证改进算法的有效性，选取了6个经典的测试函数对改进算法进行了数值仿真实验。最后将改进的BA算法应用于最小交叉熵多阈值分割问题中，并与其他3种算法进行了对比实验，实验结果证明该算法是可行且有效的。

2 基本BA算法

BA算法是受到蝙蝠种群在捕猎时的自然过程的启发而提出的一种新型群智能仿生算法，它是一类基于种群的随机全局优化技术。众所周知，蝙蝠在夜间捕猎，利用声呐探测猎物和障碍物的位置，这种行为都是依赖于蝙蝠种群自身拥有的回声定位系统。蝙蝠种群通过发出一定频率的声音脉冲，然后依据回声定位确定猎物或者障碍物的位置，在黑暗中成功觅食。Yang根据蝙蝠捕食的过程，于2010年提出BA算法，算法的数学表示为：

其中，fi,fmax,fmin分别表示第i只蝙蝠当前时刻发出的声波频率以及声波频率的最大值和最小值。β∈[0,1]为一个随机向量，p表示当前最优位置。开始时每只蝙蝠随机分配频率，频率是从[fmin,fmax]平均得出的。

3 改进BA算法

3.1 基于时变动态权重的改进BA算法

BA算法同其他智能算法相比，具有参数设置少易于操作的优点，其中权重系数ω就是蝙蝠算法为数不多参数中的一个，在算法中具有很重要的地位。一般来说，固定的权重取值和随时间变化的权重取值是权重系数的两个最主要的选择。在算法迭代过程中，固定权重是将权重系数固定地取为某个值（一般通过经验来取值），在整个优化过程中稳定不变。而随时间变化的权重系数则是随着迭代次数的增加惯性权重也随之不断变化，是动态改变的值。在整个寻优过程中，它是以一定的减速度降低，因此呈现不同的值。通过大量的数值仿真实验分析得出较大的权重系数将使蝙蝠个体具有更大的速度，从而增强蝙蝠的探索能力；另一方面较小的权重系数会使蝙蝠个体具有更强的开发能力。因此，算法的优化效果在很大程度上取决于权重系数的选择。

从基本蝙蝠算法中的速度更新公式可以看出，在基本算法中速度项的系数始终为1，这大大降低了蝙蝠个体及种群的多样性，容易导致算法全局搜索和局部搜索的不均衡。针对这个问题学者们在速度更新公式的改进方面做了一系列研究，如陈梅雯等[34]提出了一种求解多维全局优化的改进蝙蝠算法，在速度更新公式中增加了权重系数（式（4）所示）；龙文等[35]引入惯性权重以协调算法的勘探和开发能力，并用以求解约束优化问题（式（5）所示）；裴宇航等[36]设计了一种随机的惯性权重用以改进蝙蝠算法（如式（6）所示）；本文提出了三种不同衰减形态的时变动态权重系数（式（7）所示）。式（4）是所列举改进思想中最简单的一个，是单一的线性递减策略，同其他权重相比，对速度的影响不大，对算法多样性的改进程度较低。式（5）虽然采用了非线性递减策略，但是权重的选取与当前所有个体的平均目标函数值密切相关，而该值并不能显示当前蝙蝠个体是否达到了最优值，因此会导致权重的不恰当选取。式（6）为随机权重策略，其包含了均匀分布、正态分布及各种不对称分布，权重的取值非常灵活，因此很大程度上取值太过随机，降低了算法的稳定性能。本文提出的3种不同衰减形态的权重策略则考虑了线性衰减、非线性衰减（二次函数和指数函数形式）的不同模式，并且惯性权重是由种群迭代次数t来决定的，即每一代内蝙蝠种群的惯性权重保持一致，这在增加算法的多样性的同时很好地保持了算法的稳定性。通过分析上述列举的改进权重策略，式（7）所示的策略更有利于并提高算法的开发能力和探索能力，使算法性能得到有效提升。其中，ωmax和ωmin分别是权重系数的最大值和最小值，t为迭代次数，Tmax为最大迭代次数，fmin、favg为当前所有蝙蝠个体的最小目标函数值和平均目标函数值。

参考文献[34-36]提出的改进权重变化曲线分别如图1～3所示。从图中可得取值为简单线性递减取值为恒定值0.9（以测试函数Sphere为例，fmin=4.259E-07，favg=6.179E-07），这样的权重取值失去了动态变化的性质；取值为随机数，为了更加直观观察权重取值情况，图中给出了以迭代次数t=20为例的权重取值情况，可以看出其取值非常随机，在算法迭代后期需要较小的权重系数以增强蝙蝠个体开发能力时，这种随机取值将大大降低算法的稳定性。

图1 权重取值图

图2 权重取值图

图3 权重取值图

本文提出的三种不同衰减形态的权重系数的动态变化曲线如图4所示。

图4 三种不同动态时变的权重取值图

本文提出的惯性权重ω1的衰减状态是简单的一阶函数，ω2是二次函数，ω3是指数函数。根据提出的这三种不同的动态变化的权重系数，为基本BA算法提供了时变的惯性权重学习机制，改进了算法的速度更新公式。这三种方案分别如下所示：

从式（8）可以看到权重系数以当前的迭代次数作为自变量，随着迭代次数的增加不断变化，并且表现出简单的线性衰减形态。

从式（9）可以看出，权重系数的衰减形态是相较于ω1稍微复杂一些的二次函数的形式，迭代次数依旧是自变量，同时可以观察得到这种衰减形态的动态权重系数衰减后的最小值仍远大于ω1。

从式（10）可以得出权重系数ω3的衰减形态是指数函数形式，它的衰减速率比ω1的衰减速率慢得多，并且它最终的值接近ω2。

3.2 数值仿真实验

算法的收敛曲线直接反映了算法的收敛速度，是衡量算法性能的重要指标。为了验证本文所提出的3种不同的时变权重系数学习机制对基本算法的效果，选择了6个经典的标准测试函数进行数值仿真测试，并将其分别与基本BA算法进行了比较，所选测试函数如表1所示。BA算法中涉及的参数很少，在算法求解过程中所用到的参数的取值目前还没有确定的理论基础，因此本文中选择的参数值同其他文献一样主要是根据重复实验获得的经验值确定的。其中，ωmax=0.9,ωmin=0.4,Tmax=1 000。

在仿真数值实验中，规定了算法终止条件，即当算法所搜索到的实际最优值与理论最优值的相对误差如果小于1%，则认为是成功找到了最优解，寻优结束，每种算法独立运行30次，对比实验结果如图5所示。

表1 仿真测试函数

图5 6种不同测试函数下的收敛对比图

图5 展示了3种不同动态权重系数的改进BA算法和基本BA算法在6个不同经典测试函数下的对比收敛曲线。从收敛对比图中不难发现，基本BA算法在测试函数 f3、f6中不能收敛到最优值，并且收敛速度很差，在迭代次数超过200次时还没有达到最优值。在其余测试函数中基本BA算法虽然能收敛到最优值，但是收敛速度均劣于本文提出的3种改进算法。因此得出3种改进BA算法的性能都比基本算法好，而且在很大程度上优化了BA算法的收敛速度。除此以外，对于不同的仿真测试函数，可以观察分析得出3种时变权重系数方案对算法的收敛性有着不同的影响。有趣的是，通过大量实验发现运用ω1的改进方案的算法性能近似于运用ω2的效果。总体而言，ω3的改进效果大部分都比前两个要好，这一点从测试函数的收敛对比图中也可看出，第3种改进方案在上述6个经典测试函数中均表现最优，且收敛速度最快，在测试函数 f1、f2、f3、f5中迭代次数不足50次时就已收敛到最优值，并且在所有测试中出现拐点的次数都最少。通过大量的测试数据发现当权重系数的值减小到[0.4,0.5]的范围时，算法具有最佳的改进效果。进一步仿真实验表明，如果权重系数继续减少，那么寻优效果将会反弹。在方案3中，动态的权重系数始终在此范围内，综上分析基本得出结论，ω3在这3种不同的改进方法中效果最好。为了进一步证明本文提出算法在收敛精度方面的优越性，统计了式（4）～（6）所示改进BA算法和本文提出的表现最佳的第3个改进方案，这4种算法运行6个测试函数的最差解Worse、最优解Best和平均值Avg，并在数据表格中加粗了精度最高的解，具体实验数据见表2。

在表2寻优精度的对比分析数据中，除了Rastrigin测试函数和Zakharov测试函数外，本文提出的ω3改进方案均获得了最优适应度值，且寻优精度最高。

3.3 运算复杂度分析

与标准BA算法相比，本文提出的IBA增加了随着迭代次数变化的惯性权重，优化了收敛速度和收敛精度。设算法的最大迭代次数为Tmax，算法终止条件阈值（本文中设定为实际最优值与理论最优值的相对误差小于1%）为α，如果在第t次迭代中相对误差小于α时，则停止搜索，否则继续进行寻优迭代，记tend为终止迭代次数。标准BA算法和IBA算法在每一次的迭代过程中蝙蝠个体的数量是等量不变的，记为M；每个蝙蝠个体进行一次迭代所需要的时间设为t∗。设标准BA算法和IBA算法的最终迭代次数分别为t1，t2，则其时间复杂度分别为O(t1tendM)、O(t2tendM)，由此可得两种算法运行时间的差异主要由各自的迭代次数所决定。由3.2节数值仿真实验分析可知，标准BA算法速度向量的系数恒为1，这在算法前期不利于快速搜索整个解空间，在算法后期也不利于局部精确搜索。IBA算法受时变的速度项系数作用，在全局搜索中蝙蝠个体的新位置逐渐向最优解靠近，在相同迭代次数下，IBA算法会比标准BA算法先满足终止迭代条件，提前终止迭代，有t1>t2，因此IBA的运算复杂度低于标准BA。

表2 寻优精度对比分析

接下来，将效果最佳的第三个方案应用于多阈值图像分割中。

4 改进算法在多阈值图像分割中的应用

4.1 最小交叉熵阈值分割

交叉熵概念是由Kullback于1968年提出。F=是同一集合上的两个概率分布。则F和G之间的交叉熵被定义为：I为原始图像，L为灰度值，h(i),i=1,2,…,L是原始图像的直方图。用It表示阈值分割图像，t即为分割图像的阈值，如下所示：

其中：

交叉熵的计算表达式为：

根据以上定义，推导出目标函数的定量表达式为：

使n个阈值[t1,t2,…,tn]来自一组阈值向量，将原始图像的一维直方图分割为n+1个区域，那么多阈值的目标函数即可定义为：

最优的阈值t∗满足：

显然，将阈值的选取转化成了一个优化问题，接下来就将改进后的BA算法应用于多阈值图像分割问题中。

4.2 对比实验及结果

由于图像分割可转化为一类优化问题，而群智能算法作为有效求解优化问题的新型方法，受到众多学者的青睐，有很多文献研究了各个群智能优化算法在图像分割中的有效应用。然而，BA算法在这方面的可参考文献却很少。为了进行比较，将IBA同其他三种算法进行了对比实验，分别是：基本BA算法，改进粒子群优化（IPSO）算法，以及模糊聚类分割算法（FC）。

使用了经典伯克利分割数据库（Berkeley Segmentation Dataset and Benchmark）中分别名为“elephant”“horse”“plane”“pottery”“swan”“bird”“grain”的图像进行对比实验分析。这七个图像的原始图像和灰度图像如图6所示，其直方图展示在图7中。算法的参数设置为：最大迭代次数max_gen=200，种群规模为n=20。对比实验结果如表3所示。

图6 测试图像灰度图

图7 各测试图像的直方图

表3 测试图像的分割结果

从表3中得到了各测试图像在不同算法中的阈值选取情况，同时通过运行时间的对比能够发现IBA算法的分割效率明显高于其他算法。为了进一步说明所选阈值的好坏，参考文献[37]中运用适应度值反映阈值有效性的方法，通过实验给出IBA、BA、IPSO算法在分割实验中各自适应值的情况，如表4所示。

表4 算法最优适应度值对比 10－5

为了验证改进算法的有效性，该实验给出了IBA、BA、IPSO、FC这四种算法对于所选取的测试图像的分割效果图，各算法分割结果分别如图8（a）、（b）、（c）、（d）四组子图所示。从分割效果图的对比结果中不难发现，在对测试图像的分割结果中，本文所提出的IBA的分割效果保留了更多的细节信息，如测试图elephant中大象的面部象牙象鼻轮廓清楚，草地的细节更丰富；测试图pottery中瓶身上的花纹更清晰；测试图horses中马匹细节特征明显更丰富，天空、影子分割效果更好；测试图plane中飞机轮廓和机身上图标、字母细节更清晰；测试图swan中天鹅头部、颈部细节轮廓更丰富；测试图bird中IBA和BA算法分割效果差别不大，但明显比另两种算法效果更佳；测试图grain中IBA算法的分割结果中粮食的细节信息更丰富，并且粮食外围的轮廓信息也更清晰，明显比其他算法更好。

图8 测试图像的分割结果对比

除了视觉上直观感受到的更优的分割效果，为了进一步对比分割效果，采用峰值信噪比PSNR（Peak Signalto-Noise Ratio）来定量分析算法性能。信噪比准则的表达式为：

表5 分割图像的峰值信噪比值 dB

从上述各个实验结果可以看出，本文提出的改进策略——非线性衰减模式的惯性权重，有效地提升了基本BA算法的性能，使得算法在收敛速度和收敛精度方面都获得了较大改进。在蝙蝠个体的速度向量上添加的惯性权重是由种群迭代次数t来决定，这保证了每一代内蝙蝠种群的惯性权重保持一致，在增加算法的多样性的同时很好地保持了算法的稳定性。从前文中权重的寻优曲线也不难得出，本文改进后的蝙蝠算法在收敛过程中出现的拐点次数最少，这说明改进后的蝙蝠算法陷入局部极值的次数更少，有效提升了基本算法跳出局部极值的能力；同时，相较于标准BA算法的速度向量系数恒为1，恒定的速度项系数降低了蝙蝠个体的灵活性，不利于跳出局部极值。图像分割问题往往是一类复杂的优化问题，分割的结果很容易错过最优阈值，本文改进的IBA算法则很好地解决了这个问题，因此在图像分割实验中，不论是测试图像的分割结果还是分割图像的峰值信噪比都能反映出IBA改进了图像分割算法的精度及效果。

5 总结与展望

群智能优化算法——BA算法已被成功应用于各类优化问题的求解中，但在数字图像分割中却少有文献探究。本文提出了一种基于时变权重系数的IBA算法，并通过数值仿真实验验证了该改进算法的有效性。此外，将改进的算法应用于多阈值图像分割的研究中，选取Berkeley图像分割数据集中的经典测试图像，使用最小交叉熵方法将多阈值分割转化为多目标优化问题，用IBA算法进行求解，从而获得了良好的分割效果。一系列的对比实验结果表明这是一种非常有效和实用的快速分割算法。在接下来的工作中，将在算法的理论方面做进一步的研究，并尝试将该算法应用于动态视频分割。