遗传算法及其在图像分割中的应用

遗传算法及其在图像分割中的应用目录遗传算法简介图像分割简介一维最大熵阈值分割二维最大熵阈值分割2023/1/132a遗传算法简称GA〔GeneticAlgorithms〕遗传算法是20世纪60~70年代主要由美国JohnHolland教授提出。其内涵哲理启迪于自然界生物从低级、简单到高级、复杂，乃至人类这样一个漫长而绝妙的进化过程。借鉴Darwin的物竞天择、优胜劣汰、适者生存的自然选择和自然遗传的机理。其本质是一种求解问题的高效并行全局搜索方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法2023/1/133a遗传算法根本思想从初始化的群体出发，通过随机选择(复制)〔使群体中优秀的个体有更多的时机传给下一代〕，交叉〔表达了自然界中群体内个体之间的信息交换〕，和变异〔在群体中引入新的变种确保群体中信息的多样性〕等遗传操作，使最具有生存能力的染色体以最大可能生存,群体一代一代地进化到搜索空间中越来越好的区域.2023/1/134a根本遗传算法的构成要素(1)染色体编码方法根本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集{0，1}组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：x；就可表示一个个体，该个体的染色体长度是l＝18。(2)个体适应度评价根本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的时机多少。

2023/1/135a(3)遗传算子根本遗传算法使用下述三种遗传算子：•选择运算：使用比例选择算子；•交叉运算：使用单点交叉算子；•变异运算：使用根本位变异算子。

(4)根本遗传算法的运行参数根本遗传算法有下述4个运行参数需要提前设定：•M：群体大小，即群体中所含个体的数量，一般取为20~100。•T：遗传运算的终止进化代数，一般取为100~500•pc：交叉概率，一般取为•pm：变异概率，一般取为2023/1/136a根本遗传算法的形式化定义根本遗传算法可定义为一个7元组：GA＝(M,F,s,c,m,pc,pm)M——群体大小；F——个体适应度评价函数；s——选择操作算于；c——交叉操作算子：m——变异操作算于；pc——交叉概率；pm——变异概率；2023/1/137a根本遗传算法描述ProcedureGABegininitializeP(0);t=0;while(t<=T)dofori=1toMdoEvaluatefitnessofP(t);endforfori=1toMdoSelectoperationtoP(t);endforfori=1toM/2doCrossoveroperationtoP(t);endforfori=1toMdoMutationoperationtoP(t);endforfori=1toMdoP(t+1)=P(t);endfort=t+1endwhileend2023/1/138a根本遗传算法的实现根据上面对根本遗传算法构成要素的分析和算法描述，我们可以很方便地用计算机语言来实现这个根本遗传算法。现对具体实现过程中的问题作以下说明：一〕编码与解码(1)编码假设某一参数的取值范围是[umin,umax]，用长度为l的二进制编码符号串来表示该参数，那么它总共能够产生2l种不同的编码，参数编码时的对应关系如下：00000000…00000000＝0umin00000000…00000001＝1umin+00000000…00000010＝2umin+2……11111111…11111111=2l–1umax2023/1/139a其中，为二进制编码的编码精度，其公式为：(2)解码

假设某一个体的编码是：那么对应的解码公式为：2023/1/1310a二〕个体适应度评价一般情况下，根据目标函数值来进行种群中个体适应度值的计算。

(1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度F(X)就等于相应的目标函数值f(X)，即：

F(X)＝f(X)

(2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：

minf(X)＝max(-f(X))

2023/1/1311a三〕选择算子(1)选择算子或复制算子的作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。(2)最常用和最根本的选择算子：比例选择算子。(3)比例选择算子：指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。

(4)执行比例选择的手段是轮盘选择。轮盘法的根本精神是：个体被选中的概率取决于个体的相对适应度：pi=fi/fi(i=1,2,…,M)式中pi——个体i被选中的概率；fi——个体i的适应度；fi——群体的累加适应度。

2023/1/1312a选择算子轮盘赌选择特点：每次选择一个个体。假设要选择n个个体，那么要单独运行n次。2023/1/1313a轮盘选择例如上述轮盘选择过程，可描述如下：Ⅰ.顺序累计群体内各个体的适应度，得相应的累计值Si，最后一个累计值为Sn；Ⅱ.在[0,Sn]区间内产生均匀分布的随机数r；Ⅲ.依次用Si与r比较，第一个出现Si大于或等于r的个体j被选为复制对象；Ⅳ.重复Ⅲ、Ⅳ项，直至新群体的个体数目等于父代群体的规模。2023/1/1314a交叉算子(1)交叉算子作用通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。(2)最常用和最根本——单点交叉算子。(3)单点交叉算子的具体计算过程如下：Ⅰ.对群体中的个体进行两两随机配对。假设群体大小为M，那么共有[M/2]对相互配对的个体组。Ⅱ.每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。假设染色体的长度为l，那么共有(l-1)个可能的交叉点位置。Ⅲ.对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的局部染色体，从而产生出两个新的个体。

2023/1/1315a单点交叉交叉算子2023/1/1316a变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机地改变遗传基因〔表示染色体的符号串的某一位〕的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变为0，或由0变为1。变异算子假设只有选择和交叉，而没有变异，那么无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。2023/1/1317a变异算子根本位变异算子是最简单和最根本的变异操作算子。对于根本遗传算法中用二进制编码符号串所表示的个体，假设需要进行变异操作的某一基因座上的原有基因值为0，那么变异操作将该基因值变为1，反之，假设原有基因值为1，那么变异操作将其变为0。

根本位变异因子的具体执行过程是：Ⅰ.对个体的每一个基因座，依变异概率pm指定其为变异点。Ⅱ.对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。

2023/1/1318a开始Gen=0编码随机产生M个初始个体满足终止条件?计算群体中各个体适应度从左至右依次执行遗传算子j=0j=0j=0根据适应度选择复制个体选择两个交叉个体选择个体变异点执行变异执行交叉执行复制将复制的个体添入新群体中将交叉后的两个新个体添入新群体中将变异后的个体添入新群体中j=j+1j=j+2j=j+1

j=M?

j=pc·M?

j=pm·L·M?Gen=Gen+1输出结果终止YNYYYNNNpcpm2023/1/1319a实例：遗传算法求函数极值

利用遗传算法求函数的极大值2023/1/1320a假设用长度为20位的二进制编码串来表示决策变量x。20位二进制编码串可以表示从0到1048575之间的1048576个不同的数，故将x的定义域离散化为1048576个均等的区域，包括两个端点在内共有1048576个不同的离散点。从离散点-1到离散点2，分别对应于从00000000000000000000(0)到(1048575)之间的二进制编码。实例：遗传算法求函数极值〔1〕编码方案2023/1/1321a〔2〕确定解码方法：解码时需要将20位长的二进制编码转换为对应的十进制整数，分别记为y。依据个体编码方法和对定义域的离散化方法可知，将代码y转换为变量x的解码公式为例如，对个体实例：遗传算法求函数极值2023/1/1322a〔3〕确定个体评价方法：由于优化目标是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即实例：遗传算法求函数极值〔4〕设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用根本位变异算子。〔5〕确定遗传算法的运行参数：群体大小M=40，终止进化代数G=25，选择概率真Ps=0.90,交叉概率，变异概率。

2023/1/1323a采用上述方法进行仿真，经过迭代，最正确样本为即当时，函数具有极大值，极大值为。实例：遗传算法求函数极值2023/1/1324a实例：遗传算法求函数极值最后一代个体分布每代最优个体分布2023/1/1325a图像分割图像分割是自动目标识别的关键和首要步骤,其目的是将目标和背景别离,为计算机视觉的后续处理提供依据。通常图像分割包括阈值法、边缘检测法和区域跟踪法。其中阈值法是图像分割的常用方法。目前，已有众多的阈值分割方法，如最小误差阈值法、最大类别方差法(Otsu法)及最正确直方图熵法。Kapur等人所提出的最正确熵阈值方法(简称为KSW熵法)，不需要先验知识，而且对于非理想双峰直方图的图像也可以进行分割。但在确定阈值时，尤其是确定多阈值时，计算量很大。遗传算法是一具有鲁棒性、并行性的优化算法,因此利用遗传算法实现KSW最正确熵阈值确定法，可以缩短寻找阈值的时间，从而有利于计算机视觉的后续处理。2023/1/1326a图像分割简介图像分割是将图像分成假设干个互不相交的各具特性的区域，并提取出感兴趣目标的技术和过程。

图像分割的定义

图像局部特性的相似性和互斥性可作为图像分割的依据，即：区域内部的灰度相似性和区域之间的灰度突变性。

灰度图像分割的依据2023/1/1327a图像分割简介基于阈值的分割——通过阈值对不同物体进行分割基于边缘的分割——先确定边缘像素，并把它们连接在一起，以构成所需的边界基于区域的分割——把各像素划归到各个物体或区域中

图像分割的分类2023/1/1328a阈值分割

阈值分割的原理利用图像中要提取的目标物与其背景在灰度特性上的差异，把图像视为具有不同灰度级的两类区域(目标和背景)的组合，选取一个适宜的阈值，以确定图像中每个象素点应该属于目标还是背景区域，从而产生相应的二值图像。2023/1/1329a阈值分割设原始图像f(x,y)，以一定的准那么在f(x,y)中找出一个适宜的灰度值，作为阈值T，那么分割后的图像g(x,y)，可由下式表示：g(x,y)=1f(x,y)≥T0f(x,y)<Tg(x,y)=1f(x,y)≤T0f(x,y)>Tg(x,y)=1T1≤f(x,y)≤T20其它g(x,y)=f(x,y)f(x,y)≥T0其它2023/1/1330a阈值分割阈值化分割算法主要有两个步骤：(1)确定需要的分割阈值；(2)将分割阈值与像素值比较以划分像素。2023/1/1331a最大熵阈值分割根本思想将信息论中Shannon熵概念用于图像分割，测量图像灰度直方图的熵，由此找出最正确阈值，其出发点是使图像中目标与背景分布的信息量最大。利用图像的灰度分布密度函数定义图像的信息熵，根据假设的不同或视角的不同提出不同的熵准那么，最后通过优化该准那么得到阈值。2023/1/1332a一维最大熵阈值分割所谓灰度的一维熵最大：就是选择一个阈值，使图像用这个阈值分割出的两局部的一阶灰度统计的信息量最大。

根据Shannon熵的概念,对于灰度范围{0,1,⋯,L-1}的图像直方图,其熵测量为2023/1/1333a一维最大熵阈值分割目标区域和背景区域的熵分别定义为：其中PiiOBt一维直方图2023/1/1334a一维最大熵阈值分割定义熵函数为：其中当熵函数取最大值时对应的灰度值t*就是所求的最正确阈值，即：目标函数2023/1/1335a遗传算法实现〔1〕编码：由于图像灰度值在0～255之间，故将各个染色体编码为8位二进制码，它代表某个分割阈值。〔2〕初始种群：随机产生。初始种群的个体为随机产生的,其相应的适应度值也各有上下。设置种群大小为10，最大繁殖代数为50。〔3〕解码：对二进制染色体数解码为0～255之间的值，以计算其适应度值。〔4〕适应度函数：采用上式为适应度值函数。〔5〕选择算子：进行轮盘赌算法。选择概率。〔6〕交叉算子：采用单点交叉，交叉概率为。〔7〕变异算子：变异概率为0.01.〔8〕终止准那么：当算法执行到最大代数时停止运行，具有最高适应度值的个体即为分割阈值。2023/1/1336a实验结果方法阈值时间（s）遗传算法1180.043穷举法1180.073原始图像分割结果2023/1/1337a一维最大熵阈值分割缺点：由于一维最大熵阈值分割基于图像的原始直方图，仅仅利用了点灰度信息，而未充分利用图像的空间信息，所以当信噪比降低时，分割效果不理想。启发：在图像特征中，点灰度是最根本的特征，但它对噪声敏感；区域灰度特征包含了局部空间信息，且对噪声的敏感程度低于点灰度特征。综合利用点灰度特征和区域灰度特征，可以较好的表征图像的信息。2023/1/1338a二维最大熵阈值分割根本思想：利用点灰度和区域灰度均值的二维直方图，根据熵最大原那么寻找最正确阈值。

首先以原始灰度图像(L个灰度级)中各象素及其8邻域组为一个区域，计算出区域灰度均值图像(L个灰度级)，这样原始图像中的每个象素都对应一个点灰度-区域灰度均值对，这样的数据对存在L×L种可能的取值。

做法：2023/1/1339a二维最大熵阈值分割设ni,j为图像中点灰度为i及其区域灰度均值为j的象素点数，pi,j为点灰度-区域灰度均值对(i,j)发生的概率，那么那么{pi,j,i,j=0,1,……L-1}就是该图像关于点灰度-区域灰度均值的二维直方图。2023/1/1340a二维最大熵阈值分割结论：1.在强噪声干扰下，一维直方图是单峰的，二维直方图利用了图像邻域的相关信息，目标和背景的双峰仍然明显；2023/1/1341a二维最大熵阈值分割2.点灰度-区域灰度均值的概率顶峰主要出现在XOY平面的对角线附近，并且在总体上呈现双峰和一谷的状态；这是由于图像的所有象素中，目标点和背景点所占比例最大，而目标区域和背景区域内部象素灰度级比较均匀，点灰度及其区域灰度均值相差不大，所以都集中在对角线附近，两个峰分别对应于目标和背景；远离XOY平面对角线的坐标处，峰的高度急剧下降，这局部所反映的是图像中的噪声点、边缘点和杂散点。2023/1/1342a二维最大熵阈值分割二维直方图的XOY平面图目标背景边界噪声3.应该在A区和B区上用点灰度-区