基于变尺度进化的多目标图像分割算法

周 苑，周 岩

(河南工程学院 计算机学院，河南 郑州 451191)

基于变尺度进化的多目标图像分割算法

周 苑，周 岩

(河南工程学院 计算机学院，河南 郑州 451191)

针对进化计算在图像处理方面的应用存在计算代价高和评价函数单一的缺点，提出了一种变尺度进化的多目标图像分割算法。该算法在进化的不同阶段将不同数量的相邻像素作为同一像素处理，从而在不同尺度下完成图像的分割，降低了算法的计算时间。同时，设计了监测关键解变化量的方法来控制不同尺度的过渡时机。在评价函数上则采用包含紧致度和连接度的多目标方式，以更为全面地评估分割的质量。其中，连接度检查邻接像素所属类别的连续性，有效抑制了噪声和小样本类的干扰。对Sailboat和Terra图像的分割结果显示，所提出的算法能有效地将不同对象分割开来，同时在计算时间上仅为几种同类对比算法的48.08%～55.53%。

进化计算；多目标；图像分割；变尺度；连接度

图像分割质量的好坏对后续的图像处理具有重要的影响[1]，而进化计算作为一种具有良好全局寻优性能的智能随机搜索技术，已广泛应用于图像的分割、检索、复原和压缩等方面[2-3]。但进化计算通常采用单一的目标函数来评价图像处理的质量，存在评价标准过于片面的不足[4]。而多目标进化优化技术作为近些年进化计算领域新兴的一个研究方向，致力于同时处理多个相互制约的目标函数的优化问题，已经取得了大量的研究成果[5-6]。这使得将多目标进化优化技术应用于图像处理领域具有了可行性。目前已有一些学者提出了各自的多目标进化图像处理算法[7]。如Shirakawa等人[8]提出了用于图像分割的多目标进化算法，而Bandyopadhyay等人[9]则提出了用于遥感图像分类的多目标进化聚类算法。上述方法均直接以单个像素点作为样本来进行数据聚类，但图像中包含的像素点往往很多，这影响了算法的处理效率，限制了多目标进化算法的应用范围。图像分割的目的是将图像中不同种类的对象区分开，而图像中像素之间的差异并非都属于不同类对象的差异，在同类对象内部实际也存在些许细节差异[10]。但这些内部差异对图像分割并无太大贡献，反而会让算法耗费时间去计算这些细节差异，影响了优化的速度。为了提高处理效率，可以在早期将若干相差不大的邻域像素合并，便于算法快速找出不同类对象的大致轮廓，再将合并的像素逐步拆分，最终准确确定不同对象的边界。为此，提出了一种变尺度进化的多目标图像分割算法(Multi-objective Evolutionary Image Segmentation with Varying-scale，MEISV)，采用了变尺度进化的方法，对各尺度过度的时机进行了控制，还采用了多目标进化的框架，并改进了连接度目标函数。对Sailboat图像的分割则表明了算法改进的有效性。

1 总体架构变尺度进化框架的设计

本文所提变尺度进化包含合并、进化、判别和分解4个步骤。框架如图1所示。

图1 变尺度进化框架的示意图

图2 区域合并示意图

区域合并步骤只在整个算法的初始阶段执行一次，通过将图像等分而得到粗粒度的像素，此后进化算法对这些粗粒度像素进行分割，达到一定判别准则后即进行粗粒度像素的分解，再对分解后的像素执行进化算法，直到所有像素均分解为单一像素且达到进化算法的迭代停止准则。

判别步骤是为了保证图像分割的准确度，在进化到一定时期以后通过关键解的变化情况来决定是否需要对粗粒度像素进行逐步分解。所谓关键解是指相对于周围其他解，它的某些目标函数取值仅有小幅变化，而另外一些目标函数取值则出现大幅变化，如图3所示。

图3 关键解示意图

分解步骤是对于当前尺度下的每个图像区域，分别以横向和纵向的中间位置为边界，将其划分为4个子区域。然后计算每个子区域像素的R，G，B均值，再对各个子区域相邻边界位置的像素进行局部调整。调整的方式为：对于边界位置的每一个像素，计算其与各个子区域R，G，B均值的欧氏距离，按照距离最近原则划归新的子区域，最后更新各子区域的R，G，B均值。经过分解以后图像中的区域数量将变为原先的4倍，当某一区域的像素个数等于或少于4个时，则直接分解为单个像素。

2 多目标图像分割算法的设计

2.1 多目标函数的设计

本文所设计的多目标函数为2个，称为紧致度指标和连接度指标。其中紧致度指标与文献[8]所提类似，如式(1)所示

k=1,2,…,C(x)

(2)

(3)

图4 噪声和小样本对连接度指标的干扰示意图

图4中“·”、“□”和“#”分别表示3类对象，“△”表示噪声像素，原先连接度倾向于将区域①和③作为两类对象，而改进后的连接度可以去除噪声的干扰，正确地将其划分为一类对象。

2.2 算法描述

3 实验结果与分析

为了验证算法的有效性，选取标准图像Sailboat和Terra做测试，如图5所示。

图5 用于测试的标准图像

设置了两种对比算法，分别为：1)文献[8]提出的多目标聚类图像分割算法，记为MOCKIS；2)连接度指标未做改进，其余与本文算法相同，记为CMEISV。

3.1 参数设置

相关参数的设置为：MOCKIS的所有参数设置与文献[8]相同；MEISV和CMEISV的种群大小为50，存储多目标优化所得解集的集合大小也为50，合并步骤中p和q的取值均为8，判别步骤中参数k0，z，t0以及ε的取值分别为3，3，10和10-3，区域像素在4个邻域方向上的近邻数量l1，l2，l3，l4均取值为5，最大类数Cmax则设为50，迭代停止条件为所有区域分解为单个像素并且连续t0代关键解的变化量小于阈值ε。所有算法中像素的相似性度量均是以R，G，B值之间的欧氏距离作为评价标准的。

3.2 分割效果对比与分析

3种算法在Sailboat和Terra图像上的测试结果，如图6和图7所示。图6和图7中，子图a～c为本文所提算法MEISV在优化结束时所得3个关键解的分割结果，子图d～f为对比算法CMEISV所得关键解的分割结果，子图g则为文献[8]所提供的MOCKIS的最佳分割结果。

图6 3种算法对图像Sailboat的分割结果对比

图7 3种算法对图像Terra的分割结果对比

从图6结果显示，本文提出的MEISV所得的3个关键解均可以将树木(近处)、草地、树林(远处)、天空和湖泊这些景物区分开，其中子图b和c还识别出湖泊中的船，子图c还识别出天空中的部分云彩。相比而言，对比算法CMEISV虽然也将大部分景物识别，但是由于连接度指标对噪声和少量像素构成的对象过于敏感，使得图像分割以后显示出大量小的分割区域，反而不利于主要信息的判别。对比算法MOCKIS的结果则更为粗糙一些，其未能将图中的树林与草地、天空和云彩、湖泊和船只区分开来。此外，由子图a～c还可以发现MEISV所得到的几个关键解随着分割类数的增加，其细节信息也逐渐增多，颜色相近的两个物体(如天空和云彩)也逐渐区分。这可以为技术人员提供不同层次下有价值的图像分割信息。

从图7中结果也可以得出类似结论：本文算法可以将远近不同的树林、田野、山峦等区分开，而对比算法CMEISV则得到的结果过于杂乱，缺乏层次性，MOCKIS则划分得过于简单，一些信息被忽略(如近处草地中包含有黄色和绿色两种草)。

3.3 运算时间对比

除了分析算法所得图像分割结果的质量，本文还在相同运行条件下测试了所提算法MEISV、MOCKIS和MEIS在运行时间上的差别。其中MEIS与本文算法MEISV采用相同的编码、交叉和变异以及目标函数，只是不进行变尺度操作，直接对各个像素点进行多目标图像分割。3种算法的迭代停止条件均设为函数调用次数达到预先设定的15 000次。测试结果如表1所示。

表1 3种算法的计算时间对比

s

图像名称耗时MEISVMEISMOCKISSailboat53211106710889Terra71331284513015

从表1结果可以看出本文算法在所用时间最短，在图像Sailboat上为MEIS的48.08%，为MOCKIS的48.86%，在图像Terra上则分别为55.53%和54.80%。可见变尺度进化框架在保持求解质量的前提下，可以有效减少优化过程所消耗的时间。

4 小结

提出的变尺度进化的多目标图像分割算法设计了先将局部像素合并再在进化过程中逐步分解的框架，有效降低了算法的运行时间，同时保证了图像分割的质量。其中设计的改进连接度指标对噪声和少量像素所构成的对象不敏感，从而有效降低了算法所受到的干扰。标准图像Sailboat的实验结果表明了改进算法的有效性，其所得分割结果能识别出图像中的主要内容，具有层次清晰的特点，而且算法消耗的时间最多减少达一半以上。

[1] 江成顺， 汪先超. 两相图像变分分割凸松弛模型快速算法[J]. 计算机学报，2013，36(5)：1086-1096.

[2] 靳璐， 付梦印. 基于遗传模糊核聚类的图像分割 [J]. 模式识别与人工智能，2013，26(1)：205-210.

[3] 任通，程江华，金阳. 一种基于白像素增量比的字幕图像分割算法[J]. 电视技术，2014， 38(5)：190-193.

[4] 李永乐，娄静涛，张茂军，等. 基于全向总变分最小化的折反射散焦模糊图像复原方法[J]. 光学学报， 2013(8)：99-105.

[5] 王璐，胡晰远， 彭思龙. 基于分块的空间变化抖动模糊图像的全局模糊去除[J]. 计算机辅助设计与图形学学报， 2012， 24(6)：766-774.

[6] 王冬冬， 张炜， 金国锋， 等. 尖点突变理论在红外热波检测图像分割中的应用[J]. 红外与激光工程， 2014， 43(3)：1009-1015.

[7] 李磊， 金良海， 宋恩民. 基于区域合并和图割的非监督彩色图像分割算法[J]. 华中科技大学学报：自然科学版， 2013， 41(12)： 44-47.

[8] SHIRAKAWA S， NAGAO T. Evolutionary image segmentation based on multiobjective clustering[C]//Proc. 2009 IEEE Congress on Evolutionary Computation. NY， USA：IEEE Press，2009：2466-2473.

[9] BANDYOPADHYAY S， MAULIK U， MUKHOPADHYAY A. Multiobjective genetic clustering for pixel classification in remote sensing imagery [J]. IEEE Trans. Geoscience and Remote Sensing，2007，45(5)：1506-1511.

[10] HANDL J，KNOWLES J. An evolutionary approach to multiobjective clustering[J]. IEEE Trans. Evolutionary Computation，2007，11(1)：56-76.

[11] 陈恺，陈芳，戴敏，等. 基于萤火虫算法的二维熵多阈值快速图像分割[J]. 光学精密工程，2014， 22(2)：517-523.

Multi-objective Evolutionary Image Segmentation Algorithm Based on Varying-scale

ZHOU Yuan，ZHOU Yan

(SchoolofComputer，HenanInstituteofEngineering，Zhengzhou451191，China)

Evolutionary computing has some shortages such as high computational cost and single measurement when it is used in the field of image processing. Hence，a novel multi-objective evolutionary image segmentation algorithm based on varying scale is proposed. The algorithm regards different regions of image as one pixel in different stages of evolution so that the image is segmented in different scales and the total consumed time is reduced. The transition moments among different scales are controlled by monitoring the variation of important solutions. On the other hand of measurement， a multi-objective version of compactness and connectivity is used to well estimate the image’s quality，wherein the connectivity is modified by checking the continuity of cluster label among neighboring pixels. This modification can effectively suppress the influence of noise and small clusters. Experimental results on standard images of “sailboat” and “terra” show that the proposed algorithm can well distinguish different patterns in the images and the time consumed is remarkable reduced to 48.08%～55.53%of those in other algorithms.

evolutionary computing；multi-objective；image segmentation；varying-scale；connectivity

TP391.41

A

10.16280/j.videoe.2015.17.006

2014-11-12

【本文献信息】周苑，周岩.基于变尺度进化的多目标图像分割算法[J].电视技术,2015，39(17).

周 苑(1978— )，女，讲师，硕士，主要研究方向为多媒体技术与信息处理；

周 岩(1981— )，女，讲师，硕士，主要研究方向为计算机应用与数据库技术。

责任编辑：时 雯