- 1 -
一种改进的基于 Otsu 理论的遗传算法在图像
分割中的应用
王爱云,陈湘涛
湖南大学计算机与通信学院，长沙(410082)
摘 要：火焰图像中，火焰和物料是需要研究的主要目标对象，即火焰图像的前景，而图像
的其它部分(如窑壁等)则为背景。为了辨识火焰和物料，需要将其与火焰图像的背景分离出
来，在此基础上进行进一步的处理和分析。火焰图像分割是利用计算机进行火焰图像的火焰
和物料区域(前景)识别和进一步处理的重要步骤。遗传算法作为一种求解问题的高效并行的
全局搜索方法,其主要特点是群体搜索策略和群体中个体之间的信息交换,它能在搜索过程
中自动获取和积累有关搜索空间的知识,自适应地控制搜索过程以求得最优解,从而可克服
Otsu 方法的不足,有利于计算机视觉的后续处理。针对标准遗传算法在利用 Otsu 理论求取
图像阈值时存在的收敛性问题，提出了一种自适应的遗传算法，采用动态地交叉概率和变异
概率，有效地解决了过早收敛和全局收敛性问题，实验证明，改进后的遗传算法在进行图像
分割时是有效和可行的。
关键词：Otsu 理论，交叉概率，变异概率
1. 引言
阈值选取是图像处理中的基本问题,直接影响计算机视觉的后续处理效果,国内外学者
针对这一课题进行了广泛深入的研究,提出了很多阈值选取方法。但这些方法在不同程度上
存在着执行效率低、易于陷入局部最优解等问题。Otsu 方法是利用图像中的灰度直方图,
以目标与背景之间的方差最大而动态的确定图像分割门限值,是经典的非参数、无监督自适
应阈值选取方法[1] 。它不需要其他先验知识,因而应用范围很广,至今仍是最常用的图像分
割方法之一。但是Otsu方法最佳阈值的求解是通过穷尽的搜索方法得到的。因此计算量很大,
此外既便是对单阈值的情况,准则函数也不一定是单峰的,所以类似于牛顿迭代法等经典优
化方法不适用于最佳阈值的求取。
遗传算法(Genetic Algorithm ,简称GA) 作为一种求解问题的高效并行的全局搜索方法,
其主要特点是群体搜索策略和群体中个体之间的信息交换,它能在搜索过程中自动获取和积
累有关搜索空间的知识,自适应地控制搜索过程以求得最优解,从而可克服Otsu方法的不足,
有利于计算机视觉的后续处理。本文在遗传算法与Otsu方法结合的基础上，对交叉概率和变
异概率上做了一些改进，有效地解决了遗传算法的早熟现象，将该算法用在某回转窑图像的
分割中，得到的结果与实际情况相吻合，具有指导意义。
2. 本文相关原理
Otsu 理论
Otsu 在 1979 年提出的最大类间方差法(也称为大津方法) 一直被认为是阈值自动选
取方法中的最优方法, 该方法计算简单, 在一定条件下不受图像对比度与亮度变化的影响,
因而在一些实时图像处理系统中得到了很广泛的应用[1] 。Otsu 法是在判决分析最小二乘法
原理的基础上推导得出的, 该法的基本思路是: 选取的最佳阈值应当使得不同类间分离性
最好[2] 。首先基于直方图得到各分割特性值的发生概率, 并以阈值变量将分割特征值分为
两类, 然后求出每一类的类内方差及类间方差, 选取使类间方差最大或类内方差最小的 T
- 2 -
作为最佳阈值。
设一幅图像的灰度值分为m(0,1…,m-1)个灰度级, 灰度值为i 的像素数为ni , 则总像素
数为
0
m
i
i
N n
=
=∑ ，对直方图归一化，其概率密度分布和图像的整体均值为：
/i ip n N= ， 0ip ≥ ，
1
0
1
m
i
i
p
−
=
=∑ ，
0
m
i
i
u ip
=
= ∑ (1)
假设两个阈值(T1，T2)把图像灰度值分为三类， 0c 、 1c 和 2c ，即它们分别对应灰度级
{0,1… 1t },{ 1t +1, 1t +2… 2t }和{ 2t +1, 2t +2…m },它们的发生概率和均值分别为：
1
0
0
T
i
i
w p
=
= ∑ ， 10 0
0
T
i
i
u ip w
=
=∑ (2)
2
1
1 1
T
i
i T
w p
= +
= ∑ ， 21 1
1 1
T
i
i T
u ip w
= +
= ∑ (3)
2
2 1
M
i
i T
w p
= +
= ∑ =1- 0w - 1w ， 2 2
2 1
m
i
i T
u ip w
= +
= ∑ =(u- 0w 0u - 1w 1u )/ 2w (4)
这样Otsu法求取阈值的公式为：
2 2 2
1 2 0 0 1 1 2 20 1 2
( , ) ( ) ( ) ( )
T T m
g t t Arg Max w u u w u u w u u
< < <
= − + − + − （5）
遗传算法的基本原理
遗传算法是 20 世纪 70 年代由 J . H. Holland 教授首先提出的,其思想源于生物进化论,对包
含可能解(个体) 的种群反复使用基于遗传学的操作,生成新的种群,同时搜索最优解,使问题
的解不断“进化”,以求得满足要求的最优解。问题越复杂,目标越不明确,采用 GA 的优越性
也越大,因此 GA 在优化计算、搜索和人工智能等方面有广泛的应用潜力,目前 GA 已经成为
一种具有高鲁棒性和自适应性的全局概率搜索算法。遗传算法的计算过程首先是将实际的优
化问题编码成符合串,也称码串、染色体。将实际问题的目标函数转变为染色体的适应函数,
然后在随机产生的一批初始染色体的基础上,根据各染色体的适应函数进行繁殖、交叉、变
异等遗传操作产生下一代染色体。遗传算法的基本思想是模拟自然选择和自然遗传过程中发
生的繁殖、交配和突变现象,由此构成了遗传算法的三个基本算子:复制、交叉和变异。
3. 基于 GA 的 Otsu 算法
由于最佳阈值的求解是通过穷尽的搜索方法得到的。因此计算量很大,很多人利用遗传
算法来求解这一问题。在在图像处理中应用标准遗传算法实现 Otsu 法的基本步骤如下:
步骤 1：确定群体大小、交叉率、变异率和迭代次数。
步骤 2：确定编码和解码规则，并采用(1)作为适应度函数。
步骤 3：随机产生初始化群体，对其解码，计算适应度函数。
步骤 4：进行选择、交叉、变异操作。
步骤 5：转(4)，直到超过最大迭代次数，输出最佳阈值。
但是这种标准的遗传算法在求解过程中存在收敛速度慢、迭代次数多、容易出现局部极
值点等不足之处，一些理论研究也证明标准遗传算法收敛不到全局最优状态[3],为此，我们对
- 3 -
该算法做了一些改进，以弥补标准遗传算法的不足之处。
4. 改进的 GA 阈值选取算法
由于标准的遗传算法采用固定的交叉概率和变异概率，容易产生早熟现象，且在优化时
不具有全局收敛性，针对以上问题，我们主要采用动态地交叉概率和变异概率。
自适应交叉算子
为了保证算法的全局收敛性，就要维持种群中个体的多样性，以避免有效基因丢失。为
了减少迭代次数，就要加快收敛速度，使种群较快地向最优状态转移，但这又会降低群体的
多样性，容易陷入局部极值点。可见，保持多样性和加快收敛速度是一对矛盾。我们知道，
标准遗传算法在进化过程中采用固定的交叉概率，交叉概率越大，新个体产生的速度就越快。
然而，交叉概率过大，遗传模式被破坏的可能性也越大，使得具有高适应度的个体结构很快
被破坏；如果交叉概率过小，会使搜索过程缓慢．因此，遗传算法在进化过程中不宜采用固
定的交叉概率，应该针对种群中的多样性，采用不同的交叉概率[4]。当群体中各个体的适应
度趋于一致或趋于局部最优时，使交叉概率Pc增大；当群体适应度比较分散时，使交叉概率
Pc 减小。同时，对于适应度高于群体平均适应度值的个体，对应较低的Pc，使该解得以保
护进入下一代，而低于群体平均适应度的个体，对应较高的Pc ，该解被淘汰。因此，自适
应的Pc能够提供相对某个解的最佳交叉概率，
m ax
1
m ax
2
,
,
c a vg
a vg
c a vg
f Fp k F f
f f
p k F f
−= ≥−
= <
⎧⎪⎨⎪⎩ （6）
其中， maxf 为群体中最大适应度的值， avgf 为每代群体的平均适应度值，F为两个交叉个体
中最大的适应度值， 1 20 ( ) 1k k≤ ≤ ，为常数。
在杂交过程中，首先对种群中个体进行随机配对，即由（4）得到的父代个体随机两两
配对成为N／2对双亲；其次，在配对个体中根据(12)式计算出交叉概率pc，并随机设定两个
交叉点进行交叉运算。两点交叉的破坏性可以促进解的空间搜索，而不是促进解过早收敛，
因此搜索更加健壮。交叉算子体现了基因材料交换和信息交换的思想，可以实现高效搜索，
是GA的主要算子。
自适应变异算子
变异算子可以增加新的搜索空间，扩大算法的搜索范围，更有可能找到全局最优解。但
搜索范围广会使收敛速度受到影响，因而设计自适应的变异操作非常重要。遗传算法在进化
过程中不宜采用固定的变异概率，应该针对种群的多样性，采用不同的变异概率。当群体中
各个体的适应度趋一致或趋于局部最优时，使变异概率pm增大；当群体适应度比较分散时，
使变异概率pm减小。同时，对于适应度高于群体平均适应度值的个体，对应较低的pm，使该
解得以保护进入下一代，而低于群体平均适应度的个体，对应较高的pm ，该解被淘汰。因
此，自适应的pm能够提供相对某个解的最佳变异概率。另外，传统的遗传算法和各种改进的
算法在进行变异操作时，都采用随机选取一位进行翻转变值的方法，不能有效提高二进制编
- 4 -
码的搜索性能及稳定性。本文采用多点变异，即根据个体的优劣情况决定其变异位数，适应
度低的个体变异多个基因，适应度高的个体则采用少位变异或不变异。这样可以形成多种变
异组合，扩大了搜索空间。在变异过程中，首先计算出每个个体的变异概率，
m a x
3
m a x
4
,
,
i
m i a vg
a vg
m i a vg
f fp k f f
f f
p k f f
−= ≥−
= <
⎧⎪⎨⎪⎩ （7）
其中， if 为要变异个体的适应度， max if f− 为个体适应度最大值之间的距离； 3 40 ( ) 1k k≤ ≤ ，
为常数。
其次，给出变异位数，
max
1
max min
*( )( )T iM f fM INT
f f
−= −
其中， TM 为常数（一般取染色体串长的 1/4 到 1/3，即 L*1/4<N<L*/3）； minf 为群体中最
小的适应度， max minf f− 为当代的适应度范围；然后，对每个要变异的个体进行变异操作．变
异算子可以避免种群在进化中失去一些有用的基因，保持群体中基因的多样性，是阻止 GA
早熟收敛的一种有效措施。
算法实现的具体步骤
步骤1：确定群体大小为20，最大繁殖代数为40，适应度函数为(1)。
步骤2：对图像进行编码，由于图像灰度值在0～255 之间,故将每个可能的灰度阈值编码为8
位由0 ,1 符合组成的二进制码。
步骤3：利用赌轮法，进行个体选择。
步骤4：利用动态地交叉概率和变异概率，对个体进行交叉和变异，产生新个体。
步骤5：转(4)，直到超过最大迭代次数，输出最佳阈值。
5. 实验结果分析
在实验中，使用了matlab语言，系统平台为windows xp系统，其内核为Pentium 4 ,
内存为 512M,为了验证算法的可行性和实用性，笔者对某回转窑厂的图像进行了分析，对图
像进行中值滤波后，在相同的硬件配置条件下应用单阀值（迭代阀值、Otsu 单阀值）和基
于遗传算法的 Otsu 双阈值法及本文提出的算法 Otsu 进行分割处理。各种分割结果如下图 4-8
所示。
- 5 -
（a）原始图像 (b) 迭代阈值分割结果 (c) Otsu 单阈值分割结果
(d)遗传算法分割结果 (e)改进的遗传算法的分割
图 1
图 1 中，（d）和（e）都能将火焰图像划分为 3 个区域：黑把子带、物料带和窑壁带,
能够给出更加详细的信息，因此其效果优于前面两种单阀值法。很明显看出。(e)图的分割
效果要明显优于(d)图，经过改进后的遗传算法求的阈值比传统的遗传算法要更加接近实际，
有效地解决了遗传算法的早熟问题。
表 1算法分割性能比较
算法类型
比较项目
Otsu 单阀值
迭代阀值
基于 GA 的 Otsu 算法
本文算法
分割计算时间(ms) 10 20
分割效果 一般 一般 较好 好
为比较集中算法的收敛速度，表1 给出了具体收敛时间数据,对于单阈值来说,消耗的时
间相对于双阈值来说要少一些,但是分割的效果没有双阈值好，使用传统的基于遗传算法的
Otsu 方法比本文提出的算法的时间要长，且分割效果没有比本文提出的算法更加符合实际。
由表中数据可以看出仿真时间和所预期的理论测试值十分接近,从而进一步从实践上验证了
以上理论和运算程序的正确性。阈值选取不仅提高了分割质量,而且缩短了寻优时间。
6. 结论
本文在传统的标准遗传算法和 Otsu 理论的基础上，提出了一种改进的遗传算法-自适应
遗传算法，该算法采用动态地交叉概率和变异概率，对回转窑图像进行分割，实验证明，该
方法能以较少的时间达到从背景图像分割出目标的目的，且分割效果与实际情况相吻合，具
有一定的指导意义。
- 6 -
参考文献
[1] 付忠良.图像阈值选取方法-Otsu 方法的推广[J].计算机应用,2000,20(5):37-39
[2] 陈冬岚，刘金南，余玲玲.几种图像分割阈值选取方法的比较与研究[J].机械制造与自动化，2003,(1):77-80
[3] 王小平,曹立明．遗传算法一理论、应用与软件实现[M].西安：西安交通大学出版社，2002.
[4] De Jong K A．Analysis of the Behavior of a Class of Genetic Adaptive Systems[M]．University of Michigan
Press，1975．
Application of an genetic algorithm based on Otsu theory
in the image segmentation
Wang Aiyun, Cheng Xiangtao
School of computer and communication, Hunan University,Changsha(410082)
Abstract
The flame and the materials are the main target in the flame image, in other words, It is the
prospect of flame images, and other parts of the image (such as the furnace wall, etc.) for the
background. In order to identify materials and flame, and the flame needs to be separated from the
image background ,on this basis for further processing and analysis. Flame image segmentation is
the use of computer images of fire and the flames of regional materials (prospects) to identify and
deal with a further important step. GA can solve the problem and as a high-performance parallel
global search methods, It is characterized by the search strategy group and the exchange of
information between the individual, it can automatically obtain the search process and the
accumulation of relevant Knowledge of the search space, the adaptive control of the search
process in order to achieve the optimal solution, which can overcome the lack of Otsu method is
conducive to the follow-up to deal with computer convergence problems in
application of the standard genetic algorithm and Otsu theory to obtain the image threshold were
discussed and the adaptive genetic algorithm was presented, which take the dynamic cross
probability and mutation probability, and it solves the premature convergence and the global
convergence. the results showed that the modified genetic algorithm is practical and efficient in
the image segmentation.
Keywords: Otsu theory, cross probability, mutation probability
