应用改进状态转移算法优化多阈值图像分割

周向阳，罗雪梅，王 霄

(贵州大学电气工程学院，贵州 贵阳 550025)

1 引言

图像分割是一项基础又具有挑战性的研究课题，作为图像处理过程的关键环节，其分割的质量影响着图像目标提取、识别的准确程度和后续工作的有效性。阈值分割法因其实现简单且有效而被广泛用于图像分割之中[1-2]。

本文主要研究图像的多阈值分割，通过将传统的OTSU单阈值分割扩展到多阈值分割。OTSU法[3]需要遍历所有像素值来计算最佳阈值，扩展到多阈值后，计算复杂度会呈指数级增加。因此许多学者引入智能优化算法来提高分割算法的效率[4-5]。邢致恺等[6]将樽海鞘群优化算法应用到多阈值图像分割中，并通过引入莱维飞行产生特殊的随机步长，使优化算法获得更优的全局搜索能力和更强的收敛能力。Wei等[7]提出通过惯性权值将布谷鸟搜索算法的步长转为动态参数，提高了算法在求解阈值时全局搜索能力。罗钧等[8]提出一种改进的自适应差分演化算法，在种群初始化时引入混沌映射机制，并与随机分布法所产生的初始化种群竞争，选出较优的个体。在求解图像分割的阈值中，取得了较好的效果。信成涛等[9]提出一种新型果蝇算法优化图像分割阈值，通过前期的高斯采样和后期的震荡搜索，兼顾了算法的全局性和收敛性。H. Jia等[10]在飞蛾扑火优化算法的基础上，提出了一种新颖的自适应惯性权值方案和一种新的阈值启发式算法，可有效应用于图像分割问题。Mozaffari等[11]使用了收敛异构粒子群算法，将粒子分成四个子群来寻找最优的多级阈值，具有较好的收敛性和稳定性。Garima等[12]提出了一种混合差分进化的鲸鱼优化算法，并应用于基于二维直方图的多级图像分割。刘笃晋等[13]改进了人工蜂群算法，对雇佣蜂和跟随蜂各提出一个搜索方程，应用到彩色图像多阈值分割上，具有较好的效果。上述研究表明，将智能优化算法应用到图像多阈值分割中可以取得一定的效果。但是，收敛精度和效率还需进一步提升。

状态转移算法(State Transition Algorithm，STA)是由周晓君等[14]于2012年提出的一种智能型随机性全局优化算法，将全局搜索、局部搜索以及启发式搜索等功能集合于一体，在诸多工程实际优化问题中得到广泛的应用[15]。

本文提出了一种基于改进状态转移算法的多阈值图像分割方法。通过对伸缩算子采用一种方差自适应的正态分布策略，增强了状态转移算法的前期全局性和后期收敛性。此外，提出一种精英解集加权和的邻域中心解更新策略，充分利用了精英解集间的信息实现启发式搜索。在图像多阈值分割实验中，通过对比验证本文所提方法中有着较高的图像分割效率和质量。

2 相关工作

2.1 OTSU多阈值分割方法

OTSU法利用背景和目标的类间方差最大为准则来确定阈值[16]，将它推广到多阈值后则通过最大化不同类之间的差异将整幅图像划分为不同的区域。假设一副图像的大小为M×N，灰度级范围为[0，1，…，L-1]，fi表示灰度级为i时的像素频数，则该像素出现的概率pi为

(1)

设置阈值组合为[t1，t2，…，tk]将图像分为K+1个区域。则每个区域的所占比例wi和平均灰度ui为

(2)

(3)

令ut为图像平均灰度，则此时类间方差表示为

(4)

(5)

OTSU多阈值分割法即取使得σ2(t1，t2，…，tk)最大时对应的阈值[t1，t2，…，tk]为最佳分割阈值[17]。传统的穷举法需计算灰度空间中所有解的组合，总计算量接近O(LK)。因此选择合适的智能优化算法来提高算法效率十分必要。

2.2 基本状态转移算法

状态转移算法设计了旋转、平移、伸缩、坐标四种状态变换算子从当前状态xk出发，来产生候选解邻域[15]。

1) 旋转变换，具有在以α为半径的超球邻域内进行精细搜索的功能，其公式表示如下

(6)

其中α为旋转因子且α> 0；Rr是一个元素取值在[-1，1]之间均匀分布的n×n维矩阵；‖·‖2为向量2-范数或欧氏范数。

2) 平移变换，可实现启发式搜素，避免搜索的盲目性。其本质是比较相邻两个状态的候选解，并沿着候选解更好的方向、以β为最大长度进行搜索，其公式表示如下：

(7)

其中β为平移因子且β> 0；Rt是一个元素取值在[-1，1]之间均匀分布的随机数。

3) 伸缩变换，保证具有一定概率使得候选解形成的领域中包含全局最优解，其公式表示如下

xk+1=xk+γRexk

(8)

其中γ为伸缩因子且γ> 0；Re是一个服从标准正态分布的非零元素取值的随机对角矩阵。

4) 坐标变换，可实现启发式搜索，能增强单一维度的搜索，其公式表示如下

xk+1=xk+δRaxk

(9)

其中δ为坐标因子且δ> 0；Ra是一个服从标准正态分布的非零元素取值的稀疏随机对角矩阵。

状态转移算法以当前最优解为中心，交替轮换使用状态变换算子，产生样本大小为SE的候选解邻域；最优解的选择和更新采用“贪婪准则”。其伪代码如下：

1)[Best，fBest]=[Best0，fBest0]

2)repeat

3)if α< αminthen

4)α=αmax

5)end if

6)[Best，fBest]=expansion(func，Best，SE，β，γ)

7)[Best，fBest]=rotation(func，Best，SE，β，α)

8)[Best，fBest]=axesion(func，Best，SE，β，δ)

9)α=α/ fc

10)until 满足终止条件

其中Best为当前最优解，fBest为对应的目标函数值，初始解Best0由随机产生。在expansion，rotation和axesion函数中，分别实现了伸缩变换、旋转变换和坐标变换，并包括了最优解的产生和更新；此外，在分别使用旋转、伸缩和坐标变换后，都会进行判断是否使用平移变换，其伪代码如下：

1)if newfBest > fBest then

2)[Best，fBest]=translate(Best，newBest，SE，β)

3)end if

其中newBest为当前邻域的最优解，newfBest为对应的目标函数值。translate函数实现了平移变换，并包括了最优解的产生和更新。

3 优化的OSTU多阈值图像分割方法

3.1 状态转移算法改进策略

3.1.1 方差自适应的正态分布

若一个随机变量x服从图1所示概率分布，则有x～N(u，σ2)。当u=0，且σ2=1时，这个分布称为标准正态分布[18]，如图1中曲线s0。

图1 概率密度函数分布图

图1中可以看出，曲线s1所示的分布N(0，2)，整体比较均匀，变化平缓，相比标准正态分布，所包含的范围大，分布更为分散。而曲线s2所示的分布N(0，0.5)，概率峰值较高，变化陡峭，相比标准正态分布，所包含的范围小，分布更为集中。

基本状态转移算法中伸缩变换产生候选解的分布特性是固定不变的。而对于寻优过程而言，迭代前期，候选解分布较分散有利于全局搜索；迭代后期，候选解分布太分散容易使算法收敛过慢，分布集中能提高算法收敛速度。故对伸缩变换，采用一种方差自适应的正态分布策略，将式(8)调整为

(10)

其中u=0，σ2更新公式为

(11)

图2 方差自适应衰减曲线

为了说明该策略的有效性，图3给出了基于当前最优解Best=[0，0]，在σ2=2、1、0.5时，利用伸缩变换产生邻域的示意图，可分别表示方差自适应的正态分布在迭代前期、中期、后期的分布情况。

图3 不同阶段的散点图

图3中σ2=1时也可表示标准正态分布的散点图。根据三种状态的分布特性可表明，该策略有利于伸缩变换在迭代前期，形成的邻域具有更大概率包含全局最优解；在迭代后期有利于算法更好的在精细邻域内仔细搜索，以达到快速收敛。

3.1.2 邻域中心解的更新

在基本状态转移算法中，状态变换算子只会以当前最优解来产生候选解领域。这种搜索方式没有充分利用群体中的有效信息，特别是较优解的信息。而单个最优解所含的信息极少，故有必要通过多个精英解来指导搜索方向，从而提高算法的搜索性能。

为此，采用一种精英解集加权的邻域中心的更新策略。设置精英解集xtop=[xtop1，xtop1，…，xtopn]，则邻域中心的更新公式为

(12)

其中xcenter为状态转移算子产生邻域的中心，基本状态转移算法中xcenter=Best，n为精英解数量。

最优解的选择和更新根据“贪婪准则”，即

(13)

该策略可以充分利用精英解集之间的信息实现启发式搜索，增加了群体间的信息交流，扩大了搜索范围，增强了算法找到全局最优解的概率。同时，算法在总体上，采用“贪婪准则”来保留最优解，保证了算法的收敛。

3.2 多阈值图像分割的实现

本文基于改进状态转移算法优化多阈值图像分割，即利用改进状态转移算法对OTSU多阈值的搜索过程进行求解最优阈值。考虑到求解的是最大值问题，将图像的类间方差式(4)定义为改进状态转移算法的目标函数来评价解的优劣。

改进状态转移算法步骤如下：

2) 当前迭代次数K=1，随机生成SE个初始解，并根据“贪婪准则”产生当前最优解Best，设置初始邻域中心xcenter=Best；

3) 利用伸缩变换以xcenter为中心产生SE个样本，建立当前精英解集xtop，更新当前最优解Best和邻域中心xcenter。如果Best有变动，则以同样机制执行一次平移变换并更新当前最优解Best和邻域中心xcenter；

4) 利用旋转变换替换步骤3)中的伸缩变换，执行同样过程；

5) 利用坐标变换替换步骤3)中的伸缩变换，执行同样过程；

6) 判断是否满足终止条件。若满足，则输出最优解，否则重返步骤3)直至满足终止条件。

图4为多阈值图像分割总体实现流程。

图4 多阈值图像分割实现流程图

4 多阈值图像分割实验结果和分析

4.1 实验设计

本次实验选择一组经典测试图像进行分割研究，为了验证本文方法的有效性，将ISTA和文献[7]的自适应布谷鸟搜索算法(Self-adaptive Cuckoo Search Algorithm，SCS)、文献[9]的新型果蝇算法(Novel Fruit Fly Optimization Algorithm，NORFOA)、文献[12]的混合差分进化的鲸鱼优化算法(Differential Evolution and Whale Opti-mization，DEWO)、文献[14]的基本状态转移算法(State Transition Algorithm，STA)几个经典智能优化算法应用于图像OTSU多阈值分割中并将实验结果进行比对。本次仿真在Matlab R2016a环境下，Intel(R)i5 CPU @2.90GHz，4GB内存，Win10系统的电脑上进行的。

设置初始参数分割阈值的取值范围为[0，255]，阈值个数K=2，3，4，5，种群规模SE=30，最大迭代次数Iter=50。其余主要初始参数设置由表1所示。

表1 各算法初始参数

4.2 实验结果分析

图5中展示了经典测试图像Lena、Airplane、Lake和ISTA处理图像分割后的效果图。可以看出ISTA能有效的应用于图像多阈值分割，且分割后的图像轮廓清晰，层次性较好，随着阈值个数的增加，灰度信息越丰富且与原图的相似度越高。

图5 应用ISTA的分割效果图

表2列出了ISTA和SCS、NORFOA、DEWO、STA对Lena、Airplane、Lake图像求解阈值所对应的目标函数值。目标函数值即分割后图像的类间方差，一般数值越大表明对应的分割阈值越准确，分割效果越好。从表中横向数可以看出，ISTA取得的目标函数值始终最大，相比其它算法，更能保持较好的搜索能力。且在K> 2后，ISTA的优势更加明显。为了更好地说明ISTA和对比算法的收敛性能，以下从迭代曲线和收敛效率两个方面来进行分析。

表2 各算法的目标函数值

4.2.1 迭代曲线分析

图6给出了5种算法对3副图像进行5阈值分割时的迭代曲线图。从图中可以看出，对3幅测试图像，ISTA均能最早搜索到全局最优值附近，说明ISTA相比其它算法具有更好的全局性。且ISTA分别在第31代、27代、29代收敛，不仅在迭代次数上少于其它四种算法，而且所取得的目标函数值也要高于其它算法。

图6 各算法的迭代曲线图

4.2.2 收敛效率分析

表3列出了ISTA和SCS、NORFOA、DEWO、STA达到收敛的所需时间。从表中纵向数据可以看出，随着阈值个数的增加，算法所需时间也明显增加。从横向数据看，是对同一副测试图像进行分割，ISTA所需时间最短。在K=5时，ISTA具有明显优势，处理3副图像的所需时间相比SCS、NORFOA、DEWO、STA平均分别缩短了27.8%、28.1%、24.8%、28.6%。

表3 各算法所需时间/s

4.3 评价指标分析

为了客观的评价图像的分割效果，通过图像分割后的峰值信噪比(PSNR)、结构相似性度量(SSIM)两个指标来对ISTA和各对比算法进行评定对比。

PSNR[19]是根据分割图像与原图像对应像素点灰度值的差异，从统计角度来对分割图像的质量进行评价。PSNR的值越大，说明分割质量越好。PSNR的计算公式如下

(14)

(15)

其中R与I分别表示M×N大小的原图像和分割后的图像。

表5列出了5种算法对3副图像分割后计算出的PSNR值。从表中横向数据可以看出，ISTA算法均能取得最高的PSNR值，并且随着阈值个数K的增加，ISTA的PSNR值要明显高于对比算法。在K=5时，ISTA处理3副图像后的PSNR值相比SCS、NORFOA、DEWO、STA平均分别提高了4.4%、5.4%、2.6%、6.5%。

表4 各算法的PSNR值/dB

表5 各算法的SSIM值

SSIM[20]常用来衡量两幅图像相似度，基于分割图像I和原图像R之间的亮度、对比度和结构三个比较衡量，其公式表示为

(16)

其中μI为分割图像的像素平均值，μR为原图像的像素平均值，σI是分割图像像素的方差，σR是原图像像素的方差，σIR为分割图像和原图像像素的协方差。c1、c2分别取值10-4和9×10-4，以避免除零。SSIM的取值范围[0，1]，数值越大，说明图像分割的性能越好。

表6列出了5种算法对3副图像分割后计算出的SSIM值。从表中纵向数据可以看出，基本上随着分割阈值个数的增加，SSIM值在增大。因此可从数据上表明阈值个数越多，分割图像与原图像越相似。从表中横向数据可以看出，在K=2时，ISTA与对比算法的SSIM值相差不大，说明分割效果基本一致。但随着K值增大，ISTA的SSIM值会明显的高于对比算法。在K=5时，ISTA处理3副图像的SSIM值相比SCS、NORFOA、DEWO、STA平均分别提高了3.1%、3.2%、1.2%、4.7%。

5 结论

为了解决图像分割中阈值个数增加带来的分割效率变低和精度下降的问题，本文研究了通过改进的状态转移算法来确定最优的分割阈值。通过对伸缩变换采用方差自适应正态分布策略，增强了状态转移算法的前期全局性和后期收敛性。并利用精英解集加权和来确定邻域中心，增加了群体之间的交流，利用了精英解集之间的信息实现启发式搜索。进行图像分割实验，在主观效果上，可以表明ISTA能较好的完成图像的有效分割；在目标函数值、运行时间、PSNR、SSIM客观数据上与SCS、NORFOA、DEWO、STA进行了对比。综合结果表明，本文方法能高效、高精度的分割图像且优于对比算法。