基于克隆选择算法的最大模糊熵图像分割

基于克隆选择算法的最大模糊熵图像分割

Image segmentation based on maximum fuzzy entropy and Clone Selection

Algorithm

Abstract: A threshold segmentation method based on maximum fuzzy entropy and immune clone selection algorithm is proposed to segment an image with nonuniform illumination. According to the maximum fuzzy entropy principle, the optimal combination of the fuzzy parameters is searched, and the optimal threshold is determined to distinguish the object and background. In order to validate the proposed method, it is tested and compared with genetic algorithm. Experimental results show that the proposed method gives better performance, and can select the threshold automatically and efficiently, and has an advantage of reservation of the main features of the original image.

Key words: image segmentation；thresholding；maximumfuzzy entropy；Clone selection

摘 要：为了分割照度不均匀的图像，提出了一种基于最大模糊熵和免疫克隆选择算法的阈值分割方法。该方法利用最大模糊熵准则确定模糊区间的范围，寻找模糊参数的最优组合，确定区分目标和背景的最佳阈值，实现图像分割。为了验证该方法的有效性，对其进行了图像分割实验，并与遗传算法进行了比较。实验结果表明，该算法能够自动、有效地选取阈值，分割效果优于遗传算法，并能保留原始图像的主要特征。

关键词：图像分割；阈值；最大模糊熵；克隆选择 文献标识码:A 中图分类号: TP391

0引言

图像分割是图像处理和计算机视觉领域中的关键技术，主要的分割方法包括阈值法、边缘检测法、区域跟踪法等。其中，阈值法因其简单且性能稳定而成为图像分割中的最常用方法。在阈值法中，阈值的选取是图像分割的关键。目前，阈值分割方法已有很多种，例如直方图阈值分割、类间方差阈值分割、最大熵阈值分割等，但它们应用于不同的图像时，其自适应性不是很理想。近年来，模糊集合理论已成功应用于图像分割，并取得了较好的效果。Pal[1]等人于1983年提出了模糊阈值法，随后Cheng[2]等人又进行了深入的研究。该方法通过计算图像的模糊熵，寻找使模糊熵最大时的参数值，进而确定分割阈值，其模糊参数的寻优实际上是一个优化问题。采用穷举法搜索模糊参数的最优组合存在计算复杂度高、占用内存空间大等缺点。采用遗传算法[3-4]来优化参数，确定最优阈值，效果较好，但同样存在计算复杂度比较高的不足。

针对以上不足提出了一种基于免疫克隆选择算法和最大模糊熵的图像分割方法，根据最大模糊熵准则采用克隆选择算法搜索模糊参数的最优组合，进而确定图像的分割阈值。试验结果表明该算法简单，容易实现，而且可以得到较好的分割效果。

1最大模糊熵原理及免疫克隆选择算法 1.1最大模糊熵原理

由模糊集合理论，可以根据图像像素灰度值把一幅图像分成若干个模糊集，运用最大模糊熵准则确定对应的隶属函数，使之能最好地反映像素的灰度值隶属于模糊集的程度，从而确定模糊区间的范围，寻找模糊参数的最优组合，得到最优阈值。

假定一副图像为X，灰度直方图为

h

k

,其下角k表示图像像素的灰度级，

k0,1,,255。根据模糊理论，图像X可看成是一个模糊事件。由灰度值可以把图像像素

分成两个模糊集,即黑和亮两个集合。黑模糊集包含低灰度值的像素,亮模糊集包含高灰度值的像素。这两个模糊集的隶属函数



m

(k)和(k)被定义[3]如下:

n

1

2

ka

12cam(k)2ka2

ca

00

2

ka2

ca2

n(k)

ka12

ca

1

kaakb

（1）

bkckckaakb

（2）

bkckc

2。

式中，k是一个独立变量，a，b和c是参数，且满足0ac255，b(ac)[a，c]是模糊区间，[0，a]和[c，255]是非模糊区间。这两个模糊集发生的概率为

pp

m

k0

k

255n

k

255

m

(k) （3）

pp(k) （4）

k0

n

式中，

p=hk。

k

每一个模糊集的模糊熵可由下式计算

H

m

pln(p)(1

m

m

p

m

)ln(1

p

m

) （5）

H

n

pln(p)(1

n

n

p)ln(1p) （6）

n

n

H(a,c)

HH

m

n

（7）

由信息论可知，一个事件的熵越大，所含有的信息量就越大。若要实现目标与背景的最佳分割，则模糊事件X 的模糊熵应最大，也就是说分割后的图像所包含的原图像的信息量最大。当总模糊熵H(a,c)取得最大值时，通过求解可得到最优的模糊参数（此可确定最优阈值

a,c

opt

opt

）由

y

opt

。最优阈值

y

opt

满足如下条件:

即阈值

(y

m

opt

)(y)0.5 （8）

n

optn

m

n

y

opt

是隶属函数曲线



m

(k) 和(k)的交点。由于(bopt)(bopt)0.5，

因此最优阈值

y

opt

bopt(aoptcopt)2。

1.2克隆选择算法

克隆选择原理由Jerne于1955年提出，之后经Burnet和Talmage发展和完善,是免疫系统的基本理论之一。克隆选择的基本思想是当任何一种抗原侵入时，机体都能在内部克隆出识别和消灭相应抗原的免疫细胞,使之激活、分化、增殖并进行免疫应答，以最终清除抗原。克隆选择描述了获得性免疫的基本特性：只有成功识别抗原的免疫细胞才得以增殖，经历变异后的免疫细胞分化为浆细胞和记忆细胞两种。克隆选择原理可通过采用变异等免疫算子和相应的群体控制机制实现。克隆选择算法 [6]的设计是整个人工免疫系统的重要组成部分，对完成系统的进化以及特定问题的收敛具有重要作用。人工免疫系统的实现主要有阴性选择算法、克隆选择算法、人工免疫网络算法等。其中免疫克隆选择算法（ICSA）的核心是比例复制和比例变异算子，算法的实现过程如图1所示。

2 基于最大模糊熵和克隆选择算法的图像阈值分割设计

根据最大模糊熵原理，基于最大模糊熵的图像分割算法其本质是在图像的整个灰度空间上搜索一组参数（a,c）使(7)式总模糊熵取最大值的优化问题。因此，算法的计算量大，耗

时多。为此，将克隆选择算法应用于该算法中，以降低算法的复杂度，提高算法的速度和解的质量。 2.1初始化

设定种群规模为N，由于待编码的参数是a和c，而它们的值均在0-255之间，因此对每一个参数来说，通过使用一个8位的二进制字符串编码，则这两个参数的联合编码为16位长度的二进制字符串。生成初始染色体种群，如果参数a和c是随机产生的，则有可能不满足

0ac255，为了保证能满足该条件，采用了如下的数学处理方法：

使用

aa （9）

1

c1a1(255a1)

c

（10） 255

a和c代替a和c可进行后续计算。

1

1

2.2亲和度的计算

根据式（7）计算每个抗体的亲和度f(

x)，如果最大的亲和度值大于记忆阈值

i

m

，则该

抗体迁移到记忆单元，然后比较记忆单元中是否有其相似性抗体，如果有，则进行克隆抑制操作，删除其中亲和度小的抗体。

2.3克隆复制算子

根据亲和力的大小对种群中的每个个体执行独立的按比例克隆操作，按下式计算每个抗体的克隆规模

M

[7]

i

：

m

N

MiInt(N

f(i)

i

) (11)

f(x)

i1

其中：

N

m

Mi是总的克隆规模，Int()为取整函数。个体的亲和力越大，个体

i1

N

越优良，就会克隆出更多的子个体，保护优良基因，加快算法收敛速度。 2.4克隆高频变异算子

对复制的每个子个体，依概率大小判断是否执行克隆高频变异操作。高频变异，即高斯变异与柯西变异，已经成功地应用在遗传算法中[8]。高频变异算子提供了产生新解的方法，使得新解的产生不受其它个体的影响，提高了种群的多样性。

在抗体进化过程中，本文同时采用高斯变异与柯西变异这两种策略。利用高斯变异策略对个体执行小步长变异，利用柯西变异对个体执行大的变异。根据个体的好坏，选择执行哪种变异，即对优良个体执行小步长变异——高斯变异，以提高解的精度；对适应度较低的个体执行大步长变异，即柯西变异，帮助逃离局部极值。

（1）高斯变异

经过高斯变异，抗体

x将被x'代替：

i

i

x'xN(,) (12)

i

i

其中，N(,)是由高斯方程[8]产生的一个随机数：

为简化计算，本文分别取与为0和1。因此，高斯变异为：

（2）柯西变异 柯西密度函数为：

i

i

11xfGaussian(x)22()] (13)



2

x'xN(0,1) (14)

t

f

Cauchy

(x)

(tx)

22

(15)

其中t是尺度参数，并且t>0。经过柯西变异后，抗体

式中，

x变成x'：

i

i

x'x

i

i

k

(16)



k

是由柯西方程产生的随机数，是修正步长。

2.5 克隆选择

个体经过成比例克隆复制、克隆高频变异后，从父代个体与子代个体中选择出适应度最高的个体作为下一代个体。父代个体与子代个体的混合，避免了算法的退化，由于采用筛选较优新抗体的选择方法，系统不会因为变异的随机性而导致亲和力的下降，从而在保证系统多样性的同时，也使得亲和力的不断上升。 3实验结果及分析

选取标准cameraman图像作为算法的分割对象，灰度级为256，图像大小为256256。算法的群体规模N为10，最大迭代次数100，交叉概率px=0.7，变异概率pa=0.2。

为比较算法的性能，将免疫克隆选择算法（ICSA）和遗传算法(GA)各自独立运行10次并记录下各自结果加以比较，图2为阈值分割结果比较。结果可以看出，遗传算法得到的最优阈值波动比较大，然而免疫克隆选择算法得到的结果与最佳熵法相比其最优值比较稳定，而且可以在较少迭代代数下得到较优的图像分割阈值，说明算法的稳定性优于相应的遗传算法，是求取最优阈值的有效办法。

7570

656055

1

2

3

4

5

6

7

8

9

10

图2阈值分割结果比较

用实验得到的最佳熵阈值对原图像进行阈值分割，结果如图3所示，3(a)为原始图像，

图3(b)为本文算法的分割结果，所对应的模糊参数最优组合(

a

opt

32,copt100)，

y

opt

66，图3(c)为遗传算法分割结果。比较原图和遗传算法的分割图像，由遗传算法得

到的阈值偏高，对部分目标的分割不完整，图像分割失真比较大。而本文算法能较为准确地选择分割阈值，较好地实现目标和背景的分割，图像分割效果好。

图3(a)原始图像 图3(b) 本文算法分割结果 图3(c)遗传算法分割结果 4总结

最大模糊熵图像分割算法独立于图像的直方图，不需要先验知识，自适应性强，本文通过将模糊集合理论与克隆选择算法相结合，利用最大模糊熵准则确定模糊区间的范围，通过克隆选择算法搜索模糊参数使总模糊熵达到最大值，进而确定最佳分割阈值。仿真实验结果表明，克隆选择算法的分割效果明显优于相应的遗传算法，不但具有较快的运算速度,而且能够得到图像的理想分割结果，是一种有效的图像阈值分割算法。

参考文献：

[1] S K Pal, R A King，A A Hashim. Automatic grey level thresholding through index of fuzziness and entropy[J]. Pattern Recognition Letters, 1983, 1(3):141-146.

[2] H D Cheng, J R Chen, Li Jiguang.Threshold selection based on fuzzy c partition entropy approach [J]. attern Recognition, 1998,31(7): 857 - 870.

[3] 陶文兵,等.基于遗传算算法和模糊墒的前视红外图像分割[J].红外与毫米波学报，2003， 22(6):465-468. [4] 汤晖,许伦辉.退火遗传算法在交通图像分割中的应用研究[J].微电子学与计算机，2008，25(8)：22-24. [5] 吴成茂.模糊熵的修改及其在图像分割中的应用[J].微电子学与计算机，2008，25(1)：25-28. [6] DeCast ro L N，Zuben V. Learning and optimization using the clonal selection.issue on Artificial Immune System(AIS), 2002,6(3):239-351.

[7] De Castro L N, Timmis J. An artificial immune network for multi-modal function optimization [C]. Proc of the IEEE Congress on Evolutionary Computation. Honolulu, 2002: 699-704.

[8] Yao X, Liu Y. Evolutionary programming made faster. IEEE Transactions on Computation, 3(2):82-102.