基于IGA的三维OTSU算法的改进

1、基于IGA的三维OTSU算法的改进张玉连，褚巧龙，郭贵冰 （燕山大学 信息科学与工程学院，河北 秦皇岛，066004）摘要：在图像分割中三维OTSU阈值分割算法充分考虑了像素之间的灰度相关信息，较一维和二维OTSU阈值法的分割效果好，但其计算复杂性高、实时性差。为此，本文提出了将免疫遗传算法应用到三维OTSU阈值寻优中，并采用递推的方法来减少适应度函数的计算。实验表明，与传统的三维OTSU阈值分割算法相比，图像分割清晰，实时性得到明显改善。关键词：图像分割；三维OTSU阈值分割法；免疫遗传算法中图分类号:TP391Three-dimensional Otsu Threshold Algorit

2、hm Based On The Improved of Immunity Genetic AlgorithmZhang Yu-lian,Chu Qiao-long,Guo Gui-bing(College of Information Science and Engineering,Yanshan University,Qinhuangdao Hebei ,066004,China)Abstract The three-dimensional OTSU thresholding segmentation method utilizes gray level correlation inform

3、ation between each of pixel in image segmentation field,and it have better segmentation result than one-dimensional and two-dimensional thresholding,but it had the high complex computational complexity and poor real-time.So,this paper adopted an immunity genetic algorithm and used in the search of t

4、hree-dimensional OTSU optimizing threshold,and the repeat computations of the fitness function in iteration are reduced significantly using recursion. The experimental results show that compared with the traditional three-dimensional OTSU thresholding segmentation method,the image segmentation clear

5、,and the real-time had be improved.Key words:image segmentation;three-dimensional OTSU thresholding segmentation method; immunity genetic algorithm0 引言图像分割是图像处理的一个关键步骤，是计算机视觉和人工智能中基本而关键的技术之一。阈值分割因其计算简单、实时性高，而成为图像分割的应用最广泛的关键技术之一。在众多阈值分割算法中，由Otsu1在1979年提出的1维最大类间方差法，因其计算简单、分割效果较好而得到广泛应用，但其仅仅利用像素本身的灰度信息

6、，没有利用像素之间的空间信息，并且信噪比较低，遇到较复杂的图像时，容易产生较严重的分割错误。针对这一点，我国学者刘健庄2等人在1993年提出了基于自身灰度和邻域平均灰度的二维Otsu阈值分割法，其抗噪声能力要强于1维Otsu阈值分割法，并且图像处理效果也有明显改善。但是，随着噪声的增加，图像的信噪比不断降低，图像的分割效果也越来越差。为此，景晓军等人3引入了邻域中值作为第三个特征，构造了三维直方图，并提出了三维Otsu阈值分割法，使得对于低信噪比的图像有了更好的分割效果，并给出了一个递归算法，是得三维Otsu法的计算复杂度从O(L6)降到了O(L3)。范九伦等人4在此基础上指出了景晓军给出的递

7、归公式的错误并加以改正，同时给出了一组新的递推公式，计算复杂度仍为O(L3)，但时间有所减少，并且证明了加入了混合噪声的图像的处理效果更好。虽然递推算法的引入使得三维Otsu阈值分割法的计算复杂度降低了，但是计算时间仍较长，也容易受到噪声干扰，基于此点，本文提出了将免疫遗传算法融入到三维Otsu阈值分割法中，既可利用遗传算法的固有的并行性、不易陷入局部最优和全局搜索的特点，在将免疫因子融入到遗传算法的时候，也缓解了遗传算法的退化现象，克服了遗传算法的早熟收敛和收敛性能差的缺点，大大提高了搜索效率5。总而言之，将免疫遗传算法应用到三维Otsu阈值分割算法中，提高了该算法的抗噪能力，在搜索最佳阈值

8、过程中节约了时间，提高了算法的实时性，达到了较好的分割效果。1 三维Otsu阈值分割法对于一幅的数字图像，我们用来表示处像素点的灰度值，用来表示处的邻域的平均灰度值，定义如下： (1)用表示处邻域的灰度中值，定义如下： (2)从和的定义可以看出，如果图像的灰度级为，那么相应的邻域平均灰度级和邻域中值的灰度级也为。我们将由、和组成的三元组定义为三维直方图，该三维直方图定义在一个的立方体区域内，其三个坐标分别表示像素的灰度值、邻域均值和邻域中值，如图1(a)所示。将直方图上任意一点的向量发生的频率定义为，由下式确定： (3)其中是出现的频数，。(a)三维直方图的定义域775611163442(b)

9、三维直方图区域的划分02424433(c)区域0、2、3、4的划分11616775(d)区域1、5、6、7的划分图1 三维直方图区域Fig.1 D histogram region根据上面给出的三维直方图定义，若是选取的阈值点，则三维直方图被分成如图1(b)所示的八个区域，具体的区域划分如图1(c)和(d)所示。由于目标内部和背景内部的像素点之间的相关性较强，像素点的灰度值、邻域均值和邻域中值非常接近；而目标和背景的边界附近的像素点，以上三个值之间的差异会比较明显。基于以上认识，区域0和区域1分别被看成背景和目标，区域27被看成边缘和噪声。由于边界和噪声区域的像素点远远小于背景和目标的像素点，

10、所以我们将区域27的所有像素点的概率和近似为0。三维直方图中的区域0和1分别代表图像的背景和目标，为了表示方便，将这两个区域分别表示成和，则背景和目标分别出现的概率为： (4) (5)背景和目标对应的均值矢量分别为： (6) (7)三维直方图上总的均值矢量为： (8)前面我们已经假设区域27的概率之和近似为0，则可知： (9) (10)定义类间的离差矩阵 (11)使用的迹作为类间的离散度测度，有 (12)这里，。则最佳阈值即为离散度测度取得最大值时，即 (13)2 基于IGA的三维OTSU算法的改进遗传算法是根据生物进化的模型提出的一种进化算法，它模拟生物优胜劣汰的繁衍过程，算法的步骤主要是初

11、始化群体、适应度评估、选择、遗传和变异等。遗传算法具有易编码、操作简单、全局解空间搜索等优点，但也有待改进的地方：易退化、早熟收敛、收敛性能差等。免疫算法是模拟生物体的免疫系统对从外界入侵的细菌、病毒进行防御的一种优化算法，其特点是操作简单、收敛速度快，算法的核心是疫苗的提取和接种。目前，免疫遗传算法(Immunity Genetic Algorithm，简称IGA)存在多种结合模式，本为所采取的是将免疫因子融入到遗传算法当中，可以有效克服遗传算法的早熟收敛和收敛性能差的缺点，提高收敛速和搜索效率6,7。本文又将传统的免疫遗传算法进行了还进，将三维OTSU阈值法和改进后的免疫遗传算法结合到一起

12、，可以改善三维OTSU阈值法的分割效果，提高运算速度。改进算法的主要步骤如下：(1)编码由于图像的灰度级别为0255，将每个染色体的编码长度设置为8bit，对于使用三维OTSU阈值法进行分割，这里定义的每条染色体的长度即为24bit，它表示某个阈值。(2)初始化 对于初始群体的产生，一般采用的是随机的方法。由于初始群体的规模会影响算法的执行效率和结果。规模太大，则计算复杂性提高，运行时间较长；规模太小，则会导致搜索空间国小，不利于求取最优解。我们在区间0255以同等概率随机生成30个个体，作为初始群体。(3)适应度函数的确定 在遗传过程中，每一代都有许多不同的染色体，适应度的大小将决定都有哪些

13、染色体遗传到下一代。本文采用的适应度函数是式(12)，适应度值越大，则越接近最优解。本文在前面已经介绍过，式(12)已经由递推算法对其进行了优化，其计算复杂度由O(L6)降到了O(L3)，大大提高了运算速度，本文在计算适应度值时，也是使用递推算法进行计算的。(4)选择机制本文采用的选择机制是赌盘法选择机制。将每个个体按照适应度值的大小分布在读盘上，其所占的面积与其适应度的大小成正比。适应度大的个体其遗传到下一代的概率较大、个体数目较多，利于种群的优化；适应度小的个体被遗传到下一代的概率较小、个体数目较少，但可以保证群体的多样性以及适应度小的个体的某些优秀基因片段。(5)交叉算子 在三维Otsu

14、算法中，采用的是双点交叉，交叉概率为。在迭代初期交叉概率选的大一些，可以增强搜索能力；在迭代后期可以选的小一些，避免一些优秀的基因遭到破坏，并提高收敛速度。鉴于以上观点，本文采用的自适应交叉概率为： (14)式中代表了当前遗传代数，代表遗传终止代数， (15) (16)式(15)和式(16)中，表示最大适应度值，表示最小适应度值，表示平均适应度值，表示待交叉的两个个体之间的适应度较大者。(6)疫苗提取本文采取的疫苗提取的方法是从当代交叉后的群体中，以适应度最好的个体的全部基因的有效信息作为疫苗进行提取。由于免疫系统产生的抗体具有很强的针对性，所以适应度较高的抗体含有解决问题的特征信息。在改进后

15、的算法中，提取最优个体基因作为疫苗时采用疫苗更新，即在每一代个体进行交叉后，选出当代中适应度最好的个体的全部基因作为疫苗，进行接种，这样可使每一代接种的疫苗最优，还不影响算法的收敛性。(7)变异算子 为了增强算法的局部搜索能力，本文采用的变异算子为非均匀变异算子，随着进化代数的增加，变异基因位的取值范围越小、与原基因位的值越接近，这样可以保证在进化的后期保住最优个体的基因。本文选取的变异概率为： (17)其中：=0.1为最大变异概率，=0.002为最小变异概率，为要变异个体的适应度值，和分别表示当代中最大适应度和平均适应度。(8)疫苗接种 本文选取的疫苗接种方法是动态疫苗接种，即对当代群体中的

16、所有个体上的所有基因，一位一位的使用疫苗上相对应的基因位对其进行改变，并计算改变后的个体的适应度值；若某些个体上的基因与疫苗上相对应的基因相同，则该个体已经是最优个体，不再进行接种，直接遗传到下一代。在三维OTSU算法中，每个个体表示一个像素点，该像素点的灰度值、邻域均值、邻域中值为该个体上的基因，疫苗接种则是用适应度值最高的个体上的这三个值来依次改变每个个体上的每一位基因，将对其适应度值改变最大并有所提高的那一位基因用免疫疫苗所对应的基因将其覆盖，其它基因位保持不变。(9)免疫检测 对已经进行疫苗接种的个体进行检测，即计算其接种后的适应度值。若接种后的个体适应度值优于父代的适应度值，则它的子

17、孙代替父代进入下一代种群；若接种后其适应度仍不如父代，则该个体将被父代中所对应的个体取代。(10)终止准则的确定 最大遗传代数为40代；当相邻两代的平均适应度值的差在范围0.000，0.005之内时，则停止迭代。若不满足终止准则，则以新的群体为初始群体，转到步骤(3)继续进行计算；若满足，则输出结果，结果为适应度值最大的个体。该算法的流程图如图2所示。开始读取图像信息随机产生初始种群编码计算适应度值选择交叉种群更新(免疫检测)变异提取疫苗疫苗接种满足终止条件结束YN图2 基于IGA的三维Otsu改进算法流程图Fig.2 Flow chart of three- dimensional Otsu

18、 improved arithmetic based on IGA3 实验结果与分析仿真实验是在处理器为AMD2800+，1.6GHz，内存为1G的机器上进行的，仿真环境为MATLAB7.0。本次实验采用的是国际标准图像Lean图像，初始群体设置为30个个体，最大迭代次数为40代，实验结果如图3所示。(a)原始图像 (b)三维Otsu算法处理后的图像 (c)本文算法处理后的图像图3 Lean图分割结果图Fig.3 The result of Lean segmentation chart对比Lean图的分割结果可以看出，图3(c)较图3(b)的分割效果较好，传统三维Otsu阈值法求得的最佳阈值

19、为(138,125,126)，应用本文的算法求得的阈值为(138,125,127)；而且，在使用本文中的算法对Lean图像进行处理时，在迭代到23代时便得到了最佳阈值，时间为42.37S，相对于使用传统的三维Otsu算法处理Lean图像的140.39S，时间还不到其三分之一，在运算速度上有了大幅度的提高。实时性得到明显提高，分割效果也得到了改善。4 结束语 三维Otsu阈值分割算法的抗噪能力、分割的稳定性以及分割的效果相对于一维和二维Otsu算法，已经有了很大的提高，但三维Otsu算法的时间复杂度较高，实时性很差。虽然运用递推法已经将三维Otsu算法的时间复杂度从O(L6)降到了O(L3)，但对每一个候选阈值都计算一次的话，计算量非常大，仍然非常耗时。而基于免疫遗传算法改进的三维Otsu阈值分割算法，随机生成初始群体的个数为30，最大迭代次数是40，而且实验证明，往往不需要遗传到40代便可求出最佳结果，与传统的三维Ot