改进分数阶达尔文粒子群的多Renyi熵图像分割算法

袁玉珠

(福建工程学院交通运输学院，福建 福州 350118)

随着空间观测技术的不断发展，高分辨率遥感图像已经广泛应用于地质勘察、城市规划、灾害检测等领域[1]。遥感图像分割是提取遥感信息的前提和基础。近几十年图像分割技术的发展，产生了大量遥感图像的分割方法。如基于阈值的分割[2-3]、基于边缘检测的分割[4-5]、基于模糊聚类的分割[6-7]、基于神经网络的分割[8]、基于深度学习的分割[9-10]、基于马尔科夫随机场分割[11]等。其中阈值分割是一种性能较好且应用广泛的图像分割算法，阈值分割的关键是以一定的准则迅速找到最优阈值，实现图像准确分割。20世纪80年代初，学者们开始将信息论中的熵引入阈值分割中，其中以最大Shannon熵求取阈值为最常用方法，但因其未考虑图像中目标与背景的相互关系，对背景目标相近图像分割时精度不是很高。Renyi熵是Shannon熵的广义形式，与Shannon熵相比，其引入了可调节的参数α，使得对信息的度量更具灵活性和一般性。

文献[12]提出了基于二维Renyi熵的阈值分割方法，取得了较好的分割效果；文献[13]提出了基于分解的二维Renyi熵值分割方法，在选取合适的参数α下，取得了不错的分割效果；文献[14]利用粒子群优化算法选取最优Renyi熵值，利用最优Renyi熵阈值分割图像；文献[15]提出了分解二维Renyi熵图像阈值分割方法，并采用快速递推公式降低阈值选取准则函数的计算复杂度；文献[16]利用自适应人工鱼群搜索方法提出了一种参数α的自适应选取方法，在分割红外图像试验中获得了理想的分割效果。国内外学者针对Renyi熵的阈值分割研究较少，特别对可调节参数α的选取多为手动，Renyi熵阈值分割的计算复杂度较高。

基于此，本文提出一种新的阈值分割算法，算法利用自适应加速系数和变异控制机制动态调整分数阶次α系数以加强算法跳出局部最优的能力，并将改进的分数阶达尔文粒子群算法应用于二维Renyi多阈值熵的搜索，将搜索到的最优多阈值进行图像分割，获得了较好的结果。

1 基于Renyi熵的图像分割

1.1 二维Renyi熵单阈值分割

设灰度级L-1的遥感图像P大小为M×N，f(x,y)表示遥感图像P在(x,y)处的灰度值。像素灰度级i与邻域平均灰度级j组成的二元组(i,j)出现的频数设为Numi,j，p(i,j)表示二值灰度概率密度

(1)

p(i,j)构成了遥感图像P的二维直方图如图1所示。

设阈值(s,t)将遥感图像分成4个矩形区域，图像的亮像素为背景区(A区)、图像的暗像素为目标区(B区)、C区和D区表示边界和噪声[17],图像二维熵过程中通常忽略两区，故假定PC+PD≈0，背景区和目标区灰度级所对应的概率分别为PA(s,t)和PB(s,t)

(2)

参数为α的二维Renyi熵为

(3)

二维Renyi目标熵和背景熵为

(4)

(5)

(6)

1.2 二维Renyi熵多阈值分割

传统的二维直方图阈值分割只考虑待测图像的背景与目标区域，忽略了图像中的边缘和噪声信息。虽然图像中的边缘和噪声信息分量较少，但直接忽略不仅不能真实地反映待测图像的像素分布，还会导致图像分割不够精确。

由于遥感图像中目标较为隐蔽，目标与背景边缘模糊不清，利用单阈值分割往往难以将目标和背景分割精确，本文改进阈值划分形式，并将单阈值分割扩展到多阈值分割，利用n-1个灰度级对图像P进行多阈值划分，改进二维多阈值直方图划分如图2所示。

(7)

二维Renyi总熵为

Hα((t1,s1),(t2,s2),…,(tn-1,sn-1))=

(8)

(9)

二维Renyi熵多阈值选取的计算过程较为复杂，计算量也颇大，为了避免中间变量的重复计算，提高算法的速度，很多文献中都会将二维Renyi熵多阈值选取分解为多个一维Renyi熵阈值相加的形式。本文在此不再赘述，二维Renyi熵多阈值分解过程参见文献[15]。

二维Renyi熵多阈值分割就是根据利用最优阈值组合将待分割图像分割成各类的总熵值最大。为了缩短寻找最优阈值的时间，本文利用改进的分数阶达尔文粒子群算法对二维Renyi熵最优阈值进行搜索。

2 粒子群优化算法及其衍化

粒子群优化算法(partical swarm optimization,PSO)是一种群体智能全局寻优的算法[18]。该智能优化算法在优化组合、多目标寻优、聚类分析等领域应用广泛且效果突出[19-21],与其他智能优化算法一样，粒子群优化算法也存在易陷入局部最优、搜索精度不高、后期收敛慢等问题。针对这些问题，国内外学者进行了深入的研究，提出了多种改进算法。文献[22]将达尔文进化理论引入粒子群优化算法中，提出了一种达尔文粒子群优化算法(Darwinian partical swarm optimization，DPSO)；文献[23]将分数阶微分理论引入粒子群优化算法中，提出了分数阶粒子优化算法(fractional order partical swarm optimization，FOPSO),通过重排原始速度修正速度导数，以便控制优化算法的收敛速度，取得了不错的效果；受文献[23]的启发，学者Micael将分数阶微分和达尔文进化理论相结合，集中二者的优点应用于粒子群优化算法中，提出了分数阶达尔文粒子群算法(fractional order Darwinian partical swarm optimization，FODPSO)，试验结果表明与其他智能优化算法相比，该算法通过分数阶次α来控制计算精度与收敛速度，该算法由于过度依赖分数阶次α，容易造成局部最优[24]。针对FODPSO依赖分数阶次α调节算法的弊端，本文利用自适应加速系数和随机扰动控制机制动态调整分数阶次α系数以实现精确计算和快速收敛。

在一个M维目标空间中，Nnum个粒子组成群落，每个粒子的速度和位置更新公式

(10)

(11)

第i个粒子位置向量为Xi=(xi1,xi2,…,xiD)，速度向量为Vi=(vi1,vi2,…,viD)，第i个粒子经历过的位置中最优位置Wi=(wi1,wi2,…,wiD)，整个粒子群最优位置Wg=(wg1,wg2,…,wgD)。式(10)中，ω表示惯性系数；c1、c2表示加速系数；R1d、R2d为[0,1]间的随机数；wid表示粒子个体最优值；wgd表示粒子群整体最优值。

DPSO将自然选择理论引入算法中，对于能找到较好适应值的粒子群，延长其生命，对于无法找到较好适应值的粒子群，寿命就会缩短，同时遍历粒子群，删除性能较差的粒子。设置粒子搜索计数器SC用于追踪粒子群适应值没有改变次数。创建新粒子群时，粒子群内所有搜索计数器SC=0，在粒子群适应度没有提高时，其中的粒子被删除后，该粒子群的搜索计数器不置为0，而是根据式(12)将其设置为与最大计数值SCmax相近的值

(12)

式中，Nkill表示粒子群适应值没变化期间被删除的粒子数。若一个粒子群中所有粒子被删除，并且当前粒子群数没有超过种群设置数，则创建新粒子群的概率为

p=r/Nunm

(13)

式中，r为[0,1]间随机数；Nunm表示种群粒子数。文献[24]给出了分数阶次α调整公式

(14)

通过大量试验可知分数阶次α在[0.5,0.8]之间时，FODPSO算法可取的较快的收敛速度。但是通过式(14)可以看出：随着迭代次数的加大，分数阶次α会线性减小，这势必会使粒子群陷入局部最优和低速收敛。本文通过改变分数阶次α的调整方式和陷入局部最优的跳出方式，对FODPSO进行改进。

3 改进分数阶达尔文粒子群算法

3.1 基于进化信息调整分数阶次α

(15)

(16)

(17)

基于粒子进化因子fev∈[0,1]，利用高斯图函数得出分数阶次α的调整公式

(18)

通过式(18)可知，分数阶次α的调整不再依赖迭代次数，而是依据粒子自身的进化信息，这可避免算法因分数阶次α线性减小而引起的局部最优和收敛缓慢。

设惯性系数ω为1，根据分数阶微分方程的格林瓦德-列特尼科夫(G-L)定义，粒子速度更新策略变为

(19)

粒子的位置更新依据式(11)进行，其中加速系数满足3≤(c1+c2)≤4。

3.2 基于Levy飞行特征的局部最优

当粒子群陷入局部最优时，算法极易出现过早收敛，为了克服寻优算法早熟收敛，及时跳出局部最优，本文将Levy飞行特性引入改进的FODPSO中，利用Levy飞行特性扩展搜索空间，根据局部最优概率因子popt对算法取得的局部最优wg进行位置扰动。

定义局部最优概率因子popt

(20)

wgd=wgd(1+levy(ξ)tanh(fev))

(21)

式中,Levy(ξ)是随机搜索路径;步长的大小通过levy分布随机数产生且1≤ξ≤3，0≤fev≤1，0≤tanh()≤1。

4 仿真试验与对比分析

4.1 最优阈值寻优流程

(1) 初始化粒子群，随机生成粒子速度Vi和位置Xi，确定种群个数Nnum，目标空间维数M，最大迭代次数Tmax，加速系数c1、c2等参数。

(2) 对粒子群中每个粒子进行适应度评估，将粒子个体的最优值wid设为当前位置，全局最优值wgd设为群体最优粒子位置。

(3) 开始迭代，迭代次数加1。

(4) 计算每个粒子对应的Renyi熵值，找出最优粒子位置；并根据式(15)、式(16)、式(17)和式(18)计算粒子平均进化状态信息。

(5) 根据式(21)、式(10)、式(11)更新粒子的位置和速度。

(6) 更新粒子适应度值，与当前个体极值进行对比。若粒子当前适应度值优于个体极值，将wid设为该粒子位置；若所有粒子中个体极值最优者优于全局极值，则将该粒子的位置设为wgd。

(7) 对比粒子群的适应度，对粒子群适应度变优的增加其寿命，对粒子群适应度变差的删除粒子，并按式(12)重置搜索计数器。若创建新的粒子群，根据式(14)计算概率；否则，执行下一步骤。

(8) 根据式(22)计算局部最优概率因子popt，若局部最优概率因子popt大于随机产生的随机数，则按式(23)进行Levy飞行扰动;否则，执行下一步骤。

(9) 判断算法是否达到收敛或达到最大迭代次数，若是，执行下一步骤;否则，执行步骤(3)。

(10) 输出全局最优值，算法结束。

为了验证本文改进算法的优越性，从两个方面进行对比分析：①利用4种测试函数对比寻优效果；②通过分割遥感图像对比分割效果。编程平台为Windows 7 Microsoft VS 2013和OpenCV 3.0，仿真平台为Matlab 2014a,CPU为i5-4460T@2.7 GHz,RAM为4 GB。

4.2 寻优效果对比分析

将本文算法、文献[23](FOPSO)和文献[24](FODPSO)在表1所示的4个标准函数上[24]对比寻优效果。3种粒子群优化算法的参数设置见表2。

表1 4个标准函数

种群规模设为50，最大迭代次数为1000次。3种粒子群优化算法运行100次取平均。

表2 参数设置

图3为3种智能优化算法对表1中4个标准函数的寻优收敛曲线。

由图3各算法的寻优曲线可以看出：FOPSO和FODPSO对Rastrigin标准函数的寻优效果一般，过早陷入了局部最优；随着迭代次数的增加，FOPSO和FODPSO在多峰Ackley函数、单峰Sphere、Rosenbrock函数上，收敛速度缓慢，寻优精度不精。而本文改进算法无论是对Sphere、Rosenbrock 2种单峰函数还是对Rastrigin、Ackley多峰函数都能在若干次迭代后迅速从局部最优中跳出，并快速搜寻到最优值，扩大了对最优值的全局搜索能力。

4.3 图像分割效果对比分析

利用本文改进的分割算法、文献[25]、文献[26]等3种算法对选取的2幅资源三号卫星的遥感图像进行分割试验。使用概率Rand指数、信息变化指数、全局一致程度误差等3种传统图像分割评价指标[27]定量对比分割效果：

(1) 概率Rand指数(probabilistic rand index，PRI)是统计分割结果与手动分割结果间像素一致性的比例，比例越大分割精度越高。

(2) 信息变化指数(variation of information，VOI)是衡量分割结果与标准分割间的平均条件熵,取值越小分割效果越好。

(3) 全局一致程度误差(global consistency error，GCE)度量分割结果被看作另一个分割子集程度，取值越小分割效果越好。丘陵遥感图像分割结果如图4所示。

图4所示的丘陵遥感图像中，包括沟壑、绿植、道路等内容，轮廓较为清晰，边界较为分明。从分割结果可以看出：文献[26]分割算法和本文分割算法均能得到准确的轮廓，边缘清晰，在小尺度结构区域都有较高的识别质量，但文献[26]在分割细节上有待提高；文献[25]分割的边缘模糊，纹理不够清晰，局部区域偏亮或者偏暗，存在一定的虚警，总体分割效果较差。

图5所示的港口遥感图像中包含道路、大海、油罐、船只等内容，图像边界分明，细节突出。3种分割算法均能分割得到大致轮廓，分割边缘都较为清晰，但文献[25]和文献[26]在细节分割上不够精确，都没有有效分割出船只等信息。本文算法对细节的分割较为准确，这是由于本文利用优化算法得到最优多阈值分割的效果体现。3种分割算法的定量评价指标见表3。

表3 3种分割算法的定量评价

从表3数据可以看出，本文分割算法在PRI、VOI、GCE 3种定量标准上都优于其他2种分割算法。在PRI指标上，本文分割算法提升了至少7.27%、在VOI指标上降低了至少6.5%、在GCE指标上降低了至少10.4%。说明本文分割算法对遥感图像的分割结果具有像素一致性，位置偏离误差小，细节分割准确到位，并且分割后信息丢失量最少。

5 结 语

本文提出了一种基于改进FODPSO的二维Renyi熵多阈值遥感图像分割算法，利用进化信息和随机扰动控制机制动态调整分数阶次α系数，实现了算法精确计算和快速收敛，引入Levy飞行特征加强FODPSO跳出局部最优能力，将改进的优化算法应用于二维Renyi熵多阈值的最优搜索中，最终使用最优阈值对试验遥感图像进行了分割。结果表明，本文提出的分割算法不仅能对复杂图像进行准确地分割，还在各项定量评价指标上均比其他2种分割算法优越。