科技信息 博士・专家论坛 基于混合遗传算法硇图像分割识别方法 安徽科技学院数学系 张建华 ［摘要］本文基于遗传算法（ＧＡ）与共轭梯度法（ｃＧ），提出了一种混合算法，将其用于图像分割问题寻求最佳阈值，该方法具有遗 传算法的全局搜索能力和共轭梯度法的强大局部搜索的特点。试验结果表明，新算法具有快速收敛性和全局最优性。 ［关键词］图像分割 遗传算法 阈值共轭梯度法 ０．引言 图像分割是图像处理领域中的基本问题之一，也是自动目标识别 技术（ＡｒＩ１Ｒ）中的一项关键技术，是目标特征提取、测量、识别与跟踪的 式，确定目标函数位，ｆ＝ｍａｘ（ｗｏ（Ｕｏ－Ｖ）：＋ｗ。ｕ。一ｖ）２），其中ＷＯ和Ｗ１分别表示 其灰度值小于门限ｋ和大于门限的概率和，ｌｌｏ和Ｕ 分别表示上面两个 区间的平均灰度值，ｖ表示整幅图像的平均灰度，ｆ的值越大，图像分割 基础，在遥感卫星图像分析，机械自动化，医学，军事等方面得到广泛的 应用。 图像分割的好坏直接影响图像的后处理。阈值法【・１是一种简单有效 和区域分割算法中具有代表性的一类主要分割方法，可分为全局阈值 法和局部阈值法。如何选取最佳阈值一直是一个比较难解决的问题。许 多学者做了大量的工作，如０ｔｓｕ ２提出的最大类间方差法和Ｄｕｎｎ等口幌 出的均匀化误差阈值选取法等。Ｏｓｔｕ法是阈值分割的经典算法，但该算 法采用穷尽法求最佳阈值，计算时间长，对于灰度直方图的灰度级分布 谷底不明显的复杂图像，单一使用Ｏｓｔｕ准则并不能从图像中稳定可靠 地将目标分割出来且效果不理想。 张金龙等嘴图像阈值分割问题转化为优化问题并利用基本ＧＡ方 法寻求最优解。遗传算法可以改进传统阈值法的分割效 ，但基本ＧＡ 算法容易出现早熟，收敛性差等缺点，给图像分割的阈值寻优带来较大 的困难。共轭梯度法是无约束优化算法中重要算法之一，计算公式简 单，存贮量少，效率高且有很好的局部搜索能力，但其全局搜索能力较 差。基于以上各算法的优缺点，本文提出了基于共轭梯度法的混合遗传 算法，结合Ｏｓｔｕ算法，使之能保证算法的收敛性，避免早熟现象，以便 快速求出最优图像分割阈值。 １．遗传算法与共轭梯度法 １．１遗传算法的基本思想 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程中 的计算模型，由Ｊ．Ｈｏｌｌａｎｄ教授 于１９７５年首先提出。基本的遗传算法流 程描述如下： （１）初始化，随机产生初始群体； （２）根据适应值函数的定义，计算各个体的适应值； （３）根据染色体的比例信息选择父代； （４）以一点交换和两点相结合，固定Ｐ。和自适应Ｐ 相结合的方法， 对随机选出的２个个体进行交换操作； （５）以普通变异和大变异相结合，固定Ｐ 和自适应Ｐ 相结合的方 法对每一个个体进行变异运算； （６）若满足则停止准则，得到全局最优解，算法收敛，否则，则转（２）。 １．２共轭梯度法 共轭梯度法 是最速下降法的一个改进，其基本思想是最速下降法 与共轭性的结合。具体过程描述如下： （１）在ｓ内取初值 及精度ｅ＞Ｏ； （２）计算舻 ｘ ，令ｓ 一ｇ￣ｋ＝０； （３）ｘ［ｋ＋ ｘ ｋｓ∞， “＝Ｖｆ（ｘａ＋ ９，其中 ＝ａｒｇ ａｒｉｎ ｆ（ｘ￣／＋Ｘｋｓ ； （４）若ｌｌ 。ｌ１≤￡，迭代结束，否则转（５）； （５）若ｋ＜ｎ一１，计算 ｋ＋ｌ＝｝１ ｇｋ＋１ ｌ Ｉ／Ｉ ｌｇｋ ，ｓ —ｇｋ ＋ＩＸ¨ｓ∞，令ｋ＝ｋ＋１， 转（３），若ｋ＝ｎ—ｌ，令 ＝ ，转（２）。 ２．混合遗传算法的图像分割 本文所提出的混合遗传算法基于ＧＡ算法，把ＣＧ算法作为重要操 作算子加入其中，其主要思想在传统遗传算法中引入局部搜索过程，通 过编码过程将所得的局部最优解变换为新的个体，以便以一个性能较 优的新群体为基础来进行下一代的遗传进化操作。Ｏｔｓｕ法求阈值的过 程本质就是求最优解的过程，故可用混合遗传算法来完成此工作。 混合遗传算法结合Ｏｔｓｕ算法的主要步骤描述如下： （１）编码：由于图像灰度值在０—２５５之间，采用二进制编码方法，将 各个染色体编码为８位二进制码，它代表某个分割阈值； （２）种群初始化：初始群体的规模影响遗传算法的执行效率和结果， 在实验中种群个数为２Ｏ个，最大繁殖代数为５０代； （３）适应度计算：本文采用Ｏｔｓｕ法进行图像分割时质量的测试公 基金项目：本文系安徽科技学院引进人才项目（ＺＲＣ２００８１７２）。 ——８—— 的质量越好； （４）选择运算：采用赌轮选择法； （５）交叉运算：采用双点交叉； （６）变异运算： （７）经交叉，变异后得到的种群进行共轭梯度法，搜索局部最优解， 得到新的群体； （８）对新群体进行选择； （９）重复（５）一（８）； （１０）终止条件：当算法执行到最大代数（终止条件）群体中的最高 适应值仍未发生变化，算法终止，此时具有最高适应值的个体即为最佳 阈值。 ３．实验结果及分析 为验证算法的有效性，选取２５６ｘ２５６的Ｌｅｎａ图像，采用最大类问 方差法，遗传算法和混合遗传算法对图像进行分割实验。令种群规模为 ２０个种群，最大繁殖代数５Ｏ，交叉概率为０．６，变异概率为０．０１，实验环 境为Ｍａｔｌａｂ ７．１。 基于Ｏｔｓｕ法，遗传算法和混合遗传算法进行图像分割的阈值及运 算时间如下表所示。 表１图像阈值及运行时间 Ｏｓｔｕ法 ＧＡ法 混合ＧＡ法 实验 次数 阈值 时间 阈值 时间 阈值 时间 ｍｓ） （ｍｓ） （ｍｓ） １ １０８ ２６＿３ｌ６ ｌ２４ １３．５Ｏ６ １２３ １０．１０６ ２ １０８ ２６．４８７ ｌ２８ ｌ３．５７１ ｌ２４ １０．０９８ ３ １０８ ２６．５３０ ｌ３０ ｌ３．５９５ １２３ ｌ０１０３６ ４ １０８ ２６．５２４ １２４ ｌ３．６ｏ７ ｌ２３ １０．０７３ 从表１可以看出，混合遗传算法能有效减少阈值计算时间，加快收 敛速度，其稳定性好于基本ＧＡ算法。 参考文献 ｌ １ ｊＬｏｕ ｘ Ｐ，Ｔｉａｎ Ｊ，Ｚｈｕ Ｇ Ｙ，ｅｔ ａ１．Ａ ｓｕｒｖｅｙ Ｏｉｌ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ［Ｊ］．Ｐａｔｔｅｍ Ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ Ａｒｔｉｉｆｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ，１９９９，１２（３）： ３００－３１２ ［２］Ｏｔｓｕ Ｎ，Ｔｈｒｅｓｈｏｌｄ Ａ．Ｓｄｅｃｆｉｏｎ ｍｅｔｈｏｄ ｆｒｏｍ ｇｒａｙｌｅｖｄ ｈｉｓｔｏｇｒａｍｓ ｌＪｊ ＩＥＥＥ Ｔｒａｎｓ，ＳＭＣ９，１９８９（１），６２—６６ 『３］ＤＵＮＮ ＳＭ，ＨＡＫＷＯＯＤ Ｄ，ＤＡＶ ＩＳ Ｌ Ｓ．Ｌｏｃａｌ ｅｓｉｔｍａｔｉｏｎ ｏｆ ｔｈｅ ｕｎｉ２ ｆｏｒｍ ｅｒｒｏｒ ｔｈｒｅｓｈｏｌｄ［ｌ＿Ｊ．ＩＥＥＥ Ｔｒａｍ ｏｎ Ｐａｔｔ ｌ＂Ｉ１ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅ ｎｉｇｅｎｃｅ，１９８４，６（６）：７４２—７４５ ［４］张金龙，赵芙生．基于遗传算法的三维重构图像闽值分割［Ｊ］．南 京师范大学学报：工程技术版，２００５，５（１）：５—７ ［５］王朝晖，李莉，李引生等．基于遗传算法的生物组织图像最佳挖取 点寻优［Ｔ］光学精密工程，２００５，１３（２）：２３１－２３６ ［６］ＨＯＬＬＡＮＤ Ｊ Ｈ．Ａｄａｐｔａｔｉｏｎ ｉｎ ｎａｔｕｒｅ ａｎｄ ａｒｔｉｉｆｃｉａｌ ｓｙｓｔｅｍｓ【Ｍ Ｊ． Ｃａｍｂｒｉｄｇｅ：ＭＩＴ Ｐｒｅｓｓ，１９９２ ［７］潘美芹等．基于共轭梯度法的函数优化混合遗传算法［Ｊ］．山东 科技大学学报，２（Ｘ）０，ｆ４） １０－１３
