基于改进的GSA彩色图像分割方法研究

张 辞，马 丽

(中国地质大学(武汉)机械与电子信息学院，湖北武汉430074)

基于改进的GSA彩色图像分割方法研究

张 辞，马 丽

(中国地质大学(武汉)机械与电子信息学院，湖北武汉430074)

提出了一种基于改进的GSA(Gravitational Search Algorithm)无监督彩色图像分割方法。在GSA的基础上，采用了改进的欧氏距离，引入了像素分离过程，并给出了像素分离条件的最小速度。首先像素点的移动采用改进的欧氏距离进行GSA搜索;然后进行区域生长，合并相同性质的像素;最后达到一定速率的部分像素点从聚类中分离出来。实验结果表明，与传统C均值聚类算法和GSA算法相比，该方法在复杂场景图像中具有更好的分割效果。

万有引力搜索算法;无监督;图像分割;区域生长

图像分割经过40多年的研究，仍是图像处理中的一个难点问题［1］。其主要目的是把一幅图像划分成为若干互不重叠、具有相同性质的区域。目前图像分割已被广泛应用于图像检索、模式识别和机器人视觉等方面［2］。

常见的图像分割方法有:1)基于阈值的方法。例如直方图阈值法、分水岭分割等。但是它们计算量较大，运行时间较长，有时存在过分割的情况。2)基于聚类分割的方法。例如C均值聚类(CM)、模糊C均值聚类(FCM)等。受自然现象和生物学的启发，目前启发式聚类算法很受欢迎，蚁群聚类算法已应用于图像分割［3］。但当数据量较大时，速度较慢。3)基于区域的方法。例如区域生长和区域分裂合并。虽然容易实现，但有时造成局部分割不均匀。4)基于边缘的方法。常见算子有Roberts、Prewitt和Sobel等，但分割效果一般要受噪声的影响，并且其自适应分割能力不理想［4］。因此关于图像分割的新算法研究从未停止。

万有引力搜索算法(Gravitational Search Algorithm，GSA)是2009年由伊朗克曼大学教授Esmat Rashedi提出的一种启发式优化算法，是利用物理学中万有引力和运动定律进行模拟得到的群体智能优化算法［5］。将该算法应用于图像分割的研究中，本文提出一种基于改进的GSA图像分割方法，在原有GSA的基础上，采用了改进的欧氏距离，引入了像素分离过程。通过区域生长和聚类技术，利用像素的颜色、空间特征实现图像分割，并获得了较好效果。

1 万有引力搜索算法

万有引力定律是指任意两个质点通过连心线方向上的力相互吸引［6］。该引力的大小与它们的质量乘积成正比，与它们距离的平方成反比，与两物体的化学本质或物理状态以及中介物质无关。其公式可表示为

式中:Fij表示两个物体之间的引力;Mi和Mj分别为两个物体的质量;G是万有引力常量;r表示两个物体之间的欧氏距离。图1表示了两个物体之间的万有引力。

图1 两个物体之间的万有引力

GSA是受到万有引力定律及运动定律的启发而提出的。主要有以下3个特点:一是不存在初始质点的选取问题;二是初始的样本分布情况基本不影响最终分类结果;三是设定阈值要优于设定类别数目［7］。该算法中，每个质点都有位置、惯性质量、主动引力质量和被动引力质量4个描述特征。随着时间的增加，假设在某一时刻，所有的质点都被质量较大的质点所吸引，那么此时质点的位置就是搜索空间中的最优解。

假设在一个D维搜索空间中存在N个质点。定义第i个质点的位置为

在某时刻t，定义第j个质点对第i个质点的作用力大小为

式中:Maj(t)表示质点j的惯性质量;Mpi(t)表示质点i的惯性质量;ε为一个很小的常量;G(t)表示t时刻的万有引力常数，随着时间的增加而不断减小。具体关系式为

式中:G0为初始值，通常取100;α取20;T表示最大迭代次数;Rij(t)为i与j之间的欧氏距离，即

在GSA中，假设t时刻在第d维上作用在第i个物体上的总作用力等于其他所有质点对它的作用力之和，其大小Fdi(t)为

式中:randj是0～1的随机数。

由牛顿第二定律可得

式中:Mi(t)表示第i个质点的惯性质量。

GSA在每次迭代过程中，可根据式(8)、式(9)来更新质点i的速度和位置，即

式中:randi是0～1的随机数。

质点的惯性质量是根据其适应值的大小来计算的，在GSA中使用以下公式更新质点的惯性质量

式中:fiti(t)表示在t时刻第i个质点的适应值;best(t)和worst(t)分别表示最佳和最差的适应值。在求解最小值问题时，best(t)和worst(t)定义为

2 基于改进的GSA彩色图像分割方法

基于改进的GSA无监督彩色图像分割方法主要有移动、合并和分离三个过程。在达到最大迭代次数之前，首先像素点在万有引力的作用下，在属性空间中移动，搜索相同性质的像素点。然后在合并过程中，邻近的区域将被合并成新的区域。最后随着移动速度的增大，像素点将会以一定概率从聚类中分离出来，再被邻近的质点吸收。本文算法的总体流程如图2所示。

图2 基于改进的GSA彩色图像分割方法的流程图

2.1 映射

首先把彩色图像映射到属性空间。本文定义了一个5维的属性空间。前2个参数表示像素点在原始图像中的位置，后3个参数表示RGB值的成分大小。对于任意一个像素点i，上述空间可表示为

式中:N为图像像素总和;x和y代表i的位置;r，g，b是i的彩色成分大小。

2.2 移动

像素点在万有引力的作用下移动搜寻空间。本文在GSA的基础上，针对欧氏距离容易忽略不同属性的差别和属性之间的关联问题，采用一种改进的欧氏距离，即根据每个属性在聚类过程中所起作用的程度不同，给每个属性赋一个与该属性相对应的加权系数。在D维空间中，改进后的欧氏距离计算公式为

式中:hp表示每个属性的加权系数。

首先求出样本空间像素的每个属性的均值

再计算样本空间像素的每个属性的标准差

最后根据GSA搜索算法，像素点i的加速度、速度和位置可表示为

2.3 合并

当质点r和s之间的距离小于预先设定的阈值θ时，这两个质点将合并成一个新的质点q。显然在合并过程中，像素点的数量会随着迭代次数的增加而减少。其位置、质量和速度为

2.4 分离

合并之后，当像素点的速度超过一定速度时会以概率Pe从聚类中分离出来，从而成为新的自由质点，新的像素点在属性空间中又会被最邻近的聚类吸收。在聚类引力场的作用下，像素点达到分离条件的最小速度类比第二宇宙速度，即

像素点i从聚类k分离的概率为

假设像素距离中心距离小于dmin不会分离，而距离中心距离大于dmax将会分离。那么Vemax就是像素点距离中心小于阈值dmin的速度，Vemin则是距离中心大于阈值dmax的速度。Vemax和Vemin可表示为

3 实验结果及分析

实验在Windows系统环境下，使用MATLAB-2010b软件进行仿真。测试图像采用如图3所示的Plane，Peppers，Lena和Baboon等4幅图像，大小均为256×256。实验分别使用CM算法、GSA算法与本文方法对上述图像进行了分割，其中设置参数初始重力常量G0为10，阈值dmax和dmin分别为80和10，阈值θ为80，仿真实验结果如图4所示。

图3 原始图像

除了使用常见的峰值信噪比(Peak Signal-to-Noise Ratio，PSNR)作为评价标准，文献［8］提出了一个评价函数F，即

图4 仿真实验结果

此外，本文还采用一种基于熵和最小描述原则的定量评价函数E来评估分割质量［9-10］。假设图像I分割成C个任意形状的不相邻区域，SI为图像I的大小，Lj(i)为区域j(记作Rj)中的像素数，在I中的亮度值为i，Vj是Rj中所有可能的亮度值的预设值，本文把熵Rj、预计区域熵和图像布局熵分别用H(Rj)，Hr和HI表示

基于熵评估函数E=Hr+HI，其包含了预计区域熵与布局熵。

表1为分别采用CM算法、GSA算法和本文方法的分割结果评价比较，可以看出本文方法求得的峰值信噪比略逊色于CM算法和GSA算法，但求得的评价函数F和熵值E均小于其他两种算法，而且当图像的结构复杂时，本文方法具有一定优势。

表1 分割结果评价比较

4 小结

本文提出了一种基于改进的GSA彩色图像分割方法。该方法在原有GSA的基础上，优化了欧氏距离，引入了像素分离过程，并给出了像素分离时的最小速率。不仅利用像素的颜色、空间特征，而且参数都是预先设置，从而实现了无监督的图像分割。实验结果表明，与传统CM算法和GSA算法相比，当图像的结构复杂时，本文方法具有更佳的分割性能。

［1］黄洋文，王红亮.基于量子粒子群优化算法的图像分割方法［J］.电视技术，2010，34(4):16-18.

［2］纪则轩，潘瑜，陈强.无监督模糊C均值聚类自然图像分割算法［J］.中国图象图形学报，2011，16(5):773-783.

［3］林丽莉，周文晖.多蚁群动态协作优化的道路图像分割算法［J］.中国图象图形学报，2012，17(4):553-559.

［4］庞冬冬，史健芳.基于改进主动轮廓模型的图像分割算法［J］.电视技术，2013，37(1):41-44.

［5］RASHEDIE，NEZAMABADI-POUR H，SARYAZDIS.GSA:a gravitational search algorithm［J］.Information Sciences，2009，179(3): 2232-2248.

［6］王永久.引力理论［M］.北京:科学出版社，2011.

［7］杜隆胤.基于万有引力定律的分类方法研究［J］.计算机应用与软件，2013，30(2):205-207.

［8］TAN K，ISA N.Color image segmentation using histogram thresholdingfuzzy C-means hybrid approach［J］.Pattern Recognition，2011，44(1): 1-15.

［9］ZHANGH，FRITTSJ，GOLDMAN S.An entropy-based objective evaluationmethod for image segmentation［C］//Proc.Conference on Storage and Retrieval Methods and Applications for Multimedia.San Jose，CA:［s.n.］，2003:38-49.

［10］YU Z，OSCAR C，ZOU R.An adapt unsupervised approach toward pixel clustering and color image segmentation［J］.Pattern Recognition，2010 (43):1889-1906.

Color Image Segmentation Research Based on Im proved GSA

ZHANG Ci，MA Li
(Faculty of Mechanical and Electronic Information，China University of Geosciences(Wuhan)，Wuhan 430074，China)

An unsupervised color image segmentationmethod based on improved GSA is proposed in this paper.On the basis of GSA，improved euclidean distance is used，separation process of pixels is introduced and theminimum velocity isgiven.Firstly，pixelsmove by GSA using improved euclidean distance.Secondly，every two objects aremerged to a new object via region growing.Finally，some pixels reachingminimum velocity is separated from their corresponding clusterswith a probability.Comparingwith CM and GSA algorithm，the novelmethod shows a better performance especially in complex scene images.

GSA;unsupervised;image segmentation;region growing

TN911.73

A

�� 雯

2013－11－14

【本文献信息】张辞，马丽.基于改进的GSA彩色图像分割方法研究［J］.电视技术，2014，38(13).

国家自然科学基金项目(61102104)

张 辞(1988—)，硕士生，主研数字图像处理;

马 丽(1982— )，女，博士，硕士生导师，本文通讯作者，主研图像处理与分析、模式识别、计算机视觉等。