2024年4月17日发(作者：富士施乐打印机官网驱动下载)

基于改进CS算法的二维Ostu快速图像分割

高宏进;王力;龚维印;杨幸

【摘 要】For the problems of long computing time,low efficiency and easy

falling into local optimum with two-dimensional Ostu image segmentation

method based on cuckoo search algorithm,the modified fast two-

dimensional Ostu image segmentation method based on cuckoo search

algorithm is proposed. By introducing a hybrid-dimension updating

strategy in combination of dimension updating with global updating, the

cuckoo search algorithm is modified. With the adjustable normal

distribution of variance for whole neighborhood search of the

distinguishable step size, the search precision and efficiency of the

algorithm is improved, and the problem of low efficiency for two-

dimensional Ostu image segmentation solved. Experimental results

indicate that, compared with the exhaustive method and cuckoo algorithm,

the modified algorithm has the highest image segmentation efficiency and

the best effect.%针对应用布谷鸟搜索算法进行二维Ostu分割时计算时间长、效

率低、易陷入局部最优的问题,提出了基于改进布谷鸟搜索算法的二维Ostu快速

图像分割方法.通过引入逐维更新与整体更新相结合的混合维度更新策略,对布谷鸟

搜索算法进行修正,以方差可调的正态分布进行步长有区分的整体邻域搜索,提高了

算法的搜索精度与效率,解决了二维Ostu图像分割效率低的问题.实验结果表明,与

穷举法、布谷鸟算法相比,改进算法图像分割效率最高,效果最好.

【期刊名称】《通信技术》

【年(卷),期】2017(050)012

【总页数】6页(P2698-2703)

【关键词】图像分割;二维Ostu;混合维度更新;布谷鸟搜索算法

【作 者】高宏进;王力;龚维印;杨幸

【作者单位】贵州大学 大数据与信息工程学院,贵州 贵阳 550025;贵州大学 大数

据与信息工程学院,贵州 贵阳 550025;贵州大学 大数据与信息工程学院,贵州 贵阳

550025;贵州大学 大数据与信息工程学院,贵州 贵阳 550025

【正文语种】中 文

【中图分类】TP391.41

图像分割是图像处理最基本的技术之一，为图像的后续处理提供检验依据。随着科

技的快速发展，许多基于阈值的图像分割方法被不断提出，其中最大类间方差法

（Ostu）由日本学者大津提出[1]。该方法无需经过人工设定和先验知识便可自动

选取阈值，具有分割效果好、速度快等特点[2]，但传统一维Ostu法对于噪声十

分敏感[3]，灰度直方图易形成波峰波谷分布不明显，从而导致分割阈值有误。刘

健庄根据此问题提出二维Ostu法[4]，根据图像的灰度级和其邻域平均灰度级选

取阈值，提高了算法的抗噪能力，但也存在计算效率低的问题。

布谷鸟搜索算法（Cuckoo Search，CS）是由英国学者XIN-SheYANG和DEB

Suash于2009年提出的一种新型自然元启发式算法[5]。该算法的思想是基于布

谷鸟的巢寄生行为和鸟类的Lévy飞行随机游走策略寻求最优解[5-6]。该算法因其

简单有效，广泛应用于各个领域[7-8]。然而，CS算法作为一种新颖的仿真算法

[9]，在实际应用中仍存在后期收敛速度慢、易陷入局部最优的问题[10]。本文通

过引入逐维更新与整体更新相结合的混合维度更新策略对CS算法进行改进，并应

用在二维Ostu法中对图像进行分割。

设图像的灰度级和邻域平均灰度级L，则像素的灰度值i和该像素的邻域平均灰度

值j构成二元数组(i, j)，fij为其出现的频数，则相应的联合密度Pi,j 定义如下 [4]：

式中N为图像总像素点数。

根据图1，(s,t)是选取的阈值点，对角线上的区域C0和C1对应于背景和目标，

远离对角线的区域C2和C3对应于边缘和噪声。在二维Ostu法中，假设区域C2

和C3的概率之和近似为0。背景和目标出现的概率分别定义为[11]：

背景和目标对应的均值定义为：

二维直方图上总的均值定义为：

根据区域C2和C3的概率之和近似为0的假设，可以得到：

类间的离散度矩阵定义为：

类间的离散度测度定义为SB的迹，即：

最佳阈值(s0,t0)由式（10）确定：

在确定最佳分割阈值后，定义：

以此完成图像分割。

2.1 基本的CS算法

XIN-She YANG和DEB Suash在提出CS算法时，基于以下3条理想化假设[12]：

（1）每只布谷鸟每次随机选择一个巢并产一个卵；

（2）适应度最高的巢保留至下一代；

（3）鸟巢数量不变，按照概pa∈[0,1]抛弃鸟巢。

基于以上三条假设，CS算法的寻优过程如下：

（1）初始化种群；

（2）采用Lévy飞行搜索模式更新鸟巢位置，保留较优的鸟巢位置，更新公式如

下：

式中，xk+1,i表示第i个鸟巢在第k+1代的位置，α为步长控制向量，⊕表示点乘，

Levy(λ)表示莱维随机搜索路径。

（3）按照随机概率pa抛弃鸟巢，若被抛弃则重新构建相同数量鸟巢，更新公式

如下：

式中，γ是缩放因子，是（0，1）间的随机数，xk,j、xk,e则表示第k代的两个随

机鸟巢。

2.2 改进的CS算法

2.2.1 混合维度更新评价策略

CS算法有两种鸟巢更新模式，即符合Lévy飞行的随机游走模式和偏好随机游走

模式。但是，这两种模式都是整体更新模式，在二维尤其是多维空间搜索中存在某

些解的进化维因整体更新而退化的问题，从而使各维难以同时达到最优，降低了算

法的收敛速度和搜索精度[13]。

为克服此缺陷，本文在CS算法第二步即Lévy飞行随机游走更新过程中借鉴逐维

更新评价策略，提出了一种新的混合维度更新评价策略。由于完全应用逐维更新模

式会大量浪费计算资源，降低计算速度，故本文提出按照一定概率pb进行逐维更

新，更新公式如式（14）所示：

式中，xk+1,i,j表示第j个种群第i个鸟巢在第k+1代的位置，α1为步长控制向

量

按照pc（pc=1-pd）进行整体更新，并设置步长向量α2，如式（15）所示：

由此更好地整合了逐维更新和整体更新评价策略，达到算法计算速度与精度的有效

统一。假设种群规模为n，搜索空间维度为m，则此步的时间复杂度为

o(n)=n×(Pb(m-1)-1)。相较于逐维搜索o(n)=n×m，时间复杂度大大降低。

2.2.2 邻域搜索策略

在CS算法第三步以随机概率pa抛弃鸟巢后，在多维空间的求解过程中，对不同

维度采用相同的邻域搜索范围，不仅造成搜索资源浪费，而且无法有效提高搜索精

度与速度。本文以方差可调的正态分布对各维鸟巢进行步长有区分的整体邻域搜索，

以xk,best-xk,e引导邻域搜索方向，其中xk,best为第k代最优解，xk,e为第k

代的一个随机解。

式中γ为比例系数，⊕为点对点乘法，X为邻域搜索半径，其维数应与种群规模相

同，μ一般取0，δ 2一般取 5。

2.2.3 改进的CS算法流程

图2为改进CS算法流程图。

本文以二维Ostu函数作为改进CS算法的适应度函数，按照二维Ostu相关理论

进行二维Ostu图像分割，所求最大二维Ostu函数值所对应的阈值即为最佳阈值。

算法步骤如下：

（1）初始化鸟巢数目n，空间搜索维度m，发现概率pa，逐维更新概率pb，步

长控制向量α1和α2，比例系数γ，输入图像，设置适应度函数；

（2）计算每个鸟巢适应度；

（3）应用式（14）、式（15）进行混合维度更新；

（4）按照概率pa抛弃鸟巢，按照邻域搜索策略，以式（17）更新鸟巢位置；

（5）判断是否符合终止条件，符合则进行下一步，否则返回步骤（2）；

（6）输出最佳分割阈值。

为验证本文所提算法在图像分割上的优越性，本文将Lena、Barbara、Pepper和

Pens作为实验对象进行图像分割实验。测试平台为Matlab2016a、windows7，

处理器Intel Core i5-3470，主频3.20 GHz，内存4G。

3.1 对复杂图像的分割

采用本文算法对四幅图像进行二维Ostu图像分割，如图3（a）所示。经多次实

验验证，将相关参数设置如下：种群规模n=20，最大迭代次数Negn=200，鸟

巢抛弃概率pa=0.25，混合维度分配概率pb=0.75，各图像分割结果如图3（b）

所示，从左至右分别为Lena、Barbara、Pepper、Pens图。

3.2 对比实验

为验证本文所提算法的优越性，特选取Rice和Cornfield图像作为实验对象，分

别用穷举法、CS算法和本文算法进行二维Ostu图像分割。穷举法即采用穷举的

搜索模式寻找最优分割阈值，分割效果及分割数据如表1、表2所示。统一设定种

群规模n=20，最大迭代次数Negn=100。

3.2.1 图像分割效果对比

从表1可以看出，对于Rice图像，CS算法丢失了很多边缘信息，造成分割对象

不完整；而本文算法得到的边缘清晰目标完整，分割效果更接近于穷举法。对于

Cornfield图像，CS算法分割阈值选择不合理、有噪声点分布、且部分细节丢失，

而本文算法则完好保留了图像的整体与细节信息，与穷举法分割效果更相近。

3.2.2 图像分割数据对比

从表2可以看出：在最佳阈值选取上，CS算法已经相当接近穷举法结果，而本文

算法和穷举法结果一致；在收敛代数上，本文算法低于CS算法10代左右；在计

算时间上，CS算法和本文算法都大大低于穷举法，计算速度提高270倍左右；本

文算法相较于CS算法，成功率提高50%左右。总之，在相同情况下，本文算法

分割速度尤其是分割效果是都较CS算法获得了大幅提升。

3.2.3 算法收敛性能

为了进一步分析本算法对图像进行二维Ostu阈值分割的收敛性能，图4给出了最

佳阈值(s,t)的变化趋势。可以明显看出，本算法在寻找最佳阈值的过程中，s、t以

不同变化趋势趋近于最优解，并在35代左右收敛。图5给出了本算法和CS算法

最优函数值的收敛趋势。可以明显看出，迭代前期本文算法的下降速度明显高于

CS算法，迭代后期本文算法寻找到最优解并稳定的时间也早于CS算法，收敛速

度提高50%左右。

针对二维Ostu方法分割复杂图像存在计算量大、计算时间长的问题，本文引入

CS算法，并针对CS算法准确率低、收敛速度慢的问题进行了改进。首先本文对

二维Ostu方法进行公式推导并进行分析，然后针对CS算法的问题进行修正，提

出了基于改进CS算法的二维Ostu快速图像分割方法，最后应用典型图像，分别

对本文方法、穷举法和CS算法进行验证，并将分割效果、分割数据及算法收敛性

能进行比较。实验表明：本文方法的分割效果优于CS算法，与穷举法相同；收敛

速度与CS算法相近，较穷举法提高约270倍；收敛成功率较CS算法提高约

50%，且在多种实验条件下均能保证较高成功率。因此，本文所提基于改进CS算

法的二维Ostu快速图像分割方法能够实现对复杂图像更加快速、准确、有效的分

割。

【相关文献】

[1] Smith P,Reid D B,Environment C,et al.A Tlreshold Selection Method from Gray-Level

Histograms[J].Systems Man & Cybernetics,1979,9(01):62-66.

[2] 罗丽霞.基于遗传算法的Ostu图像分割方法[J].河北北方学院学报:自然科学版,2014(06):29-

Image Segmentation Method based on Genetic Algorithm[J].Journal of

Hebei North University(Natural Science Edition),2014(06):29-33.

[3] 金元郁,张洪波,冯宇.基于遗传算法的二维双阈值Otsu图像分割算法[J].电子科

技,2009,22(11): Yuan-yu,ZHANG Hong-Bo,FENG -Dimensional Two-Otsu

Threshold Image Segmentation Algorithm Based on the Genetic Algorithm[J].Electronic

Technology,2009,22(11):35-33.

[4] 刘健庄,栗文青.灰度图象的二维Otsu自动阈值分割法[J].自动化学报,1993(01):

Jian-zhuang,LI Automatic Thresholding of Gray-Level Pictures Via Two-

Dimensional Ostu Method[J].Journal of Automation,1993(01):101-105.

[5] Yang X S,Deb Search via Levy Flights[J].Mathematics,2010:210-214.

[6] 黄继达.布谷鸟算法的改进及其应用研究[D].武汉:华中科技大学, ch

Cuckoo Search and Its Application[D].Wuhan:Huazhong University of Science and

Technology,2014.

[7] Senthilnath J,Das V,Omkar S N,et ring Using Levy Flight Cuckoo

Search[M].Advances in Intelligent Systems and Computing,2013:65-75.

[8] Kumar A,Chakarverty Optimization for Reliable Embedded System Using

Cuckoo Search[C].International Conference on Electronics Computer Technology

IEEE,2011:264-268.

[9] Yang X S,Deb ering Optimisation by Cuckoo Search[J].International Journal of

Mathematical Modelling & Numerical Optimisation,2010,1(04):330-343.

[10] 李瑞芳.基于改进布谷鸟搜索算法的图像分割[J].电子科技,2016,29(05): Rui-

Image Segmentation Based on Modified Cuckoo Search[J].Electronic

Technology,2016,29(05):105-107.

[11] 兰少峰,刘升.布谷鸟搜索算法研究综述[J].计算机工程与设计,2015(04): Shao-

feng,LIU ew of Research on Cuckoo Search Algorithm[J].Computer

Engineering and Design,2015(04):1063-1067.

[12] 薛益鸽.改进的布谷鸟搜索算法及其应用研究[D].重庆:西南大学, ch on

Improved Cuckoo Search Algorithm and Its Application[D].Chongqing:Southwest

University,2015.

[13] 王李进,尹义龙,钟一文.逐维改进的布谷鸟搜索算法[J].软件学报,2013(11):

Li-jin,YI Yi-long,ZHONG Search Algorithm with Dimension by Dimension

Improvement[J].Journal of Software,2013(11):2687-2698.