基于新遗传算法的Otsu图像阈值分割方法

王宏文，梁彦彦，王志华

（河北工业大学控制科学与工程学院，天津300130）

基于新遗传算法的Otsu图像阈值分割方法

王宏文，梁彦彦，王志华

（河北工业大学控制科学与工程学院，天津300130）

最大类间方差（Otsu）图像分割法是常用的一种基于统计原理的图像阈值分割方法。为了改善Otsu耗时较多、分割的精度低、易产生图像误分割等不足，将猴王遗传算法与Otsu算法结合，运用猴王遗传算法的原理，寻找图像灰度的最大类间方差，即最佳阈值。结果表明，结合后的方法不仅提高了图像的分割质量、缩短了运算时间，而且非常适合图像的实时处理。

图像处理；最佳阈值；猴王遗传算法；最大类间方差

引 言

图像分割是数字图像处理中的关键技术，它通常是为了简化或者改变图像的表示形式，使图像更容易理解和分析［1］。图像分割的准确性直接影响后续任务的有效性［2］，因此具有十分重要的理论和实际意义。常用的图像分割方法［3］有边缘检测法、区域跟踪法和阈值法等。在实际应用中，考虑到外界因素影响，阈值分割简单有效且性能稳定，成为图像分割中的常用技术。

阈值分割技术中最大类间方差法（Otsu算法）［4］是最常用的，它基于统计原理，通过选择一个阈值使得目标与背景类间方差最大，从而达到分离图像。但它比较耗时、分割的精度低、存在图像误分割等缺点。

猴王遗传算法是一种新颖的全局搜索遗传算法，具有程序直观易懂、参量少、计算量小、收敛速度快等特点［5］。将此算法与Otsu算法进行组合［6］来求解图像的分割阈值，可有效地缩短Otsu算法处理实时图像的时间，大大提高图像的分割质量。

1 Otsu算法

在1980年，Otsu算法被日本的大津展之提出来，Otsu算法是经典的、无参量、没有监督的一种自适应阈值选取的方法，它的原理是利用图像中的灰度直方图，确定目标与背景之间的最大方差值，即图像分割的阈值。

假设原始灰度图像大小为A×B，灰度级别为D，f（x，y）为图像中坐标为（x，y）的像素的灰度值，设Rij为图像中灰度级别为i、邻域平均灰度为j的像素点的个数，那么可以得到图像中灰度级别为i、邻域平均灰度为j的像素点在整个图像中的概率是：

图1为图像的2维直方图，是一个L×L的矩阵。设原始灰度图像的2维直方图被阈值（m，n）分成4个部分，背景（目标）内部的像素与邻域的平均灰度值接近。但是二者边界处的像素与邻域的平均灰度值差距较大，因此设区域0和1代表目标或背景，区域2和3代表边界点。所以应该在0和1区上用Otsu法确定最佳阈值。

Fig.1 2-D histogram

设图像中存在目标C0（ω0）和背景C1（ω1）两大类，那么二者出现的概率可以表示为：

则两类对应的均值向量分别为：

2维直方图上总的均值向量为：

由于区域2和3占少量，可假设2维直方图中区域2和3的分量和约为0（Pij≈0），

则定义一个目标和背景间的离散测度矩阵为：

以矩阵σ（m，n）的轨迹作为类间离散度的测度，有：

寻找最佳阈值向量（m′，n′），使得：

从上述分析可知，传统Otsu算法直接搜索使得（9）式运算量十分大、耗费时间长，难以应用到实时处理中，而且效率低、分割误差大。如果图像尺寸的增加，其运算量急剧增加。猴王遗传算法存在并行性和全局搜索的优点，加快获得最优阈值的速率，完善图像分割的效果。

2 基于猴王遗传算法的Otsu算法

2.1 猴王遗传算法

猴王遗传算法基本思想是：首先对种群中的各点按适应度函数值进行升序排列，排在前面的视为猴王点，然后和少部分较优点一起直接复制到下代种群；接着引入部分变异染色体来更换其中的较劣点；然后让最优点依次与种群中的其它点通过一定的概率，进行交叉变异，得到符合约束条件的新点。将这些点依次加入下一代种群，直到下一代种群中的数目达到设想规模。重复以上过程，达到最终预想结果［7］。与传统遗传算法［8-9］相比，猴王遗传算法［10］融合交叉和变异遗传运算，可以各代最优点（猴王点）为核心展开遗传计算，迅速提高收敛速度和收敛概率。可简述如下。

（1）初始化：搜索空间内随机产生L个个体，将其函数值做升序排列，确定猴王点。将排在后面的Im个个体用搜索空间内随机产生的同样数目的个体置换。令初始进化代数为0。

（2）复制：从当前群体中复制前面In个个体直接进入新一代群体。

（3）交叉变异遗传：通过猴王点交叉再产生LIn个新个体。如此产生新一代群体。

（4）排序新一代群体并引进随机个体：同步骤（1）。此时令进化代数＝进化代数＋1。新猴王点确定。

（5）达到终止代数或获得满意解则过程结束，否则转步骤（2）。

2.2 基于猴王遗传算法的阈值寻优步骤和流程图

步骤简述如下。（1）初始化。在MATLAB7.1环境下对20幅256pixel×256pixel原始灰度图像进行阈值选取仿真，设初始种群L＝20，初始代数＝0，最大进行化代数100，随机个体占比Rm＝0.4，复制率Rn＝0.08，随机数Rd＝0.8∈（0，1），调整系数α＝3，交叉概率0.7，变异概率0.3。

（2）计算初始个体灰度的类间方差。若要分割越准确，目标和背景的方差就要越大，所以用图像灰度的类间方差为适应度函数。如果个体的适应度值越大，表明其性能越好。适应度函数如下：

式中，λ1（m）为大于m的灰度像素数，λ2（m）为小于m的灰度像素数，v2（m）为大于m的平均灰度值，v1（m）表示小于m的平均灰度值。

（3）排序和替换。将计算出来的每个个体（设个体为Qi，i＝1，2，…，L）适应度进行升序排列，即有f（Q1′）≤f（Q2′）≤…≤f（QL′）（i＝1，2，…，L），找出猴王点Q1′。然后根据随机个体占比Rm，用随机生成的同样规模的新个体替换Im（Im＝round（Rm·L），round（x）表示与x距离最小的整数）之后的个体，组成新的种群。

（4）复制、产生新个体。根据复制率Rn，从当前群体中复制前面In＝round（Rn·L）个个体直接进入新一代群体。

（5）交叉变异。将猴王点与In之后的个体进行交叉，然后产生L－In个新个体。其中：

若（12）式中的Qi越界，则重新用（11）式反复计算，直到Qi在搜索范围内。在一定的概率下选取个体向量的元素进行变异。

Fig.2 Flow chart

（6）计算新一代种群个体灰度的类间方差（见步骤（2））。若连续多代种群适应度都没有任何改变，或已经达到最大进化代数，停止寻优操作，这时得到的最高适应度值就是图像分割阈值。否则返回步骤（2）。

流程图见图2。

3 仿真结果及分析

图3为原图，图4为传统的Otsu算法的分割效果图，图5为本文中算法的分割效果图，表1为本文中的算法与传统的Otsu算法的性能表（只列举了其中10幅图像的仿真结果）。

Fig.3 Original illustration

Fig.4 Segmentation effect of traditional Ostu algorithm

Table 1 The performance of two algorithms

对比上述3幅图像可见，基于猴王遗传算法的Otsu图像分割方法明显优于传统的Otsu图像分割方法。图像分割后边缘轮廓的清晰度提高，目标边缘的范围增大，轮廓清晰度也瞬间提高，整个图像也更清楚，而且图像的失真率大幅度减小。通过表1可以看出，达到最大阈值的时间明显缩短，传统算法取得最优阈值的平均时间为7.825ms，新算法平均时间为2.138ms。传统算法平均最优阈值约为116，新算法平均最优阈值约为109。从而明显弥补单独使用Otsu算法的不足，成为一种较理想的图像实时阈值分割方法。

4 结 论

图像分割在近代的应用领域已取得了重大的成果和深远的影响，如生物医学工程、航空航天、工业检测、机器人视觉、公安司法等。仿真实验结果表明，将本文中的算法对比传统Otsu图像分割算法，前者能够更快速、更准确地找到图像的全局最优分割阈值，大大缩短了最优阈值搜索时间，有利于图像的实时处理，将具有广泛的应用前景。

［1］ YANG H，QU X J.Survey of image segmentationmethod［J］.Computer Development and Applications，2005，18（3）：21-23（in Chinese）.

［2］ LIU JH，WANG JW.research on contour correction in medical CT image segmentation［J］.Journal of Computers，2012，7（3）：762-767.

［3］ YANG H Y.Application research on image segmentation method［J］.Computer Simulation，2012，29（2）：229-232（in Chinese）.

［4］ HAN C Y，KONG J.An improved image segmentation algorithm based on Otsu method［J］.Computer Simulation，2011，28（6）：262-265（in Chinese）.

［5］ WEIZh Ch，ZHOU J L，HANG L，et al.A study on image segmentation by a new adaptive algorithm［J］.Journal of Image and Graphics，2000，5（3）：216-220（in Chinese）.

［6］ XU Y F.Image segmentation based on the genetic fuzzy C-mean algorithm［J］.Journal of Northwestern Polytechnical University，2002，20（4）：549-553（in Chinese）.

［7］ LU B B，JIA Zh H，HE D，et al.A new FCM algorithm based on monkey-king genetic algorithm for remote sensing image segmengtation［J］.Laser Journal，2010，31（6）：15-17（in Chinese）.

［8］ LIY Zh，LIU H X，ZHANG Sh.Improvingmonkey-king genetic algorithm［J］.Journal of Nanjing Normal University（Engineering and Technology Edition），2004，4（3）：53-56（in Chinese）.

［9］ JIN J，SU Y.An improved adaptive genetic algorithm［J］.Computer Engineering and Applications，2005，18（2）：64-69（in Chinese）.

［10］ SHI B，TONG X N.Dual-threshold image segmentation method based on parallel genetic algorithms［J］.Microcomputer Information，2009，25（1）：304-306（in Chinese）.

Otsu image threshold segmentation method based on new genetic algorithm

WANG Hongwen，LIANG Yanyan，WANG Zhihua
（School of Control Science and Engineering，Hebei University of Technology，Tianjin 300130，China）

Maximum between-class variance（Otsu）image segmentation method is a common image threshold segmentation method based on statistical theory，but Otsu image segmentation method has some disadvantages，such as more time-consuming，low segmentation accuracy and false image segmentation.Combining the principles ofmonkey king genetic algorithms，with Otsu algorithm，image gray，justas optimal threshold，was found.The results show that combined method not only improves the quality of image segmentation but also reduce the computation time.It is very suitable for real-time image processing.

image processing；optimal threshold；monkey king genetic algorithm；maximum between-class variance

TN919.73

A

10.7510／jgjs.issn.1001-3806.2014.03.017

1001-3806（2014）03-0364-04

王宏文（1957-），男，硕士，教授，主要从事现代传动控制系统与智能化工程装备的研究。

E-mail：wanghongwen＠hebut.edu.cn

2013-05-20；

2013-07-31