遗传算法新论文
学校代码 10126 学号 00708037 分 类 号 密级
本科毕业论文
学院、系 数学科学学院计算数学系
专业名称 信息与计算科学
年 级 2007级
学生姓名 刘家祥
指导教师 曹军
2011年 5月 20 日
内容摘要
图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。图像的分割是以灰度值作为分割的依据, 通过各个像素的灰度值和事先确定的阈值的比较来分割图像。如何确定最合适的阈值是处理好图像分割的关键, 这自然成为一直以来分割算法研究的焦点。
遗传算法是对生物进化论中自然选择和遗传学机理中生物进化过程的模拟来计算最优解的方法。遗传算法具有众多的优点, 如鲁棒性、并行性、自适应性和快速收敛, 可以应用在图像处理技术领域中图像分割技术来确定分割阈值。
本文主要介绍基于遗传算法的最小误差阈值法、最大类间方差法(Otsu 法)以及最佳直方图熵法(KSW 熵法) 等三种方法分割图像。
关键词:图像分割,遗传算法,阈值分割
Abstract
Image segmentation refers to the image into regions each with characteristics and goals of the technology to extract and process of interest. Segmentation is a segmentation based on gray value, gray value of each pixel through the predetermined threshold value and comparing the image segmentation. How to determine the most appropriate threshold is the key to handling image segmentation, which has naturally become the focus of segmentation algorithms.
Genetic algorithm is a biological theory of evolution and genetic mechanism of natural selection in biological evolution simulation method to calculate the optimal solution. Genetic algorithm has many advantages, such as robustness, parallel, adaptive, and fast convergence, can be used in the field of image processing image segmentation technique to determine the split threshold.
In this paper, genetic algorithm based on minimum error threshold, the largest class variance (Otsu method) and the best histogram entropy (KSW entropy method) are three ways to split the image.
Keywords : Image segmentation, genetic algorithms, threshold
目录
第一章 绪论 .................................................. - 1 -
第二章 遗传算法概述 ........................................ . - 2 -
2.1遗传算法的研究历史....................................... - 2 -
2.2生物背景................................................. - 2 -
2.3遗传算法的基本思想....................................... - 3 -
2.4遗传算法的几个概念....................................... - 4 -
2.4.1适应度函数 ......................................... - 4 -
2.4.2遗传算法最常用的算子 ............................... - 4 -
2.5遗传算法运算的基本流程................................... - 5 -
第三章 图像分割的现状 ........................................ - 7 -
3.1图像分割简介............................................. - 7 -
3.2图像分割方法............................................. - 8 -
3.2.1基于边缘检测的分割 ................................. - 8 -
3.2.2基于区域的分割 ..................................... - 8 -
3.2.3边缘与区域相结合的分割 ............................. - 9 -
3.3阈值选取................................................. - 9 -
第四章 基于遗传算法的图像阈值分割 ........................... - 10 -
4.1图像阈值................................................ - 10 -
4.2阈值分割的原理.......................................... - 10 -
4.3最小误差阈值法.......................................... - 11 -
4.3.1最小误差法图像阈值分割 ............................ - 11 -
4.3.2 利用遗传算法来改进最小误差法...................... - 12 -
4.4 最大类间方差法(Otsu 法) ............................... - 13 -
4.4.1最大类间方差法(Otsu 法)阈值分割 .................. - 13 -
4.4.2 Otsu阈值分割的遗传算法设计 ........................ - 15 -
4.5 KSW熵法................................................ - 17 -
4.5.1 KSW熵阈值分割 ................................... - 17 -
4.5.2 KSW 单阈值分割的遗传算法设计 . .................... - 18 -
4.5.3 KSW 双阈值分割的遗传算法设计 . .................... - 19 -
第五章 基于新的遗传算法的图像分割 ........................... - 25 -
5.1混沌遗传算法............................................ - 25 -
5.2量子遗传算法............................................ - 25 -
5.3免疫遗传算法............................................ - 25 - 结论 .......................................................... - 26 - 致谢 .......................................................... - 27 - 参考文献: ..................................................... - 28 -
基于遗传算法的图像阈值分割
第一章 绪论
图像分割是图像处理与计算机视觉的基本问题之一,是图像处理到图像分析的关键步骤。图像分割方法(包括阈值法、边缘检测法、区域跟踪法) 的研究始于上世纪50年代。随着越来越多人的研究,近年来涌现了许多新理论、新方法,但是没有一种方法能满足所有图像分割领域。
在众多的图像分割技术中,阈值化技术是基于区域的图像分割技术,是图像分割中最重要而有效的技术之一。阈值法是一种传统的图像分割方法,因其实现简单、计算量小、性能较稳定而成为图像分割中最基本和应用最广泛的分割技术。在实际应用中,分割是对图像进一步分析、识别的前提,分割的准确性将直接影
响后续任务的有效性。其中阈值的选取是图像阈值分割方法中的关键技术。
遗传算法(genetic algorithm,GA) 是基于进化论自然选择机制的、并行的、
统计的、随机化搜索方法。使用遗传算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基本思想早在20世纪60年代初期就由美国Michigan 大学的Holland 教授提出,其数学框架也于20世纪60年代中期形成。由于GA 的整体搜索策略和优化计算不依赖于梯度信息,所以它的应用范围非常广泛,尤其适合于处理传统方法难以解决的高度复杂的非线性问题。
在分割复杂的图像时,人们往往采用多参量进行信息融合,在多参量参与的最优值的求取过程中,优化计算是最重要的,把自然进化的特征应用到计算机算法中,将能解决很多困难。遗传算法的出现为解决这类问题提供了新而有效的方法,它不仅可以得到全局最优解,而且大量缩短了计算时间。在图像分割过程中,最关键的就是找到最优的阈值,遗传算法的整体搜索策略和优化搜索方法能够快速准确地得到基于成个灰度图像的阈值最优解。
第二章 遗传算法概述
1. 遗传算法的研究历史
遗传算法是演化计算的一个分枝,也是人工智能发展的一个重要领域。它是受达尔文进化理论的思想而激发的一种用进化思想来解决问题的方法。遗传算法研究的兴起是在80年代末和90年代初期,但它的历史起源可追溯至60年代初期。早期的研究大多以对自然系统的计算机模拟为主。如Fraser 的模拟研究,他提出了和现在的遗传算法十分相似的概念和思想;同时代,演化计算思想首先是由I.Rechenberg 于20世纪60年代在他的著作《演化策略》“Evolution strategies”() 一书中提出来的,然后一些研究者发展了他们的思想。Holland 和DeJong 的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏。其中,Holland 于1975年出版的著名著作《自然系统和人工系统的适配》系统地阐述了遗传算法的基本理论和方法,并提出了对遗传算法的理论研究和发展极为重要的模式理论。这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。
同年,DeJong 的重要论文《遗传自适应系统的行为分析》将Holland 的模式理论与他的计算实验结合起来,并提出了诸如代沟等新的遗传操作技术。可以认为,DeJong 所作的研究工作是遗传算法发展过程中的一个里程碑。
进入80年代,遗传算法迎来了兴盛发展时期,无论是理论研究还是应用研究都成了十分热门的课题。此后至今遗传算法的应用领域不断扩大,遗传算法应用研究已从初期的组合优化求解拓展到了许多更新,更工程化的应用方面。
2. 生物背景
达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为,生物要生存下去,就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中,具有有利变异的个体容易存活下来,并且有更多的机会将有利变异传给后代;具有不利变异的个体就
容易被淘汰,产生后代的机会也少得多。因此,凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存,不适者淘汰的过程叫做自然选择。它表明,遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化,是和遗传和变异生命现象分不开的。正是生物的这种遗传特性,使生物界的物种能够保持相对的稳定;而生物的变异特性,使生物个体产生新的性状,以致于形成新的物种,推动了生物的进化和发展。
遗传算法正是模拟达尔文的这种遗传选择和自然淘汰的生物进化过程的计算模型,是一种具有“生存+检测”的迭代过程的搜索算法。它以一种群体中的所有个体为对象,并利用随机化技术指导对一个被编码的参数空间进行高效搜索. 其中,选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容;作为一种新的全局优化搜家算法,遗传算法以其简单通用、稳定性强、适于并行处理以及高效、实用等显著特点,在各个领域得到了广泛应用,取得了良好效果,并逐渐成为重要的智能算法之一。
3. 遗传算法的基本思想
生物在自然界中的生存繁衍,显示出了其对自然环境的自适应能力。受其启发,人们致力于对生物各种生存特性的机理研究和行为模拟,为人工自适应系统的设计和开发提供了广阔的前景。遗传算法就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟,遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。
遗传算法受到达尔文进化论的影响很大。在遗传算法中,问题的解是逐渐进化得到的。遗传算法的计算从一组可能解开始,这组解被称作种群(Population ),在算法中被表示成基因。我们又把种群中的解拿出来去构成新的一个种群,这是因为我们期望新的种群要比旧的种群要好。当然,新的种群中的解要有这样的性质,就必须按照它的适应度去选择,适应度越高,它参与构造新的种群的机会就
越大。这个过程一次又一次的重复,一直到我们所给的约束条件满足为止,比如说种群中解得个数或者种群的良好程度。
4.遗传算法的几个概念
4.1 适应度函数
在遗传算法中使用适应度来度量群体中各个个体在优化计算中有可能达到或接近或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率 就较大;而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应 度的函数称为适应度函数。
评价个体适应度的过程为:
(1)对个体编码串进行解码处理后,可得到个体的表现型;
(2)由个体的表现型可计算出对应个体的目标函数值;
(3)根据最优化问题的类型,由目标函数按一定的转换规则求出个体的适应度。
4.2 遗传算法最常用的算子
(1)选择算子:选择算子从群体中按某一概率成对选择个体,某个体xi 被选择的概率Pi 与其适应度值成正比。
选择算子有很多,最常用的是比例选择算子。它是把当前的个体按与适应度成正比的概率复制到新的群体中去。比例选择实际上也是一种赌盘选择,其基本步骤为:
①先计算出群体中所有个体的适应度的总和;
②其次计算出每个个体的相对适应度的大小,它即为各个个体被遗传到 下一代群体中的概率;
③最后再使用模拟赌盘操作(即O 和1之间的随机数) 来确定各个个体被选中
的次数。
(2)交叉算子:交叉算子将被选中的2个个体的基因链按概率进行交叉,生成2个新的个体, 交叉位置是随机的。
(3)变异算子:变异算子将新个体的基因链的各位按概率进行变异,对二值基因链来说即是取反。
在遗传算法中使用变异算子主要由以下两个目的:
①改善遗传算法的局部搜索能力;
②维持群体的多样性,防止出现早熟现象。
5. 遗传算法运算的基本流程
(1)针对图像分割编写代码:遗传算法一般不直接处理空间的参数而是集进行编码, 即用0和1构成的字符串形成矩阵。
(2)随机初始化像素群体X(0):=( x1,x 2 ,„,x n ):遗传算法从这些群体出发,
模拟生物进化过程进行选择, 最后得出需要的个体集合, 满足优化搜索的要求。
(3)对当前像素群体X(t)中每个个体x i 计算其适应度F(xi ) ,适应度表示了该
像素的灰度值:遗传算法不涉及问题的具体领域, 只需依据适应度函数控制像素变化。根据适应度函数对每个像素计算其适应度,为选择提供依据。设计适应度函数的方法是把问题的目标函数转换成合适的适应度函数和辅助函数。
(4)应用选择算子产生Xr(t)。
(5)对Xr(t)应用其他的算子, 产生新一代像素群体X(t+1),应用其他的算子可以扩展图片像素的覆盖面,体现整体计算的策略。
(6)选择:这是是遗传算法的关键,它参照了适者生存的理论。
(7)变异:模拟了生物的基因突变现象。对像素进行重新评价、选择如此循环往复,使图像中目标物体平均适应度不断提高直到上限则迭代过程收敛,算法结束。
GA 的计算过程流程图如下:
第三章 图像分割的现状
1. 图像分割简介
图像分割是一种重要的图像技术,它不仅得到人们广泛的重视和研究,也在实际中得到大量的应用。图像分割在不同领域有时也用其他名称,如目标轮廓 (Object Delineation ) 技术,阈值化(Thresholding ) 技术,图像区分或求差(Image discrimination ) 技术,目标检测(Target Detection ) 技术,目标识别 (Target recognition ) 技术,目标跟踪(Target tracking) 技术等。这些技术本身或核心实际上也就是图像分割技术。图像技术在广义上是指与各种图像有关技术的总称。图像技术种类很多,跨度很大,但可以将它们归在一个整体框架—图像工程之下。图像工程是一个对整个图像领域进行研究的新学科。它的内容十分丰富,根据抽象程度和研究方法等的不同可分为三个各有特点的层次:图像处理、图像分析和图像理解(如下图所示
)
图像处理着重强调在图像之间进行变换以改善图像的视觉效果。图像分析则主要是对图像中感兴趣的目标进行检测和测量,以获得它们的客观信息从而建立对图像的描述。图像理解的重点是在图像分析的基础上,进一步研究图像中各目标的性质和它们之间的相互关系,并得出对原始成像客观场景的解释,从而指导和规划行动。图像处理、图像分析和图像理解具有不同的操作对象。图像处理是比较低层的操作,它主要在图像象素级上进行处理。图像分析则进入了中层,它侧重于对象素集合—目标的表达、测量和描述。图像理解主要是高层操作,基本
上是对从描述中抽象出来的数据符号进行处理。
在对图像的研究和应用中,人们往往对图像中的某些部分感兴趣。这些部分常称为目标或前景(其他部分为背景) ,它们一般对应图像中特定的、具有独特性质的区域。为了辨识和分析目标,需要将它们分离提取出来。在此基础上才有可能对目标进一步利用。图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。这里特性可以是象素的灰度、颜色、纹理等,预先定义的目标可以对应单个区域,也可以对应多个区域。
2. 图像分割方法
图像分割方法有很多,常见的分割包括基于边缘检测的分割、基于区域的分割、边缘与区域相结合的分割等。
2.1基于边缘检测的分割
基本思想是先检测图像中的边缘点,再按一定策略连接成轮廓,从而构成分割区域。其难点在于边缘检测时抗噪性和检测精度的矛盾。若提高检测精度则噪声产生的伪边缘会导致不合理的轮廓;若提高抗噪性,则会产生轮廓漏检和位置偏差。为此,人们提出各种多尺度边缘检测方法,根据实际问题设计多尺度边缘信息的结合方案,以较好地兼顾抗噪性和检测精度,但仍不能从根本上克服此矛盾。
2.2 基于区域的分割
基本思想是根据图像数据的特征将图像空间划分为不同区域。常用的特征包括:直接来自原始图像的灰度或彩色特征,由原始灰度或彩色值变换得到的特征。方法有阈值法、区域生长法、聚类法、松弛法等。阈值法是通过设定不同的特征值,将象素点分为若干类。其难点在于阈值的设定方法。对传统阈值法的改进包括局部阈值法、模糊阈值法、随机阈值法以及引入新的理论来优选阈值;聚类法是在特征空间对象素进行聚类。它包括硬聚类、概率聚类和模糊聚类等。聚类准则是聚类分割的关键;松弛法是一种动态调优的标号方法。它包括概率松弛、模糊松弛等。其关键在于标号相容模型和迭代方法的收敛性。
2.3 边缘与区域相结合的分割
边缘检测能够获得灰度或彩色值的局部变化强度,而区域分割能够检测特征的相似性与均匀性。边缘与区域组合分割的主要思想是结合二者的优点,通过边缘点的限制,避免区域的过分割;同时通过区域分割补充漏检的边缘,使轮廓更加完整。
3. 阈值选取
图像分割在图像识别和分析中具有重要意义,阈值选取是其关键技术,国内外学者从不同角度提出了许多种阈值选择的方法。
目前公认较好的几种方法如下所示:
(1)最佳熵法。最佳熵法对不同目标大小和信噪比的图像均产生很好的分割效果,且受目标大小的影响小,可用于小目标分割,但由于最大嫡法涉及对数运算,运算速度慢,不能用于实时处理。
(2)最大类间方差法。最大类间方差法对噪声和目标大小十分敏感,它仅对类间方差为单峰的图像产生较好的分割效果。当目标与背景的大小比例悬殊时,类间方差函数可能呈现双峰或多峰,此时用最大类间方差法选取的全局最大值并不一定是正确阈值,此方法失效。Reddi 等提出了一种快速算法,提高了运算速度,但并没有解决准则函数极大值不唯一的缺陷。
(3)最小误差法。最小误差法受目标大小和噪声影响小,对小目标图像仍具。有较好的分割效果。但运算量较大,不利于实时处理。
第四章 基于遗传算法的图像阈值分割
1. 图像阈值
一幅图像通常包括目标物体、背景高斯噪声、运动模糊等, 由于目标物体和背景的灰度有较大差异, 和噪声产生的麻点的灰度值相差更多, 要从多值的灰度图像中提取目标物体, 常用的方法就是设定某一阈值, 将图像像素分成2大部分:大于阈值的像素和小于阈值的像素即灰度图像的二值化。二值化处理主要功能就是把目标物体和背景灰度差异较大的图像分成2个部分。二值化是数字图像处理中一项最简单的变换方法, 通过采用固定阈值、双固定阈值等不同算法, 把一幅灰度图变成二值图像, 将所需的目标物体从复杂的图像背景中脱离出来。具体的操作过程是先由通过算法找到一个合适阈值, 要求是阈值处于目标物体阈值和背景阈值之间。若图像中的像素灰度值小于该阈值, 则将该像素的灰度值设置为0或255,若图像中的像素灰度值大于该阈值, 则将该像素的灰度值设置为255或0。也就是说通过一个以阈值灰度值为跳变点的阶跃函数来实现图像处理。
固定阈值法:固定阈值法就是为灰度图像设定一个阈值, 把灰度值小于给定阈值的像素置为0(或者255) ,大于阈值的像素置为255(或者0) ,从而实现灰度图像到二值图像的变换。
双固定阈值法:双固定阈值法预先设置2个阈值, 当对图像进行处理时, 如果某个像素的灰度值在两者之间时置0(或者255) ;其余情况则置255(或者置0) 。应当根据具体情况选择双固定阈值法改变图像灰度值的方向。
2. 阈值分割的原理
对灰度图像的阈值分割就是先确定一个处于图像灰度取值范围之中的灰度阈值,然后将图像中各个象素的灰度值都与这个阈值相比较,并根据比较结果将对应的象素分割为两类:象素的灰度值大于阈值的为一类,象素的灰度值小于阈值的为一类。这两类一般分属于图像中的两类区域:目标和背景。这样就可以将 目标从背景中分离出来。由此可见,阈值化分割算法主要有两个步骤:
(1)确定需要的分割阈值;
(2)将阈值与象素比较以划分象素。
以上步骤中,确定阈值是分割的关键。确定阈值后就可以将阈值与象素值比较以对图像进行分割。分割的结果直接给出图像区域。假设一幅原始图像为f(x,y),则分割后的图像g(x,y)可定义为:
⎧1g (x , y ) =⎨⎩0f (x , y ) >T f (x , y ) ≤T
其中,T 为阈值。这样得到的g(x,y)是一幅二值图像,它相当于把原始图像用空间占有数组来进行表达。
3. 最小误差阈值法
3.1 最小误差法图像阈值分割
最小误差法由Kittler 和Illingworth 于1986年提出, 该分割方法受目标大小和噪声影响小, 能较好地克服算法的不足, 是一种理论严密, 效果较佳的图像阈值分割方法。定义如下:
假设h(i)为图像的各级灰度值,0≤i ≤255, 准则函数:
f (t ) =1+2[P 0(t )ln σ0(t ) +P 1(t )ln σ1(t )]-2[P 0(t )ln P 0(t ) +P 1(t )ln P 1(t )]
式中:
p 0(t ) =∑h (i )
i =0
t t ,p 2(t ) =i =t +1∑h (i ) L -1; 2
σ02=∑[i -μ(t )]h (i ) 20
i =0
p 0(t ) 2σ2=i =t +1∑[i -μ(t )]h (i ) 2L -1
,p 2(t ) ;
μ0(t ) =∑h (i ) i *i =0t
p 0(t ) ,μ2(t ) =i =t +1∑h (i ) i *L -1
p 1(t ) ;
则最佳阈值为: t=ArgminF(t), 其中:
, ... -, ,p 0(t ) 、p 1(t ) 分别为灰度值在0~t 和t ~( t ∈(0, 1, 2L L- 1) 之间的
像素数;
22σσ02 、分别为灰度值在0~t 和t ~( L- 1)之间的方差;
μ0(t ) 、μ1(t ) 分别为灰度值在0~t 和t ~( L- 1)之间
的平均灰度值。
3.2 利用遗传算法来改进最小误差法
由于最小误差法选取阈值的过程实质上是一种寻求最优解的过程,故可利用GA 所具有的快速寻优的特点对其进行优化,以达到提高效率的目的。其具体做法如下:
(1)编码和适应度函数的确定
对于具有256级灰度的图像,其侯选阈值在0~255之间,故可用一个8位二进制码进行编码,即把O ~255之间的值编码成00000000~11111111之间的一个码。
至于适应度函数,可用最小误差法的准则函数,即:
f (t ) =1+2[P 0(t )ln σ0(t ) +P 1(t )ln σ1(t )]-2[P 0(t )ln P 0(t ) +P 1(t )ln P 1(t )]
为了正确计算不同情况下各个个体的遗传概率,要求所有个体的适应度必须为正数或零,不能为负数。为此,采用一种变换方法:
⎧C max -f (t ) F (t ) =⎨0⎩f (t )
式中C max 为我们预先指定的一个较大的数。
(2)控制参数的确定
GA 的控制参数主要包括群体规模、变异率和交换率等。这些参数的选择尚处于研究阶段,目前参数的选择主要靠实验确定,群体规模影响到遗传算法的最终性能和效率。若规模太小会过早收敛到局部最优解,然而群体规模太大,每一代需要的计算量也越多,这有可能导致无法接受的慢收敛率。
交叉率控制交叉算子应用的频率,交叉率越高,群体中个体的更新就越快,如果交叉率过高,相对选择能够产生的改进而言,高性能的个体被破坏的要更快。如果交叉率过低,搜索会因为太小的探查率而导致停滞不前。
变异是增加群体多样性的搜索算子,一个很小的变异率足以防止整个群体中任一给定位保持永远收敛到单一的值。
(3)选择方法的确定
采用比例选择的方法,其具体执行过程如下:
①先计算出群体中所有个体的适应度总和。
②其次计算出每个个体的相对适应度的大小,它即为每个个体被遗传到下 一代群体中的概率。
③最后再使用模拟赌盘操作(即O 到1之间的随机数) 来确定各个个体被选 中的次数。
(4)停止准则的确定
根据最大迭代次数G 和当前群体的平均适应度与上一代群体的平均适应度 值的差是否小于某一个较小的常数来确定是否终止运算。即当迭代次数大于G 或平均适应度的差小于某一个较小的常数时,终止运算。
4. 最大类间方差法(Otsu 法)
4.1最大类间方差法(Otsu 法)阈值分割
Otsu 提出的通过求类间方差最大来选择阈值的方法是一种较为常见的方法。 它的基本原理为用最佳阈值将图像的灰度直方图分割成两部分,使两部分的类间方差取最大值、即分离性最大。
设图像的灰度范围为{o,1,„,l 一l},选择阈值t 将图像划分为两类:C 0:{o,1,„,t},C 1{t+1,t+2,„,l —1}。对图像直方图归一化,且有概率分
布:
p i =n i /N , p i ≥0, ∑p i =1,
i =0l -1
其中N 为总像素数,n i 为灰度为i 的像素数。C 0类和C 1类的类出现概率及均
值分别为:
w 0=P r (C 0) =∑p i =w (t ) ,
i =0
t -1t
w 1=P r (C 1) =
i =t +1∑p i =1-w (t ) 。
令μ0=∑i =0ip i /w 0=μ(t ) /w (t ) ,μ1=∑i =t +1ip i /w 1=
t t l -1t l -1μT -μ(t ) 1-w (t ) ,其中w (t ) =∑i =0p i ,μ(t ) =∑i =0ip i ,μT =∑i =0ip i 。
可以验证有下式成立:
w 0μ0+w 1μ1=μT ,w 0+w 1=1。
2=∑i =0(i -μ0) 2p i /w 0,σ12=∑i =t +1(i -μ1) 2p i /w 1。C 0和C 1类的方差分别为σ0t t -1
22两类的类间方差σB 为σB =w 0(μ0-μT ) 2+w 1(μ1-μT ) 2=w 0w 1(μ1-μ0) 2。
最佳阈值t *应使类间方差最大,即
2t *=Arg Max σB 0≤t ≤l -1
Otsu 最多用于双阈值分割,这是因为当阈值很多时,基于一维直方图的类间方差公式不再适用。将Otsu 法用于双阈值分割时,最佳阈值t *应使三类间方差最大,即
2σB =w 0(μ0-μT ) 2+w 1(μ1-μT ) 2+w 2(μ2-μT ) 2
4.2 Otsu 阈值分割的遗传算法设计
(1)染色体的编码
通过编码将决策变量表示成串结构数据, 采用最常用的二进制编码方案。由于图像灰度值在0~255之间,故可用00000000~11111111之间的一个八位二进制代码表示一个分割阈值。对于一维Otsu 分割, 染色体串长为10, 其中前八位为阈值的二进制编码,后两位为阈值真值和适应度。
(2)初始群体
采用逐个产生初始群体的方法,若产生一个不满足约束条件,则被淘汰,重新产生。直到产生popsize 个满足约束条件的初始群体为止。一维Otsu 法分割设置初始群体的个数为20。
(3)解码 对二进制染色体数组采用公式k =U min +(∑b i ∙2l -1) ∙
i =1l U max -U min ,U min =0,l -12
U max =255,某一个体K 的二进制编码为bb l l -1b l -2Λb 2b 1。
(4)适应度函数
遗传算法的执行过程中,每一代有许多不同的染色体同时存在,确定这些染色体中哪些遗传到下一代,是根据群体中各个个体的适应度大小决定的。适应度的大小是通过计算适应度函数的值,这个值称为适应度。适应度函数通常是根据 目标函数确定的,一维Otsu 法的类间方差函数就是所求目标函数,由于所求问题为最大值且为非负因此适应度函数可以直接等于目标函数。
(5)遗传算子和参数设定
主要的遗传算子有选择、交叉、变异3种。
①选择算子:先采用最优保存策略,然后采用赌轮法(比例选择)。
②交叉算子:它是遗传算法区别于其它进化算法的重要特征,是产生新个体的主要方法。交叉算子的设计和实现与所研究的问题密切相关,它决定了遗传算法的全局搜索能力。一般要求它既不要太多地破坏个体编码串中优良模式,又要能够有效地产生出一些较好的新个体模式。对一维Otsu 阈值分割法的染色体采用单点交叉的方式。分别在变量s ,t 的编码段内设定一个交叉点。
③变异算子:只是产生新个体的辅助方法,但它决定了遗传算法的局部搜索能力。在反复的试验时,发现基本位变异对结果的影响微乎其微,而一旦增大变异概率,算法又近似于随机搜索算法。所以采用下面的变异策略,把进化过程分为初期、中期和后期三个阶段,分别采用不同的变异方法。进化初期以小的概率P m 1在稍大的范围内变异,维持多样性而又不破坏好的模式;进化中期以稍大的
概率P m 2在中等的范围内变异,算法开始收敛;进化后期以大的概率P m 3在小的范围内变异, 增加局部搜索能力。
(6)终止准则
设定停机准则为在达到最大进化代数50代之前,若当前群体的平均适应度值与上一代群体的平均适应度值与上一代群体的平均适应度的比值范围 为[1.000,1.005],则跳出循环。
(7)结果处理
由于在实际图像处理中。GA 寻优的解可能是最优解也可能是准最优解(即与最优解相差10%左右)。对于一个有256级灰度的图像,其准最优阈值与最优阈值的差值一般在25.5左右。为了适应不同图像的阈值选取,设定一个波动阈值A=25,在求出的阈值k 的基础上, 在范围[k-A,k+A]内进行局部搜索, 以求得最佳阈值。
下面是原图及用最大类间方差法(Otsu ) 分割的图像对比:
原图 最大类间方差法(otsu )
5. KSW 熵法
5.1 KSW 熵阈值分割
将信息论中shannon 熵概念用于图像分割时, 测量图像灰度直方图的熵,由此找出最佳阈值,其出发点是使图像中目标与背景分布的信息量最大。
根据shannon 熵的概念,对于灰度范围{0,l„,l —l}的图像直方图,其熵测为:
H T =-∑p i ln p i
i =0l -1
其中p i 为第i 个灰度出现的概率。设阈值t 将图像划分为目标与背景两类, 责令p t =∑i =0p i ,H t =-∑i =0p i ln p i 。
由阈值t 分为A,B 两类后,两类的概率分布分别为p 0P t ,p 1P t ,p t P t ;
t
t
p t +1(1-P t ) ,p t +2(1-P t ) ,p l -1(1-P t ) ,与每个分布有关的熵分别为H A (t ) 和H B (t ) 。
H A (t ) =-∑
i =0
l -1
t
p i p l -1H T
, ln =ln P +T
P P P T T t
H B (t ) =-∑
p i p H T -H t
。 ln i =ln (1-P +)T
1-P 1-P t i =t +11-P T T
图像的总熵H(t)为H A (t ) 和H B (t ) 之和,即H (t ) =ln P t (1-P t ) +
H t H T -H t
+
P t 1-P t
最佳阅值t *为使总熵取最大值,即t *=Arg Max H (t ) 。
0≤t ≤l -1
KSW 最佳熵自动门限法适合于多阈值(设为k 个阈值) 分割。此时,
H (S 1, S 2,..., S k ) =ln(∑p i ) +ln(
i =1S 1
i =S 1+1
∑
S 2
p i ) +... +ln(
i =S k +1
∑
n
p i )
-
∑i =1p i ln p i
∑
S 1i =1
S 1
p i
∑-... -
∑
n
i =S k +1
n
p i ln p i
p i
i =S k +1
式中S 1,S 2,...,S k 是分割阈值且有S 1
**
S 1*, S 2,..., S k =Arg
0≤S 1
Max
H (S 1, S 2,..., S k )
特别地,对于阈值情况即为S 1
H (S 1, S 2) =ln(∑p i ) +ln(
i =1S 1
i =S 1+1
∑
S 2
p i ) +ln(
i =S 2+1
∑
n
p i )
∑p ln p -
∑p
i =1
i S 1i =1
i
S 1
i
-
∑i =S +1p i ln p i
1
S 2
∑
S 2i =S 1+1
p i
∑-
∑
n
i =S 2+1
n
p i ln p i
p i
i =S 2+1
最佳阈值S 1*,S 2*为使总熵取最大值,即
*
S 1*, S 2=Arg Max H (S 1, S 2)
0≤S 1
5.2. KSW 单阈值分割的遗传算法设计
编码:由于图像灰度值在0—255之间,故将各个染色体编码为8位二进制码,它代表某个分割阈值。初始代人口的值为随机产生的,其相应的适应度值也各有高低。
人口模型:若人口数过多,则每一代适应度值的计算量大,因此人口数设置应该合理。在此,设置人口数为l0,最大繁殖代数为50。
解码:对二进制染色体数组解码为0~255之间的值,以求其适应度值。 适应度函数:采用(1)式为适应度值函数。同时采取对适应度函数的线性定标。
选择:根据遗传算法的收敛定理,先进行赌轮法(蒙特卡罗法) ,再采用精英策略。
交叉:交叉互换的重要特征是它能产生不同于父体的子体。交叉概率越大,交叉操作的可能性也越大;如果交叉率太低,收敛速度可能降低。单阈值分割由于只有一个参数,所以采用一点交叉,在此设置交叉概率为0.6。
变异:变异概率为0.1。
终止准则:规定当算法执行到最大代数(终止条件) 或经过l5代进化,群体中的最高适应度值仍未发生变化(稳定条件) 时,算法停止运行,具有最高适应度值的个体即为分割阈值。
5.3 KSW 双阈值分割的遗传算法设计
编码:将单阈值分割中的8位二进制码串改为16位,前8位表示一个门限值,后8位表示另一个门限值。
人口模型:双阈值分割属于多参数遗传程序设计,在此设置人口数为20,繁殖代数为100。
解码:对二进制染色体数组解码为两个0~255之间的数作为双阈值。 适应度函数:采用(2)式为适应度值函数。同时采取对适应度函数的线性定标, 交叉:采用双点交叉,随机产生的两个交叉点分别位于前8位和后8位,交叉概率为0.6。
终止准则:在双阈值分割中,规定经过30代进化群体中的最高适应度值仍未发生变化为稳定条件。
选择和变异:同单阈值分割。
其中(1)式、(2)式分别为:H (t ) =ln P t (1-P t ) +
H t H T -H t
, +
P t 1-P t
H (S 1, S 2) =ln(∑p i ) +ln(
i =1
S 1
i =S 1+1
∑
-
S 2
p i ) +ln(
S 2
i =S 2+1
∑
n
p i )
-
∑i =1p i ln p i
∑i =1p i
S 1
S 1
∑i =S +1p i ln p i
1
∑
S 2i =S 1+1
p i
∑-
∑
n
i =S 2+1
n
p i ln p i
p i
i =S 2+1
。
下面是利用最佳直方图熵法(KSW 熵法)及传统遗传算法实现灰度图像阈值分割的matlab 代码:
%%%利用最佳直方图熵法(KSW 熵法)及传统遗传算法实现灰度图像阈值分割 %%%主程序
%%初始部分,读取图像及计算相关信息 clear; close all; clc;
I=imread('rice.bmp'); hist=imhist(I); total=0; for i=0:255
total=total+hist(i+1); end
hist1=hist/total; HT=0; for i=0:255
if hist1(i+1)==0 temp=0; else
temp=hist1(i+1)*log(1/hist1(i+1)); end
HT=HT+temp; end
%%程序主干部分
%种群随机初始化,种群数取10,染色体二进制编码取8位 t0=clock; population=10;
X0=round(rand(1,population)*255); for i=1:population
adapt_value0(i)=ksw(X0(i),0,255,hist1,HT); end
adapt_average0=mean(adapt_value0); X1=X0;
adapt_value1=adapt_value0; adapt_average1=adapt_average0; %循环搜索,搜索代数取100 generation=100; for k=1:generation
s1=select(X1,adapt_value1); s_code1=dec2bin(s1,8); c1=cross(s_code1); v1=mutation(c1); X2=(bin2dec(v1))'; for i=1:population
adapt_value2(i)=ksw(X2(i),0,255,hist1,HT); end
adapt_average2=mean(adapt_value2); if abs(adapt_average2-adapt_average1)
adapt_value1=adapt_value2; adapt_average1=adapt_average2; end end
max_value=max(adapt_value2);
number=find(adapt_value2==max_value); t_opt=round(mean(X2(number))); t1=clock;
search_time=etime(t1,t0);
%%阈值分割及显示部分 threshold_opt=t_opt/255; I1=im2bw(I,threshold_opt);
disp('灰度图像阈值分割的效果如图所示:'); disp('源图为:Fifure No.1');
disp('最佳直方图熵法及传统遗传算法阈值分割后的图像为:Fifure No.2'); figure(1); imshow(I); title('源图'); figure(2); imshow(I1);
title('最佳直方图熵法及传统遗传算法阈值分割后的图像'); disp('最佳直方图熵法及传统遗传算法阈值为:'); disp(t_opt);
disp('最佳直方图熵法及传统遗传算法阈值搜索所用时间(s ):'); disp(search_time); %%程序结束
下面是原图及用最佳直方图熵法(KSW 熵法)分割后的图像:
第五章 基于新的遗传算法的图像分割
传统遗传算法的优点:与传统算法相比,遗传算法以其简单、鲁棒性强,不需很多的先验知识等特点,使它能适应于不同的环境、问题,并且在大多数情况下都能得到最优解。
传统遗传算法的缺点:遗传算法具有高效的全局搜索能力,以及传统方法无法比拟的并行性和鲁棒性,但对于局部空间的搜索不是很有效,个体的多样性减少地很快,易出现为成熟收敛和收敛速度慢的问题,同时在整个优化过程中,多采用固定不变的进化策略,忽视了实际求解问题自身的一些基本的或显而易见的特征信息或知识。
近期出现的一些新的遗传算法,它的出发点是解决以上介绍的标准遗传算法存在的缺点。 1. 混沌遗传算法
是近年来提出的一种优化算法。其基本思想是利用混沌运动所具有的随机性、遍历性和初值敏感性。将混沌状态引入到优化变量中,把混沌运动的遍历范围扩大到优化变量的取值范围,并在一定程度上利用遗传算法的基本框架。与遗传算法相比,混沌遗传算法显著地提高了计算效率。 2. 量子遗传算法
它是量子计算思想与遗传算法结合的产物。与遗传算法类似,它也是一个产生 —检验的过程,但其实现跟标准遗传算法不一样。量子遗传算法表现出比标准遗传算法更好的种群多样性、更强的全局搜索能力和更快的收敛速度。 3. 免疫遗传算法
借鉴生命科学中的免疫概念,在遗传算法中引入免疫算子,通过基于个体浓度的自适应调节操作,使基因不断优化,从而找到最优个体。既保证了解群分布的多样性,又提高了算法的局部搜索能力。
结论
图像分割是图像处理和计算机视觉中基本技术,是大多数图像处理和视觉系统过程的重要预处理阶段。在图像分割过程中,最关键的就是找到最优阈值。遗传算法的整体搜索策略和优化搜索方法能够快速准确地得到基于整个灰度图像的阈值最优解。遗传算法作为一种优化算法,用于图像分割时,可以大大缩短寻找阈值的时间,从而有利于计算机视觉的后续处理。
本文主要介绍了图像阈值分割的几种方法。最小误差阈值法、最大类间方差法(Otsu )以及最佳直方图熵法(KSW 熵法) 等。当搜索空间越大时(如多阈值分割) ,遗传算法越有效, 在实际应用中应根据实际需要选取不同的图像分割方法。遗传算法是处理图像分割的优秀算法,图像分割效果相比于传统的图像分割算法更加优秀,但是也难免有一些缺点。
随着时代的进步,图像分割在日常生活中扮演越来越重要的角色。各种新方法的不断涌现,也使遗传算法不断完善。遗传算法用于图像分割前景广阔,并且在图像分割领域必将大放光彩。
致谢
论文写作过程是一段艰苦漫长的经历,同时也是大学毕业的一次总结。开始的时候对于遗传算法图像分割的知识并不十分了解,在老师的指导下参阅了一些书籍并且了解了相关知识。可以说本文是计算科学和数学的一种高度结合的产物,因此其难度也可想而知。
在论文完成之际,首先感谢我的导师曹军老师在论文写作过程中给予的指导和帮助。老师细心的指导和耐心的讲解让我受益匪浅。特别在论文进行和完成期间,导师作为我学习路上的领路人,更是让我认识到成功不是一蹴而就的,不断的积累才是走向成功的基石,正是如此在论文完成的过程中更是充分认识到自己的不足,以及知识积累的重要性。
另外论文创作期间,同组同学的积极配合,认真的研究、讨论也是论文得以完成的重要原因。在此向他们表示感谢!
最后,向在学习中所有给予过我帮助和支持的老师、同学、朋友及家人再次表示感谢!
参考文献:
[1]刘直芳、朱敏. 数字图像处理与分析. 清华大学出版社.2006.
[2]夏良正. 数字图像处理. 东南大学出版社.1999.
[3]章毓晋、图像分割. 北京科学出版.2001.
[4]周明、孙树栋. 遗传算法原理及应用. 国防工业出版社.1999.
[5]陈国良、王东生. 遗传算法及其应用. 人民邮电出版.1996.
[6]李敏强、李全书著. 遗传算法的基础理论与应用. 科学出版社2003.