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

遗传算法及其在图像分割中的应用 2020 4 5 2 目录 遗传算法简介图像分割简介一维最大熵阈值分割二维最大熵阈值分割 2020 4 5 3 遗传算法简称GA GeneticAlgorithms 遗传算法是20世纪60 70年代主要由美国JohnHolland教授提出 其内涵哲理启迪于自然界生物从低级 简单到高级 复杂 乃至人类这样一个漫长而绝妙的进化过程 借鉴Darwin的物竞天择 优胜劣汰 适者生存的自然选择和自然遗传的机理 其本质是一种求解问题的高效并行全局搜索方法 它能在搜索过程中自动获取和积累有关搜索空间的知识 并自适应地控制搜索过程以求得最优解 遗传算法 2020 4 5 4 遗传算法基本思想 从初始化的群体出发 通过随机选择 复制 使群体中优秀的个体有更多的机会传给下一代 交叉 体现了自然界中群体内个体之间的信息交换 和变异 在群体中引入新的变种确保群体中信息的多样性 等遗传操作 使最具有生存能力的染色体以最大可能生存 群体一代一代地进化到搜索空间中越来越好的区域 2020 4 5 5 基本遗传算法的构成要素 1 染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体中的个体 其等位基因由二值符号集 0 1 组成 初始群体中各个个体的基因值用均匀分布的随机数来生成 如 x 100111001000101101就可表示一个个体 该个体的染色体长度是l 18 2 个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少 2020 4 5 6 3 遗传算子基本遗传算法使用下述三种遗传算子 选择运算 使用比例选择算子 交叉运算 使用单点交叉算子 变异运算 使用基本位变异算子 4 基本遗传算法的运行参数基本遗传算法有下述4个运行参数需要提前设定 M 群体大小 即群体中所含个体的数量 一般取为20 100 T 遗传运算的终止进化代数 一般取为100 500 pc 交叉概率 一般取为0 4 0 99 pm 变异概率 一般取为0 0001 0 1 2020 4 5 7 基本遗传算法的形式化定义 基本遗传算法可定义为一个7元组 GA M F s c m pc pm M 群体大小 F 个体适应度评价函数 s 选择操作算于 c 交叉操作算子 m 变异操作算于 pc 交叉概率 pm 变异概率 2020 4 5 8 基本遗传算法描述 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 1endwhileend 2020 4 5 9 基本遗传算法的实现 根据上面对基本遗传算法构成要素的分析和算法描述 我们可以很方便地用计算机语言来实现这个基本遗传算法 现对具体实现过程中的问题作以下说明 一 编码与解码 1 编码假设某一参数的取值范围是 umin umax 用长度为l的二进制编码符号串来表示该参数 则它总共能够产生2l种不同的编码 参数编码时的对应关系如下 00000000 00000000 0umin00000000 00000001 1umin 00000000 00000010 2umin 2 11111111 11111111 2l 1umax 2020 4 5 10 其中 为二进制编码的编码精度 其公式为 2 解码假设某一个体的编码是 则对应的解码公式为 2020 4 5 11 二 个体适应度评价 一般情况下 根据目标函数值来进行种群中个体适应度值的计算 1 当优化目标是求函数最大值 并且目标函数总取正值时 可以直接设定个体的适应度F X 就等于相应的目标函数值f X 即 F X f X 2 对于求目标函数最小值的优化问题 理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题 即 minf X max f X 2020 4 5 12 三 选择算子 1 选择算子或复制算子的作用 从当前代群体中选择出一些比较优良的个体 并将其复制到下一代群体中 2 最常用和最基本的选择算子 比例选择算子 3 比例选择算子 指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比 4 执行比例选择的手段是轮盘选择 轮盘法的基本精神是 个体被选中的概率取决于个体的相对适应度 pi fi fi i 1 2 M 式中pi 个体i被选中的概率 fi 个体i的适应度 fi 群体的累加适应度 2020 4 5 13 选择算子 轮盘赌选择特点 每次选择一个个体 若要选择n个个体 则要单独运行n次 2020 4 5 14 轮盘选择示例 上述轮盘选择过程 可描述如下 顺序累计群体内各个体的适应度 得相应的累计值Si 最后一个累计值为Sn 在 0 Sn 区间内产生均匀分布的随机数r 依次用Si与r比较 第一个出现Si大于或等于r的个体j被选为复制对象 重复 项 直至新群体的个体数目等于父代群体的规模 2020 4 5 15 交叉算子 1 交叉算子作用通过交叉 子代的基因值不同于父代 交换是遗传算法产生新个体的主要手段 正是有了交换操作 群体的性态才多种多样 2 最常用和最基本 单点交叉算子 3 单点交叉算子的具体计算过程如下 对群体中的个体进行两两随机配对 若群体大小为M 则共有 M 2 对相互配对的个体组 每一对相互配对的个体 随机设置某一基因座之后的位置为交叉点 若染色体的长度为l 则共有 l 1 个可能的交叉点位置 对每一对相互配对的个体 依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体 从而产生出两个新的个体 2020 4 5 16 单点交叉 交叉算子 2020 4 5 17 变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变 它以很小的概率随机地改变遗传基因 表示染色体的符号串的某一位 的值 在染色体以二进制编码的系统中 它随机地将染色体的某一个基因由1变为0 或由0变为1 变异算子 若只有选择和交叉 而没有变异 则无法在初始基因组合以外的空间进行搜索 使进化过程在早期就陷入局部解而进入终止过程 从而影响解的质量 为了在尽可能大的空间中获得质量较高的优化解 必须采用变异操作 2020 4 5 18 变异算子 基本位变异算子是最简单和最基本的变异操作算子 对于基本遗传算法中用二进制编码符号串所表示的个体 若需要进行变异操作的某一基因座上的原有基因值为0 则变异操作将该基因值变为1 反之 若原有基因值为1 则变异操作将其变为0 基本位变异因子的具体执行过程是 对个体的每一个基因座 依变异概率pm指定其为变异点 对每一个指定的变异点 对其基因值做取反运算或用其它等位基因值来代替 从而产生出一个新的个体 2020 4 5 20 实例 遗传算法求函数极值 利用遗传算法求函数的极大值 2020 4 5 21 假如用长度为20位的二进制编码串来表示决策变量x 20位二进制编码串可以表示从0到1048575之间的1048576个不同的数 故将x的定义域离散化为1048576个均等的区域 包括两个端点在内共有1048576个不同的离散点 从离散点 1到离散点2 分别对应于从00000000000000000000 0 到11111111111111111111 1048575 之间的二进制编码 实例 遗传算法求函数极值 1 编码方案 2020 4 5 22 2 确定解码方法 解码时需要将20位长的二进制编码转换为对应的十进制整数 分别记为y 依据个体编码方法和对定义域的离散化方法可知 将代码y转换为变量x的解码公式为例如 对个体 实例 遗传算法求函数极值 2020 4 5 23 3 确定个体评价方法 由于优化目标是求函数的最大值 故可将个体的适应度直接取为对应的目标函数值 即 实例 遗传算法求函数极值 4 设计遗传算子 选择运算使用比例选择算子 交叉运算使用单点交叉算子 变异运算使用基本位变异算子 5 确定遗传算法的运行参数 群体大小M 40 终止进化代数G 25 选择概率真Ps 0 90 交叉概率Pc 0 70 变异概率Pm 0 01 2020 4 5 24 采用上述方法进行仿真 经过迭代 最佳样本为即当时 函数具有极大值 极大值为3 8503 实例 遗传算法求函数极值 2020 4 5 25 实例 遗传算法求函数极值 最后一代个体分布 每代最优个体分布 2020 4 5 26 图像分割 图像分割是自动目标识别的关键和首要步骤 其目的是将目标和背景分离 为计算机视觉的后续处理提供依据 通常图像分割包括阈值法 边缘检测法和区域跟踪法 其中阈值法是图像分割的常用方法 目前 已有众多的阈值分割方法 如最小误差阈值法 最大类别方差法 Otsu法 及最佳直方图熵法 Kapur等人所提出的最佳熵阈值方法 简称为KSW熵法 不需要先验知识 而且对于非理想双峰直方图的图像也可以进行分割 但在确定阈值时 尤其是确定多阈值时 计算量很大 遗传算法是一具有鲁棒性 并行性的优化算法 因此利用遗传算法实现KSW最佳熵阈值确定法 可以缩短寻找阈值的时间 从而有利于计算机视觉的后续处理 2020 4 5 27 图像分割简介 图像分割是将图像分成若干个互不相交的各具特性的区域 并提取出感兴趣目标的技术和过程 图像分割的定义 图像局部特性的相似性和互斥性可作为图像分割的依据 即 区域内部的灰度相似性和区域之间的灰度突变性 灰度图像分割的依据 2020 4 5 28 图像分割简介 基于阈值的分割 通过阈值对不同物体进行分割基于边缘的分割 先确定边缘像素 并把它们连接在一起 以构成所需的边界基于区域的分割 把各像素划归到各个物体或区域中 图像分割的分类 2020 4 5 29 阈值分割 阈值分割的原理 利用图像中要提取的目标物与其背景在灰度特性上的差异 把图像视为具有不同灰度级的两类区域 目标和背景 的组合 选取一个合适的阈值 以确定图像中每个象素点应该属于目标还是背景区域 从而产生相应的二值图像 2020 4 5 30 阈值分割 设原始图像f x y 以一定的准则在f x y 中找出一个合适的灰度值 作为阈值T 则分割后的图像g x y 可由下式表示 2020 4 5 31 阈值分割 阈值化分割算法主要有两个步骤 1 确定需要的分割阈值 2 将分割阈值与像素值比较以划分像素 2020 4 5 32 最大熵阈值分割 基本思想 将信息论中Shannon熵概念用于图像分割 测量图像灰度直方图的熵 由此找出最佳阈值 其出发点是使图像中目标与背景分布的信息量最大 利用图像的灰度分布密度函数定义图像的信息熵 根据假设的不同或视角的不同提出不同的熵准则 最后通过优化该准则得到阈值 2020 4 5 33 一维最大熵阈值分割 所谓灰度的一维熵最大 就是选择一个阈值 使图像用这个阈值分割出的两部分的一阶灰度统计的信息量最大 根据Shannon熵的概念 对于灰度范围 0 1 L 1 的图像直方图 其熵测量为 2020 4 5 34 一维最大熵阈值分割 目标区域和背景区域的熵分别定义为 其中 一维直方图 2020 4 5 35 一维最大熵阈值分割 定义熵函数为 其中 当熵函数取最大值时对应的灰度值t 就是所求的最佳阈值 即 目标函数 2020 4 5 36 遗传算法实现 1 编码 由于图像灰度值在0 255之间 故将各个染色体编码为8位二进制码 它代表某个分割阈值 2 初始种群 随机产生 初始种群的个体为随机产生的 其相应的适应度值也各有高低 设置种群大小为10 最大繁殖代数为50 3 解码 对二进制染色体数解码为0 255之间的值 以计算其适应度值 4 适应度函数 采用上式为适应度值函数 5 选择算子 进行轮盘赌算法 选择概率0 9 6 交叉算子 采用单点交叉 交叉概率为0 6 7 变异算子 变异概率为0 01 8 终止准则 当算法执行到最大代数时停止运行 具有最高适应度值的个体即为分割阈值 2020 4 5 37 实验结果 原始图像分割结果 2020 4 5 38 一维最大熵阈值分割 缺点 由于一维最大熵阈值分割基于图像的原始直方图 仅仅利用了点灰度信息 而未充分利用图像的空间信息 所以当信噪比降低时 分割效果不理想 启发 在图像特征中 点灰度是最基本的特征 但它对噪声敏感 区域灰度特征包含了部分空间信息 且对噪声的敏感程度低于点灰度特征 综合利用点灰度特征和区域灰度特征 可以较好的表征图像的信息 2020 4 5 39 二维最大熵阈值分割 基本思想 利用点灰度和区域灰度均值的二维直方图 根据熵最大原则寻找最佳阈值 首先以原始灰度图像 L个灰度级 中各象素及其8邻域组为一个区域 计算出区域灰度均值图像 L个灰度级 这样原始图像中的每个象素都对应一个点灰度 区域灰度均值对 这样的数据对存在L L种可能的取值 做法 2020 4 5 40 二维最大熵阈值分割 设ni j为图像中点灰度为i及其区域灰度均值为j的象素点数 pi j为点灰度 区域灰度均值对 i j 发生的概率 则 则 pi j i j 0 1 L 1 就是该图像关于点灰度 区域灰度均值的二维直方图 2020 4 5 41 二维最大熵阈值分割 结论 1 在强噪声干扰下 一维直方图是单峰的 二维直方图利用了图像邻域的相关信息 目标和背景的双峰仍然明显 2020 4 5 42 二维最大熵阈值分割 2 点灰度 区域灰度均值的概率高峰主要出现在XOY平面的对角线附近 并且在总体上呈现双峰和一谷的状态 这是由于图像的所有象素中 目标点和背景点所占比例最大 而目标区域和背景区域内部象素灰度级比较均匀 点灰度及其区域灰度均值相差不大 所以都集中在对角线附近 两个峰分别对应于目标和背景 远离XOY平面对角线的坐标处 峰的高度急剧下降 这部分所反映的是图像中的噪声点 边缘点和杂散点 2020 4 5 43 二维最大熵阈值分割 二维直方图的XOY平面图 3 应该在A区和B区上用点灰度 区域灰度均值二维最大熵法确定最佳阈值 使真正代表目标和背景的信息量最大 2020 4 5 44 二维最