基于链式竞争遗传算法的KSW熵的图像分割*

曹 静， 王 元， 娄泽坤， 冷鹏飞

(河南大学 计算机与信息工程学院，河南 开封 475000)

基于链式竞争遗传算法的KSW熵的图像分割*

曹 静， 王 元， 娄泽坤， 冷鹏飞

(河南大学计算机与信息工程学院，河南开封475000)

针对最佳熵阈值图像分割算法过程中计算复杂度高的问题，提出了一种基于链式竞争遗传算法的最佳熵阈值确定法(KSW熵法)的图像分割算法。通过将3个邻域的链式竞争引入到常规遗传算法框架下，实现特征选择过程；将改进的遗传算法应用到最佳阈值图像分割算法中，完成对阈值的寻优过程。仿真实验结果与分析表明：算法在分割速度和效果上均优于传统的最佳阈值图像分割算法和单纯的遗传优化最佳阈值图像分割算法。

图像分割； 最佳阈值图像分割； 遗传算法； 链式竞争

0 引 言

图像分割是一种将图像分割成若干个具有特定性质的区域，是不同区域之间的差别尽可能明显的图像处理方法[1]。传统的图像分割方法分为阈值法图像分割、边缘检测法图像分割、区域生长法图像分割、模糊理论图像分割及数学形态学图像分割等。由于其应用目的不同，且图像特征不同，这些方法均存在一定的局限性。其中，阈值方法因其简单且稳定的性能成为了图像分割中最基本的技术之一[2]。Ostu N等人[3]针对控制图像分割造成的信息损失提出了基于信息论熵准则的图像阈值自动选取方法解决了阈值分割中门限的选取问题，优于常用的灰度差直方图法。但由于多数图像并不可以简单的一分为二，因此对于灰度等级分布谷底不明显的复杂图像，利用单一Otsu准则无法将目标可靠、稳定地从图像中分割出来。为解决上述问题，Kapur，Sahoo和Wong等人[4]提出了最佳熵阈值确定性图像分割算法,简称KSW算法。无需利用先验知识，且即使是非理想双峰直方图的图像也可进行处理，然而，其在确定多阈值时，计算复杂度过大，分割图像所需时间较长。根据以上问题，种劲松等人[5]提出了基于遗传算法的最佳熵阈值图像分割法(GA-KSW算法)，利用遗传算法的鲁棒性、并行性和自适应性的特点，将其与KSW算法有效地结合，缩短了寻找阈值的时间。但是该算法利用了传统遗传算法容易令图像分割过程陷入“早熟”，图像分割效果并不理想。

本文针对上述问题，提出了一种基于链式竞争遗传算法的KSW熵的图像分割处理算法(L-GA-KSW熵算法)。

通过对常规遗传算法加入三个邻域的链式竞争[6]，改进特征选择过程；然后将改进后的遗传算法应用到最佳阈值图像分割上，克服了传统遗传算法在阈值图像分割中的不足。

1 KSW熵算法[7，8]

根据Shannon熵的概念，对于灰度范围为{0,1,…,l,-1}的图像，其直方图熵的定义为

(1)

式中pi为第i个灰度出现的概率。在单阈值情况下，设阈值t将图像划分为目标与背景两类，则令

(2)

(3)

有阈值t分为A和B两类后,则这两类的概率分布列分别为

(4)

(5)

则目标与背景的熵H0(t)和HB(t)分别为

(6)

(7)

图像的总熵H(t)为H0(t)和HB(t)之和，即

H(t)=H0(t)+HB(t)

(8)

最佳阈值t*为使得图像的总熵取得最大值

(9)

在多阈值情况下，设S1,S2,…,Sk为分割阈值，且有S1

(10)

S2，…,Sk)

(11)

(12)

(13)

2 L-GA-KSW熵算法设计

GA[9]全局寻优能力较强且具有较好的鲁棒性。但是由于标准GA容易陷入局部最优和“早熟”等，为了改进GA，文中采用链式竞争策略寻找最优KSW阈值,通过链式智能体相互竞争、变异和交叉等方式有效地保持了种群个体的多样性，从而能够获得更准确的结果和更快的收敛速度。算法设计如下:

1)初始化GA中的参数(包括迭代次数、种群规模、交叉和变异概率的选择等)以及种群选择的适应度函数。

2)采用轮盘赌法选择若干满足适应度函数要求的染色体组成新种群作为父本。

3)通过GA的交叉、变异对父本进行处理，产生新一代种群。

4)计算种群中每个个体的适应值，引入三个邻域的链式竞争，对个体的适应值进行三个邻域比较进行特征选择，产生新的种群。

5)重复步骤(2)～步骤(4)，使染色体不断变化，直到进化代数完成，记录每一代进化中最好的适应度值。

6)终止准则：规定当算法执行到最大代数(终止条件)或经过100代进化，群体中的最高适应度值仍未发生变化(稳定条件)时，算法停止运行，具有最高适应度值的个体即为分割阈值。

步骤(4)是本文引入的链式竞争策略对个体的适应值进行三个邻域的比较，完成特征选择。当扫描到第一个个体时，其前一个体为最后个体，下一个体为第二个个体，同理当扫描到最后一个个体时，其前一个体为倒数第二个个体，下一个体为第一个个体。将相邻的三个个体作为适应值存放在邻域寄存器中，找出相邻三个个体中的最小适应值以及对应的个体，则当前个体不变；否则，将此最小适应值对应的个体与当前扫描的个体比较，相同位不变；不同位则随机生成0～1之间的随机数。

基于以上分析，给出算法的编码方案如下：对于单阈值图像分割，由于图像灰度值在0～255之间，故将各个染色体编码为8位二进制码，其代表某个分割阈值。当图像中存在多个分割目标时采用多阈值分割，文中针对双阈值分割进行程序设计，将单阈值分割中的8位二进制码串改为16位，前8位代表一个门限值，后8位代表另一个门限值。双阈值分割属于多参数遗传程序设计，本文设置种群数20，繁殖代数为100。

3 仿真结果

仿真场景硬件设置为HP 286，内存4 GBWindows 7，仿真软件为Matlab 2012a。为测试L-GA-KSW算法的有效性和优越性，选择原始Lena图像，加噪声的Lena图像以及Rice图像作为仿真对象。为使加入L-GA-KSW熵算法更有说服力，选择标准的KSW熵算法、标准GA优化KSW熵算法(GA-KSW熵算法)和文中提出L-GA-KSW熵算法进行了对比实验。遗传算法交叉概率0.8，变异概率0.1， 种群数20。

图1中的3类图像分别为Lena标准原始图像、加噪声的Lena和加噪声的Rice。分别用KSW熵算法、GA-KSW熵算法、L-GA-KSW熵算法分割，结果如图2～图4。

图1 仿真对象

图2 原始Lena图像分割结果

图3 加噪Lena图像分割结果

图4 原始Rice图像分割结果

从表1和表2中可以看出，利用加入L-GA-KSW熵算法对Lena图像、加噪声的Lena图像、Rice图像进行分割所用时间明显少于标准KSW熵算法和GA-KSW熵算法实验结果表明，L-GA-KSW算法将分割效果及处理速度进行了优化，得到了更好的分割效率，且鲁棒性更好。

表1 3种算法分割阈值结果

表2 3种算法图像分割时间 s

4 结 论

实验结果表明:本文提出的算法提高了图像的分割效果、提高了图像分割算法的鲁棒性、缩短了图像分割时间，有利于图像的实时处理。通过实验对比本文提出的算法优于传统的KSW算法和GA-KSW熵算法。

[1] 宋家慧.基于遗传算法的最大熵阈值的图像分割[J].信息化研究,2005,31(2):60-63.

[2] Pal N R,Pal S K.A review on image segmentation techniques[J].Pattern Recognition,1993,26(9):1277-1294.

[3] Ohtsu N.A threshold selection method from gray-level histograms[J].IEEE Transactions on Systems Man & Cybernetics,1979,9(1):62-66.

[4] Kapur J N,Sahoo P K,Wong A K C.A new method for gray-level picture thresholding using the entropy of the histogram[J].Computer Vision Graphics & Image Processing,1980,29(3):273-285.

[5] 种劲松,王宏琦.基于遗传算法的最佳熵阈值图像分割法[J].北京航空航天大学学报,1999,25(6):747-750.

[6] 曾孝平,李勇明,王 靖,等.基于竞争策略的链式智能体遗传算法用于特征选择的研究[J].系统仿真学报,2008,20(8):1973-1979.

[7] 谢鹏鹤,杨恢先,王绪四.基于最大累积剩余熵的红外图像分割[J].传感器与微系统,2011,30(7):34-37.

[8] 伦向敏,侯一民.运用迭代最大熵算法选取最佳图像分割阈值[J].计算机工程与设计,2015(5):1265-1268.

[9] 李敏强.遗传算法的基本理论与应用[M].北京：科学出版社,2002.

ImagesegmentationofKSWentropicbasedonchaincompetitivegeneticalgorithm*

CAO Jing， WANG Yuan， LOU Ze-kun， LENG Peng-fei

(SchoolofComputerandInformationEngineering,HenanUniversity,Kaifeng475000,China)

Aiming at the problem of high computational complexity in the process of the optimal entropic threshold image segmentation algorithm,propose an image segmentation algorithm based on link-like competition genetic algorithm for optimum entropy thresholding method,i.e.KSW entropy(L-GA-KSW).In the process of algorithm realization,feature selection process is realized by introducing the chain competition of 3 neighboring chains into the framework of conventional genetic algorithm;then,the improved genetic algorithm is applied to the optimal threshold image segmentation algorithm to achieve threshold optimizing.Simulation results and analysis show that the algorithm is superior to the traditional image segmentation algorithm and the simple genetic optimization threshold image segmentation algorithm in segmentation speed and effect.

image segmentation; optimal threshold image segmentation; genetic algorithm(GA); link-like competition

10.13873/J.1000—9787(2017)11—0128—03

TP 391

A

1000—9787(2017)11—0128—03

2016—09—29

国家科技支撑计划课题资助项目(2015BAK01B06)

曹 静(1992-),女，硕士研究生，研究方向为数字图像处理。