基于种内协同克隆选择的Otsu图像分割算法

童成意

长沙师范学院电子信息工程系，长沙 410100

基于种内协同克隆选择的Otsu图像分割算法

童成意

长沙师范学院电子信息工程系，长沙 410100

1 引言

图像分割是图像处理和计算机视觉中的关键技术之一，其结果的好坏将直接决定视觉系统的性能。在众多图像分割方法中，阈值分割法因其简洁直观、计算量小、易于实现而成为一种最基本的分割算法并获得了广泛应用[1]。目前已出现的阈值分割方法多达十余种，常用的有最大类间方差（Otsu）法[2]、最小误差法[3]和最大熵法[4]等。其中Otsu法是基于图像的灰度直方图，以最大类间方差为准则选择最佳阈值，不需要其他先验知识，是一种非常有效的阈值分割法。一维Otsu法只考虑了图像的灰度信息，而未考虑像素间空间位置的相关性，因此，当图像的灰度直方图不呈明显的波峰和波谷时，仅根据一维灰度信息进行图像分割，往往难以取得理想的分割效果，对此，刘健庄[5]等提出了基于二维直方图的Otsu算法。二维Otsu法在利用图像灰度特征的同时兼顾了像素间的空间相关性，因此比一维Otsu法具备更强的抗噪性，但是，二维Otsu法扩大了阈值搜索空间，造成了计算的复杂性。

针对二维Otsu阈值法存在计算复杂度高，实时性差等缺陷，许多学者进行了深入研究，提出了很多改进方法，如：Gong[6]等提出了一种二维Otsu法的快速递推算法，大大提高了算法的运算速度；郎咸朋[7]等提出了基于积分图像的快速二维Otsu算法，减少了算法的计算量，实现了图像的快速分割；徐长新[8]等通过缩小阈值搜索的空间，从而改善了算法的实时性。此外，随着智能优化技术的发展，运用智能优化算法求解最佳阈值逐渐成为图像分割的研究热点，取得了很多成果，如：将遗传算法应用于二维Otsu图像分割[9]，将差分算法应用于二维最小类方差阈值分割[10]，将微粒群算法应用于二维最小交叉熵阈值分割[11]等。但是，智能优化算法往

往收敛速度慢，且易于陷入局部极值。对此，本文对克隆选择算法进行改进，提出一种基于种内协同的克隆选择算法（CSACS），并用其求解二维Otsu的最佳阈值，实验结果表明，CSACS的分割结果与传统二维Otsu法基本相同，且运算速度快，能较好地满足实时性要求。

2 二维Otsu算法

设原图像f的尺寸为M×N，灰度级为L，计算f中像素的邻域均值得其平滑图像g，则g的尺寸和灰度级也分别为M×N和L。设灰度级为i，其邻域均值为j的像素出现的频数为mij，则可得灰度值-邻域灰度均值的二维直方图，相应的概率密度pij为：

如图1所示，对于任意阈值(s,t)，可将直方图分为A、B、C、D四个区域，其中A、B分别对应于图像的目标和背景，而远离对角线的C、D则对应于边缘和噪声，目标和背景出现的概率分别为：

图1 二维Otsu法直方图划分

目标和背景的均值矢量分别为：

在二维Otsu法中假设区域C，D的概率和为0，则w0+w1≈1，那么总体均值可表示为：

当类间方差S(s,t)取得最大值时的阈值(s,t)即为最佳阈值。

3 基于CSACS的二维Otsu图像分割

CSA以Burnet抗体克隆选择学说为基础，通过模拟机体受抗原入侵时，抗体与抗原的反应（如免疫细胞的分化与增殖，抗体细胞的产生等）而形成的优化算法。CSA包括三个步骤：克隆、克隆变异与克隆选择。CSA的具体原理与详细步骤见文献[12]。传统的CSA仅是各个抗体单独地进行克隆-变异-选择过程，而没有考虑抗体间的联系，因而优化效果往往不理想。对此，本文基于生物群体中成员的协作关系，对传统CSA进行改进。

生物群体中成员的协作关系已被广泛应用于优化领域，如微粒群算法、蜂群算法、鱼群算法等。在各种基于成员协作的优化算法中，有两条共同的规律：一是优秀个体会吸引其他个体（如蜂群发现蜂蜜即表演舞蹈吸引更多工蜂等）；二是劣势个体会排斥其他个体，使得个体远离它（如处于危险环境的个体，会通知其他个体远离危险）。对此，本文提出以下两种协作关系，并将其引入CSA。

（1）优势抗体吸引其他抗体，优势越明显，对其他抗体的吸引作用越强烈。抗体i受其他抗体吸引作用的计算公式如下：

其中，t∈[1,n]，rand为[0，1）上的随机数，f(ai)表示抗体i的亲和度。

（2）劣势抗体排挤其他抗体，环境越恶劣，对其他抗体的排挤越剧烈。与式（8）类似，给出抗体i受其他抗体排挤作用的计算公式如下：

刘佳走的时候，我去送他，他把领结摘了，要拿它换被我硬抢走的乳牙，我却把领结一并抢了过来，歪里歪气地说，这玩意儿跟上吊一样样的。

其中，t，rand和f(·)含义同上。

由式（8）、式（9）可得抗体i的位置更新公式：

其中，a′i(t+1)、a′i(t)分别表示抗体当前位置和上次迭代的位置。

基于CSACS的图像分割流程如下：

步骤1算法初始化。设置算法的各项参数，在阈值搜索范围内随机生成初始抗体群。

步骤2将式（7）作为抗体亲合力函数，计算各个抗体的亲合力。

步骤3按照式（8）和式（9）计算每个抗体受优秀个体吸引和受劣势个体排挤的程度。

步骤4依据式（10）移动抗体，实现抗体群的成员协作。

步骤5抗体克隆过程，为实现简单，设每个抗体的克隆规模相同。

步骤6抗体变异，按照突变概率对步骤5的克隆群体进行高频变异。

步骤7克隆选择，从步骤6的抗体变异群体中选择最优抗体，如该抗体比原始抗体优秀，则用其替换原始抗体。

步骤8判断算法是否终止。如算法终止，则算法结束并输出结果；否则，返回步骤2继续。

4 实验结果与讨论

4.1 CSACS与CSA的经典测试函数比较

测试对象函数f1、f2如下：

表1 CSACS与CSA的性能比较

函数f1为Schaffer’s函数，该函数有多处峰值，其中只有（0，0）为全局最大值，最大值为1。此函数的最大峰值周围有若干圆脊，因而可以很好地测试算法跳出局部最优的能力。

函数f2为Rosenbrock函数，该函数的每个等高线大致呈抛物线形，其全局最小值也位于抛物线形的山谷中（香蕉型山谷）。很容易找到这个山谷，但由于山谷内的值变化不大，要找到全局的最小值相当困难，因而可以很好地测试算法的寻优速度。其全局最小值位于（1，1），最小值为0。

为了比较CSACS与CSA的优化性能，选择f1、f2作为测试函数。参数设置如下：最大迭代次数为1 000，抗体种群规模为20，克隆规模为20，克隆变异率为0.2，每个函数独立测试20次。实验结果如表1所示。

由表1可知：在参数设置相同时，对于f1，CSACS获得的最大值、最小值、平均值都大于CSA的相应值，CSACS结果的标准差小于CSA；对于f2，CSACS获得的最大值、最小值、平均值都小于CSA的相应值，且CSACS结果的标准差小于CSA。故CSACS的优化性能比CSA好，且比CSA稳定。

4.2 基于CSACS的图像分割测试

为了检测CSACS在图像分割方面的有效性，采用带噪声的Airplane、Lena、Cameraman三幅图像进行仿真实验，其中Airplane带椒盐噪声、Lena带高斯噪声、Cameraman带高斯-椒盐混合噪声，三幅图像的分辨率均为512×512，灰度级为256。原始图像如图2所示。实验分别采用一维Otsu法、传统二维Otsu法、基于CSA的二维Otsu法和基于CSACS的二维Otsu法对图像进行分割，其分割效果如图3～图6所示。对比结果可知：一维Otsu法的抗噪性差，不能对噪声图像进行有效的分割；与一维Otsu法相比，二维Otsu法虽然可能会丢失图像的部分信息，但是抗噪性更强；基于CSACS的分割方法抗噪性比基于CSA的分割法好，寻找到的阈值更优（如对于Lena图像的分割，基于CSA的分割法帽沿分割不清晰，而基于CSACS的分割法能较好地对其进行区分）；基于CSACS的分割方法分割原理与传统二维Otsu法相同，且能获得与传统二维Otsu法相同的分割效果。

图2 原始图像

图3 一维Otsu法分割结果

图4 传统二维Otsu法分割结果

图5 基于CSA的二维Otsu分割结果

图6 基于CSACS的二维Otsu分割结果

为了进一步测试CSACS的性能，将CSACS与遗传算法（GA）[13]、微粒群算法（PSO）[14]、差分进化算法（DE）[10]进行比较并与传统二维Otsu算法进行对照。各种算法对Airplane、Lena和Cameraman的分割结果如表2所示。由表2可知：GA优化能力较差，算法很难寻找到最优值，且算法效率低；PSO、CSACS和DE的分割效果较好，与最优值较为接近，且算法速度较快。CSACS由于考虑了种群内成员间的合作关系，能使个体较快地靠近最优个体远离差的个体，从而取得了最快的收敛速度；同时由于克隆免疫算法具有较强的搜索能力，故CSACS在快速收敛的同时，具有较高的收敛精度。因此，CSACS算法能够在获得与传统二维Otsu法相近的分割效果的同时其速度却成倍提高，克服了传统二维Otsu算法实时性差的缺点。

表2 CSACS与其他算法分割结果比较

5 结束语

本文将CSACS与传统二维Otsu法相结合，用于图像分割，不但继承了传统二维Otsu法的优点，由于CSACS考虑了种群成员间的协作关系，计算速度快，能在较短时间内对图像进行分割，有效克服了传统二维Otsu法计算量大、实时性差等不足。实验测试表明基于CSACS的图像分割在保证图像分割效果的同时具有很好的实时性，在图像处理领域有着较为广泛的应用前景。

[1]吴一全，潘喆，吴文怡.二维直方图区域斜分的最大熵阈值分割算法[J].模式识别与人工智能，2009，22（1）：162-168.

[2]Otsu N.A threshold selection method from gray-level histograms[J].IEEE Transactions on Systems，Man and Cybernetics，1979，9（1）：62-66.

[3]张新明，冯云芝，闫林，等.一种改进的二维最小误差阈值分割方法[J].计算机科学，2012，39（8）：259-287.

[4]阿里木·赛买提，杜培军，柳思聪.基于人工蜂群优化的二维最大熵图像分割[J].计算机工程，2012，38（9）：223-243.

[5]刘健庄，栗文青.灰度图像的二维Otsu自动阈值分割法[J].自动化学报，1993，19（1）：101-105.

[6]Gong J，Li L Y，Chen W N.Fast recursive algorithm for twodimensional threshold[J].Pattern Recognition，1998，31（3）：295-300.

[7]郎咸朋，朱枫，郝颖明，等.基于积分图像的快速二维Otsu算法[J].仪器仪表学报，2009，30（1）：39-43.

[8]徐长新，彭国华.二维Otsu阈值法的快速算法[J].计算机应用，2012，32（5）：1258-1260.

[9]江禹生，宋香丽，任晶晶.基于遗传算法的二维Otsu算法改进[J].计算机应用研究，2010，27（3）：1189-1191.

[10]聂方彦，高潮，郭永彩.灰度图像二维最小类方差递推及差分演化的快速分割[J].计算机辅助设计与图形学学报，2010，22（11）：1866-1873.

[11]吴一全，张晓杰，吴诗婳.基于混沌弹性粒子群优化与基于分解的二维交叉熵阈值分割[J].上海交通大学学报，2011，45（3）：301-307.

[12]孙大为，常桂然，李凤云，等.一种基于免疫克隆的偏好多维QoS云资源调度优化算法[J].电子学报，2011，39（8）：1824-1831.

[13]Bhattacharya M，Das A，Chandana M.GA-based multiresolution fusion of segmented brain images using PD-，T1-and T2-weighted MR modalities[J].Neural Computing&Applications，2012，21（6）：1433-1447.

[14]Chander A，Chatterjee A，Siarry P.A new social and momentum component adaptive PSO algorithm for image segmentation[J].Expert Systems with Applications，2011，38（5）：4998-5004.

TONG Chengyi

Electronic Information Engineering Department,Changsha Normal University,Changsha 410100,China

Traditional two-dimensional Otsu’s method has the disadvantages of high computational complexity,poor real-time performance.In order to improve its efficiency,inspired by the collaborative relationships among group members,a Clonal Selection Algorithm based on Cooperation within Species（CSACS）is proposed.CSACS is compared with Clonal Selection Algorithm（CSA）,and is used to image segmentation.The experimental results show that：the algorithm can accelerate the convergence speed,has good real-time ability,and its segmentation effect is very well.

Clonal Selection Algorithm（CSA）;coevolution;image segmentation;Otsu

传统二维Otsu算法存在计算复杂度高、实时性差等缺点。针对这一不足，受生物群体成员间协作关系的启示，对克隆免疫算法进行改进，提出了一种基于种内协同的克隆选择算法（Clonal Selection Algorithm based on Cooperation within Species，CSACS），将其与克隆选择算法（Clonal Selection Algorithm，CSA）进行对比测试，将其应用于二维Otsu图像分割。测试实验表明：该算法能加快收敛速度，具有较好的实时性，且分割效果较为理想。

克隆选择算法；协同进化；图像分割；Otsu

A

TP301.6

10.3778/j.issn.1002-8331.1304-0490

TONG Chengyi.Image threshold segmentation method based on CSACS.Computer Engineering and Applications,2013, 49（24）：161-164.

湖南省自然科学基金重点项目（No.13JJA002）。

童成意（1965—），男，副教授，研究领域为嵌入式系统及其应用，智能控制理论与应用，电力系统与控制。E-mail：329699077@qq.com

2013-05-06

2013-08-29

1002-8331（2013）24-0161-04